DE 
EnglishDefault
Українська
Polski💍 Konsistentes Hashing — Der Hash-Ring
Ordnen Sie Schlüssel und Server auf einem Hash-Ring an, sodass das Hinzufügen oder Entfernen eines Knotens nur einen kleinen Bruchteil der Schlüssel neu zuordnet. Virtuelle Knoten glätten die Last — die Technik hinter verteilten Caches und DHTs.
Über diese Simulation
Ordnen Sie Schlüssel und Server auf einem Hash-Ring an, sodass das Hinzufügen oder Entfernen eines Knotens nur einen kleinen Bruchteil der Schlüssel neu zuordnet. Virtuelle Knoten glätten die Last — die Technik hinter verteilten Caches und DHTs.
🔬 Was gezeigt wird
Schlüssel und Server werden auf einem Ring aus Hash-Werten platziert. Jeder Schlüssel gehört zum nächsten Server im Uhrzeigersinn. Virtuelle Knoten verteilen die Last gleichmäßiger, und beim Hinzufügen oder Entfernen eines Servers wird nur ein kleiner Bruchteil der Schlüssel neu zugeordnet.
🎮 Bedienung
Stellen Sie die Regler für Server, virtuelle Knoten und Schlüssel ein. Fügen Sie Server hinzu oder entfernen Sie sie, mischen Sie die Schlüssel neu oder setzen Sie die Simulation zurück, um zu beobachten, wie sich die Zuordnung der Schlüssel zu den Servern verändert.
💡 Wussten Sie schon?
Amazon Dynamo (2007) machte konsistentes Hashing mit virtuellen Knoten für Key-Value-Speicher populär; Cassandra übernahm dieselbe Architektur.
Häufig gestellte Fragen
Wie funktioniert eine Schlüsselsuche in konstanter Zeit?
Die Positionen der virtuellen Knoten werden in einem sortierten Array oder balancierten Suchbaum gespeichert. Um den Besitzer eines Schlüssels zu finden, wird der Schlüssel gehasht, um seine Ringposition zu erhalten, dann folgt eine binäre Suche nach der kleinsten virtuellen Knotenposition, die größer oder gleich der Schlüsselposition ist. Diese Suche läuft in O(log(V×N)) Zeit — effektiv konstant bei festem V und N.
Welche realen Systeme nutzen konsistentes Hashing?
Amazon Dynamo (2007) machte konsistentes Hashing mit virtuellen Knoten für sein Key-Value-Speichersystem populär; Cassandra übernahm dieselbe Architektur. Memcached-Client-Bibliotheken (z. B. der Ketama-Algorithmus) nutzen es zur Verteilung von Cache-Schlüsseln über einen Server-Pool. Content-Delivery-Netzwerke und Peer-to-Peer-DHTs wie Chord und Kademlia setzen ebenfalls auf ringbasiertes Hashing.
Was passiert mit Daten, wenn ein Server abstürzt und entfernt wird?
Fällt Server S aus, werden seine virtuellen Knotenpositionen frei. Die Schlüssel, die S besaß, gehören nun dem nächsten Server im Uhrzeigersinn für jeden Bogen. Ist Replikation konfiguriert (typisch 3 Repliken bei Cassandra), existieren die Daten bereits auf den nächsten N−1 Servern im Uhrzeigersinn, sodass der Cluster ohne Datenverlust weiter Lesezugriffe bedienen kann.
Wie hängt konsistentes Hashing mit Chord DHT zusammen?
Chord (Stoica et al., 2001) ist ein Peer-to-Peer-Nachschlageprotokoll, das direkt auf konsistentem Hashing aufbaut. Jeder Peer erhält eine Position auf einem 160-Bit-SHA-1-Ring. Chord fügt eine „Finger-Tabelle“ mit O(log N) Abkürzungen pro Knoten hinzu, sodass jeder Schlüssel in O(log N) Sprüngen gefunden werden kann.
Kann konsistentes Hashing Server mit unterschiedlicher Kapazität verarbeiten?
Ja. Durch Zuweisung von mehr virtuellen Knoten an einen leistungsfähigeren Server — etwa 200 virtuelle Knoten für eine Maschine mit doppeltem RAM gegenüber 100 für einen Standardknoten — wächst dessen Anteil am Ring proportional zu seiner Kapazität. Dieses gewichtete konsistente Hashing wird von Cassandras Token-Zuweisung und von Cloud-Lastverteilern genutzt.
Was ist konsistentes Hashing mit „begrenzter Last“?
2017 veröffentlichte Google „Consistent Hashing with Bounded Loads“, das eine Kapazitätsbeschränkung hinzufügt: Kein Server darf mehr als das (1 + ε)-fache der durchschnittlichen Schlüsselzahl halten. Ist ein Zielserver überlastet, wird der Schlüssel stattdessen dem nächsten Server im Uhrzeigersinn zugewiesen, was die Last gleichmäßiger verteilt.
Wie beeinflusst die Wahl der Hash-Funktion die Ringverteilung?
Eine gute Hash-Funktion muss sowohl Schlüssel als auch Labels virtueller Knoten gleichmäßig über den 2^32-Bit-Ring verteilen. Schlechte Hash-Funktionen erzeugen Klumpenbildung, wodurch manche Bögen selbst mit vielen virtuellen Knoten deutlich länger als der Durchschnitt sind. In der Praxis sind FNV-1a, MurmurHash3 und xxHash beliebte Wahlmöglichkeiten.
Warum verursacht Modulo-Hashing eine massive Schlüssel-Neuverteilung, wenn sich Server ändern?
Bei hash(key) mod N hängt der Slot jedes Schlüssels von N ab. Ändert sich N — etwa von 4 auf 5 —, ändert sich der Modulus für praktisch jeden Schlüssel und remappt etwa (N−1)/N ≈ 80 % von ihnen. Konsistentes Hashing beseitigt dies, indem es Schlüsselpositionen vom Serveranzahl entkoppelt.
Wie viele Schlüssel wandern genau, wenn ein Server zum Ring hinzugefügt wird?
Wird ein neuer Server S an Position p auf dem Ring platziert, beansprucht er den Bogen vom vorherigen Server (im Uhrzeigersinn) bis p. Nur Schlüssel, die in diesen Bogen fallen, wandern — sie wechseln vom bisherigen Besitzer zu S. Im Durchschnitt sind das 1/N aller Schlüssel, wobei N die neue Serveranzahl ist.
Welches Problem lösen virtuelle Knoten, und wie viele sollte man verwenden?
Mit nur einer Position pro Server erzeugt zufällige Platzierung auf dem Ring stark ungleiche Bogenlängen: Manche Server könnten die dreifache durchschnittliche Last erhalten. Die Platzierung jedes physischen Servers an V virtuellen Knotenpositionen teilt den Ring in V×N Segmente und gleicht die Ungleichheit aus. Produktionssysteme (Amazon Dynamo, Cassandra) verwenden üblicherweise 100–200 virtuelle Knoten pro Server.