Hachage cohérent : un placement de clés stable quand les nœuds vont et viennent

Ce que c'est

La documentation de Cassandra (citée) oppose le hachage naïf, un hash de clé modulo le nombre de compartiments (buckets), au hachage cohérent : chaque nœud possède un ou plusieurs jetons sur un anneau de hachage continu, une clé est hachée sur cet anneau, et la propriété revient au nœud suivant en parcourant l'anneau dans un sens. Lorsque le nombre de nœuds change, seule une petite fraction des clés se déplace. Avec un seul jeton par nœud et peu de nœuds, il n'existe aucune position de jeton pour un nouveau nœud qui laisse l'anneau équilibré, et des plages inégales signifient une charge inégale ; Cassandra suit donc l'article Dynamo et attribue plusieurs jetons par nœud physique, les nœuds virtuels, de sorte que même un seul nœud ajouté prélève de nombreux petits morceaux chez de nombreux voisins.

Le module upstream de nginx (cité) offre le même choix : un simple hash $key peut redistribuer la plupart des clés lorsqu'un serveur est retiré, tandis que hash $key consistent utilise la méthode ketama, de sorte que seules quelques clés se déplacent. Envoy (cité) propose un équilibreur à hachage en anneau ainsi que Maglev, une variante fondée sur une table offrant des recherches plus rapides ; sa documentation note que Maglev déplace davantage de clés que l'anneau lorsque des hôtes sont retirés.

Pourquoi c'est important

Les caches perdent leur taux de succès à chaque changement de composition si les clés se dispersent ; les entrepôts partitionnés devraient déplacer la majeure partie des données ; les services à affinité de session perdraient cette affinité à chaque déploiement. Le hachage cohérent borne la perturbation à ce qui a réellement changé.

Comment l'appliquer

• Choisir une clé de hachage à cardinalité suffisante (identifiant utilisateur, identifiant de tenant, clé de cache), pas quelque chose comme une IP client derrière un NAT.
• Utiliser une bibliothèque ou une implémentation de proxy ; configurer les nœuds virtuels ou la taille de table de façon à égaliser la charge par nœud, et surveiller la part par hôte (Envoy expose des jauges pour le nombre minimum et maximum d'entrées par hôte).
• Pour la réplication, prendre les k prochains nœuds physiques distincts sur l'anneau, en sautant les nœuds virtuels de la même machine et, si possible, du même rack ou de la même zone.
• Prévoir la façon dont les données se déplacent lorsqu'un nœud rejoint l'anneau : le nouveau propriétaire doit recevoir sa plage avant de servir, ou faire servir les échecs par l'ancien propriétaire pendant une transition.
• Fixer la fonction de hachage pour toute la durée de vie du déploiement ; en changer redistribue tout.

Pièges

Le hachage cohérent ne corrige pas les clés chaudes : une clé populaire atterrit toujours sur un seul nœud. Les nœuds pondérés ont besoin de davantage de nœuds virtuels, proportionnellement. Le hachage cohérent n'a rien à voir avec la cohérence des données ; il ne fait que décider du placement.