É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

Fondée sur les principes de l’économie du savoir en 1999, Savoir-faire Linux a développé une expertise unique dans les technologies de l’information, l’ingénierie des logiciels libres et à code ouvert, le développement du noyau Linux et les objets connectés. Depuis, l’entreprise a accompagné de nombreuses sociétés à répondre à l’évolution constante de leurs systèmes d’information.
En tant qu'entreprise de taille moyenne dotée d'équipes multidisciplinaires d'ingénieurs basées à Montréal, Québec, Lyon et Rennes, Savoir-faire Linux a offert un large panel de services, lors de ces 19 dernières années, à plus de 500 organismes, dont des institutions gouvernementales, des grandes agences internationales, des géants de l'industrie et des PME / PMI. Déployant les meilleurs outils libres et à code ouvert couplés à son expertise, Savoir-faire Linux vise à améliorer les systèmes informatiques de ses clients et à accélérer leurs processus d'innovation. Son ingénierie de qualité, ses performances fiables et son excellent service client lui a valu plusieurs reconnaissances dont ISO 9001, ISO 14001, Silver Member de la Linux Foundation, Platinum Partner de Liferay et Advanced Partner de Red Hat.

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

Les commentaires sont fermés.