Le hachage cohérent expliqué : anneau de hachage, nœuds virtuels et rééquilibrage

Vous répartissez un cache sur dix serveurs avec hash(key) % 10. Le trafic augmente, vous ajoutez un onzième serveur, et le taux de succès s'effondre : presque chaque clé correspond désormais à un autre serveur, le cache est froid partout à la fois et la base de données derrière lui encaisse toute la charge. Le hachage cohérent (consistent hashing) existe précisément pour éviter cela.

Cet article explique l'anneau de hachage et les nœuds virtuels avec un diagramme, mesure leur apport, montre une implémentation compacte et compare les alternatives que vous croiserez dans les vrais systèmes : le hachage rendezvous, le jump hash, Maglev et les slots de hachage fixes.

Pourquoi le hachage modulo casse

Avec server = hash(key) % N, l'affectation dépend de N. Changez N, et une clé ne reste en place que si son hash donne le même reste pour les deux valeurs, ce qui est rare. Dans une simulation rapide avec un million de clés :

L'idéal est 1/11, soit environ 9,1 % : le nouveau serveur devrait prendre sa juste part et rien d'autre ne devrait bouger. L'anneau s'en approche ; l'écart restant vient de ce que les jetons du nouveau serveur tombent sur des arcs un peu plus grands que la moyenne.

Pour un cache, la différence se joue entre une brève baisse du taux de succès et un démarrage à froid. Pour une base de données shardée ou un ensemble de workers avec état, c'est la différence entre déplacer un dixième des données et les déplacer presque toutes.

L'anneau de hachage

Le hachage cohérent, introduit par Karger et ses collègues en 1997 pour le cache web, projette les serveurs et les clés sur le même espace de hachage circulaire, par exemple les entiers de 0 à 2^64 - 1, la plus grande valeur revenant à 0.

1. Hachez le nom de chaque serveur vers une position sur l'anneau.
2. Hachez chaque clé vers une position sur l'anneau.
3. Partez de la position de la clé dans le sens horaire. Le premier serveur rencontré possède la clé.

Ajouter un serveur le place à une position, et il ne reprend que les clés situées entre son prédécesseur et lui. Toutes les autres clés restent où elles étaient. Retirer un serveur confie ses clés au serveur suivant dans le sens horaire. Rien d'autre ne change.

Les nœuds virtuels : corriger le déséquilibre

Avec une seule position par serveur, les arcs entre serveurs sont aléatoires et inégaux : certains serveurs possèdent une part de l'anneau bien plus grande que d'autres. La même simulation avec dix serveurs montre l'ampleur de l'écart :

La solution consiste à donner à chaque serveur de nombreuses positions, appelées nœuds virtuels ou jetons (tokens), en hachant des noms comme cache-a#0, cache-a#1 et ainsi de suite. Les nœuds virtuels apportent aussi deux autres avantages :

• Les poids. Un serveur doté de deux fois plus de mémoire reçoit deux fois plus de jetons.
• Des pannes plus douces. Quand un serveur tombe, ses nombreux petits arcs reviennent à de nombreux successeurs différents : sa charge se répartit sur le cluster au lieu de doubler celle d'un seul voisin.

Le prix à payer est une table de recherche plus grande et davantage de métadonnées à déplacer quand la composition change. Cassandra illustre ce compromis : il utilisait par défaut 256 jetons par nœud jusqu'à ce que la version 4.0 abaisse ce défaut à 16, associé à un algorithme d'allocation qui place ces 16 jetons de façon régulière plutôt qu'aléatoire.

Une petite implémentation

Un anneau, c'est une liste triée de positions de jetons et une recherche dichotomique :

import bisect
import hashlib

def hash64(value: str) -> int:
    # MD5 for spread, not security; any well-mixed hash works
    return int.from_bytes(hashlib.md5(value.encode()).digest()[:8], "big")

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.vnodes = vnodes
        self.points = []   # sorted token positions
        self.owners = {}   # position -> server
        for server in servers:
            self.add(server)

    def add(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            bisect.insort(self.points, p)
            self.owners[p] = server

    def remove(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            self.points.remove(p)
            del self.owners[p]

    def lookup(self, key: str) -> str:
        i = bisect.bisect_right(self.points, hash64(key)) % len(self.points)
        return self.owners[self.points[i]]

Les recherches coûtent O(log T) pour T jetons. Les versions de production gèrent aussi les collisions de jetons et maintiennent une vue identique de la composition chez chaque client, car deux clients dotés de listes de serveurs différentes ne s'accordent pas sur l'emplacement des clés.

La réplication sur l'anneau

Les systèmes de stockage utilisent l'anneau pour le placement autant que pour le routage. L'article sur Dynamo d'Amazon stocke chaque clé sur les N premiers serveurs distincts dans le sens horaire depuis sa position, sa preference list, en sautant les jetons supplémentaires d'un serveur déjà présent dans la liste. Avec N = 3, la perte d'un serveur laisse encore deux copies de tout ce qu'il détenait, sur des serveurs voisins sur l'anneau.

La même idée « avancer dans le sens horaire et sauter les doublons » s'étend aux racks et aux zones : sautez des jetons jusqu'à ce que les répliques couvrent des domaines de panne différents.

Les alternatives que vous croiserez

Le jump consistent hash convient au stockage shardé où les shards sont numérotés et ne font que croître. Le hachage rendezvous convient aux petits ensembles de serveurs, où un coût O(N) par recherche ne compte pas. Les slots de hachage échangent le placement automatique contre des déplacements explicites, pilotés par l'opérateur, que beaucoup d'équipes préfèrent pour les bases de données.

Clés chaudes et charges bornées

Le hachage cohérent équilibre les clés, pas le trafic. Un utilisateur célèbre ou un produit viral atterrit toujours sur un seul serveur. Le hachage cohérent à charges bornées plafonne chaque serveur à un pourcentage donné au-dessus de la moyenne et envoie le surplus au serveur suivant dans le sens horaire. HAProxy l'implémente avec son paramètre hash-balance-factor. Pour les clés vraiment chaudes, il vous faut quand même répliquer cette clé, regrouper les requêtes ou placer un petit cache local devant.

Les pièges d'exploitation

• Changer la fonction de hachage ou le schéma de jetons redistribue tout, exactement comme le hachage modulo. Traitez-le comme une migration.
• La composition doit être cohérente. Distribuez la liste des serveurs depuis une source unique, comme un service de coordination ou la configuration du répartiteur de charge, et modifiez-la en une seule étape.
• Les serveurs instables provoquent du churn. Un serveur qui échoue aux health checks toutes les quelques minutes fait faire des allers-retours à ses clés. Ajoutez de l'hystérésis avant de le retirer et de le réintégrer.
• Les nouveaux serveurs démarrent à froid. Un nouveau nœud de cache reçoit immédiatement sa part de requêtes ; préchauffez-le ou augmentez progressivement son poids si le backend ne peut pas absorber les défauts de cache.

Le diagramme de l'anneau de hachage

Comment le lire :

• Le cercle est l'espace de hachage. Les positions croissent dans le sens horaire, et le sommet est l'endroit où la plus grande valeur revient à zéro.
• Les jetons colorés sont des nœuds virtuels. Chaque couleur est un serveur, et chaque serveur possède plusieurs jetons répartis sur l'anneau.
• Les clés sont placées à la position de leur hash, et les flèches pointent dans le sens horaire vers le jeton qui les possède.
• Les jetons en pointillé appartiennent au serveur D, en cours d'ajout. Seules les clés situées juste avant les jetons de D, dans le sens antihoraire, changent de propriétaire.
• La légende et le bloc Markdown listent les serveurs et les chiffres de déplacement de la simulation ci-dessus.

Dessiner clairement les schémas de hachage

• Dessinez l'anneau, pas une table. La règle du sens horaire est visuelle ; une table de recherche cache pourquoi seules certaines clés bougent.
• Colorez les jetons par serveur et ajoutez une légende, au lieu de tirer une arête de chaque jeton vers son serveur.
• Montrez un changement de composition. Un anneau statique explique le routage ; un anneau où un serveur arrive explique tout l'intérêt de la technique.
• Placez de vrais chiffres à côté : clés déplacées et répartition de la charge. Ils convainquent davantage que l'image.

Le hachage cohérent revient dans de nombreux articles de conception de systèmes de ce blog : dans le diagramme de sharding de base de données pour placer les données, dans le diagramme de répartiteur de charge pour le routage persistant et dans le diagramme des stratégies de cache pour les caches distribués.

Le construire dans Archboard

1. Connectez-vous avec Google ou GitHub et créez un diagramme.
2. Ajoutez une grande forme Ellipse du pack Base pour figurer l'anneau.
3. Ajoutez sur l'anneau de petites formes Ellipse comme jetons, colorées par serveur : deux pour chacun des serveurs A, B et C, et deux en pointillé pour le nouveau serveur D.
4. Ajoutez quatre nœuds Redis du pack Données en colonne à côté de l'anneau comme légende, colorés comme leurs jetons.
5. Ajoutez les clés sous forme d'étiquettes Texte du pack Base sur l'anneau, avec de courtes flèches vers leurs jetons.
6. Ajoutez un bloc Markdown du pack Base avec les chiffres de déplacement des clés et de charge.

L'exemple utilise 14 nœuds de diagramme et reste dans les limites de l'offre Free.

FAQ

Quel problème le hachage cohérent résout-il ? Il garde la plupart des clés sur le même serveur quand on ajoute ou retire des serveurs. Avec le hachage modulo, changer le nombre de serveurs réaffecte presque toutes les clés ; avec le hachage cohérent, environ 1/N des clés seulement se déplacent.

Que sont les nœuds virtuels dans le hachage cohérent ? Chaque serveur physique est placé de nombreuses fois sur l'anneau sous des noms différents. Plus de positions rendent les arcs plus réguliers, permettent de pondérer les serveurs selon leur capacité et répartissent la charge d'un serveur en panne sur beaucoup d'autres.

Combien de nœuds virtuels faut-il par serveur ? Assez pour une répartition régulière à la taille de votre cluster : dans notre simulation, 100 par serveur ont maintenu le serveur le plus chargé à moins de 7 % de la moyenne sur dix serveurs. Les systèmes dotés d'une allocation de jetons plus intelligente, comme Cassandra 4.0 et suivants, en utilisent bien moins.

Redis Cluster utilise-t-il le hachage cohérent ? Pas au sens de l'anneau. Redis Cluster associe les clés à 16 384 slots de hachage fixes et attribue les slots aux nœuds ; déplacer des données revient à déplacer explicitement des slots.

Quelle est la différence entre le hachage cohérent et le hachage rendezvous ? Tous deux déplacent environ 1/N des clés quand la composition change. Le hachage rendezvous note chaque serveur pour chaque clé et choisit le meilleur : il n'a pas besoin d'anneau, mais coûte O(N) par recherche.

Commencez gratuitement — un siège, sans carte bancaire.