Un saut vers le propriétaire : comment le client Zaris route une clé

Il y a deux façons honnêtes de construire un client de cache distribué. La première est de choisir n'importe quel nœud, de lui envoyer la requête, et de laisser le cluster la relayer en interne vers celui qui possède la clé — simple côté client, mais chaque requête qui atterrit sur le mauvais nœud paie un saut réseau supplémentaire à l'intérieur du cluster. La seconde est de rendre le client assez intelligent pour savoir quel nœud possède la clé avant d'envoyer quoi que ce soit, de sorte que la première socket qu'il touche soit celle qui peut réellement répondre. Zaris prend la seconde voie. Un GET quitte votre processus déjà adressé au nœud qui détient la clé — pas de proxy, pas de saut de relais, pas de coordinateur au milieu.

Cet article est la vue de l'intérieur de son fonctionnement : la fonction qui transforme une clé en propriétaire, la table de correspondance que le client garde en mémoire, et — la partie facile à rater — comment le client reste correct quand la possession bouge pendant que votre trafic est en vol.

La revendication, énoncée précisément

Quand vous appelez client.GetAsync("user:42"), le client fait trois choses avant qu'aucun octet n'atteigne le réseau :

1. Hacher la clé en un segment. Une fonction pure mappe la chaîne de clé à l'un des segments du cluster.
2. Rechercher le propriétaire du segment. Un tableau en mémoire mappe ce segment directement à l'unique connexion qui atteint son nœud propriétaire actif.
3. Envoyer en direct au propriétaire. La requête passe par cette connexion et nulle part ailleurs.

Aucune étape ne consulte un routeur central. L'étape 1 est de l'arithmétique, les étapes 2 et 3 sont un index de tableau et une écriture de socket. Le client détient une connexion par nœud et une petite table de routage, et c'est tout l'appareillage. L'ingénierie intéressante n'est pas le chemin heureux — c'est de garder cette table honnête.

Étape 1 — la clé devient un segment

Zaris hache les clés exactement comme le fait un client Redis Cluster, à dessein. La fonction de placement vit dans SegmentMapper, et son commentaire de doc est brutal sur pourquoi elle a l'air de ce qu'elle a l'air :

// Maps a key to its segment. Placement is aligned to the Redis Cluster slot model so a Redis cluster client
// (which routes by CRC16(key) % 16384) and Zaris agree on where a key lives: the key's Redis slot is
// computed the exact Redis way (XMODEM CRC16 over the hash-tag, mod 16384), then the 16384 slots are mapped
// proportionally onto the cluster's segments.
// This is the SINGLE shared placement function used by both the client and the server.

Cette dernière ligne est celle qui compte le plus. Ce n'est pas « le client calcule le placement d'une façon et le serveur le valide d'une autre ». C'est le même code, compilé dans l'assembly client et l'assembly serveur, produisant le même segment pour la même clé à chaque fois. Si le client et le serveur étaient en désaccord sur l'endroit où vit une clé, chaque écriture serait un pile ou face entre atterrir sur le propriétaire et atterrir sur un nœud qui doit la rejeter. Partager la fonction rend cette classe de bug irreprésentable.

Le calcul lui-même est deux manœuvres :

public static ushort ComputeSegmentId(string key, int shardCount, ...)
{
    var slot = ComputeSlot(key);                 // CRC16(hash-tag) % 16384
    return SlotToSegment(slot, shardCount);      // proportional slot -> segment
}

// The Redis Cluster key slot: XMODEM CRC16 over the hash-tag (or the whole key), mod 16384.
public static int ComputeSlot(string key)
{
    var (start, len) = HashTagRange(key);
    return Crc16(key, start, len) % RedisSlots;  // RedisSlots = 16384
}

D'abord la clé est réduite à un slot dans la plage fixe [0, 16384) en utilisant XMODEM CRC16 — le même polynôme CRC16-CCITT (0x1021, init 0x0000) qu'utilise Redis. Puis les 16384 slots sont mappés proportionnellement sur le nombre de segments que le cluster possède réellement :

public static ushort SlotToSegment(int slot, int shardCount)
    => (ushort)((long)slot * shardCount / RedisSlots);

Deux slots peuvent atterrir dans le même segment ; un segment est une plage contiguë de slots. Cet alignement est ce qui permet à Zaris de répondre correctement à CLUSTER SLOTS pour un client Redis Cluster tout en routant par son propre modèle de segment en interne — les deux vues sont la même vue à des résolutions différentes.

Hash tags : décider ce qui se co-localise

Il y a une échappatoire délibérée dans le hachage des clés. Si une clé contient un groupe {...} avec au moins un caractère à l'intérieur des accolades, seuls les octets à l'intérieur des accolades sont hachés :

// Redis hash tag: if the key contains "{...}" with at least one char between the braces, only that
// substring is hashed (so "{u1}:a" and "{u1}:b" co-locate). Otherwise the whole key is hashed.

C'est ainsi que vous forcez des clés apparentées sur le même segment. {u1}:profile et {u1}:sessions hachent toutes deux sur u1, donc elles partagent un segment et par conséquent un propriétaire — ce qui est exactement ce dont vous avez besoin pour une transaction multi-clés ou toute opération qui doit toucher plusieurs clés atomiquement sur un nœud. Les clés sans tag s'étalent sur tout le keyspace. Le client et le serveur s'accordent là-dessus aussi, car c'est le même HashTagRange des deux côtés.

Un détail de plus à noter pour le chemin chaud : la boucle CRC16 a un chemin rapide tout-ASCII qui hache les caractères comme des octets sans allocation, et ne retombe sur un encodage UTF-8 que pour les clés non-ASCII. Router chaque opération signifie que cela s'exécute à chaque opération, donc il a été écrit pour ne pas allouer dans le cas courant.

Étape 2 — le segment devient une connexion

Le client a maintenant un numéro de segment. Il lui faut le nœud qui le possède actuellement. Le client garde une RoutingTable immuable dont les champs sont toute l'histoire :

// one live connection per node, keyed by node id
public ImmutableDictionary<string, ZarisRemoteClient> Clients { get; init; }

// segment -> the active-owner client it routes to (the precomputed answer)
public ZarisRemoteClient?[] SegmentMap { get; init; }

// segment -> partition, and partition -> owning node id
public ushort[] SegmentToPartition { get; init; }
public ImmutableDictionary<int, string?> RuntimeOwners { get; init; }

Le choix de conception clé est SegmentMap. C'est un tableau, indexé par segment, dont les entrées sont déjà résolues vers la connexion du propriétaire de ce segment. Router une clé n'est pas un parcours de graphe de segment à partition à nœud à connexion au moment de la requête — cette résolution est faite à l'avance quand la table est construite, de sorte que le coût par requête est un seul index de tableau :

internal ZarisRemoteClient GetClientForKey(string key)
{
    var table = _routing;
    return GetClientForSegment(
        SegmentMapper.ComputeSegmentId(key, table.TotalSegments),
        table);
}

private static ZarisRemoteClient GetClientForSegment(ushort segment, RoutingTable table)
{
    if (segment >= table.SegmentMap.Length)
        throw new InvalidOperationException($"No client mapped for segment {segment} — map may be mid-update, retry");

    if (table.SegmentMap[segment] is not { } client)
    {
        var partitionId = segment < table.SegmentToPartition.Length
            ? table.SegmentToPartition[segment] : -1;
        throw new PartitionUnavailableException(partitionId, segment);
    }
    return client;
}

Clients détient exactement un ZarisRemoteClient — une connexion — par nœud. Le client n'ouvre pas une socket fraîche par requête ou par clé ; il multiplexe tout le trafic d'un nœud sur l'unique connexion de ce nœud, et SegmentMap pointe simplement de nombreux segments vers le même objet de connexion (l'égalité de référence les déduplique quand le client a besoin de l'ensemble distinct des propriétaires actifs, par exemple pour éventailler un scan). Donc le coût mémoire de la conscience des partitions est d'une connexion par nœud plus quelques tableaux dimensionnés au nombre de segments — il ne croît pas avec le nombre de clés ou de requêtes.

Le bénéfice est qu'il n'y a aucun nœud dans le cluster dont le travail est de recevoir des requêtes mal routées et de les relayer. Chaque requête bien routée est servie par le premier nœud qu'elle atteint. Cela retire tout un étage du budget de latence et, tout aussi important, de la surface de défaillance — vous ne pouvez pas perdre une requête dans un saut de relais qui n'existe pas. (La pièce compagnon sur le plancher de latence parcourt ce qui reste dans le budget une fois le saut de proxy parti.)

Étape 3 — la map bouge sous vos pieds

Voici la partie difficile. La table de routage est un cache d'un fait — « le segment S est possédé par le nœud N » — que le cluster peut changer à tout moment. Un propriétaire peut tomber et un réplica est promu ; une partition peut être migrée pour faire grandir ou drainer un nœud. À l'instant où cela arrive, le SegmentMap[S] du client pointe vers une connexion qui n'est plus le propriétaire. Un client qui ferait aveuglément confiance à sa table enverrait des écritures à un nœud qui les refusera correctement.

Zaris garde la table honnête de trois façons, par ordre de préférence.

Push — le serveur prévient le client. Quand la possession change, le cluster émet un RuntimeOwnershipChangedEvent, et le client a un handler abonné dessus :

public Task HandleAsync(IServerEvent @event)
{
    if (@event is RuntimeOwnershipChangedEvent runtimeEvent)
        _router.TryUpdateRuntimeOwnership(runtimeEvent);
    return Task.CompletedTask;
}

TryUpdateRuntimeOwnership ne reconstruit pas toute la table. Il clone le tableau SegmentMap, repointe seulement les segments dont la partition a réellement changé de propriétaire, et échange la table immuable en place par une seule assignation de référence. Les lecteurs ne voient jamais une table à moitié mise à jour — ils lisent soit l'ancienne soit la nouvelle, jamais un mélange déchiré. C'est du routage copy-on-write : le cas courant (rien n'a changé) ne coûte rien, et un changement ne touche que les segments affectés.

Poll — un garde-fou lent. Un timer rafraîchit la map du cluster toutes les dix secondes quoi qu'il arrive, de sorte que même si un événement push est manqué (une reconnexion, une notification perdue), la vue du client s'auto-répare en un intervalle :

private readonly TimeSpan _pollInterval = TimeSpan.FromSeconds(10);

React — la requête elle-même corrige la map. La dernière ligne de défense est la requête qui route mal. Si le client envoie à un nœud qui n'est plus le propriétaire, le nœud ne la relaie pas silencieusement — il renvoie un statut qui dit au client que sa map est périmée, et le helper de réessai rafraîchit et réessaie :

private static bool RequiresMapRefresh(KvStatus status)
    => status == KvStatus.Moved
       || status == KvStatus.ReplicaWriteRejected
       // Ownership is mid-handoff: the client must force-fetch the updated
       // ownership and retry against the node that now owns the segment.
       || status == KvStatus.OwnershipChanging;

Quand une op réessayable revient Moved, OwnershipChanging ou ReplicaWriteRejected, le client appelle son hook de rafraîchissement et réessaie — une boucle bornée de quelques tentatives avec un bref backoff, pas une rotation sans fin. Il y a une leçon subtile cuite dans le code actuel ici : une version antérieure rafraîchissait la map à chaque tentative de réessai, ce qui, sous un fort churn de nœuds, transformait une seule op défaillante en des dizaines de rafraîchissements tous sérialisés derrière un verrou. La correction a été de ne rafraîchir que lorsque le statut dit réellement « votre map est fausse », pas simplement parce qu'une tentative a échoué. Le traitement plus profond de cette discipline de réessai a son propre article — les réessais sous churn de possession — mais la version en une ligne est : une map périmée est une condition qui se corrige d'elle-même, et la correction est bon marché précisément parce qu'elle est rare et ciblée.

Les trois mécanismes se superposent : le push rend le cas courant instantané, le poll rend un push manqué consistant à terme, et le réessai réactif rend toute obsolescence résiduelle invisible à votre appel — il prend juste un aller-retour supplémentaire à l'instant où la possession a bougé, et est correct dès l'appel suivant.

Pourquoi le faire côté client du tout ?

Le routage conscient des partitions côté client coûte quelque chose. Le client doit porter un modèle du cluster, le garder frais, et expédier la même logique de placement qu'utilise le serveur. Une conception fondée sur un proxy pousse tout cela dans le cluster et laisse le client rester bête. Alors pourquoi payer ?

Parce que l'alternative paie à chaque requête, à jamais. Un proxy ou une conception « envoyez n'importe où, on le relaiera » ajoute un saut au chemin chaud de chaque opération — un saut qui est pure surcharge, présent même quand rien n'a échoué et rien ne bouge. Zaris paie le coût du routage une fois, d'avance, et seulement à nouveau quand la possession change réellement — ce qui, dans un cluster sain, n'arrive presque jamais. Le régime permanent est un index de tableau et une écriture de socket vers le bon nœud. C'est toute la raison pour laquelle les lectures montent avec vos cœurs au lieu de goulotter sur un étage intermédiaire : il n'y a pas d'étage intermédiaire sur quoi goulotter.

Et cela se compose avec tout le reste. La même résolution GetClientForKey est ce par quoi une surveillance de clé, un incrément de compteur, un compare-and-swap et une opération de structure de données à clé unique routent tous, donc ils héritent tous de la livraison directe au propriétaire et de la même map auto-réparante. Le client n'est pas un tuyau bête avec du routage boulonné dessus ; le routage est ce qu'est le client.

Les compromis honnêtes

Le routage direct au propriétaire n'est pas sans bords, et il vaut la peine de les nommer.

• Le client doit atteindre chaque nœud. Parce qu'il n'y a pas de proxy, le client ouvre une connexion vers chaque nœud vers lequel il route. Dans un réseau plat c'est un non-problème ; à travers une frontière — disons un client hors de Kubernetes — ces nœuds doivent être adressables individuellement. C'est exactement le problème que l'adressage de client externe existe pour résoudre, et c'est une conséquence directe de l'absence de porte d'entrée unique.
• Un bref retard de map est possible, pas une perte. Dans la fenêtre entre le déplacement de la possession et le moment où le client l'apprend, une requête peut router vers l'ancien propriétaire. Elle est rejetée et réessayée, pas mal appliquée — le chemin réactif ci-dessus garantit que le réessai atterrit sur le vrai propriétaire. Vous payez un aller-retour, pas une mauvaise réponse.
• La fonction de placement est un contrat de compatibilité. Parce que le client et le serveur partagent SegmentMapper, vous ne pouvez pas changer la façon dont les clés hachent vers les segments sans que les deux côtés s'accordent — ce qui est précisément pourquoi le hachage a été aligné sur le modèle de slot Redis stable plutôt que sur un schéma interne qui pourrait dériver.

Dit simplement : le client Zaris sait où vivent vos clés, garde ce savoir à jour sans que vous y pensiez, et dépense un saut réseau — celui qui fait réellement le travail — à chaque opération. L'habileté n'est pas dans le chemin rapide, qui est délibérément ennuyeux. Elle est dans les trois mécanismes discrets qui gardent le chemin rapide correct pendant que le cluster se remodèle en dessous.