Table de hachage distribuée
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Une table de hachage distribuée (ou DHT pour Distributed Hash Table), est une technologie permettant l'identification et l'obtention, dans un système réparti, comme certains réseaux P2P, d'une information. L'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...) de la table de hachage est constituée virtuellement par tous ces constituants répartis sur tous les éléments du réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un filet (un réseau est un « petit rets », c'est-à-dire un petit filet), on appelle nœud (node)...), qui en possèdent chacun une partie.

Les tables de hash réparties sont utilisées notamment dans les protocoles Chord (Chord est un projet P2P subventionné par le gouvernement des États-Unis d'Amérique, utilisant notamment une topologie en anneau.), protocole P2P CAN, Tapestry (Tapestry (de l'anglais: tapisserie) est un protocole P2P utilisant une table de hachage distribuée.), Kademlia (Kademlia est un réseau de recouvrement créé pour décentraliser les autres réseaux d'échange de fichiers poste-à-poste (Peer-to-Peer ou P2P en anglais).) (utilisé par eMule), Ares Galaxy (Ares Galaxy, actuellement en version 2.0.9, est un logiciel libre de peer-to-peer (P2P) intégrant la technologie DHT et fonctionnant sur son propre réseau décentralisé.). Système aussi utilisé dans de nombreux clients récents pour le protocole BitTorrent (BitTorrent est un protocole de transfert de données poste à poste (P2P) à travers un réseau informatique développé par Bram Cohen. Le protocole a été conçu en avril 2001 et mis en place à l'été 2002 par le...) comme Azureus, Bitcomet ou encore µTorrent (prononcer Micro Torrent). Le premier client (Le mot client a plusieurs acceptations :) BitTorrent à utiliser le DHT était Azureus, suivi du client officiel BitTorrent, c'était deux versions différentes. La version officielle fut alors appelée Mainline DHT. Dorénavant la plupart des clients supportent la version Mainline DHT.

Principe

Supposons un grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'utilisateurs (5 millions) ayant lancé leur logiciel (En informatique, un logiciel est un ensemble d'informations relatives à des traitements effectués automatiquement par un appareil informatique. Y sont inclus les instructions de traitement, regroupées sous forme de programmes,...) de P2P (Peer-to-Peer) sur leur ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler des données sous forme...). Chacun partage quelques fichiers (films au format MPEG, images, disques, etc.)

Un utilisateur (Luc) possède par exemple l'album de musique "Les idees saines de Serge Dassault (Serge Dassault, né Serge Bloch le 4 avril 1925 à Paris, est un chef d'entreprise et homme politique français, sénateur et ancien maire de Corbeil-Essonnes.)" (disponible sous licence Creative Commons).

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 (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon de causes, au moins d'une reconnaissance de cause à effet d'un événement.) ils possèdent cet album. Le logiciel de Luc répondrait alors : "Je le possède et peux commencer à le transférer".

Il serait cependant bien lent de demander aux 5 millions d'ordinateurs si ils ont cet album, car il y aurait en permanence des millions de questions "Je cherche tel album, l'as-tu ?", entraînant des millions de réponses : "Non, désolé !".

Un grand annuaire (Un annuaire est une publication (imprimée ou électronique) mise à jour chaque année qui regroupe des informations (nom, adresse, coordonnées, etc.)...) 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 "Les idees saines de Serge Dassault"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. Il y avait un serveur central (En informatique, un serveur central centralise un service. Les serveurs centraux sont utilisés généralement dans une architecture centralisée a contrario d'une architecture décentralisée. On parle...) qui servait de "grand annuaire". Exemples : Napster (Napster est souvent considéré comme le premier réseau P2P. Son architecture était centralisée : les éléments du réseau annoncaient les...), Audiogalaxy (Audiogalaxy était un système de partage de fichier centralisé sur Internet très populaire. Le site met aujourd'hui à disposition de la musique en ligne via la...), Edonkey, Kazaa

Cette solution est de plus en plus abandonnée en raison de sa fragilité (La fragilité est l'état d'une substance qui se fracture lorsqu'on lui impose des contraintes mécaniques ou qu'on lui fait subir des...). Que faire lorsque le serveur central tombe en panne ? Ou prend feu ? Ou est saisi par la police ? Le réseau ne fonctionne plus, on ne peut plus faire de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne...) sur les fichiers partagés.

Les programmeurs de logiciels P2P ont alors eu une idée : Il faudrait que le "grand annuaire" ne soit pas sur un seul ordinateur, mais sur des centaines. Et ils se sont dit, on a qu'a faire notre logiciel de tel façon que chaque utilisateur soit responsable d'un petit bout du grand annuaire. Chacun des 5 millions d'utilisateurs est responsable d'une petite partie: On dit que c'est une table de hachage distribuée.

Par exemple, l'utilisateur Jean-Claude va etre responsable de tous les fichiers qui commencent par A, Toto va être responsable de tous les fichiers qui commencent par B, etc. Lorsque un nouvel utilisateur se connecte au reseau, la première chose que le logiciel va faire, c'est de dire quels fichiers il peut partager. Si il possède un film qui s'appelle par exemple "Bourdieu", il va dire a l'utilisateur Toto (qui est responsable des fichiers qui commencent par B): " j'ai le film "Bourdieu". Si des gens le veulent, c'est chez moi. " Et donc les recherches deviennent très rapides. Si on cherche "Bourdieu" : 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 on perd une partie de l'annuaire. Il faut donc introduire de la redondance dans l'annuaire, et plusieurs ordinateurs sont simultanément responsables des mêmes mots. De plus, il y a des centaines de millions de fichiers partagés, donc le principe de division (La division est une loi de composition qui à deux nombres associe le produit du premier par l'inverse du second. Si un nombre est non nul, la fonction "division par ce nombre" est la réciproque de la fonction "multiplication...) de l'annuaire n'est pas selon les lettres de l'alphabet, mais selon une table de hachage des mots des titres des fichiers.

Enfin, chaque ordinateur n'a pas besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est souvent fait un classement des besoins humains en trois grandes...) de connaitre tous les ordinateurs qui archivent des mots. Il connaitra typiquement une centaine d'ordinateurs. Si l'utilisateur fait une recherche sur "Bourdieu" et ne connait pas l'ordinateur qui archive les fichiers commencant par B,

  • il demandera à l'ordinateur le plus proche (par exemple l'ordinateur qui archivent les fichiers commencant par C) : "Connais-tu l'ordinateur s'occupant des mots commencant par B ?",
  • l'autre 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 commencant par BA, BO, BU, donc tu ferais bien de demander à celui qui connaît les fichiers commençant par BO si il a par hasard le film que tu cherches". Après on interroge le responsable des "BO" 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 film, par contre je connais un ordinateur qui s'occupe des fichiers commençant par BOU, donc demande-lui."
Page générée en 0.276 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique