Appearance
11.12 — Web Crawler & Search Engine
A publisher writes to say your crawler took their site down. You check the logs: your fetchers were each sending one request per second to that host, exactly as configured. There were forty fetchers. The host received forty requests a second for eleven hours.
That is the characteristic failure of a crawler, and it explains why this study is different from everything before it. A crawler runs almost entirely on other people's infrastructure, with their tacit permission, and that permission is revocable — technically, by blocking you, and legally, by writing to your lawyers. Politeness is not an ethical decoration on the design. It is the licence to operate, and it has to be structural rather than configured, because anything configured will eventually be configured wrong by forty machines at once.
There are two systems on this page. A crawler that fetches billions of pages without hurting anyone, and a search engine that answers an arbitrary query over ten billion documents in a few hundred milliseconds. The second is where the read path finally stops being a lookup and becomes a real algorithm.
1. Requirements
Functional. Discover and fetch pages continuously. Respect each site's stated crawling rules and per-host limits. Detect duplicate and near-duplicate content. Extract text and links. Build a searchable index. Answer ranked keyword queries.
Non-functional, with numbers.
- Crawl 1 billion pages a month.
- Recrawl pages at a rate matched to how often they change.
- Search p99 under 300 ms over a 10-billion-document index.
- Never overload a host. Not "rarely" — this is a hard constraint with a business consequence attached.
Out of scope today: running a browser to render pages that build their content with scripts (section 6.5 says honestly what it costs), ranking sophistication beyond the basics, and personalisation.
The clarifying questions, and what each answer changes
"Are we crawling the open web, or a defined set of sites we have an agreement with?" The open web means politeness, traps, blocks and legal exposure. A partner set means you can be told the update schedule and skip most of the crawler's difficulty. These are different projects.
"How fresh must the index be?" Hours is a batch pipeline. Sixty seconds is a completely different architecture, and the drill at the end of this page designs it — the answer is not to make the batch index faster.
"How many terms in a typical query?" Two or three changes the shape of query execution: intersecting posting lists is where the work is, and the number of lists to intersect is the main input to that cost.
"Do we need exact result counts?" "About 4,120,000 results" is an estimate, and it can be, because computing an exact count means walking the entire posting list rather than the top of it. Establishing that early saves a lot of work.
"What happens when a site asks us to stop?" The answer must be "immediately and permanently, through a documented channel". Establishing that this is a requirement rather than a courtesy is what makes section 6.1's machinery worth building.
2. Estimation
Fetch rate. 1 billion pages a month ÷ 2.6 million seconds = ~400 pages a second sustained. Roughly 30% of fetches fail, redirect or return non-content, so budget ~600 requests a second. What that forces: not a throughput problem. Six hundred requests a second is nothing for a fleet. The difficulty is entirely in which six hundred and to whom — politeness, not capacity.
Raw storage. ~100 KB a page, compressing to ~25 KB = 25 TB a month, about 300 TB a year. What that forces: object storage with a retention policy. The raw page is kept because reprocessing is common — a parser improvement should not require recrawling the web.
Extracted text. ~5 KB a page = 5 TB a month, and this is what the index is built from. What that forces: the text is twenty times smaller than the page, which is why every stage after parsing works on text and never touches the original bytes again.
Index size. 10 billion documents × ~500 distinct terms each = 5 trillion postings; compressed to a few bytes each, that is tens of terabytes. What that forces: far beyond one machine, so the index is sharded — and section 6.6 shows that how you shard it is the single most consequential decision in the search half of this study.
The fan-out consequence. With the index sharded by document, every query touches every shard. With 100 shards and a per-shard p99.9 of "slow", the chance a query hits at least one slow shard is 1 − 0.999¹⁰⁰ ≈ 9.5%. What that forces: a rare slow response becomes a common slow query. This arithmetic is why section 6.7 exists, and it is the most important number on the search side.
Seen-URL memory. 10 billion URLs in a Bloom filter — a compact structure that answers "have I seen this?" with occasional false positives and never a false negative — at about 10 bits each = 12.5 GB. What that forces: the whole seen-set fits in memory on one machine, which is what makes duplicate suppression free. And the direction of the error is right: a false positive means skipping a page you have not actually crawled, which costs a little coverage, whereas a false negative would mean crawling something twice.
3. API
The crawler has no public API worth designing. The search side does.
http
GET /search?q=distributed+consensus&page=1&limit=10&lang=en
→ 200 OK
{ "query": "distributed consensus",
"estimatedTotal": 4120000,
"tookMs": 84,
"results": [
{ "url": "https://…", "title": "…", "snippet": "…<em>consensus</em>…",
"score": 18.4, "crawledAt": "2026-07-29T04:11Z" } ],
"shardsQueried": 100,
"shardsAnswered": 100 }estimatedTotal is honest about being an estimate. Producing an exact count means walking the whole posting list; producing an estimate means reading its length and adjusting for the intersection. Nobody looks at result four million, so the field says estimated in its name and the product shows "about".
shardsAnswered is the field that earns its place during an incident. When it reads 97 of 100, the results are slightly incomplete because three shards missed their deadline — and section 6.7 explains why returning slightly incomplete results is correct rather than shameful. Without this field, a partial result and a complete one are indistinguishable, and you will spend an afternoon proving that a missing page was never indexed when in fact its shard timed out.
Pagination is by page number here, not by cursor, which is one of the few places in this Part where offset is right. The result set is a ranked list computed fresh for each query rather than a mutating feed, deep pages are almost never requested, and users expect to jump to page three. The cost is that deep pagination gets expensive — which is why the depth is capped, and why nobody notices.
4. Data model
pages -- crawl metadata, partitioned by host hash
url_hash BYTEA PRIMARY KEY
url TEXT
host TEXT
last_fetched TIMESTAMPTZ
last_changed TIMESTAMPTZ
change_period INTERVAL -- observed, drives recrawl scheduling
content_hash BYTEA -- exact-duplicate detection
simhash BIGINT -- near-duplicate fingerprint
status SMALLINT -- ok | redirect | error | blocked | excluded
importance REAL
raw_pages -- object storage, not a database
/pages/{url_hash[0:2]}/{url_hash}.gz
frontier -- see section 5; per-host queues, leased work
host → [ { url, priority, earliest_fetch_at } ]
index segments -- immutable files, sharded by document
term → posting list: [(doc_id, term_frequency, positions…), …]Access patterns:
| Query | Frequency | Returns |
|---|---|---|
| "Is this URL seen?" | ~5,000/s | a boolean, from the Bloom filter |
| Next due host and its URL | ~600/s | one URL |
| Write crawl metadata for a page | ~400/s | — |
| Look up a near-duplicate candidate | ~400/s | a handful of candidates |
| Fetch posting lists for a term | ~1,000/s × terms × shards | a compressed list |
pages is partitioned by host hash, and that choice is doing more work than it appears. Every URL for one host lives on one node, which is what makes per-host politeness enforceable without cross-node coordination — the node that owns a host also owns its rate budget, so there is nothing to synchronise. This is the same reasoning that made geography the partition key in 11.10: partition by the thing that owns the constraint.
The index is sharded by document, not by term. Section 6.6 argues it properly, but the model reflects it: each shard holds a complete index over its own subset of documents, so it can score and rank locally.
Index segments are immutable files. New documents create new segments; deletions write a tombstone rather than modifying anything; a background process merges small segments into larger ones. Nothing is ever updated in place, which is what makes reads lock-free and crash recovery trivial (10.5).
5. The crawler
6. Deep dives
6.1 Politeness, made structural
The failure at the top of this page happened because politeness was enforced per fetcher rather than per host. Forty machines each obeying a one-per-second limit produced forty per second at the host, and every one of them was correct by its own configuration.
The fix is that the rate lives with the host, not with the fetcher. All URLs for a host live in one queue on one node — which is why pages is partitioned by host hash — and the only way to obtain work is to pop the host whose earliest-fetch time has arrived. There is no code path that can fetch a host early, because there is no code path that hands out a URL without going through its host's queue.
Three details that people get wrong.
Rate-limit on the resolved host, not the URL's hostname. Many hostnames often resolve to one server. Limiting per hostname while a site has forty subdomains produces the same forty-fold amplification in a different costume.
Treat a failure to read a site's crawling rules as "do not crawl", not "crawl freely". Failing open on the rules file is the single most common crawler defect, and it is exactly what produces a public complaint — you crawled a site that had explicitly told you not to, and your defence is that you could not parse their file.
Back off on the host's own signals. A host returning "too many requests" or "service unavailable" is telling you something, and the correct response is exponential backoff and a flag for human review, not a retry loop.
6.2 The frontier
Three guarantees, and the tension between them is the design.
Politeness — never exceed a host's tolerated rate. Priority — an important, frequently-changing page should be fetched sooner and more often than a decade-old static one. Coverage — recrawling what changes must not starve discovery of what is new.
The structure is two levels. A set of front queues implements priority: each URL gets a score from link authority, observed change rate and business importance, and lands in one of a handful of priority queues, sampled in proportion so that high priority dominates without ever starving the low. A set of back queues implements politeness: one queue per host, with a heap ordered by earliest-fetch time deciding which host is due next.
Four properties it needs that are easy to omit. It must be persistent, because it holds billions of URLs and losing it loses the crawl's memory. Work is leased rather than assigned, so a crashed fetcher's URLs return automatically after a timeout instead of vanishing. It is partitioned by host, which is what makes politeness enforceable without coordination. And it needs admission control, because the frontier grows faster than it drains — permanently. The web is effectively infinite, so an unbounded frontier is not a bug to be fixed but a condition to be managed with budgets and prioritisation.
6.3 Duplicates, which are about a third of the web
Exact duplicates are caught with a content hash. The same page served at many URLs — with and without www, with tracking parameters, through a print view — is a large fraction of what a crawler fetches.
Near-duplicates are harder and more common: two pages differing only in a timestamp, an advertisement, or a session identifier. The tool is a similarity fingerprint — a hash designed so that similar documents produce similar fingerprints, differing in only a few bits, rather than the completely different values an ordinary hash would give. Comparing every new page's fingerprint against ten billion stored ones is impossible, so the fingerprints are indexed by splitting them into bands: two documents whose fingerprints agree on any whole band become candidates, and only those candidates are compared properly. That turns an impossible comparison into a lookup.
URL-level defences catch a lot before a fetch happens. Normalise the URL: sort query parameters, strip known session and tracking parameters, honour a page's own declaration of its preferred address. Then check the seen-URL Bloom filter — 10 billion URLs in about 12.5 GB — where a false positive means skipping a page you have not crawled and a false negative is impossible. That is the right direction for the error to point.
6.4 Traps, and why budgets beat cleverness
Some sites will generate links forever. A calendar with "next month" links has no last page. A faceted product search generates a URL for every combination of filters, which is exponential in the number of filters. Neither site is malicious; both will consume your entire crawl budget on one host if you let them.
Clever detection helps and budgets are what actually save you. Depth limits, a hard cap on distinct URLs per host, and detection of URL patterns that are structurally similar and mutually reachable. The budget is the one that matters, because it works against traps you have never seen — and new ones appear constantly.
6.5 Rendering pages that build themselves, honestly
A large share of the modern web puts its content on the page with scripts after the initial response arrives. A crawler that fetches and parses HTML sees an empty shell.
Rendering means running a real browser per page, which costs roughly ten times the processor time and memory of a plain fetch. Pretending otherwise is a common interview error.
The practical design is a two-tier crawl. Everything gets the cheap fetch. Only pages that meet a threshold — high importance, or a strong signal that the fetched content is incomplete — enter the render queue. The threshold is a tuning knob with a visible trade: raise it and you save enormous cost while missing content, lower it and you spend ten times more on pages that did not need it.
6.6 Sharding the index: by document, not by term
This is the most consequential decision on the search side, and the wrong answer is the one that looks efficient.
Sharding by term puts each term's whole posting list on one node. A two-word query then touches only two nodes, which sounds wonderful. It fails three ways. Load skew: common words have posting lists of billions of entries and are queried constantly, so those nodes melt while rare-term nodes idle — and no rebalancing fixes it, because the skew is a property of language itself. Network cost: computing "documents containing both A and B" means bringing the two lists together, and shipping a billion-entry list across the network per query costs far more than any computation it saves. Update cost: indexing one new document touches every node holding one of its five hundred terms.
Sharding by document gives each shard a complete, self-contained index over its own slice. Every shard scores and ranks locally and returns only its own top ten, so the network carries a handful of results instead of posting lists, load is even by construction, and indexing a document touches exactly one shard.
The cost is fan-out, and it is a real cost rather than a footnote: every query goes to every shard, so total work per query is high — and latency becomes the maximum over all shards rather than the average.
6.7 The tail-latency problem, with the arithmetic
With 100 shards, a query is only as fast as its slowest shard. If each shard is slow one time in a thousand, the probability that a query hits at least one slow shard is 1 − 0.999¹⁰⁰ ≈ 9.5%. A one-in-a-thousand event has become a one-in-ten experience (10.9).
Three mitigations, and they are part of the design rather than an optimisation.
Replicate and hedge. Each shard has replicas. If the first request has not answered within, say, the 95th-percentile time, fire a duplicate to a replica and take whichever returns first. Total work rises by a few per cent and the tail collapses.
Enforce a deadline and return partial results. A shard that misses its deadline is simply left out. A top-ten missing contributions from one of a hundred shards is almost always indistinguishable to the user — and shardsAnswered in the response is how you know it happened.
Keep per-shard work bounded and predictable. Latency that depends on the data is latency you cannot budget for, which is why the query executor caps how many candidates it will score.
6.8 Executing a query
Normalise. Lowercase, reduce words to their stems so that "running" and "runs" match "run", and drop words so common they carry no signal.
Fetch posting lists. One compressed list per term, sorted by document identifier.
Intersect. Finding documents containing all terms means walking the lists together. The lists carry skip pointers — periodic markers letting the reader jump ahead rather than examining every entry — so intersecting a short list with a long one costs roughly the length of the short one rather than the long one. That single structure is why a two-term query where one term is rare is fast.
Score. The standard scoring function rewards a document for containing the term often, rewards the term for being rare across the corpus, and penalises very long documents so that length alone does not win. On top of that sit query-independent signals: how many other pages link here, and how fresh the page is.
Take the top ten per shard, merge, then fetch snippets for the final ten only. Generating the highlighted extract is expensive, and doing it for a thousand candidates instead of ten is one of the easiest ways to blow the latency budget.
6.9 Recrawl scheduling
Not all pages deserve equal attention. A news homepage changes hourly; a paper from 2009 never will.
Track each URL's observed change frequency and schedule adaptively: pages that never change back off exponentially, pages that always change are polled at their cadence. Combine that with an importance signal so the budget flows toward pages that matter.
The payoff is worth stating in numbers: a fixed budget of a billion fetches a month, spent adaptively, produces far better coverage and freshness than the same budget spent uniformly — because uniform recrawling spends most of it re-fetching pages that are byte-identical to last time.
7. Decision Ledger
| Decision | Alternatives | Why this | What it costs |
|---|---|---|---|
| Per-host queues with an earliest-fetch heap | one global queue with a rate limiter | politeness becomes structural rather than configured | a more complex frontier; one slow host blocks its own queue |
| Partition crawl state by host | partition by URL hash | per-host rate enforcement needs no coordination at all | a host with millions of URLs is a large partition |
| Leased work, not assigned | assign URLs to fetchers | a crashed fetcher's URLs return automatically | leases expire, so a slow fetch can be duplicated |
| Similarity fingerprints with banded lookup | compare every pair; exact hashes only | catches the near-duplicate third of the web in one lookup | thresholds to tune; a false match drops a real page |
| Bloom filter for seen URLs | a database of every URL | 10 billion URLs in ~12.5 GB, in memory | false positives skip pages — the safe direction |
| Index sharded by document | sharded by term | even load, local ranking, small network payloads | every query fans out to every shard |
| Hedged requests plus deadlines | wait for every shard | a 9.5% slow-query rate becomes negligible | a few per cent more total work; occasional partial results |
| Immutable segments with background merging | update the index in place | lock-free reads, trivial crash recovery | deleted documents occupy space until merged |
| Two-tier rendering | render everything; render nothing | pay the 10× cost only where it earns something | some content missed; a threshold to maintain |
8. Scale and failure
At 10×, both halves partition cleanly — more crawl nodes by host, more index shards by document. Two further moves matter. Fetch from near the host, which lowers latency and often produces better regional content. And tier the index: a small hot index over popular documents answers most queries, with the full index consulted only when it must be. That is the same head-and-tail split that makes almost every system in this Part affordable.
| What breaks | Blast radius | How you find out | What keeps it running | Recovery |
|---|---|---|---|---|
| Fetcher crashes | its in-flight URLs | lease expiry rate | work is leased, so URLs return to the frontier | another fetcher picks them up |
| A host blocks us | coverage of that site, and reputation | per-host error and block rate | automatic backoff; flag for human review | a documented contact channel and a rate agreement |
| Rules file fails to parse | one host — potentially badly | parse-failure counter | treat as disallow, never as allow | fix the parser; the host is not crawled meanwhile |
| Trap consumes the budget | one host swallows the crawl | distinct URLs fetched per host | hard per-host budgets and depth limits | budget stops it even for an unseen trap type |
| Frontier grows without bound | it always does | frontier size, which only ever rises | admission control and prioritisation | this is a condition to manage, not a bug to fix |
| Index shard down | queries return slightly fewer results | shardsAnswered below the shard count | partial results plus replicas | restore the shard; the field tells you when it is back |
| Slow shard | ~9.5% of queries at 100 shards | p99 by shard, not aggregate | hedged requests and per-shard deadlines | replace the shard; hedging masks it meanwhile |
| Bad index build promoted | every query, immediately | canary queries before promotion | versioned snapshots, exactly as in 11.11 | roll back to the previous version |
The row that matters most is "a host blocks us", because it is the only failure here that is a business problem rather than a metric. The correct response is not to reduce a number in a configuration file. It is to have a per-host health dashboard that noticed before the publisher did, a documented crawl policy page with published address ranges and an identifiable agent string, and a contact channel through which a site can ask you to slow down or stop. A crawler that discovers it has been blocked by reading the news has a monitoring failure, not a politeness failure.
What the interviewer will push on
"How do you avoid overloading a site?" The wrong answer is "a rate limit". The right one is that the rate lives with the host, not with the fetcher, so all of a host's URLs sit in one queue on one node behind an earliest-fetch time and there is no code path that can fetch it early. Then volunteer the three ways this still goes wrong: limiting per node instead of globally, limiting per hostname when forty subdomains share a server, and treating an unparseable rules file as permission.
"Why shard the index by document when a term-sharded index touches only two nodes per query?" Because the two nodes it touches are the same two nodes for everybody. Common words produce billion-entry posting lists queried constantly, so load skew is intrinsic to language and no rebalancing helps; intersecting across nodes means shipping those lists over the network; and indexing one document touches every node holding one of its terms. Then name the cost you accepted — fan-out — rather than leaving it for them to find.
"Your search p99 is fine per shard but terrible overall. Why?" The arithmetic is the answer: with 100 shards and a per-shard slow rate of one in a thousand, about 9.5% of queries hit at least one slow shard. Then the three fixes — hedged requests to replicas, per-shard deadlines with partial results, and bounded per-shard work — and the observation that shardsAnswered is how you tell a partial result from a complete one afterwards.
"How do you handle near-duplicate pages?" Exact hashes catch the same page at many URLs, which is a large share of fetches. Near-duplicates need a fingerprint where similar documents produce similar values, indexed in bands so candidate lookup is a hash lookup rather than a comparison against ten billion. The tell is mentioning that comparing pairwise is impossible, because that is what makes the banding necessary rather than clever.
"Most of the web renders with scripts now. What do you do?" State the cost honestly — roughly ten times the resources per page — and then describe the two-tier crawl: everything gets the cheap fetch, only pages above an importance or incompleteness threshold get rendered. Candidates who say "we'd render everything" have not costed it, and candidates who say "we'd ignore it" have not looked at the web recently.
"The frontier keeps growing. When does the crawl finish?" It does not, and understanding that is the point. The web is effectively infinite and generates new URLs faster than you can fetch them, so the frontier is a prioritisation problem with budgets, not a queue to be drained. A candidate who treats completion as the goal will build a system with no admission control and be surprised by it.
Volunteer this, because nobody asks: a crawler runs on other people's infrastructure with their revocable permission. That single sentence justifies everything expensive in the crawl half of this design — the frontier's structure, per-host budgets, failing closed on unreadable rules, an identifiable agent string, published address ranges and a contact channel. It also reframes the monitoring requirement: the metric that matters is not pages per second, it is per-host error and block rate, because losing access to major sites costs coverage that no amount of engineering ever recovers.
Next: 11.13 — from indexing documents nobody is changing to a document two people are editing in the same second, where the hard problem stops being scale and becomes agreement.
Recall
- Politeness is structural, not configured. All of a host's URLs sit in one queue on one node behind an earliest-fetch time, so no fetcher can hit it early. Rate-limit on the resolved host, coordinate globally not per node, and treat an unparseable rules file as disallow.
- The frontier is two levels: front queues for priority (sampled in proportion), back queues one per host with an earliest-due heap for politeness. Persistent, leased rather than assigned, partitioned by host, and permanently under admission control — the web is infinite, so the frontier never drains.
- Duplicates: content hash for exact (a large share of fetches), similarity fingerprints indexed in bands for near-duplicates, plus URL normalisation and a seen-URL Bloom filter (10B in ~12.5 GB, false positives skip pages — the safe direction).
- Traps (infinite calendars, faceted search) are stopped by per-host budgets and depth limits, which work against traps you have never seen.
- Index sharded by DOCUMENT, not by term: term sharding has intrinsic load skew, ships billion-entry lists over the network, and touches every node per indexed document. The cost accepted is fan-out.
- Fan-out arithmetic: 100 shards × one-in-a-thousand slow = 9.5% of queries slow. Fixes: hedged requests, per-shard deadlines with partial results, bounded per-shard work. Report
shardsAnswered. - Query execution: normalise → posting lists → intersect using skip pointers → score (term frequency, term rarity, length normalisation, plus authority and freshness) → top-k per shard → merge → snippets for the final ten only.
- Immutable segments with background merging. Never updated in place, so reads need no locks and crash recovery is trivial.
- Adaptive recrawl by observed change rate × importance beats uniform recrawling on the same budget. Rendering costs ~10×, so two-tier: cheap fetch for all, render above a threshold.
Self-test: What structure makes politeness impossible to violate, and what are the three ways it still gets violated? Why document sharding despite fan-out, and what does fan-out cost in numbers? Name both deduplication mechanisms and what each catches. Why are index segments immutable? Why does the crawl never finish?
Quiz Bank
FoundationalDesign the URL frontier. What must it guarantee?
Three guarantees, and the tension between them is the design.
Politeness — never exceed what a host tolerates, honouring the delay a site states and backing off when it returns "too many requests". Priority — an important, fast-changing page should be fetched sooner and more often than a decade-old static one. Coverage — recrawling what changes must not starve the discovery of what is new.
The structure is two levels, each solving one of these.
A set of front queues implements priority. Each URL is scored — link authority, observed change rate, business importance — and routed into one of a handful of priority queues, which are sampled in proportion so that high priority dominates without ever completely starving the low. Sampling rather than strict ordering is deliberate: strict priority means the lowest queue is never read.
A set of back queues implements politeness. Each back queue holds URLs for exactly one host, and a heap ordered by earliest-fetch time decides which host is due next. A fetcher pops the earliest-due host, takes a URL from its queue, fetches it, and reinserts the host at now + that host's delay.
That structure is what makes politeness impossible to violate. A fetcher cannot hit a host early because the only way to obtain a URL is through that host's queue, and the queue only becomes available when its time arrives. Politeness stops being a rule someone might forget to apply and becomes the shape of the data structure.
Four further properties, all easy to omit and all necessary. The frontier is persistent, because it holds billions of URLs and losing it loses the crawl's memory of what it has planned. Work is leased rather than assigned, so a crashed fetcher's URLs return automatically after a timeout instead of disappearing. It is partitioned by host hash, which is precisely what makes per-host rate enforcement possible with no cross-node coordination — the node that owns the host owns its rate budget. And it needs admission control, because the frontier grows faster than it drains, permanently: the web is effectively infinite and generates new URLs faster than anyone can fetch them, so an unbounded frontier is not a bug awaiting a fix but a condition to be managed with budgets and prioritisation.
InterviewWhy shard the search index by document rather than by term, and what does that cost?
Term sharding puts each term's entire posting list on one node, so a two-word query touches only two nodes. That looks efficient and fails three ways.
Load skew. Common words have posting lists of billions of entries and appear in a large fraction of queries, so the nodes holding them are permanently saturated while nodes holding rare terms sit idle. No rebalancing fixes this, because the skew is a property of language rather than of your data distribution — it is the celebrity problem from 10.6 wearing different clothes.
Network cost of intersection. Finding documents that contain both A and B means bringing the two lists together. Shipping a billion-entry posting list across the network on every query costs vastly more than any computation it saves.
Update cost. Indexing a single new document means touching every node that holds one of its roughly five hundred distinct terms.
Document sharding gives every shard a complete, self-contained index over its own slice of the corpus. Each shard can intersect, score and rank entirely locally, returning only its own top ten — so the network carries a handful of small results per shard rather than posting lists, load is even by construction because documents distribute evenly, and indexing a document touches exactly one shard.
The cost is fan-out, and it is real. Every query goes to every shard, so total work per query is high. Worse, latency becomes the maximum over all shards rather than anything like an average, which turns a rare slow response into a common slow query: with 100 shards and a per-shard slow rate of one in a thousand, 1 − 0.999¹⁰⁰ ≈ 9.5% of queries hit at least one slow shard.
The mitigations are part of the design rather than an afterthought. Replicate each shard and hedge: if the first request has not returned by roughly its 95th-percentile time, send a duplicate to a replica and take whichever answers first — a few per cent more total work for a large reduction in the tail. Enforce a per-shard deadline and return partial results instead of failing, because a top-ten missing contributions from one shard out of a hundred is essentially always indistinguishable to the user. And keep per-shard work bounded — cap how many candidates get scored — so that latency is predictable rather than dependent on which terms were queried (10.9).
InterviewHow do you keep from re-indexing the same content over and over?
Three layers, applied in increasing order of cost, so that most duplicates are caught before anything expensive happens.
Before fetching: normalise the URL and check whether you have seen it. Sort query parameters into one fixed order, strip known session and tracking parameters, and honour a page's own declaration of its preferred address. Then check a Bloom filter of seen URLs — a compact structure that answers "have I seen this?" using about ten bits per entry, so ten billion URLs occupy roughly 12.5 GB and fit in memory. It occasionally says yes when the answer is no, which means skipping a page you never actually crawled, and it can never say no when the answer is yes. That direction is exactly the one you want: a little lost coverage rather than repeated work.
After fetching: hash the content. The same page is routinely served at many addresses — with and without a www prefix, through a print view, with a tracking parameter — and an exact content hash collapses all of them into one document. This alone accounts for a substantial share of what a crawler fetches.
After that: catch the near-duplicates, which is the harder and more common case. Two pages differing only in a timestamp, an advertisement or a session identifier are not byte-identical and are not worth indexing twice. The tool is a similarity fingerprint: a hash constructed so that similar documents produce similar fingerprints, differing in only a few bits, rather than the completely unrelated values an ordinary hash gives.
Comparing a new fingerprint against ten billion stored ones is impossible, so the fingerprints are indexed by splitting each into several bands and hashing each band. Two documents that agree on any whole band become candidates, and only those few candidates are compared properly. That converts an impossible pairwise comparison into a hash lookup, which is what makes the whole technique usable.
The cost worth naming: the similarity threshold is a tuning knob, and setting it too aggressively drops genuinely distinct pages — a product listing that differs from another only in the model number is not a duplicate, even though it looks like one to a fingerprint.
StaffYour crawler is being blocked by an increasing number of sites and a major publisher has complained publicly. Respond.
Immediately: stop the harm before diagnosing it. Reduce the global per-host rate ceiling and put the complaining publisher on an explicit very-low-rate list while you investigate. Crawling that site slowly costs almost nothing; continuing to hammer it during a public complaint costs a great deal. Then pull the logs for exactly what was sent to that host — request rate over time, concurrency, whether their rules file was fetched and whether it parsed, and what agent string you presented.
Within the hour: establish which of four causes applies, because they need different fixes.
Politeness broke. Look for the three classic bugs. The rules file was fetched but failed to parse, and the failure was treated as "allow all" — it must be treated as disallow for that host until a parse succeeds, and failing open here is the single most common crawler defect. Or the per-host limit was enforced per node, so ten crawl nodes each politely sent one request a second and the host received ten. Or the limit was keyed on the URL's hostname while forty subdomains resolve to one server, so the rate must key on the resolved host or address instead.
A trap amplified you. A faceted search or a calendar generated millions of URLs on one host, so even a perfectly polite per-URL rate became a sustained multi-day crawl of near-identical pages. The fix is per-host budgets and pattern detection, not a rate change.
You are not identifying yourself. A crawler must present an honest agent string with a URL explaining what it is and how to contact you, and it should operate from documented address ranges. Sites block anonymous high-volume traffic on principle, and they are right to.
They simply do not want to be crawled. That is their prerogative, and it must be honoured immediately and permanently through a documented path.
Within the day: fix the class rather than the instance. Build a per-host health dashboard — error rate, rate-limit responses, block detection — with automatic backoff and alerting, because the real finding here is that you learned about this from the news rather than from monitoring. Publish a crawl policy page with your address ranges and agent string. Create a contact channel with a fast path for a site to request a lower rate or removal. Add global rate coordination keyed on resolved address. And change the rules-file parser to fail closed.
The framing for leadership, said plainly: a crawler operates entirely on other people's infrastructure with their tacit and revocable permission. That permission can be withdrawn technically, by blocking you, and legally, by their lawyers. Politeness is not an ethical garnish on the design — it is the licence to operate, and losing it costs coverage that no amount of engineering ever recovers.
Flashcards
FlashFrontier structure
Front queues = priority, sampled in proportion. Back queues = one per host, selected by an earliest-due heap. Persistent, leased not assigned, partitioned by host. Politeness becomes structural.
FlashThe three ways politeness still breaks
Limiting per node instead of globally · keying on hostname when many subdomains share a server · treating an unparseable rules file as permission. All three produce a public complaint.
FlashDeduplication layers
URL normalisation + a seen-URL Bloom filter (10B in ~12.5 GB; false positives skip pages, the safe direction) → exact content hash → similarity fingerprints indexed in bands so candidate lookup is a hash lookup.
FlashIndex sharding
By document: even load, local ranking, small payloads on the wire. By term: intrinsic language skew, billion-entry lists over the network, every node touched per indexed document. Document sharding costs fan-out.
FlashFan-out tail arithmetic
100 shards × one-in-a-thousand slow ≈ 9.5% of queries slow. Fixes: hedged requests to replicas, per-shard deadlines with partial results, bounded per-shard work. Report shardsAnswered.
FlashIndex writes
Immutable segments; updates create new segments; deletions write tombstones; a background process merges. Never updated in place, so reads need no locks and crash recovery is trivial.
Scenario Drill
DrillThe product team wants search results to include content published in the last 60 seconds. The index rebuilds in batches every few hours. Design the path to real-time.
Do not make the batch index real-time. Add a second index and merge at query time. The batch index is large, immutable and heavily optimised for exactly the reasons that make it fast to query and slow to build. Converting it to accept per-document updates sacrifices all of that in order to serve a tiny fraction of the corpus.
The design is a real-time tier. New documents flow into a small index that accepts writes immediately — held in memory, flushed periodically into a small on-disk segment. Queries run against both the batch index and the real-time tier, and the coordinator merges the two result sets by score. This is the same slow-base-plus-fast-delta shape as the trending overlay in 11.11, applied to a much larger structure. Because the real-time tier only ever holds the last few hours of documents, it stays small enough to be fast even with a straightforward implementation.
Four hard parts, and the second is the one people miss.
Scores must be comparable across the two tiers. The standard scoring function depends on corpus-wide statistics — how rare a term is, how long an average document is — and those differ enormously between a ten-billion-document index and a hundred-thousand-document one. Merge naively and recent documents systematically out-rank or under-rank everything else. The fix is to compute the statistics from the batch corpus and apply them to both tiers, accepting slight inaccuracy for genuinely new terms in exchange for scores that can be compared at all.
The handoff must produce neither duplicates nor gaps. When a batch rebuild completes and includes documents the real-time tier already holds, those documents must leave the real-time tier atomically with the new batch index going live. Do it as a separate deletion and you get the same document twice, or — if the order is wrong — a window where it is in neither. The mechanism is a watermark: the batch index records the newest ingest timestamp it covers, and the real-time tier serves only documents newer than the currently live batch index's watermark. The handoff then happens as a consequence of the version swap rather than as a coordinated deletion that has to be got right.
Deletions are harder than insertions. A document deleted thirty seconds ago is still sitting in the batch index, which will not be rebuilt for hours. So the real-time tier must also carry a tombstone set applied as a filter over batch results — the same read-time filtering as 11.8, for the same reason: filtering a small result set beats rebuilding a large structure.
The fan-out cost rises. Every shard now queries two structures instead of one. That is acceptable because the real-time tier is small, but it must be counted inside the per-shard deadline, because the tail-latency arithmetic from section 6.7 does not get any friendlier.
What to push back on, before building any of it. Ask what "the last sixty seconds" is actually for. If it is breaking news, a small curated real-time vertical merged into results is far cheaper than making the whole corpus real-time. If it is user-generated content whose author expects to find it immediately, scoping the real-time tier to the author's own documents satisfies the real requirement at a fraction of the cost. Both of those answers are better engineering than the general solution, and neither is available once "real-time search" has been agreed as a requirement.
The sentence for the design document: freshness is bought per document, not per corpus — so the architecture is a small real-time index with a watermark handoff to an immutable batch index, and the requirements conversation should establish which documents genuinely need the expensive tier before anyone builds it.