YACY - L'architecture d'un moteur de recherche P2P
Publié le 29 avril 2005

YACY est un nouveau moteur de recherche libre en P2P auquel je contribue.

Architecture

YACY se compose principalement de quatre parties : Le protocole d'échange de l'index en p2p basé sur http ; un crawler/ indexeur ; un proxy/cache qui est non seulement un outil simple mais également un fournisseur de données afin que le pear indexant la machine et la machine intégrée à la base de données rendent l'installation et la maintenance de yacy très faciles.

(GIF)

Tous les modules de cette architecture sont inclus dans la distribution de YACY. Le moteur de recherche de YACY peut être manipulé grâce au serveur http intégré.

Algorithmes

Pour notre architecture du logiciel nous soulignons que nous cherchons à garantir la performance maximale. La bonne combinaison entre la structure et l'algorithme est la clé pour la conception d'une application performante. Nous rejettons le mythe que le language Java n'est pas appropriée pour un logiciel temp-réel ; au contraire, nous croyons que Java avec ses structures de données propres et dynamiques sont plus notamment qualifiées pour mettre des algorithmes extrêmement complexes en application.

HTTP transparent et proxy HTTPS avec cache

L'implémentation du proxy fournit un système de passation rapide de contenu, alors que chaque fichier lu par le proxy du serveur cible l'est en PIPE jusqu'au client (stream) pendant que le flux est copié en mémoire cache pour un traitement ultérieur. Cela assure que le mode proxy est extrêmement rapide et n'interromp pas la navigation. Pendant que le proxy est en pause, il traite sa mémoire cache pour effectuer l'indexation et le stockage dans un fichier en local. Chaque en-tête HTTP passé avec le fichier est stocké en base et est réutilisé plus tard ou lorsque une demande provenant du cache apparaît. Le proxy agit en priorité maximum au dessus des autres processus tout comme la gestion du cache et les fonctions d'indexation.

Implémentation efficiente de la base de donnée

Nous avons implémenté un arbre AVL stocké dans un fichier selon un accès direct. Les nÅ“uds peuvent être alloués et libérés dynamiquement et une liste de nodes non utilisés est maintenue. Pour l'algorithme de recherche intitulé PLASMA, une liste ordonnée pour accéder aux résultats est nécessaire. Cependant, nous avons besoin d'un mécanisme d'indexation qui stocke l'index selon une méthode ordonnée. La base de donnée supporte ce genre d'accès, et la base de donnée résultante est stockée dans un simple fichier. La base de donnée n'a pas besoin d'être initialisée ou d'être maintenue par un administrateur. Elle se réorganise toute seule. La propriété AVL assure un maximum de performances dans l'algorithme de tri. N'importe quelle base peut grossir à un nombre inimaginable d'enregistrements : avec un milliards d'enregistrements, une requête de base de donnée a besoin théoriquement d'un maximum de seulement 44 comparaisons.

Système d'indexation sophistiqué

L'indexation des pages est réalisé grâce à la création d'un index inversé : chaque page est "découpée", les mots sont extraits et pour chaque mot une table est maintenue. Les tables sont gérées dans un fichier de type "table de hachage", donc l'accès à un mot est extrêmement rapide, résultant en une recherche très rapide. Les conjonctions de mots sont trouvés facilement, parce que les résultats de la recherche pour chaque mot sont ordonnés et peuvent être énumérés par paires. En termes de traitement : l'ordre de l'accès à la recherche jusqu'au mot est O (log ). La rapidité d'accès est toujours constante étant donné que la structure de données fournit un résultat "pré-calculé". Cela signifie que la vitesse résultante est indépendante du nombre de pages indexées ! Il réduit un peu pour la notation des pages et est multiplié par le nombre de mots qui sont recherchés simultanément. Cela veut dire que l'effort de recherche à fournir pour n mots est O (n * log w). On ne peut pas faire mieux (considérez que n est toujours petit, parce que vous cherchez rarement plus de 10 mots.

Moteur de recherche parralèle massive

Cette technologie est la force derrière l'implémentation de YACY. Une DHT (Table de Hachage Distribuée) - comme technique sera utilisée pour publier le cache du mot. L'idée est que les mots indexés voyagent autour des peers avant qu'une demande de recherche arrive sur un index spécifique. La recherche d'un mot spécifique peut être obtenue dans le traitement du PEER en pointant directement sur le PEER qui héberge l'index. Pas de perte de temps car les requêtes sont critiques en termes de temps (l'internaute ne souhaite pas attendre longtemps d'habitude). La redondance doit être implémentée, également, pour pallier à la disparition de PEER. La privacité est assurée car aucun PEER peut connaître quel index de mots est stocké sur sa machine, mis à jour et transféré parce que les mots sont stockés dans une table de hachage. Les erreurs de saisie de requête sont régulées par les lois P2P de l'émetteur/récepteur : chaque PEER doit contribuer dans le processus "crawl/proxy et indexation" avant qu'il soit autorisé à chercher.

Vie privée

Partager l'index avec d'autres utilisateurs peut vous concerner à propos de la protection de votre vie privée. Nous avons fait de gros efforts pour conserver et sécuriser votre privacité :

Index privé et mouvement d'index

Votre index local contient non seulement de l'information que vous avez créé en surfant sur la toile, mais aussi les entrées d'autres PEERS. Les fichiers d'index voyagent à travers les PEERS pour former et distribuer la table de hachage. Par ailleurs, personne ne peut se targuer que l'information qui est fournie par votre PEER a aussi été récupérée par votre PEER et aussi par votre utilisation personnelle d'internet. En fait, c'est quasiment l'information qui peut être trouvée dans votre PEER qui a été créé par vous car le processus de recherche cible seulement les PEERS. C'est à cause du mouvement d'index qui forme la table hachage distribuée. Durant la phase de test, tout les indexs sur votre PEER sont accessibles. La prochaine version de production de YACY contraindra les recherches aux entrées d'index de votre PEER qui ont été créé par les autres PEERS. Ce qui assurera un surf complètement protégé.

Stockage d'Index and Responsabilité du contenu

Les mots qui sont stockés dans votre index local le sont grâce à une table de hachage. Cela signifie qu'aucun mot n'est stocké mais seulement son code. Vous ne trouverez aucun mot indexé en texte pur. Vous ne pouvez pas non plus transformer le code en mot à nouveau. Cela veut dire que vous ne pouvez pas savoir quels mots sont stockés dans votre système. L'effet positif est que vous ne pouvez être tenu pour responsable des mots qui sont stockés dans votre PEER. Mais si vous souhaitez refuser le stockage de certains mots, vous pouvez les mettres dans la liste "bleue" (dans le fichier httpProxy.bluelist).

Cryptage de la communication PEER

L'information qui est envoyée d'un PEER à l'autre est cryptée. Cela signifie qu'aucune donnée texte ne circule sur le réseau. Les espions de réseaux ne peuvent voir le contenu échangé. Nous avons également implémenté une méthode de cryptage, où une clé temporaire créée par le PEER d'origine de la requête est utilisée pour crypter la réponse (non encore actif dans la release de test - codage base64 en atendant).

Restrictions d'accès

Le proxy contient un contrôle d'accès en 2 étapes : un filtrage de l'IP et un compte utilisateur peut être configuré pour accéder au proxy. Le paramétrage par défaut interdit l'accès à votre proxy à partir d'internet mais permet son usage à partir d'un intranet. Le proxy et sa sécurité sont configurés en utilisant un serveur web pour rendre les pages ; l'accès à ce service peut aussi être restreint en filtrant les IP ou avec un compte utilisateur.

Voici une présentation (article traduit automatiquement de l'anglais) de ce système.