Explication de base Simple d'une Table de hachage distribuée (DHT)
Quelqu'un pourrait-il donner une explication sur le fonctionnement d'une DHT?
Rien de trop lourd, juste les bases.
5 réponses
Ok, ils sont fondamentalement une idée assez simple. Un DHT vous donne une interface de type dictionnaire, mais les nœuds sont distribués sur le réseau. L'astuce avec DHTs est que le nœud qui stocke une clé particulière est trouvé en hachant cette clé, donc en effet vos compartiments de table de hachage sont maintenant des nœuds indépendants dans un réseau.
Cela donne beaucoup de tolérance aux pannes et de fiabilité, et peut-être des avantages de performance, mais cela soulève aussi beaucoup de maux de tête. Par exemple, ce se produit lorsqu'un nœud quitte le réseau, en échouant ou autrement? Et comment redistribuez-vous les clés lorsqu'un nœud se joint pour que la charge soit à peu près équilibrée. En y réfléchissant, comment répartissez-vous uniformément les clés de toute façon? Et quand un nœud se joint, Comment éviter de tout ressasser? (Rappelez-vous que vous devriez le faire dans une table de hachage normale si vous augmentez le nombre de compartiments).
Un exemple 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. Une fois que vous ajoutez un nœud au réseau, il trouve un endroit sur l'anneau pour s'asseoir entre deux autres nœuds, et prend la responsabilité de certaines des clés de ses nœuds frères. La beauté de cette approche est 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, disons dans un anneau à trois nœuds le premier nœud a des clés 0-10, le second 11-20 et le troisième 21-30. Si un quatrième nœud arrive et s'insère entre nœuds 3 et 0 (rappelez-vous, ils sont dans un anneau), il peut prendre la responsabilité de dire la moitié de l'espace de clés de 3, alors maintenant il traite de 26-30 et le nœud 3 traite de 21-25.
Il existe de nombreuses autres structures de superposition telles que celle-ci qui utilisent le routage basé sur le contenu pour trouver le bon nœud sur lequel stocker une clé. Localiser une clé dans un anneau nécessite une recherche autour de l'anneau un nœud à la fois (sauf si vous gardez une table de recherche locale, problématique dans un DHT de milliers de nœuds), qui est le routage O(N)-hop. Autre les structures - y compris les anneaux augmentés - garantissent le routage o(log n)-hop, et certaines prétendent au routage O(1)-hop au coût de plus d'entretien.
Lisez la page wikipedia, et si vous voulez vraiment savoir un peu de profondeur, consultez cette coursepage {[12] } à Harvard qui a une liste de lecture assez complète.
Les DHT fournissent le même type d'interface à l'utilisateur qu'une table de hachage normale (recherchez 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 essentiellement si j'écris plus -
Je voudrais ajouter à la réponse utile de HenryR car je viens d'avoir un aperçu du hachage cohérent. Une recherche de hachage normale / naïve est une fonction de deux variables, dont l'une est le nombre de compartiments. La beauté du hachage cohérent est 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 clé "x". La deuxième variable est le nombre de seaux, "n". Ainsi, afin de déterminer qui seau/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 cela à un hachage cohérent. Définissons "R" comme la plage d'une fonction de hachage. R est juste une constante. Dans le hachage cohérent, l'adresse d'un objet est située à hash (x) / R. puisque notre recherche n'est plus fonction du nombre de compartiments, nous nous retrouvons avec moins remappage lorsque nous changeons le nombre de seaux.
Découvrez cet article de Wikipédia Ou cette diapositive powerpoint
Découvrez Dynamo D'Amazon, il explique une implémentation DHT simple mais Nouvelle basée sur le hachage cohérent du cercle.