Consistent hashing en Go : pourquoi hash(key) % N casse et comment un anneau le répare

Vous gérez un cache de 10 nœuds. Pour décider où vit une clé, vous faites l'évidence : hash(key) % 10. C'est rapide, sans état, et chaque client calcule la même réponse. Puis le trafic grimpe et vous ajoutez un 11e nœud.

Désormais hash(key) % 11 donne une réponse différente pour presque toutes les clés. Quasiment tout le cache se retrouve au mauvais endroit, chaque lecture rate, et votre base de données encaisse toute la charge au pire moment.

Ceci est le premier article d'une série sur les mathématiques derrière les systèmes distribués. On commence par la structure qui règle ce problème : le consistent hashing (hachage cohérent). Le code est en Go, et les chiffres ci-dessous viennent de son exécution.

Le problème : le modulo lie chaque clé à N

Avec hash(key) % N, le propriétaire d'une clé dépend de N lui-même. Changez N et tout le mapping bouge. J'ai haché 100 000 clés en passant de 10 à 11 nœuds :

modulo 10->11 moved: 91.0%

Pour qu'une clé garde son propriétaire en passant de N à N+1 nœuds, son hash doit donner le même reste modulo N et modulo N+1. C'est rare, donc environ N/(N+1) des clés bougent. La réponse idéale est bien plus petite : le nouveau nœud devrait prendre environ 1/(N+1) des clés, et personne d'autre ne devrait céder plus que nécessaire.

L'idée : placer clés et nœuds sur le même anneau

On projette l'espace des valeurs de hash sur un cercle, disons de 0 à 2^32 - 1, où la fin reboucle sur le début. Puis :

1. On hache chaque nœud vers une position de l'anneau.
2. On hache chaque clé vers une position de l'anneau.
3. Une clé appartient au premier nœud rencontré dans le sens horaire depuis sa position.

Un nœud ne possède plus que l'arc entre son prédécesseur et lui-même. Ajoutez un nœud : il récupère une tranche de l'arc d'un voisin. Retirez un nœud : son arc tombe chez le suivant. Toutes les autres clés restent exactement où elles étaient. En moyenne seules K/N clés bougent, K étant le nombre de clés et N le nombre de nœuds. C'est le contenu mathématique : la propriété dépend de l'ordre relatif sur un cercle, pas du nombre de nœuds.

Implémentation en Go

L'anneau est une slice triée de positions plus une map position vers nœud. La recherche est une recherche binaire de la première position >= hash(key), avec retour à l'indice 0 après la fin.

type Ring struct {
    replicas int
    points   []uint32          // positions triées sur l'anneau
    owner    map[uint32]string // position -> nœud
}

func hash32(s string) uint32 {
    sum := sha256.Sum256([]byte(s))
    return binary.BigEndian.Uint32(sum[:4])
}

func (r *Ring) Add(node string) {
    for i := 0; i < r.replicas; i++ {
        p := hash32(fmt.Sprintf("%s#%d", node, i))
        r.owner[p] = node
        r.points = append(r.points, p)
    }
    sort.Slice(r.points, func(a, b int) bool { return r.points[a] < r.points[b] })
}

func (r *Ring) Get(key string) string {
    h := hash32(key)
    i := sort.Search(len(r.points), func(i int) bool { return r.points[i] >= h })
    if i == len(r.points) {
        i = 0 // après le dernier point, on reboucle
    }
    return r.owner[r.points[i]]
}

La recherche coûte O(log P) où P est le nombre de points sur l'anneau. Ajouter ou retirer un nœud coûte ici un re-tri, par souci de clarté. Une version de production insérerait en place, et protégerait l'anneau avec un sync.RWMutex puisque les lectures sont bien plus fréquentes que les changements de membres.

Le champ replicas est l'idée suivante, et elle compte plus qu'il n'y paraît.

Nœuds virtuels : corriger l'anneau déséquilibré

Avec un seul point par nœud, les positions sont aléatoires, et des points aléatoires sur un cercle forment des arcs de longueurs très inégales. Un nœud peut hériter d'un énorme arc par hasard. Au lieu de hacher chaque nœud une fois, on le hache replicas fois (node-3#0, node-3#1, ...). Chaque nœud possède alors beaucoup de petits arcs éparpillés, et par la loi des grands nombres sa part totale converge vers 1/N.

J'ai fait tourner 100 000 clés sur 10 nœuds, puis ajouté un 11e, pour plusieurs nombres de nœuds virtuels :

Deux choses ressortent. Le mouvement à l'ajout reste près de l'idéal 9,1 % (contre 91 % pour le modulo) quel que soit le réglage : la stabilité de l'anneau ne dépend pas des vnodes. L'équilibrage, lui, en dépend : avec un seul point, le nœud le plus chargé porte trois fois sa part, et il faut de l'ordre de 100 nœuds virtuels ou plus pour être à environ 20 % de l'uniforme. Le coût est un peu de mémoire et une slice triée plus grande, ce qui est bon marché.

Les nœuds virtuels permettent aussi un placement pondéré gratuitement : donnez à un nœud de capacité double deux fois plus de réplicas.

L'erreur qui ruine tout en silence : une fonction de hachage faible

Mon premier essai utilisait hash/fnv, un hash non cryptographique rapide qui semble le bon outil. Les chiffres étaient mauvais :

vnodes= 10  max/mean=3.96  écart-type=102%     (FNV-1a)
vnodes= 10  max/mean=1.38  écart-type=24.7%    (SHA-256, 4 premiers octets)

Même code, mêmes clés, mêmes 10 nœuds virtuels. La différence, c'est le hash. Des libellés comme node-3#7 sont des chaînes très proches, et FNV-1a mélange mal les entrées similaires : les nœuds virtuels s'agglutinent au lieu de se répartir. Les garanties de l'anneau supposent des positions qui paraissent uniformément aléatoires. Si votre hash ne le fournit pas, ajouter des nœuds virtuels ne vous sauvera pas.

Utilisez un hash à bonne diffusion (avalanche). SHA-256 tronqué fonctionne et reste largement assez rapide ici. En production on voit souvent MurmurHash3 ou xxHash, rapides et bien mélangés. Quel que soit votre choix, mesurez la répartition de charge comme ci-dessus avant de lui faire confiance.

Où ça tourne dans les vrais systèmes

• Caches distribués (bibliothèques clientes memcached comme ketama, clients Redis) : choix du shard par clé de cette façon, donc faire grossir le cache ne le vide pas.
• Bases de type Dynamo (Cassandra, Riak, la lignée de DynamoDB) : les données sont placées sur un anneau de tokens et répliquées sur les nœuds suivants dans le sens horaire.
• Load balancers : routage persistant. L'article sur le load balancing couvre la même structure côté routage de requêtes : Algorithmes de load balancing.

Limites et alternatives

• Hot keys. L'anneau équilibre les clés, pas le trafic. Une clé très populaire surcharge toujours un nœud, et aucun hachage n'y change rien. Il faut de la réplication ou un cache devant.
• Le rééquilibrage reste un vrai travail. Seules K/N clés bougent, mais elles bougent, et quelque chose doit réellement copier ces données.
• Le rendezvous hashing (highest random weight) note chaque nœud pour chaque clé et prend le meilleur. Pas d'anneau ni de vnodes, bon équilibrage, au prix de O(N) par recherche.
• Jump consistent hash n'utilise aucune mémoire et équilibre presque parfaitement, mais on ne peut ajouter ou retirer des nœuds qu'en fin de liste numérotée, ce qui convient mieux à du stockage shardé qu'à un cache dont les nœuds tombent au hasard.

À retenir

• hash(key) % N fait dépendre la propriété de N : changer N déplace environ N/(N+1) des clés (91 % de 10 à 11 nœuds dans mon essai).
• Un anneau de hachage la fait dépendre de la position sur un cercle : ajouter ou retirer un nœud ne déplace qu'environ K/N clés.
• Un point par nœud donne des arcs déséquilibrés. Prenez environ 100 nœuds virtuels ou plus par nœud pour lisser la charge.
• L'anneau suppose un hash qui mélange bien. Un hash faible comme FNV-1a sur des libellés proches a annulé le bénéfice des vnodes dans mon test : mesurez.
• Il équilibre les clés, pas le trafic. Les hot keys demandent une autre réponse.

Prochain article de la série : comment les systèmes distribués ordonnent les événements sans horloge partagée, avec les horloges de Lamport et vectorielles.