Des centaines de pages aspirées chaque seconde, des files d'attente, un tas de priorités, des empreintes numériques... Voici, concrètement, comment un robot d'exploration parcourt le web sans se perdre (ni fâcher les serveurs).
Le web crawling, ou l'art d'aspirer le web
Le web crawling désigne le processus par lequel un moteur de recherche va chercher les pages du web pour les indexer. L'objectif est double : récolter vite et efficacement le plus grand nombre de pages utiles possible, et récupérer au passage la structure de liens qui les relie entre elles.
Le principe de base est presque enfantin. Le robot part d'un ensemble d'URLs de départ (le "seed set"), il en choisit une, télécharge la page correspondante, puis l'analyse pour en extraire deux choses : le texte, qui part vers l'indexeur, et les liens, qui pointent vers d'autres URLs. Ces nouvelles URLs sont versées dans une frontière d'URLs, c'est-à-dire l'ensemble des adresses dont la page n'a pas encore été récupérée.
Au fur et à mesure des téléchargements, les URLs traitées sortent de la frontière. Vu de loin, tout cela revient à parcourir le graphe du web de proche en proche. Et en exploration continue, l'URL d'une page déjà récupérée est réinjectée dans la frontière pour être visitée à nouveau plus tard, afin que l'index reste à jour.
Pourquoi est-ce essentiel ? Sans cette collecte, pas d'index, donc pas de résultats de recherche. Et l'échelle donne le vertige : récupérer un milliard de pages en un mois d'exploration (une petite fraction du web statique) suppose déjà de télécharger plusieurs centaines de pages par seconde.
Un web bâti sans chef d'orchestre : les vrais obstacles
Le web n'a pas été conçu par une équipe centralisée avec un cahier des charges. Il a été publié par des millions de personnes sans aucune coordination, dans des dizaines de langues et des milliers de dialectes, avec des styles, des structures et des qualités très inégales. Certaines pages, y compris des pages d'accueil de grandes entreprises, ont même été entièrement composées d'images... donc sans un mot de texte indexable.
Premier piège concret : les spider traps. Ce sont des serveurs qui génèrent un nombre infini de pages et enferment le robot dans un domaine, où il tourne indéfiniment. Toutes ne sont pas malveillantes : certaines viennent simplement d'un site mal développé. D'autres sont volontaires, montées par des spammeurs pour faire indexer des milliers de pages de leur site.
Deuxième piège : l'infinité des pages dynamiques. Une adresse fantaisiste ajoutée derrière un nom de domaine peut renvoyer une page HTML valide (le fameux "soft 404") plutôt qu'une erreur. Impossible, dans ces conditions, de raisonner sérieusement sur "la fraction du web indexée".
Troisième obstacle : la duplication. Selon certaines estimations, jusqu'à 40 % des pages du web sont des copies d'autres pages, parfois pour de bonnes raisons (miroirs, redondance, fiabilité d'accès). Ajoutez à cela une grande proportion de pages de faible utilité pour répondre aux requêtes, et vous comprenez pourquoi un crawler doit être sélectif, robuste et poli à la fois.
Crawler, spider, robot : le composant qui alimente tout le reste
Dans l'architecture d'un moteur de recherche, le crawler (aussi appelé spider) est le module qui va chercher la matière première. On attend de lui deux qualités non négociables. La robustesse d'abord : il doit résister aux pièges à robots décrits plus haut. La politesse ensuite : les serveurs web imposent des politiques implicites et explicites sur le rythme auquel on peut les visiter, et ces règles doivent être respectées.
Viennent ensuite les qualités très fortement souhaitables. Être distribué (fonctionner sur plusieurs machines) et scalable (pouvoir accélérer le rythme en ajoutant machines et bande passante). Être performant, c'est-à-dire économe en processeur, en stockage et en bande passante. Privilégier la qualité, en allant chercher d'abord les pages utiles, puisqu'une part importante du web n'apporte rien aux requêtes des utilisateurs.
Deux derniers critères comptent beaucoup : la fraîcheur, avec un fonctionnement en continu qui revisite chaque page à une fréquence proche de son propre taux de modification, et l'extensibilité, pour absorber de nouveaux formats de données ou de nouveaux protocoles de récupération. D'où l'exigence d'une architecture modulaire.
Nota Bene : même pour un projet artisanal, trois règles minimales s'imposent. Une seule connexion ouverte à la fois vers un hôte donné, quelques secondes d'attente entre deux requêtes successives au même hôte, et le respect des restrictions de politesse déclarées par le site.
© BravRez IA
Sous le capot : les modules d'un crawler distribué
Concrètement, l'exploration s'appuie sur cinq briques qui s'emboîtent. La frontière d'URLs, qui stocke les adresses restant à visiter. Un module de résolution DNS, qui détermine le serveur d'où récupérer la page. Un module de récupération (fetch) qui utilise le protocole http. Un module d'analyse qui extrait le texte et les liens. Enfin un module d'élimination des doublons, qui vérifie si un lien extrait est déjà dans la frontière ou vient d'être visité.
Le travail est réalisé par un nombre de threads allant de un à plusieurs centaines, chacun bouclant sur ce cycle logique. Ces threads peuvent tourner dans un seul processus ou être répartis entre plusieurs processus sur des noeuds différents. Le fil de vie d'une URL est toujours le même : on la sort de la frontière, on télécharge la page dans un stockage temporaire, on l'analyse, le texte (avec ses informations de balisage, les termes en gras par exemple) part vers l'indexeur, les liens et leurs textes d'ancre aussi, puis chaque lien extrait subit une série de tests avant d'être ajouté ou non à la frontière.
Pour distribuer tout cela, on réplique ce flux sur chaque noeud avec une différence essentielle : après le filtre d'URLs, un répartiteur d'hôtes (host splitter) envoie chaque URL survivante au noeud responsable de son hôte. La partition des hôtes entre noeuds peut se faire par une fonction de hachage ou par une politique plus fine (un noeud en Europe pour les domaines européens, par exemple - même si ce n'est pas fiable, les routes des paquets ne reflétant pas toujours la géographie).
Deux détails d'ingénierie méritent d'être connus. La résolution DNS est un goulot d'étranglement notoire : elle peut demander plusieurs allers-retours et des secondes entières, ce qui ruine l'objectif de centaines de pages par seconde. On la met donc en cache, et la plupart des crawlers implémentent leur propre résolveur, où un thread envoie sa requête puis attend un temps donné, tandis qu'un thread dédié écoute les réponses sur le port DNS standard (le port 53) et réveille le demandeur. En cas d'échec, on retente environ cinq fois avec une attente qui croît de façon exponentielle, d'une seconde à environ quatre-vingt-dix secondes, car certains noms mettent des dizaines de secondes à se résoudre.
Enfin, un thread de maintenance dort la plupart du temps, se réveille toutes les quelques secondes pour journaliser les statistiques (URLs explorées, taille de la frontière), décider d'arrêter l'exploration, et toutes les quelques heures réaliser un checkpoint : un instantané de l'état du crawler écrit sur disque, pour redémarrer au dernier point de contrôle en cas de panne catastrophique.
La frontière d'URLs : le carnet d'adresses à visiter
La frontière d'URLs reçoit les adresses fournies par son propre processus d'exploration (ou par le répartiteur d'hôtes d'un autre noeud), les conserve, et les restitue dans un certain ordre dès qu'un thread réclame du travail. Toute l'intelligence du crawler tient dans cet ordre.
Deux contraintes le gouvernent. D'abord la priorité : les pages de bonne qualité qui changent souvent doivent être revisitées souvent. La priorité d'une page est donc fonction à la fois de son taux de changement et de sa qualité estimée - la combinaison est indispensable, car un grand nombre de pages de spam changent intégralement à chaque visite.
Ensuite la politesse : il faut éviter d'enchaîner les requêtes vers un même hôte dans un court laps de temps. Le risque est élevé à cause d'une forme de localité de référence, beaucoup de liens d'une page pointant vers d'autres pages du même hôte. Une frontière implémentée comme une simple file de priorité provoquerait donc des rafales de requêtes vers un seul serveur, même si l'on interdit à plus d'un thread de télécharger simultanément depuis cet hôte.
La solution retenue est une structure à deux étages : un ensemble de F files frontales qui gèrent la priorité, et un ensemble de B files arrière qui gèrent la politesse. Nota Bene : toutes ces files sont FIFO, c'est-à-dire "premier entré, premier sorti". Et quand la frontière devient trop volumineuse pour tenir en mémoire (cas courant à l'échelle du web), on la laisse résider majoritairement sur disque, en gardant une portion de chaque file en mémoire, réalimentée depuis le disque à mesure qu'elle se vide.
Les files frontales : qui passe devant ?
Quand une URL entre dans la frontière, elle rencontre d'abord un module de priorisation. Celui-ci lui attribue une priorité entière i comprise entre 1 et F, en fonction de son historique de récupération, notamment du rythme auquel la page a changé entre les explorations précédentes.
Le raisonnement est simple : un document qui a montré des changements fréquents reçoit une priorité plus élevée. D'autres heuristiques peuvent être explicites et dépendre de l'application : les URLs venant de services d'actualités, par exemple, peuvent recevoir systématiquement la priorité maximale.
Once sa priorité i attribuée, l'URL est simplement ajoutée à la fin de la i-ème file frontale. Rien de plus. C'est le nombre de files frontales, combiné à la politique d'attribution des priorités et à la manière de choisir dans quelle file puiser, qui détermine les propriétés de priorisation que l'on souhaite obtenir dans le système.
Les files arrière : un hôte, une file
Chaque file arrière respecte deux invariants stricts. Premier invariant : elle n'est jamais vide pendant que l'exploration est en cours. Second invariant : elle ne contient que des URLs provenant d'un seul et même hôte (on suppose évidemment que le nombre d'hôtes dépasse très largement B).
Le mécanisme de réapprovisionnement est le coeur du dispositif. Après avoir téléchargé une URL, le thread vérifie si la file arrière j qu'il vient de servir est vide. Si oui, il choisit une file frontale et en extrait l'URL de tête, appelons-la v. Le choix de la file frontale est biaisé (généralement par un tirage aléatoire pondéré) vers les files de priorité élevée, ce qui garantit que les URLs prioritaires descendent plus vite vers les files arrière.
On examine alors v : existe-t-il déjà une file arrière dédiée à son hôte ? Si oui, v y est ajoutée, et on repart vers les files frontales chercher une autre candidate pour remplir la file j restée vide. Sinon, v ouvre la file j, qui devient la file de son hôte. Le processus se répète jusqu'à ce que j soit de nouveau non vide.
Combien de files arrière faut-il ? Ce nombre détermine notre capacité à garder tous les threads occupés tout en respectant la politesse. Une règle empirique donne un ordre d'idée solide : environ trois fois plus de files arrière que de threads d'exploration.
La table hôtes-vers-files : le petit annuaire indispensable
Puisque chaque file arrière est réservée à un hôte unique, il faut pouvoir répondre très vite à la question "cet hôte a-t-il déjà une file ?". C'est le rôle d'une table auxiliaire T, qui maintient la correspondance entre les hôtes et les numéros de files arrière.
Dans la pratique, cette table ressemble à un annuaire minimaliste à deux colonnes. Une ligne par hôte, avec en face le numéro de sa file :
- stanford.edu, file arrière 23
- microsoft.com, file arrière 47
- acm.org, file arrière 12
Un point de vigilance : à chaque fois qu'une file arrière se vide et est réapprovisionnée depuis une file frontale, la table T doit être mise à jour en conséquence. Sans cela, l'invariant "une file, un hôte" se casse, et avec lui toute la garantie de politesse du crawler.
Politesse : le tas qui dit "pas avant telle heure"
Savoir quelle file appartient à quel hôte ne suffit pas : il faut aussi savoir quand on a le droit de recontacter cet hôte. Pour cela, on maintient un tas (une structure de priorité) comportant une entrée par file arrière. Cette entrée contient le temps te, la date la plus proche à laquelle l'hôte correspondant à cette file peut être sollicité de nouveau.
Le déroulé côté thread est très mécanique. Le thread qui réclame une URL extrait la racine de ce tas, et si nécessaire attend jusqu'à l'instant te qu'elle indique. Il prend ensuite l'URL u en tête de la file arrière j associée à cette racine, et va la télécharger.
Après le téléchargement (et après le réapprovisionnement de j si elle s'est vidée), le thread réinsère dans le tas une entrée pour j, avec un nouveau te calculé à partir des propriétés de la dernière URL récupérée : moment du dernier contact avec l'hôte, durée du dernier téléchargement. La règle heuristique classique consiste à insérer entre deux requêtes un intervalle d'un ordre de grandeur supérieur à la durée du dernier fetch. En pratique, on prend souvent l'heure courante plus dix fois la durée du dernier téléchargement.
Résultat : trois garanties tenues simultanément. Une seule connexion ouverte à la fois par hôte, quelques secondes d'attente entre deux requêtes vers un même hôte, et une exploration préférentielle des pages prioritaires.
Repérer les copies : empreintes, puis shingles
Avant d'ajouter un lien à la frontière, le thread vérifie si une page au contenu identique n'a pas déjà été vue à une autre adresse. L'implémentation la plus simple utilise une empreinte (fingerprint), par exemple une somme de contrôle ou un condensé de 64 bits des caractères de la page, stockée dans un magasin dédié. Si deux empreintes coïncident, on compare les pages et on déclare l'une comme copie de l'autre.
Problème : cette approche rate complètement le phénomène de quasi-duplication. Deux pages peuvent être identiques à quelques caractères près (une date de dernière modification, par exemple) et devraient malgré tout être traitées comme une seule. C'est là qu'intervient le shingling. Pour un entier k et une séquence de mots d'un document, les k-shingles sont l'ensemble de toutes les suites de k mots consécutifs. Sur le texte "a rose is a rose is a rose", les 4-shingles (k = 4 est une valeur typique pour détecter les quasi-doublons sur le web) sont : "a rose is a", "rose is a rose" et "is a rose is".
Deux documents sont considérés comme quasi-identiques si leurs ensembles de shingles se recouvrent fortement. On mesure ce recouvrement par le coefficient de Jaccard, soit la taille de l'intersection divisée par la taille de l'union des deux ensembles, et on fixe un seuil (0,9 par exemple) au-delà duquel on n'indexe qu'une seule copie. Mais comparer toutes les paires de documents est impensable à l'échelle du milliard de pages.
La parade est probabiliste et élégante. On hache chaque shingle sur un large espace de 64 bits, on applique une permutation aléatoire à ces valeurs, et on retient la plus petite valeur permutée pour chaque document. La probabilité que deux documents partagent ce minimum est exactement égale à leur coefficient de Jaccard. On répète l'opération avec 200 permutations indépendantes : les 200 valeurs obtenues forment le sketch du document, et le recouvrement des sketches divisé par 200 estime le Jaccard.
Reste à assembler tout cela sans exploser en calculs quadratiques. On commence par éliminer les copies strictement identiques grâce aux empreintes, on retire du calcul les balises HTML courantes et les entiers (qui ne disent rien sur la duplication), puis on trie la liste des valeurs de sketch avec leur document pour générer, pour chaque paire de documents partageant au moins une valeur, un compteur de valeurs communes. Avec un seuil de 80 %, il faut au moins 160 valeurs partagées sur 200. Les paires retenues sont regroupées par un algorithme d'union-find en "grappes syntaxiques" de quasi-doublons. Astuce supplémentaire pour économiser de l'espace : trier les valeurs du sketch puis les "shingler" à leur tour, ce qui donne des super-shingles - si deux documents n'ont aucun super-shingle en commun, on ne calcule même pas leur recouvrement précis.
Attention, une subtilité en mode distribué : contrairement aux URLs, les empreintes et shingles ne peuvent pas être répartis par nom d'hôte, puisque rien n'empêche le même contenu d'apparaître sur des serveurs différents. On les partitionne donc selon une propriété de l'empreinte elle-même (par exemple l'empreinte modulo le nombre de noeuds), ce qui transforme la plupart des tests "contenu déjà vu ?" en appels distants. Et comme il n'existe pas d'empreintes "populaires", mettre en cache les plus fréquentes ne sert à rien.
Le filtre d'URLs : inclure, exclure, normaliser
Chaque lien extrait passe ensuite par un filtre d'URLs, qui décide s'il mérite d'entrer dans la frontière. Le principe est celui d'une série de tests, exclusifs ou inclusifs selon le besoin. Une exploration peut par exemple vouloir écarter certains domaines : le test se contente alors de rejeter toute URL appartenant au domaine .com. À l'inverse, un test inclusif ne garde que les URLs répondant à un critère donné (un domaine, un site, un type de chemin).
Vient ensuite une étape trop souvent négligée : la normalisation. Le codage HTML d'un lien indique très souvent la cible de façon relative à la page qui le contient. Un lien écrit sous la forme href="/wiki/Wikipedia:General disclaimer" dans une page d'un site pointe en réalité vers l'adresse absolue complète du site suivie de ce chemin. Sans reconstruction de l'URL absolue, le robot ne peut tout simplement pas la télécharger, et pire, il risque de traiter comme distinctes des adresses identiques.
Enfin, l'URL subit le test d'élimination des doublons : si elle figure déjà dans la frontière ou (dans le cas d'une exploration non continue) si elle a déjà été explorée, on ne l'ajoute pas. Si elle passe, elle reçoit sa priorité et rejoint la file frontale correspondante.
Petit détail d'architecture qui a son importance dans un système distribué : le répartiteur d'hôtes est placé après le filtre d'URLs, et sa sortie alimente le module d'élimination des URLs dupliquées de chaque autre noeud. Chaque noeud ne voit ainsi que les URLs des hôtes dont il a la charge.
robots.txt : le panneau "accès interdit" du web
De nombreux sites déclarent que certaines parties de leur arborescence sont hors limites pour les robots. Cela se fait via le protocole d'exclusion des robots, en déposant un fichier nommé robots.txt à la racine de la hiérarchie d'URLs du site.
La syntaxe est volontairement rudimentaire. Un fichier peut par exemple indiquer qu'aucun robot ne doit visiter les URLs dont le chemin commence par /yoursite/temp/, tout en accordant une exception à un robot nommé "searchengine" : on écrit un premier bloc avec une ligne User-agent générale suivie d'une ligne Disallow: /yoursite/temp/, puis un second bloc User-agent: searchengine suivi d'une ligne Disallow: laissée vide, ce qui signifie "rien n'est interdit à celui-là".
Pour tester une URL, il faut donc avoir récupéré le robots.txt du site concerné. Le refetcher pour chaque URL candidate serait absurde : on utilise un cache conservant une copie récente du fichier par hôte. La tentation est grande de faire ce filtrage au moment de l'extraction des liens, car beaucoup de liens d'une page restent sur le même hôte, ce qui donnerait un flux d'hôtes très concentré et donc un excellent taux de succès du cache.
Sauf que cela irait à l'encontre des attentes des webmasters. Une URL - surtout si elle pointe vers un document de faible qualité ou qui change rarement - peut rester dans la frontière pendant des jours voire des semaines. Si le filtrage robots avait été fait avant son insertion, le robots.txt du site aurait pu changer entre-temps. Conclusion : le filtrage robots doit être effectué juste avant la tentative de téléchargement. Bonne nouvelle, le cache reste très efficace malgré tout, car il subsiste suffisamment de localité même dans le flux des URLs sortant de la frontière.
Qui a le plus gros index ? La méthode capture-recapture
La question "quelle est la taille du web ?" n'a pas de réponse propre, mais on peut se demander quelque chose de plus précis : quelles sont les tailles relatives des index de deux moteurs, appelons-les E1 et E2. Même cette question reste délicate, car un moteur peut renvoyer des pages qu'il n'a pas indexées entièrement (souvent seuls les premiers milliers de mots le sont), voire des pages simplement pointées par d'autres pages indexées, et parce que les index sont organisés en strates dont toutes ne sont pas consultées à chaque recherche.
L'idée de la méthode capture-recapture est la suivante. On tire une page au hasard dans l'index de E1 et on teste sa présence dans E2, puis symétriquement. On obtient deux fractions : une fraction x des pages de E1 est présente dans E2, et une fraction y des pages de E2 est présente dans E1. Comme le nombre de pages communes est le même vu des deux côtés, on a x fois la taille de E1 sensiblement égal à y fois la taille de E2, donc |E1| / |E2| égal environ y / x. Un exemple parle mieux : si 30 % des pages de A se retrouvent chez B et 50 % des pages de B chez A, le rapport donne 0,5 divisé par 0,3, soit un index A environ 1,67 fois plus grand que celui de B.
Attention aux hypothèses, qui sont franchement discutables : on suppose que le web a une taille finie et que chaque moteur en choisit un sous-ensemble indépendant et uniformément aléatoire. Ce n'est pas le cas. Et surtout, tirer une page vraiment au hasard est un problème difficile. Les quatre approches connues ont chacune leur biais : les recherches aléatoires tirées d'un journal de requêtes (biais lié au profil du groupe observé, et une page tirée dans les résultats n'est pas une page tirée dans l'index), les adresses IP aléatoires (plusieurs hôtes peuvent partager une IP à cause de l'hébergement virtuel, et on tombe surtout sur des sites peu volumineux), les marches aléatoires sur le graphe du web (qui n'est pas fortement connexe, et dont le temps de convergence est inconnu), et enfin les requêtes aléatoires.
Cette dernière méthode est la plus travaillée. On constitue d'abord un dictionnaire du web (par une exploration limitée, ou en s'appuyant sur un sous-ensemble représentatif assemblé à la main), car un dictionnaire classique ne contient ni les termes rares du web ni les fréquences réelles. On envoie ensuite à E1 une requête conjonctive de deux mots ou plus tirés de ce dictionnaire, on choisit au hasard une page p parmi les 100 premiers résultats, puis on teste p dans E2 en construisant une requête conjonctive avec six à huit termes peu fréquents extraits de p. On répète massivement l'opération. Là encore les biais s'accumulent : favoritisme envers les documents longs, influence du classement de E1, moteurs qui gèrent mal les requêtes à huit mots, refus de répondre à ce qui ressemble à du spam robotique, délais de connexion. Les travaux plus récents estiment l'ampleur du biais document par document pour en tirer des échantillons non biaisés, remplacent les requêtes conjonctives par des requêtes de phrase mieux gérées, et utilisent l'échantillonnage par marche aléatoire sur les documents, où l'on passe d'un document à un autre en tirant une paire de mots-clés du document courant, en lançant la requête et en choisissant une page au hasard parmi les résultats.
Au final, ce qu'il faut retenir de tout ce parcours : un crawler efficace n'est pas un programme qui suit les liens, c'est un système d'ordonnancement. La frontière d'URLs avec ses files frontales pour la priorité et ses files arrière pour la politesse, la table hôtes-vers-files, le tas des dates te, les empreintes et les shingles pour éliminer les copies, le filtre d'URLs et le respect scrupuleux de robots.txt : chacune de ces pièces répond à une contrainte précise. Si vous construisez votre propre robot, commencez par les trois règles minimales (une connexion par hôte, quelques secondes d'attente, robots.txt vérifié juste avant le téléchargement), ajoutez le checkpointing pour ne pas repartir de zéro à la première panne, et ne mettez les shingles et la distribution en place que lorsque le volume l'exige. Le reste suivra.
Questions fréquentes
Le web crawling est le processus par lequel un moteur de recherche explore et indexe les pages web.
Sans le web crawling, il n'y a pas d'index, donc pas de résultats de recherche disponibles pour les utilisateurs.
Les obstacles incluent les spider traps, les pages dynamiques infinies et la duplication de contenu.
Un bon crawler doit être robuste, poli, distribué, performant et capable de s'adapter à de nouveaux formats.
Les URLs sont priorisées en fonction de leur qualité et de leur taux de changement, influençant leur fréquence de réexamen.
