Der Ring, der die Last verteilt: Consistent Hashing und die Kunst des sanften Umzugs

Der Aufhänger: Der teuerste Fehler beim Verteilen

Stell dir vor, du betreibst einen Cache – eine Sammlung schneller Server, die häufig angefragte Daten im Arbeitsspeicher vorhalten, damit die dahinterliegende Datenbank nicht bei jedem Klick befragt werden muss. Du hast zehn dieser Server, und du musst entscheiden, welcher Server für welchen Datensatz zuständig ist. Die naheliegende, geradezu offensichtliche Lösung lernt jeder Informatikstudent im ersten Semester: Nimm einen Hashwert des Schlüssels, rechne modulo der Anzahl der Server, und schon hast du eine Serverzuweisung. server = hash(key) % 10. Elegant, schnell, gleichmäßig.

Und eine Katastrophe, sobald sich die Anzahl der Server ändert.

Denn nehmen wir an, ein elfter Server kommt hinzu, weil die Last steigt. Aus % 10 wird % 11. Was passiert? Praktisch jeder Schlüssel landet nun bei einem anderen Server. Nicht ein Zehntel, nicht ein Elftel – fast alle. Der Datensatz, der eben noch auf Server 3 lag, liegt nun auf Server 7, der nächste auf Server 0, und so weiter. Für einen Cache bedeutet das: Von einer Sekunde auf die andere sind fast alle Einträge am falschen Ort. Jede Anfrage verfehlt den Cache, jede Anfrage schlägt bis zur Datenbank durch. Man nennt das einen Cache-Sturm, und er kann eine Datenbank, die eigentlich für zehn Prozent der Last ausgelegt war, unter der plötzlichen vollen Last zusammenbrechen lassen. Der Versuch, mehr Kapazität hinzuzufügen, löst genau den Zusammenbruch aus, den man vermeiden wollte.

Dieses Problem ist der Kern einer der wichtigsten und zugleich unterschätztesten Ideen der modernen Cloud-Infrastruktur: Consistent Hashing. Es beantwortet eine Frage, die im Maschinenraum praktisch jedes verteilten Systems auftaucht – von Amazons Warenkorb über Discords Nachrichtenrouting bis zu Content-Delivery-Netzwerken, die Videos an Milliarden Nutzer ausliefern: Wie verteile ich Daten oder Last auf eine Menge von Maschinen, sodass beim Hinzufügen oder Wegfall einer Maschine nur ein minimaler, kontrollierter Bruchteil der Zuordnungen sich ändert?

Dieser Artikel nimmt dich auf die ganze Strecke mit: von der genauen Definition dessen, was „konsistent" hier bedeutet, über den ursprünglichen Ring von David Karger und Kollegen aus dem Jahr 1997, das entscheidende Nachbessern mit virtuellen Knoten, bis hin zu den modernen Alternativen – Rendezvous-Hashing, Jump-Hashing und Googles Maglev –, die je eigene Abwägungen treffen. Am Ende steht nicht nur ein Algorithmus, sondern ein Denkprinzip über Stabilität unter Veränderung.

Teil 1: Was „konsistent" wirklich bedeutet

Das Maß aller Dinge: minimale Störung

Der Begriff „Consistent Hashing" ist historisch gewachsen und leider etwas irreführend – er hat nichts mit „Konsistenz" im Sinne von Datenbank-Konsistenz oder dem CAP-Theorem zu tun. Gemeint ist etwas Präziseres. Karger und seine Mitautoren definierten eine konsistente Hashfunktion 1997 als eine, die sich minimal ändert, wenn sich der Wertebereich der Funktion ändert – also wenn Buckets (Server, Knoten, Bereiche) hinzukommen oder verschwinden.

Formulieren wir die Anforderung sauber. Wir haben eine Menge von Schlüsseln (die Datensätze, Anfragen, Objekte) und eine Menge von Buckets (die Server). Eine Zuordnungsfunktion bildet jeden Schlüssel auf einen Bucket ab. Von einer guten solchen Funktion für verteilte Systeme verlangen wir vier Eigenschaften:

Balance (Ausgeglichenheit): Die Schlüssel sollen sich möglichst gleichmäßig auf die Buckets verteilen. Kein Server soll überproportional viel Last tragen.

Monotonie / minimale Störung (minimal disruption): Wenn ein Bucket hinzukommt oder wegfällt, sollen nur die Schlüssel neu zugeordnet werden, die unbedingt müssen. Idealerweise wandert beim Wegfall eines von n Buckets nur ein Anteil von etwa 1/n aller Schlüssel – nämlich genau die, die auf dem verschwundenen Bucket lagen. Alle anderen bleiben, wo sie sind.

Spread und Load (Streuung und Last): In Systemen, in denen verschiedene Clients unterschiedliche, möglicherweise veraltete Sichten auf die Bucket-Menge haben, soll ein Schlüssel trotzdem nicht auf zu viele verschiedene Buckets gestreut werden, und kein Bucket soll für zu viele Schlüssel verantwortlich sein.

Geringe Kosten: Die Berechnung der Zuordnung und die nötige Zustandshaltung sollen billig sein.

Der Modulo-Ansatz erfüllt Balance hervorragend, versagt aber katastrophal bei der Monotonie: Eine Änderung von n reißt fast alles neu durcheinander. Genau hier setzt Consistent Hashing an.

Warum das gerade in der Cloud so wichtig ist

In einem statischen System mit fester Serverzahl wäre der Modulo-Trick völlig ausreichend. Aber die Cloud ist das Gegenteil von statisch. Server werden gestartet und beendet, um mit der Last zu atmen (Autoscaling). Maschinen fallen aus – bei Zehntausenden von Servern ist zu jedem Zeitpunkt fast garantiert irgendwo eine defekt. Deployments ersetzen laufend Instanzen. Die Menge der verfügbaren Knoten ist also ständig in Bewegung. Ein Verteilungsschema, das bei jeder solchen Änderung fast alle Daten umschichtet, ist in dieser Umgebung schlicht unbrauchbar. Consistent Hashing ist die Antwort darauf, dass Elastizität – die Fähigkeit, Kapazität dynamisch anzupassen – zum Grundprinzip der Cloud geworden ist. Es ist die stille Voraussetzung dafür, dass ein System wachsen und schrumpfen kann, ohne bei jedem Atemzug in sich zusammenzufallen.

Teil 2: Der Ring – Kargers Idee von 1997

Von der geraden Linie zum Kreis

Die zentrale Erfindung wurde 1997 in einem heute berühmten Papier vorgestellt: Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web von David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin und Rina Panigrahy, damals am Laboratory for Computer Science des MIT. Die Motivation war ausgesprochen praktisch: das junge World Wide Web litt unter „Hot Spots" – plötzlich populäre Seiten, die einzelne Server überrannten. Man wollte die Last über ein Netz von Cache-Servern verteilen, ohne dass jeder Client eine aktuelle, konsistente Sicht auf alle Server brauchte. (Dieselbe Arbeit wurde später zum technischen Fundament des Content-Delivery-Netzwerks Akamai, das Daniel Lewin und Tom Leighton mitgründeten.)

Die Grundidee ist von bestechender Einfachheit. Statt die Server auf eine gerade Zahlenlinie zu legen und modulo zu rechnen, biegt man die Zahlenlinie zu einem Kreis – einem Ring. Man stellt sich einen Wertebereich vor, etwa alle Zahlen von 0 bis 2³²−1, und schließt ihn zu einem Kreis: Nach der größten Zahl kommt wieder die 0.

Nun geschieht der entscheidende Trick: Man platziert nicht nur die Schlüssel auf diesem Ring, sondern auch die Server. Jeder Server bekommt durch eine Hashfunktion seines Namens (z. B. seiner IP-Adresse) eine oder mehrere Positionen auf dem Ring zugewiesen. Jeder Schlüssel bekommt durch dieselbe Hashfunktion ebenfalls eine Position. Damit landen Server und Daten im selben abstrakten Raum.

Die Zuständigkeitsregel: im Uhrzeigersinn zum nächsten Knoten

Die Zuordnung folgt jetzt einer einzigen, eleganten Regel: Ein Schlüssel gehört zu dem Server, den man erreicht, wenn man von der Position des Schlüssels aus im Uhrzeigersinn um den Ring läuft, bis man auf den ersten Server trifft. Jeder Server ist also verantwortlich für den Bogen des Rings, der unmittelbar „vor" ihm liegt – für alle Schlüssel zwischen ihm und seinem Vorgänger auf dem Ring.

Jetzt kommt der springende Punkt, die eigentliche Magie. Was passiert, wenn ein Server ausfällt? Sein Bogen des Rings wird verwaist. Aber statt das ganze System durcheinanderzuwerfen, geschieht etwas Lokales: Nur die Schlüssel, die auf diesem einen verwaisten Bogen lagen, wandern zum nächsten Server im Uhrzeigersinn. Alle anderen Schlüssel im gesamten Ring bleiben exakt dort, wo sie waren. Ihre Position hat sich nicht geändert, ihr im Uhrzeigersinn nächster Server ist immer noch derselbe. Es ziehen also nur ungefähr 1/n aller Schlüssel um – bei zehn Servern etwa ein Zehntel statt, wie beim Modulo-Ansatz, praktisch alles.

Spiegelbildlich beim Hinzufügen eines Servers: Der Neue setzt sich an eine Position auf dem Ring und übernimmt genau den Teil des Bogens, der zwischen ihm und seinem Vorgänger liegt – Schlüssel, die vorher zum nächsten Server im Uhrzeigersinn gehörten. Nur dieser eine Abschnitt zieht um; der Rest des Rings bleibt unberührt. Das ist die minimale Störung, die die Definition verlangt, praktisch umgesetzt.

Ein Bild zum Festhalten

Man kann sich den Ring wie eine runde Uhr vorstellen, auf der die Server an verschiedenen Stunden sitzen. Jeder Datensatz sucht sich seine eigene Uhrzeit und wandert dann im Uhrzeigersinn, bis er den nächsten Server erreicht – dort checkt er ein. Fällt der Server bei „drei Uhr" aus, suchen sich alle seine Gäste einfach den nächsten Server bei „vier Uhr". Niemand sonst auf dem Zifferblatt muss umziehen. Diese Lokalität – dass eine Störung nur ihre unmittelbare Nachbarschaft betrifft – ist die konzeptionelle Errungenschaft von Consistent Hashing.

Teil 3: Das Problem des nackten Rings und die Rettung durch virtuelle Knoten

Der Ring ist naiv gefährlich unwuchtig

So schön der Grundring ist, in seiner nackten Form hat er zwei ernste Schwächen, die ihn für den Produktivbetrieb untauglich machen.

Problem 1 – ungleiche Verteilung. Wenn man nur n Server zufällig auf den Ring wirft, sind die Bögen zwischen ihnen nicht gleich lang. Rein statistisch entstehen große und kleine Lücken. Ein Server, dem zufällig ein besonders langer Bogen zufällt, bekommt weit mehr Schlüssel als seine Kollegen. Bei wenigen Servern kann die Standardabweichung der Lastverteilung erheblich sein – Ausreißer, die das Doppelte oder Dreifache des Durchschnitts tragen, sind keine Seltenheit. Die Theorie sagt: Mit nur n Positionen kann die Unwucht leicht im Bereich von Faktor zwei liegen.

Problem 2 – ungleiche Umverteilung bei Ausfall. Fällt ein Server aus, wandert sein gesamter Bogen zu genau einem einzigen Nachbarn – dem nächsten im Uhrzeigersinn. Dieser Nachbar erbt schlagartig die komplette Last des Ausgefallenen zusätzlich zu seiner eigenen. Statt die Last des Ausgefallenen gleichmäßig auf alle verbleibenden Server zu verteilen, wird sie auf einen einzigen abgewälzt – der dann seinerseits leicht überlastet und ausfallen kann. Ein solcher Dominoeffekt ist der Albtraum jedes Betreibers.

Die elegante Lösung: viele Geister pro Server

Die Antwort auf beide Probleme ist so einfach wie wirkungsvoll und stammt in ihrer bekannten Ausprägung aus Amazons Dynamo-System: virtuelle Knoten (auch Tokens oder vnodes genannt). Statt jeden physischen Server nur einmal auf den Ring zu setzen, platziert man ihn viele Male – etwa 100 bis 200 Mal – an verschiedenen, durch Hashing gestreuten Positionen. Jeder physische Server erscheint also als eine Wolke vieler kleiner „Geister" über den ganzen Ring verteilt.

Das behebt beide Probleme auf einen Schlag. Zur Balance: Wenn jeder Server durch hundert zufällige Punkte repräsentiert wird, mitteln sich die Längen der vielen kleinen Bögen aus. Das Gesetz der großen Zahlen sorgt dafür, dass die Gesamtlast pro physischem Server sehr eng um den Durchschnitt liegt. Je mehr virtuelle Knoten, desto gleichmäßiger – auf Kosten von etwas mehr Speicher für die Ring-Datenstruktur.

Zur Umverteilung bei Ausfall: Fällt nun ein physischer Server aus, verschwinden seine hundert Geister an hundert verschiedenen Stellen des Rings. Jeder dieser hundert kleinen Bögen wandert zu seinem jeweiligen Nachbarn im Uhrzeigersinn – und diese Nachbarn sind, weil die Geister über den ganzen Ring gestreut sind, mit hoher Wahrscheinlichkeit hundert verschiedene physische Server. Die Last des Ausgefallenen wird also fein zerstäubt und gleichmäßig auf alle übrigen Server verteilt, statt einen einzigen zu erschlagen. Der Dominoeffekt ist gebannt.

Ein weiterer, oft unterschätzter Vorteil: virtuelle Knoten erlauben Heterogenität. Ein doppelt so leistungsfähiger Server bekommt einfach doppelt so viele virtuelle Knoten und trägt entsprechend doppelt so viel Last. Man kann die Kapazität also feinkörnig gewichten, ohne den Algorithmus zu ändern.

Dynamo: Consistent Hashing im industriellen Maßstab

Das kanonische Beispiel für Consistent Hashing im großen Stil ist Amazons Dynamo, beschrieben 2007 von Giuseppe DeCandia und Kollegen in einem einflussreichen Papier, das eine ganze Generation von NoSQL-Datenbanken prägte (Cassandra, Riak, Voldemort und andere bauen direkt darauf auf). Dynamo verteilt seine Schlüssel-Wert-Paare mit Consistent Hashing über den Ring – in der Grundidee sehr ähnlich zu Chord, dem verteilten Hashtabellen-System. Jeder Knoten bekommt beim Beitritt mehrere Positionen (Tokens) auf dem Ring, und die Zahl dieser virtuellen Knoten pro Maschine lässt sich nach deren Kapazität einstellen.

Dynamo nutzt den Ring aber nicht nur zur Verteilung, sondern auch zur Replikation: Jeder Datensatz wird nicht nur auf dem ersten Knoten im Uhrzeigersinn gespeichert, sondern zusätzlich auf den nächsten N−1 Knoten. Der Ring liefert damit gleich die Liste der Server, die eine Kopie halten sollen – die sogenannte Präferenzliste. So wird aus einem Verteilungsschema zugleich ein Fundament für Ausfallsicherheit. Wer die Mechanik der Verteilung verinnerlicht hat, versteht auch, warum solche Systeme so elegant mit Knotenausfällen umgehen: Der nächste Knoten im Uhrzeigersinn hält ohnehin schon eine Kopie.

Teil 4: Die Alternativen – ein Ökosystem von Abwägungen

Der Ring mit virtuellen Knoten ist die klassische, am weitesten verbreitete Lösung. Aber er ist nicht die einzige, und für bestimmte Anwendungsfälle gibt es bessere. Die Geschichte des Consistent Hashing ist eine Geschichte von Abwägungen: Speicher gegen Gleichmäßigkeit, Einfachheit gegen Flexibilität, Rechenzeit gegen Vorhersagbarkeit.

Rendezvous-Hashing (Highest Random Weight)

Interessanterweise ist eine der elegantesten Alternativen sogar älter als der Ring. Rendezvous-Hashing, auch Highest Random Weight (HRW) genannt, wurde 1996/1998 von David Thaler und Chinya Ravishankar an der University of Michigan beschrieben (technischer Bericht CSE-TR-316-96, formal publiziert als Using Name-Based Mapping Schemes to Increase Hit Rates in IEEE/ACM Transactions on Networking 1998). Es entstand ebenfalls aus dem Problem des verteilten Web-Caching und fand früh Anwendung in Microsofts Cache Array Routing Protocol (CARP).

Die Idee kommt ganz ohne Ring aus. Um herauszufinden, welcher Server für einen Schlüssel zuständig ist, geht man so vor: Für jeden verfügbaren Server s berechnet man einen kombinierten Hashwert hash(key, s) – also einen Hash aus der Kombination von Schlüssel und Servername. Das ergibt für jeden Server eine Art Zufallszahl, ein „Gewicht". Dann wählt man einfach den Server mit dem höchsten dieser Werte. Fertig.

Das Bestechende: Fällt ein Server aus, betrifft das nur die Schlüssel, für die genau dieser Server das höchste Gewicht hatte. Für alle anderen Schlüssel bleibt der Gewinner unverändert – der zweithöchste war ohnehin schon ein anderer und wird nun eben zum höchsten für die betroffenen Schlüssel. Man erreicht damit dieselbe minimale Störung wie beim Ring, aber mit perfekter, natürlicher Balance und ohne virtuelle Knoten und ohne eine Ring-Datenstruktur im Speicher halten zu müssen. Der Preis: Die Zuordnung eines einzelnen Schlüssels kostet O(n) Hash-Berechnungen, weil man über alle Server iterieren muss. Für kleine bis mittlere Servermengen ist das kein Problem und oft die sauberste Lösung; für tausende Buckets wird es teuer (auch wenn es Varianten mit logarithmischer Laufzeit über Skip-Strukturen gibt). Gewichtung für heterogene Kapazitäten ist ebenfalls möglich – durch eine Ein-Zeilen-Änderung, die das Gewicht in die Formel einbezieht.

Jump-Hashing: fünf Zeilen, kein Speicher

2014 veröffentlichten John Lamping und Eric Veach bei Google ein bemerkenswert kurzes Papier: A Fast, Minimal Memory, Consistent Hash Algorithm. Der darin beschriebene Jump Consistent Hash lässt sich in etwa fünf Zeilen Code ausdrücken, braucht überhaupt keinen Speicher für Zustand, ist schneller als Kargers Ring und verteilt die Schlüssel nachweislich gleichmäßiger auf die Buckets.

Der Algorithmus berechnet direkt, in welchen von n nummerierten Buckets ein Schlüssel fällt, indem er eine deterministische Pseudozufallsfolge durchläuft und „Sprünge" macht, bei denen sich die Zuordnung ändern würde. Er braucht O(1) Speicher und O(ln n) Zeit und erreicht nahezu perfekte Balance ohne virtuelle Knoten.

Die entscheidende Einschränkung – und der Grund, warum Jump-Hashing den Ring nicht einfach überall ablöst – ist, dass die Buckets sequenziell durchnummeriert sein müssen: 0, 1, 2, …, n−1. Man kann nur Buckets am Ende hinzufügen oder entfernen. Es gibt keine Möglichkeit, einen beliebigen Bucket in der Mitte zu entfernen (etwa weil genau dieser eine Server ausgefallen ist), ohne die Nummerierung zu stören. Das macht Jump-Hashing hervorragend geeignet für Datenspeicher-Systeme mit durchnummerierten Shards, in denen man geordnet nach oben oder unten skaliert – aber ungeeignet für verteiltes Web-Caching, wo einzelne, benannte Server jederzeit und in beliebiger Reihenfolge ausfallen.

Maglev: die konsistente Lookup-Tabelle

Googles Maglev, vorgestellt 2016 auf der NSDI von Daniel Eisenbud und Kollegen, ist ein softwarebasierter Netzwerk-Lastverteiler, der pro Sekunde Millionen von Paketen auf Backend-Server verteilt. Für diesen Zweck brauchte Google ein Verfahren, das sehr schnell nachschlägt (jedes Paket muss in konstanter Zeit einem Backend zugewiesen werden) und dabei die Verbindungen möglichst wenig durcheinanderwirbelt, wenn sich die Menge der Backends ändert.

Maglevs Consistent-Hashing-Algorithmus baut dazu vorab eine Lookup-Tabelle fester Größe auf, in der jedes Backend seine Einträge über ein durchdachtes Permutationsverfahren belegt. Ein Paket wird dann durch einen einzigen Tabellenzugriff einem Backend zugeordnet – konstante Zeit, sehr cache-freundlich. Das Verfahren erreicht nahezu perfekte Lastverteilung und hält gleichzeitig die connection churn – den Anteil der Verbindungen, die bei einer Änderung der Backend-Menge zu einem anderen Backend umziehen – gering. Gewichtung erreicht Maglev, indem stärker gewichtete Backends häufiger Einträge in der Tabelle belegen dürfen. Der Kompromiss: Die minimale Störung ist nicht perfekt wie beim Ring – ein kleiner Anteil zusätzlicher Verbindungen kann bei Änderungen umziehen –, dafür ist der Lookup extrem schnell und der Speicherbedarf berechenbar konstant.

Eine Landkarte der Abwägungen

Die Tabelle macht das zentrale Muster sichtbar: Es gibt kein universell bestes Verfahren, sondern nur ein für den jeweiligen Kontext passendes. Wer benannte Knoten in beliebiger Reihenfolge verlieren kann, braucht den Ring oder Rendezvous. Wer geordnet skaliert und keinen Speicher verschwenden will, nimmt Jump. Wer pro Sekunde Millionen Pakete in konstanter Zeit routen muss, nimmt Maglev.

Teil 5: Die Feinheiten, die in der Praxis wehtun

Hot Keys – wenn ein einzelner Schlüssel das System sprengt

Consistent Hashing verteilt Schlüssel gleichmäßig – aber nicht notwendigerweise Last. Wenn ein einzelner Schlüssel überproportional oft angefragt wird (der Tweet eines Prominenten, ein viraler Produktartikel, das Profil eines Superstars), dann landet die gesamte Last dieses einen „Hot Key" auf dem einen Server, der für ihn zuständig ist – egal wie fein der Ring ausbalanciert ist. Kein Hashing-Verfahren kann dieses Problem allein lösen, weil es prinzipiell auf der Ebene der Schlüssel arbeitet, nicht auf der Ebene der Zugriffshäufigkeit. In der Praxis begegnet man Hot Keys mit zusätzlichen Schichten: Replikation besonders heißer Schlüssel auf mehrere Knoten, eine kleine Cache-Schicht davor, oder das künstliche Aufspalten eines heißen Schlüssels in mehrere Unterschlüssel. Es ist wichtig, diese Grenze zu kennen: Consistent Hashing löst das Problem der strukturellen Umverteilung, nicht das Problem schiefer Zugriffsmuster.

Bounded Loads – Balance mit Sicherheitsgurt

Selbst mit virtuellen Knoten bleibt die Balance statistisch, nicht garantiert. 2016 stellten Forscher (unter Beteiligung von Google und Vimeo) eine Erweiterung namens Consistent Hashing with Bounded Loads vor. Die Idee: Man legt eine harte Obergrenze fest, wie viel Last ein einzelner Server maximal tragen darf – etwa das 1,25-Fache des Durchschnitts. Läuft ein Schlüssel bei seiner Ringsuche auf einen bereits „vollen" Server, wandert er einfach weiter im Uhrzeigersinn zum nächsten, der noch Kapazität hat. So kombiniert man die minimale Störung des Rings mit einer echten Garantie gegen Überlastung – ein schönes Beispiel dafür, wie sich die Grundidee schichtweise robuster machen lässt.

Die Wahl der Hashfunktion

Ein oft übersehenes Detail: Damit die statistische Gleichverteilung überhaupt greift, muss die zugrunde liegende Hashfunktion die Werte gut über den Wertebereich streuen. Kryptografische Stärke ist dabei meist unnötig und zu langsam; man nimmt schnelle, aber gut streuende nicht-kryptografische Funktionen (etwa MurmurHash, xxHash oder ähnliche). Eine schlechte Hashfunktion mit Klumpenbildung kann die schönste Ring-Konstruktion unterlaufen, weil Server und Schlüssel dann nicht wirklich zufällig verteilt liegen.

Teil 6: Das übergeordnete Denkprinzip

Wenn man einen Schritt zurücktritt, ist Consistent Hashing weit mehr als ein Trick zum Verteilen von Cache-Einträgen. Es ist eine Antwort auf eine sehr allgemeine Frage: Wie baut man ein System, dessen Verhalten sich unter Veränderung nur so wenig wie nötig ändert? Der Modulo-Ansatz ist fragil, weil eine kleine Änderung des Parameters (n) eine globale Umwälzung auslöst – das gesamte System reagiert auf jede lokale Störung. Der Ring ist robust, weil er Lokalität erzwingt: Eine Störung an einer Stelle bleibt an dieser Stelle. Diese Eigenschaft – dass die Auswirkung einer Änderung proportional zur Größe der Änderung bleibt und nicht auf das Ganze übergreift – ist ein tiefes Designprinzip, das weit über Hashing hinausreicht.

Man findet dasselbe Muster überall in gut entworfenen verteilten Systemen: in der Art, wie Wie Maschinen sich einig werden - Verteilter Konsens von FLP ueber Paxos zu Raft darauf setzt, dass ein Wechsel des Anführers nicht das ganze Log neu schreibt; in der Art, wie Uhren die ihre eigene Unsicherheit kennen - Spanner TrueTime und die Beherrschung der Zeit in der Cloud die Unsicherheit der Zeit lokal begrenzt, statt sie durch das System propagieren zu lassen; in der Art, wie Das Logbuch der Wahrheit - Event Sourcing und CQRS verstehen Zustandsänderungen als unveränderliche, lokale Ereignisse behandelt, die den bestehenden Zustand nicht rückwirkend umschreiben. Die Botschaft ist überall dieselbe: Robuste Systeme sind solche, in denen der Radius einer Störung klein bleibt.

Erkenntnis zum Mitnehmen

Die praktische Lehre für den Entwurf jedes verteilten oder elastischen Systems lautet: Frage bei jedem Verteilungs- oder Zuordnungsschema nicht nur, ob es im statischen Fall gleichmäßig ist, sondern was passiert, wenn sich die Menge der Ziele ändert. Wie viele Zuordnungen brechen auf, wenn ein Knoten hinzukommt oder wegfällt? Wenn die Antwort „fast alle" lautet, hast du eine Zeitbombe eingebaut, die beim ersten Autoscaling-Ereignis oder Serverausfall hochgeht. Wenn die Antwort „nur der betroffene Bruchteil" lautet, hast du ein System gebaut, das mit Veränderung atmen kann. Consistent Hashing – ob als Ring, als Rendezvous, als Jump oder als Maglev – ist das Werkzeug, das diese zweite Antwort möglich macht. Und die Wahl zwischen den Varianten triffst du bewusst anhand der Fragen: Können meine Knoten in beliebiger Reihenfolge verschwinden? Wie viel Speicher und Rechenzeit darf ein Lookup kosten? Wie perfekt muss die Balance sein?

Eine Frage zum Nachdenken

Consistent Hashing löst das Problem, Störungen räumlich zu begrenzen – eine Änderung an einem Knoten bleibt lokal. Aber es gibt eine verwandte Frage, die es nicht beantwortet: Wie begrenzt man die Störung zeitlich, wenn viele Clients gleichzeitig noch eine veraltete Sicht auf die Knotenmenge haben und deshalb kurzzeitig widersprüchliche Zuordnungen berechnen? Wie viel Inkonsistenz während einer Umstellung ist akzeptabel, und wo in deinem eigenen System würdest du lieber kurzzeitig falsch, aber schnell, statt korrekt, aber blockierend zuordnen?

Querverweise im Vault

• Wie Maschinen sich einig werden - Verteilter Konsens von FLP ueber Paxos zu Raft – wie sich Knoten trotz Ausfällen auf einen gemeinsamen Zustand einigen; die logische Ergänzung zur Frage, welcher Knoten wofür zuständig ist.
• Uhren die ihre eigene Unsicherheit kennen - Spanner TrueTime und die Beherrschung der Zeit in der Cloud – ein weiteres Beispiel dafür, wie man Unsicherheit in verteilten Cloud-Systemen lokal beherrschbar macht.
• Das Logbuch der Wahrheit - Event Sourcing und CQRS verstehen – Zustand als lokale, unveränderliche Ereignisse statt global umschreibbarer Werte.

Quellen

• Karger, D., Lehman, E., Leighton, T., Levine, M., Lewin, D., Panigrahy, R. (1997): Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proc. 29th ACM Symposium on Theory of Computing (STOC), S. 654–663. DOI: 10.1145/258533.258660. https://dl.acm.org/doi/10.1145/258533.258660
• DeCandia, G. et al. (2007): Dynamo: Amazon's Highly Available Key-value Store. Proc. 21st ACM Symposium on Operating Systems Principles (SOSP). https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
• Thaler, D., Ravishankar, C. (1998): Using Name-Based Mapping Schemes to Increase Hit Rates. IEEE/ACM Transactions on Networking 6(1), S. 1–14 (zuerst als tech. Bericht CSE-TR-316-96, 1996). https://en.wikipedia.org/wiki/Rendezvous_hashing
• Lamping, J., Veach, E. (2014): A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv:1406.2294. https://arxiv.org/abs/1406.2294
• Eisenbud, D. E. et al. (2016): Maglev: A Fast and Reliable Software Network Load Balancer. Proc. 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI). https://research.google/pubs/maglev-a-fast-and-reliable-software-network-load-balancer/
• Stanford CS168, Vorlesung 1: Introduction and Consistent Hashing. https://web.stanford.edu/class/cs168/l/l1.pdf

← All articles