skip to content

With a fixed daily fetch budget, how should a web crawler decide how often to recrawl each page it already knows?

level: principalimportance: nice to knowfreq 30%

answer

  1. budget arithmetic first
  2. change as a Poisson rate
  3. freshness versus age
  4. marginal gain per visit
  5. conditional GET still costs a slot

basics

~20 s

Estimate each page's change rate from past fetches and weight it by importance, then spend the budget where a revisit most improves freshness. Revisiting strictly in proportion to change rate can backfire on pages that change faster than you can return.

solid answer

~50 s

Start with the arithmetic: 1,000 fetches per second is about 86.4 million a day, so one uniform pass over 5 billion pages takes about 58 days, and revisits must be targeted. Model each page's changes as a Poisson process with rate λ, estimated from how often past revisits found changed content. **Freshness** is the fraction of time the stored copy matches the live page; with revisit interval I its expected value is `(1 − e^(−λI)) / (λI)`. Revisiting in proportion to change rate over-invests in pages that change hourly, because each visit is stale again almost at once. A better policy spends extra visits where they raise freshness most, weighted by importance such as traffic or links, and may give very fast pages a separate fast lane or fewer visits. Conditional GETs (`If-None-Match`, `If-Modified-Since`) make unchanged revisits cheap, but still use a request and a politeness slot.

go deeper

for a junior

Recall that stored pages go stale and that the crawler must split a fixed fetch budget between new pages and revisits.

for a middle

Explain how a change rate is estimated from past visits and how conditional GET makes unchanged revisits cheaper.

for a senior

Show the budget arithmetic, adaptive intervals with bounds, change detection on main content, and how politeness caps a host's refresh rate.

for a principal

Argue the policy: marginal freshness gain weighted by importance, freshness versus age as the target, and how capacity is split between refresh and discovery.

## Why recrawling needs a policy A web crawler does not fetch each page once. Pages change, and a search engine's copy goes **stale**. With a fixed fetch rate, every revisit to a known page is a fetch not spent discovering a new one, so the crawler needs a **refresh policy**. The budget makes this concrete. Assume, for illustration, 1,000 fetches per second: - 1,000 × 86,400 seconds is about **86.4 million fetches per day**. - A corpus of 5 billion pages takes about 5,000,000,000 ÷ 86,400,000 ≈ **58 days** for one uniform pass. A news front page that changes every few minutes and an archived paper that never changes cannot sensibly share a 58-day cycle. ## Modelling change The usual model treats changes to a page as a **Poisson process** with rate λ (expected changes per day). Two measures describe how good the stored copy is: - **Freshness**: the fraction of time the stored copy equals the live page. - **Age**: how long the stored copy has been out of date, averaged over time. If a page is revisited every I days, its expected freshness is `(1 − e^(−λI)) / (λI)`. ## Why proportional revisiting can backfire The intuitive policy, *visit each page in proportion to how often it changes*, is not optimal for average freshness. A well-known analysis shows it can do worse than even uniform revisiting. The formula shows why, using illustrative numbers: | Page | λ (per day) | Visits | λI | Freshness | |---|---|---|---|---| | hourly-changing | 24 | 1 per day | 24 | about 4.2% | | hourly-changing | 24 | 2 per day | 12 | about 8.3% | | daily-changing | 1 | 1 per week | 7 | about 14.3% | | daily-changing | 1 | 2 per week | 3.5 | about 27.7% | Adding **seven** visits a week to the hourly page raises its freshness by about 4 points. Adding **one** visit a week to the daily page raises it by about 13 points. Per visit, the daily page gains roughly twenty times more. Pages that change faster than the crawler can return are stale again almost immediately, so extra visits buy little. The practical conclusions: - Spend visits where the **marginal freshness gain** per fetch is highest. - **Weight by importance** (traffic, links, how often the page appears in results), because staleness on a popular page costs more. - Give genuinely fast, important content (front pages, feeds) a **dedicated fast lane** with its own budget rather than letting it drain the general pool. - Accept that some very fast, low-value pages are best revisited *less*. ## Estimating the change rate The crawler only sees a page at its own visits, so it observes *changed* or *unchanged* between visits, not how many changes happened. 1. Counting changes per visit **underestimates** λ, because several changes between two visits look like one. 2. If a fraction p of visits at interval I found the page unchanged, then p ≈ e^(−λI), so λ ≈ −ln(p) / I. 3. Use extra evidence when present: `Last-Modified` headers, sitemap last-modified hints, and the change history of similar pages on the same host for pages with little history. 4. **Adapt**: shorten the interval when a visit finds a change, lengthen it when it does not, within minimum and maximum bounds. Change should be judged on the **main content** (for example a content fingerprint with boilerplate stripped), or a rotating ad makes every page look like it changes on every visit. ## Making revisits cheap, and what they still cost - **Conditional GET.** Sending `If-None-Match` with a stored `ETag`, or `If-Modified-Since` with a stored date, lets the server answer `304 Not Modified` with no body. That saves bandwidth, parsing and downstream work. - **What is still spent.** A 304 is still a request to the host and still consumes one of that host's **politeness slots**, so it does not raise how many URLs per host can be checked per day. - **Host-level limits.** Politeness caps how fast any one host can be refreshed, so a large host's pages compete with each other for its slots. ## The judgement calls a lead owns - **Which metric**: average freshness rewards keeping many pages exactly current; average age punishes pages that stay stale for long. They lead to different schedules. - **Refresh versus discovery**: how much of daily capacity goes to known pages versus finding new ones. - **Importance model**: which signals define a page's value, and how quickly a newly popular page is promoted. There is no single right answer; the policy follows from what the downstream search product values most.

  • How can a web crawler estimate a page's change rate when it only sees the page at its own visits?
    Treat changes as a Poisson process. If a fraction p of visits at interval I found the page unchanged, then p is about e^(−λI), so λ is about −ln(p) / I. Simply counting changes per visit underestimates λ, because several changes between two visits look like one. Headers such as Last-Modified, sitemap hints and the history of similar pages on the host help when a page has few observations.
  • How does conditional GET change the economics of recrawling?
    An unchanged page answers `304 Not Modified` with no body, which saves bandwidth, parsing and downstream processing. It does not save the request itself or the host's politeness slot, so it barely changes how many URLs per host can be checked per day. It makes checking cheaper, not faster.

It is like watering a garden with limited time: a plant that dries out every hour is never kept moist however often you visit, so the time is better spent keeping the weekly-drying plants in good shape.

saying these in an interview costs you the question

  • Change rate is irrelevant; one fixed interval for every page is optimal.
  • Pages that change most often should always get the most visits.
  • A 304 Not Modified response costs the crawler nothing.
  • Counting changes seen per visit gives an accurate change rate.
  • Freshness can be maximised without considering page importance.