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é. 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, , 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. 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). 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é ! ».