Design a Web Crawler

Clarify the problem

The interview question is to design a web crawler.

A web crawler is a service that fetches pages from across the web. It follows links from page to page, like a reader who never sleeps.

Its customer is a search system. The crawler fetches, and the search system indexes what the crawler brings back.

Discovering pages is in scope. Fetching pages is in scope.

Extracting links and text is in scope. Revisiting for freshness is in scope.

Ranking results is out of scope. Answering searches is out of scope.

What the crawler must do

The crawler must discover pages. Starting from known pages, it extracts the links on each page and adds new addresses to visit.

The crawler must fetch each page and extract its text. Text is what the search index is built from.

The crawler must revisit pages. A page fetched once goes stale as its content changes.

The crawler must behave well on other people's sites. It is a guest on servers it does not own.

What stays out

Ranking stays out of scope. Deciding which page best answers a search is the search system's problem.

Answering searches also stays out. No user waits on the crawler directly, which shapes its whole design.

Pages a site asks crawlers not to fetch stay out. The crawler honours those requests, and politeness rules govern that behaviour.

How well it must work

Coverage must be wide. A search index built from a narrow crawl misses what users look for.

Freshness must be reasonable. Important pages should be revisited soon after they change.

Good behaviour is a hard limit, not a nicety. A crawler that overloads a small site harms a stranger and gets itself blocked.

The crawl target for this design is 50,000,000,000 known pages. That figure is a stated estimate, and the scale design builds on it.

The crawler fetches 1,000,000,000 pages a day in this design. The tension between the target and that rate runs through the whole design.

The crawl frontier

The crawl frontier is the heart of the crawler.

The crawl frontier is the stored set of web addresses waiting to be fetched. It also holds the order in which they will be visited.

Everything else serves the frontier. Fetchers empty it, and fetched pages refill it with newly found links.

The seed list holds known starting addresses.

Per-site queues hold addresses grouped by site.

Priority order means important pages are fetched sooner.

The seen set holds addresses already queued or fetched.

Fetcher hand-out means work is given with a site delay.

How addresses arrive

The crawl starts from a seed list. A seed is a known address chosen as a starting point for discovery.

Each fetched page adds more addresses. In a worked example, one page yields 10 new addresses on average, a stated assumption for the example.

1,000,000,000 pages fetched a day × 10 new addresses = 10,000,000,000 addresses discovered a day in this example.

Most discovered addresses are already known. A seen set records every address queued or fetched, so the frontier does not fill with repeats.

Checking the seen set is constant work. It sits in fast storage and answers before any address is queued.

Order inside the frontier

The frontier is split into per-site queues. A site is all the pages under one host name, and each site gets its own queue.

Fetchers draw from many site queues in turn. No fetcher takes two pages from the same site back to back.

Priority orders the queues. Pages that change often, and pages many other pages link to, are fetched sooner than quiet pages.

Priority is a judgement, not a fact. The frontier stores a score per address, and the scoring can improve without redesigning the queues.

The fetching rate

The design fetches 1,000,000,000 pages a day.

1,000,000,000 pages ÷ 86,400 seconds = 11,574 pages fetched per second.

The frontier must hand out work at that rate without losing order. It is a queue at very large scale, sharded by site so many workers can draw from it at once.

Sharding by site has a second benefit. All decisions about one site, including how fast to fetch it, live in one place.

Where the frontier breaks

One giant site can dominate the frontier. Its queue grows while small sites wait, so the hand-out rotates fairly across queues.

A fetcher can die holding an address. The frontier leases each address out, and an address not reported back in time returns to its queue.

A lease here is a time-limited claim on one job. It stops two fetchers doing the same fetch while keeping lost work recoverable.

Politeness and traps

Politeness and traps are about the sites being crawled, which the crawler does not control.

Politeness is the set of limits a crawler puts on itself so it never burdens the sites it visits. The limits exist because the crawler is a guest on other people's servers.

A crawler without limits is a hazard. At this crawl rate, careless fetching can act like an attack on a small site.

The delay per site means fetches from one site stay spaced out.

One fetch at a time per site means no parallel hits on one host.

Honouring site rules means forbidden pages are never fetched.

An honest identity means sites can contact the operator.

Back-off on errors means a struggling site is left alone.

The per-site delay

The frontier releases one site's addresses slowly. In this design, a site is fetched at most once every 10 seconds, a stated choice.

60 seconds ÷ 10 seconds = 6 fetches a minute from one site at most.

86,400 seconds ÷ 10 seconds = 8,640 fetches a day from one site at most.

The overall crawl stays fast because thousands of sites are in rotation. Slowness per site and speed overall are both true at once.

Only one fetch runs against a site at a time. A second fetcher wanting that site waits for the delay, however idle it is.

Rules and identity

Many sites publish rules for crawlers. The rules name the parts of the site that crawlers must not fetch.

The crawler reads a site's rules before fetching from it. A forbidden address is dropped from the frontier, not fetched and not retried.

The crawler also names itself honestly in each request. A site operator who sees a problem can then find and contact the crawler's operator.

When a site returns errors, the crawler backs off. Backing off means waiting longer between attempts, and a site that keeps failing is parked for a later day.

Traps

A trap is a set of pages that generates endless new addresses. A calendar that links to the next day forever is the classic shape.

A trap wastes the crawl budget. Every fetch inside it returns a page nobody searches for, plus more trap addresses.

Generated addresses share patterns. The same path with a changing date is a pattern the frontier can learn to distrust.

The design caps depth per site section. Past the cap, new addresses from that section are queued at the lowest priority or dropped.

The design also caps pages per site. A site yielding far more addresses than its size suggests is treated as a suspected trap and reviewed.

Where politeness breaks

Strict delays slow discovery on huge, well-provisioned sites. Those sites can be given shorter delays, by agreement or by their published rules.

Loose delays risk real harm. The default stays strict, and exceptions are earned per site, never global.

Politeness is therefore a per-site setting, stored with the site's queue. One policy for the whole web fits nobody.

Design the data model and storage

The data model and storage start with deduplication, because storing repeats would waste most of the storage budget.

Deduplication is spotting that a page, or its content, has been seen before, so it is not stored or indexed twice. The web repeats itself constantly, through copied pages, mirrors and shared templates.

The crawler checks twice. It checks the address before fetching, and the content after fetching.

Extracted text is stored at 10 KB per page. The index share is 5 KB per page.

A content fingerprint is 8 bytes. The address and fetch record is a short record.

Same address, written differently

One page can be reached by several addresses. Capital letters, a trailing slash or tracking parameters can all point at the same page.

So addresses are normalised before the seen set is checked. Normalising means rewriting an address into one standard form, with one spelling per page.

A normalised address that is already in the seen set is dropped. No fetch is spent on it.

Normalising is delicate work. Rewriting too eagerly can merge two different pages, and those pages then vanish from the index.

Content fingerprints

Different addresses can still hold identical content. Address checks cannot catch that, so the content itself is checked.

A content fingerprint is a short value worked out from a page's content, which changes when the content changes. It works like a checksum for the whole page.

The fingerprint is taken over the extracted main text. Page furniture such as menus and adverts is left out, so the same article on two layouts still matches.

A fetched page whose fingerprint is already stored is a duplicate. Its address is recorded against the existing page, and its text is not stored again.

Near-duplicates are harder. Pages that differ in a line or two get different fingerprints, and the index, not the crawler, decides how to group them.

Storage arithmetic

An average fetched page is 100 KB. Most of that is markup and scripts, which the index does not need.

1,000,000,000 pages × 100 KB = 100 TB fetched a day.

In this design, the extracted text kept per page is 10 KB, a stated assumption. The index share kept per page is 5 KB, also a stated assumption.

1,000,000,000 pages × 10 KB = 10 TB of stored text a day.

1,000,000,000 pages × 5 KB = 5 TB of index growth a day.

10 TB + 5 TB = 15 TB of new stored data a day. Extraction is the saving, because keeping text and index cuts storage to a fraction of the fetched volume.

The full set, stored

One full crawl covers 50,000,000,000 pages. The fingerprint store alone shows the scale of even the smallest per-page item.

In this design a fingerprint is 8 bytes, a stated choice.

50,000,000,000 pages × 8 bytes = 400 GB of fingerprints for the full set.

50,000,000,000 pages × 10 KB = 500 TB of stored text for the full set.

Even a tiny per-page cost becomes a fleet problem at this count. Every stored field must earn its place.

Deep-dive scaling and freshness

Scaling and freshness pull against each other, because every revisit is a fetch that could have discovered a new page.

Freshness is how recent the crawler's copy of a page is compared with the live page. A page that changed yesterday and was fetched last month is stale in the index.

The design must choose, page by page, how much staleness is acceptable. That choice is the freshness policy.

Sizing the fetcher fleet

The crawl must sustain 11,574 pages fetched per second. That rate came from the daily target divided by the seconds in a day.

In a worked example, one fetcher completes 20 fetches per second. That rate is a stated assumption, held down by per-site delays and slow servers.

11,574 pages per second ÷ 20 fetches per second per fetcher = 579 fetchers, rounded up.

The fleet is sized above that figure in practice. Failed machines and slow regions must not drop the crawl below its daily target.

Fetchers are stateless workers. Any fetcher can take any site queue, so a replacement starts work at once.

The full cycle

The known set holds 50,000,000,000 pages. The daily rate is 1,000,000,000 pages.

50,000,000,000 pages ÷ 1,000,000,000 pages a day = 50 days for one full crawl.

A flat policy would revisit every page on that cycle. News pages would sit stale for weeks under such a policy.

So the crawl budget is not shared evenly. Freshness is bought where change and importance are, and spent nowhere else.

Revisit tiers

Pages are grouped into tiers by how fast they change and how much they matter. The tiers are listed in the table.

In a worked example, a fast-changing set of 100,000,000 pages is revisited daily. That set is a stated figure for the example.

100,000,000 pages ÷ 1,000,000,000 daily fetches × 100 = 10 percent of the daily budget spent on that tier.

Change is measured, not guessed. Each revisit compares the new content fingerprint with the stored one, and pages that changed move up a tier.

Pages that never change drift down. Their revisit gap widens until it matches their real behaviour.

Where scale breaks freshness

A big news event makes many pages change at once. The frontier promotes them, and ordinary revisits slip behind.

That slip is the right failure. Fresh copies of quiet pages matter less than fresh copies of the pages everyone is reading.

A fetcher region can also fail. Its site queues are picked up by other regions, and the per-site delays still hold, because they live with the queues.

Evaluate the design

Evaluation means judging the crawler against its ask. A trade-off is a choice that gains one quality by giving up another.

The ask was wide coverage, reasonable freshness and good behaviour on other people's sites. The design's tensions all sit between those three aims.

50,000,000,000 pages ÷ 1,000,000,000 pages a day = 50 days for one full crawl.

That single figure explains most choices in this design. The budget never covers everything, so everything is a priority decision.

Strict per-site delays gain sites that stay unharmed. Discovery per site is slower.

Tiered revisits gain fresh important pages. Quiet pages go stale.

Aggressive dedup gains far less storage. It risks merging distinct pages.

Storing text, not raw pages, gains a fraction of the storage. No exact original remains to recheck.

Coverage against freshness

Every fetch is either a discovery or a revisit. Discovery widens the index, and revisits keep it honest.

The design favours a mix, set by tiers. A crawl that only discovered would rot, and a crawl that only revisited would never grow.

The balance can move. A young index should discover more, and a mature index should revisit more.

Politeness against speed

Per-site delays leave fetcher capacity idle. That idle time is the visible price of not harming strangers' servers.

The design pays it without apology. A blocked crawler loses a whole site, which costs far more coverage than the delays ever did.

Speed is recovered across sites instead. Thousands of queues in rotation keep the fleet busy while each site rests.

Dedup against safety

Aggressive deduplication saves large amounts of storage. It risks merging pages that are merely similar, and a merged page disappears as its own result.

The design dedups on exact fingerprints only. Near-duplicates are left for the index to group, where a mistake is easier to undo.

That is the general pattern of this design. The crawler makes the cheap, safe decision, and harder judgements are handed to the system built for them.

What would change the design

A much smaller web would change everything. A single-machine crawler with one queue is the right design at small scale, and this fleet would be waste.

A freshness-critical customer would change the tiers. If the index served breaking news first, the fast tier would grow and quiet pages would wait far longer.

Spend a fixed fetch budget by priority, behave as a guest, and never store the same page twice.

Revisit tiers in this design