Épisode 1 : Les arbres préfixes (PHT) comme moteur de recherche

OpenDHT est un système distribué public permettant d’indexer des données sous la forme de paire clé – valeur. La clé représente un identifiant unique et la valeur est le contenant de la donnée.

OpenDHT peut stocker des valeurs tout en répartissant les données sur l’ensemble des nœuds du réseau. La librairie est basée sur l’algorithme « Kademlia » introduit par Maymounkov et Mazières.

technology-x-binary-and-backgrounds-541917

OpenDHT innove en implémentant de nouvelles fonctionnalités comme listen : une opération de notification à la réception de nouvelles valeurs annoncées sur le réseau. Toutefois, les tables de hachage distribuées (DHT) offrent la possibilité d’effectuer uniquement des recherches exactes, sur une clef-précise. Or, l’un des principaux problèmes auxquels le logiciel Ring fait face est la recherche d’utilisateurs. Voici pourquoi l’équipe Ring et une équipe de l’UQAM ont travaillé à la recherche d’une solution pour ce problème.

Le solution utilisée: La PHT ou Prefix Hash Tree

capture2

La solution est inspirée d’un article intitulé Prefix Hash Tree : An Indexing Data Structure over Distributed hash Tables. L’objectif est de créer un arbre dont la structure représente l’information qu’on y ajoute. Les feuilles stockent les clés et les liens de l’arbre servent au routage logique. Le tout repose sur le réseau distribué de la DHT. Cette structure permet une recherche basée sur des mots clefs.

On peut également noter la possibilité de faire exister plusieurs arbres préfixes sur un même réseau. Ce qui servirait par la suite à indexer d’autres données comme des profils Ring ou des services tiers. Il est à noter que l’utilisation du PHT n’est soumise à aucune limitation. En effet, dans un contexte différent, on peut très bien imaginer l’indexation de blogs, d’appareils connectés (domotique), etc.

Cas pratique sur la PHT

Un utilisateur A souhaite rechercher un utilisateur B dont l’identifiant Ring est le suivant : ring:9ad22cac841bed877b8d5f65d4fb2d44bda7fdc4. L’utilisateur A pourra utiliser le PHT pour rechercher l’utilisateur B grâce à des mots clefs comme son prénom, son nom, sa ville de résidence, etc.

À suivre….épisode 2 : l’optimisation des requêtes sur la PHT! 

Publié par

Savoir-faire Linux

Savoir-faire Linux est le chef de file de l’informatique à code ouvert sous licence libre au Québec et au Canada. Moteur d’une économie nouvelle fondée sur le savoir, Savoir-faire Linux développe depuis 1999 une expertise exceptionnelle qu’elle met au service des entreprises et des organisations publiques afin de répondre aux défis d’évolution de leurs systèmes d’information. Forte d’une équipe multidisciplinaire de plus de 145 experts de 24 nationalités différentes dans 5 villes et sur 2 continents, Savoir-faire Linux fournit des services à plus de 500 organisations à travers le monde.

Une réflexion au sujet de « Épisode 1 : Les arbres préfixes (PHT) comme moteur de recherche »

Les commentaires sont fermés.