Consistent Hashing erklärt: Hash-Ring, virtuelle Knoten und Rebalancing

Du verteilst einen Cache mit hash(key) % 10 auf zehn Server. Der Traffic wächst, du fügst einen elften Server hinzu, und die Trefferquote bricht ein: Fast jeder Key landet jetzt auf einem anderen Server, also ist der Cache überall gleichzeitig kalt, und die Datenbank dahinter trägt die volle Last. Consistent Hashing gibt es, um genau das zu verhindern.

Dieser Beitrag erklärt den Hash-Ring und virtuelle Knoten mit einem Diagramm, misst, wie viel sie bringen, zeigt eine kompakte Implementierung und vergleicht die Alternativen, denen du in echten Systemen begegnest: Rendezvous Hashing, Jump Hash, Maglev und feste Hash-Slots.

Warum Modulo-Hashing bricht

Mit server = hash(key) % N hängt die Zuordnung von N ab. Ändert sich N, bleibt ein Key nur dann, wo er ist, wenn sein Hash für beide Werte denselben Rest ergibt, und das ist selten. In einer schnellen Simulation mit einer Million Keys:

Ideal wäre 1/11, etwa 9,1 %: Der neue Server sollte seinen fairen Anteil übernehmen, und sonst sollte sich nichts bewegen. Der Ring kommt nah heran; die verbleibende Lücke entsteht, weil die Tokens des neuen Servers auf etwas größeren Bögen als dem Durchschnitt landen.

Für einen Cache ist der Unterschied ein kurzer Einbruch der Trefferquote gegenüber einem Kaltstart. Für eine geshardete Datenbank oder eine Gruppe zustandsbehafteter Worker ist es der Unterschied, ob ein Zehntel der Daten oder fast alle Daten umziehen.

Der Hash-Ring

Consistent Hashing, 1997 von Karger und Kollegen für Web-Caching eingeführt, bildet Server und Keys auf denselben kreisförmigen Hash-Raum ab, zum Beispiel die ganzen Zahlen von 0 bis 2^64 - 1, wobei der größte Wert wieder auf 0 umbricht.

1. Hashe den Namen jedes Servers auf eine Position im Ring.
2. Hashe jeden Key auf eine Position im Ring.
3. Geh von der Position des Keys im Uhrzeigersinn weiter. Der erste Server, auf den du triffst, besitzt den Key.

Ein neuer Server bekommt eine Position und übernimmt nur die Keys zwischen seinem Vorgänger und sich selbst. Jeder andere Key bleibt, wo er war. Wird ein Server entfernt, gehen seine Keys an den nächsten Server im Uhrzeigersinn. Sonst ändert sich nichts.

Virtuelle Knoten: das Ungleichgewicht beheben

Mit einer Position pro Server sind die Bögen zwischen den Servern zufällig und ungleich, also besitzen manche Server einen viel größeren Teil des Rings als andere. Dieselbe Simulation mit zehn Servern zeigt, wie groß der Effekt ist:

Die Lösung: Gib jedem Server viele Positionen, virtuelle Knoten oder Tokens genannt, indem du Namen wie cache-a#0, cache-a#1 und so weiter hashst. Virtuelle Knoten bringen außerdem zwei weitere Vorteile:

• Gewichte. Ein Server mit doppelt so viel Speicher bekommt doppelt so viele Tokens.
• Sanftere Ausfälle. Fällt ein Server aus, gehen seine vielen kleinen Bögen an viele verschiedene Nachfolger, sodass sich seine Last über den Cluster verteilt, statt die Last eines Nachbarn zu verdoppeln.

Der Preis sind eine größere Lookup-Tabelle und mehr Metadaten, die bei Mitgliedschaftsänderungen umziehen. Cassandra zeigt den Kompromiss in der Praxis: Es nutzte standardmäßig 256 Tokens pro Knoten, bis Version 4.0 den Standard auf 16 senkte, kombiniert mit einem Token-Zuteilungsalgorithmus, der diese 16 gleichmäßig statt zufällig platziert.

Eine kleine Implementierung

Ein Ring ist eine sortierte Liste von Token-Positionen plus binäre Suche:

import bisect
import hashlib

def hash64(value: str) -> int:
    # MD5 for spread, not security; any well-mixed hash works
    return int.from_bytes(hashlib.md5(value.encode()).digest()[:8], "big")

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.vnodes = vnodes
        self.points = []   # sorted token positions
        self.owners = {}   # position -> server
        for server in servers:
            self.add(server)

    def add(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            bisect.insort(self.points, p)
            self.owners[p] = server

    def remove(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            self.points.remove(p)
            del self.owners[p]

    def lookup(self, key: str) -> str:
        i = bisect.bisect_right(self.points, hash64(key)) % len(self.points)
        return self.owners[self.points[i]]

Lookups kosten O(log T) bei T Tokens. Produktionsversionen behandeln außerdem Token-Kollisionen und halten die Sicht jedes Clients auf die Mitgliedschaft identisch, denn zwei Clients mit unterschiedlichen Serverlisten sind sich uneinig darüber, wo Keys liegen.

Replikation auf dem Ring

Speichersysteme nutzen den Ring sowohl für die Platzierung als auch für das Routing. Amazons Dynamo-Paper speichert jeden Key auf den ersten N verschiedenen Servern im Uhrzeigersinn ab seiner Position, seiner Preference List, und überspringt zusätzliche Tokens, die einem Server gehören, der schon in der Liste steht. Mit N = 3 bleiben nach dem Verlust eines Servers immer noch zwei Kopien von allem, was er hielt, auf Servern, die seine Nachbarn im Ring sind.

Dieselbe Idee „im Uhrzeigersinn gehen und Duplikate überspringen“ lässt sich auf Racks und Zonen übertragen: Überspring Tokens, bis die Repliken verschiedene Fehlerdomänen abdecken.

Alternativen, denen du begegnest

Jump Consistent Hash passt zu geshardetem Speicher, bei dem Shards nummeriert sind und nur wachsen. Rendezvous Hashing passt zu kleinen Servermengen, bei denen O(N) pro Lookup keine Rolle spielt. Hash-Slots tauschen automatische Platzierung gegen explizite, vom Operator gesteuerte Verschiebungen, was viele Teams bei Datenbanken bevorzugen.

Hot Keys und begrenzte Last

Consistent Hashing gleicht Keys aus, nicht Traffic. Ein prominenter Nutzer oder ein viral gehendes Produkt landet trotzdem auf einem Server. Consistent Hashing with Bounded Loads deckelt jeden Server bei einem festgelegten Prozentsatz über dem Durchschnitt und schickt den Überlauf an den nächsten Server im Uhrzeigersinn. HAProxy setzt das mit seiner Einstellung hash-balance-factor um. Für wirklich heiße Keys brauchst du trotzdem Replikation dieses Keys, Request Coalescing oder einen kleinen lokalen Cache davor.

Fallstricke im Betrieb

• Die Hashfunktion oder das Token-Schema zu ändern verteilt alles neu, genau wie Modulo-Hashing. Behandle es als Migration.
• Die Mitgliedschaft muss konsistent sein. Verteile die Serverliste aus einer einzigen Quelle, etwa einem Koordinationsdienst oder der Konfiguration des Load Balancers, und ändere sie in einem Schritt.
• Flatternde Server erzeugen Churn. Ein Server, der alle paar Minuten Health Checks nicht besteht, schiebt seine Keys hin und her. Bau eine Hysterese ein, bevor du ihn entfernst und wieder aufnimmst.
• Neue Server starten kalt. Ein neuer Cache-Knoten übernimmt sofort seinen Anteil der Requests; wärm ihn vor oder fahr sein Gewicht hoch, wenn das Backend die Misses nicht verkraftet.

Das Hash-Ring-Diagramm

So liest du es:

• Der Kreis ist der Hash-Raum. Positionen steigen im Uhrzeigersinn, und oben bricht der größte Wert auf null um.
• Farbige Tokens sind virtuelle Knoten. Jede Farbe ist ein Server, und jeder Server besitzt mehrere Tokens, die über den Ring verteilt sind.
• Keys sitzen an ihren Hash-Positionen, und die Pfeile zeigen im Uhrzeigersinn auf das Token, dem sie gehören.
• Die gestrichelten Tokens gehören zu Server D, der gerade hinzukommt. Nur die Keys direkt gegen den Uhrzeigersinn vor den Tokens von D wechseln den Besitzer.
• Die Legende und der Markdown-Block listen die Server und die Verschiebungszahlen aus der Simulation oben auf.

Hashing-Verfahren klar zeichnen

• Zeichne den Ring, keine Tabelle. Die Uhrzeigersinn-Regel ist visuell; eine Lookup-Tabelle verbirgt, warum nur manche Keys umziehen.
• Färbe Tokens nach Server und füge eine Legende hinzu, statt von jedem Token eine Kante zu seinem Server zu ziehen.
• Zeig eine Mitgliedschaftsänderung. Ein statischer Ring erklärt das Routing; ein Ring, dem ein Server beitritt, erklärt den ganzen Sinn der Technik.
• Stell echte Zahlen daneben: verschobene Keys und Lastverteilung. Sie überzeugen mehr als das Bild.

Consistent Hashing taucht in vielen System-Design-Beiträgen dieses Blogs auf: im Datenbank-Sharding-Diagramm zur Platzierung von Daten, im Load-Balancer-Diagramm für Sticky Routing und im Diagramm der Caching-Strategien für verteilte Caches.

In Archboard nachbauen

1. Melde dich mit Google oder GitHub an und leg ein Diagramm an.
2. Füge als Ring eine große Form in der Variante Ellipse aus dem Basis-Pack hinzu.
3. Füge auf dem Ring kleine Ellipse-Formen als Tokens hinzu, nach Server eingefärbt: je zwei für die Server A, B und C und zwei gestrichelte für den neuen Server D.
4. Füge neben dem Ring als Legende vier Redis-Nodes aus dem Daten-Pack in einer Spalte hinzu, eingefärbt wie ihre Tokens.
5. Füge Keys als Text-Labels aus dem Basis-Pack auf dem Ring hinzu, mit kurzen Pfeilen zu ihren Tokens.
6. Füge einen Markdown-Block aus dem Basis-Pack mit den Zahlen zu Key-Verschiebung und Last hinzu.

Das Beispiel nutzt 14 Diagramm-Nodes und bleibt damit im Free-Plan.

FAQ

Welches Problem löst Consistent Hashing? Es hält die meisten Keys auf demselben Server, wenn Server hinzukommen oder wegfallen. Mit Modulo-Hashing ordnet eine geänderte Serverzahl fast jeden Key neu zu; mit Consistent Hashing zieht nur etwa 1/N der Keys um.

Was sind virtuelle Knoten beim Consistent Hashing? Jeder physische Server wird unter verschiedenen Namen viele Male auf dem Ring platziert. Mehr Positionen machen die Bögen gleichmäßiger, erlauben es, Server nach Kapazität zu gewichten, und verteilen die Last eines ausgefallenen Servers auf viele andere.

Wie viele virtuelle Knoten sollte jeder Server haben? Genug für eine gleichmäßige Verteilung bei deiner Clustergröße: In unserer Simulation hielten 100 pro Server den stärksten Server bei zehn Servern innerhalb von 7 % des Durchschnitts. Systeme mit klügerer Token-Zuteilung, etwa Cassandra ab 4.0, kommen mit weit weniger aus.

Ist Redis Cluster Consistent Hashing? Nicht im Sinne eines Rings. Redis Cluster bildet Keys auf 16.384 feste Hash-Slots ab und weist die Slots Knoten zu; Daten zu verschieben heißt, Slots explizit zu verschieben.

Was ist der Unterschied zwischen Consistent Hashing und Rendezvous Hashing? Beide verschieben bei Mitgliedschaftsänderungen etwa 1/N der Keys. Rendezvous Hashing bewertet für jeden Key jeden Server und wählt den höchsten; das braucht keinen Ring, kostet aber O(N) pro Lookup.

Kostenlos starten — ein Seat, keine Kreditkarte.