Table de hachage distribuée

Une table de hachage distribuée (ou DHT pour Distributed Hash Table), est une technique permettant la mise en place d’une table de hachage dans un système réparti. 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é.

Distributed hash tables

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

Supposons qu'un grand nombre d'utilisateurs (5 millions) aient lancé leur logiciel de partage de fichiers en pair à pair (Peer-to-Peer, P2P) sur leur ordinateur. Chacun partage ses fichiers (audio, images, vidéo, multimédia, etc.). Un utilisateur (Luc) possède, par exemple, l'album (fictif) « 42 mon amour ».

Supposons qu'un autre utilisateur (Pierre) souhaite télécharger cet album. Comment son logiciel de P2P peut-il trouver l'ordinateur de Luc ? Le logiciel de Pierre pourrait éventuellement demander aux 5 millions d'ordinateurs si par hasard ils possèdent cet album. Le logiciel de Luc répondrait alors : « Je le possède et je peux commencer à le transférer. » Il serait cependant très long et très lourd en consommation de ressources de demander aux 5 millions d'ordinateurs s'ils ont cet album, car il y aurait en permanence des millions de questions du type « Je cherche tel album, l'as-tu ? », entraînant des millions de réponses : « Non, désolé ! ».

Un grand annuaire archivant les noms des fichiers partagés par tous les utilisateurs résoudrait la question : il suffirait de demander à ce « grand annuaire » (la table de hachage) l'album de musique 42 mon amour pour obtenir la réponse : « Il est disponible sur l'ordinateur de Luc. (et celui de Mathieu, de Paul, etc.) ». C'est ainsi que fonctionnait la première génération de réseaux P2P. Un serveur central servait de « grand annuaire » (exemples : Napster, Audiogalaxy, Edonkey, Kazaa). Cette solution est de moins en moins utilisée en raison de sa fragilité ; en effet si le serveur central n'est plus disponible, on ne peut plus faire aucune recherche sur les fichiers partagés du réseau, on parle alors de point de défaillance unique.

La table de hachage distribuée apporte donc, par rapport aux techniques précédentes, l'indépendance vis-à-vis d'un serveur central en le distribuant sur les différents nœuds.

Par exemple, l'utilisateur Jean-Claude va être responsable de tous les fichiers qui commencent par A, Toto va être responsable de tous les fichiers qui commencent par B, etc. Lorsqu'un nouvel utilisateur se connecte au réseau, la première chose que le logiciel va faire est d'annoncer quels fichiers sont en mesure d'être partagés. S'il possède par exemple le film Big Buck Bunny, il va dire à l'utilisateur Toto (qui est responsable des fichiers qui commencent par B) : « J'ai le film Big Buck Bunny. Si des gens le veulent, il est disponible chez moi ». Les recherches deviennent donc très rapides. Si on cherche Big Buck Bunny, on va directement demander à la personne responsable de la lettre « B ».

La réalité est un peu plus complexe : il ne faut pas qu'une seule personne soit responsable des mots qui commencent par "B", car si elle éteint son ordinateur une partie de l'annuaire sera perdue. Il faut donc introduire une certaine redondance dans l'annuaire, et donc plusieurs ordinateurs sont simultanément responsables des mêmes listes. De plus, vu qu’il y a des centaines de millions 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 des mots des titres des fichiers.

Enfin, chaque ordinateur n'a pas besoin de connaître tous les ordinateurs qui archivent des mots. Il connaîtra typiquement une centaine d'ordinateurs. Si l'utilisateur fait une recherche sur Big Buck Bunny et ne connaît pas l'ordinateur qui archive les fichiers commençant par B, alors :

• il demandera à l'ordinateur le plus proche (par exemple l'ordinateur qui archive les fichiers commençant par C) : « Connais-tu l'ordinateur s'occupant des mots commençant par B ? »
• celui-ci répondra « Parmi mes voisins, je connais les ordinateurs qui s'occupent des B, et même je connais des ordinateurs qui s'occupent des fichiers commençant par BA, BI, BO, BU, donc tu ferais bien de demander à celui qui connaît les fichiers commençant par BI s'il a par hasard le fichier que tu cherches. »
• on interroge le responsable des « BI » et il dira : « Oui, je connais les ordinateurs qui ont le film que tu veux » ou alors, s'il ne les connaît pas, il répondra « Je ne connais pas ton fichier, par contre je connais un ordinateur qui s'occupe des fichiers commençant par BIG, donc demande-lui. »

Utilisation

Dans les logiciels de partage de données

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

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

Annexes

Voir aussi

• Fonction de hachage
• Hashtable
• P2P
• Kademlia (mécanisme de table de hachage distribuée utilisé dans eMule)
• BitTorrent