Ein Hop zum Owner: Wie der Zaris-Client einen Key routet

Es gibt zwei ehrliche Wege, einen Client für einen verteilten Cache zu bauen. Der erste: irgendeinen Node wählen, ihm die Anfrage senden und den Cluster sie intern an den Besitzer des Keys weiterleiten lassen — einfach für den Client, aber jede Anfrage, die auf dem falschen Node landet, zahlt für einen zusätzlichen Netzwerk-Hop innerhalb des Clusters. Der zweite: den Client klug genug machen, um zu wissen, welcher Node den Key besitzt, bevor er irgendetwas sendet, sodass der erste Socket, den er berührt, derjenige ist, der tatsächlich antworten kann. Zaris geht den zweiten Weg. Ein GET verlässt Ihren Prozess bereits an den Node adressiert, der den Key hält — kein Proxy, kein Weiterleitungs-Hop, kein Koordinator in der Mitte.

Dieser Beitrag ist der Blick ins Innere, wie das funktioniert: die Funktion, die einen Key in einen Owner verwandelt, die Lookup-Tabelle, die der Client im Speicher hält, und — der Teil, den man leicht falsch macht — wie der Client korrekt bleibt, wenn sich das Ownership bewegt, während Ihr Traffic unterwegs ist.

Die Behauptung, präzise formuliert

Wenn Sie client.GetAsync("user:42") aufrufen, tut der Client drei Dinge, bevor irgendwelche Bytes das Netzwerk berühren:

1. Den Key auf ein Segment hashen. Eine reine Funktion bildet den Key-String auf eines der Segmente des Clusters ab.
2. Den Owner des Segments nachschlagen. Ein In-Memory-Array bildet dieses Segment direkt auf die eine Verbindung ab, die den aktiven Owner-Node erreicht.
3. Owner-direkt senden. Die Anfrage geht über diese Verbindung und nirgendwo sonst hin.

Kein Schritt befragt einen zentralen Router. Schritt 1 ist Arithmetik, die Schritte 2 und 3 sind ein Array-Index und ein Socket-Schreibvorgang. Der Client hält eine Verbindung pro Node und eine kleine Routing-Tabelle, und das ist die gesamte Apparatur. Das Interessante an der Ingenieursarbeit ist nicht der Happy Path — es ist, diese Tabelle ehrlich zu halten.

Schritt 1 — der Key wird zu einem Segment

Zaris hasht Keys absichtlich genau so wie ein Redis-Cluster-Client. Die Platzierungsfunktion lebt in SegmentMapper, und ihr Doc-Kommentar ist unverblümt darüber, warum sie so aussieht, wie sie aussieht:

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

Diese letzte Zeile ist die wichtigste. Es heißt nicht „der Client berechnet die Platzierung auf die eine Weise und der Server validiert sie auf eine andere." Es ist derselbe Code, in die Client-Assembly und die Server-Assembly kompiliert, der jedes Mal dasselbe Segment für denselben Key erzeugt. Wären sich Client und Server uneinig, wo ein Key lebt, wäre jeder Schreibzugriff ein Münzwurf zwischen der Landung beim Owner und der Landung auf einem Node, der ihn ablehnen muss. Das Teilen der Funktion macht diese Klasse von Bugs nicht darstellbar.

Die Berechnung selbst besteht aus zwei Zügen:

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
}

Zuerst wird der Key mit XMODEM-CRC16 auf einen Slot im festen Bereich [0, 16384) reduziert — dasselbe CRC16-CCITT-Polynom (0x1021, Init 0x0000), das Redis verwendet. Dann werden die 16384 Slots proportional auf so viele Segmente abgebildet, wie der Cluster tatsächlich hat:

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

Zwei Slots können im selben Segment landen; ein Segment ist ein zusammenhängender Bereich von Slots. Diese Ausrichtung erlaubt es Zaris, CLUSTER SLOTS für einen Redis-Cluster-Client korrekt zu beantworten und intern dennoch nach seinem eigenen Segmentmodell zu routen — die beiden Sichten sind dieselbe Sicht in unterschiedlicher Auflösung.

Hash-Tags: entscheiden, was co-lokalisiert wird

Im Key-Hashing gibt es eine bewusste Hintertür. Enthält ein Key eine {...}-Gruppe mit mindestens einem Zeichen zwischen den Klammern, werden nur die Bytes innerhalb der Klammern gehasht:

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

So erzwingen Sie, dass zusammengehörige Keys auf demselben Segment landen. {u1}:profile und {u1}:sessions hashen beide auf u1, teilen also ein Segment und damit einen Owner — genau das, was Sie für eine Multi-Key-Transaktion oder jede Operation brauchen, die mehrere Keys atomar auf einem Node berühren muss. Keys ohne Tag verteilen sich über den gesamten Keyspace. Auch hierin sind sich Client und Server einig, denn auf beiden Seiten ist es dasselbe HashTagRange.

Ein weiteres Detail für den Hot Path: Die CRC16-Schleife hat einen reinen ASCII-Schnellpfad, der die Zeichen ohne Allokation als Bytes hasht und nur für Nicht-ASCII-Keys auf ein UTF-8-Encoding zurückfällt. Jede Operation zu routen heißt, dass dies bei jeder Operation läuft, daher wurde es so geschrieben, dass es im Normalfall nicht allokiert.

Schritt 2 — das Segment wird zu einer Verbindung

Jetzt hat der Client eine Segmentnummer. Er braucht den Node, der es gerade besitzt. Der Client hält eine unveränderliche RoutingTable, deren Felder die ganze Geschichte erzählen:

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

Die zentrale Designentscheidung ist SegmentMap. Es ist ein nach Segment indiziertes Array, dessen Einträge bereits aufgelöst sind auf die Verbindung zum Owner dieses Segments. Einen Key zu routen ist kein Graphdurchlauf von Segment über Partition und Node zur Verbindung zur Request-Zeit — diese Auflösung geschieht im Voraus, wenn die Tabelle gebaut wird, sodass die Kosten pro Request ein einziger Array-Index sind:

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 hält genau einen ZarisRemoteClient — eine Verbindung — pro Node. Der Client öffnet keinen frischen Socket pro Request oder pro Key; er multiplext den gesamten Traffic für einen Node über dessen einzelne Verbindung, und SegmentMap zeigt mit vielen Segmenten einfach auf dasselbe Verbindungsobjekt (Referenzgleichheit dedupliziert sie, wenn der Client die Menge der verschiedenen aktiven Owner braucht, zum Beispiel für den Fan-out eines Scans). Die Speicherkosten der Partitionsbewusstheit sind also eine Verbindung pro Node plus ein paar Arrays in Größe der Segmentanzahl — sie wachsen nicht mit der Zahl der Keys oder Requests.

Der Gewinn: Es gibt keinen Node im Cluster, dessen Aufgabe es ist, fehlgeroutete Requests entgegenzunehmen und weiterzuleiten. Jeder gut geroutete Request wird vom ersten Node bedient, den er erreicht. Das entfernt eine ganze Ebene aus dem Latenzbudget und, ebenso wichtig, aus der Fehlerfläche — man kann keinen Request in einem Weiterleitungs-Hop verlieren, den es nicht gibt. (Der Begleitbeitrag zum Latenzboden geht durch, was im Budget übrig bleibt, sobald der Proxy-Hop weg ist.)

Schritt 3 — die Map bewegt sich unter Ihnen

Hier kommt der schwere Teil. Die Routing-Tabelle ist ein Cache einer Tatsache — „Segment S gehört Node N" —, die der Cluster jederzeit ändern kann. Ein Owner kann ausfallen, und eine Replica wird befördert; eine Partition kann migriert werden, um einen Node zu vergrößern oder zu leeren. Sobald das geschieht, zeigt SegmentMap[S] des Clients auf eine Verbindung, die nicht mehr der Owner ist. Ein Client, der seiner Tabelle blind vertraute, würde Schreibzugriffe an einen Node senden, der sie korrekterweise ablehnt.

Zaris hält die Tabelle auf drei Wegen ehrlich, in der Reihenfolge der Präferenz.

Push — der Server sagt es dem Client. Ändert sich das Ownership, sendet der Cluster ein RuntimeOwnershipChangedEvent, und der Client hat einen Handler, der es abonniert hat:

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

TryUpdateRuntimeOwnership baut nicht die ganze Tabelle neu. Es klont das SegmentMap-Array, setzt nur die Segmente um, deren Partition tatsächlich den Owner gewechselt hat, und tauscht die unveränderliche Tabelle mit einer einzigen Referenzzuweisung aus. Leser sehen nie eine halb aktualisierte Tabelle — sie lesen entweder die alte oder die neue, nie eine zerrissene Mischung. Das ist Copy-on-Write-Routing: Der Normalfall (nichts hat sich geändert) kostet nichts, und eine Änderung berührt nur die betroffenen Segmente.

Poll — ein langsamer Backstop. Ein Timer aktualisiert die Cluster-Map unabhängig davon alle zehn Sekunden, sodass sich die Sicht des Clients selbst dann innerhalb eines Intervalls heilt, wenn ein Push-Ereignis verpasst wird (ein Reconnect, eine verlorene Benachrichtigung):

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

React — der Request selbst korrigiert die Map. Die letzte Verteidigungslinie ist der Request, der falsch routet. Sendet der Client an einen Node, der nicht mehr der Owner ist, leitet der Node ihn nicht stillschweigend weiter — er liefert einen Status zurück, der dem Client sagt, dass seine Map veraltet ist, und der Retry-Helfer aktualisiert und versucht es erneut:

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;

Kommt eine wiederholbare Operation mit Moved, OwnershipChanging oder ReplicaWriteRejected zurück, ruft der Client seinen Refresh-Hook auf und versucht es erneut — eine begrenzte Schleife mit einigen Versuchen und kurzem Backoff, kein offenes Drehen im Kreis. Im aktuellen Code steckt eine subtile Lehre: Eine frühere Version aktualisierte die Map bei jedem Retry-Versuch, was bei starkem Node-Churn eine einzelne fehlschlagende Operation in Dutzende Aktualisierungen verwandelte, die alle hinter einem Lock serialisiert waren. Die Lösung war, nur dann zu aktualisieren, wenn der Status tatsächlich sagt „Ihre Map ist falsch", nicht schon deshalb, weil ein Versuch fehlschlug. Die tiefere Behandlung dieser Retry-Disziplin ist ein eigener Beitrag — Retries bei Ownership-Churn —, aber die Kurzfassung lautet: Eine veraltete Map ist ein selbstkorrigierender Zustand, und die Korrektur ist gerade deshalb billig, weil sie selten und gezielt ist.

Die drei Mechanismen schichten sich: Push macht den Normalfall sofortig, Poll macht einen verpassten Push letztlich konsistent, und der reaktive Retry macht jede verbleibende Veraltung für Ihren Aufruf unsichtbar — er kostet im Moment des Ownership-Wechsels einen zusätzlichen Round-Trip und ist ab dem nächsten Aufruf korrekt.

Warum überhaupt auf dem Client?

Partitionsbewusstes Client-Routing kostet etwas. Der Client muss ein Modell des Clusters tragen, es aktuell halten und dieselbe Platzierungslogik mitliefern wie der Server. Ein Proxy-basiertes Design schiebt all das in den Cluster und lässt den Client dumm bleiben. Warum also zahlen?

Weil die Alternative bei jedem einzelnen Request für immer zahlt. Ein Proxy oder ein Design „an irgendwen senden, wir leiten es weiter" fügt dem Hot Path jeder Operation einen Hop hinzu — einen Hop, der reiner Overhead ist, selbst wenn nichts ausgefallen ist und nichts sich bewegt. Zaris zahlt die Kosten des Routings einmal, im Voraus, und nur dann wieder, wenn sich das Ownership tatsächlich ändert — was in einem gesunden Cluster fast nie vorkommt. Der Normalzustand ist ein Array-Index und ein Socket-Schreibvorgang zum richtigen Node. Das ist der ganze Grund, warum Lesezugriffe mit Ihren Kernen skalieren, statt an einer mittleren Ebene zum Flaschenhals zu werden: Es gibt keine mittlere Ebene, die zum Flaschenhals werden könnte.

Und es lässt sich mit allem anderen kombinieren. Dieselbe Auflösung GetClientForKey ist das, worüber ein Key-Watch, ein Counter-Inkrement, ein Compare-and-Swap und eine Datenstruktur-Operation auf einem einzelnen Key alle routen, sodass sie alle die Owner-direkte Zustellung und dieselbe selbstheilende Map erben. Der Client ist keine dumme Leitung mit angeschraubtem Routing; das Routing ist das, was der Client ist.

Die ehrlichen Kompromisse

Owner-direktes Routing ist nicht frei von Kanten, und es lohnt sich, sie zu benennen.

• Der Client muss jeden Node erreichen können. Da es keinen Proxy gibt, öffnet der Client eine Verbindung zu jedem Node, zu dem er routet. In einem flachen Netzwerk ist das kein Problem; über eine Grenze hinweg — sagen wir, ein Client außerhalb von Kubernetes — müssen diese Nodes einzeln adressierbar sein. Genau dieses Problem soll die Adressierung externer Clients lösen, und es ist eine direkte Folge davon, dass es keine einzelne Eingangstür gibt.
• Eine kurze Map-Verzögerung ist möglich, kein Verlust. In dem Fenster zwischen dem Wandern des Ownerships und dem Erfahren des Clients kann ein Request zum alten Owner routen. Er wird abgelehnt und wiederholt, nicht falsch angewendet — der reaktive Pfad oben garantiert, dass der Retry beim echten Owner landet. Sie zahlen einen Round-Trip, keine falsche Antwort.
• Die Platzierungsfunktion ist ein Kompatibilitätsvertrag. Weil Client und Server SegmentMapper teilen, können Sie nicht ändern, wie Keys auf Segmente gehasht werden, ohne dass beide Seiten zustimmen — genau deshalb wurde das Hashing am stabilen Redis-Slot-Modell ausgerichtet statt an einem internen Schema, das driften könnte.

Klar gesagt: Der Zaris-Client weiß, wo Ihre Keys leben, hält dieses Wissen aktuell, ohne dass Sie daran denken müssen, und verbraucht für jede Operation einen Netzwerk-Hop — den, der tatsächlich die Arbeit erledigt. Die Raffinesse liegt nicht im schnellen Pfad, der bewusst langweilig ist. Sie liegt in den drei stillen Mechanismen, die den schnellen Pfad korrekt halten, während sich der Cluster unter ihm neu formt.