A crawl is a snapshot, and the web does not hold still. Pages are edited, moved, and deleted, and new ones appear. A search engine whose copy of a page is out of date may rank it for words it no longer contains, or show a snippet that no longer matches. Freshness is one of the features Manning, Raghavan, and Schütze (2008, §20.1.2) say a crawler should provide: it should run continuously and revisit each page at a rate suited to how often that page changes. Choosing those rates is a resource allocation problem, and its best solution is not the obvious one.
How pages change
Studies that fetched the same pages repeatedly found that change is very uneven. Cho and Garcia-Molina (2000a) crawled 720,000 pages from 270 popular sites every day for four months. Some pages changed every time they were visited and many did not change at all during the study, and commercial sites changed far more often than educational or government ones. Fetterly, Manasse, Najork, and Wiener (2003) followed 151 million pages weekly for eleven weeks and found that most changes were small, often limited to markup, while a minority of pages changed substantially and repeatedly.
Cho and Garcia-Molina found that the changes of an individual page were well described by a Poisson process: changes arrive independently at random times, at an average rate $\lambda$ that differs from page to page. A page with $\lambda = 2$ per day changes twice a day on average, but on a given day it may change zero, one, three, or more times. Under this model, the waiting time $T$ from any moment until the next change has the exponential distribution, with density $\lambda e^{-\lambda t}$, and the probability that a page has not changed in the $t$ days since it was fetched is
$$P[T > t] = \int_t^\infty \lambda e^{-\lambda s}\, ds = e^{-\lambda t}.$$
The model is memoryless: how long ago the page last changed says nothing about when it will change next. That property makes the calculations below short.
Measuring freshness
Cho and Garcia-Molina (2003a) defined two measures of how current a collection is:
- Freshness is the fraction of the collection's pages whose copies are up to date, that is, identical to the live page.
- Age is how long a page's copy has been out of date, zero for a current copy, averaged over the collection.
Freshness counts how many copies are stale. Age also counts how stale they are. Both change over time, so a crawler is judged by their averages over a long period.
Freshness of one page
Follow one page, with change rate $\lambda$, that the crawler revisits every $I$ days, so its visit frequency is $f = 1/I$. Just after a visit, at time $0$, the copy is certainly fresh. At time $t$ before the next visit, it is fresh only if the page has not changed since time $0$, which has probability $e^{-\lambda t}$. Writing $F(t)$ for the freshness of the copy at time $t$, which is 1 or 0, its expected value is
$$E[F(t)] = 1 \cdot e^{-\lambda t} + 0 \cdot \left(1 - e^{-\lambda t}\right) = e^{-\lambda t}.$$
The next visit resets the copy, so the same pattern repeats in every interval. The long-run average freshness is the average of $e^{-\lambda t}$ over one interval:
$$\bar{F} = \frac{1}{I} \int_0^I e^{-\lambda t}\, dt = \frac{1}{I} \left[ -\frac{e^{-\lambda t}}{\lambda} \right]_0^I = \frac{1 - e^{-\lambda I}}{\lambda I}.$$
Only the product $\lambda I$ appears. Writing $r = \lambda I = \lambda / f$, the expected number of changes between visits,
$$\bar{F}(r) = \frac{1 - e^{-r}}{r}.$$
As a worked case, take a page that changes once a day on average, $\lambda = 1$, visited daily, $I = 1$. The probability that the copy is fresh falls from 1 just after the visit to $e^{-0.5} = 0.607$ at noon and $e^{-1} = 0.368$ just before the next visit, and its average over the day is $1 - e^{-1} = 0.632$. Even though the crawler visits exactly as often as the page changes, the copy is stale more than a third of the time, because changes come at random moments and some days bring two changes and others none.
Age of one page
Age needs one more step. If the page first changes at time $s$ after the visit, then at a later time $t$ the copy has been stale for $t - s$. Weighting each possible first-change time $s$ by its density $\lambda e^{-\lambda s}$,
$$E[A(t)] = \int_0^t (t - s)\, \lambda e^{-\lambda s}\, ds = t - \frac{1 - e^{-\lambda t}}{\lambda}.$$
The integral is done by parts, or by splitting it into $t \int_0^t \lambda e^{-\lambda s}\, ds = t(1 - e^{-\lambda t})$ minus $\int_0^t s \lambda e^{-\lambda s}\, ds = \frac{1 - e^{-\lambda t}}{\lambda} - t e^{-\lambda t}$. Averaging over the interval as before,
$$\bar{A} = \frac{1}{I} \int_0^I \left( t - \frac{1 - e^{-\lambda t}}{\lambda} \right) dt = I \left( \frac{1}{2} - \frac{1}{r} + \frac{1 - e^{-r}}{r^2} \right).$$
For the page that changes daily and is visited daily, $I = 1$ and $r = 1$, so $\bar{A} = \tfrac{1}{2} - 1 + (1 - e^{-1}) = 0.5 - 1 + 0.632 = 0.132$ days, about 3.2 hours. Expected age rises slowly at first, since the page probably has not changed yet, and then grows almost linearly.
Both formulas were checked against a simulation of Poisson changes: over 30 runs of 2,000 simulated days each, the median average freshness of the daily case was 0.6319, with the middle half of the runs between 0.6263 and 0.6351, against the formula's 0.6321.
How often to visit one page
The freshness formula answers practical questions directly. For the page that changes once a day:
| Visits per day | $r = \lambda / f$ | Average freshness | Average age |
|---|---|---|---|
| 0.5 | 2 | 0.432 | 10.4 hours |
| 1 | 1 | 0.632 | 3.2 hours |
| 2 | 0.5 | 0.787 | 0.9 hours |
| 4 | 0.25 | 0.885 | 0.2 hours |
| 10 | 0.1 | 0.952 | 0.04 hours |
Doubling the visit rate from one to two a day raises freshness by 0.155, and doubling it again adds only 0.098. Average freshness of 0.8 requires $r \le 0.464$, that is, about 2.15 visits for every change. Values are rounded to three places, and ages to a tenth of an hour except the last.
Proportional is not optimal
A crawler has a fixed budget of fetches per day. The intuitive policy is to visit each page in proportion to how often it changes, so that a page changing ten times as often is visited ten times as often. Cho and Garcia-Molina (2003a) showed that this proportional policy is worse for freshness than simply visiting every page equally often.
Two pages
A two-page example, with the change rates Cho and Garcia-Molina use (2000b), shows why. One page changes 9 times a day on average and the other once a day, and the crawler can make 10 visits a day in total.
| Policy | Visits per day | Freshness of fast page | Freshness of slow page | Mean freshness |
|---|---|---|---|---|
| Uniform | 5 and 5 | 0.464 | 0.906 | 0.685 |
| Proportional | 9 and 1 | 0.632 | 0.632 | 0.632 |
| Best split | 6.89 and 3.11 | 0.558 | 0.855 | 0.707 |
The proportional policy gives each page the same $r = 1$, and so the same freshness, 0.632. It spends 9 visits keeping the fast page fresh 63 percent of the time. Moving four of those visits to the slow page costs the fast page some freshness but raises the slow page from 63 to 91 percent. Each visit to a page that changes very often buys little, because its copy goes stale again almost immediately. The best allocation still gives the fast page more visits than the slow one, but far fewer than in proportion to its change rate.
The marginal value of a visit
The best split can be found without searching, by asking what one more visit a day is worth. Writing the average freshness of a page as a function of its visit frequency,
$$\bar{F}(\lambda, f) = \frac{f}{\lambda}\left(1 - e^{-\lambda / f}\right),$$
and differentiating with respect to $f$ gives the freshness gained per additional visit:
$$\frac{\partial \bar{F}}{\partial f} = \frac{1 - e^{-r}}{\lambda} - \frac{e^{-r}}{f}, \qquad r = \frac{\lambda}{f}.$$
Under the proportional policy, this marginal value is 0.029 for the fast page and 0.264 for the slow one. A visit taken from the fast page loses about 0.029 of its freshness, and the same visit given to the slow page gains about 0.264, so the move is worth making. Under the uniform policy the comparison runs the other way, 0.060 for the fast page against 0.018 for the slow, so a few visits should move back to the fast page. At the optimum the two marginal values are equal, at 0.0417: no transfer of a visit in either direction helps.
This is the method of Lagrange multipliers, which Cho and Garcia-Molina (2000b) use for the general problem. To maximize the mean freshness of $N$ pages, $\frac{1}{N}\sum_i \bar{F}(\lambda_i, f_i)$ subject to a fixed total $\sum_i f_i$, the optimal frequencies satisfy
$$\frac{\partial \bar{F}}{\partial f}(\lambda_i, f_i) = \mu \quad \text{for every page that is visited at all,}$$
for one constant $\mu$ chosen so that the frequencies add up to the budget. Two facts make this condition easy to use. First, the second derivative, $-\lambda e^{-r} / f^3$, is negative, so each page's freshness is concave in its visit rate: every extra visit is worth less than the one before, and the equal-marginal point is a maximum, not a minimum. Second, as $f$ approaches 0, the marginal value approaches $1/\lambda$. When visits are rare, each visit leaves the copy fresh until the next change, which takes $1/\lambda$ days on average, and that is all a visit can buy. A page whose $1/\lambda$ is below $\mu$ is therefore not worth even one visit, and the optimum skips it entirely.
With a small budget the effect is stark. With only one visit a day for the same two pages, the optimum gives it all to the slow page, for a mean freshness of 0.316, against 0.244 for the uniform split and 0.100 for the proportional one.
Five pages
Cho and Garcia-Molina (2000b) illustrate the general solution with five pages that change 1, 2, 3, 4, and 5 times a day and a budget of 5 visits a day. Solving the Lagrange condition numerically gives:
| Change rate (per day) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Optimal visits per day | 1.15 | 1.36 | 1.35 | 1.14 | 0.00 |
| Proportional visits per day | 0.33 | 0.67 | 1.00 | 1.33 | 1.67 |
The page that changes most often is not visited at all, and the page that changes four times a day gets fewer visits than the one that changes twice. The mean freshness is 0.374 for the optimum, 0.365 for uniform visits, and 0.317 for proportional ones. The computed frequencies match the values Cho and Garcia-Molina report.
In general, Cho and Garcia-Molina showed that the policy that maximizes freshness visits pages with moderate change rates most, and visits pages that change extremely often less than slower ones, since keeping them fresh is a losing battle. The result depends on the measure. Optimizing average age instead of freshness gives more visits to faster-changing pages, because a stale copy of a fast page grows old quickly and age counts how old. In the five-page example the age-optimal rates still stay close to uniform, from 0.84 visits a day for the slowest page to 1.09 for the fastest (Cho and Garcia-Molina, 2000b). A real crawler also weighs each page by its importance. A stale copy of a popular page costs more than a stale copy of an obscure one, so important pages get more visits than their change rate alone would justify.
Estimating the change rate
All of this assumes the crawler knows each page's $\lambda$, and it does not, because it sees a page only when it visits. If the page differs from the last visit, it has changed at least once, but the crawler cannot tell how many times. A naive estimate, the number of visits at which a change was detected divided by the time observed, is biased low for pages that change often, since several changes between visits count as one. Cho and Garcia-Molina (2003b) give estimators that correct for the changes a crawler misses between visits.
Cheaper revisits
Revisiting is less costly when the server can say that nothing has changed.
- Conditional requests. When a server sends a page, it may include an
ETag, an identifier for that version of the page, and aLast-Modifieddate. On the next visit, the crawler sends them back inIf-None-MatchandIf-Modified-Sinceheaders. If the page has not changed, the server answers with status 304 (Not Modified) and no body (Fielding, Nottingham, and Reschke, 2022). On this site, a stylesheet fetched a second time with its validators came back as a 304 with no body instead of the 18,198 bytes it had at the time. The site's pages, which are generated by the application on each request, send no validators, so every revisit transfers the whole page. - Sitemaps. A site can list its URLs in an XML sitemap, giving each one an optional last-modified date. A crawler that reads the sitemap can skip pages whose dates have not changed and discover new pages that have no links yet.
- Notifications. Some sites announce changes instead of waiting to be checked. RSS and Atom feeds list recent updates, and protocols such as IndexNow let a site notify participating search engines when a URL changes.
A conditional request does not change the freshness arithmetic, since the crawler must still ask, but it makes each check of an unchanged page nearly free, so a crawler can afford to check more often. Each of these mechanisms depends on the site's cooperation and honesty. A server that sends a fresh Last-Modified date on every request, or none, gives the crawler no help, and the crawler must fetch the page and compare the content itself, as monitoring websites does.
The numbers in this article are computed by tools/experiments/crawling/freshness_math.py in the site repository.
References
- Cho, J., and Garcia-Molina, H. (2000a). The evolution of the web and implications for an incremental crawler. In Proceedings of VLDB 2000, 200–209.
- Cho, J., and Garcia-Molina, H. (2000b). Synchronizing a database to improve freshness. In Proceedings of ACM SIGMOD 2000, 117–128.
- Cho, J., and Garcia-Molina, H. (2003a). Effective page refresh policies for web crawlers. ACM Transactions on Database Systems, 28(4), 390–426.
- Cho, J., and Garcia-Molina, H. (2003b). Estimating frequency of change. ACM Transactions on Internet Technology, 3(3), 256–290.
- Fetterly, D., Manasse, M., Najork, M., and Wiener, J. L. (2003). A large-scale study of the evolution of web pages. In Proceedings of WWW 2003, 669–678.
- Fielding, R., Nottingham, M., and Reschke, J. (2022). HTTP Semantics. RFC 9110, Internet Engineering Task Force.
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 20.1. Cambridge University Press.