Table de hachage distribuée
Pour les articles homonymes, voir DHT.
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 communication (typiquement les nœuds participants 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 de données sur l’ensemble des nœuds du réseau, chaque nœud étant responsable d’une partie des 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, P2P CAN, 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.), 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 gousse d'ail avec I2P.
Principe
[modifier | modifier le code]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 exemples le cas de Napster, Audiogalaxy, Edonkey, Kazaa). 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 à 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 résister à l'extinction ou au départ d'un des participants, il faut aussi 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 plutôt sur une table de hachage sur 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 participant à l'annuaire, mais seulement l'adresses de ses voisins (en fonction de la topologie et de la stratégie de recherche choisies).
Utilisation
[modifier | modifier le code]Dans les logiciels de partage de données
[modifier | modifier le code]De nombreux logiciels de partage de données utilisent une DHT pour décentraliser une partie des informations, par exemple, Ares Galaxy, également, de nombreux clients récents pour le protocole BitTorrent comme Azureus, Bitcomet, Deluge, I2pSnark, KTorrent, Transmission ou encore µTorrent utilisent une DHT pour permettre de trouver des pairs sans utiliser de tracker.
Le premier client BitTorrent à utiliser une DHT était Azureus, suivi du client officiel BitTorrent qui créa une version différente. La version du client officiel fut alors appelée Mainline DHT. Dorénavant la plupart des clients supportent la version Mainline DHT.
Dans les logiciels de messagerie instantanée
[modifier | modifier le code]Certains logiciels de messagerie instantanée utilisent une DHT pour décentraliser une partie des informations, par exemple Jami ou Tox.
Notes et références
[modifier | modifier le code]Annexes
[modifier | modifier le code]Voir aussi
[modifier | modifier le code]- Fonction de hachage
- Hashtable
- P2P
- Kademlia (mécanisme de table de hachage distribuée utilisé dans eMule)
- BitTorrent
