Sélecteur de nœud par hachage de rendezvous

Le hachage de rendezvous, aussi appelé highest random weight hashing, assigne chaque clé à exactement un nœud de l’ensemble actif sans anneau de nœuds virtuels. Pour chaque nœud candidat, l’algorithme combine la clé avec l’identifiant du nœud, classe les scores et retient le gagnant. Lorsqu’un nœud rejoint ou quitte l’ensemble, seules se déplacent les clés qui préféraient le nœud parti ou qui préfèrent désormais le nouvel arrivant ; le reste reste en place, de sorte que le taux de succès du cache et la propriété des shards restent stables face aux changements d’appartenance. Ce sélecteur accepte une clé de routage, une liste d’identifiants de nœuds, une graine de cluster optionnelle et des poids positifs optionnels, puis renvoie le nœud choisi et le tableau complet des scores pour que vous puissiez auditer ou tester le placement.

Comment le hachage de rendezvous choisit un nœud pour une clé

Le consistent hashing a popularisé l’idée de placer les clés sur un anneau afin qu’ajouter ou retirer un nœud ne remappe qu’une petite fraction des clés. Le hachage de rendezvous résout le même problème d’équilibrage de charge avec un contrat plus simple : pour chaque nœud de l’ensemble d’appartenance courant, calculez un score qui ne dépend que de la clé et de l’identité de ce nœud, puis sélectionnez le score le plus élevé.

Le nom classique « highest random weight » reflète que le hachage se comporte comme un poids pseudo-aléatoire par paire. Comme le score du nœud A ne dépend jamais de la présence de B, retirer B n’affecte que les clés pour lesquelles B était le gagnant ; toutes les autres préfèrent encore le même survivant. Ajouter un nœud C ne vole que les clés qui obtiennent un score plus élevé avec C qu’avec leur propriétaire précédent.

Cette disruption minimale explique pourquoi les caches, les POP de bordure et les bases de données fragmentées utilisent le rendezvous lorsqu’ils veulent une propriété équilibrée sans maintenir un grand anneau de nœuds virtuels. Ce point d’accès implémente le HRW non pondéré avec un mélange FNV-1a 32 bits de graine optionnelle, de clé et de chaque id de nœud : le hachage non signé est le score, pour des comparaisons entières stables.

Lorsque vous fournissez des poids positifs parallèles à la liste de nœuds, l’algorithme passe au HRW pondéré : le hachage est projeté sur un intervalle unitaire u dans (0,1] et le score devient u élevé à un sur le poids, de sorte que les nœuds plus lourds gagnent plus souvent tout en restant pleinement déterministes. Les égalités — rares avec 32 bits mais possibles — se départagent en choisissant l’id de nœud lexicographiquement plus petit afin que deux clients ne divergent jamais.

Où un sélecteur de nœud rendezvous apporte de la valeur

Les développeurs d’applications utilisent un sélecteur de nœud par hachage de rendezvous pour épingler des sessions utilisateur, des shards d’objets ou des compteurs de limitation de débit à un backend stable sans dresser d’anneaux ZooKeeper ni de grandes bibliothèques de consistent hashing. Les équipes CDN et de bordure multi-région mappent les clés de contenu vers des POP pour que l’affinité de cache survive à la montée en charge.

Les flottes de jeux et d’IoT routent les ids d’appareils vers des workers de simulation et ne remaillent que la fraction qui préférait un nœud parti. Les pipelines de données qui partitionnent des clés style Kafka entre consommateurs peuvent simuler hors ligne des changements d’appartenance en alimentant des listes candidates dans la même fonction pure que les workers appelleront.