Kostenbewusste Crawl-Planung: Ihr Budget dort einsetzen, wo sich etwas ändert

Sehen Sie sich die Fetch-Logs fast jedes lang laufenden Crawlers an, und dasselbe Muster taucht auf. Die große Mehrheit der Requests liefert eine Seite zurück, die mit der letzten Kopie identisch ist. Jeder dieser Fetches hat Bandbreite oder Credits gekostet, einen Concurrency-Slot belegt und den Server eines anderen belastet, und dabei genau nichts erbracht.

Das ist kein Fehler im Fetcher. Es ist eine Scheduling-Entscheidung, meist per Voreinstellung getroffen: alles im gleichen Zyklus erneut besuchen, oder die wichtigen Dinge öfter besuchen. Beides fühlt sich vernünftig an, und beides verschwendet den größten Teil des Budgets. Dieser Beitrag handelt davon, die Entscheidung bewusst zu treffen und jeden Besuch danach zu bepreisen, was er wahrscheinlich einbringt.

Die richtige Einheit messen

Teams verfolgen üblicherweise die Kosten pro abgerufener Seite. Die Zahl, die zählt, sind die Kosten pro entdeckter Änderung.

Ein Crawler, der eine Million Seiten pro Tag abruft und zehntausend Änderungen entdeckt, hat hundert Fetches pro nützlicher Beobachtung ausgegeben. Die Halbierung der Fetch-Anzahl ohne Verlust von Änderungen halbiert die Kosten des Datensatzes. Die Verdopplung der Fetch-Anzahl ohne mehr gefundene Änderungen verdoppelt sie umsonst. Stellen Sie „Fetches, die keine Änderung fanden” auf ein Dashboard, pro Site und pro Seitentyp, und es wird offensichtlich, wo das Geld hingeht.

Wissen, was ein Fetch tatsächlich kostet

Die Kosten eines Besuchs hängen davon ab, wie Sie abgerechnet werden, und die beiden gängigen Modelle belohnen unterschiedliche Optimierungen.

Abrechnungsmodell	Wofür Sie zahlen	Was einen Besuch günstiger macht
Residential-Proxy-Bandbreite	Bytes durch das Gateway	Kleinere Antworten: kein Rendering, keine Bilder, komprimierte Übertragung
Scraping-API-Credits	Erfolgreiche Antworten	Weniger Fetches; die Größe jedes einzelnen spielt kaum eine Rolle

Auf Shifters Residential-Gateway zählt jedes gesendete oder empfangene Byte, einschließlich Header, und fehlgeschlagene Requests zählen, wenn vor dem Fehler Bytes übertragen wurden. Jeden Fetch zu verkleinern zahlt sich direkt aus, und die Taktiken dafür sind in Proxy-Bandbreitenkosten senken beschrieben. Bei der Web Scraping API kostet ein erfolgreicher Request einen Credit, unabhängig davon, ob JavaScript-Rendering aktiviert ist, und fehlgeschlagene Requests sowie Zielfehler kosten nichts. Dort kosten eine gerenderte Seite und eine einfache dasselbe, und der einzige Hebel, der die Rechnung bewegt, ist, wie viele erfolgreiche Fetches Sie anfordern.

In jedem Fall ist der Scheduler der größte Hebel, den Sie haben, denn der billigste Fetch ist der, den Sie beschlossen haben, nicht zu machen.

Wie oft ändert sich jede Seite?

Scheduling nach erwartetem Wert erfordert eine Schätzung, wie oft sich jede Seite ändert. Die übliche Arbeitsannahme in der Crawler-Forschung ist, dass Änderungen ungefähr zufällig mit einer durchschnittlichen Rate pro Seite auftreten, was die Wahrscheinlichkeit, dass sich eine Seite seit Ihrem letzten Besuch geändert hat, ergibt zu:

P(changed) = 1 - e^(-rate × time since last visit)

Sie schätzen die Rate aus Ihrer eigenen Historie. Jeder Besuch verrät Ihnen, ob sich die Seite seit dem vorherigen geändert hat. Teilen Sie beobachtete Änderungen durch beobachtete Zeit, pro Seite, und glätten Sie sie zum Durchschnitt ähnlicher Seiten, damit eine dreimal besuchte Seite keine extreme Schätzung erhält.

Zwei Vorbehalte. Erstens kann ein Besuch nur zeigen, dass sich eine Seite geändert hat, nicht wie oft, sodass Seiten, die sich schneller ändern, als Sie besuchen, langsamer erscheinen, als sie sind. Zweitens definieren Sie „geändert” anhand der Felder, die Sie interessieren. Eine Seite, deren Zeitstempel, Werbeplatz oder Session-Token bei jedem Laden anders ist, ändert sich ständig und bedeutet nichts. Hashen Sie den extrahierten Datensatz, nicht das HTML.

Das kontraintuitive Ergebnis: nicht den schnellsten Seiten nachjagen

Die naheliegende Policy ist, Seiten proportional dazu zu besuchen, wie oft sie sich ändern. Sie ist auch falsch, und der Beweis dafür ist über zwanzig Jahre alt.

In „Effective Page Refresh Policies for Web Crawlers” (ACM Transactions on Database Systems, 2003) verglichen Junghoo Cho und Hector Garcia-Molina Allokations-Policies, um mit einem festen Besuchsbudget eine lokale Kopie aktuell zu halten. Ihr Fund lautet, in ihren Worten: „the uniform policy is always more effective than the proportional policy under any scenario”. Ihre optimale Policy geht weiter, und sie fassen es direkt zusammen: „To improve freshness, we should penalize the elements that change too often.”

Die Intuition ist einfach, wenn man sie einmal benennt. Eine Seite, die sich alle fünfzehn Minuten ändert, ist fast sofort wieder veraltet, nachdem Sie sie abgerufen haben. Sie zu besuchen, erkauft ein paar Minuten Aktualität. Eine Seite, die sich etwa einmal täglich ändert, bleibt bei täglichem Besuch den größten Teil des Tages nach jedem Besuch korrekt. Bei begrenztem Budget ist Letzteres ein weitaus besserer Kauf.

Man kann das in Zahlen fassen. Unter demselben Änderungsmodell ist die Aktualität, die ein Besuch erkauft, die Wahrscheinlichkeit, dass die Seite gerade veraltet ist, multipliziert mit der Dauer, die sie danach voraussichtlich korrekt bleibt. Für einen Crawler, der etwa einmal täglich erneut besuchen kann:

Seite ändert sich	Erkaufte Aktualität pro Besuch (Tage)
Etwa alle 15 Minuten	0,010
Etwa stündlich	0,042
Etwa alle 6 Stunden	0,241
Etwa täglich	0,400
Etwa wöchentlich	0,124
Etwa monatlich	0,032
Etwa jährlich	0,003

Die besten Käufe sind Seiten, die sich etwa in dem Tempo ändern, das Sie sich leisten können, erneut zu besuchen. Seiten, die sich viel schneller ändern, lassen sich zu keinem erschwinglichen Preis aktuell halten; Seiten, die sich viel langsamer ändern, sind fast immer bereits aktuell.

Es gibt eine wichtige Ausnahme. Das Ergebnis betrifft Aktualität: wie oft Ihre Kopie mit der Live-Seite übereinstimmt. Manche Aufgaben drehen sich stattdessen darum, Ereignisse zu erfassen: jede Preisänderung, jeden Lagerausfall, jede Bearbeitung. Wenn jede Änderung einzeln zählt, brauchen sich schnell ändernde Seiten mehr Besuche, nicht weniger, und die richtige Antwort kann eine ganz andere Quelle sein, etwa eine API, ein Feed oder eine Listing-Seite, die die Änderung ohne vollständigen Fetch zeigt. Entscheiden Sie, welches Problem Sie lösen, bevor Sie optimieren.

Jeden Besuch nach erwartetem Wert pro Kosten bewerten

Fügt man die Teile zusammen, erhält jeder Besuchskandidat eine Priorität: wie wichtig die Seite ist, mal die Aktualität, die ein Besuch erkaufen würde, geteilt durch die Kosten des Besuchs.

import math


def freshness_gain(rate, days_since_visit, interval_days):
    """Expected fresh days bought by visiting now, under a Poisson change model."""
    p_stale = 1 - math.exp(-rate * days_since_visit)
    fresh_after = (1 - math.exp(-rate * interval_days)) / rate if rate > 0 else interval_days
    return p_stale * fresh_after


def priority(page, today, interval_days=1.0):
    gain = freshness_gain(page.change_rate, today - page.last_fetched, interval_days)
    return page.value * gain / page.cost

Der Scheduler arbeitet dann von einer Prioritätswarteschlange aus: In jedem Zyklus wird das Budget für die höchstbewerteten Besuche ausgegeben, dann wird gestoppt. Drei Eingaben verdienen besondere Sorgfalt.

• Wert ist ein geschäftliches Urteil, kein technisches. Ein Produkt, das sich verkauft, ein Wettbewerber, der wichtig ist, eine Anfrage, die Ihre Kunden stellen. Halten Sie es grob; drei oder vier Stufen reichen meist aus.
• Kosten sollten die tatsächlichen Kosten dieses Besuchs sein: Bytes für diesen Seitentyp, Credits, und ob Rendering nötig ist. Eine Seite, die auf einem bandbreitenabgerechneten Plan einen Headless-Browser benötigt, kann ein Vielfaches eines einfachen Fetches kosten.
• Änderungsrate stammt aus Ihrer Historie, aktualisiert nach jedem Besuch.

Billige Signale vor teuren Fetches

Oft können Sie viel günstiger als durch den Preis des Fetches herausfinden, ob sich eine Seite geändert hat.

• Conditional Requests. Wo eine Site ETag oder Last-Modified respektiert, kostet eine 304 Not Modified-Antwort einen Bruchteil der Bytes. Verfolgen Sie pro Host, ob die Validatoren zuverlässig sind; manche Sites senden sie und ignorieren sie.
• Listing-Seiten als Änderungsdetektoren. Eine Kategorie- oder Suchseite zeigt oft Preis und Verfügbarkeit für Dutzende von Artikeln. Rufen Sie das Listing ab, vergleichen Sie, und rufen Sie nur die Artikel ab, deren Zusammenfassung sich geändert hat. So bleiben die meisten Echtzeit-Preisfeeds und Bestandsmonitore erschwinglich.
• Sitemaps und Feeds. Wo sie vertrauenswürdige Änderungsdaten tragen, verraten sie Ihnen, was sich geändert hat, ohne dass Sie sonst etwas besuchen müssen.
• Strukturierte Endpunkte. Eine JSON-Antwort hinter einer Seite ist meist kleiner und stabiler als die Seite selbst.

Budget für das reservieren, was der Scheduler nicht sehen kann

Ein Scheduler, der nur bekannte Seiten optimiert, wird langsam blind. Halten Sie in jedem Zyklus einen Teil für drei Dinge zurück:

1. Discovery. Neue URLs haben keine Historie und würden nie etablierte Seiten überbieten. Geben Sie ihnen eine eigene Zuteilung.
2. Re-Estimation. Eine Seite, die monatelang als unveränderlich bewertet wurde, sollte trotzdem gelegentlich besucht werden, weil Seiten ihr Verhalten ändern. Ohne das wird eine falsche Schätzung nie korrigiert.
3. Verifikation. Eine kleine Zufallsstichprobe, unabhängig von der Bewertung abgerufen, zeigt, ob die Annahmen des Modells noch gelten.

Kosten und Health auf den Zeitplan zurückwirken lassen

Der Zeitplan ist ein Plan, keine Garantie. Wenn eine Site anfängt zu throttlen, sollte der Scheduler davon erfahren und neu ranken, statt weiter Besuche einzureihen, die die Fetch-Stufe nicht ausführen kann. Dieser Rückmeldeweg, von den Fetchern zurück zur Frontier, wird in Backpressure und Flow Control in verteilten Crawlern behandelt, und der Gesamtzustand einer Site in den Aufbau eines Target Health Scores. Ein fallender Health Score sollte auch die effektiven Kosten für den Besuch dieser Site erhöhen, genau das Signal, das ein kostenbewusster Scheduler braucht.

Fazit

Ein Crawl-Budget, das gleichmäßig ausgegeben wird, oder proportional dazu, wie beschäftigt jede Seite ist, wird größtenteils damit verbracht, zu bestätigen, dass nichts passiert ist. Schätzen Sie aus Ihrer eigenen Historie, wie oft sich jede Seite ändert, bepreisen Sie jeden Besuch danach, was er einbringen und was er kosten wird, und geben Sie das Budget zuerst den besten Käufen. Erwarten Sie, dass das die Seiten sind, die sich etwa in dem Tempo ändern, das Sie sich leisten können zu verfolgen, nicht die, die sich am schnellsten ändern.

Der Gewinn ist nicht nur eine kleinere Rechnung. Ein Crawler, der weniger abruft und sorgfältiger abruft, belastet auch die Sites, auf die er angewiesen ist, weniger.

Quellen und Referenzen

• Junghoo Cho und Hector Garcia-Molina, Effective Page Refresh Policies for Web Crawlers, ACM Transactions on Database Systems, Vol. 28, No. 4, December 2003.
• Shifter, Residential Proxies bandwidth and billing. Was als Traffic zählt.
• Shifter, Web Scraping API errors and limits. Credit-Kosten, Fehlerverhalten und Retries.