Algoritmo
L'hashing consistente distribuisce le chiavi tra i server così che aggiungere o rimuovere un nodo sposti solo le chiavi necessarie; si usa in cache e database.
L'hashing consistente è un metodo per distribuire chiavi su molti server, proposto da Karger e colleghi nel 1997 per le cache web distribuite. Lo spazio degli hash viene visto come un anello: server e chiavi vi sono collocati e ogni chiave appartiene al primo server incontrato in senso orario. Assegnare a ogni server più punti sull'anello, detti nodi virtuali, bilancia il carico.
Con hash(key) % N, cambiare il numero di server sposta quasi tutte le chiavi: il tasso di successo della cache crolla e occorre migrare grandi quantità di dati. L'hashing consistente sposta in media solo 1/(N+1) delle chiavi quando si aggiunge un server, e solo verso quello nuovo, così il cluster può crescere e ridursi in esercizio. Ketama nei client Memcached, l'articolo Dynamo di Amazon, Cassandra e le opzioni di hash consistente di Nginx e HAProxy si basano su questa idea.
Inizia calcolando quante chiavi sposta lo sharding mod-N, poi implementa un anello di hash con un array ordinato e la ricerca binaria. Misura quindi come si riduce la variabilità del carico aggiungendo nodi virtuali e confronta la scelta delle repliche, il rendezvous hashing e il jump consistent hash. Con queste basi saprai spiegare con chiarezza i compromessi anche nei colloqui di system design.
Aggiungere o rimuovere un nodo sposta in media circa 1/(N+1) delle chiavi, e i nodi esistenti non si scambiano mai chiavi tra loro.
Lo spazio degli hash è un cerchio e una chiave appartiene al primo nodo in senso orario. La ricerca è una ricerca binaria su posizioni ordinate.
Più punti per nodo riducono lo squilibrio di carico, e il loro numero esprime le differenze di capacità tra i server.
Le repliche vanno ai successivi R nodi distinti in senso orario; il rendezvous hashing e il jump hash raggiungono lo stesso obiettivo in altro modo.
I primi 8 byte di un digest MD5 fanno da posizione sull'anello, e ogni nodo riceve 100 nodi virtuali inseriti in una lista ordinata con bisect.insort. get usa bisect_left per trovare il primo punto nella posizione della chiave o dopo, e superata la fine riparte dall'inizio. Aggiungere il nodo D sposta solo circa un quarto delle chiavi, e rimuoverlo riporta ogni chiave al nodo originale.
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.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Hashing consistente.
Fai domande, condividi la tua esperienza e scambia opinioni su Hashing consistente.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.