Exposé d'Algo P2P : Moteurs de recherches utilisant un système P2P
1. Quelques rappels
1.1. Sur les moteurs de recherche
Les moteurs de recherches actuels sont le plus souvent centralisés, utilisent des grilles ou grappes statiques pour l'indexation et la recherche.
Tous les moteurs de recherches sont composés de 4 éléments:
- Crawler:
- Un robot indépendant visitant les pages internets et suivant les liens contenus sur ces dernières.
- Analyseur:
- Analyse les pages explorées par le crawler et essaye d'en tirer des relations mot-URLs d'après certains critères de pertinence.
- Index:
- Un autre système autonome qui stocke les relations mot-URLs.
- Module de recherche:
- L'utilisateur propose des mots-clés, et la recherche se fait sur l'index.
Avantages:
- Le système a accès à l'ensemble de l'index d'une manière rapide pour faire ses calculs, ce qui "garantit" une certaine performance au système.
Inconvénients:
- Nécessite une infrastructure de type cluster, lourde et cher à entretenir.
- Pour qu'un site soit indexé (donc dans l'internet visible), il faut ou bien qu'il se soit déclaré en contactant le moteur de recherche, ou qu'un site déjà indexé possède un lien vers lui.
1.2. Sur les moteurs de recherche utilisant les technologies P2P
Avantages:
- Les mise à jour des pages sont rapidement intégrées au moteur de recherche
- Pas d'infrastructure lourde et chère à mettre en place, le coût est réduit et distribué sur la masse d'utilisateurs (utile lorsqu'on a pas de moyens (comme la communauté du logiciel libre)).
- Si une personne conçoit un site web et est un noeud du réseau, alors son site se trouve automatiquement indexé par le moteur de recherche (sans avoir à se déclarer d'une manière quelconque) : augmente la part de l'internet visible
Inconvénients:
- En est-ce réellement un, toutefois, il n'y a aucune possibilité de contrôler d'une manière globale le contenu de l'indexation ou de limiter son déploiement (ne plaît pas trop aux sociétés commerciales qui influencent le contenu de l'indexation afin de valoriser le plus offrant (dans certains cas), par contre plaît beaucoup à la communauté du logiciel libre...)
- On a accès a un ensemble local de pages, mais pas à toutes.
- Il existe des problèmes de sécurité, notamment concernant la vie privée.
- Le temps pris par une recherche est plus lent que sur un site de recherche classique.
Il y a alors plusieurs approches possible:
- crawler distribué/P2P
- indexeur centralisé/distribué/P2P
- moteur de recherche centralisé/distribué/P2P
Différence entre P2P et distribué, nous entendons par P2P un système n'ayant pas la possibilité d'avoir des noeuds n'étant que des clients, à la différence de distribué, qui permet à un ensemble de machines de faire le travail, et à un autre d'obtenir des précédentes le résultat de leurs recherches.
Problème: Les configurations de firewall empêche fréquemment de joindre les pairs.
2. Présentation de quelques moteurs de recherche P2P
- Grub (projet mort):
- Adresse: http://grub.looksmart.com/
- Crawler: Décentralisé, le but visé est de pouvoir visiter toutes les pages d'internet au moins une fois par jour.
- Index: Dans une BD centralisée sur les serveurs de Grub.
- Requêtes: Non-documenté.
- JXTA Search
- Origine: Sun (2001)
- Adresse: http://search.jxta.org/
- Services: P2P + DHT
- Hub/routeurs: P2P
- Engines: P2P
- Basé sur XML / Java.
- Multi-protocole: resolver, rendez-vous, etc.
- Apparemment c'est très généraliste, et permet de développer à peu près n'importe quoi sur des protos P2P. Donc pas spécifique aux moteurs de recherches.
- Odissea
- Adresse: http://cis.poly.edu/tr/tr-cis-2003-01.pdf
- Crawler: distribué
- Index: distribué (assez peu de redondance, nécessite un réseau stable)
- Requêtes: une API de recherche est fournie pour créer des clients, les requêtes sont envoyées aux pairs.
- Les cibles de ce type de système sont les serveurs web eux mêmes à prioris.
- Coopeer
- Adresse: http://ieeexplore.ieee.org/iel5/9202/29177/01316635.pdf
- C'est un système à la fois de moteur de recherche centralisé et un système de bookmark distribué, chacun peut ajouter des pages web mais surtout des documents qu'il a trouvés intéressants et les ajouter dans le système. C'est en fait un recueuil collaboratif d'informations.
- YaCy
2.1. Un "vrai" exemple: YaCy
http://www.yacy.net/yacy/
2.1.1 La structure
- un noeud :
- Un proxy : L'utilisateur doit configurer son navigateur préféré pour utiliser ce proxy (qui tourne en local). À travers le proxy, l'utilisateur alimente par sa propre navigation la liste des sites à visiter.
- Le moteur de recherche PLASMA :
- Va sur les URLs de la liste des sites à visiter.
- Analyse les pages : index leur contenu, alimente la liste des sites à visiter par le URLs présentes sur les pages visitées, transmet au système local de partage p2p les relations connues et ainsi indexées.
- Enregistre dans la base de données KELONDRO les relations.
- Le système d'echange p2p des index :
- Se charge de se connecter aux voisins.
- Maintient une liste des URLs parcourus par le noeud qu'il représente, la partage avec les autres noeuds.
- Transmet les requêtes de recherche à PLASMA, si ces dernières sont contenues dans l'ensemble des connaissances de son noeud local.
- Retransmet les requêtes qui ne correspondent pas à ces critères aux noeuds dont il pense savoir qu'ils pourront y répondre.
- Maintient une base de connaissance (dans KELONDRO) de ce que savent les noeuds voisins.
- Une base de données : Chargée de stocker les index, et les informations sur les voisins.
2.1.2 Plus en détail
- Communication entre les noeuds
- Les communications sont chiffrées entre les pairs.
- La connexion initiale au réseau se fait via une seed-list.
- La découverte de nouveaux pairs se fait de proche en proche : Lorsqu'un noeud se connecte à un autre, ils s'échangent les coordonnées de leurs voisins les plus récemment connectés.
- Equité
- La loi des P2P est respectée : tous les pairs doivent contribuer pour pouvoir faire une recherche.
- La contribution doit se faire sur la navigation, le cache et l'indexage.
- Stabilité
- Les index de mots, voyagent en permanence sur le réseau et sont dupliqués.
- Sécurité/Résistance aux attaques
- attaques ciblées :
- description : attaque d'un noeud ou d'un groupe de noeuds restraint ciblé.
- réponse :
- Rien n'est centralisé, c'est un p2p total, donc une attaque ciblée sur une seule machine fait autant de dommage qu'une seule panne.
- Par contre réussir à obtenir l'ensemble des pairs ayant par exemple un mot ou un contenu, pourrait permettre d'invalider ce mot.
- attaques de falsifications :
- description : attaque visant à introduire de mauvaises/fausses informations dans le moteur de recherche, ou de falsifier les résultats.
- réponse :
- Après la diffusion de la table d'index falsifié, cette dernière au bout d'un moment sera reconstruite par les pairs "contaminés", Donc l'attaque ne pourra fonctionner que très peu de temps.
- attaques par "concentration" (genre de spoofing):
- description : Un noeud essaie d'être le centre d'information du réseaux, afin de contrôler l'information.
- réponse : Il n'y a pas possibilité de faire cela car le réseaux n'attribut pas de priorité à des noeuds en particulier. La liste des noeuds est maintenue en fonction des nouvelles connections.
- Qualité des résultats
- On peut affiner les recherches en fonction de plusieurs critères: Entropie, Date, Position dans le texte, Word Hit Count, Taille du nom de domaine, Taille de l'url, Taille des composants de l'url, Taille de la description, nombre de composants dans la description, La requête apparait dans l'URL, la requête apparait dans la description ...
- Aucune censure globale ne peut être appliquée (problème éthique, politique ou pas...).
- Efficacité
- Crawler :
- L'action est totalement distribuée, ce qui implique que différents pairs peuvent visiter et analyser les mêmes URLs sans coordinations.
- Toutefois le crawler évite de visiter les pages à jour dans l'index local (ou les index fournis par les voisins).
- L'analyse des mêmes URLs par différents pairs, n'est pas un problème en soit, étant donné qu'elle permet aussi d'obtenir la redondance des index qui est voulu pour la résistance aux pannes.
- La redondance intrinsèque permet encore de vérifier la cohérence des informations entre différents pairs et permet d'éviter les biais ponctuels au niveau d'un pair.
- Les URLs d'origines sont définies à la main ou sont définies par l'intermédiaire d'un proxy (local, enregistrant la navigation de l'utilisateur).
- Le réseau sera donc dans un premier temps orienté vers les intérêts des utilisateurs. Le graphe en résultant finira par au moins inclure le graphe recouvert par google, puis qu'il utilise en soit le même principe de proposition d'URLs.
- Indexer :
- Stockage limité (par l'utilisateur et de fait)
- Lorsqu'un pair fait des analyses, il transmet à ses voisins les mots qu'il vient d'indexer.
- Régulièrement, les pairs transmettent des copies partielles de leur index à une partie de leurs voisins. (robustesse aux pannes)
- search engine :
- Une requête est envoyé par mot clé.
- Si on a le mot clé dans l'index local des mots, alors on route la requête vers les pairs pointés par le mots clé.
- Sinon on propage la requête par inondation sur les voisins.
- Scalabilité
- Pour l'instant, le projet est expérimental, et non réellement déployé pour savoir, s'il est capable de tenir à l'échelle.
- Toutefois, vous pouvez l'installer sur votre machine, afin d'en vérifier la robustesse sur une plus grande échelle.
- Implémentation
- Le choix du langage s'est porté sur java, en raison de sa facilité de programmation et de la priorité accordée à l'aspect algorithmique. Pour l'instant, la latence entre les pairs, peut permettre de concidérer le temps d'exécution comme n'étant pas réellement prépondérant.
- Toutefois à terme, ce système a pour objectif de tourner en permanence sur les pairs, et donc consommer le moins possible leurs ressources (mémoire et processeur) devra être une priorité, afin que les utilisateurs ne rechignent pas à les laisser allumés (ou simplement à les installer).
Références