Algorithme
Le hachage cohérent répartit les clés entre serveurs pour qu'ajouter ou retirer un nœud ne déplace que les clés nécessaires ; il sert aux caches et aux bases.
Le hachage cohérent (consistent hashing) est une méthode de répartition des clés entre de nombreux serveurs, proposée par Karger et al. en 1997 pour les caches web distribués. L'espace de hachage est vu comme un anneau : serveurs et clés y sont placés, et chaque clé revient au premier serveur rencontré dans le sens des aiguilles d'une montre. Donner à chaque serveur plusieurs points sur l'anneau, appelés nœuds virtuels, équilibre la charge.
Avec hash(key) % N, changer le nombre de serveurs déplace presque toutes les clés : le taux de succès du cache s'effondre et d'énormes volumes de données doivent migrer. Le hachage cohérent ne déplace en moyenne que 1/(N+1) des clés lors de l'ajout d'un serveur, et uniquement vers le nouveau, ce qui permet d'agrandir ou de réduire un cluster en production. Ketama dans les clients Memcached, l'article Dynamo d'Amazon, Cassandra et les options de hachage cohérent de Nginx et HAProxy reposent sur ce principe.
Commencez par calculer combien de clés le sharding mod-N déplace, puis implémentez un anneau de hachage avec un tableau trié et une recherche dichotomique. Mesurez ensuite comment l'écart de charge diminue avec les nœuds virtuels, et comparez le choix des réplicas, le hachage de rendez-vous et le jump consistent hash. Vous pourrez ainsi expliquer clairement les compromis lors d'un entretien de conception de systèmes.
Ajouter ou retirer un nœud déplace en moyenne environ 1/(N+1) des clés, et les nœuds existants n'échangent jamais de clés entre eux.
L'espace de hachage est un cercle et une clé appartient au premier nœud dans le sens horaire. Une recherche est une dichotomie sur des positions triées.
Plusieurs points par nœud réduisent le déséquilibre de charge, et leur nombre traduit les différences de capacité entre serveurs.
Les réplicas vont aux R nœuds distincts suivants dans le sens horaire ; le hachage de rendez-vous et le jump hash atteignent le même but autrement.
Les 8 premiers octets d'une empreinte MD5 servent de position sur l'anneau, et chaque nœud reçoit 100 nœuds virtuels insérés dans une liste triée avec bisect.insort. get utilise bisect_left pour trouver le premier point à la position de la clé ou après, et revient au début une fois la fin dépassée. Ajouter le nœud D ne déplace qu'environ un quart des clés, et le retirer renvoie chaque clé vers son nœud d'origine.
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.pySix chapitres pour aller de l'installation aux notions essentielles de Hachage cohérent.
Posez vos questions, partagez votre expérience et échangez vos avis sur Hachage cohérent.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.