Einen Keyspace scannen, der nicht stillhält: Wie SCAN einen Cluster durchläuft
Ein einzelnes GET auf einen Key ist leicht zu durchdenken: den Key hashen, den Owner finden, genau diesen einen Node fragen. SCAN ist die gegenteilige Art von Operation. Es hat keinen Key — es stellt eine Frage über den gesamten Keyspace: Gib mir jeden Key in diesem Bereich, Seite für Seite. Und in einem partitionierten, replizierten Store ist dieser Keyspace nicht eine Sache an einem Ort. Er ist über 256 Segmente verteilt, die auf so viele Nodes entfallen, wie Sie betreiben, wobei jeder Node nur die Ausschnitte hält, die er gerade besitzt, und während Sie iterieren, wird in die Gesamtheit geschrieben. Es gibt keinen globalen sortierten Index zum Durchlaufen. Woher kommt also die Ordnung, worauf zeigt ein Resume-Token genau, und was passiert mit Ihrem Scan, wenn mittendrin ein Key geschrieben wird — oder eine Partition umzieht?
Dieser Beitrag folgt einem SCAN durch die drei Schichten, die ihn tatsächlich bedienen: ein einzelnes Segment, ein einzelner Node und der Client, der die Nodes zusammenfügt. Jede Schicht löst ein Teilstück des Problems, und die ehrlichen Grenzen der Operation ergeben sich daraus, wie diese Teile zusammenpassen.
Die Anfrage: ein Bereich und eine Seitengröße, kein Key
Ein Scan wird durch zwei kleine Objekte beschrieben. Ein KeyRange sagt, welche Keys — ein Start, ein Ende oder ein Präfix, jeweils optional:
public sealed class KeyRange
{
public string? Start { get; set; }
public string? End { get; set; }
public string? Prefix { get; set; }
}
Und ScanOptions sagt, wie sie geliefert werden — wie groß eine Seite ist, ob Werte oder nur Keys übertragen werden, ein optionales hartes Limit und ein Resume-Token, um einen vorherigen Aufruf fortzusetzen:
public sealed class ScanOptions
{
public int PageSize { get; set; } = 100;
public bool IncludeValues { get; set; } = true;
public bool IncludeMetadata{ get; set; } = false;
public string? ResumeToken { get; set; }
public int? LimitCount { get; set; }
}
Nichts davon nennt einen Node oder ein Segment. Das ist der Punkt: Der Aufrufer beschreibt, was er will, und die drei Schichten darunter finden heraus, wo es liegt und in welcher Reihenfolge es zurückgegeben wird.
Schicht eins: ein Segment scannt sich selbst, lock-frei und geordnet
Die kleinste Einheit, die einen Teil eines Scans beantworten kann, ist ein Segment — die Einheit der partitionierten Speicherung in Zaris, gestützt auf ein ConcurrentDictionary mit Live-Records. Ein Dictionary hat keine Ordnung, also braucht ein Segment-Scan zuerst eine sortierte Sicht seiner Keys. Diese bei jeder Seite neu aufzubauen wäre ruinös, daher hält jedes Segment einen gecachten, unveränderlichen Snapshot sortierter Keys und baut ihn nur neu auf, wenn sich die Key-Menge ändert:
// No lock held during scan — the snapshot is immutable once built.
var sortedKeys = GetOrBuildSortedKeys();
int startIdx = BinarySearchKey(sortedKeys, startKey, StringComparer.Ordinal);
if (startIdx < 0) startIdx = ~startIdx;
Das Array wird einmal zugewiesen und nie verändert; ein nebenläufiger Neuaufbau erzeugt einfach ein neues Array und tauscht die Referenz. Der Scan-Durchlauf selbst nimmt also überhaupt keinen Lock — er sucht per Binärsuche den Start-Key und läuft in ordinaler Reihenfolge vorwärts, wobei er Live-Records aus dem Concurrent-Dictionary liest. Lese- und Schreibzugriffe auf das Segment blockieren den Scan nie, und der Scan blockiert sie nie.
Zwei Arten von Keys werden beim Durchlaufen stillschweigend übersprungen:
if (!_data.TryGetValue(key, out var record)) continue; // vanished since snapshot
if (record.IsDeleted || ExpirationManager.IsExpired(record, now)) continue; // tombstone / TTL
Ein gelöschter Key ist ein Tombstone — ein echter Record, der als IsDeleted markiert ist, weil ein Löschvorgang ein Record sein muss und keine Abwesenheit, damit die Replikation ihn weitertragen kann. Der Scan filtert diese heraus, ebenso Keys, deren TTL abgelaufen ist, deren Sweeper aber noch nicht gelaufen ist. Der Snapshot der sortierten Keys ist also eine Obermenge dessen, was Sie sehen; Ablauf und Löschung werden beim Lesen gegen den Live-Record aufgelöst und nicht im Snapshot eingefroren.
Der Durchlauf stoppt bei PageSize und liefert ein ResumeToken. Hier ist das erste ehrliche Detail: Auf Segmentebene ist das Token im Wesentlichen ein Offset — eine Zählung, wie viele passende Einträge bereits zurückgegeben wurden (ReturnedSoFar). Ein fortgesetzter Segment-Scan sucht erneut per Binärsuche denselben Start-Key und überspringt so viele Treffer, bevor er ausgibt. Es ist eine Position per Zählung, kein Seek per Key.
cursor.ReturnedSoFar += taken;
bool hasMore = results.Count >= pageSize && cursor.ReturnedSoFar < totalLimit;
Diese Wahl ist wichtig für das, was die Operation verspricht, und wir kommen darauf zurück.
Schicht zwei: ein Node führt seine Segmente zu einem einzigen geordneten Strom zusammen
Ein Node besitzt viele Segmente — nicht alle 256, sondern die, die den Partitionen zugeordnet sind, die er gerade bedient. Ein Scan auf Node-Ebene muss alle davon als ein geordnetes Ergebnis präsentieren, weil der Aufrufer nach einem Bereich gefragt hat, nicht nach Segment 42. Das ist ein klassisches Merge-Problem: Jedes Segment kann seine Keys sortiert liefern, und gewünscht ist die sortierte Vereinigung.
Die erste Seite eines Node-Scans tut genau das. Sie sammelt einen Fetcher für jedes lokal besessene Segment und führt mit einer Prioritätswarteschlange einen k-Wege-Merge über sie aus, wobei Keys ordinal verglichen werden:
var heap = new PriorityQueue<(KvResult<ZarisEntry> Item, int Source), KvResult<ZarisEntry>>(comparison);
// seed with the head of each segment, then repeatedly pop the smallest
// key and pull the next from that segment's enumerator
Das zusammengeführte, geordnete Ergebnis wird in einen Buffer materialisiert, der von einem RouterQueryCoordinator gehalten wird — einer kurzlebigen, serverseitigen Session, die unter einer frisch erzeugten QueryId registriert ist:
coord = new RouterQueryCoordinator();
await coord.InitScanAsync(fetchers, ct); // drains + merges every owned segment
var id = _coordManager.Register(coord);
cursor = new QueryCursor { QueryId = id, ReturnedSoFar = 0 };
Jede weitere Seite ist nur eine Scheibe dieses Buffers, und das Resume-Token des Nodes trägt die QueryId, damit der nächste Aufruf dieselbe Session findet:
if (!string.IsNullOrEmpty(options?.ResumeToken))
{
cursor = QueryCursor.Deserialize(options.ResumeToken);
if (!_coordManager.TryGet(cursor.QueryId, out coord))
throw new InvalidOperationException($"Search session {cursor.QueryId} not found (expired or cleaned).");
}
Das ist das zweite ehrliche Detail, und es ist ein echter Kompromiss. Ein Scan auf Node-Ebene ist zustandsbehaftet: Das Paging ist stabil und die Ordnung pro Node exakt, aber der Preis ist, dass der Node beim Beginn des Scans seinen gesamten besessenen, zusammengeführten Keyspace in einen Buffer materialisiert und für die Dauer der Iteration eine Session hält. Scans sind ein Werkzeug für Administration und Massen-Iteration, kein Streaming-Cursor mit konstantem Speicherbedarf über Milliarden von Keys — und ein Resume-Token gilt nur gegenüber dem Node und der Session, die es erzeugt haben. Lassen Sie diese Session ablaufen oder versuchen Sie, an anderer Stelle fortzusetzen, erhalten Sie ein lautes „Session nicht gefunden" statt einer still falschen Antwort.
Schicht drei: Der Client verteilt per Fan-out und verzahnt die Owner
Ein Node antwortet für die Segmente, die er besitzt. Ein Cluster-Scan muss jeden Owner abdecken, daher öffnet der clientseitige ScanClusterClient einen Scan gegen jeden Node parallel und verzahnt deren Seiten, sobald sie eintreffen, statt einen Node vollständig abzuarbeiten, bevor der nächste beginnt:
var enumerators = clients
.Select(c => c.Scan.ScanAsync(range, options, ct).GetAsyncEnumerator(ct))
.ToList();
// advance all owners concurrently; yield whichever produces next
var finishedTask = await Task.WhenAny(pending.Select(p => p.Task));
Diese Parallelität ist der Grund, warum LimitCount Sorgfalt braucht. Jeder Node behandelt das Limit als Obergrenze pro Node; würde der Client es nicht zusätzlich durchsetzen, könnte ein LimitCount von 1.000 gegen vier Owner nach dem Zusammenführen bis zu 4.000 Zeilen liefern. Die Cluster-Schicht wendet das Limit daher als hartes Gesamtlimit an und liefert nichts mehr aus, sobald es erreicht ist — während sie die laufende Seite jedes Owners dennoch bis zum Ende abarbeitet, weil das Disposen eines asynchronen Enumerators mitten im Move nicht erlaubt ist und die Ergebnisse pro Node ohnehin begrenzt sind:
if (emitted < limit)
{
yield return enumerator.Current;
emitted++;
}
// keep draining siblings even past the cap; do not yield-break mid-move
Die Konsequenz, die klar benannt sein muss: Innerhalb des Beitrags eines einzelnen Nodes kommen Keys geordnet an; zwischen Nodes werden sie nach Ankunft verzahnt, sodass ein vollständiger Cluster-Scan nicht global sortiert ist, es sei denn, Sie verlangen es ausdrücklich. (Der verwandte Search-Pfad trägt aus genau diesem Grund SortFields und führt mit einem Comparator zusammen.) Wenn Sie jeden Key im Cluster in ordinaler Reihenfolge brauchen, sortieren Sie das zusammengesetzte Ergebnis; SCAN selbst garantiert Ordnung pro Owner und Vollständigkeit, keine globale Sortierung.
Was ein SCAN verspricht — und was nicht
Setzt man die drei Schichten zusammen, wird der tatsächliche Vertrag der Operation sichtbar, ohne dass etwas davon verborgen wird:
- Es ist kein Point-in-Time-Snapshot des Clusters. Jeder Node materialisiert seinen eigenen zusammengeführten Buffer, wenn sein Scan beginnt, und diese Zeitpunkte fallen nicht zusammen. Schreibzugriffe, die vor dem Aufbau des Buffers auf einem Node landen, sind enthalten; spätere nicht. Es gibt kein clusterweites Einfrieren.
- Gelöschte und abgelaufene Keys erscheinen nie. Tombstones und Records mit abgelaufener TTL werden beim Durchlaufen des Segments gegen den Live-Record gefiltert, ein Scan spiegelt also den logischen, nicht den physischen Inhalt wider.
- Das Fortsetzen ist eine Position per Zählung innerhalb einer Session. Da der Cursor pro Segment ein Offset ist, kann ein Key, der zwischen zwei Seiten vor der aktuellen Position eingefügt oder entfernt wird, die Grenze verschieben — ein Scan, der nebenläufig zu starker Mutation des gescannten Bereichs läuft, kann prinzipiell einen Key an der Nahtstelle wiederholen oder überspringen. Ein Scan eines ruhenden Bereichs ist exakt. Das ist dieselbe Garantiefamilie, die Redis
SCANbietet — eine Best-Effort-Vollständigkeits-Iteration, keine Snapshot-Isolation — und es ist der richtige Kompromiss für einen ungeordneten, nebenläufig beschriebenen Store. - Der Keyspace kann sich unter Ihnen bewegen. Der Client verteilt per Fan-out an die Owner, die beim Start des Scans existieren. Partitionen können mitten in der Iteration migrieren oder ein Failover erleben; ein Scan ist ein Best-Effort-Durchlauf eines Live-Clusters, weshalb er das Werkzeug für Massen-Export, Reindexierung und administrative Abfragen ist und nicht für transaktionale Lesezugriffe. Für Read-your-writes auf einem einzelnen Key routen Sie stattdessen zum Owner.
Nichts davon sind Bugs, die man übertünchen müsste; es ist die ehrliche Form der Iteration über einen ungeordneten, geshardeten, sich verändernden Keyspace, ohne die Welt anzuhalten. Das Design macht den billigen, häufigen Fall schnell — einen lock-freien sortierten Snapshot und einen Merge pro Node — und ist bei den Rändern ausdrücklich.
Ein Hinweis zum RESP-Front-End
Redis-Clients erreichen dieselbe Maschinerie über KEYS und SCAN auf dem RESP-Front-End, die auf den nativen Scan abgebildet werden. Ein Vorbehalt, der klar gesagt sein sollte: Das RESP-SCAN ist heute Single-Shot — es arbeitet den nativen Scan vollständig ab und antwortet in einem Round-Trip mit Cursor 0 (Iteration abgeschlossen), statt den inkrementellen Cursor von Redis durch jeden Aufruf zu fädeln. Es ist ehrlich bei der Vollständigkeit, aber noch nicht inkrementell. Der native Client ist derjenige, der mit einem Resume-Token seitenweise abruft.
Eine Operation, drei ehrliche Schichten
Ein GET berührt einen Owner und einen Key; ein SCAN berührt jeden Owner und bittet jeden, seinen Ausschnitt eines geordneten Ganzen zu liefern. Die Arbeit teilt sich sauber auf: Ein Segment macht aus einem ungeordneten Dictionary einen sortierten, lock-freien Durchlauf; ein Node führt seine Segmente zu einem geordneten, stabil seitenweisen Strom hinter einem Session-Cursor zusammen; der Client verteilt per Fan-out an die Owner, verzahnt deren Seiten und setzt das eine Limit durch, das der Fan-out sonst brechen würde. Jede Schicht ist für sich einfach, und die Garantien der Operation — Ordnung pro Owner, Vollständigkeit über einen ruhenden Bereich, keine Snapshot-Isolation, kein globales Einfrieren — sind genau das, was diese drei einfachen Schichten gemeinsam ehrlicherweise liefern können.