Explication de base simple d'une table de hachage distribuée (DHT)
https://stackoverflow.com/questions/144360
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quelqu'un pourrait-il expliquer le fonctionnement d'une DHT?
Rien de trop lourd, juste l'essentiel.
La solution
Ok, c’est fondamentalement une idée assez simple. Un DHT vous donne une interface de type dictionnaire, mais les nœuds sont répartis sur le réseau. Le truc avec les DHT est que le noeud qui doit stocker une clé particulière est trouvé en hachant cette clé. Ainsi, vos compartiments de table de hachage sont désormais des noeuds indépendants dans un réseau.
Cela donne beaucoup de tolérance aux pannes et de fiabilité, et peut-être même un avantage en termes de performances, mais également beaucoup de maux de tête. Par exemple, que se passe-t-il lorsqu'un nœud quitte le réseau, en cas d'échec ou autrement? Et comment redistribuer les clés lorsqu'un nœud se joint pour que la charge soit approximativement équilibrée. À bien y penser, comment distribuez-vous les clés de façon égale? Et quand un nœud rejoint, comment éviter de tout ressasser? (N'oubliez pas que vous devez le faire dans une table de hachage normale si vous augmentez le nombre de compartiments).
Un exemple de DHT qui aborde certains de ces problèmes est un anneau logique de n nœuds, chacun prenant la responsabilité de 1 / n de l’espace clé. Une fois que vous avez ajouté un nœud au réseau, celui-ci trouve une place sur l’anneau pour s’asseoir entre deux autres nœuds et assume la responsabilité de certaines des clés de ses nœuds frères. La beauté de cette approche réside dans le fait qu’aucun des autres nœuds de l’anneau n’est affecté; seuls les deux nœuds frères doivent redistribuer les clés.
Par exemple, dans un anneau à trois noeuds, le premier noeud a les clés 0-10, le deuxième 11-20 et le troisième 21-30. Si un quatrième nœud arrive et s'insère entre les nœuds 3 et 0 (rappelez-vous, ils forment un anneau), il peut assumer la responsabilité de la moitié de l'espace de clé de 3, il traite donc maintenant de 26 à 30 et le nœud 3 de 21 -25.
De nombreuses autres structures de recouvrement telles que celle-ci utilisent le routage basé sur le contenu pour trouver le bon nœud sur lequel stocker une clé. Pour localiser une clé dans un anneau, vous devez rechercher tour à tour un noeud à la fois (sauf si vous conservez une table de correspondance locale, problématique dans une DHT de milliers de noeuds), qui correspond au routage O (n) -hop. D'autres structures, y compris les anneaux augmentés, garantissent le routage O (log n) et certaines revendiquent le routage O (1) au détriment de la maintenance.
Lisez la page wikipedia et si vous voulez vraiment avoir plus de détails, jetez un œil à ceci page de cours à Harvard, qui possède une liste de lecture assez complète.
Autres conseils
Les DHT fournissent à l'utilisateur le même type d'interface qu'une hashtable normale (recherche d'une valeur par clé), mais les données sont réparties sur un nombre arbitraire de nœuds connectés. Wikipedia a une bonne introduction de base que je régurgiterais si j'écrivais davantage -
J'aimerais ajouter une réponse utile à la réponse de HenryR, car je venais de comprendre le hachage cohérent. Une recherche de hachage normale / naïve est une fonction de deux variables, l'une d'entre elles étant le nombre de compartiments. La beauté du hachage cohérent réside dans le fait que nous éliminons le nombre de seaux "n" de l'équation.
Dans le hachage naïf, la première variable est la clé de l’objet à stocker dans la table. Nous appellerons la touche "x". La seconde variable est le nombre de compartiments, "n". Donc, pour déterminer dans quel compartiment / quelle machine l’objet est stocké, vous devez calculer: hash (x) mod (n). Par conséquent, lorsque vous modifiez le nombre de compartiments, vous modifiez également l'adresse à laquelle presque tous les objets sont stockés.
Comparez ceci à un hachage cohérent. Définissons " R " comme la plage d'une fonction de hachage. R est juste une constante. Dans un hachage cohérent, l'adresse d'un objet est située à hash (x) / R. Étant donné que notre recherche n'est plus fonction du nombre de compartiments, nous avons moins de remappages lorsque nous modifions le nombre de compartiments.
Découvrez cet article de Wikipedia . Ou bien cette diapositive PowerPoint
Découvrez le Dynamo d’Amazon, qui décrit une implémentation DHT simple mais nouvelle basée sur le hachage conforme au cercle.
