Conception d'un crawler web : frontière d'URL, politesse et déduplication

Un crawler semble simple : télécharger une page, extraire ses liens, les télécharger, recommencer. Écrit sous forme de boucle, cela marche pour mille pages. À un milliard de pages, cela s'effondre de façon instructive : il pilonne de petits sites avec des centaines de requêtes parallèles, télécharge la même page sous cinquante URL, se perd dans un calendrier infini et passe le plus clair de son temps à attendre le DNS.

Cet article conçoit un crawler qui passe à l'échelle tout en restant poli : chiffres de capacité, frontière d'URL avec files de priorité et files par hôte, robots.txt tel que standardisé par la RFC 9309, déduplication des URL et du contenu, pièges à crawlers et composants alentour, avec un diagramme de toute la boucle.

Exigences et chiffres

L'objectif : crawler environ un milliard de pages par mois pour un index de recherche ou d'analyse, rafraîchir plus souvent les pages importantes, et ne jamais surcharger un site web.

La dernière ligne compte le plus. La découverte dépasse largement le téléchargement, si bien que le crawler choisit en permanence ce qu'il ne téléchargera pas. La priorisation est une fonction centrale, pas une optimisation.

La boucle de crawl

1. Prenez l'URL suivante dans la frontière.
2. Vérifiez le robots.txt de son hôte, depuis le cache.
3. Résolvez le nom d'hôte, depuis un cache DNS local.
4. Téléchargez la page en respectant le délai de politesse de l'hôte.
5. Stockez la réponse brute.
6. Analysez-la, extrayez les liens et normalisez-les.
7. Écartez les liens déjà vus ; ajoutez les autres à la frontière avec une priorité.
8. Calculez l'empreinte du contenu et ignorez les quasi-doublons dans les traitements suivants.

Chaque étape après la première est un endroit où un crawler naïf gaspille des efforts ou cause des dégâts.

La frontière d'URL

La frontière est le cœur d'un crawler : une file qui doit répondre à deux questions différentes à la fois. Quelle URL compte le plus ? Et quel hôte avons-nous le droit de contacter maintenant ?

La réponse classique est la conception de Mercator, décrite dans le chapitre sur la frontière d'URL d'Introduction to Information Retrieval :

• Les files avant gèrent la priorité. Un priorisateur affecte chaque nouvelle URL à l'une des F files selon des signaux comme la fréquence de changement de la page, sa popularité en liens ou l'importance de son site.
• Les files arrière gèrent la politesse. Chaque file arrière contient les URL d'un seul hôte. Un tas enregistre, pour chaque hôte, le moment le plus proche où il pourra être recontacté.
• Un thread de fetcher prend l'hôte au sommet du tas, télécharge une URL de la file arrière de cet hôte, puis réinsère l'hôte avec un nouveau moment au plus tôt. Quand une file arrière se vide, elle est réalimentée depuis les files avant, en favorisant les priorités élevées.

Les concepteurs de Mercator recommandaient environ trois fois plus de files arrière que de threads de fetcher, pour que les threads attendent rarement un hôte à ménager.

À grande échelle, partitionnez la frontière par hôte : hachez le nom d'hôte pour choisir un shard de frontière, afin que toutes les URL d'un hôte se trouvent au même endroit et que la politesse puisse s'appliquer localement, sans coordination.

Politesse et robots.txt

Un crawler poli envoie une seule requête à la fois par hôte et attend entre deux requêtes. Une heuristique courante tirée du même chapitre : attendre environ dix fois la durée du dernier téléchargement depuis cet hôte, pour que les serveurs lents respirent automatiquement davantage. Reculez encore sur les réponses 429 et 503, et respectez tout en-tête Retry-After.

robots.txt est devenu un standard en 2022 avec la RFC 9309. Les règles qu'un crawler doit appliquer correctement :

L'asymétrie entre 4xx et 5xx surprend : un fichier absent signifie « allez-y », mais une erreur serveur signifie « n'entrez pas », car le crawler ne peut pas savoir ce qu'auraient dit les règles. Crawl-delay ne fait pas partie de la RFC 9309, et les crawlers diffèrent sur le fait de le respecter ou non. Identifiez votre crawler par un user agent explicite qui inclut une URL avec vos coordonnées.

Dédupliquer les URL

La même page se cache derrière de nombreuses URL : HTTP://Example.com:80/a/./b?utm_source=x#top et http://example.com/a/b sont une seule page. Normalisez avant de vérifier si une URL a déjà été vue :

• Mettez le schéma et l'hôte en minuscules, supprimez les ports par défaut, résolvez les segments . et .., et normalisez l'encodage-pourcent, selon la section 6 de la RFC 3986.
• Supprimez le fragment, qui n'atteint jamais le serveur.
• Retirez les paramètres de suivi connus comme utm_*, avec prudence ; d'autres paramètres peuvent changer le contenu.
• Respectez les indications rel="canonical" après le téléchargement.

Vérifiez ensuite un ensemble d'URL déjà vues. Avec des milliards d'URL, un filtre de Bloom est le choix habituel. Dimensionné pour un milliard d'URL avec 1 % de faux positifs, il demande environ 9,6 bits par URL, soit à peu près 1,2 Go au total, avec sept fonctions de hachage. Un faux positif revient à ignorer une URL que vous n'avez pas réellement vue, un coût acceptable à 1 % pour la plupart des crawls ; gardez un stockage exact pour les URL à ne pas manquer, comme les entrées de sitemap.

Dédupliquer le contenu

Les miroirs, les versions imprimables et les paramètres de session produisent des pages identiques, ou presque, sous des URL différentes. Les doublons exacts sont faciles : hachez le contenu normalisé et comparez. Les quasi-doublons demandent une empreinte qui change peu quand la page change peu. Simhash est la technique standard : une empreinte de 64 bits où des documents similaires diffèrent de peu de bits. Des chercheurs de Google ont indiqué en 2007 que, pour un dépôt de huit milliards de pages, des empreintes simhash de 64 bits avec un seuil de trois bits différents constituaient un réglage pratique pour détecter les quasi-doublons.

Les pièges à crawlers

Certains sites génèrent des espaces d'URL infinis, souvent par accident : des calendriers avec un lien « mois suivant » sans fin, des identifiants de session dans chaque URL, une recherche à facettes avec toutes les combinaisons de filtres, et des liens relatifs qui allongent sans cesse un chemin. Les parades :

• Plafonnez la longueur des URL et la profondeur des chemins.
• Plafonnez le nombre de pages par hôte et par cycle de crawl, selon l'importance de l'hôte.
• Détectez les segments de chemin répétés comme /a/b/a/b/a/b.
• Baissez la priorité des URL dont les empreintes de contenu correspondent sans cesse à des pages que vous avez déjà.

Les sitemaps aident dans l'autre sens : ils listent les URL qu'un site veut voir crawlées, jusqu'à 50 000 URL ou 50 Mo non compressés par fichier sitemap, avec des fichiers d'index de sitemaps au-delà.

Autour de la boucle : DNS, stockage et recrawl

• Le DNS est un goulot d'étranglement caché. À des centaines de téléchargements par seconde, un résolveur cache partagé proche des fetchers évite d'envoyer chaque requête vers l'amont.
• Le stockage. Écrivez les réponses brutes dans un stockage objet sous forme de gros fichiers par lots, et envoyez le texte analysé et les liens vers l'indexation via un flux.
• Le recrawl. Les pages changent à des rythmes différents. Suivez la fréquence de changement de chaque page lors des visites précédentes et planifiez son prochain téléchargement en conséquence ; les requêtes conditionnelles avec If-Modified-Since ou ETag économisent de la bande passante quand rien n'a changé.
• Les pages riches en JavaScript demandent un navigateur headless, bien plus coûteux par page. Ne faites le rendu que pour les hôtes qui en ont besoin.

Le diagramme du crawler web

Comment le lire :

• Le cadre est la frontière d'URL : les files de priorité alimentent les files par hôte, qui appliquent la politesse.
• Les fetchers prennent une URL par hôte à la fois, consultent le cache robots.txt et le cache DNS, et téléchargent depuis Internet.
• Les pages brutes vont dans le magasin d'objets. Le parseur extrait les liens et le texte.
• Les nouveaux liens passent par le filtre d'URL déjà vues avant de revenir à la frontière, ce qui referme la boucle. Les empreintes de contenu signalent les quasi-doublons.
• Les pages analysées partent vers l'indexation via le flux à droite.
• Le bloc Markdown liste les chiffres de capacité et les règles de politesse.

Dessiner des pipelines avec des boucles

• Rendez la boucle visible. Un crawler est un cycle ; le dessiner comme un pipeline linéaire cache la rétroaction qui cause les pièges et les doublons.
• Montrez où la politesse est appliquée. Mettez les files par hôte dans l'image, pas dans une note de bas de page.
• Signalez les caches comme des caches. Les caches robots.txt et DNS changent la charge imposée au monde extérieur ; indiquez leur expiration.
• Placez des chiffres sur les arêtes : pages par seconde en entrée, liens par page en sortie.

Pour la méthode générale, voyez l'exemple de diagramme de conception de système. Le contrôle du débit vers chaque hôte reprend les idées de la conception d'un rate limiter, et le traitement après le crawl ressemble au diagramme d'architecture de pipeline de données.

Le construire dans Archboard

1. Connectez-vous avec Google ou GitHub et créez un diagramme.
2. Ajoutez un Cadre du pack Base nommé URL frontier et placez-y deux nœuds File d'attente du pack Données : les files de priorité et les files par hôte.
3. Ajoutez un nœud Instance de calcul du pack Cloud pour les fetchers, un nœud DNS et un nœud Internet du pack Réseau, et un nœud Redis du pack Données pour le cache robots.txt.
4. Ajoutez un Magasin d'objets du pack Données pour les pages brutes et un autre nœud Instance de calcul pour le parseur.
5. Ajoutez un second nœud Redis pour le filtre d'URL déjà vues, une Base de données gérée du pack Cloud pour les empreintes de contenu et un nœud Kafka du pack Données pour les pages destinées à l'indexation.
6. Dessinez la boucle avec des arêtes étiquetées et ajoutez un bloc Markdown du pack Base avec les chiffres.

L'exemple utilise 13 nœuds de diagramme et reste dans les limites de l'offre Free.

FAQ

Qu'est-ce qu'une frontière d'URL ? La structure de données qui décide de ce qu'un crawler télécharge ensuite. Elle combine des files de priorité, qui classent les URL par importance, avec des files par hôte et un calendrier qui empêchent le crawler de contacter un hôte trop souvent.

Comment les crawlers restent-ils polis ? Une connexion par hôte à la fois, un délai entre les requêtes qui augmente avec le temps de réponse du serveur, un recul sur les réponses 429 et 503, et le respect de robots.txt.

Que se passe-t-il si robots.txt renvoie une erreur ? Selon la RFC 9309, un statut 4xx signifie que le crawler peut crawler le site, tandis qu'un statut 5xx ou une erreur réseau signifie qu'il doit tout considérer comme interdit tant qu'il ne peut pas lire le fichier.

Comment les crawlers évitent-ils de télécharger deux fois la même page ? Ils normalisent les URL et les comparent à un ensemble d'URL déjà vues, souvent un filtre de Bloom, et ils calculent des empreintes du contenu avec des hash exacts et simhash pour repérer la même page sous des URL différentes.

Quelle taille faut-il pour un filtre de Bloom d'un milliard d'URL ? Environ 1,2 Go pour un taux de faux positifs de 1 %, avec à peu près 9,6 bits par URL et sept fonctions de hachage. Des taux d'erreur plus faibles coûtent davantage de bits par entrée.

Commencez gratuitement — un siège, sans carte bancaire.