Simple explication de base d'une Table de Hachage (DHT)

Ok, ils sont fondamentalement une idée plutôt simple. Une DHT vous donne un dictionnaire-comme l'interface, mais les nœuds sont distribués à travers le réseau. Le truc avec Dht est que le nœud qui reçoit pour stocker une clé est trouvé par hachage de cette clé, donc en effet votre table de hachage seaux sont maintenant indépendants des nœuds dans un réseau.

Cela donne beaucoup de tolérance de panne et de fiabilité, et éventuellement un avantage en termes de performance, mais il jette aussi beaucoup de maux de tête. Par exemple, ce qui se passe quand un nœud quitte le réseau, par défaut ou autrement? Et comment voulez-vous de les redistribuer les touches lorsqu'un nœud rejoint de sorte que la charge est à peu près équilibré. Venez pour penser à elle, comment avez-vous répartir les clés de toute manière? Et lorsqu'un nœud rejoint, comment éviter de ressasser tout? (N'oubliez pas que vous avez à faire cela dans un normal la table de hachage si vous augmentez le nombre de seaux).

Un exemple de DHT qui s'attaque à certains de ces problèmes est une logique de l'anneau de n nœuds, chacun de prendre la responsabilité de 1/n de l'espace. Une fois que vous ajoutez un nœud dans le réseau, il trouve une place sur le ring pour s'asseoir entre deux autres nœuds, et prend la responsabilité de quelques-unes des clés de son frère nœuds. La beauté de cette approche est qu'aucun des autres nœuds de l'anneau sont affectés; seuls les deux nœuds frère ont pour redistribuer les touches.

Par exemple, dire de un à trois nœuds de l'anneau le premier nœud dispose de touches de 0 à 10, la deuxième 11-20 et la 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 3 clés, alors maintenant, il traite avec 26-30 et le nœud 3 est consacré à 21-25.

Il existe de nombreuses autres superposition des structures telles que l'utilisation du contenu de routage pour trouver le bon nœud sur lequel stocker une clé. La localisation d'une clé dans un anneau nécessite la recherche tour de la bague d'un nœud à la fois (sauf si vous gardez un local à look-up table), problématique dans une DHT de milliers de nœuds), qui est O(n)-hop de routage. D'autres structures, y compris augmentée anneaux de garantie O(log n)-hop de routage, et certains prétendent O(1)-hop de routage au prix de plus d'entretien.

Lire la page de wikipedia, et si vous voulez vraiment savoir dans un peu de profondeur, découvrez cette page de cours à Harvard, qui a une assez complète de la liste de lecture.

Je tiens à ajouter sur HenryR de réponse utile que j'ai juste eu un aperçu cohérent de hachage. Normal/naïve de hachage de recherche est une fonction de deux variables, dont l'un est le nombre de compartiments. La beauté de la constance de hachage est que nous éliminer le nombre de seaux "n", à partir de l'équation.

Naïve de hachage, la première variable est la clé de l'objet à être stockées dans la table. Nous allons appeler la touche "x". La deuxième variable est le nombre de seaux, "n". Donc, pour déterminer le seau/machine, l'objet est stocké, vous devez calculer: hash(x) mod(n). Par conséquent, lorsque vous modifiez le nombre de seaux, vous pouvez également modifier l'adresse à laquelle presque tous les objets sont stockées.

Comparer cela à la cohérence de hachage. Nous allons définir un "R" comme la gamme d'une fonction de hachage. La R est juste une constante. Dans l'optique de hachage, l'adresse d'un objet est situé à la hash(x)/R. étant donné que notre recherche n'est plus fonction du nombre de seaux, nous nous retrouvons avec moins de reconfiguration si on change le nombre de compartiments.

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