Aller au contenu principal

Parcourir un keyspace qui ne tient pas en place : comment SCAN itère un cluster

· 11 minutes de lecture
Clustron Team
Clustron Team
Ingénierie des systèmes distribués

De nombreux segments triés fusionnés en un flux ordonné et paginé

Un GET à clé unique est facile à raisonner : hacher la clé, trouver son propriétaire, demander à ce seul nœud. SCAN est le genre d'opération opposé. Il n'a pas de clé — il pose une question sur tout le keyspace : donne-moi chaque clé dans cette plage, une page à la fois. Et dans un store partitionné et répliqué, ce keyspace n'est pas une seule chose en un seul endroit. Il est réparti sur 256 segments étalés sur autant de nœuds que vous en exécutez, chaque nœud ne détenant que les tranches qu'il possède actuellement, et l'ensemble est en cours d'écriture pendant que vous itérez. Il n'y a pas d'index trié global à parcourir. Alors d'où vient l'ordre, que pointe exactement un jeton de reprise, et qu'arrive-t-il à votre scan quand une clé est écrite — ou qu'une partition se déplace — en plein milieu ?

Cet article suit un SCAN à travers les trois couches qui le servent réellement : un seul segment, un seul nœud, et le client qui recoud les nœuds ensemble. Chaque couche résout une pièce du problème, et les limites honnêtes de l'opération découlent de la façon dont ces pièces s'emboîtent.

La requête : une plage et une taille de page, pas une clé​

Un scan est décrit par deux petits objets. Un KeyRange dit quelles clés — un début, une fin ou un préfixe, chacun optionnel :

public sealed class KeyRange
{
    public string? Start  { get; set; }
    public string? End    { get; set; }
    public string? Prefix { get; set; }
}

Et ScanOptions dit comment les délivrer — quelle taille de page, s'il faut expédier les valeurs ou juste les clés, une limite stricte optionnelle, et un jeton de reprise pour continuer un appel précédent :

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; }
}

Rien ici ne nomme un nœud ou un segment. C'est tout l'enjeu : l'appelant décrit ce qu'il veut, et les trois couches en dessous déterminent où cela réside et dans quel ordre le rendre.

Couche un : un segment se scanne lui-même, sans verrou et dans l'ordre​

La plus petite unité qui peut répondre à une partie d'un scan est un segment — l'unité de stockage partitionné de Zaris, soutenue par un ConcurrentDictionary d'enregistrements vivants. Un dictionnaire n'a pas d'ordre, donc la première chose dont un scan de segment a besoin est une vue triée de ses clés. La construire à chaque page serait ruineux, donc chaque segment conserve un snapshot trié de clés, immuable et mis en cache et ne le reconstruit que lorsque le jeu de clés change :

// 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;

Le tableau est assigné une fois et jamais muté ; une reconstruction concurrente produit simplement un nouveau tableau et échange la référence. Cela signifie que le parcours du scan lui-même ne prend aucun verrou du tout — il fait une recherche binaire jusqu'à la clé de départ et avance dans l'ordre ordinal, lisant les enregistrements vivants depuis le dictionnaire concurrent au fur et à mesure. Les lectures et écritures sur le segment ne bloquent jamais le scan, et le scan ne les bloque jamais.

Deux sortes de clés sont silencieusement passées au fil du parcours :

if (!_data.TryGetValue(key, out var record)) continue;        // vanished since snapshot
if (record.IsDeleted || ExpirationManager.IsExpired(record, now)) continue;  // tombstone / TTL

Une clé supprimée est une pierre tombale (tombstone) — un enregistrement réel marqué IsDeleted, car une suppression doit être un enregistrement, pas une absence, pour que la réplication la transporte. Le scan les filtre, ainsi que les clés dont le TTL est écoulé mais dont le balayeur ne s'est pas encore déclenché. Le snapshot trié de clés est donc un sur-ensemble de ce que vous verrez ; expiration et suppression sont résolues contre l'enregistrement vivant au moment de la lecture, pas figées dans le snapshot.

Le parcours s'arrête à PageSize et renvoie un ResumeToken. Voici le premier détail honnête : au niveau du segment, le jeton est essentiellement un décalage (offset) — un décompte du nombre d'entrées correspondantes déjà renvoyées (ReturnedSoFar). Un scan de segment repris refait une recherche binaire jusqu'à la même clé de départ et saute ce nombre de correspondances avant d'émettre. C'est une position-par-décompte, pas une position-par-clé.

cursor.ReturnedSoFar += taken;
bool hasMore = results.Count >= pageSize && cursor.ReturnedSoFar < totalLimit;

Ce choix compte pour ce que l'opération promet, et nous y reviendrons.

Couche deux : un nœud fusionne ses segments en un seul flux ordonné​

Un nœud possède de nombreux segments — pas les 256, juste ceux mappés aux partitions qu'il sert actuellement. Un scan au niveau du nœud doit présenter tous ces segments comme un seul résultat ordonné, car l'appelant a demandé une plage, pas le segment 42. C'est un problème de fusion classique : chaque segment peut produire ses clés dans l'ordre trié, et vous voulez l'union triée.

Donc la première page d'un scan de nœud fait exactement cela. Elle rassemble un fetcher pour chaque segment possédé localement et exécute une fusion k-voies à travers eux avec une file de priorité, comparant les clés de façon ordinale :

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

Le résultat fusionné et ordonné est matérialisé dans un buffer détenu par un RouterQueryCoordinator — une session côté serveur de courte durée enregistrée sous un QueryId fraîchement frappé :

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 };

Chaque page suivante n'est qu'une tranche de ce buffer, et le jeton de reprise du nœud porte le QueryId pour que l'appel suivant retrouve la même session :

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).");
}

C'est le deuxième détail honnête, et c'est un vrai compromis. Un scan au niveau du nœud est à état (stateful) : la pagination est stable et l'ordre par nœud est exact, mais le prix est que le nœud matérialise tout son keyspace possédé et fusionné dans un buffer quand le scan commence, et détient une session pour la durée de vie de l'itération. Les scans sont un outil d'administration et d'itération en masse, pas un curseur de streaming à mémoire constante sur des milliards de clés — et un jeton de reprise n'est valable que contre le nœud et la session qui l'ont frappé. Laissez cette session expirer, ou tentez de la reprendre ailleurs, et vous obtenez un bruyant « session not found » plutôt qu'une réponse silencieusement fausse.

Couche trois : le client s'éventaille et entrelace les propriétaires​

Un nœud répond pour les segments qu'il possède. Un scan de cluster doit couvrir chaque propriétaire, donc le ScanClusterClient côté client ouvre un scan contre chaque nœud en parallèle et entrelace leurs pages à mesure qu'elles arrivent, plutôt que de vider un nœud avant de commencer le suivant :

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));

Ce parallélisme est pourquoi LimitCount demande du soin. Chaque nœud traite la limite comme un plafond par nœud ; si le client ne l'imposait pas aussi, un LimitCount de 1 000 contre quatre propriétaires pourrait renvoyer jusqu'à 4 000 lignes une fois fusionnées. Donc la couche cluster applique la limite comme un plafond total strict et cesse d'émettre une fois qu'elle est atteinte — tout en continuant à vider jusqu'au bout la page en vol de chaque propriétaire, car disposer d'un énumérateur asynchrone en plein déplacement n'est pas permis et les résultats par nœud sont de toute façon déjà bornés :

if (emitted < limit)
{
    yield return enumerator.Current;
    emitted++;
}
// keep draining siblings even past the cap; do not yield-break mid-move

La conséquence à clarifier : au sein de la contribution d'un seul nœud, les clés arrivent dans l'ordre ; entre les nœuds elles sont entrelacées par ordre d'arrivée, donc un scan de cluster complet n'est pas trié globalement sauf si vous le demandez explicitement. (Le chemin Search apparenté porte bien SortFields et fusionne avec un comparateur pour exactement cette raison.) Si vous avez besoin de chaque clé du cluster dans l'ordre ordinal, triez le résultat assemblé ; SCAN lui-même garantit l'ordre par propriétaire et l'exhaustivité, pas un tri global.

Ce qu'un SCAN promet — et ne promet pas​

Mettez les trois couches ensemble et le vrai contrat de l'opération est visible, sans que rien n'en soit caché :

  • Ce n'est pas un snapshot ponctuel du cluster. Chaque nœud matérialise son propre buffer fusionné quand son scan commence, et ces moments ne coïncident pas. Les écritures qui atterrissent sur un nœud avant que son buffer ne soit construit sont incluses ; celles d'après ne le sont pas. Il n'y a pas de gel à l'échelle du cluster.
  • Les clés supprimées et expirées ne font jamais surface. Les pierres tombales et les enregistrements au TTL écoulé sont filtrés contre l'enregistrement vivant au fil du parcours du segment, donc un scan reflète le contenu logique, pas physique.
  • La reprise est position-par-décompte à l'intérieur d'une session. Parce que le curseur par segment est un décalage, une clé insérée ou retirée avant la position courante entre deux pages peut décaler la frontière — un scan concurrent à une forte mutation de la plage scannée peut, en principe, répéter ou sauter une clé autour de la couture. Un scan d'une plage au repos est exact. C'est la même famille de garantie que donne le SCAN de Redis — une itération complète au mieux, pas un niveau d'isolation snapshot — et c'est le bon compromis pour un store non ordonné et écrit en concurrence.
  • Le keyspace peut bouger sous vos pieds. Le client s'éventaille vers les propriétaires qui existent au démarrage du scan. Les partitions peuvent migrer ou basculer en pleine itération ; un scan est un balayage au mieux d'un cluster vivant, ce qui est pourquoi c'est l'outil de l'export en masse, de la réindexation et des requêtes d'administration plutôt que des lectures transactionnelles. Pour le read-your-writes sur une clé unique, routez vers le propriétaire à la place.

Aucune de ces propriétés n'est un bug à masquer ; ce sont la forme honnête de l'itération d'un keyspace non ordonné, partitionné et en mutation sans arrêter le monde. La conception rend le cas courant et bon marché rapide — un snapshot trié sans verrou et une fusion par nœud — et est explicite sur les bords.

Une note sur le front-end RESP​

Les clients Redis atteignent la même machinerie via KEYS et SCAN sur le front-end RESP, qui se mappent sur le scan natif. Une mise en garde à énoncer sans détour : le SCAN RESP est aujourd'hui en un seul coup — il vide le scan natif et répond avec le curseur 0 (itération terminée) en un aller-retour, plutôt que de filer le curseur incrémental de Redis à travers chaque appel. Il est honnête sur l'exhaustivité, pas encore incrémental. Le client natif est celui qui pagine avec un jeton de reprise.

Une opération, trois couches honnêtes​

Un GET touche un propriétaire et une clé ; un SCAN touche chaque propriétaire et demande à chacun de produire sa tranche d'un tout ordonné. Le travail se divise proprement : un segment transforme un dictionnaire non ordonné en un parcours trié sans verrou ; un nœud fusionne ses segments en un seul flux ordonné et paginé de façon stable derrière un curseur de session ; le client s'éventaille sur les propriétaires, entrelace leurs pages, et impose le seul plafond que l'éventail casserait autrement. Chaque couche est simple en soi, et les garanties de l'opération — ordre par propriétaire, exhaustivité sur une plage au repos, pas d'isolation snapshot, pas de gel global — sont exactement ce que ces trois couches simples peuvent honnêtement délivrer ensemble.