Explication de base simple d'une table de hachage distribuée (DHT)

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

Rien de trop lourd, juste les bases.

Ok, c'est fondamentalement une idée assez simple. Un DHT vous offre une interface de type dictionnaire, mais les nœuds sont répartis sur le réseau. L'astuce avec les DHT est que le nœud qui parvient à stocker une clé particulière est trouvé en hachant cette clé, donc en fait 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 certains avantages en termes de performances, mais cela crée également beaucoup de maux de tête. Par exemple, que se passe-t-il lorsqu'un nœud quitte le réseau, en échec ou autrement? Et comment redistribuer les clés lorsqu'un nœud se joint pour que la charge soit à peu près équilibrée. En y réfléchissant bien, comment répartissez-vous de manière uniforme les clés? Et quand un nœud se joint, comment éviter de tout ressasser? (N'oubliez pas que vous devrez 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 de clés. Une fois que vous avez ajouté un nœud au réseau, il trouve une place 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 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 quatrième nœud arrive et s'insère entre les 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, donc maintenant il traite 26-30 et le nœud 3 traite 21 -25.

Il existe de nombreuses autres structures de superposition comme celle-ci qui utilisent le routage basé sur le contenu pour trouver le bon nœud sur lequel stocker une clé. La localisation d'une clé dans un anneau nécessite une recherche autour de l'anneau, un nœud à la fois (à moins que vous ne gardiez 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 le routage O (log n) -hop, et certaines prétendent au routage O (1) -hop au prix d'une maintenance accrue.

Lisez la page wikipedia, et si vous voulez vraiment savoir un peu 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 distribuées sur un nombre arbitraire de nœuds connectés. Wikipedia a une bonne introduction de base que je régurgiterais essentiellement si j'écrivais plus -

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

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 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 touche "x". La deuxième variable est le nombre de compartiments, "n". Ainsi, pour déterminer dans quel 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. Comme notre recherche n'est plus fonction du nombre de compartiments, nous nous retrouvons avec moins de remappage lorsque nous modifions le nombre de compartiments.

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