Design a Web Crawler

It is the last over of a World Cup final. A cricket news site, news.example.in, is serving millions of readers on servers already near their limit, and it posts a new match report every few minutes. Readers searching for the result want that report in search soon. Now picture a careless crawler that picks this moment to discover the site's 40,000 archive pages and fetches 300 of them a second. It is the push that takes the site down, and the owners block it for good. A good crawler finds the new report quickly and still visits the host gently. The part that strikes that balance, the frontier, is the heart of this chapter.

The product: the crawler behind a search engine. It starts from a list of seed URLs and follows links across the web. It fetches about 100 million pages a day, keeps important pages fresh and hands every page to the indexer, and no website owner should ever feel it as an attack. We follow news.example.in through the whole design.

A web crawler, also called a spider or a bot, downloads web pages, finds the links inside them and downloads those pages too. Its seed URLs, such as the home pages of news sites, government portals and universities, are only the start: it keeps following links until it has fetched billions of pages. The whole job fits in a loop:

frontier = Frontier(seed_urls)
while True:
    url = frontier.next_ready()        # priority and politeness
    page = fetch(url)                  # DNS, robots.txt, HTTP
    store(page)                        # kept for the indexer
    for link in extract_links(page):
        link = normalise(link)
        if not seen(link):             # de-duplication
            frontier.add(link)

Every hard part of this chapter hides inside one of these lines.

Run that loop a thousand times a second for months, on millions of other people's websites, and every line becomes a design problem. The frontier, the crawler's to-do list, sits at both ends: every URL leaves from it and every new link returns to it. next_ready must pick important URLs first without flooding any one site, fetch meets slow servers and pages that never end, and seen must answer for billions of URLs, tens of thousands of times a second.

Here is the scope for today:

Everything out of scope plugs in later as an extra stage after fetch; nothing in it changes the loop.

The loop says what the crawler does; this page says how well. A crawler has nobody waiting at a screen, so steady throughput and good manners matter far more than latency:

• Polite. One request at a time per host, at least a second apart, and slower when the site is slow or asks; robots.txt is always obeyed. To a small website, a careless crawler looks like an attack.
• High throughput. 100 million pages a day now and ten times that later, by adding machines rather than redesigning.
• Fresh where it matters. The busiest news home pages and feeds are re-checked every few minutes; an average page about once a month.
• Resilient to a messy web. Broken HTML, endless link loops, huge files and servers that report errors as success must not stall or flood the crawl.
• Survives crashes. A dead machine's queues are restored from a checkpoint; at worst some pages are fetched twice.

To size it, assume a web like this:

Refreshing 3 B pages once a month means about 100 M fetches a day, and every estimate on the next page starts from that number. New pages compete with refreshes for the same budget, so deciding what not to fetch matters as much as fetching fast.

Use the method from the estimates chapter. 100 M fetches a day is 100 M ÷ 86,400 s, about 1,160 pages a second. Crawl traffic has no evening peak: the crawler sets its own pace and keeps it all day, so the average is also the rate to plan for, plus headroom for retries.

About 1.4 PB a year fits on fewer than a hundred 16 TB disks, before spares, so storage is not the hard part. The other numbers show where the pressure is:

The third row uses Little's law: requests in flight = rate × time each takes. Most of that second is spent waiting on a distant server, so 1,500 open connections need little CPU. The row that shapes the design is the fifth: 58,000 lookups a second against a set of 10 billion URLs. Ten crawler nodes are a comfortable start: each owns a tenth of the hosts, keeps about 150 connections open and holds 8 GB of the seen set in memory. One number is still missing, how many hosts must be in rotation at once; the frontier deep dive works it out.

With the numbers set, the next question is how the rest of the company talks to the crawler. It has no end users, so its API is small and internal: operators add seeds and manage hosts, other systems ask for a page to be fetched again, and the indexer hears about new pages through events instead of calling in.

POST /v1/seeds      {"urls": ["https://news.example.in/"], "priority": 0}          -> 202 {"accepted": 1}
POST /v1/recrawl    {"url": "https://shop.example.in/p/881", "reason": "sitemap"}  -> 202
GET  /v1/pages?url=https://news.example.in/scores   -> 200 {"status": 200, "fetched_at": "...", "content_key": "..."}
GET  /v1/hosts/news.example.in                     -> 200 {"gap_ms": 1000, "queued": 1240, "errors_1h": 2}
PUT  /v1/hosts/news.example.in/policy   {"max_per_sec": 0.2, "blocked": false}     -> 204

202 means queued, not fetched: the frontier decides when.

202 Accepted is the honest answer. A seed or a recrawl request joins the frontier, and the fetch may happen in seconds or in days, depending on its priority and the host's politeness gap. Nothing outside the crawler should wait on a fetch.

The host policy call is the emergency brake. If news.example.in's owners complain during the final, an operator slows the crawler for that host or blocks it, and every fetcher obeys within seconds, because the frontier reads the policy before handing out the host's next URL. The same call can raise the limit for large sites that are happy to be crawled faster.

Behind those calls sit a few tables. Everything is keyed by a URL hash, a 64-bit hash of the normalised URL: URLs average about 100 bytes and the hash is 8, so sets and tables keyed by it stay small. Hosts get their own table, because politeness, robots.txt rules and DNS answers belong to a host, not to a page.

Each kind of data goes where its access pattern is cheap:

The frontier and the seen set live on the crawler nodes themselves, because they are touched on every fetch; everything else can sit in shared stores.

Pages are packed because a 25 KB compressed page is a tiny object, and the blob store chapter warned that per-object overhead then outweighs the data; a content_key looks like pages/n07/f31@88123. The links table feeds an offline job that scores importance: a page linked from many different sites is probably worth fetching first, so that score becomes one input to the frontier's priority.

Now put the pieces in motion. Split the web across crawler nodes by host: each host name is hashed onto a ring with virtual nodes, as in the key-value store chapter, and the node that owns it runs the whole loop for it. All the state for one host lives on one machine: its queue, its politeness timer, its robots.txt rules and its DNS answer, so two machines can never hit the same site at once by accident.

The scene follows one URL from news.example.in around a node's loop. The danger it shows is waste: most links on a page are ones the crawler already knows, and some pages are copies of others.

The seen check is the frontier's gatekeeper: without it, every page would re-add dozens of known URLs and the frontier would grow without end. The fingerprint check does the same job for content, so the page store holds one copy of the report.

Every node runs this loop on its own slice of the web, sending links for hosts it does not own to their owners in batches every second or so. A URL handed to a fetcher is marked in flight with a deadline, like the visibility timeout in the message queue chapter; if the fetcher dies, the URL is handed out again, and fetching a page twice is harmless. The scene glossed over one question: which URL should the frontier hand out next, and when may a host be visited again?

Think of a teacher taking questions from a crowded class: the most urgent go first, but no single student may ask ten in a row. The frontier is not a first-in, first-out queue. A large share of the links on a news.example.in page point back into the same site: menus, related reports, footers. Queue them in a row and the fetchers either hit that one site in a burst or sit idle waiting for it while thousands of other sites are ready. So the frontier answers two separate questions: what to fetch first, and when each host may be visited again.

Each host's gap follows one rule: the largest of 1 second, the site's Crawl-delay if it sets one, and 3 times its last response time. A server that slows down is probably busy, so the crawler backs off without being told. It is the rate limiter chapter's idea turned around: we limit ourselves, per host, before the site has to.

That rule fixes the missing number from the estimates. A typical 1 s fetch earns a 3 s gap, so each host yields about one page every 4 seconds, and 1,160 pages a second needs over 4,600 hosts in rotation at once; keep about 10,000 active. Speed comes from breadth, never from hitting one host harder. The cost is depth: even at one page a second, a site with 10 M pages takes about four months, so its home and section pages go before its archives.

The rule is simple on a quiet day. The final is not quiet: news.example.in slows down, then starts refusing requests, while 1,240 of its URLs wait in its back queue and two fetchers want work.

The heap turned one host's trouble into a longer wait for that host alone: the fetchers never idled, and the news site saw at most one request at a time, spaced further apart as it struggled. A 503 or 429 doubles the gap and honours any Retry-After the site sends; after repeated errors the host is paused and an operator alerted.

Two more limits guard the same promise. Thousands of small sites can share one server, so the frontier also limits requests per IP address. And a host that moves to another node after a crash is treated as just fetched, so a hand-over never gives a site two quick visits.

The frontier only works if it holds each page once. Duplicates come in two kinds. URL duplicates are one page reached through different spellings of its address; content duplicates are the same text at different URLs. This page handles the first kind, caught before a URL enters the frontier.

found:      HTTPS://News.Example.in:443/sports/../scores/?utm_source=app&b=2&a=1#live
normalised: https://news.example.in/scores/?a=1&b=2

Lowercase the scheme and host, drop the default port, resolve . and .., drop the #fragment and tracking parameters, then sort what is left.

The parser first resolves each href against the page's own address and drops mailto: and javascript: links. Normalising each link then turns many spellings into one. Leave the path's letter case and trailing slash alone: many servers treat /Scores and /scores as different pages. A <link rel="canonical"> tag, when present, names the address the site prefers.

Then comes the seen set: every URL the crawler has ever queued, checked 58,000 times a second. Four ways to hold 10 B URLs:

Every option trades memory for pages silently skipped.

A Bloom filter, met in the key-value store chapter, is a bit array plus several hash functions; if a lookup finds any of a URL's bits unset, the URL is definitely new. A new URL whose bits all happen to be set is skipped until the filter is rebuilt. At our scale 8-byte hashes fit in memory across ten nodes, so we use them; at ten times the scale the filter starts to pay.

Normalising cannot tell that news.example.in/scores and news.example.in/print/scores hold the same report, or that a wire story appears on fifty sites. Those are content duplicates, caught after the fetch, by the parser. They waste disk and, worse, their links flood the frontier with more copies.

For exact copies, hash the page's extracted text, not its raw HTML, so a changed advert or timestamp in the markup does not matter. Equal hashes mean an exact copy: store a pointer to the first copy in the content table and skip its links. That is what happened to the print page in the crawl loop scene.

Near-copies defeat an ordinary hash. Change one character, such as an "updated 10:47" line under the match report, and the whole hash changes. A similarity fingerprint such as SimHash handles them. The intuition: let every short run of words vote, so a few changed words cannot outvote the rest. The mechanism: each run of words is hashed to 64 bits and votes +1 or −1 on each bit position; the fingerprint keeps the sign of each total. Similar pages get fingerprints that differ in only a few bits, and this design treats pages within 3 bits as duplicates.

Finding those among billions of fingerprints needs one more trick. Split each fingerprint into four 16-bit blocks. Two fingerprints within 3 bits must match exactly on at least one block, because 3 differing bits cannot touch all four. So keep four lookup tables, one per block, fetch only the fingerprints that share a block, and compare those bit by bit.

The threshold is the trade-off. At 3 bits, two different reports of the same match, sharing a scorecard and little else, stay separate; raise it to 10 and the crawler starts throwing away genuinely new pages. Copies are now caught. The next danger is pages that are not copies, yet never stop coming.

Some sites generate URLs without end, by accident or on purpose. A crawler trap is any part of a site that keeps producing new URLs while adding little new content. Every one of those URLs passes the seen check, because it really is new, so without limits the frontier fills with one site's junk:

The defences share one idea: a site gets a budget, not a blank cheque.

The per-host budget is the frontier's last line of defence, and it is set by importance: news.example.in earns a large budget, a site nobody links to a small one. Traps waste the budget on new URLs. The other claim on it is old URLs that need fetching again.

A stored page goes stale the moment its site changes it. The frontier must decide when each page is fetched again, without wasting fetches on pages that never change. Each page keeps a refresh_interval. After every fetch, compare the content fingerprint with the last one: if the page changed, halve the interval, down to an hour; if not, double it, up to about 60 days. Important pages get a lower ceiling, so a top news site's pages are re-fetched at least daily. Here is where that rule settles for four kinds of page:

The rule spends fetches where pages change and starves pages that do not, with no list for anyone to maintain.

An hour is too slow for the final, so the busiest news sites get more: a floor of a few minutes for their home pages, and polling of their feeds and news sitemaps, which list new URLs with a time. That is how the new match report is found within minutes. At one request every 4 s or more, polling one host every few minutes is still gentle.

Two HTTP features make refreshing cheap. Send the ETag or Last-Modified value from the last fetch back as If-None-Match or If-Modified-Since, and an unchanged page comes back as a 304 Not Modified with no body. The deep dives are done; next, what fails when this runs for months.

A crawler runs for months, so everything on this page will happen sooner or later. The goal each time is the same: lose little work, and never take a problem out on someone else's website.

Almost every row ends the same way: the frontier is restored or slowed, and no site pays for our failure.

Growth shifts the balance. At ten times the scale, 1 B pages a day, the fetch rate is about 11,600 pages a second and the frontier needs more than 46,000 hosts in rotation at once. The 8-byte hash set grows to 800 GB for 100 B URLs, and a 1% Bloom filter at about 120 GB starts to look attractive.

Three tensions run through every choice in this chapter. Each one is a dial on the frontier:

• Coverage against freshness. Every refresh is a fetch not spent on discovery. Set the split explicitly, such as 70% refreshes and 30% new pages, and watch both.
• Speed against politeness. Politeness does not grow with your hardware: extra speed must come from more hosts in parallel, never from hitting one harder.
• Plain HTML against rendering. A headless browser sees content that JavaScript builds, at many times the CPU per page, so only pages that need it go to a separate, smaller pool.

Fetchers in more than one region. A node in Mumbai fetching a site served from the US east coast waits about 200 ms per round trip, several round trips per page, and pulls every byte over long, costly links. So run crawler nodes in three or four regions and give each host to the region nearest its servers, judged from its IP address. A host still belongs to exactly one node, so politeness holds, and links for hosts owned elsewhere travel to their owners in batches, as before.

What dominates the bill: storage. It is not the hard part, but it grows every month: a year of pages, about a petabyte, costs on the order of $20,000 to $30,000 a month at object-storage prices (check current prices), while ten fetch nodes cost far less. Rendering JavaScript would change that, since a headless browser needs many times the CPU per page.

Optional: the fetch details behind the loop, for when you need to know exactly how robots.txt and HTTP replies are handled.

Every fetch needs the host's IP address. As the DNS chapter showed, a cold lookup often takes 50 to 150 ms, and a shared resolver may not welcome 1,500 queries a second from one client. So each node runs its own caching resolver that keeps answers for their TTL, caches "no such name" too, and looks a host up just before its turn.

Every host has its own robots.txt, a plain-text file at its root that says which paths crawlers may visit; fetch it before the host's first page and keep it for up to a day, as the standard published in 2022 as RFC 9309 recommends.

# https://shop.example.in/robots.txt
User-agent: *
Disallow: /cart/
Disallow: /search
Allow: /search/help
Crawl-delay: 2

Sitemap: https://shop.example.in/sitemap.xml

Crawl-delay is not part of the standard, but some crawlers honour it, and ours does.

Three details catch people out. The longest matching rule wins: /search?q=shoes is blocked by Disallow: /search, but /search/help is allowed because Allow: /search/help is the longer match. A group for your crawler's own name replaces the * group instead of adding to it. And a 4xx for robots.txt means no rules apply, while a 5xx or a timeout means treating the whole site as off limits for now. Each HTTP reply then tells the frontier what to do:

Errors that blame the site slow the host down; errors that blame the page only reschedule the URL. Finally, send a user-agent such as ExampleBot/1.0 (+https://example.in/bot) linking to a page that explains the crawler, and crawl from published IP addresses, because many owners block crawlers they cannot identify.

A 45-minute interview leaves about 40 minutes of design. Here is the crawler on that clock.

Pick the frontier if they ask how you stay polite or what gets fetched first. Pick de-duplication if they ask how to check billions of URLs or spot the same article on many sites. If they ask about freshness, use the halve-or-double refresh rule.

Each question changes one thing about the crawl. Answer it before you open it.