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 tel type de système, caches distribués qui alimentent de nombreux sites Web dynamiques et applications Web à fort trafic, consistent généralement en un cas particulier de hachage distribué. Celles-ci tirent parti d'un algorithme appelé hachage cohérent .
Qu'est-ce que le hachage cohérent? Quelle est la motivation derrière cela et pourquoi devriez-vous vous en soucier?
Dans cet article, je vais d'abord passer en revue le concept général du hachage et son objectif, suivi d'une description du hachage distribué et des problèmes qu'il entraîne. En retour, cela nous mènera à notre sujet titre.
Qu'est-ce que le hachage?
Qu'est-ce que le «hachage»? Merriam Webster définit le nom hacher comme «viande hachée mélangée avec des pommes de terre et dorée» et le verbe comme «hacher (comme de la viande et des pommes de terre) en petits morceaux». Donc, mis à part les détails culinaires, hash signifie en gros «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 mappe un élément de données - décrivant généralement un type d'objet, souvent de taille arbitraire - à un autre élément de données, généralement un entier, appelé code de hachage , ou simplement hacher .
Par exemple, une fonction de hachage conçue pour hacher des chaînes, avec une plage de sortie de 0 .. 100, peut mapper la chaîne Hello à, disons, le nombre 57, Hasta la vista, baby au nombre 33, et toute autre chaîne possible à un certain nombre dans cette plage. Puisqu'il y a beaucoup plus d'entrées possibles que de sorties, tout nombre donné aura de nombreuses chaînes différentes mappées dessus, 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, des propriétés différentes peuvent être souhaitées. Il existe un type de fonction de hachage appelé 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 par mot de passe, la vérification de l'intégrité et la prise d'empreintes digitales 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 tables de hachage , qui est celle qui nous concerne et que nous allons explorer plus en détail.
Présentation des tables de hachage (cartes de hachage)
Imaginez que nous devions garder une liste de tous les membres d'un club tout en étant capable de rechercher un membre spécifique. Nous pourrions le gérer en conservant 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 souhaité (nous pourrions rechercher 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 pas du tout présent), soit 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 proportionnellement au 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 étaient acceptables, nous pourrions placer tous les membres dans un tableau, avec leurs index correspondant à leurs ID s (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 faible possible, O(1), également appelée temps constant .
Mais, certes, notre membre du club ID scénario est quelque peu artificiel. Et si ID s était de grands nombres non séquentiels ou aléatoires? Ou, si vous recherchez par ID n'étaient pas acceptables, et nous devions effectuer une recherche par nom (ou dans un autre champ) à la place? Il serait certainement utile de conserver notre accès direct rapide (ou quelque chose de proche) tout en étant capable de gérer des ensembles de données arbitraires et des critères de recherche moins restrictifs.
Voici où les fonctions de hachage viennent à la rescousse. Une fonction de hachage appropriée peut être utilisée pour mapper une donnée arbitraire à un entier, qui jouera un rôle similaire à celui du membre de notre club ID, mais avec quelques différences importantes.
Premièrement, une bonne fonction de hachage a généralement une large plage de sortie (généralement, toute la plage d'un entier de 32 ou 64 bits), donc la création d'un tableau pour tous les indices possibles serait soit peu pratique, soit carrément 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 nous attendons à stocker) et effectuer un module opération sur le hachage pour obtenir l'index du tableau. Ainsi, l'index 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 un fonction de hachage parfaite , mais nous n'en discuterons pas ici). Il y aura collisions (encore augmenté par l'opération modulo), et donc un simple accès direct à l'index ne fonctionnera pas. Il existe plusieurs façons de gérer cela, mais une méthode typique consiste à joindre une liste, communément appelée seau , à chaque index de tableau pour contenir tous les objets partageant un index donné.
Donc, nous avons un tableau de taille N, avec chaque entrée pointant vers un compartiment d'objets. Pour ajouter un nouvel objet, nous devons calculer son hash modulo N et vérifier le compartiment à l'index résultant, en ajoutant l'objet s'il n'y est pas déjà. Pour rechercher un objet, nous faisons de même, il suffit de regarder dans le seau pour vérifier si l'objet est là. Une telle structure s'appelle un table de hachage , et bien que les recherches dans les buckets soient linéaires, une table de hachage correctement dimensionnée doit avoir un nombre raisonnablement petit d'objets par bucket, ce qui entraîne presque accès à temps constant (une complexité moyenne de O(N/k), où k est le nombre de buckets).
Avec les objets complexes, la fonction de hachage n'est généralement pas appliquée à l'objet entier, mais à un clé au lieu. Dans notre exemple de membre du club, chaque objet peut contenir plusieurs champs (comme le nom, l'âge, l'adresse, l'adresse e-mail, le téléphone), mais nous pourrions choisir, par exemple, l'e-mail pour agir comme clé afin que la fonction de hachage soit appliquée à l'e-mail seulement. En fait, la clé n'a pas besoin de 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 une donnée arbitraire. Dans de tels cas, la table de hachage ou la carte de hachage est utilisée comme dictionnaire , et c’est ainsi que certains langages de haut niveau implémentent des objets ou des tableaux associatifs.
quel est l'un des moyens les plus courants pour une entreprise de réduire le pouvoir de ses fournisseurs ?
Mise à l'échelle: hachage distribué
Maintenant que nous avons discuté du hachage, nous sommes prêts à examiner 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, permettant la construction de tables de hachage arbitrairement grandes (avec suffisamment de serveurs).
Dans un tel scénario, les objets (et leurs clés) sont distribué parmi plusieurs serveurs, d'où le nom.
Un cas d'utilisation typique pour cela est l'implémentation 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 extraire d’abord les données des serveurs de cache, et uniquement si elles n’y sont pas présentes - une situation appelée cache manque : Effectuer un tri dans la base de données, exécuter la requête appropriée et mettre en cache les résultats avec une clé appropriée, afin qu’elle puisse être trouvée la prochaine fois qu’elle en aura besoin.
Maintenant, comment se déroule la distribution? Quels critères sont utilisés pour déterminer quelles clés héberger sur quels serveurs?
Le moyen le plus simple est de prendre le hachage module du nombre de serveurs. Autrement dit, server = hash(key) mod N, où N est la taille de la piscine. Pour stocker ou récupérer une clé, le client calcule d'abord le hachage, applique un modulo N et utilise l'index résultant pour contacter le serveur approprié (probablement en utilisant une table de recherche d'adresses IP). Notez que la fonction de hachage utilisée pour la distribution des clés doit être la même sur tous les clients, mais il n'est pas nécessaire qu'elle 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 des clés de chaîne avec leurs hachages:
| CLÉ | HACHER | HASH mod 3 |
|---|---|---|
| 'John' | 1633428562 | 2 |
| 'facture' | 7594634739 | 0 |
| 'Jeanne' | 5000799124 | un |
| «Steve» | 9787173343 | 0 |
| «Kate» | 3421657995 | 2 |
Un client souhaite 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. La piscine ressemble à ceci:
| À | B | C |
|---|---|---|
| 'John' |
Ensuite, 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 de la source et les ajoute. La piscine ressemble à ceci maintenant:
| À | B | C |
|---|---|---|
| 'facture' | 'John' |
Une fois les clés restantes ajoutées, le pool ressemble à ceci:
| À | B | C |
|---|---|---|
| 'facture' | 'Jeanne' | 'John' |
| «Steve» | «Kate» |
Le problème du ressassement
Ce schéma de distribution est simple, intuitif et fonctionne correctement. Autrement dit, jusqu'à ce que le nombre de serveurs change. Que se passe-t-il si l'un des serveurs tombe en panne 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. Cela 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 hashes modulo N va changer, donc la plupart des clés devront être déplacées vers un autre serveur. Ainsi, même si un seul serveur est supprimé ou ajouté, toutes les clés devront probablement être remises en place sur un serveur différent.
De notre exemple précédent, si nous supprimions le serveur C, nous devrons modifier toutes les clés en utilisant hash modulo 2 au lieu de hash modulo 3, et les nouveaux emplacements des clés deviendraient:
| CLÉ | HACHER | HASH mod 2 |
|---|---|---|
| 'John' | 1633428562 | 0 |
| 'facture' | 7594634739 | un |
| 'Jeanne' | 5000799124 | 0 |
| «Steve» | 9787173343 | un |
| «Kate» | 3421657995 | un |
| À | B |
|---|---|
| 'John' | 'facture' |
| 'Jeanne' | «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 à coup, les clés ne seront pas trouvées car elles ne seront pas encore présentes à leur nouvel emplacement.
Ainsi, la plupart des requêtes entraîneront des erreurs, et les données d'origine devront probablement être extraites à nouveau de la source pour être remaniées, plaçant ainsi une lourde charge sur le (s) serveur (s) d'origine (généralement une base de données). Cela peut très bien dégrader les performances et éventuellement planter les serveurs d'origine.
La solution: un hachage cohérent
Alors, comment résoudre ce problème? Nous avons besoin d'un système de distribution qui ne pas dépendent directement du nombre de serveurs, de sorte que, lors de l'ajout ou de la suppression de serveurs, le nombre de clés à déplacer est minimisé. Un de ces schémas - intelligent, mais étonnamment simple - est appelé hachage cohérent , et a été décrit pour la première fois par Karger et coll. 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 un table de hachage en leur attribuant 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.
Imaginons que nous mappions la plage de sortie de 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 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 savoir où elle se trouve sur le bord du cercle. En supposant un INT_MAX sur 10dix(par exemple), les clés de notre exemple précédent ressembleraient à ceci:
comment utiliser bootstrap en html
| CLÉ | HACHER | ANGLE (DEG) |
|---|---|---|
| 'John' | 1633428562 | 58,8 |
| 'facture' | 7594634739 | 273,4 |
| 'Jeanne' | 5000799124 | 180 |
| «Steve» | 9787173343 | 352,3 |
| «Kate» | 3421657995 | 123,2 |
Imaginez maintenant que nous ayons également placé les serveurs sur le bord du cercle, en leur attribuant également des angles pseudo-aléatoirement. Cela doit être fait de manière répétable (ou du moins de manière à ce que tous les clients s’accordent sur les angles des serveurs). Un moyen pratique de procéder consiste à hacher le nom du serveur (ou l’adresse IP, ou un identifiant) - comme nous le ferions avec toute autre clé - pour trouver son angle.
Dans notre exemple, les choses pourraient ressembler à ceci:
| CLÉ | HACHER | ANGLE (DEG) |
|---|---|---|
| 'John' | 1633428562 | 58,8 |
| 'facture' | 7594634739 | 273,4 |
| 'Jeanne' | 5000799124 | 180 |
| «Steve» | 9787173343 | 352,3 |
| «Kate» | 3421657995 | 123,2 |
| 'À' | 5572014558 | 200,6 |
| «B» | 8077113362 | 290,8 |
| «C» | 2269549488 | 81,7 |
Puisque nous avons les clés à la fois 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 antihoraire (ou sens horaire, selon les conventions utilisées). En d'autres termes, pour savoir quel serveur demander une clé donnée, nous devons localiser la clé sur le cercle et se déplacer dans le sens de l'angle ascendant jusqu'à ce que nous trouvions un serveur.
Dans notre exemple:
| CLÉ | HACHER | ANGLE (DEG) |
|---|---|---|
| 'John' | 1633428562 | 58,7 |
| «C» | 2269549488 | 81,7 |
| «Kate» | 3421657995 | 123,1 |
| 'Jeanne' | 5000799124 | 180 |
| 'À' | 5572014557 | 200,5 |
| 'facture' | 7594634739 | 273,4 |
| «B» | 8077113361 | 290,7 |
| «Steve» | 787173343 | 352,3 |
| CLÉ | HACHER | ANGLE (DEG) | ÉTIQUETTE | SERVEUR |
|---|---|---|---|---|
| 'John' | 1632929716 | 58,7 | «C» | C |
| «Kate» | 3421831276 | 123,1 | 'À' | À |
| 'Jeanne' | 5000648311 | 180 | 'À' | À |
| 'facture' | 7594873884 | 273,4 | «B» | B |
| «Steve» | 9786437450 | 352,3 | «C» | C |
Du point de vue de la programmation, ce que nous ferions serait de conserver une liste triée de valeurs de serveur (qui pourraient être des angles ou des nombres dans n'importe quel intervalle réel), et parcourir cette liste (ou utiliser une recherche binaire) pour trouver le premier serveur avec une valeur supérieure supérieure ou égale à celle de la clé souhaitée. Si aucune valeur de ce type n'est trouvée, nous devons terminer en prenant la première de la liste.
Pour nous assurer que les clés d'objet sont uniformément réparties entre les serveurs, nous devons appliquer une astuce simple: attribuer non pas une, mais plusieurs étiquettes (angles) à chaque serveur. Donc au lieu d'avoir des étiquettes A, B et C, on pourrait avoir, disons, A0 .. A9, B0 .. B9 et C0 .. C9, tous intercalés le long du cercle. Le facteur d'augmentation du 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 des clés se retrouvent sur chacun. Par exemple, si serveur B étaient deux fois plus puissants que les autres, il pouvait être attribué 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 compris entre 100 et 500 fonctionnerait mieux, et des pools plus importants peuvent nécessiter des poids encore plus élevés. ):
| CLÉ | HACHER | 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 |
| 'Jeanne' | 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 |
| 'facture' | 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 |
| CLÉ | HACHER | ANGLE (DEG) | ÉTIQUETTE | SERVEUR |
|---|---|---|---|---|
| 'John' | 1632929716 | 58,7 | «B2» | B |
| «Kate» | 3421831276 | 123,1 | «A5» | À |
| 'Jeanne' | 5000648311 | 180 | «C7» | C |
| 'facture' | 7594873884 | 273,4 | «A4» | À |
| «Steve» | 9786437450 | 352,3 | «C6» | C |
Alors, quel est l'avantage de toute cette approche circulaire? Imaginez le serveur C est retiré. Pour en tenir compte, nous devons supprimer les étiquettes C0 .. C9 du cercle. Il en résulte que les clés d'objet auparavant adjacentes aux étiquettes supprimées sont désormais étiquetées au hasard Ax et Bx, en les réaffectant 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 ça la beauté: l’absence de Cx labels n'affecte en aucun cas 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 touches intactes :
| CLÉ | HACHER | 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 |
| 'Jeanne' | 5000799124 | 180 |
| «B1» | 5444659173 | 196 |
| «A6» | 6210502707 | 223,5 |
| «A0» | 6511384141 | 234,4 |
| «B9» | 7292819872 | 262,5 |
| 'facture' | 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 |
| CLÉ | HACHER | ANGLE (DEG) | ÉTIQUETTE | SERVEUR |
|---|---|---|---|---|
| 'John' | 1632929716 | 58,7 | «B2» | B |
| «Kate» | 3421831276 | 123,1 | «A5» | À |
| 'Jeanne' | 5000648311 | 180 | «B1» | B |
| 'facture' | 7594873884 | 273,4 | «A4» | À |
| «Steve» | 9786437450 | 352,3 | «A1» | À |
Quelque chose de similaire se produit si, au lieu de supprimer un serveur, nous en ajoutons un. Si nous voulions ajouter un serveur D à notre exemple (disons, en remplacement de C), nous aurions besoin d'ajouter des étiquettes D0 .. D9. Le résultat serait 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:
| CLÉ | HACHER | 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 |
| 'Jeanne' | 5000799124 | 180 |
| «B1» | 5444659173 | 196 |
| «D6» | 5703092354 | 205,3 |
| «A6» | 6210502707 | 223,5 |
| «A0» | 6511384141 | 234,4 |
| «B9» | 7292819872 | 262,5 |
| 'facture' | 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 |
| CLÉ | HACHER | ANGLE (DEG) | ÉTIQUETTE | SERVEUR |
|---|---|---|---|---|
| 'John' | 1632929716 | 58,7 | «B2» | B |
| «Kate» | 3421831276 | 123,1 | «A5» | À |
| 'Jeanne' | 5000648311 | 180 | «B1» | B |
| 'facture' | 7594873884 | 273,4 | «A4» | À |
| «Steve» | 9786437450 | 352,3 | «D2» | ré |
C'est ainsi que le hachage cohérent résout le problème du ressassement.
En général, seulement k/N les clés doivent être remappées lorsque k est le nombre de touches et N est le nombre de serveurs (plus précisément, le maximum du nombre initial et final de serveurs).
Et ensuite?
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 produisait, le nombre de clés remaniées - et par conséquent, l'impact sur les serveurs d'origine - sera minimisé, évitant ainsi les temps d'arrêt potentiels ou les problèmes de performances.
Il existe des clients pour plusieurs systèmes, tels que Memcached et Redis, qui prennent en charge le hachage cohérent prêt à l'emploi.
Alternativement, vous pouvez implémenter l'algorithme vous-même, dans la langue 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, ApeeScape a certains des meilleurs articles sur le sujet à la Blog
