Algorithmus
Konsistentes Hashing verteilt Schlüssel so auf Server, dass beim Hinzufügen oder Entfernen eines Knotens nur nötige Schlüssel wandern – für Caches und Speicher.
Konsistentes Hashing ist ein Verfahren, Schlüssel auf viele Server zu verteilen, das Karger et al. 1997 für verteilte Web-Caches vorgestellt haben. Der Hash-Wertebereich wird als Ring betrachtet, Server und Schlüssel liegen auf demselben Ring, und jeder Schlüssel gehört dem ersten Server im Uhrzeigersinn. Mehrere Punkte pro Server, sogenannte virtuelle Knoten, gleichen die Last aus.
Bei hash(key) % N ändert sich mit der Serveranzahl die Position fast aller Schlüssel: Die Cache-Trefferquote bricht ein, und große Datenmengen müssen umziehen. Konsistentes Hashing verschiebt beim Hinzufügen eines Servers im Mittel nur 1/(N+1) der Schlüssel, und zwar nur auf den neuen Server. So lassen sich Cluster im laufenden Betrieb vergrößern und verkleinern. Ketama in Memcached-Clients, das Dynamo-Paper von Amazon, Cassandra sowie die Consistent-Hash-Optionen von Nginx und HAProxy beruhen auf diesem Prinzip.
Berechnen Sie zuerst, wie viele Schlüssel bei mod-N-Sharding umziehen, und implementieren Sie dann einen Hash-Ring mit sortiertem Array und binärer Suche. Messen Sie anschließend, wie die Lastschwankung mit mehr virtuellen Knoten sinkt, und vergleichen Sie Replikatauswahl, Rendezvous-Hashing und Jump Consistent Hash. Damit können Sie die Abwägungen auch im System-Design-Interview klar erklären.
Beim Hinzufügen oder Entfernen eines Knotens wandern im Erwartungswert etwa 1/(N+1) der Schlüssel; bestehende Knoten tauschen untereinander nichts aus.
Der Hash-Raum ist ein Kreis, und ein Schlüssel gehört dem ersten Knoten im Uhrzeigersinn. Eine Suche ist eine binäre Suche über sortierte Positionen.
Viele Punkte pro Knoten verringern Lastungleichgewichte, und ihre Anzahl drückt unterschiedliche Serverkapazitäten aus.
Replikate liegen auf den nächsten R verschiedenen Knoten im Uhrzeigersinn; Rendezvous-Hashing und Jump Hash erreichen dasselbe Ziel anders.
Die ersten 8 Bytes eines MD5-Digests dienen als Ringposition, und jeder Knoten erhält 100 virtuelle Knoten, die bisect.insort in eine sortierte Liste einfügt. get sucht mit bisect_left den ersten Punkt ab der Schlüsselposition und springt nach dem Ende wieder an den Anfang. Das Hinzufügen von Knoten D verschiebt nur etwa ein Viertel der Schlüssel, und nach dem Entfernen landet jeder Schlüssel wieder auf seinem ursprünglichen Knoten.
consistent_hashing.py
import bisect
import hashlib
def h(key: str) -> int:
return int.from_bytes(hashlib.md5(key.encode()).digest()[:8], "big")
class HashRing:
def __init__(self, nodes=(), vnodes=100):
self.vnodes = vnodes
self.points = [] # sorted hash positions on the ring
self.owner = {} # position -> physical node
for node in nodes:
self.add(node)
def add(self, node):
for i in range(self.vnodes):
p = h(f"{node}#{i}")
bisect.insort(self.points, p)
self.owner[p] = node
def remove(self, node):
for i in range(self.vnodes):
p = h(f"{node}#{i}")
self.points.pop(bisect.bisect_left(self.points, p))
del self.owner[p]
def get(self, key):
if not self.points:
raise LookupError("ring is empty")
i = bisect.bisect_left(self.points, h(key)) % len(self.points)
return self.owner[self.points[i]]
ring = HashRing(["A", "B", "C"])
keys = [f"user:{n}" for n in range(10_000)]
before = {k: ring.get(k) for k in keys}
ring.add("D")
moved = sum(before[k] != ring.get(k) for k in keys)
print(f"moved {moved / len(keys):.1%} of keys") # about 25%
ring.remove("D")
print(all(ring.get(k) == before[k] for k in keys)) # True
python consistent_hashing.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Konsistentes Hashing.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Konsistentes Hashing aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.