Anneau de hachage cohérent Consistent hash ring
Répartir des clés sur N nœuds de sorte qu'ajouter ou retirer un nœud ne déplace que 1/N des clés — au lieu de toutes avec un simple hash % N.
Inventé par David Karger et son équipe (1997). On place nœuds et clés sur un anneau de hachage circulaire (de 0 à 2³²-1) ; chaque clé appartient au premier nœud rencontré dans le sens horaire. Ajout d'un nœud ⇒ seules les clés situées entre son prédécesseur et lui migrent. L'astuce : les nœuds virtuels — chaque nœud physique est posé 100 à 200 fois sur l'anneau pour équilibrer la charge. C'est la technique motrice des clusters Memcached, de Cassandra, DynamoDB, Riak et du CDN d'Akamai. Concurrents : le rendezvous hashing, Jump consistent hash (plus rapide, mais il faut connaître N) et Maglev (Google).