Pourquoi ne pas simplement utiliser clé mod N pour choisir un serveur ?

Avec hash(clé) mod N, changer N d'un nombre de serveurs à un autre rebrasse presque toutes les clés, car le modulo change pour chacune d'elles. Le hachage cohérent évite cela en découplant les positions des clés du nombre de serveurs.

Combien de clés se déplacent lors de l'ajout d'un serveur ?

En moyenne, seules environ 1/N des clés se déplacent, où N est le nombre de serveurs, car un nouveau serveur ne s'approprie que l'arc de l'anneau entre lui-même et le serveur précédent dans le sens horaire.

Que sont les nœuds virtuels ?

Chaque serveur physique est placé à de nombreux points sur l'anneau, appelés nœuds virtuels ou répliques. Au lieu d'une position par serveur, V positions répartissent la possession du serveur en de nombreux petits arcs, ce qui uniformise la charge.

Pourquoi les nœuds virtuels améliorent-ils l'équilibrage de charge ?

Avec un seul point par serveur, un placement aléatoire peut donner à certains serveurs d'immenses arcs et à d'autres de minuscules. De nombreux nœuds virtuels moyennent ces variations, si bien que chaque serveur physique finit par obtenir une part plus équitable des clés.

Comment une clé trouve-t-elle son serveur sur l'anneau ?

La clé est hachée vers une position sur l'anneau, puis on avance dans le sens horaire jusqu'à atteindre le premier serveur (nœud virtuel). Ce serveur possède la clé. Si l'on dépasse le sommet de l'anneau, on revient au début.

Où le hachage cohérent est-il utilisé ?

Il alimente les caches distribués comme le partitionnement client de memcached, les bases clé-valeur telles qu'Amazon Dynamo, Cassandra et Riak, les réseaux de diffusion de contenu, et les tables de hachage distribuées pair-à-pair (DHT) comme Chord.

Que deviennent les clés lorsqu'un serveur est supprimé ?

Seules les clés possédées par les nœuds virtuels du serveur supprimé sont réattribuées. Chaque clé concernée se déplace dans le sens horaire vers le serveur survivant suivant, tandis que toutes les autres clés restent exactement où elles étaient.

Combien de nœuds virtuels devrais-je utiliser ?

En pratique, les systèmes utilisent entre environ 100 et plusieurs centaines de nœuds virtuels par serveur. Plus de répliques donnent un équilibre plus lisse mais coûtent davantage en mémoire et en surcharge de structure de recherche.

Comment les clés sont-elles exactement associées à l'anneau ?

Une fonction de hachage associe chaque clé et chaque étiquette de nœud virtuel à un nombre dans une plage fixe, par exemple de 0 à 2^32 − 1. Cette plage est traitée comme un cercle, si bien que la plus grande valeur revient à la plus petite.

Accueil▸Informatique Distribuée & Parallèle▸Hachage Cohérent — L'Anneau de Hachage

💍 Hachage Cohérent — L'Anneau de Hachage

Placez clés et serveurs sur un anneau de hachage afin que l'ajout ou la suppression d'un nœud ne remappe qu'une petite fraction des clés. Les nœuds virtuels lissent la charge — la technique derrière les caches distribués et les DHT.

Informatique Distribuée & Parallèle3DModérée60 FPS

À propos du Hachage Cohérent

Le hachage cohérent résout un problème critique des systèmes distribués : comment attribuer des clés de données à des serveurs de sorte que l'ajout ou la suppression d'un nœud rebrasse le moins de clés possible. La technique place à la fois les clés et les serveurs à des positions sur un anneau de hachage circulaire de taille 2^32. Chaque clé appartient au premier serveur trouvé dans le sens horaire à partir de sa position. Avec l'approche naïve du modulo (hash(clé) mod N), changer N d'un nombre de serveurs à un autre peut remapper presque toutes les clés — catastrophique pour un cache en production. Le hachage cohérent limite la perturbation à environ 1/N des clés en moyenne, car seul l'arc de l'anneau adjacent au serveur ajouté ou supprimé change de propriétaire.

Les nœuds virtuels (aussi appelés répliques) sont le raffinement pratique : chaque serveur physique est placé à V positions sur l'anneau au lieu d'une seule, divisant sa possession en de nombreux petits arcs. Cela lisse considérablement la distribution de charge — sans nœuds virtuels, un seul serveur pourrait par hasard s'accaparer 40 % des clés ; avec 100+ nœuds virtuels, la distribution converge vers l'idéal de 1/N par serveur. Ajustez les serveurs, le nombre de nœuds virtuels et l'ensemble de clés avec les curseurs, puis ajoutez ou supprimez des serveurs pour observer combien peu de clés (surlignées en blanc) doivent se déplacer.

Questions fréquentes

Pourquoi le hachage par modulo provoque-t-il une redistribution massive des clés lorsque les serveurs changent ?

Avec hash(clé) mod N, l'emplacement auquel chaque clé est associée dépend de N. Quand N change — disons de 4 à 5 — le modulo change pour pratiquement chaque clé, remappant environ (N−1)/N ≈ 80 % d'entre elles. Le hachage cohérent élimine ce problème en découplant les positions des clés du nombre de serveurs : chaque clé correspond toujours à la même position sur l'anneau, et seule la recherche dans le sens horaire change lors de l'ajout ou de la suppression d'un serveur.

Combien de clés se déplacent exactement lors de l'ajout d'un serveur à l'anneau ?

Lorsqu'un nouveau serveur S est placé à la position p sur l'anneau, il s'approprie l'arc allant du serveur précédent (dans le sens horaire) jusqu'à p. Seules les clés situées dans cet arc se déplacent — elles passent de leur ancien propriétaire à S. En moyenne, cela représente 1/N de toutes les clés, où N est le nouveau nombre de serveurs. Toutes les autres clés restent avec leurs propriétaires existants.

Quel problème les nœuds virtuels résolvent-ils, et combien devrait-on en utiliser ?

Avec une seule position par serveur, un placement aléatoire sur l'anneau produit des longueurs d'arc très inégales : certains serveurs peuvent recevoir 3 fois la charge moyenne. Placer chaque serveur physique à V positions de nœuds virtuels divise l'anneau en V×N segments, moyennant le déséquilibre. Les systèmes en production (Amazon Dynamo, Cassandra) utilisent couramment 100 à 200 nœuds virtuels par serveur, où l'écart-type de la charge tombe sous 10 % de la moyenne.

Comment fonctionne une recherche de clé en temps constant ?

Les positions des nœuds virtuels sont stockées dans un tableau trié ou un arbre binaire de recherche équilibré. Pour trouver le propriétaire d'une clé, on hache la clé pour obtenir sa position sur l'anneau, puis on effectue une recherche binaire de la plus petite position de nœud virtuel supérieure ou égale à la position de la clé (en revenant à la position 0 si aucune n'est trouvée). Cette recherche s'exécute en O(log(V×N)) — effectivement constante pour V et N fixés.

Quels systèmes réels utilisent le hachage cohérent ?

Amazon Dynamo (2007) a popularisé le hachage cohérent avec nœuds virtuels pour sa base clé-valeur ; Cassandra a hérité de la même architecture. Les bibliothèques clientes memcached (par exemple l'algorithme ketama) l'utilisent pour partitionner les clés de cache sur un ensemble de serveurs. Les réseaux de diffusion de contenu et les tables de hachage distribuées pair-à-pair (DHT) telles que Chord et Kademlia reposent aussi sur le hachage en anneau.

Que deviennent les données lorsqu'un serveur tombe en panne et est supprimé ?

Si le serveur S tombe en panne, ses positions de nœuds virtuels deviennent vacantes. Les clés que S possédait appartiennent désormais au serveur suivant dans le sens horaire pour chaque arc. Si la réplication est configurée (typiquement 3 répliques dans Cassandra), les données existent déjà sur les N−1 serveurs suivants dans le sens horaire, si bien que le cluster continue à servir les lectures sans perte de données. Les quorums d'écriture assurent la cohérence pendant le basculement.

Quel est le rapport entre le hachage cohérent et la DHT Chord ?

Chord (Stoica et al., 2001) est un protocole de recherche pair-à-pair construit directement sur le hachage cohérent. Chaque pair se voit attribuer une position sur un anneau SHA-1 de 160 bits. Chord ajoute une « table de doigts » (finger table) de O(log N) raccourcis par nœud afin que toute clé puisse être localisée en O(log N) sauts — combinant le hachage cohérent avec une structure de routage distribuée efficace.

Le hachage cohérent peut-il gérer des serveurs de capacités différentes ?

Oui. En attribuant davantage de nœuds virtuels à un serveur de plus grande capacité — disons 200 nœuds virtuels pour une machine avec le double de RAM contre 100 pour un nœud standard — sa part de l'anneau augmente proportionnellement à sa capacité. Ce hachage cohérent pondéré est utilisé par l'allocation de jetons de Cassandra et par les répartiteurs de charge cloud pour acheminer plus de trafic vers les instances plus grandes.

Qu'est-ce que le hachage cohérent à « charge bornée » ?

En 2017, Google a publié « Consistent Hashing with Bounded Loads », qui ajoute une contrainte de capacité : aucun serveur ne peut détenir plus de (1 + ε) fois le nombre moyen de clés. Lorsqu'un serveur cible est surchargé, la clé est attribuée au serveur suivant dans le sens horaire à la place, répartissant la charge plus uniformément. Cette variante est utilisée dans les répartiteurs de charge en production de Google.

Comment le choix de la fonction de hachage affecte-t-il la distribution sur l'anneau ?

Une bonne fonction de hachage doit distribuer à la fois les clés et les étiquettes de nœuds virtuels uniformément sur l'anneau de 2^32 bits. Les fonctions de hachage médiocres produisent des regroupements, ce qui fait que certains arcs sont bien plus longs que la moyenne même avec de nombreux nœuds virtuels. En pratique, FNV-1a, MurmurHash3 et xxHash sont des choix populaires pour leur rapidité et leurs propriétés de distribution uniforme.

⚙ Sous le capot

hachage cohérentanneau de hachagenœuds virtuelséquilibrage de chargeCanvas 2D

3D · Moteur de rendu Three.js / WebGL · Cible 60 FPS · fonctionne entièrement côté client, sans installation