La principale recherche de cet article est le code d'algorithme cohérenthashing.
L'algorithme de hachage cohérent a été proposé par le MIT en 1997 (voir 0). L'objectif de conception était de résoudre le problème Hotpot sur Internet, et son intention initiale était très similaire à la carpe. Le hachage cohérent corrige le problème causé par l'algorithme de hachage simple utilisé par la carpe, afin que la DHT puisse être vraiment appliquée dans les environnements P2P.
Le hachage cohérent propose quatre conditions d'adaptation que l'algorithme de hachage doit remplir dans un environnement de cache en évolution dynamique:
L'équilibre signifie que le résultat du hachage peut être distribué à tous les caches autant que possible, afin que tout l'espace de cache puisse être utilisé. De nombreux algorithmes de hachage peuvent remplir cette condition.
La monotonité fait référence à si un contenu a été envoyé au cache correspondant par le hachage, et de nouveaux caches sont ajoutés au système. Le résultat du hachage devrait garantir que le contenu alloué d'origine peut être mappé au nouveau cache sans être mappé à d'autres tampons dans l'ancienne collection de cache.
Les algorithmes de hachage simples ne peuvent souvent pas répondre aux exigences de monotonie, comme le hachage linéaire le plus simple:
X → AX + B MOD (P)
Dans la formule ci-dessus, P représente la taille de tous les caches. Il n'est pas difficile de voir que lorsque la taille du cache change (de P1 à P2), tous les résultats du hachage d'origine changeront, ne répondant donc pas aux exigences de la monotonie.
Les changements dans les résultats du hachage signifient que lorsque l'espace de cache change, toutes les relations de cartographie doivent être mises à jour dans le système. Dans les systèmes P2P, les modifications de cache sont équivalentes à l'adhésion aux pairs ou à la sortie du système. Cette situation se produit fréquemment dans les systèmes P2P, ce qui apportera une énorme charge informatique et de transmission. La monotonité exige que l'algorithme de hachage puisse éviter cette situation.
Dans un environnement distribué, le terminal peut ne pas voir tous les caches, mais ne peut en voir que certains. Lorsqu'un terminal souhaite cartographier le contenu au cache à travers le processus de hachage, car la plage de cache observée par différents terminaux peut être différente, le résultat du hachage est incohérent. Le résultat final est que le même contenu est mappé dans différentes zones de cache par différents terminaux. Cette situation doit évidemment être évitée car elle fait stocker le même contenu dans différents tampons, réduisant l'efficacité du stockage du système. La définition de la dispersion est la gravité de la situation ci-dessus. Un bon algorithme de hachage devrait être en mesure d'éviter autant que possible les incohérences, c'est-à-dire pour minimiser la dispersion.
Le problème de charge consiste en fait à un problème de décentralisation sous une autre perspective. Étant donné que différents terminaux peuvent cartographier le même contenu à différents tampons, pour un tampon spécifique, il peut également être mappé à différents contenus par différents utilisateurs. Comme la dispersion, cette situation doit être évitée, donc un bon algorithme de hachage devrait être en mesure de minimiser la charge tampon.
En surface, le hachage cohérent cible le problème de la mise en mémoire tampon distribuée, mais si vous considérez la mise en mémoire tampon comme un pair dans un système P2P et le contenu cartographié comme diverses ressources partagées (données, fichiers, flux multimédias, etc.), vous constaterez que les deux décrivent réellement le même problème.
Dans l'algorithme de hachage cohérent, chaque nœud (correspondant au pair dans le système P2P) a un ID attribué au hasard. Lors du mappage du contenu dans un nœud, une opération de hachage cohérente est effectuée en utilisant le mot-clé du contenu et l'ID du nœud et obtient la valeur clé. Le hachage cohérent nécessite que la valeur de clé et l'ID de nœud soient dans la même plage de valeur. La valeur de clé et l'ID la plus simple peuvent être unidimensionnels, comme un ensemble d'entiers de 0000 à 9999.
Lors du stockage du contenu en fonction de la valeur clé, le contenu est stocké sur le nœud avec l'ID la plus proche de sa valeur clé. Par exemple, si la valeur clé est 1001, il y a des nœuds avec IDS 1000, 1010, 1100 dans le système, et le contenu sera mappé à 1000 nœuds.
Pour construire les itinéraires requis pour la requête, le hachage de cohérence nécessite que chaque nœud stockait les informations de localisation (adresse IP) de son nœud de liaison montante (la valeur d'ID est supérieure à la plus petite parmi ses propres nœuds) et le nœud de liaison descendante (la valeur ID est inférieure à la plus grande parmi ses propres nœuds). Lorsqu'un nœud doit trouver du contenu, il peut décider d'initier une demande de requête au nœud de liaison montante ou de liaison descendante en fonction de la valeur clé du contenu. Si un nœud qui reçoit la demande de requête constate qu'il a la cible demandée, il peut renvoyer directement la confirmation au nœud qui initie la demande de requête; S'il constate qu'il n'appartient pas à sa propre portée, il peut transmettre la demande à son nœud de liaison montante / liaison descendante.
Afin de maintenir les informations de routage mentionnées ci-dessus, lorsqu'un nœud rejoint / quitte le système, les nœuds adjacents doivent mettre à jour les informations de routage en temps opportun. Cela nécessite que les nœuds stockent non seulement des informations de localisation de nœuds de liaison descendante directement connectés, mais connaissent également des informations indirectes de nœud de liaison descendante à une certaine profondeur (N-HOP) et maintiennent dynamiquement la liste des nœuds. Lorsqu'un nœud quitte le système, son nœud de liaison montante essaiera de se connecter directement au nœud de liaison descendante le plus proche. Une fois la connexion réussie, il obtiendra la liste des nœuds de liaison descendante à partir du nouveau nœud de liaison descendante et mettra à jour sa propre liste de nœuds. De même, lorsqu'un nouveau nœud est ajouté au système, trouvez d'abord le nœud de liaison descendante en fonction de son propre ID et obtenez la liste des nœuds de liaison descendante, puis demandez au nœud de liaison montante de modifier sa liste de nœuds de liaison descendante, restaurant ainsi la relation de routage.
discuter
Le hachage cohérent résout essentiellement le problème le plus critique dans un environnement P2P - comment distribuer le stockage et le routage dans une topologie de réseau dynamique. Chaque nœud n'a besoin que de maintenir les informations d'un petit nombre de nœuds voisins, et lorsque le nœud rejoint / quitte le système, seul un petit nombre de nœuds pertinents participent à la maintenance de la topologie. Tout cela fait du hash cohérent le premier algorithme DHT pratique.
Cependant, l'algorithme de routage du hachage cohérent présente toujours des lacunes. Pendant le processus de requête, le message de requête doit passer par l'étape O (n) (o (n) indique une relation proportionnelle avec n, et n représente le nombre total de nœuds dans le système) avant de pouvoir atteindre le nœud de requête. Il n'est pas difficile d'imaginer que lorsque le système est très important, le nombre de nœuds peut dépasser un million et une telle efficacité de requête est évidemment difficile à répondre aux besoins d'utilisation. Dans un autre point de vue, même si l'utilisateur peut tolérer de longs retards, la grande quantité de messages générés pendant le processus de requête apportera une charge inutile au réseau.
Package Herotrix; Importer java.util.collection; import java.util.sortedmap; import java.util.treemap; classe publique cohérenthash <t> {// algorithme de hashs privé hashfonction hashfonction; // nombre de nœuds virtuels privés final nombre Treemap <Integer, t> (); public cohérenthash (hashfonction hashfunction, int numberofreplicas, collection <T> nœuds) {this.hashfonction = hashfonction; this.numberofreplicas = nombreOfReplicas; pour (t nœud: nœuds) {add (nœud);}} public void add (t nœud) {for (int i = 0; i <numberofreplicas; i ++) {Circle.put (hashfonction.hash (node.tostring () + i), node);}} public retire (t nœud) {pour (pour it i = 0; i <nombre i ++) {Circle.Remove (hashfunction.hash (node.toString () + i));}} // algorithme clé public t get (clé d'objet) {if (cercle.isempty ()) {return null;} // calcul hash value inth hash = hashfunction.hash (key); // si la valeur hash est incluse hash = hashfunction. if (! Circle.ContainsKey (hash)) {tridmap <Integer, t> tailmap = cercle.tailmap (hash); hash = tailmap.isempty ()? Circle.FirstKey (): TailMap.FirstKey ();} return Circle.get (hash);}}Ce qui précède est l'intégralité du contenu de cet article sur les notes d'apprentissage de l'algorithme de hachage cohérent de la langue java (exemples de code). J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!