Table de hachage distribuée

Une table de hachage distribuée (ou DHT en anglais, de Distributed Hash Table) est une table de hachage équitablement répartie sur des ordinateurs d'un réseau de communications (typiquement les nœuds d'un réseau pair-à-pair).

Une table de hachage est une structure de données de type « clé → valeur ». Chaque donnée est associée à une clé et est distribuée sur le réseau. Les tables de hachage permettent de répartir le stockage des données sur l’ensemble des nœuds du réseau, chaque nœud étant responsable d’une partie de ces données. Les tables de hachage distribuées fournissent un algorithme pour retrouver le nœud responsable de la donnée et sa valeur à partir de la clé.

Les protocoles Chord^[1], P2P CAN^[1], Tapestry, Pastry, Kademlia mettent en place des tables de hachage distribuées. Les tables de hachage distribuées sont utilisées dans des systèmes de partage de données de type pair-à-pair (comme BitTorrent, IPFS, etc.)^[2],[1], mais aussi dans des logiciels fonctionnant de manière décentralisée comme le moteur de recherche distribué YaCy ou encore dans le routage anonyme en oignon avec Tor ou I2P.

Lorsqu'un utilisateur souhaite télécharger un fichier dans un réseau pair-à-pair, il est possible d'envoyer une requête à tous les utilisateurs du système, mais cette solution nécessite autant de requêtes que de nœuds alors qu'une seule pourrait suffire si l'utilisateur pouvait avoir accès à un annuaire centralisé (hébergé sur un serveur du système).

Une solution à ce problème consiste donc à proposer un annuaire centralisé auquel les requêtes peuvent être adressées (c'était, par exemple, le cas de Napster, Audiogalaxy, Edonkey, Kazaa)^[1]. Cependant cette solution a parfois été considérée comme « vulnérable » en ce sens que le système repose sur un seul ordinateur.

La génération suivante de systèmes pair-à-pair a donc cherché à multiplier le nombre de serveurs hébergeant l'annuaire et, pour que la charge soit naturellement équilibrée, que chacun soit seulement responsable d'une partie de cet annuaire.

Dans le meilleur des cas, chaque participant peut être responsable d'une partie de l'annuaire. Par exemple, dans le cas d'un système (très simple) avec 26 utilisateurs, chacun pourrait être responsable des titres commençant par une lettre donnée de l'alphabet et chaque participant devrait seulement connaître l'ensemble des couples associant chaque lettre à l'ordinateur qui en est responsable.

Pour compenser l'extinction ou le départ d'un des participants, il faut introduire une certaine redondance dans le système (une liste donnée doit être supportée par un certain nombre d'ordinateurs).

De plus, étant donné la grande quantité de fichiers partagés, le principe de division de l'annuaire n'est pas basé sur les lettres de l'alphabet mais sur une table de hachage de l'ensemble des noms des fichiers.

Enfin, les tables de hachage distribuées partent du principe que chaque ordinateur n'a pas besoin de connaître tous les ordinateurs faisant partie de l'annuaire, mais seulement l'adresses de ses voisins (en fonction de la topologie et de la stratégie de recherche choisies).

De nombreux logiciels de partage de données utilisent une DHT pour décentraliser une partie des informations, par exemple, Ares Galaxy, de nombreux clients récents pour le protocole BitTorrent^[3] également, comme Azureus, BitComet, Deluge, KTorrent, Transmission ou encore µTorrent utilisent une DHT pour trouver des pairs sans nécessité d'utiliser destrackers.

Le premier client BitTorrent (Bt) à utiliser une DHT est Azureus, suivi du client officiel : « BitTorrent » qui crée une version différente. La version du client officiel est alors appelée Mainline DHT, version supportée par la plupart des clients Bt.

Certains logiciels de messagerie instantanée utilisent une DHT pour décentraliser une partie des informations, par exemple Jami^[4] ou Tox.

• Fonction de hachage
• Table de hachage

• Portail de l’informatique