Ok, à la base, c'est une idée assez simple. Un DHT vous offre une interface de type dictionnaire, mais les nœuds sont distribués sur le réseau. L'astuce avec les DHT est que le nœud qui peut stocker une clé particulière est trouvé en hachant cette clé, donc en fait, les buckets de votre table de hachage sont maintenant des nœuds indépendants dans un réseau.
Cela permet d'obtenir une grande tolérance aux pannes et une grande fiabilité, et éventuellement quelques avantages en termes de performances, mais cela pose également de nombreux problèmes. Par exemple, que se passe-t-il lorsqu'un nœud quitte le réseau, par défaillance ou autre ? Et comment redistribuer les clés lorsqu'un nœud se joint au réseau afin que la charge soit à peu près équilibrée ? En y réfléchissant, comment distribuer les clés de manière égale de toute façon ? Et lorsqu'un nœud s'ajoute, comment éviter de tout remettre à plat ? (Rappelez-vous que vous devriez faire cela dans une table de hachage normale si vous augmentez le nombre de seaux).
Un exemple de DHT qui aborde certains de ces problèmes est un anneau logique de nœuds, chacun prenant la responsabilité de 1/n de l'espace des clés. Une fois que vous ajoutez un nœud au réseau, il trouve une place sur l'anneau entre deux autres nœuds, et prend la responsabilité de certaines des clés de ses nœuds frères. L'intérêt 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 la moitié de l'espace des clés du nœud 3, donc maintenant il s'occupe de 26-30 et le nœud 3 s'occupe de 21-25.
Il existe de nombreuses autres structures superposées de ce type qui 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, il faut faire le tour de l'anneau un nœud à la fois (à moins de conserver une table de consultation locale, ce qui est problématique dans une DHT de milliers de nœuds), ce qui représente un routage de O(n). D'autres structures - y compris les anneaux augmentés - garantissent un routage à O(log n), et certaines prétendent à un routage à O(1) au prix d'une maintenance plus importante.
Lisez la page wikipédia, et si vous voulez vraiment savoir un peu plus en profondeur, regardez ceci page du cours à Harvard qui a une liste de lecture assez complète.
