Table de hachage distribuée

Une table de hachage distribuée ( DHT ) est un système distribué qui fournit un service de recherche similaire à une table de hachage . Les paires clé-valeur sont stockées dans une DHT et tout nœud participant peut récupérer efficacement la valeur associée à une clé donnée. Le principal avantage d'une DHT est que des nœuds peuvent être ajoutés ou supprimés avec un minimum de travail autour de la redistribution des clés. Les clés sont des identifiants uniques qui correspondent à des valeurs particulières , qui à leur tour peuvent être n'importe quoi, des adresses aux documents en passant par des données arbitraires . La responsabilité de maintenir le mappage des clés aux valeurs est répartie entre les nœuds, de telle sorte qu'un changement dans l'ensemble des participants entraîne un minimum de perturbations. Cela permet à une DHT de s'adapter à un nombre extrêmement important de nœuds et de gérer les arrivées, les départs et les échecs continus des nœuds.

Les DHT forment une infrastructure qui peut être utilisée pour créer des services plus complexes, tels que l'anycast , la mise en cache coopérative du Web , les systèmes de fichiers distribués , les services de noms de domaine , la messagerie instantanée , la multidiffusion , ainsi que le partage de fichiers peer-to-peer et les systèmes de distribution de contenu . Parmi les réseaux distribués notables qui utilisent les DHT, on peut citer le tracker distribué de BitTorrent , le réseau Kad , le botnet Storm , la messagerie instantanée Tox , Freenet , le moteur de recherche YaCy et l' InterPlanetary File System .

Les recherches sur la DHT ont été initialement motivées, en partie, par les systèmes peer-to-peer (P2P) tels que Freenet , Gnutella , BitTorrent et Napster , qui exploitaient les ressources distribuées sur Internet pour fournir une seule application utile. En particulier, ils ont profité de l'augmentation de la bande passante et de la capacité du disque dur pour fournir un service de partage de fichiers.

Ces systèmes différaient dans la manière dont ils localisaient les données proposées par leurs homologues. Napster, le premier système de diffusion de contenu P2P à grande échelle, nécessitait un serveur d'index central : chaque nœud, lors de sa connexion, envoyait une liste de fichiers détenus localement au serveur, qui effectuait des recherches et renvoyait les requêtes aux nœuds qui détenaient les résultats. Ce composant central rendait le système vulnérable aux attaques et aux poursuites judiciaires.

Gnutella et les réseaux similaires ont évolué vers un modèle de requêtes par inondation – en substance, chaque recherche aboutissait à la diffusion d’un message sur chaque machine du réseau. Tout en évitant un point de défaillance unique , cette méthode était nettement moins efficace que Napster. Les versions ultérieures des clients Gnutella ont évolué vers un modèle de requête dynamique qui a considérablement amélioré l’efficacité.

Freenet est entièrement distribué, mais utilise un routage heuristique basé sur des clés dans lequel chaque fichier est associé à une clé, et les fichiers avec des clés similaires ont tendance à se regrouper sur un ensemble de nœuds similaires. Les requêtes sont susceptibles d'être acheminées via le réseau vers un tel cluster sans avoir besoin de visiter de nombreux homologues. Cependant, Freenet ne garantit pas que les données seront trouvées.

Les tables de hachage distribuées utilisent un routage basé sur des clés plus structuré afin d'atteindre à la fois la décentralisation de Freenet et Gnutella, et l'efficacité et les résultats garantis de Napster. Un inconvénient est que, comme Freenet, les DHT ne prennent en charge directement que la recherche de correspondance exacte, plutôt que la recherche par mot-clé, bien que l'algorithme de routage de Freenet puisse être généralisé à tout type de clé où une opération de proximité peut être définie.

En 2001, quatre systèmes – CAN , Chord , Pastry et Tapestry – ont fait des DHT un sujet de recherche populaire. Un projet appelé Infrastructure for Resilient Internet Systems (Iris) a été financé par une subvention de 12 millions de dollars de la National Science Foundation des États-Unis en 2002. Les chercheurs comprenaient Sylvia Ratnasamy , Ion Stoica , Hari Balakrishnan et Scott Shenker . En dehors du monde universitaire, la technologie DHT a été adoptée comme composant de BitTorrent et dans des projets PlanetLab tels que le Coral Content Distribution Network.

Les DHT mettent généralement l’accent sur les propriétés suivantes :

• Autonomie et décentralisation : Les nœuds forment collectivement le système sans aucune coordination centrale.
• Tolérance aux pannes : Le système doit être fiable (dans un certain sens) même si des nœuds se joignent, se quittent et échouent en permanence.
• Évolutivité : le système doit fonctionner efficacement même avec des milliers ou des millions de nœuds.

Une technique clé utilisée pour atteindre ces objectifs est que chaque nœud doit se coordonner avec seulement quelques autres nœuds du système ‍ — le plus souvent, O (log n ) des n participants (voir ci-dessous) ‍ — de sorte que seule une quantité limitée de travail doit être effectuée pour chaque changement d'appartenance.

Certaines conceptions DHT cherchent à être sécurisées contre les participants malveillants et à permettre aux participants de rester anonymes , bien que cela soit moins courant que dans de nombreux autres systèmes peer-to-peer (en particulier le partage de fichiers ) ; voir P2P anonyme .

La structure d'un DHT peut être décomposée en plusieurs composants principaux. La base est un espace de clés abstrait, tel que l'ensemble de chaînes de 160 bits . Un schéma de partitionnement de l'espace de clés répartit la propriété de cet espace de clés entre les nœuds participants. Un réseau superposé connecte ensuite les nœuds, leur permettant de trouver le propriétaire de n'importe quelle clé donnée dans l'espace de clés.

Une fois ces composants en place, une utilisation typique de la DHT pour le stockage et la récupération peut se dérouler comme suit. Supposons que l'espace de clés soit l'ensemble de chaînes de 160 bits. Pour indexer un fichier avec un nom de fichier et des données donnés dans la DHT, le hachage SHA-1 de nom de fichier est généré, produisant une clé de 160 bits k , et un message put ( k,data ) est envoyé à tout nœud participant à la DHT. Le message est transmis d'un nœud à l'autre via le réseau de superposition jusqu'à ce qu'il atteigne le nœud unique responsable de la clé k comme spécifié par le partitionnement de l'espace de clés. Ce nœud stocke ensuite la clé et les données. Tout autre client peut ensuite récupérer le contenu du fichier en hachant à nouveau nom de fichier pour produire k et en demandant à tout nœud DHT de trouver les données associées à k avec un message get ( k ) . Le message sera à nouveau acheminé via la superposition vers le nœud responsable de k , qui répondra avec les données stockées .

Les composants du partitionnement de l'espace de clés et du réseau de superposition sont décrits ci-dessous dans le but de capturer les principales idées communes à la plupart des DHT ; de nombreuses conceptions diffèrent dans les détails.

La plupart des DHT utilisent une variante de hachage cohérent ou de hachage de rendez-vous pour associer les clés aux nœuds. Les deux algorithmes semblent avoir été conçus indépendamment et simultanément pour résoudre le problème de la table de hachage distribuée.

Le hachage cohérent et le hachage de rendez-vous ont tous deux la propriété essentielle selon laquelle la suppression ou l'ajout d'un nœud modifie uniquement l'ensemble des clés appartenant aux nœuds avec des ID adjacents et laisse tous les autres nœuds inchangés. Comparez cela à une table de hachage traditionnelle dans laquelle l'ajout ou la suppression d'un bucket entraîne le remappage de presque tout l'espace de clés. Étant donné que tout changement de propriété correspond généralement à un déplacement gourmand en bande passante des objets stockés dans la DHT d'un nœud à un autre, il est nécessaire de minimiser cette réorganisation pour prendre en charge efficacement des taux élevés de désabonnement (arrivée et défaillance du nœud).

Le hachage cohérent utilise une fonction qui définit une notion abstraite de la distance entre les clés et , qui n'est pas liée à la distance géographique ou à la latence du réseau . Chaque nœud se voit attribuer une clé unique appelée son identifiant (ID). Un nœud avec ID possède toutes les clés pour lesquelles est l'ID le plus proche, mesuré selon .

Par exemple, le DHT Chord utilise un hachage cohérent, qui traite les nœuds comme des points sur un cercle, et correspond à la distance parcourue dans le sens des aiguilles d'une montre autour du cercle de à . Ainsi, l'espace de clés circulaire est divisé en segments contigus dont les extrémités sont les identifiants de nœud. Si et sont deux identifiants adjacents, avec une distance dans le sens des aiguilles d'une montre plus courte de à , alors le nœud avec l'identifiant possède toutes les clés qui se situent entre et .

Dans le hachage de rendez-vous, également appelé hachage à poids aléatoire le plus élevé (HRW), tous les clients utilisent la même fonction de hachage (choisie à l'avance) pour associer une clé à l'un des n serveurs disponibles. Chaque client dispose de la même liste d'identifiants { S ₁ , S ₂ , ..., S _n } , un pour chaque serveur. Étant donnée une clé k , un client calcule n poids de hachage w ₁ = h ( S ₁ , k ), w ₂ = h ( S ₂ , k ), ..., w _n = h ( S _n , k ) . Le client associe cette clé au serveur correspondant au poids de hachage le plus élevé pour cette clé. Un serveur avec ID possède toutes les clés pour lesquelles le poids de hachage est supérieur au poids de hachage de tout autre nœud pour cette clé.

Le hachage préservant la localité garantit que des clés similaires sont attribuées à des objets similaires. Cela peut permettre une exécution plus efficace des requêtes de plage, cependant, contrairement à l'utilisation d'un hachage cohérent, il n'y a plus de garantie que les clés (et donc la charge) sont uniformément réparties de manière aléatoire sur l'espace de clés et les homologues participants. Les protocoles DHT tels que Self-Chord et Oscar traitent de ces problèmes. Self-Chord dissocie les clés d'objet des identifiants des homologues et trie les clés le long de l'anneau avec une approche statistique basée sur le paradigme de l'intelligence en essaim . Le tri garantit que des clés similaires sont stockées par les nœuds voisins et que les procédures de découverte, y compris les requêtes de plage , peuvent être effectuées en temps logarithmique. Oscar construit un réseau navigable de petit monde basé sur un échantillonnage aléatoire de marche garantissant également un temps de recherche logarithmique.

Chaque nœud conserve un ensemble de liens vers d'autres nœuds (ses voisins ou sa table de routage ). Ensemble, ces liens forment le réseau superposé. Un nœud choisit ses voisins selon une certaine structure, appelée topologie du réseau .

Toutes les topologies DHT partagent une variante de la propriété la plus essentielle : pour toute clé k , chaque nœud possède soit un identifiant de nœud qui possède k , soit un lien vers un nœud dont l'identifiant de nœud est plus proche de k , en termes de distance d'espace de clés définie ci-dessus. Il est alors facile d'acheminer un message vers le propriétaire de toute clé k en utilisant l' algorithme glouton suivant (qui n'est pas nécessairement optimal au niveau mondial) : à chaque étape, transférez le message au voisin dont l'identifiant est le plus proche de k . Lorsqu'il n'y a pas de voisin de ce type, nous devons alors être arrivés au nœud le plus proche, qui est le propriétaire de k tel que défini ci-dessus. Ce style de routage est parfois appelé routage basé sur les clés .

Au-delà de l'exactitude du routage de base, deux contraintes importantes sur la topologie sont de garantir que le nombre maximal de sauts dans n'importe quelle route (longueur de la route) est faible, afin que les requêtes soient traitées rapidement ; et que le nombre maximal de voisins de n'importe quel nœud ( degré maximal du nœud ) soit faible, afin que la charge de maintenance ne soit pas excessive. Bien entendu, avoir des routes plus courtes nécessite un degré maximal plus élevé . Voici quelques choix courants pour le degré maximal et la longueur de la route, où n est le nombre de nœuds dans la DHT, en utilisant la notation Big O :

Le choix le plus courant, degré/longueur de la route, n'est pas optimal en termes de compromis degré/longueur de la route, mais de telles topologies permettent généralement plus de flexibilité dans le choix des voisins. De nombreux DHT utilisent cette flexibilité pour choisir des voisins qui sont proches en termes de latence dans le réseau physique sous-jacent. En général, tous les DHT construisent des topologies de réseau navigables de type petit monde, qui font un compromis entre la longueur de la route et le degré du réseau.

La longueur maximale de la route est étroitement liée au diamètre : le nombre maximal de sauts dans tout chemin le plus court entre les nœuds. De toute évidence, la longueur de la route du pire des cas du réseau est au moins aussi grande que son diamètre, de sorte que les DHT sont limités par le compromis degré/diamètre qui est fondamental dans la théorie des graphes . La longueur de la route peut être supérieure au diamètre, car l'algorithme de routage gourmand peut ne pas trouver les chemins les plus courts.

Outre le routage, il existe de nombreux algorithmes qui exploitent la structure du réseau superposé pour envoyer un message à tous les nœuds, ou à un sous-ensemble de nœuds, dans un DHT. Ces algorithmes sont utilisés par les applications pour effectuer des multidiffusion superposées , des requêtes de plage ou pour collecter des statistiques. Deux systèmes basés sur cette approche sont Structella, qui implémente l'inondation et les marches aléatoires sur une superposition Pastry, et DQ-DHT, qui implémente un algorithme de recherche d'interrogation dynamique sur un réseau Chord.

En raison de la décentralisation, de la tolérance aux pannes et de l'évolutivité des DHT, ils sont intrinsèquement plus résistants face à un attaquant hostile qu'un système centralisé.

Des systèmes ouverts de stockage de données distribuées , robustes face à des attaques hostiles massives, sont réalisables.

Un système DHT soigneusement conçu pour avoir une tolérance aux pannes byzantines peut se défendre contre une faiblesse de sécurité, connue sous le nom d' attaque Sybil , qui affecte la plupart des conceptions DHT actuelles. Whanau est un DHT conçu pour résister aux attaques Sybil.

Petar Maymounkov, l'un des auteurs originaux de Kademlia , a proposé un moyen de contourner la faiblesse de l'attaque Sybil en incorporant des relations de confiance sociale dans la conception du système. Le nouveau système, dont le nom de code est Tonika ou également connu sous son nom de domaine 5ttt, est basé sur une conception d'algorithme connue sous le nom de « routage électrique » et co-écrite avec le mathématicien Jonathan Kelner. Maymounkov a maintenant entrepris un effort de mise en œuvre complet de ce nouveau système. Cependant, la recherche sur les défenses efficaces contre les attaques Sybil est généralement considérée comme une question ouverte, et une grande variété de défenses potentielles sont proposées chaque année lors des principales conférences de recherche sur la sécurité.

Les différences les plus notables rencontrées dans les cas pratiques d’implémentations DHT incluent au moins les suivantes :

• L'espace d'adressage est un paramètre de DHT. Plusieurs DHT réels utilisent un espace de clé de 128 bits ou 160 bits.
• Certains DHT du monde réel utilisent des fonctions de hachage autres que SHA-1 .
• Dans le monde réel, la clé k pourrait être un hachage du contenu d'un fichier plutôt qu'un hachage du nom d'un fichier pour fournir un stockage adressable par contenu , de sorte que le changement de nom du fichier n'empêche pas les utilisateurs de le trouver.
• Certains DHT peuvent également publier des objets de différents types. Par exemple, la clé k peut être l' ID du nœud et les données associées peuvent décrire comment contacter ce nœud. Cela permet la publication d'informations de présence et est souvent utilisé dans les applications de messagerie instantanée, etc. Dans le cas le plus simple, l'ID est simplement un nombre aléatoire qui est directement utilisé comme clé k (donc dans un DHT 160 bits, l'ID sera un nombre de 160 bits, généralement choisi au hasard). Dans certains DHT, la publication des ID des nœuds est également utilisée pour optimiser les opérations DHT.
• La redondance peut être ajoutée pour améliorer la fiabilité. La paire de clés (k, data) peut être stockée dans plusieurs nœuds correspondant à la clé. En général, plutôt que de sélectionner un seul nœud, les algorithmes DHT du monde réel sélectionnent i nœuds appropriés, i étant un paramètre spécifique à l'implémentation du DHT. Dans certaines conceptions DHT, les nœuds acceptent de gérer une certaine plage d'espace de clés, dont la taille peut être choisie de manière dynamique plutôt que codée en dur.
• Certaines DHT avancées comme Kademlia effectuent d'abord des recherches itératives via la DHT afin de sélectionner un ensemble de nœuds appropriés et d'envoyer des messages put(k, data) uniquement à ces nœuds, réduisant ainsi considérablement le trafic inutile, puisque les messages publiés ne sont envoyés qu'aux nœuds qui semblent adaptés au stockage de la clé k ; et les recherches itératives ne couvrent qu'un petit ensemble de nœuds plutôt que l'ensemble de la DHT, réduisant ainsi les transferts inutiles. Dans de telles DHT, le transfert de messages put(k, data) ne peut se produire que dans le cadre d'un algorithme d'auto-réparation : si un nœud cible reçoit un message put(k, data) , mais pense que k est hors de sa plage de traitement et qu'un nœud plus proche (en termes d'espace de clés DHT) est connu, le message est transmis à ce nœud. Sinon, les données sont indexées localement. Cela conduit à un comportement DHT quelque peu auto-équilibré. Bien entendu, un tel algorithme nécessite que les nœuds publient leurs données de présence dans la DHT afin que les recherches itératives puissent être effectuées.
• Étant donné que sur la plupart des machines, l'envoi de messages est beaucoup plus coûteux que l'accès à la table de hachage locale, il est logique de regrouper de nombreux messages concernant un nœud particulier dans un seul lot. En supposant que chaque nœud dispose d'un lot local composé d'au plus b opérations, la procédure de regroupement est la suivante. Chaque nœud trie d'abord son lot local par l'identifiant du nœud responsable de l'opération. En utilisant bucket sort , cela peut être fait en O(b + n) , où n est le nombre de nœuds dans la DHT. Lorsqu'il existe plusieurs opérations portant sur la même clé dans un lot, le lot est condensé avant d'être envoyé. Par exemple, plusieurs recherches de la même clé peuvent être réduites à une ou plusieurs incréments peuvent être réduits à une seule opération d'ajout. Cette réduction peut être mise en œuvre à l'aide d'une table de hachage locale temporaire. Enfin, les opérations sont envoyées aux nœuds respectifs.

• Apache Cassandra
• BATON Superposition
• Mainline DHT – DHT standard utilisé par BitTorrent (basé sur Kademlia tel que fourni par Khashmir)
• Réseau adressable par contenu (CAN)
• Accord
• Courrier
• Kademlia
• Pâtisserie
• Grille P
• Riak
• ScyllaDB
• Tapisserie
• TomP2P
• Voldemort

• BTDigg : moteur de recherche DHT BitTorrent
• Codeen : mise en cache Web
• Freenet : un réseau anonyme résistant à la censure
• GlusterFS : un système de fichiers distribué utilisé pour la virtualisation du stockage
• GNUnet : réseau de distribution de type Freenet incluant une implémentation DHT
• I2P : Un réseau peer-to-peer anonyme open source
• I2P-Bote : messagerie anonyme sécurisée sans serveur
• IPFS : un protocole de distribution hypermédia peer-to-peer adressable par contenu
• JXTA : plateforme P2P open source
• LBRY : Un protocole de partage de contenu basé sur la blockchain qui utilise un système DHT influencé par Kademlia pour la distribution de contenu
• Oracle Coherence : une grille de données en mémoire construite sur une implémentation Java DHT
• Perfect Dark : une application de partage de fichiers peer-to-peer venue du Japon
• Retroshare : un réseau d'amis à amis
• Jami : une plateforme de communication vocale, vidéo et chat préservant la confidentialité, basée sur un DHT de type Kademlia
• Tox : un système de messagerie instantanée destiné à remplacer Skype
• Twister : une plateforme de microblogging peer-to-peer
• YaCy : un moteur de recherche distribué