Consistent Hashing

Quand on ajoute un nœud à un cluster, ne déplacer que 1/N des clés au lieu de tout rééquilibrer.

Problème

Naïvement, distribuer K clés sur N nœuds avec hash(key) % N est correct mais devient catastrophique au rescaling : ajouter un nœud (N → N+1) change la position de presque toutes les clés ; on doit déplacer ~ K(N/N+1) données. Pour un cache de 100 GB et 10 nœuds, ajouter un 11^e nœud déplace ~91 GB — inacceptable.

Forces

• L'ajout/retrait de nœud doit être quasi-instantané (autoscaling, panne).
• La distribution des clés doit rester uniforme malgré la croissance.
• Les nœuds chauds (hot keys) déséquilibrent l'anneau.
• Un client doit pouvoir calculer la cible sans coordinateur centralisé.

Solution

Placer nœuds et clés sur un anneau virtuel de hashs (espace [0, 2⁶⁴)). Une clé est servie par le premier nœud rencontré en allant dans le sens horaire. Ajouter un nœud n'invalide que les clés situées entre lui et le nœud précédent — soit ~ K/N en moyenne. Pour éviter les déséquilibres dus à de petits clusters, chaque nœud physique est représenté par v virtual nodes (typiquement 100-200) répartis aléatoirement sur l'anneau. Variants : Jump consistent hash (Google, 2014) pour des espaces simples, Rendezvous hashing (Highest Random Weight).

Structure

Ring [0 .. 2^64):

    Node A vNode1  ──┐
                     │
    key X ──► hashed │
                     ▼  (closest clockwise)
                  Node A vNode1 serves it
                     │
    Node B vNode1 ───┘
       :
    Node C vNode1
       :
    A vNode2, B vNode2, C vNode2 ... (interleaved)

Add Node D: only ~K/4 keys move (those falling between D's vNodes and their successors).

Implémentation EDI

Un hub EDI multi-tenant utilise consistent hashing pour distribuer les partenaires sur un pool de workers : hash(partnerId) → worker. Quand on ajoute un worker, seuls ~1/N des partenaires migrent, sans rebuild complet du cache de leur état. Kafka utilise consistent hashing pour le partitionnement quand on ajoute des partitions à un topic (avec sticky partitioner). Pour des CDN EDI (cas exotique : caching de catalogues PRICAT), Akamai et Cloudflare l'utilisent depuis 20 ans.

Anti-patterns

• Pas de virtual nodes — distribution déséquilibrée sur petits clusters (3-5 nœuds).
• Hash function biaisée — concentration sur quelques nœuds (utiliser MurmurHash, xxHash, SHA).
• Cluster avec différents capacités sans pondération — un petit nœud absorbe autant qu'un gros.
• Modification du nombre de virtual nodes après mise en production — réorganisation massive.
• Hot keys non gérées — un compte premium qui prend 80% du trafic sature son nœud.

Patterns liés

• Sharding — usage typique du consistent hashing pour le placement.
• Competing Consumers — alternative quand l'affinity n'est pas requise.
• Rate Limiter — peut être réparti via consistent hashing par tenant.
• Partition Tolerance — discute des trade-offs CAP qui président.

Sources

• Karger D., Lehman E., Leighton T., Panigrahy R., Levine M., Lewin D. — Consistent Hashing and Random Trees, STOC 1997. dl.acm.org/doi/10.1145/258533.258660
• DeCandia G. et al. — Dynamo: Amazon's Highly Available Key-Value Store, SOSP 2007. allthingsdistributed.com — Dynamo paper
• Kleppmann M. — Designing Data-Intensive Applications, O'Reilly 2017, chap. 6 « Partitioning ».