Consistent Hashing
Consistent Hashing remappt beim Hinzufügen oder Entfernen von Knoten nur 1/n der Keys neu und minimiert die Umverteilung; es wird in verteiltem Caching und Sharding eingesetzt.
Zweck
Datenbewegung beim Beitreten oder Verlassen von Knoten minimieren; eine Kerntechnik für verteilten Speicher und verteiltes Caching.
Mechanismus
Knoten und Keys werden auf einen Hash-Ring von 0-2^32 abgebildet; jeder Key gehört zum ersten Knoten im Uhrzeigersinn. Das Hinzufügen oder Entfernen eines Knotens betrifft nur die Keys des angrenzenden Bogens. Virtuelle Knoten (mehrere Hash-Punkte pro Knoten) verbessern die Balance. Die Last verteilt sich ungefähr gleichmäßig.
Anwendungsfälle
- Verteiltes Caching (Memcached)
- CDN-Knoten-Sharding
- Datenbank-Sharding (Cassandra)
- Lastverteilung
Beispiele
- Eingabe
Node C joinsOutputOnly keys in C's adjacent arc migrateMinimal migration
Häufige Fehler
- Too few virtual nodes causes uneven load
- Use 150+ virtual nodes per node
Verwandte Begriffe
Hash Table
Eine Hashtabelle bildet Schlüssel über eine Hashfunktion auf ein Bucket-Array ab und bietet im Schnitt O(1) bei Suche/Einfügen/Löschen; sie gehört zu den meistgenutzten Datenstrukturen. GLOSSAR
Bloom Filter
Ein Bloom-Filter approximiert die Zugehörigkeit zu einer Menge mit k Hashfunktionen und einem Bit-Array und bietet Platzeffizienz zum Preis einer False-Positive-Rate. GLOSSAR
Merkle Tree
Ein Merkle-Baum legt Daten-Hashes in den Blättern und Hashes der Kinder in inneren Knoten ab und ermöglicht effiziente Integritätsprüfung großer Daten; er wird in Git und Blockchains verwendet. GLOSSAR