Konsistentes Hashing: stabile Schlüssel-Platzierung, wenn Knoten kommen und gehen

Worum es geht

Die Cassandra-Dokumentation (zitiert) stellt naives Hashing – Schlüssel-Hash modulo der Anzahl Buckets – dem konsistenten Hashing gegenüber: Jeder Knoten besitzt einen oder mehrere Tokens auf einem fortlaufenden Hash-Ring, ein Schlüssel wird auf den Ring gehasht, und der Besitz geht an den nächsten Knoten, wenn man den Ring in eine Richtung entlanggeht. Ändert sich die Anzahl der Knoten, verschiebt sich nur ein kleiner Bruchteil der Schlüssel. Mit einem Token pro Knoten und wenigen Knoten gibt es keine Token-Position für einen neuen Knoten, die den Ring ausgeglichen lässt, und ungleiche Bereiche bedeuten ungleiche Last; Cassandra folgt deshalb dem Dynamo-Paper und weist mehrere Tokens pro physischem Knoten zu, die virtuellen Knoten, sodass selbst ein einzelner hinzugefügter Knoten viele kleine Stücke von vielen Nachbarn übernimmt.

Das nginx-upstream-Modul (zitiert) bietet dieselbe Wahl: Einfaches hash $key kann die meisten Schlüssel neu zuordnen, wenn ein Server entfernt wird, während hash $key consistent die Ketama-Methode verwendet, sodass sich nur wenige Schlüssel verschieben. Envoy (zitiert) bietet einen Ring-Hash-Balancer und Maglev, eine tabellenbasierte Variante mit schnellerem Nachschlagen; seine Dokumentation merkt an, dass Maglev beim Entfernen von Hosts mehr Schlüssel verschiebt als der Ring.

Warum es wichtig ist

Caches verlieren bei jeder Änderung der Knotenmitgliedschaft ihre Trefferquote, wenn Schlüssel sich verstreuen; partitionierte Speicher müssten den Grossteil der Daten verschieben; sitzungsaffine Dienste würden bei jedem Deployment ihre Affinität verlieren. Konsistentes Hashing begrenzt die Störung auf das, was sich tatsächlich geändert hat.

So wird es angewendet

• Einen Hash-Schlüssel mit ausreichender Kardinalität wählen (Nutzer-ID, Mandanten-ID, Cache-Schlüssel), nicht etwas wie die Client-IP hinter einem NAT.
• Eine Bibliothek oder Proxy-Implementierung verwenden; virtuelle Knoten oder Tabellengrösse so konfigurieren, dass die Last pro Knoten ausgeglichen ist, und den Anteil pro Host überwachen (Envoy stellt Gauges für minimale und maximale Einträge pro Host bereit).
• Für Replikation die nächsten k verschiedenen physischen Knoten auf dem Ring nehmen, wobei virtuelle Knoten derselben Maschine und, wenn möglich, desselben Racks oder derselben Zone übersprungen werden.
• Planen, wie sich Daten bewegen, wenn ein Knoten beitritt: Der neue Besitzer muss seinen Bereich erhalten, bevor er bedient, oder während einer Übergangsphase Fehltreffer vom alten Besitzer bedienen lassen.
• Die Hash-Funktion für die Lebensdauer des Deployments fixieren; sie zu ändern ordnet alles neu zu.

Stolpersteine

Konsistentes Hashing behebt keine Hot Keys: Ein beliebter Schlüssel landet weiterhin auf einem einzigen Knoten. Gewichtete Knoten brauchen proportional mehr virtuelle Knoten. Konsistentes Hashing hat nichts mit Datenkonsistenz zu tun; es entscheidet nur über die Platzierung.