Explication de base simple d’une table de hachage dissortingbuée (DHT)

Quelqu’un pourrait-il expliquer comment fonctionne une DHT?

Rien de trop lourd, juste les bases.

Ok, ils sont fondamentalement une idée assez simple. Un DHT vous donne une interface de type dictionnaire, mais les noeuds sont répartis sur le réseau. L’astuce avec les DHT est que le nœud qui stocke une clé particulière est trouvé en hachant cette clé. En conséquence, vos compartiments de table de hachage sont désormais des nœuds indépendants sur un réseau.

Cela donne beaucoup de tolérance aux fautes et de fiabilité, et peut-être un avantage en termes de performances, mais cela crée également beaucoup de problèmes. Par exemple, que se passe-t-il lorsqu’un nœud quitte le réseau, en cas d’échec ou autre? Et comment redissortingbuez-vous les clés lorsqu’un nœud se joint pour que la charge soit à peu près équilibrée. En y repensant, comment dissortingbuez-vous les clés de manière uniforme? Et quand un nœud se joint, comment éviter de tout réutiliser? (Rappelez-vous 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 de clés. Une fois que vous avez ajouté un nœud au réseau, il trouve une place sur l’anneau entre deux autres nœuds et prend en charge 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 redissortingbuer les clés.

Par exemple, disons que dans un anneau à trois nœuds, le premier nœud a les clés 0-10, le deuxième 11-20 et le troisième 21-30. Si un quasortingème nœud arrive et s’insère entre les nœuds 3 et 0 (souvenez-vous qu’ils sont dans un anneau), il peut assumer la responsabilité de la moitié de l’espace des touches de 3, alors il traite maintenant de 26-30 et du nœud 3 de 21 -25.

Il existe de nombreuses autres structures de recouvrement telles que celle-ci qui utilisent le routage basé sur le contenu pour trouver le nœud approprié sur lequel stocker une clé. Localiser une clé dans un anneau nécessite de rechercher l’anneau un nœud à la fois (sauf si vous conservez une table de recherche locale, problématique dans un DHT de milliers de nœuds), qui est le routage O (n) -hop. D’autres structures – y compris des anneaux augmentés – garantissent un routage O (log n) -hop, et certaines prétendent au routage O (1) -hop au prix d’une maintenance plus importante.

Lisez la page wikipedia et, si vous voulez vraiment savoir en profondeur, consultez cette page de cours à Harvard, qui contient 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 dissortingbuées sur un nombre arbitraire de noeuds connectés. Wikipedia a une bonne introduction de base que je conspirerais essentiellement si j’écris plus –

http://en.wikipedia.org/wiki/Dissortingbuted_hash_table

Je voudrais append à 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 fonction de deux variables, dont 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’object à stocker dans la table. Nous appellerons la clé “x”. La deuxième variable est le nombre de compartiments, “n”. Donc, pour déterminer quel compartiment / machine l’object 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 objects 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 object est située à hash (x) / R. Comme notre recherche ne dépend plus du nombre de compartiments, nous avons moins de remappage lorsque nous modifions le nombre de compartiments.

http://michaelnielsen.org/blog/consistent-hashing/

Consultez cet article Wikipedia ou cette diapositive PowerPoint

Découvrez Amazon Dynamo, il explique une implémentation DHT simple mais originale basée sur le hachage cohérent de cercle.