Consistent Hashing

Kurz: Consistent Hashing ordnet Schlüssel und Server auf einem Ring an. Ein Schlüssel gehört zum nächsten Server im Uhrzeigersinn. Kommt oder geht ein Server, ändert sich nur ein kleiner Teil der Zuordnung.

Genauer: Beim einfachen hash(key) % n ändern sich fast alle Zuordnungen, wenn n sich ändert. Beim Ring wandern im Mittel nur K/n Schlüssel. Virtuelle Knoten (jeder Server erscheint mehrfach auf dem Ring) sorgen für gleichmäßige Verteilung.

Im Detail

• Ring: Hash-Raum 0 … 2^32−1, wird als Kreis gedacht.
• Zuordnung: Schlüssel → erster Server im Uhrzeigersinn.
• Virtuelle Knoten: Glättet ungleiche Abstände und unterschiedlich starke Server.
• Replikation: Schlüssel zusätzlich auf die nächsten N Server legen.
• Einsatz: Caches (Memcached-Cluster), Dynamo, Cassandra, CDNs.
• Alternative: Rendezvous-(HRW-)Hashing.

Siehe auch: Sharding und Partitionierung, Gossip-Protokolle