Webcrawler-Systemdesign: URL-Frontier, Höflichkeit und Deduplizierung

Ein Crawler wirkt einfach: Seite herunterladen, Links extrahieren, diese herunterladen, wiederholen. Als Schleife geschrieben funktioniert das für tausend Seiten. Bei einer Milliarde Seiten bricht es auf lehrreiche Weise zusammen: Er bombardiert kleine Sites mit Hunderten paralleler Requests, lädt dieselbe Seite unter fünfzig URLs herunter, verirrt sich in einem endlosen Kalender und verbringt die meiste Zeit mit Warten auf DNS.

Dieser Beitrag entwirft einen Crawler, der skaliert und höflich bleibt: Kapazitätszahlen, die URL-Frontier mit Prioritäts- und Host-Queues, robots.txt in der Form, die RFC 9309 standardisiert hat, URL- und Inhalts-Deduplizierung, Crawler-Fallen und die Komponenten drumherum, mit einem Diagramm der ganzen Schleife.

Anforderungen und Zahlen

Das Ziel: etwa eine Milliarde Seiten pro Monat für einen Such- oder Analyseindex crawlen, wichtige Seiten häufiger aktualisieren und nie eine Website überlasten.

Die letzte Zeile ist die wichtigste. Das Entdecken überholt das Abrufen mit großem Abstand, also wählt der Crawler ständig aus, was er nicht abruft. Priorisierung ist ein Kernfeature, keine Optimierung.

Die Crawl-Schleife

1. Nimm die nächste URL aus der Frontier.
2. Prüf robots.txt für ihren Host, aus dem Cache.
3. Löse den Hostnamen über einen lokalen DNS-Cache auf.
4. Ruf die Seite ab und halte dabei die Höflichkeitspause des Hosts ein.
5. Speichere die Rohantwort.
6. Parse sie, extrahiere Links und normalisiere sie.
7. Verwirf bereits gesehene Links; füge den Rest mit einer Priorität zur Frontier hinzu.
8. Bilde einen Fingerprint des Inhalts und überspring Beinahe-Duplikate in der späteren Verarbeitung.

Jeder Schritt nach dem ersten ist eine Stelle, an der ein naiver Crawler Aufwand verschwendet oder Schaden anrichtet.

Die URL-Frontier

Die Frontier ist das Herz eines Crawlers: eine Queue, die zwei verschiedene Fragen gleichzeitig beantworten muss. Welche URL ist am wichtigsten? Und welchen Host dürfen wir gerade kontaktieren?

Die klassische Antwort ist das Mercator-Design, beschrieben im Kapitel zur URL-Frontier von Introduction to Information Retrieval:

• Front-Queues kümmern sich um Priorität. Ein Priorisierer ordnet jede neue URL einer von F Queues zu, anhand von Signalen wie der Änderungshäufigkeit der Seite, ihrer Link-Popularität oder der Bedeutung ihrer Site.
• Back-Queues kümmern sich um Höflichkeit. Jede Back-Queue enthält URLs genau eines Hosts. Ein Heap speichert pro Host den frühesten Zeitpunkt, zu dem er wieder kontaktiert werden darf.
• Ein Fetcher-Thread nimmt den Host oben im Heap, ruft eine URL aus dessen Back-Queue ab und legt den Host mit einem neuen frühesten Zeitpunkt zurück. Wird eine Back-Queue leer, wird sie aus den Front-Queues nachgefüllt, wobei höhere Prioritäten bevorzugt werden.

Die Mercator-Entwickler empfahlen etwa dreimal so viele Back-Queues wie Fetcher-Threads, damit Threads selten auf einen Host warten, der geschont werden muss.

Im großen Maßstab partitionierst du die Frontier nach Host: Hashe den Hostnamen, um einen Frontier-Shard zu wählen, sodass alle URLs eines Hosts an einem Ort liegen und Höflichkeit lokal ohne Koordination durchgesetzt werden kann.

Höflichkeit und robots.txt

Ein höflicher Crawler schickt pro Host jeweils nur einen Request und wartet zwischen den Requests. Eine verbreitete Faustregel aus demselben Kapitel: Warte etwa zehnmal so lange, wie der letzte Abruf von diesem Host gedauert hat, damit langsame Server automatisch mehr Luft bekommen. Zieh dich bei 429- und 503-Antworten weiter zurück und beachte einen vorhandenen Retry-After-Header.

robots.txt wurde 2022 mit RFC 9309 zum Standard. Die Regeln, die ein Crawler richtig umsetzen muss:

Die Asymmetrie zwischen 4xx und 5xx überrascht viele: Eine fehlende Datei heißt „nur zu“, ein Serverfehler aber „draußen bleiben“, weil der Crawler nicht wissen kann, was die Regeln gesagt hätten. Crawl-delay ist nicht Teil von RFC 9309, und Crawler unterscheiden sich darin, ob sie es beachten. Identifiziere deinen Crawler mit einem aussagekräftigen User Agent, der eine URL mit Kontaktdaten enthält.

URLs deduplizieren

Dieselbe Seite versteckt sich hinter vielen URLs: HTTP://Example.com:80/a/./b?utm_source=x#top und http://example.com/a/b sind eine Seite. Normalisiere, bevor du prüfst, ob eine URL schon gesehen wurde:

• Schreib Schema und Host klein, entferne Standardports, löse .- und ..-Segmente auf und normalisiere die Prozentkodierung gemäß RFC 3986 Abschnitt 6.
• Entferne das Fragment, das nie beim Server ankommt.
• Entferne bekannte Tracking-Parameter wie utm_*, aber vorsichtig; andere Parameter können den Inhalt ändern.
• Beachte nach dem Abruf rel="canonical"-Hinweise.

Dann prüfst du ein Seen-URL-Set. Bei Milliarden URLs ist ein Bloom-Filter die übliche Wahl. Ausgelegt für eine Milliarde URLs bei 1 % False Positives braucht er etwa 9,6 Bit pro URL, insgesamt rund 1,2 GB, mit sieben Hashfunktionen. Ein False Positive bedeutet, eine URL zu überspringen, die du in Wahrheit nicht gesehen hast; bei 1 % ist das für die meisten Crawls ein akzeptabler Preis. Für URLs, die du nicht verpassen darfst, etwa Sitemap-Einträge, führst du einen exakten Speicher.

Inhalte deduplizieren

Mirrors, Druckversionen und Session-Parameter erzeugen Seiten, die unter verschiedenen URLs identisch oder fast identisch sind. Exakte Duplikate sind leicht: Hashe den normalisierten Inhalt und vergleiche. Beinahe-Duplikate brauchen einen Fingerprint, der sich wenig ändert, wenn sich die Seite wenig ändert. Simhash ist die Standardtechnik: ein 64-Bit-Fingerprint, bei dem sich ähnliche Dokumente in wenigen Bits unterscheiden. Google-Forscher berichteten 2007, dass für ein Repository mit acht Milliarden Seiten 64-Bit-Simhash-Fingerprints mit einer Schwelle von drei abweichenden Bits eine praktikable Einstellung zur Erkennung von Beinahe-Duplikaten waren.

Crawler-Fallen

Manche Sites erzeugen unendliche URL-Räume, oft aus Versehen: Kalender mit einem endlosen „nächster Monat“-Link, Session-IDs in jeder URL, facettierte Suche mit jeder Filterkombination und relative Links, die einen Pfad immer weiter wachsen lassen. Gegenmittel:

• Begrenze URL-Länge und Pfadtiefe.
• Begrenze die Seiten pro Host und Crawl-Zyklus, skaliert nach der Bedeutung des Hosts.
• Erkenne sich wiederholende Pfadsegmente wie /a/b/a/b/a/b.
• Senke die Priorität von URLs, deren Inhalts-Fingerprints immer wieder zu Seiten passen, die du schon hast.

Sitemaps helfen in die andere Richtung: Sie listen die URLs, die eine Site gecrawlt haben will, bis zu 50.000 URLs oder 50 MB unkomprimiert pro Sitemap-Datei, mit Sitemap-Indexdateien für mehr.

Rund um die Schleife: DNS, Speicher und Recrawling

• DNS ist ein versteckter Engpass. Bei Hunderten Abrufen pro Sekunde verhindert ein gemeinsamer cachender Resolver nahe an den Fetchern, dass jede Anfrage nach oben geschickt wird.
• Speicher. Schreib Rohantworten in großen Batch-Dateien in den Objektspeicher und schick geparsten Text und Links über einen Stream weiter zur Indexierung.
• Recrawling. Seiten ändern sich unterschiedlich schnell. Verfolge, wie oft sich jede Seite bei früheren Besuchen geändert hat, und plane ihren nächsten Abruf entsprechend; bedingte Requests mit If-Modified-Since oder ETag sparen Bandbreite, wenn sich nichts geändert hat.
• JavaScript-lastige Seiten brauchen einen Headless-Browser, der pro Seite weit teurer ist. Rendere nur die Hosts, die es brauchen.

Das Webcrawler-Diagramm

So liest du es:

• Der Rahmen ist die URL-Frontier: Prioritäts-Queues speisen Queues pro Host, die die Höflichkeit durchsetzen.
• Fetcher nehmen pro Host jeweils eine URL, fragen robots.txt-Cache und DNS-Cache ab und laden aus dem Internet herunter.
• Rohseiten gehen in die Objektablage. Der Parser extrahiert Links und Text.
• Neue Links passieren den Seen-URL-Filter, bevor sie zur Frontier zurückkehren, und schließen so die Schleife. Inhalts-Fingerprints markieren Beinahe-Duplikate.
• Geparste Seiten fließen über den Stream rechts weiter zur Indexierung.
• Der Markdown-Block listet die Kapazitätszahlen und Höflichkeitsregeln auf.

Pipelines mit Schleifen zeichnen

• Mach die Schleife sichtbar. Ein Crawler ist ein Kreislauf; ihn als gerade Pipeline zu zeichnen, versteckt die Rückkopplung, die Fallen- und Duplikatprobleme verursacht.
• Zeig, wo Höflichkeit durchgesetzt wird. Setz die Queues pro Host ins Bild, nicht in eine Fußnote.
• Kennzeichne Caches als Caches. robots.txt- und DNS-Caches verändern die Last auf die Außenwelt; beschrifte ihre Ablaufzeit.
• Schreib Zahlen an die Kanten: Seiten pro Sekunde hinein, Links pro Seite heraus.

Zur allgemeinen Methode sieh dir das System-Design-Diagramm-Beispiel an. Die Ratensteuerung gegenüber jedem Host nutzt dieselben Ideen wie das Systemdesign eines Rate Limiters, und die Verarbeitung nach dem Crawl ähnelt dem Architekturdiagramm für Datenpipelines.

In Archboard nachbauen

1. Melde dich mit Google oder GitHub an und leg ein Diagramm an.
2. Füge einen Rahmen aus dem Basis-Pack namens URL frontier hinzu und setz zwei Warteschlange-Nodes aus dem Daten-Pack hinein: Prioritäts-Queues und Queues pro Host.
3. Füge einen Recheninstanz-Node aus dem Cloud-Pack für die Fetcher hinzu, einen DNS- und einen Internet-Node aus dem Netzwerk-Pack und einen Redis-Node aus dem Daten-Pack für den robots.txt-Cache.
4. Füge eine Objektablage aus dem Daten-Pack für Rohseiten hinzu und einen weiteren Recheninstanz-Node für den Parser.
5. Füge einen zweiten Redis-Node für den Seen-URL-Filter hinzu, eine Verwaltete Datenbank aus dem Cloud-Pack für Inhalts-Fingerprints und einen Kafka-Node aus dem Daten-Pack für Seiten auf dem Weg zur Indexierung.
6. Zeichne die Schleife mit beschrifteten Kanten und füge einen Markdown-Block aus dem Basis-Pack mit den Zahlen hinzu.

Das Beispiel nutzt 13 Diagramm-Nodes und bleibt damit im Free-Plan.

FAQ

Was ist eine URL-Frontier? Die Datenstruktur, die entscheidet, was ein Crawler als Nächstes abruft. Sie kombiniert Prioritäts-Queues, die URLs nach Bedeutung ordnen, mit Queues pro Host und einem Zeitplan, die verhindern, dass der Crawler einen Host zu oft kontaktiert.

Wie bleiben Crawler höflich? Eine Verbindung pro Host gleichzeitig, eine Pause zwischen Requests, die mit der Antwortzeit des Servers wächst, Zurückhaltung bei 429- und 503-Antworten und die Beachtung von robots.txt.

Was passiert, wenn robots.txt einen Fehler liefert? Nach RFC 9309 bedeutet ein 4xx-Status, dass der Crawler die Site crawlen darf, während ein 5xx-Status oder ein Netzwerkfehler bedeutet, dass er von einem vollständigen Verbot ausgehen muss, bis er die Datei lesen kann.

Wie vermeiden Crawler, dieselbe Seite zweimal herunterzuladen? Sie normalisieren URLs und prüfen sie gegen ein Seen-URL-Set, oft einen Bloom-Filter, und sie bilden Fingerprints des Inhalts mit exakten Hashes und Simhash, um dieselbe Seite unter verschiedenen URLs zu erkennen.

Wie groß muss ein Bloom-Filter für eine Milliarde URLs sein? Etwa 1,2 GB für eine False-Positive-Rate von 1 %, mit rund 9,6 Bit pro URL und sieben Hashfunktionen. Niedrigere Fehlerraten kosten mehr Bits pro Eintrag.

Kostenlos starten — ein Seat, keine Kreditkarte.