Ces dernières années, avec l’avènement de concepts tels que le cloud computing et le big data, les systèmes distribués ont gagné en popularité et en pertinence.
Un de ces types de systèmes, les caches distribués qui alimentent de nombreux sites web dynamiques à fort trafic et des applications web, consistent généralement en un cas particulier de hachage distribué. Ceux-ci tirent parti d’un algorithme connu sous le nom de hachage cohérent.
Qu’est-ce que le hachage cohérent ? Quelle est la motivation derrière elle, et pourquoi devriez-vous vous en soucier?
Dans cet article, je vais d’abord passer en revue le concept général de hachage et son but, suivi d’une description du hachage distribué et des problèmes qu’il implique. À son tour, cela nous mènera à notre sujet titre.
Qu’est-ce que le hachage?
Qu’est-ce que le « hachage » ? Merriam-Webster définit le substantif hash comme « viande hachée mélangée à des pommes de terre et dorée », et le verbe comme « couper (comme la viande et les pommes de terre) en petits morceaux. » Donc, détails culinaires mis à part, hacher signifie grossièrement « hacher et mélanger » – et c’est précisément de là que vient le terme technique.
Une fonction de hachage est une fonction qui fait correspondre une donnée – décrivant typiquement un type d’objet, souvent de taille arbitraire – à une autre donnée, typiquement un entier, connue sous le nom de code de hachage, ou simplement de hachage.
Par exemple, une certaine fonction de hachage conçue pour hacher des chaînes de caractères, avec une plage de sortie de 0 .. 100, peut mettre en correspondance la chaîne Hello avec, disons, le nombre 57, Hasta la vista, baby avec le nombre 33, et toute autre chaîne possible avec un certain nombre dans cette plage. Puisqu’il y a beaucoup plus d’entrées que de sorties possibles, un nombre donné aura beaucoup de chaînes différentes mappées sur lui, un phénomène connu sous le nom de collision. Les bonnes fonctions de hachage devraient en quelque sorte « hacher et mélanger » (d’où le terme) les données d’entrée de telle sorte que les sorties pour différentes valeurs d’entrée soient réparties aussi uniformément que possible sur la plage de sortie.
Les fonctions de hachage ont de nombreuses utilisations et pour chacune d’elles, différentes propriétés peuvent être souhaitées. Il existe un type de fonction de hachage connu sous le nom de fonctions de hachage cryptographiques, qui doivent répondre à un ensemble restrictif de propriétés et sont utilisées à des fins de sécurité – y compris des applications telles que la protection des mots de passe, la vérification de l’intégrité et l’empreinte digitale des messages, et la détection de la corruption des données, entre autres, mais celles-ci sortent du cadre de cet article.
Les fonctions de hachage non cryptographiques ont également plusieurs utilisations, la plus courante étant leur utilisation dans les tables de hachage, qui est celle qui nous concerne et que nous allons explorer plus en détail.
Introducing Hash Tables (Hash Maps)
Imaginez que nous devions conserver une liste de tous les membres d’un certain club tout en étant capable de rechercher un membre spécifique. Nous pourrions le gérer en gardant la liste dans un tableau (ou une liste chaînée) et, pour effectuer une recherche, itérer les éléments jusqu’à ce que nous trouvions celui désiré (nous pourrions chercher en fonction de leur nom, par exemple). Dans le pire des cas, cela signifierait vérifier tous les membres (si celui que nous recherchons est le dernier, ou n’est pas présent du tout), ou la moitié d’entre eux en moyenne. En termes de théorie de la complexité, la recherche aurait alors une complexité O(n), et elle serait raisonnablement rapide pour une petite liste, mais elle deviendrait de plus en plus lente en proportion directe du nombre de membres.
Comment cela pourrait-il être amélioré ? Supposons que tous ces membres du club aient un membre ID, qui se trouve être un numéro séquentiel reflétant l’ordre dans lequel ils ont rejoint le club.
En supposant que la recherche par ID soit acceptable, nous pourrions placer tous les membres dans un tableau, avec leurs index correspondant à leurs ID (par exemple, un membre avec ID=10 serait à l’index 10 dans le tableau). Cela nous permettrait d’accéder directement à chaque membre, sans aucune recherche. Ce serait très efficace, en fait, aussi efficace que possible, correspondant à la complexité la plus basse possible, O(1), également connue sous le nom de temps constant.
Mais, il faut l’admettre, notre scénario de membre de club ID est quelque peu artificiel. Et si les ID étaient de grands nombres non séquentiels ou aléatoires ? Ou, si la recherche par ID n’était pas acceptable, et que nous devions rechercher par nom (ou un autre champ) à la place ? Il serait certainement utile de conserver notre accès direct rapide (ou quelque chose d’approchant) tout en étant capable de gérer des ensembles de données arbitraires et des critères de recherche moins restrictifs.
C’est là que les fonctions de hachage viennent à la rescousse. Une fonction de hachage appropriée peut être utilisée pour mapper un morceau arbitraire de données à un entier, qui jouera un rôle similaire à celui de notre membre du club ID, bien qu’avec quelques différences importantes.
Premièrement, une bonne fonction de hachage a généralement une large gamme de sortie (typiquement, toute la gamme d’un entier de 32 ou 64 bits), donc construire un tableau pour tous les indices possibles serait soit peu pratique ou tout simplement impossible, et un gaspillage colossal de mémoire. Pour surmonter cela, nous pouvons avoir un tableau de taille raisonnable (disons, juste deux fois le nombre d’éléments que nous prévoyons de stocker) et effectuer une opération modulo sur le hachage pour obtenir l’indice du tableau. Ainsi, l’indice serait index = hash(object) mod N, où N est la taille du tableau.
Deuxièmement, les hachages d’objets ne seront pas uniques (sauf si nous travaillons avec un ensemble de données fixe et une fonction de hachage parfaite personnalisée, mais nous n’en parlerons pas ici). Il y aura des collisions (encore accrues par l’opération modulo), et donc un simple accès direct à l’index ne fonctionnera pas. Il y a plusieurs façons de gérer cela, mais une typique est d’attacher une liste, communément appelée un seau, à chaque indice de tableau pour contenir tous les objets partageant un indice donné.
Donc, nous avons un tableau de taille N, avec chaque entrée pointant vers un seau d’objets. Pour ajouter un nouvel objet, nous devons calculer son hash modulo N, et vérifier le seau à l’indice résultant, en ajoutant l’objet s’il n’est pas déjà là. Pour rechercher un objet, nous faisons la même chose, en regardant dans le seau pour vérifier si l’objet s’y trouve. Une telle structure est appelée table de hachage, et bien que les recherches dans les seaux soient linéaires, une table de hachage correctement dimensionnée devrait avoir un nombre raisonnablement faible d’objets par seau, ce qui entraîne un accès en temps presque constant (une complexité moyenne de O(N/k), où k est le nombre de seaux).
Avec des objets complexes, la fonction de hachage n’est généralement pas appliquée à l’objet entier, mais à une clé à la place. Dans notre exemple de membre de club, chaque objet pourrait contenir plusieurs champs (comme le nom, l’âge, l’adresse, l’email, le téléphone), mais nous pourrions choisir, disons, l’email pour agir comme la clé afin que la fonction de hachage soit appliquée à l’email seulement. En fait, la clé ne doit pas nécessairement faire partie de l’objet ; il est courant de stocker des paires clé/valeur, où la clé est généralement une chaîne relativement courte, et la valeur peut être un élément de données arbitraire. Dans de tels cas, la table de hachage ou la carte de hachage est utilisée comme un dictionnaire, et c’est la façon dont certains langages de haut niveau mettent en œuvre des objets ou des tableaux associatifs.
Scaling Out : Hachage distribué
Maintenant que nous avons discuté du hachage, nous sommes prêts à examiner le hachage distribué.
Dans certaines situations, il peut être nécessaire ou souhaitable de diviser une table de hachage en plusieurs parties, hébergées par différents serveurs. L’une des principales motivations pour cela est de contourner les limitations de mémoire liées à l’utilisation d’un seul ordinateur, ce qui permet la construction de tables de hachage arbitrairement grandes (étant donné un nombre suffisant de serveurs).
Dans un tel scénario, les objets (et leurs clés) sont répartis entre plusieurs serveurs, d’où le nom.
Un cas d’utilisation typique pour cela est la mise en œuvre de caches en mémoire, tels que Memcached.
Ces configurations consistent en un pool de serveurs de mise en cache qui hébergent de nombreuses paires clé/valeur et sont utilisées pour fournir un accès rapide aux données initialement stockées (ou calculées) ailleurs. Par exemple, pour réduire la charge sur un serveur de base de données et en même temps améliorer les performances, une application peut être conçue pour d’abord récupérer les données à partir des serveurs de cache, et seulement si elles n’y sont pas présentes – une situation connue sous le nom de cache miss – recourir à la base de données, en exécutant la requête pertinente et en mettant en cache les résultats avec une clé appropriée, de sorte qu’elle puisse être trouvée la prochaine fois qu’elle est nécessaire.
Maintenant, comment la distribution a lieu ? Quels critères sont utilisés pour déterminer quelles clés héberger dans quels serveurs ?
La façon la plus simple est de prendre le hachage modulo du nombre de serveurs. C’est-à-dire server = hash(key) mod N, où N est la taille du pool. Pour stocker ou récupérer une clé, le client calcule d’abord le hachage, applique une opération modulo N, et utilise l’index résultant pour contacter le serveur approprié (probablement en utilisant une table de consultation d’adresses IP). Notez que la fonction de hachage utilisée pour la distribution des clés doit être la même pour tous les clients, mais il n’est pas nécessaire que ce soit la même que celle utilisée en interne par les serveurs de mise en cache.
Voyons un exemple. Disons que nous avons trois serveurs, A, B et C, et nous avons quelques clés de chaîne avec leurs hachages :
| KEY | HASH | HASH mod 3 |
|---|---|---|
| « john » | 1633428562 | 2 |
| « bill » | 7594634739 | 0 |
| « jane » | 5000799124 | 1 |
| « steve » | 9787173343 | 0 |
| « kate » | 3421657995 | 2 |
Un client veut récupérer la valeur de la clé john. Son hash modulo 3 est 2, il doit donc contacter le serveur C. La clé n’y est pas trouvée, donc le client récupère les données de la source et les ajoute. Le pool ressemble à ceci:
| A | B | C |
|---|---|---|
| « john » |
Suivant, un autre client (ou le même) veut récupérer la valeur de la clé bill. Son hash modulo 3 est 0, il doit donc contacter le serveur A. La clé n’y est pas trouvée, donc le client récupère les données depuis la source et les ajoute. Le pool ressemble maintenant à ceci:
| A | B | C |
|---|---|---|
| « bill » | « john » |
Après l’ajout des clés restantes, le pool ressemble à ceci :
| A | B | C |
|---|---|---|
| « bill » | « jane » | « john » |
| « steve » | « kate » |
Le problème du rabâchage
Ce schéma de distribution est simple, intuitif, et fonctionne bien. C’est-à-dire, jusqu’à ce que le nombre de serveurs change. Que se passe-t-il si l’un des serveurs se plante ou devient indisponible ? Les clés doivent être redistribuées pour tenir compte du serveur manquant, bien sûr. Il en va de même si un ou plusieurs nouveaux serveurs sont ajoutés au pool ; les clés doivent être redistribuées pour inclure les nouveaux serveurs. Ceci est vrai pour n’importe quel schéma de distribution, mais le problème avec notre distribution modulo simple est que lorsque le nombre de serveurs change, la plupart des hashes modulo N changeront, donc la plupart des clés devront être déplacées vers un serveur différent. Ainsi, même si un seul serveur est supprimé ou ajouté, toutes les clés devront probablement être remises dans un serveur différent.
D’après notre exemple précédent, si nous supprimions le serveur C, nous devrions remanier toutes les clés en utilisant hash modulo 2 au lieu de hash modulo 3, et les nouveaux emplacements des clés deviendraient :
| KEY | HASH | HASH mod 2 |
|---|---|---|
| « john » | 1633428562 | 0 |
| « bill » | 7594634739 | 1 |
| « jane » | 5000799124 | 0 |
| « steve » | 9787173343 | 1 |
| « kate » | 3421657995 | 1 |
| A | B |
|---|---|
| « john » | « bill » |
| « jane » | « steve » |
| « kate » |
Notez que tous les emplacements clés ont changé, pas seulement ceux du serveur C.
Dans le cas d’utilisation typique que nous avons mentionné précédemment (mise en cache), cela signifierait que, tout d’un coup, les clés ne seront pas trouvées parce qu’elles ne seront pas encore présentes à leur nouvel emplacement.
Donc, la plupart des requêtes aboutiront à des ratés, et les données d’origine devront probablement être récupérées à nouveau depuis la source pour être remises en mémoire, plaçant ainsi une lourde charge sur le ou les serveurs d’origine (typiquement une base de données). Cela peut très bien dégrader gravement les performances et éventuellement faire planter les serveurs d’origine.
La solution : Hachage cohérent
Alors, comment résoudre ce problème ? Nous avons besoin d’un schéma de distribution qui ne dépend pas directement du nombre de serveurs, de sorte que, lors de l’ajout ou de la suppression de serveurs, le nombre de clés qui doivent être relocalisées est minimisé. Un tel schéma – astucieux, mais étonnamment simple – est appelé hachage cohérent, et a été décrit pour la première fois par Karger et al. au MIT dans un article académique de 1997 (selon Wikipedia).
Le hachage cohérent est un schéma de hachage distribué qui fonctionne indépendamment du nombre de serveurs ou d’objets dans une table de hachage distribuée en leur assignant une position sur un cercle abstrait, ou anneau de hachage. Cela permet aux serveurs et aux objets d’évoluer sans affecter le système global.
Imaginez que nous ayons mappé la plage de sortie du hachage sur le bord d’un cercle. Cela signifie que la valeur de hachage minimale possible, zéro, correspondrait à un angle de zéro, la valeur maximale possible (un grand nombre entier que nous appellerons INT_MAX) correspondrait à un angle de 2𝝅 radians (ou 360 degrés), et toutes les autres valeurs de hachage s’inscriraient linéairement quelque part entre les deux. Ainsi, nous pourrions prendre une clé, calculer son hachage, et trouver où elle se trouve sur le bord du cercle. En supposant un INT_MAX de 1010 (pour l’exemple), les clés de notre exemple précédent ressembleraient à ceci :
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| « john » | 1633428562 | 58.8 |
| « bill » | 7594634739 | 273.4 |
| « jane » | 5000799124 | 180 |
| « steve » | 9787173343 | 352.3 |
| « kate » | 3421657995 | 123.2 |
Maintenant imaginez que nous avons également placé les serveurs sur le bord du cercle, en leur attribuant des angles de manière pseudo-aléatoire également. Cela doit être fait de manière répétable (ou au moins de manière à ce que tous les clients soient d’accord sur les angles des serveurs). Une façon pratique de le faire est de hacher le nom du serveur (ou l’adresse IP, ou un identifiant quelconque) – comme nous le ferions avec n’importe quelle autre clé – pour obtenir son angle.
Dans notre exemple, les choses pourraient ressembler à ceci :
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| « john » | 1633428562 | 58.8 |
| « bill » | 7594634739 | 273.4 |
| « jane » | 5000799124 | 180 |
| « steve » | 9787173343 | 352.3 |
| « kate » | 3421657995 | 123.2 |
| « A » | 5572014558 | 200.6 |
| « B » | 8077113362 | 290,8 |
| « C » | 2269549488 | 81.7 |
Puisque nous avons les clés des objets et des serveurs sur le même cercle, nous pouvons définir une règle simple pour associer les premiers aux seconds : Chaque clé d’objet appartiendra au serveur dont la clé est la plus proche, dans le sens inverse des aiguilles d’une montre (ou dans le sens des aiguilles d’une montre, selon les conventions utilisées). En d’autres termes, pour savoir quel serveur demander pour une clé donnée, nous devons localiser la clé sur le cercle et nous déplacer dans la direction de l’angle ascendant jusqu’à ce que nous trouvions un serveur.
Dans notre exemple :
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| « john » | 1633428562 | 58.7 |
| « C » | 2269549488 | 81.7 |
| « kate » | 3421657995 | 123.1 |
| « jane » | 5000799124 | 180 |
| « A » | 5572014557 | 200.5 |
| « bill » | 7594634739 | 273.4 |
| « B » | 8077113361 | 290.7 |
| « steve » | 787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| « john » | 1632929716 | 58.7 | « C » | C |
| « kate » | 3421831276 | 123.1 | « A » | A |
| « jane » | 5000648311 | 180 | « A » | A |
| « bill » | 7594873884 | 273.4 | « B » | B |
| « steve » | 9786437450 | 352.3 | « C » | C |
D’un point de vue programmation, ce que nous ferions serait de garder une liste triée des valeurs du serveur (qui pourraient être des angles ou des nombres dans n’importe quel intervalle réel), et de parcourir cette liste (ou d’utiliser une recherche binaire) pour trouver le premier serveur avec une valeur supérieure ou égale à celle de la clé désirée. Si aucune valeur de ce type n’est trouvée, nous devons faire le tour, en prenant le premier de la liste.
Pour s’assurer que les clés des objets sont distribuées de manière égale entre les serveurs, nous devons appliquer une astuce simple : attribuer non pas une, mais plusieurs étiquettes (angles) à chaque serveur. Ainsi, au lieu d’avoir les étiquettes A, B et C, nous pourrions avoir, disons, A0 .. A9, B0 .. B9 et C0 .. C9, toutes intercalées le long du cercle. Le facteur par lequel augmenter le nombre d’étiquettes (clés de serveur), appelé poids, dépend de la situation (et peut même être différent pour chaque serveur) pour ajuster la probabilité que les clés se retrouvent sur chacun. Par exemple, si le serveur B était deux fois plus puissant que les autres, on pourrait lui attribuer deux fois plus d’étiquettes et, par conséquent, il finirait par contenir deux fois plus d’objets (en moyenne).
Pour notre exemple, nous supposerons que les trois serveurs ont un poids égal de 10 (cela fonctionne bien pour trois serveurs, pour 10 à 50 serveurs, un poids dans la gamme de 100 à 500 fonctionnerait mieux, et des pools plus grands pourraient avoir besoin de poids encore plus élevés) :
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| « C6 » | 408965526 | 14.7 |
| « A1 » | 473914830 | 17 |
| « A2 » | 548798874 | 19.7 |
| « A3 » | 1466730567 | 52.8 |
| « C4 » | 1493080938 | 53.7 |
| « john » | 1633428562 | 58.7 |
| « B2 » | 1808009038 | 65 |
| « C0 » | 1982701318 | 71.3 |
| « B3 » | 2058758486 | 74.1 |
| « A7 » | 2162578920 | 77.8 |
| « B4 » | 2660265921 | 95,7 |
| « C9 » | 3359725419 | 120.9 |
| « kate » | 3421657995 | 123.1 |
| « A5 » | 3434972143 | 123.6 |
| « C1 » | 3672205973 | 132.1 |
| « C8 » | 3750588567 | 135 |
| « B0 » | 4049028775 | 145.7 |
| « B8 » | 4755525684 | 171.1 |
| « A9 » | 4769549830 | 171.7 |
| « jane » | 5000799124 | 180 |
| « C7 » | 5014097839 | 180.5 |
| « B1 » | 5444659173 | 196 |
| « A6 » | 6210502707 | 223.5 |
| « A0 » | 6511384141 | 234.4 |
| « B9 » | 7292819872 | 262.5 |
| « C3 » | 7330467663 | 263.8 |
| « C5 » | 7502566333 | 270 |
| « bill » | 7594634739 | 273.4 |
| « A4 » | 8047401090 | 289.7 |
| « C2 » | 8605012288 | 309.7 |
| « A8 » | 8997397092 | 323.9 |
| « B7 » | 9038880553 | 325.3 |
| « B5 » | 9368225254 | 337.2 |
| « B6 » | 9379713761 | 337.6 |
| « steve » | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| « john » | 1632929716 | 58.7 | « B2 » | B |
| « kate » | 3421831276 | 123.1 | « A5 » | A |
| « jane » | 5000648311 | 180 | « C7 » | C |
| « bill » | 7594873884 | 273.4 | « A4 » | A |
| « steve » | 9786437450 | 352.3 | « C6 » | C |
Alors, quel est l’avantage de toute cette approche en cercle ? Imaginons que le serveur C soit supprimé. Pour en tenir compte, nous devons retirer les étiquettes C0 .. C9 du cercle. Il en résulte que les clés d’objet autrefois adjacentes aux étiquettes supprimées sont maintenant étiquetées aléatoirement Ax et Bx, ce qui les réaffecte aux serveurs A et B.
Mais que se passe-t-il avec les autres clés d’objet, celles qui appartenaient à l’origine à A et B ? Rien ! C’est là toute la beauté de la chose : L’absence d’étiquettes Cx n’affecte en rien ces clés. Ainsi, la suppression d’un serveur entraîne la réaffectation aléatoire de ses clés d’objet au reste des serveurs, laissant toutes les autres clés intactes :
| KEY | HASH | ANGLE. (DEG) |
|---|---|---|
| « A1 » | 473914830 | 17 |
| « A2 » | 548798874 | 19.7 |
| « A3 » | 1466730567 | 52.8 |
| « john » | 1633428562 | 58.7 |
| « B2 » | 1808009038 | 65 |
| « B3 » | 2058758486 | 74.1 |
| « A7 » | 2162578920 | 77,8 |
| « B4 » | 2660265921 | 95.7 |
| « kate » | 3421657995 | 123.1 |
| « A5 » | 3434972143 | 123.6 |
| « B0 » | 4049028775 | 145.7 |
| « B8 » | 4755525684 | 171.1 |
| « A9 » | 4769549830 | 171.7 |
| « jane » | 5000799124 | 180 |
| « B1 » | 5444659173 | 196 |
| « A6 » | 6210502707 | 223.5 |
| « A0 » | 6511384141 | 234.4 |
| « B9 » | 7292819872 | 262.5 |
| « bill » | 7594634739 | 273.4 |
| « A4 » | 8047401090 | 289.7 |
| « A8 » | 8997397092 | 323.9 |
| « B7 » | 9038880553 | 325.3 |
| « B5 » | 9368225254 | 337.2 |
| « B6 » | 9379713761 | 337.6 |
| « steve » | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| « john » | 1632929716 | 58.7 | « B2 » | B |
| « kate » | 3421831276 | 123.1 | « A5 » | A |
| « jane » | 5000648311 | 180 | « B1 » | B |
| « bill » | 7594873884 | 273.4 | « A4 » | A |
| « steve » | 9786437450 | 352.3 | « A1 » | A |
Quelque chose de similaire se produit si, au lieu de supprimer un serveur, nous en ajoutons un. Si nous voulions ajouter le serveur D à notre exemple (disons, en remplacement de C), nous devrions ajouter les étiquettes D0 .. D9. Il en résulterait qu’environ un tiers des clés existantes (appartenant toutes à A ou B) seraient réaffectées à D, et, encore une fois, le reste resterait le même :
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| « D2 » | 439890723 | 15.8 |
| « A1 » | 473914830 | 17 |
| « A2 » | 548798874 | 19.7 |
| « D8 » | 796709216 | 28.6 |
| « D1 » | 1008580939 | 36.3 |
| « A3 » | 1466730567 | 52.8 |
| « D5 » | 1587548309 | 57.1 |
| « john » | 1633428562 | 58.7 |
| « B2 » | 1808009038 | 65 |
| « B3 » | 2058758486 | 74.1 |
| « A7 » | 2162578920 | 77,8 |
| « B4 » | 2660265921 | 95.7 |
| « D4 » | 2909395217 | 104.7 |
| « kate » | 3421657995 | 123.1 |
| « A5 » | 3434972143 | 123.6 |
| « D7 » | 3567129743 | 128.4 |
| « B0 » | 4049028775 | 145.7 |
| « B8 » | 4755525684 | 171.1 |
| « A9 » | 4769549830 | 171.7 |
| « jane » | 5000799124 | 180 |
| « B1 » | 5444659173 | 196 |
| « D6 » | 5703092354 | 205.3 |
| « A6 » | 6210502707 | 223.5 |
| « A0 » | 6511384141 | 234.4 |
| « B9 » | 7292819872 | 262.5 |
| « bill » | 7594634739 | 273.4 |
| « A4 » | 8047401090 | 289.7 |
| « D0 » | 8272587142 | 297,8 |
| « A8 » | 8997397092 | 323.9 |
| « B7 » | 9038880553 | 325.3 |
| « D3 » | 9048608874 | 325.7 |
| « D9 » | 9314459653 | 335.3 |
| « B5 » | 9368225254 | 337.2 |
| « B6 » | 9379713761 | 337.6 |
| « steve » | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| « john » | 1632929716 | 58.7 | « B2 » | B |
| « kate » | 3421831276 | 123.1 | « A5 » | A |
| « jane » | 5000648311 | 180 | « B1 » | B |
| « bill » | 7594873884 | 273.4 | « A4 » | A |
| « steve » | 9786437450 | 352.3 | « D2 » | D |
C’est ainsi que le hachage cohérent résout le problème du rehashing.
En général, seules k/N clés doivent être remappées lorsque k est le nombre de clés et N est le nombre de serveurs (plus précisément, le maximum du nombre initial et final de serveurs).
Nous avons observé que lors de l’utilisation de la mise en cache distribuée pour optimiser les performances, il peut arriver que le nombre de serveurs de mise en cache change (les raisons peuvent être un plantage du serveur, ou la nécessité d’ajouter ou de supprimer un serveur pour augmenter ou diminuer la capacité globale). En utilisant un hachage cohérent pour distribuer les clés entre les serveurs, nous pouvons être assurés que si cela se produit, le nombre de clés qui sont remises en forme – et donc, l’impact sur les serveurs d’origine – sera minimisé, empêchant les temps d’arrêt potentiels ou les problèmes de performance.
Il existe des clients pour plusieurs systèmes, tels que Memcached et Redis, qui incluent le support du hachage cohérent hors de la boîte.
Alternativement, vous pouvez implémenter l’algorithme vous-même, dans le langage de votre choix, et cela devrait être relativement facile une fois que le concept est compris.
Si la science des données vous intéresse, Toptal a certains des meilleurs articles sur le sujet sur le blog
.