Consistent Hashing

Le hachage cohérent remappe seulement 1/n des clés lors de l'ajout ou du retrait de nœuds, minimisant la redistribution ; il est utilisé dans le cache distribué et le sharding.

Objectif

Minimiser le déplacement de données quand des nœuds rejoignent ou quittent le système, technique centrale du stockage et du cache distribués.

Mécanisme

Place les nœuds et les clés sur un anneau de hash de 0 à 2^32 ; chaque clé appartient au premier nœud dans le sens horaire. Ajouter ou retirer un nœud n'affecte que les clés de l'arc adjacent. Les nœuds virtuels (plusieurs points de hash par nœud) améliorent l'équilibre. La charge se répartit à peu près uniformément.

Cas d’usage

Cache distribué (Memcached)
Sharding de nœuds CDN
Sharding de bases de données (Cassandra)
Répartition de charge

Exemples

entrée

Node C joins

Output

Only keys in C's adjacent arc migrate

Minimal migration

Erreurs courantes

Too few virtual nodes causes uneven load: Use 150+ virtual nodes per node

Termes associés

Une table de hachage associe des clés à un tableau de compartiments via une fonction de hachage, offrant recherche/insertion/suppression en O(1) en moyenne ; c'est l'une des structures de données les plus utilisées.

Un filtre de Bloom approxime l'appartenance à un ensemble avec k fonctions de hachage et un tableau de bits, offrant une efficacité spatiale au prix d'un taux de faux positifs.

Un arbre de Merkle place les hachés des données aux feuilles et les hachés des enfants aux nœuds internes, permettant une vérification d'intégrité efficace de grandes masses de données ; utilisé dans Git et les blockchains.

References