09 — Design A Web Crawler

“Design a crawler that fetches a billion pages a month.”

A web crawler is a program that starts from a handful of known web addresses, downloads each page, extracts the links inside it, and repeats — forever.

One number decides the size and the shape of that system: how many pages per second you are allowed to take from a single web server. Derive that number first and every other decision follows from it — the queue layout, the shard key (the field whose hash decides which machine a given row is stored on, unpacked in Data model), the two duplicate filters, the guards against runaway URL spaces, and the re-crawl policy.

When you finish, you should be able to do three things: size a crawler from a blank page, explain to someone else why adding machines does not make it faster, and defend every structure in it with arithmetic instead of a diagram.

What goes in, and what comes out. The input is a seed set: a few thousand starting web addresses, hand-picked — the home pages of large sites, a directory dump, a previous crawl’s index. A web address is a URL, short for uniform resource locator, the https://example.com/path?q=1 string that names one document.

The output is a growing store of raw HTML documents, plus one metadata row per document. That row records when the page was fetched, the server’s version tag for it, a fingerprint of its content, and how fast it appears to change. Everything in between is scheduling.

Two words carry the whole chapter.

• Politeness is the unwritten contract a crawler owes a web server it does not own: open at most one connection to that server at a time, and wait a fixed gap between consecutive fetches from it, so that your crawl never looks like an attack.
• The frontier is the crawler’s to-do list — the set of URLs that have been discovered but not yet fetched, together with the machinery that decides which one to hand a worker next.

Every candidate reaches for threads, queues, and a bloom filter — a compact memory structure, defined and priced in Deep dive 2 url dedup and what a false positive costs, that answers “have I seen this URL before?”.

Almost nobody reaches for the number that actually sizes the system. You may open one connection to a host and you must wait between fetches, so throughput is not a function of your fleet — it is a function of how many distinct hosts you have URLs for right now. A host here means one web server, named by a hostname such as example.com.

Three mistakes lose the interview, and each one has a section below devoted to it:

1. Designing the frontier as one priority queue. That serializes politeness away — Deep dive 1 front queues and back queues.
2. Calling the URL-seen filter “a bloom filter” without pricing what its mistakes cost — Deep dive 2 url dedup and what a false positive costs.
3. Treating content deduplication as a SHA-256 hash of the page body, when a third of the web differs only by a rendering timestamp — Deep dive 3 content dedup where exact hashing has zero recall. Deduplication here means recognizing that a document you just fetched is one you already have, so you can drop it.

Three other chapters supply background this one uses and does not re-derive. Estimation discipline is chapter 02. The bloom-filter formula is derived in chapter 06. Splitting data across machines — partitioning, also called sharding — is chapter 05. You do not need to read any of them first; each idea is restated here in the sentence that needs it.

1. Framing: what decision, and what breaks

A crawler is a scheduler wearing an HTTP client. Downloading a page over HTTP, the request-response protocol the web runs on, is a solved problem you get from a library. Deciding which page to download next is the whole problem — and the design turns on one decision, how the frontier is organized.

Four forces constrain that decision at once, and any frontier design has to answer for all of them.

A CMS is a content management system — the software a site runs to publish pages, such as WordPress or Drupal. A session id is a per-visitor token some sites paste into the URL, so the same page hands you a different address every time you look at it.

Say this out loud in the first two minutes: “politeness is not a feature I add at the end, it is the constraint that decides the frontier’s data structure.” Everything downstream — the queue layout, the shard key, the fleet size — follows from the 0.833 pages/s per host computed in 3b the politeness ceiling the number that sizes everything.

Four things break in production, listed from most frequent to least:

1. A DNS resolver saturates. DNS, the domain name system, is the lookup that turns example.com into a numeric IP address. When it stalls, the fetchers idle at 5% utilization (Dns).
2. A single CMS generates 40 million calendar URLs and eats a week of crawl budget (Traps and the guards that are arithmetic rather than heuristic).
3. A shared-hosting IP address takes 4,000 requests per second, because politeness was keyed on the hostname rather than on the server behind it (3b the politeness ceiling the number that sizes everything).
4. The URL-seen filter passes the capacity it was sized for and begins silently discarding real pages (Deep dive 2 url dedup and what a false positive costs).

2. Requirements

Before any arithmetic, pin down what the crawler must do, what it deliberately will not do, and — in 2a the assumptions this design rests on — the assumptions every number later in the chapter stands on.

Functional

• Fetch pages starting from a seed set, extract links, and repeat.
• Store the raw document plus enough metadata to re-fetch it conditionally.
• Honor robots.txt, including Crawl-delay and Sitemap.
• Detect and skip duplicate and near-duplicate content.
• Re-crawl pages at a rate driven by their observed change rate.

Three of those bullets need glossing before they mean anything:

• robots.txt is a plain-text file every site may publish at its root — https://example.com/robots.txt — listing the paths crawlers may and may not fetch. Crawl-delay inside it asks for a specific number of seconds between your fetches. Sitemap points at a machine-readable list of the site’s URLs.
• A conditional re-fetch is a request that says “send me this page only if it changed since the copy I already have.” The server answers with either the full page or a tiny “not modified” reply.
• Near-duplicate content is two documents that are not byte-identical but say the same thing — a print view, a mirror, the same article with a different advertisement in the margin.

Out of scope, said explicitly: ranking, the search index itself, and running a full browser on every page to execute its JavaScript (Alternatives rejected prices that last one). Each is real work; none of it changes the scheduler, which is what this chapter is about.

Non-functional — the ones that settle the architecture

Three terms in that table need unpacking:

• A trap is a URL space that is infinite, or finite but enormous, and machine-generated. Traps and the guards that are arithmetic rather than heuristic is entirely about them.
• To DoS a server is to deny service to it: to send so many requests that real users cannot get through.
• last_fetch_at is the timestamp of the crawler’s most recent fetch from a given host. It is the only thing standing between a fleet restart and a simultaneous burst at every server the crawler knows about.

2a. The assumptions this design rests on

Every number in this chapter is downstream of a short list of assumptions. Naming them is not throat-clearing: an interviewer who changes one of the load-bearing ones changes the answer, and you want to be the person who notices out loud.

The last column of the table is the one to read carefully. “Load-bearing” means a design decision moves if that assumption moves; “No” means only a cost moves.

Three rows need a note each.

A8, the Poisson process. This is the standard model for “events that arrive independently at a constant average rate, with no memory of when the last one happened.” It is the assumption behind the freshness formula in Freshness re crawl driven by observed change rate and nowhere else.

A11 is not a second guess on top of A5. It is a reading of it. A5 says a page carries about 100 outbound links. A6 says novelty stays above 1%. A11 pins the working value between the two at 10%, which is ten genuinely new pages per page crawled.

A12 is a measurement, not a derivation, and it is worth flagging as such. Sanity-check it: 33 M page fetches a day spread over 1 M hosts is 33 pages per host per day. That is the shape of a broad crawl rather than a deep one, which is what a general web crawler is.

The four to say out loud are A1, A3, A4, and A5.

• A1 decides the architecture.
• A3 decides the bandwidth by a factor of twenty.
• A4 decides every capacity number.
• A5 decides that the frontier is a prioritization problem rather than a drainage problem.

A11 and A12 are the two to have ready when someone asks where the depth cap and the DNS numbers came from. The rest move costs around without moving a design decision.

3. Back of the envelope

The product hands you one number — a billion pages a month — and every other quantity the design needs comes out of it: pages per second, bandwidth, storage, the per-host fetch rate, and the fleet. Each block below feeds the next.

The 1e5 convention, and when to undo it

Rounding discipline is chapter 02, and the substitution it licenses is 86,400 -> 1e5.

There are 86,400 seconds in a day. Rounding that to 100,000 makes every division a shift of the decimal point, at the cost of about 16% of accuracy — far inside the error bars of anything else on this page.

But 1e5 is a drill convention, not a reporting convention. Ch 02 is explicit about the other half of the rule: divide by 1e5 while you are thinking, and divide by 86,400 the moment a number leaves your mouth as a result — a schedule, a fleet size, a utilization.

Here is the size of the distortion, worked out:

• The divisor 100,000 is 100,000 / 86,400 = 1.157, so it is 15.7% too high.
• Dividing by a divisor that is too high gives a quotient that is too low: 86,400 / 100,000 = 0.864, so the answer is 13.6% low.
• Every per-day and per-elapsed-time figure computed at 1e5 in this chapter is therefore flattering — it makes the crawler look faster than it is.

Five figures in this chapter are results rather than thoughts, so each is printed both ways below and both ways in the cheat sheet: the years to crawl one big site, the days under Crawl-delay: 10, the months to build the corpus, the pages per day one host yields, and the DNS resolver’s utilization. Where you see two numbers, the second one is the one you say to the interviewer.

3a. Volume, bandwidth, storage

Start with the product target and derive the request rate, then the bytes on the wire, then the bytes at rest.

The first block turns “a billion pages a month” into pages per second, average and peak. The x 2 at the end is assumption A9 — traffic is not flat over a day, and you size for the busy hour, not the mean.

pages per month                             1,000,000,000
pages per day
  1,000,000,000 / 30                     =  33,333,333
pages per second
  33,333,333 / 100,000                   =  333
peak, at 2x
  333 x 2                                =  666

Now the bytes, and the first place a candidate goes 20x wrong.

A typical web page is ~2 MB (ch 02). But that figure is the rendered page — everything a browser downloads to display it: images, fonts, scripts, stylesheets.

A crawler fetches the HTML document and nothing else. An HTML document compressed with gzip — the compression browsers and servers negotiate automatically — is about 100 KB on the wire.

Naming that distinction is worth a point on its own. A candidate who bills 2 MB per page is 20x over on bandwidth and will size a fleet that does not exist. This is assumption A3 from 2a the assumptions this design rests on, and it is the one an interviewer is most likely to poke at.

The next block multiplies the 100 KB by the page rates you just derived. Watch the last two lines: they convert bytes per second into megabits per second by multiplying by 8 bits per byte and dividing by a million, and then compare that against one network port’s capacity.

HTML document on the wire, gzipped, bytes         100,000
bytes per day
  33,333,333 x 100,000                   =  3,333,333,300,000
bytes per second
  3,333,333,300,000 / 100,000            =  33,333,333
the same in Mbps, at the 333 pages/s AVERAGE
  33,333,333 x 8 / 1,000,000             =  267
the same at the 666 pages/s PEAK
  666 x 100,000 x 8 / 1,000,000          =  533
fraction of one 1 Gbps NIC, at peak
  533 / 1,000                            =  0.533

Bytes at rest are smaller than bytes on the wire. A10 assumes the stored form is another 5:1 down from the 100 KB you received, so a page occupies 20 KB in the document store. The block below carries that through to a day, a month, a year, and then to the three copies you actually keep.

stored bytes per page, HTML recompressed 5:1
  100,000 / 5                            =  20,000
stored bytes per day
  33,333,333 x 20,000                    =  666,666,660,000
TB per month
  666,666,660,000 x 30 / 1,000,000,000,000  =  20
TB per year
  666,666,660,000 x 365 / 1,000,000,000,000 =  243.3
at replication factor 3, in TB
  243.3 x 3                              =  730

Two terms in those blocks:

• A NIC is a network interface card, the port that connects one machine to the network. A commodity one moves 1 Gbps, meaning one gigabit — a billion bits — per second.
• RF 3, replication factor three, means every stored byte is kept on three machines, so losing two machines does not lose data.

533 Mbps of peak demand is 53% of one machine’s NIC, and 730 TB is twenty commodity boxes. Neither is the constraint. Say so and move to the one that is.

Offered load is not service capacity

Label every rate as you write it down, because this is where the arithmetic goes wrong later.

• 267 Mbps and 533 Mbps are offered load — what the workload demands, at the average and at the peak respectively. Offered load is a property of the work.
• 1 Gbps is service capacity — what one NIC supplies. Service capacity is a property of the machine.

Confusing the two is how a fleet ends up four times too small. The rule, which earns its keep in Interviewer pushback: state whether a rate is offered load or service capacity at the moment you derive it, and never divide one by the other without saying which is which.

Two corollaries fall out of that rule.

1. Never scale an average by a peak ratio to get a peak. Re-derive the peak from the peak page rate instead. 267 Mbps is the load at 333 pages/s; scaling it by a ratio built from a peak page rate mixes the two bases and lands you at half the right answer, which is exactly the trap Interviewer pushback walks into on purpose.
2. Never size a fleet at exactly the offered load. That gives zero headroom by construction. Every fleet in this chapter is derived in this order: offered load -> chosen utilization -> resulting capacity -> box count.

Utilization is the fraction of a machine’s capacity you plan to consume. 80% is the conventional target, because queueing delay climbs steeply above it.

3b. The politeness ceiling — the number that sizes everything

Bandwidth and storage turned out cheap; the constraint that is not cheap is how many pages per second one host can give you — because that number, multiplied by the number of hosts you can work on at once, is your throughput.

Start from the politeness contract and turn it into seconds.

One connection per host means fetches to a host are serial: one finishes before the next begins. A crawl delay means they are serial with a gap. So the period between two consecutive pages from one host is the fetch itself plus the delay.

Two terms in the block below. RTT is round-trip time, how long a packet takes to reach a server and come back. Keep-alive means the connection stays open between fetches, so only the first fetch pays the cost of establishing it — which is why the fetch here is priced at one round trip rather than a connection setup plus a round trip.

RTT to a random internet host                        0.100  s
transfer of a 100 KB document on a warm connection   0.100  s
fetch latency per page, keep-alive
  0.100 + 0.100                          =  0.200
politeness delay between two fetches of one host     1.000  s
period per page from one host
  0.200 + 1.000                          =  1.200
pages per second from one host
  1 / 1.200                              =  0.833

0.833 pages per second per host is the constant the whole chapter runs on.

Throughput is hosts_in_flight x 0.833, where hosts_in_flight counts the distinct hosts the crawler is legally allowed to be fetching from at this instant. And hosts_in_flight is a property of your frontier’s contents, not of your hardware.

Invert that to find how many hosts the peak needs:

distinct hosts needed to sustain the 666 pages/s peak
  666 / 0.833                            =  800

The table below is the throughput law at four working points. Read down the first column — those are hosts, not machines. The bold row is the peak this design has to hit.

That last column is at 1e5 and is therefore 15.7% high as a reported figure. Redone at 86,400 seconds, one host yields 71,971 pages/day, not 83,300, and every other cell scales by the same 0.864. The per-second column is exact; only the per-day one carries the shortcut.

Now price the fleet those 800 host-slots need. A socket is one open network connection. An async fetcher is a process that keeps thousands of sockets open at once by never blocking a thread on any single response.

The block below asks two questions: how many fetcher processes do 800 simultaneous connections need, and how much CPU does parsing 666 pages a second cost. Note the last two lines applying the offered-load-to-capacity rule from 3a volume bandwidth storage: 6.66 cores of demand needs 8.3 cores of capacity at 80% utilization.

concurrent sockets, one per host in flight              800
sockets one async fetcher process holds comfortably  10,000
fetcher processes needed for the sockets
  800 / 10,000                           =  0.08
parse and link-extract CPU per page, seconds          0.010
cores of parsing at peak (offered load)
  666 x 0.010                            =  6.66
cores of capacity at 80% utilization
  6.66 / 0.8                             =  8.3

Eight percent of one process and 6.7 cores. The crawler is not CPU-bound, not bandwidth-bound, and not socket-bound. It is bound by host diversity.

That is the single most counter-intuitive result in the chapter and the one to lead with. Adding machines does nothing. Adding hosts to the frontier does everything.

Two consequences fall straight out.

First, one large site is effectively uncrawlable. Take a site with 100 million pages and divide by the 0.833 pages/s that politeness permits:

pages on one large site                       100,000,000
seconds to crawl it at 0.833 pages/s
  100,000,000 / 0.833                    =  120,048,019
days, thinking, at 1e5
  120,048,019 / 100,000                  =  1,200
years, thinking
  1,200 / 365                            =  3.29
days, REPORTED, at 86,400
  120,048,019 / 86,400                   =  1,389
years, REPORTED
  1,389 / 365                            =  3.8

3.8 years for one site. Say the 3.8, not the 3.3. The 3.3 is the 1e5 shortcut, and this is a schedule — exactly the kind of number ch 02 says to re-divide before you report it.

Either way it is why large-site crawling is a negotiated relationship — sitemaps, feeds, an agreed crawl rate, or a bulk export — and not a scheduling problem you solve.

It gets worse if the site publishes Crawl-delay: 10, which replaces the 1-second gap with a 10-second one:

period per page at Crawl-delay 10
  0.200 + 10.000                         =  10.2
pages per second from that host
  1 / 10.2                               =  0.098
days to crawl a 1,000,000-page site, thinking, at 1e5
  1,000,000 / 0.098 / 100,000            =  102
days, REPORTED, at 86,400
  1,000,000 / 0.098 / 86,400             =  118

Second, politeness must be keyed on the IP address, not the hostname.

An IP address names the machine. A hostname names a site. Shared hosting puts thousands of sites on one machine, so a per-hostname rate limit lets thousands of “polite” streams hit the same box at once:

hostnames sharing one shared-hosting IP             5,000
aggregate rate if politeness is keyed on hostname
  5,000 x 0.833                          =  4,165

4,165 requests/second at one box is a denial of service that you will be blamed for, even though every individual hostname was perfectly polite. The key is the resolved IP address, or the (host, IP) pair.

The pair matters for sites behind a CDN — a content delivery network, a fleet of caching servers spread across the world that answers on behalf of the origin site. Such a host may resolve to 50 different anycast addresses, meaning the same address is announced from many locations and the network routes you to the nearest one. Keying on the hostname alone would throttle all of that capacity down to a single slot.

3c. The frontier does not converge

The to-do list never empties, which is why the interesting question is what to fetch next rather than how to fetch faster. Novelty below is the fraction of extracted links that the crawler has never seen before.

Set up the bookkeeping first, because the block below is a balance sheet.

Crawling one page removes exactly one URL from the frontier — the one you just fetched. It adds 100 x novelty URLs, because the page carries about 100 outbound links (A5) and only the novel ones survive the seen-filter. So the frontier breaks even when 100 x novelty = 1, which is novelty = 1%.

outlinks per page, average                            100
novelty rate at which the frontier neither grows nor shrinks
  1 / 100                                =  0.01
frontier growth per crawled page at 2% novelty
  100 x 0.02                             =  2
net frontier growth over a billion crawled pages
  1,000,000,000 x (2 - 1)                =  1,000,000,000

The (2 - 1) in the last line is that balance sheet: 2 URLs in, 1 URL out, per page crawled. At 2% novelty the frontier gains one net URL for every page you fetch, so a billion pages crawled leaves the frontier a billion URLs longer than it started.

One percent novelty is the knife edge. Below it the frontier drains. Above it the frontier grows without bound no matter how fast you fetch.

Real novelty on a fresh crawl is far above 1%, so the frontier is permanently oversubscribed and the design question is prioritization, not drainage. Anyone who says “we crawl the web” has not done this arithmetic.

4. API sketch

A crawler’s API is internal, meaning no outside customer ever calls it. It is still worth writing down, because it is the seam between the scheduler and everything else, and the three choices inside it — lease rather than pop, an empty answer that is not an error, and link extraction on the worker — are each defensible design decisions rather than plumbing.

Read the sketch below as four endpoints. Each line starts with an HTTP verb and a path, followed by the request body in braces. Responses are indented underneath, or written after a ->.

POST /v1/frontier/urls     {"urls": [{"url","priority","depth","from"}]}
  202 accepted             filtering and dedup happen asynchronously

GET  /v1/frontier/lease?worker_id=&n=32
  200 [{"url","host","ip","lease_expires_at"}]
  204 nothing is polite to fetch right now      <- the normal empty case

POST /v1/frontier/complete {"url","status","etag","content_ref",
                            "simhash","outlinks":[...]}
GET  /v1/hosts/{host}/policy  -> {"crawl_delay_s","robots_expires_at"}

The status codes are HTTP’s. 202 means accepted for later processing. 204 means “success, and there is deliberately no content in the reply.”

Two fields in complete are named here before their sections:

• An etag is the opaque version tag a server hands out with a document. Send it back on the next request and the server can answer “not modified” instead of resending the body. That is the conditional re-fetch of Requirements and the 200x saving of Freshness re crawl driven by observed change rate.
• A simhash is a 64-bit similarity fingerprint of the page’s text, built so that two documents saying the same thing land at nearly the same value rather than at unrelated ones. It is the whole subject of Deep dive 3 content dedup where exact hashing has zero recall. The only thing to know here is that it is not a cryptographic hash and is not used like one.

Three choices in that sketch are deliberate:

• Lease, not pop. Popping removes a URL from the queue and hands it over; leasing hands it over but keeps it, marked as out on loan until a deadline. A worker that dies mid-fetch must not lose the URL and must not have it re-issued instantly. The lease expiry is the redelivery clock, and it must exceed the fetch timeout or you double-fetch every slow host.
• 204 is a first-class response, not an error. “Nothing is polite right now” is the steady state whenever host diversity is thin, and a client that treats it as a failure will hot-loop — retry immediately and continuously — hammering the scheduler for nothing.
• complete carries the outlinks, the links pointing out of the page just fetched. Extraction happens on the worker, where the bytes already are; shipping documents back to a central parser would move 267 Mbps for no reason.

5. Data model

The crawler keeps three tables, and only one decision inside them is genuinely load-bearing: which field decides where a row lives.

• host_state — what the crawler owes each host.
• frontier — the to-do list.
• docs — what has already been fetched.

TEXT, BYTEA, INET, SMALLINT, BIGINT and REAL are SQL column types: text, raw bytes, an IP address, a small whole number, a large whole number, and a floating-point number. The comment on the frontier table is the line to notice — it is the one decision in this schema worth arguing about.

host_state                                -- the politeness ledger
  host TEXT PRIMARY KEY, ip INET, crawl_delay_s REAL
  last_fetch_at TIMESTAMP                 -- must survive restart
  robots_body TEXT, robots_expires_at TIMESTAMP, consecutive_errors SMALLINT

frontier                                  -- partitioned by hash(ip)
  url_hash BYTEA PRIMARY KEY, url TEXT, host TEXT
  priority SMALLINT, depth SMALLINT, discovered_at TIMESTAMP

docs
  url_hash BYTEA PRIMARY KEY, fetched_at TIMESTAMP, http_status SMALLINT
  etag TEXT, last_modified TEXT
  simhash BIGINT                          -- 64 bits, section 9
  change_rate REAL                        -- lambda, section 11
  content_ref TEXT                        -- object store key

Why the frontier shards on IP

The shard key is hash(ip), not hash(url). A shard is one of the machines the table is split across, and the shard key is the field whose hash decides which shard a row lands on. This is a direct application of ch 05 with a deliberately non-obvious key.

Compare the two candidates against the invariant you have to enforce, which is “one connection per host.”

• hash(url) spreads one host’s URLs across every shard. Enforcing one connection per host would then need every shard to coordinate with every other shard on every single fetch.
• hash(ip) makes each host the exclusive property of one shard. Politeness becomes a purely local decision: compare last_fetch_at against the clock. No locks, and no RPC — a remote procedure call, which is a network round trip to another machine dressed up as a function call.

Where the bytes live

The document store is append-mostly with large immutable values: rows are added and almost never modified.

That is the workload an LSM tree is built for — a log-structured merge tree, a storage engine that buffers writes in memory and flushes them as sorted files rather than updating pages in place. The derivation is in sql/03.

The document bodies themselves do not go in the row at all. They go to object storage, a service such as S3 that stores whole blobs under a key for a tenth of the price of a database, and only the content_ref key lives in the row.

6. High-level architecture

With the tables in place, here is the whole pipeline once, end to end, so that the four deep dives that follow each have a place to hang.

The diagram runs top to bottom, from a seed URL to a fetched document and back around. Rectangles are processing stages, diamonds are decisions, and the arrow leaving the bottom returns to the top — a crawler is a loop, not a pipeline with an end.

flowchart TD
    SEED["Seed URLs"] --> FRONT["Front queues<br/>priority 0 to 4"]
    FRONT --> ROUTER["Back queue router<br/>sticky host to queue map"]
    ROUTER --> BACK["Back queues<br/>1,024, one host each"]
    BACK --> HEAP["Ready heap<br/>keyed on next_fetch_at"]
    HEAP --> DNS["DNS<br/>own recursive resolver + cache"]
    DNS --> ROB{"robots.txt cached<br/>and allows it?"}
    ROB -->|"no"| DROP["Drop"]
    ROB -->|"yes"| FETCH["HTTP fetcher<br/>keep-alive, conditional GET"]
    FETCH -->|"304 Not Modified"| SCHED["Re-crawl scheduler<br/>update change rate"]
    FETCH -->|"200"| CSEEN{"Content seen?<br/>simhash within 3"}
    CSEEN -->|"yes"| SCHED
    CSEEN -->|"no"| STORE[("Doc store<br/>compressed HTML")]
    STORE --> EXT["Link extractor<br/>and URL canonicalizer"]
    EXT --> FILT["URL filter<br/>scheme, depth, traps, blocklist"]
    FILT --> USEEN{"URL seen?<br/>bloom, 20 bits per key"}
    USEEN -->|"yes"| DROP
    USEEN -->|"no"| FRONT
    SCHED --> FRONT

    style ROUTER fill:#bc6c25,color:#fff
    style USEEN fill:#1d3557,color:#fff
    style CSEEN fill:#1d3557,color:#fff
    style DROP fill:#9d0208,color:#fff

The colour key

This is not the key chapter 01 publishes. Ch 01 reads these same four hexes as component roles — blue is the authoritative copy of the data, green takes load off the request path. None of that applies to a scheduler where every box is a stage of one loop. Here:

• Orange is the sticky router, the single component that turns politeness from a distributed lock into a local timestamp comparison. It is orange in both diagrams in this chapter.
• Blue is a probabilistic gate whose mistakes are silent — the two “seen?” diamonds, whose false positives are priced in Deep dive 2 url dedup and what a false positive costs and Deep dive 3 content dedup where exact hashing has zero recall.
• Green, which appears only in Deep dive 1 front queues and back queues, is the scheduling structure that enforces the delay.
• Red is a URL dropped and never revisited.

Following one URL through the loop

1. It enters the front queues. Either as one of the seed URLs, or later as a link found in some other page. There are five front queues, numbered by priority 0 to 4.

2. The back queue router assigns it a back queue. It uses a sticky host-to-queue map, so the URL goes to whichever back queue already owns its host. There are 1,024 back queues, each holding one host only.

3. The ready heap decides which back queue goes next. It is keyed on next_fetch_at, the earliest time politeness permits another fetch from that host.

4. DNS resolves the hostname, using the crawler’s own recursive resolver plus a cache. Recursive means the resolver chases the answer all the way down the domain hierarchy itself instead of asking someone else to.

5. A gate asks whether the cached robots.txt for this host allows the fetch. If not, the URL is dropped and never revisited.

6. The HTTP fetcher issues the request, over a kept-alive connection, as a conditional GET. GET is the HTTP verb for “send me this document”; conditional means it carries the version tag from last time, so the server may answer 304 Not Modified instead of resending bytes.

7a. A 304 goes straight to the re-crawl scheduler, which updates that page’s change rate and reschedules it. No document is stored, because nothing changed.

7b. A 200 — the HTTP code for success, with a body — reaches the content-seen check. This compares the document’s simhash fingerprint against everything already stored and treats a match within Hamming distance 3 as a duplicate. Hamming distance is the count of bit positions in which two equal-length bit strings differ, so “within 3” means at most three of the fingerprint’s 64 bits moved.

8. Fresh documents go to the doc store as compressed HTML.

9. The link extractor and URL canonicalizer pull out the outbound links and rewrite each into a single standard form.

10. The URL filter drops what should never be fetched — by scheme, depth, trap signature, or blocklist.

11. What survives hits the URL-seen check, the bloom filter at 20 bits per key. Anything genuinely new re-enters the front queues, and the loop closes.

What the diagram is claiming

The diagram asserts four things, and every one gets its own section below:

1. Priority and politeness need two queue layers — Deep dive 1 front queues and back queues.
2. URL dedup is a bloom filter whose false-positive rate is a product decision — Deep dive 2 url dedup and what a false positive costs.
3. Content dedup cannot be an exact hash — Deep dive 3 content dedup where exact hashing has zero recall.
4. The arrow that loops back into the front queues is governed by an observed change rate — Freshness re crawl driven by observed change rate.

7. Deep dive 1: front queues and back queues

The frontier’s shape falls out of two impossibilities: one queue cannot hold both priority and politeness, and per-host queues alone cannot hold priority at all. What survives is two layers of queues with a router between them — and the number of queues in the second layer turns out to be a hard ceiling on throughput.

Why one queue cannot work

A page contains 100 links to the same host, so any FIFO or priority order hands a worker 100 consecutive URLs for one server. FIFO is first-in-first-out, plain arrival order.

From there you have two options, and both are wrong:

• Fetch those 100. You have now violated politeness by 100x against that one server.
• Skip them. Your queue is now a linear scan through the head, looking for a host you are allowed to touch. That scan runs on every single fetch.

Why per-host queues alone cannot work either

With millions of hosts you would need millions of queues, which is not a structure you can keep in memory or schedule over.

Worse, nothing in that structure expresses “this news site matters more than that parked domain” — a parked domain being one registered but holding no real content. Per-host queues give you politeness and throw away priority.

The answer: two layers with a router between them

In the diagram, the left half is about priority, the right half is about politeness, and the orange box in the middle is the only thing that connects them.

flowchart LR
    IN["New URLs"] --> P["Prioritizer<br/>site rank, freshness, depth"]
    P --> F0["Front 0"] & F1["Front 1"] & F2["Front 2"]
    F0 & F1 & F2 --> R["Router<br/>host -> back queue<br/>sticky, table-backed"]
    R --> B0["Back 0<br/>host A only"] & B1["Back 1<br/>host B only"] & B2["Back 2<br/>host C only"]
    B0 & B1 & B2 --> H["Ready heap<br/>next_fetch_at per queue"]
    H --> W["Worker pool"]

    style R fill:#bc6c25,color:#fff
    style H fill:#2d6a4f,color:#fff

Same key as High level architecture. Orange is the router, the same box doing the same job in both pictures. The ready heap is green rather than blue because it is a scheduling structure, not a probabilistic gate — blue in this chapter is reserved for the two filters that fail silently, and reusing it here for a data structure would be the ch 07 mistake of carrying one key across two questions.

The flow, in order: new URLs are scored by the prioritizer on site rank, expected freshness, and depth from the seed. They queue by priority. The router hands each to the back queue that owns its host. The ready heap picks which back queue may go next. A worker pool of fetchers drains it.

Four properties make that work, and each is a decision you should be able to defend:

• Front queues carry priority. Selection between them is weighted-random, not strict — under strict priority the low queues never get picked at all, and the low queues are where host diversity lives.
• Back queues carry politeness. Each holds URLs for one host only. A worker takes from one back queue at a time, so two overlapping requests to one server are structurally impossible rather than policed by a check somebody can forget.
• The router is a sticky table, not a hash. Sticky means a host keeps the same slot for as long as it has work. Hashing the host into a slot instead gives collisions, and a collision means two hosts share a back queue and one blocks the other. The table assigns a free slot on first sight and releases it when the queue drains.
• The ready heap is keyed on next_fetch_at per back queue — the earliest time politeness permits another fetch from that host. A heap keeps the smallest key on top, so “what may I fetch now” costs O(log b) with b queues, which is a handful of comparisons rather than a scan of all 1,024.

Sizing the back-queue count

One back queue holds one host, and 3b the politeness ceiling the number that sizes everything said the 666 pages/s peak needs 800 hosts in flight. So you need at least 800 back queues, rounded up to a power of two for the usual reason that it makes index arithmetic a bit mask:

back queues, one per host in flight, rounded to a power of two   1,024
headroom over the 800 the peak requires
  1,024 / 800                            =  1.28

The number of back queues is a hard ceiling on throughput. With b back queues you can never exceed b x 0.833 pages/s, no matter how many workers you run. That is the single most useful sentence to have ready when an interviewer asks “how do you scale this?”

The frontier in miniature

The code below is a working frontier with a simulated clock instead of real fetches. Four assertions at the bottom pin the three claims of this section plus the invariant that is easiest to lose:

1. One host tops out at 1/1.2 = 0.833 pages per second. The politeness ceiling.
2. Eight hosts with eight queues run eight times faster, at identical per-host politeness. Host diversity is what buys throughput.
3. Eight hosts with only two queues are capped by the queues, not by the hosts. b back queues means b x 0.833 and no more.
4. A host whose back queue drains and whose slot is handed to somebody else still owes the full 1.2 s when it comes back.

That fourth one is the subtle path, and it is the one worth reading the code for. The slot is a recyclable resource; the politeness debt is not. Notice that last_fetch is a defaultdict that lives outside the slot table, and that _next_ok charges fetch_s + delay_s — the full 1.2 s period — rather than the 1.0 s delay alone. A simulation that adds every host once and never lets a queue drain will never reach that path, which is why the last assertion builds the case by hand.

Two methods to read closely: _fill routes URLs from front queues into back queues and returns early when no slot is free, and pop hands out a URL and then either reschedules the slot or releases it.

"""The frontier: front queues carry priority, back queues carry politeness."""
import heapq
from collections import defaultdict, deque


class Frontier:
    """One back queue per host in flight, so a worker bound to one back queue
    cannot issue two overlapping requests to the same server."""

    def __init__(self, n_back=8, delay_s=1.0, fetch_s=0.2, priorities=3):
        self.front = [deque() for _ in range(priorities)]
        self.back, self.slot_of, self.host_of = {}, {}, {}
        self.free = deque(range(n_back))
        self.ready = []                       # heap of (next_fetch_at, slot)
        self.last_fetch = defaultdict(lambda: -1e18)   # outlives slot reuse
        self.delay_s, self.fetch_s = delay_s, fetch_s
        self.admissions = 0                   # host -> slot assignments so far

    def add(self, url, host, priority=1):
        self.front[min(priority, len(self.front) - 1)].append((url, host))

    def _next_ok(self, host, now):
        """Earliest polite time for `host`: a FULL period after its last fetch.

        Fetch plus delay, the same expression `pop` uses in the slot it is
        already holding. Charging only the delay here is the live-looking bug:
        it makes the gap 1.0 s instead of 1.2 s for exactly the hosts that lost
        their slot and came back, which no simulation that adds each host once
        will ever reach.
        """
        return max(now, self.last_fetch[host] + self.fetch_s + self.delay_s)

    def _fill(self, now):
        """Route front-queue URLs into back queues until the slots run out."""
        for q in self.front:
            while q:
                url, host = q[0]
                slot = self.slot_of.get(host)
                if slot is None:
                    if not self.free:
                        return                # no slot: the router blocks
                    slot = self.free.popleft()
                    self.slot_of[host], self.host_of[slot] = slot, host
                    self.back[slot] = deque()
                    self.admissions += 1
                    heapq.heappush(self.ready, (self._next_ok(host, now), slot))
                q.popleft()
                self.back[slot].append(url)

    def pop(self, now):
        """Return (url, host), or None if nothing is polite to fetch yet."""
        self._fill(now)
        if not self.ready or self.ready[0][0] > now:
            return None
        _, slot = heapq.heappop(self.ready)
        host, url = self.host_of[slot], self.back[slot].popleft()
        self.last_fetch[host] = now
        if self.back[slot]:
            heapq.heappush(self.ready, (now + self.fetch_s + self.delay_s, slot))
        else:
            del self.back[slot], self.slot_of[host], self.host_of[slot]
            self.free.append(slot)            # slot recycled; the debt is not
        return url, host


def simulate(hosts, per_host, n_back):
    f = Frontier(n_back=n_back)
    for h in range(hosts):
        for i in range(per_host):
            f.add(f"http://h{h}/p{i}", f"h{h}")
    now, done = 0.0, 0
    while done < hosts * per_host:
        if f.pop(now) is not None:
            done += 1
        elif f.ready:
            now = max(now, f.ready[0][0])
        else:
            break
    # Each admission gets one fetch for free -- the gap is BETWEEN fetches of
    # one host -- so netting them off is what makes `b x 0.833` an exact
    # ceiling rather than a bound the handovers can slip past.
    return done, (done - f.admissions) / now            # fetched, pages/s


# One host: the period is fetch + delay, so the ceiling is 1/1.2 = 0.833/s.
assert abs(simulate(1, 100, n_back=1)[1] - 1 / 1.2) < 0.01
# Eight hosts, eight queues: 8x the rate, identical politeness per host.
assert abs(simulate(8, 100, n_back=8)[1] - 8 / 1.2) < 0.05
# Eight hosts, two queues: throughput is capped by the QUEUES, not the hosts,
# at exactly the b x 0.833 ceiling this section claims -- no 2.1/1.2 slack.
assert simulate(8, 50, n_back=2)[1] < 2 / 1.2 + 1e-9
# The slot-resurrection path, which no simulate() call above reaches: host A
# drains its queue, loses the slot, and is re-added. Politeness still owes the
# full 1.2 s from A's last fetch, not the 1.0 s delay alone.
resurrect = Frontier(n_back=1)
resurrect.add("http://a/1", "A")
assert resurrect.pop(0.0) == ("http://a/1", "A")   # queue drains, slot freed
resurrect.add("http://a/2", "A")
assert resurrect.pop(1.0) is None                  # 1.0 s is not yet 1.2 s
assert resurrect.pop(1.2) == ("http://a/2", "A")

8. Deep dive 2: URL dedup, and what a false positive costs

“Have I already seen this URL?” has a two-stage answer — first rewrite the URL into a standard form, then test it against a compact probabilistic filter — and the filter’s one failure mode carries the most under-appreciated price in the chapter.

Stage one: canonicalization

Before any filter runs, canonicalize the URL, also called URL normalization: rewrite it into one standard form, so that the many ways of spelling the same address collapse into a single string.

The rules, concretely:

• Lowercase the scheme and the host. The scheme is the https part.
• Drop the default port (:80 for HTTP, :443 for HTTPS).
• Resolve . and .. path segments.
• Drop the #fragment — the #section part, which never reaches the server at all.
• Sort the query parameters, so ?a=1&b=2 and ?b=2&a=1 become one string.
• Strip known tracking and session parameters: utm_*, sid, jsessionid, PHPSESSID. These are marketing tags and per-visitor tokens that change the string without changing the page.

This is the cheapest deduplication in the system, it is pure string manipulation, and it runs first. Here is what it removes before the expensive filter ever sees a URL:

raw extracted URLs per day
  33,333,333 x 100                       =  3,333,333,300
distinct after canonicalization, at a 30% collapse rate
  3,333,333,300 x (1 - 0.30)             =  2,333,333,310
filter lookups avoided per day
  3,333,333,300 - 2,333,333,310          =  999,999,990

A billion lookups a day removed by string manipulation, for free.

Stage two: the bloom filter, and what it costs when it lies

A bloom filter is a bit array plus k hash functions.

• To insert a key, hash it k ways and set those k bits.
• To test a key, hash it the same k ways and check whether all k bits are set.
• If any bit is clear, the key is definitely absent. A bloom filter never produces a false negative.
• If all k bits are set, the key is probably present. But those bits may have been set by other keys, and that is a false positive — abbreviated FP below. The filter says “seen” about something it has never seen.

Two quantities matter: n, the number of keys stored, and m, the number of bits available. The design knob is their ratio m/n, the bits per key. The optimal k = (m/n) ln 2 and the closed form p = 0.6185 ^ (m/n) for the false-positive probability are derived in ch 06 and used here as given.

What is new in this chapter is the cost function. A false positive in a crawler is not a wasted disk read — it is a page that is never fetched, and nothing anywhere logs it. The URL is declared already-seen, dropped, and never reconsidered. There is no error, no retry, and no metric that moves.

The block below computes the false-positive rate at the crawler’s operating point, 20 bits per key with k = 14.

fraction of bits still CLEAR after n insertions at m/n = 20, k = 14
  e ^ -(k / (m/n)) = e ^ -0.7            =  0.496585
FP rate at 20 bits per key, k = 14
  (1 - 0.496585) ^ 14                    =  0.000067

The 0.496585 is not a magic constant; it comes out in three steps:

1. e^(-k/(m/n)) is the standard-textbook probability that a particular bit is still zero after the filter has taken all n of its keys. At k = 14 and m/n = 20 that exponent is -14/20 = -0.7, and e^-0.7 = 0.496585.
2. So 1 - 0.496585 = 0.503415 is the probability that a particular bit is set.
3. Raise that to the k: 0.503415 ^ 14 = 0.000067. That is the probability that all 14 bits of a URL the filter has never seen happen to be set anyway.

Every FP number below is that same expression at a different m/n, and the code at the end of this section computes it rather than quoting it.

The next table sizes the filter across the four bits-per-key settings you would actually consider. The RAM column is 10^10 keys x bits / 8 bits per byte. The last column converts the FP rate into pages of the web, over one corpus pass — one full sweep through the 10 billion URLs of A4.

Watch the unit on that last column. A corpus pass is a different clock from the monthly cycle the per-host budget in Traps and the guards that are arithmetic rather than heuristic is measured in. Say which one you mean; “cycle” on its own is the word that gets misread here.

The last column is the one that matters. It converts a percentage nobody has intuition about into pages of the web that will never be crawled, and nobody will ever know which ones.

Now price the move from the cheap setting to the expensive one:

pages silently never crawled per corpus pass, at 10 bits per key
  10,000,000,000 x 0.008194              =  81,940,000
the same at 20 bits per key
  10,000,000,000 x 0.000067              =  670,000
extra RAM to move from 10 to 20 bits per key, in GB
  10,000,000,000 x (20 - 10) / 8 / 1,000,000,000  =  12.5
pages recovered per GB of that RAM
  (81,940,000 - 670,000) / 12.5          =  6,501,600

12.5 GB of RAM buys back 81 million pages, or 6.5 million pages per gigabyte.

That is why the crawler runs at 20 bits per key while an LSM store runs at 10. Same structure, same formula, different cost of being wrong: the LSM tree pays a false positive with one wasted disk read, and the crawler pays it with a document that will never exist.

The false-positive rate is a product decision, and the product manager needs the last column of that table, not the middle one.

The cliff

The failure mode is worse than the rate suggests, because a bloom filter does not degrade gracefully. Put twice as many keys into a filter sized for n and m/n halves — from 20 bits per key to 10 — but k stays at the 14 the filter was built with. That does not halve the accuracy. It collapses it:

fraction of bits still clear at m/n = 10 with k still 14
  e ^ -(14 / 10) = e ^ -1.4              =  0.246597
the same filter holding twice its design n, so m/n = 10 with k still 14
  (1 - 0.246597) ^ 14                    =  0.018984
degradation factor
  0.018984 / 0.000067137                 =  283

Twice the keys is 283 times the false-positive rate, and the only symptom is that the crawl quietly gets smaller.

One note on that 283. Divide the two displayed rates — 0.019 / 0.000067 — and you get 284, because rounding the inputs shows up in the answer. The assertion in the code below pins the unrounded 283, and 283 is the number to quote.

Two mitigations, and you should name both:

• A scalable bloom filter. When the current generation reaches the capacity it was sized for, freeze it and start a new one. A lookup checks every generation. The error rate then grows by addition across generations instead of collapsing exponentially inside one.
• An exact backing set. A real on-disk sorted set of every URL seen. The filter answers “definitely new” for free, and only the “maybe seen” answers pay for a disk lookup to confirm.

Partition both across the fleet by hash(url), using the ring from ch 05.

Note the deliberate asymmetry with Data model. The frontier is partitioned by IP address because politeness is per-server. The seen-set is partitioned by URL because dedup is per-URL. Two different shard keys in one system, each derived from what it has to make local.

The code below inverts the closed form to answer “what does a target error rate cost in bits per key.” Its assertions pin the two operating points, the 25 GB footprint, the 81 million pages recovered, and the 283x cliff — so every number in this section is computed rather than quoted.

import math


def bits_per_key(target_fp):
    """Invert p = 0.6185 ^ (m/n): the bits/key a target FP rate costs."""
    return math.log(target_fp) / math.log(0.6185)


def fp_at(bits, k=None):
    k = k or max(1, round(bits * math.log(2)))
    return (1 - math.exp(-k / bits)) ** k


N = 10_000_000_000
assert round(fp_at(10), 6) == 0.008194          # the LSM operating point
assert round(fp_at(20), 6) == 0.000067          # the crawler operating point
assert round(N * 20 / 8 / 1e9, 1) == 25.0       # 25 GB of RAM
assert round(N * fp_at(10) - N * fp_at(20)) == 81_265_850   # pages recovered
assert 19.0 < bits_per_key(1e-4) < 19.4         # 0.01% costs ~19 bits/key
assert round((1 - math.exp(-14 / 10)) ** 14 / fp_at(20)) == 283   # the cliff

9. Deep dive 3: content dedup, where exact hashing has zero recall

The previous section deduplicated addresses. Deduplicating content is a different and harder problem: an exact hash is useless here, so it takes a similarity fingerprint — and a way to look one up among ten billion others without scanning.

Why an exact hash scores zero

SHA-256 is a cryptographic hash: a function that turns any input into a 32-byte value, where a one-bit change in the input scrambles the whole output. That property is exactly what makes it useless here.

It catches byte-identical documents and nothing else. Any page carrying a rendering timestamp, a rotating ad slot, a CSRF token, a visitor counter, or a “3 comments” badge is byte-different on every fetch. A CSRF token is a per-visit random string a site embeds to defend against cross-site request forgery, so it changes on every load by design.

Measure it as recall — the fraction of the true duplicates a detector actually finds. An exact hash against the near-duplicate population does not score low. It scores zero, because “near-duplicate” means “not byte-identical” and that is the only thing an exact hash can see.

Here is what that costs, using A7’s 30% near-duplicate and 10% byte-identical shares:

near-duplicate share of the crawled corpus            0.30
byte-identical share that an exact hash catches       0.10
share only a near-duplicate detector can catch
  0.30 - 0.10                            =  0.20
pages per month in that band
  1,000,000,000 x 0.20                   =  200,000,000
storage those pages waste per month, in TB
  200,000,000 x 20,000 / 1,000,000,000,000  =  4

Twenty percent of the fetch budget and 4 TB a month, spent on mirrors, print views, syndicated wire copy, and session-id variants of pages you already have.

The fetch budget is the expensive half. 4 TB of storage is nothing. But 200 million wasted fetches is 20% of the throughput you just derived a whole fleet for in 3b the politeness ceiling the number that sizes everything, and fetch slots are the resource you cannot buy more of.

What a simhash is

Simhash is a 64-bit fingerprint. Build it in four steps:

1. Cut the document into shingles — overlapping runs of a few consecutive words. “the quick brown fox” and “quick brown fox jumps” are two shingles of length 4.
2. Hash each shingle to 64 bits.
3. For each of the 64 bit positions, keep a running total. Add one if that bit is set in the shingle’s hash, subtract one if it is clear.
4. The final fingerprint has a 1 wherever the running total came out positive, and a 0 elsewhere.

The point of that construction is the vote. Changing a few shingles nudges a few of the 64 totals across zero and leaves the rest alone, because every other shingle is still voting the same way. So two documents that share most of their text land at small Hamming distance — the number of bit positions in which two equal-length bit strings differ. Near-duplicate is distance <= 3.

Querying ten billion fingerprints without scanning

The hard part is not computing the fingerprint. It is querying it: find every fingerprint within distance 3 of a probe, over 10 billion fingerprints, at 666 probes per second.

Scanning is 10 billion comparisons per probe and is not a candidate. You cannot use an ordinary hash table either, because the whole point is that the two fingerprints are not equal.

The trick is the pigeonhole principle: if you distribute items into fewer containers than you have items, some container holds more than one. Used here in the form: if only 3 bits differ and there are more than 3 blocks, some block has no differing bit in it at all.

That gives the index. Split the 64 bits into B blocks. If two fingerprints differ in at most 3 bits, at least B - 3 blocks are bit-identical. So build one hash table for every combination of B - 3 blocks, keyed on the concatenation of those blocks’ bits. At least one of those tables is guaranteed to have filed both fingerprints under the same key — which turns a fuzzy search into a set of exact lookups.

Two ways to choose B, where C(n,r) is the count of ways to choose r items from n:

• B = 4 blocks of 16 bits leaves at least 4 - 3 = 1 block clean. You do not know which one, so you index every single block: C(4,1) = 4 tables, keyed on 16 bits each.
• B = 6 blocks (11, 11, 11, 11, 10, 10) leaves at least 6 - 3 = 3 blocks clean. Index every combination of three: C(6,3) = 20 tables, keyed on 31 bits or more.

More tables cost more storage and return far fewer candidates to check. The block below decides between them: the first group counts candidates for the 4-table split, the second for the 20-table split, and the third turns both into comparisons per second at the 666 pages/s peak. A key of w bits spreads the corpus over 2^w buckets, so candidates per probe is 10^10 / 2^w.

4-table candidates per probe
  10,000,000,000 / 65,536                =  152,588
4-table candidates per query
  152,588 x 4                            =  610,352
4-table index, in TB
  4 x 10,000,000,000 x 8 / 1,000,000,000,000  =  0.32

20-table key width, three blocks, worst case, bits
  10 + 10 + 11                           =  31
20-table candidates per probe
  10,000,000,000 / 2,147,483,648         =  4.66
20-table candidates per query
  4.66 x 20                              =  93.2
20-table index, in TB
  20 x 10,000,000,000 x 8 / 1,000,000,000,000  =  1.6

comparisons/s at 4 tables, 666 probes/s
  666 x 610,352                          =  406,494,432
comparisons/s at 20 tables
  666 x 93.2                             =  62,071
extra index, in TB
  1.6 - 0.32                             =  1.28
comparisons removed per second
  406,494,432 - 62,071                   =  406,432,361

1.28 TB of extra index removes 406 million comparisons per second.

At 4 tables the near-duplicate check is a memory-bandwidth problem larger than the crawl itself. At 20 tables it is 62,000 comparisons per second, which is free. Buy the tables.

Say the caveat too: the trade is entirely a consequence of the corpus size. An interviewer who moves 10 B down to 100 M changes the answer, because the candidate count per probe falls by the same factor.

Simhash rather than minhash

Minhash is the other standard similarity sketch. It stores the minimum hash value under each of many independent hash functions, and compares how many of those minima agree. Price the two side by side:

minhash signature, 128 hashes at 4 B each             512
signature bytes for the corpus, in TB
  10,000,000,000 x 512 / 1,000,000,000,000  =  5.12
simhash signature bytes for the corpus, in GB
  10,000,000,000 x 8 / 1,000,000,000      =  80
ratio
  5,120 / 80                             =  64

Minhash costs 64x the space and answers a richer question that a crawler does not need. That richer question is an estimate of Jaccard similarity: the size of the overlap between two sets divided by the size of their union, a number between 0 and 1.

“Is this the same page” is a threshold test at a fixed cut-off, not a graded score. So the 8-byte fingerprint wins.

Minhash earns its keep where you do need the graded answer or genuine set-overlap semantics — clustering, plagiarism scoring. Not for a yes-or-no near-duplicate rejection.

The fingerprint and the index in code

The code below implements both. Read simhash against the four steps above: v is the 64 running totals, the loop over range(bits) casts the votes, and the final sum turns positive totals into set bits. NearDupIndex builds the 20 tables from itertools.combinations, and _keys extracts the three-block key for each one.

The assertions at the bottom demonstrate the section’s claim directly. Two copies of a page that differ only in a rendering timestamp get different SHA-256 hashes, land within Hamming distance 3 of each other, and are matched by a single probe against the index — while unrelated prose is more than 10 bits away and matches nothing.

"""Simhash plus the block-permutation index that makes it queryable."""
import hashlib
import itertools
import re

BLOCKS = [(0, 11), (11, 11), (22, 11), (33, 11), (44, 10), (54, 10)]


def simhash(text, bits=64, k=4):
    w = re.findall(r"[a-z0-9]+", text.lower())
    v = [0] * bits
    for i in range(max(1, len(w) - k + 1)):
        h = int.from_bytes(hashlib.blake2b(
            " ".join(w[i:i + k]).encode(), digest_size=8).digest(), "big")
        for b in range(bits):
            v[b] += 1 if (h >> b) & 1 else -1
    return sum(1 << b for b in range(bits) if v[b] > 0)


def hamming(a, b):
    return bin(a ^ b).count("1")


class NearDupIndex:
    """C(6,3) = 20 tables. At Hamming distance <= 3 across 6 blocks at least
    3 blocks are untouched, so one of the 20 three-block keys must match."""

    def __init__(self, max_distance=3, clean=3):
        self.combos = list(itertools.combinations(range(len(BLOCKS)), clean))
        self.tables = [{} for _ in self.combos]
        self.max_distance = max_distance

    def _keys(self, fp):
        for combo in self.combos:
            yield tuple((fp >> BLOCKS[i][0]) & ((1 << BLOCKS[i][1]) - 1)
                        for i in combo)

    def add(self, fp, doc_id):
        for table, key in zip(self.tables, self._keys(fp)):
            table.setdefault(key, []).append((fp, doc_id))

    def probe(self, fp):
        seen, hits = set(), []
        for table, key in zip(self.tables, self._keys(fp)):
            for cand, doc_id in table.get(key, ()):
                if doc_id not in seen:
                    seen.add(doc_id)
                    if hamming(fp, cand) <= self.max_distance:
                        hits.append(doc_id)
        return hits


BASE = " ".join(f"the quick brown fox jumps over the lazy dog number {i}"
                for i in range(80))
A, B = BASE + " page generated at 04 15 02", BASE + " page generated at 09 41 37"
C = " ".join(f"unrelated prose about b trees and write amplification {i}"
             for i in range(80))

assert sum(BLOCKS[-1]) == 64 and len(NearDupIndex().combos) == 20
# Exact hashing has zero recall against a rendering timestamp; simhash does not.
assert hashlib.sha256(A.encode()).digest() != hashlib.sha256(B.encode()).digest()
assert hamming(simhash(A), simhash(B)) <= 3
assert hamming(simhash(A), simhash(C)) > 10

idx = NearDupIndex()
idx.add(simhash(A), "doc-A")
assert idx.probe(simhash(B)) == ["doc-A"] and idx.probe(simhash(C)) == []

10. Traps, and the guards that are arithmetic rather than heuristic

Sites generate unbounded URL spaces by accident — nobody built a trap to hurt you — and each guard against them can be derived from a number rather than picked, which is what lets you defend it when an interviewer asks “why 16 and not 12?”.

The table below lists the five traps you will actually meet. The middle column is what the trap looks like in your logs, which is how you recognize one in production. The right column is the guard that contains it.

Two of those rows use shorthand:

• Faceted navigation is the filter sidebar on a shop — colour, size, sort order, page number — where every combination of choices is its own URL. So n filters with a few values each produce a combinatorial explosion of addresses over one small catalogue.
• A soft 404 is a page that says “not found” in its body while the server reports the opposite of a 404: a 200 success. It defeats every check that looks only at the status code.

The depth cap, derived

Depth is the number of link hops from a seed URL. Branching factor is how many genuinely new pages each crawled page reveals.

The whole cap rests on that branching factor, so it is assumption A11 from 2a the assumptions this design rests on and not a number invented at this point in the page.

It is not the 100 of A5. A5 counts outbound links, most of which point at pages the crawler already has. A11 takes 10% of them to be genuinely new — a novelty rate an order of magnitude above the 1% knife edge of 3c the frontier does not converge, which is what a fresh crawl actually sees.

Move the branching factor and the cap moves with it: at a branching factor of 5, the corpus is reached at depth 15 instead of 10, and the same “a million times the corpus” cap lands at 23 instead of 16.

The block below raises the branching factor to successive powers, because reach at depth d is branching_factor ^ d:

unique new pages discovered per crawled page (A11)     10
reach at depth 8
  10 ^ 8                                 =  100,000,000
reach at depth 10
  10 ^ 10                                =  10,000,000,000
reach at depth 16
  10 ^ 16                                =  10,000,000,000,000,000
ratio of depth-16 reach to the 10 B target corpus
  10,000,000,000,000,000 / 10,000,000,000  =  1,000,000

A branching factor of 10 reaches the entire 10-billion-page target at depth 10, so depth 16 is a million times the corpus and cannot be reachable content.

Cap at 16 and you have never argued about a heuristic. The cap is not “16 feels deep enough”; it is “everything real is at depth 10 or less, and 16 gives six orders of magnitude of slack.”

The same move works for URL length. The guard is not a round number someone liked — it is 15x the median, so nothing a human ever typed comes near it:

median URL length, bytes                               66
guard length, bytes
  1,000
ratio of the guard to the median
  1,000 / 66                             =  15.2

And for the per-host budget, which is the guard that actually contains a trap. The block below sets the cap against two reference points: what one host could physically yield in a day, and how many distinct hosts the cap forces you to find.

pages one host can yield in a day at 0.833 pages/s, thinking, at 1e5
  0.833 x 100,000                        =  83,300
the same, REPORTED, at 86,400
  0.833 x 86,400                         =  71,971
per-host cap per MONTH (the same 30-day window the 1 B target is stated over)
  10,000
distinct hosts required to fill the 1 B monthly budget
  1,000,000,000 / 10,000                 =  100,000

The per-host cap is not a politeness control, it is a diversity control.

At 10,000 pages per host per month, filling the monthly budget requires 100,000 distinct hosts — which is exactly the property 3b the politeness ceiling the number that sizes everything said throughput depends on. One guard solves two problems: it stops any single trap from eating the budget, and it forces the breadth that makes the fleet go fast.

Note the unit, because “cycle” is overloaded in this chapter and this is the load-bearing place. Here a cycle is one month, the window the 1 B product target is quoted over. The bloom-filter table in Deep dive 2 url dedup and what a false positive costs counts silently-lost pages over one pass through the 10 B corpus. Those two windows differ by a factor of ten and are not interchangeable.

One more honesty check on the numbers above. The real per-host ceiling is 71,971 pages/day, not 83,300 — the 83,300 is the 1e5 shortcut. The cap of 10,000 sits comfortably under either, which is the point: it binds long before politeness does.

robots.txt

The crawler must fetch each site’s robots.txt before fetching anything else from it, which creates a second request stream that can easily outweigh the first. The cache that prevents that is worth pricing.

A TTL, time to live, is how long a cached copy may be used before it must be re-fetched.

The block below compares three policies: no cache at all, a shared 24-hour cache, and a cache that is per-process rather than shared. The last one is the mistake worth pricing, because it looks like caching and costs 16x.

robots.txt fetches with no cache, per day (one per page fetch)
  33,333,333
distinct hosts touched per day (A12)
  1,000,000
reduction from a 24-hour shared cache
  33,333,333 / 1,000,000                 =  33.3
fetcher processes, for redundancy and failure domain
  16
robots.txt fetches if the cache is per-process instead of shared
  1,000,000 x 16                         =  16,000,000
inflation over the shared cache
  16,000,000 / 1,000,000                 =  16

The cache must be shared, not per-process, or you multiply the fetch count by the fleet size — and every one of those fetches consumes a politeness slot on the very host you are trying to be polite to.

Both the 33.3 and the 16 rest entirely on that 1,000,000 hosts, which is assumption A12 in 2a the assumptions this design rests on and is a measurement, not a derivation. Change the host count and both numbers move with it, in the same direction, by the same factor.

The two status-code rules candidates get backwards

4xx means allow-all. 5xx or a timeout means disallow-all.

• A 4xx status is the server saying “there is no such file.” A missing robots.txt is a site saying nothing, so nothing is forbidden. Crawl it.
• A 5xx is the server saying “I am broken.” A failing robots.txt is a site that is unwell, and hammering it is both rude and useless. Back off the whole host.

Cache the negative verdict with a short TTL, so a site that recovers is picked up again within minutes rather than a day.

DNS

Every fetch needs the hostname turned into an IP address first, and doing that the obvious way saturates before a single page is downloaded.

The block below asks one question: if you resolve hosts one at a time and wait for each answer, how much of a day does that consume? The answer is a utilization — demand divided by the seconds available — so it is one of the five figures this chapter prints both ways.

distinct hosts resolved per day (A12)
  1,000,000
uncached recursive resolution latency, seconds        0.100
wall-clock seconds if resolution is serialized
  1,000,000 x 0.100                      =  100,000
seconds in a day, thinking, at 1e5
  100,000
utilization of one blocking resolver, thinking
  100,000 / 100,000                      =  1.00
seconds in a day, REPORTED
  86,400
utilization of one blocking resolver, REPORTED
  100,000 / 86,400                       =  1.16

One blocking resolver is over 100% utilized just resolving new hosts, before a single page is fetched — 116% of a day’s seconds, not 100%.

The neat 1.00 is the 1e5 shortcut landing on itself, which makes it look like a coincidence worth remembering. It is not. A utilization is exactly the kind of figure ch 02 says to re-divide before reporting, and the honest number is 1.16. That does not merely saturate the resolver — it falls behind by about four hours of work every day and never catches up.

But the real problem is not capacity. It is blocking — the calling thread sits idle and unusable until the answer arrives.

getaddrinfo is the standard C library call that every language’s DNS lookup eventually reaches. It is synchronous. In several implementations of libc — the C standard library the operating system ships — it also serializes on a process-wide lock. So a crawler with one thread per fetch stalls its entire fleet behind DNS, no matter how many threads you give it.

The fix has two parts: an asynchronous resolver that keeps many queries outstanding at once over UDP (the connectionless protocol DNS runs on), plus an aggressive local cache. Price both:

resolutions per second at the recursive resolver
  1,000,000 / 100,000                    =  10
DNS cache hit rate against the day's fetches
  1 - 1,000,000 / 33,333,333             =  0.97

10 recursive resolutions per second. Trivial — once it is not in the critical path. The 97% hit rate is why: only the first fetch of each host on a given day pays for a resolution.

One deliberate protocol violation to name before the interviewer does. Crawlers hold DNS entries far past their TTL — minutes to hours, against CDN TTLs of 30-60 seconds. A crawler does not need a browser’s failover precision, and re-resolving on every fetch would put you straight back at 100% resolver utilization.

11. Freshness: re-crawl driven by observed change rate

How often should you re-fetch a page you already have? The result contradicts everyone’s intuition, including the answer most candidates give.

The freshness formula

Model a page’s changes as a Poisson process at rate lambda: changes arrive independently, at a constant average rate of lambda per unit of time, with no memory of when the last one happened. Re-crawl the page every T units of time.

Then freshness F is the fraction of the time your stored copy matches the live page, averaged over one re-crawl interval T:

F = (1 - e^(-lambda T)) / (lambda T)

The only input that formula has is the product lambda T — the expected number of changes per crawl interval. lambda T = 1 means “crawled exactly as often as it changes.” Evaluate it at four points:

at lambda T = 0.1
  (1 - 0.904837) / 0.1                   =  0.952
at lambda T = 1
  (1 - 0.367879) / 1                     =  0.632
at lambda T = 7
  (1 - 0.000912) / 7                     =  0.143
at lambda T = 30
  (1 - 0.000000) / 30                    =  0.033

Crawling a page exactly as often as it changes leaves you fresh only 63% of the time. That is the first surprise, and it kills the intuition that matching the change rate is “keeping up.”

The budget split, where intuition fails badly

The second surprise is bigger. Take two pages and a budget of one fetch per day to split between them:

• A wire feed that changes 10 times a day, so lambda = 10.
• A slow blog that changes once every 10 days, so lambda = 0.1.

The table below tries four splits. Read the first row like this. “Proportional to lambda, 99/1” splits the budget as 10/10.1 and 0.1/10.1, so:

• The feed gets 0.990 fetches a day. Its interval T is 1 / 0.990 = 1.01 days, so lambda T = 10 x 1.01 = 10.1, and the formula gives F = 0.099.
• The blog gets 0.0099 fetches a day. Its interval is 1 / 0.0099 = 101 days, so lambda T = 0.1 x 101 = 10.1 as well — the same number, which is exactly what “proportional” means — and again F = 0.099.

The Total column is the sum of the two pages’ freshness, so the best possible score here is 2.0.

uniform against proportional
  0.956 / 0.198                          =  4.83
optimal against uniform
  0.962 / 0.956                          =  1.006

Allocating crawl budget in proportion to change rate is 4.8x worse than allocating it uniformly, and it is the policy every candidate proposes.

The mechanism is worth saying slowly. A page changing 10 times a day is stale almost all the time no matter what you do, so every fetch spent on it buys nearly nothing. The same fetch spent on a slow page buys almost all of that page’s freshness. Proportional allocation spends the budget precisely where it is worth least.

The optimal policy is therefore non-monotonic in lambda: as a page changes faster, the effort you should spend on it first rises, and then falls back toward zero for pages that change faster than you could ever track.

Uniform is within 0.6% of optimal and needs no per-page estimate, so uniform is the answer to ship. Do not build the estimator that gets you the last 0.6%.

Estimating lambda, and what a 304 buys

You still want a rough per-page lambda to cap the fast movers. Estimate it from the observed intervals between changes, using exponential smoothing over the last few fetches — a weighted average that lets recent observations count for more.

A 304 is evidence of no change and must update the estimate too. Skip that and every unchanged page drifts toward a fictitious high rate, because you only ever feed the estimator the fetches where something moved.

Then use conditional requests, which carry the previous ETag or Last-Modified value so the server can answer 304 Not Modified with headers alone:

bytes for a 304 Not Modified, headers only            500
bytes for a 200 carrying the document             100,000
bandwidth saving on an unchanged page
  100,000 / 500                          =  200

A 304 is 200x cheaper in bytes and exactly as expensive in fetch slots. It still occupies a connection and still burns a full crawl-delay interval.

Put that against the two constraints already derived. 3a volume bandwidth storage found peak bytes at 53% of one NIC’s capacity. 3b the politeness ceiling the number that sizes everything found host slots to be the binding constraint. So conditional requests save the resource you have plenty of and none of the resource you are short of.

They are still worth doing, for the origin server’s sake and for your bandwidth bill. Just do not let anyone claim they buy throughput.

Coverage against freshness: the split that actually matters

How much of the fetch rate goes to re-crawling pages you already have, versus discovering pages you do not? That is the decision with a schedule attached:

crawl budget, pages per second
  333
share spent on re-crawl
  0.50
discovery rate that leaves
  333 x 0.50                             =  166.5
months to build a 10 B corpus, thinking, at 1e5
  10,000,000,000 / 166.5 / 100,000 / 30  =  20.0
months, REPORTED, at 86,400
  10,000,000,000 / 166.5 / 86,400 / 30   =  23.2

A 50/50 split means the corpus takes 23 months to build.

The 20.0 is the drill convention. A build schedule is the definitional case of a number that has to be re-divided at 86,400 before anyone plans against it, and three months of difference on a two-year programme is not a rounding detail to whoever owns the roadmap.

State the trade explicitly: freshness and coverage come out of the same budget, and the split is a product decision with a schedule attached.

The code below evaluates the freshness formula and the four budget splits. Note how total_freshness converts a budget share into an interval — 1.0 / (budget * s) — which is the same step the table walkthrough did by hand. The assertions reproduce every number in that table, including the 4.8x gap between uniform and proportional allocation, and the search over range(1, 100) finds the optimal split rather than asserting it.

import math


def freshness(lam, period):
    """Time-average probability a copy is current under Poisson change."""
    x = lam * period
    return 1.0 if x == 0 else (1 - math.exp(-x)) / x


def total_freshness(rates, shares, budget=1.0):
    """shares[i] is page i's fraction of the fetch budget, in fetches/day."""
    return sum(freshness(lam, 1.0 / (budget * s))
               for lam, s in zip(rates, shares) if s > 0)


RATES = [10.0, 0.1]                      # a wire feed and a slow blog
proportional = [r / sum(RATES) for r in RATES]
uniform = [0.5, 0.5]
best = max(((a / 100, 1 - a / 100) for a in range(1, 100)),
           key=lambda s: total_freshness(RATES, list(s)))

assert abs(freshness(1.0, 1.0) - 0.632) < 0.001
assert abs(total_freshness(RATES, proportional) - 0.198) < 0.002
assert abs(total_freshness(RATES, uniform) - 0.956) < 0.002
assert abs(total_freshness(RATES, list(best)) - 0.962) < 0.002
assert 0.28 <= best[0] <= 0.38           # optimal is ~33% to the fast page
assert total_freshness(RATES, uniform) / total_freshness(RATES, proportional) > 4.8

12. Bottlenecks and scaling

One table holds every resource the crawler consumes and the number that bounds it, and it makes the point of the whole chapter visible at a glance: only one of them is actually binding. Everything below the first two rows has slack; those two do not.

The scaling conversation people expect is “add fetchers.” The scaling conversation that is true is “add hosts.”

Make it concrete. Suppose the frontier is deep on 50 hosts — millions of URLs each, but only 50 distinct servers. A thousand machines fetch 50 x 0.833 = 42 pages per second between them, because that is all politeness permits. The other 999 machines are idle by construction, and no amount of hardware changes that number.

13. Failure modes

Nine ways the design fails in production, each with the trace an operator would actually see, the signal that detects it, and the guard that prevents it. Most of these are silent by default, which is why the detection column is the interesting one.

Four terms in that table deserve a line each:

• 429 and 403 are the HTTP statuses for “too many requests” and “forbidden.” A spike in either is a server telling you that your politeness is not working.
• Jitter is a small random offset added to a scheduled time, so that many timers do not all fire in the same instant.
• A private, loopback, or link-local address is one that is only meaningful inside a network — 10.x, 127.0.0.1, and the 169.254.x range respectively. The reason to refuse them is that 169.254.169.254 is the cloud metadata endpoint, so a crawler that follows a link to it fetches its own credentials and files them in the document store. Refuse them after resolution, not before, because a public hostname can resolve to a private address.
• Enforced streaming means the size cap is checked while the response is being decompressed, not after. “After” is the point at which 10 GB is already in memory.

14. Alternatives rejected

Seven designs a candidate is likely to propose, each rejected with a number rather than a preference. Two of them fail for a different reason than the folklore gives, which is the part worth remembering.

One global priority queue for the frontier. Good: trivial, and priority is exact. Rejected because a page yields ~100 links to one host, so the head of the queue is always a burst against a single server — you either violate politeness by 100x or scan the queue looking for a legal URL. The two-layer frontier exists precisely to make the politeness check O(1) instead of a search.

Partition the frontier by hash(url). Good: perfectly even load, which is what ch 05 optimizes for. Rejected because it spreads one host’s URLs across every shard, so “one connection to this host” becomes a distributed lock taken on every fetch. Partition by hash(ip): politeness is then a local timestamp comparison. The uneven load this creates is real and is handled by the per-host cap, not by the hash.

An exact URL set in a database instead of a bloom filter. Good: no false positives, so no page is silently lost. Rejected — but not on device count, and the correction is worth stating, because the familiar version of this argument is wrong.

That familiar version divides the lookup rate by 10,000 IOPS — input/output operations per second — and concludes you need seven NVMe devices, NVMe being the fast flash-storage interface that replaced SATA.

The 10,000 figure is what one device delivers when you ask it for one thing at a time and wait for the answer. It is a latency number misread as a capacity number (The two rows that will burn you). Ask the device for many things at once — at queue depth, in the jargon — and it delivers about fifty times more:

extracted links per second at peak, offered load
  666 x 100                              =  66,600
random-read IOPS one NVMe device supplies at depth, capacity
  500,000
devices needed for the seen-lookups alone
  66,600 / 500,000                       =  0.13

A tenth of one device, so the I/O objection evaporates and the old “6.7 devices” line is wrong.

What actually rejects the exact set is footprint and latency:

• Footprint. 10 billion URLs at about 70 bytes a key is 700 GB, against the 25 GB the filter needs. It cannot live in RAM.
• Latency. Because it cannot live in RAM, every lookup becomes a ~100 microsecond device read instead of a ~100 nanosecond memory reference. That is a thousandfold more time, on the hottest path in the system.

The right answer is still both: bloom filter in front, exact set behind. Only the 0.0067% of lookups that say “maybe” ever pay that latency.

SHA-256 of the body for content dedup. Good: exact, cheap, no index. Rejected because a rendering timestamp changes every byte of the hash while changing zero bits of meaning, so recall against the 20% near-duplicate band is zero — 200 million wasted fetches a month (Deep dive 3 content dedup where exact hashing has zero recall).

Render every page in a headless browser — a real browser engine driven by code, with no window on screen, so that the page’s JavaScript actually runs. Good: you see what a user sees, and single-page apps become crawlable. A single-page app, or SPA, is a site that ships an almost-empty HTML document and builds the visible content in the browser, which means a crawler that reads only the HTML sees nothing.

parse-only CPU at peak
  666 x 0.010                            =  6.66
headless render CPU at 1 s per page
  666 x 1.0                              =  666
ratio
  666 / 6.66                             =  100

Rejected at 100x: 6.7 cores becomes 666.

Render selectively instead. A cheap classifier reads the raw HTML and asks two questions: does the body contain real text, and does the page load a known single-page-app framework? Only pages that answer badly get a browser.

The render budget then becomes an explicit, capped fraction of the fleet rather than an unbounded multiplier on it.

Re-crawl in proportion to change rate. Good: intuitive, and it is what everyone proposes. Rejected because it scores 0.198 against uniform’s 0.956 (Freshness re crawl driven by observed change rate) — a 4.8x loss — since fetches spent on a page you can never keep up with buy nothing.

Skip robots.txt caching and fetch it per URL. Good: always current. Rejected because it doubles request volume against every host.

The part that makes it self-defeating rather than merely expensive: each of those robots.txt fetches consumes one of the host’s politeness slots, taken from the very host the file exists to protect. So you halve your own throughput and double your request load on every server you crawl.

And you get nothing for it. You are 33x more current about a file that changes weekly. Being 33x more current is not being 33x more polite — fetching a file 33 times as often is 33 times ruder, and it is the site that pays for it.

The correct trade is a shared 24-hour cache and a short TTL on the negative verdict, which is Robotstxt.

15. Interviewer pushback

Seven questions, each with the answer and the thing it is really testing.

“How do you scale this to 10,000 pages per second?” Testing: whether you know what the bottleneck is.

Not with more machines. At one connection per host and a one-second delay, one host yields 0.833 pages/s, so 10,000 pages/s needs 10,000 / 0.833 = 12,000 distinct hosts with URLs ready at that instant.

For the fleet, re-derive rather than scale. 10,000 pages/s is offered load, and 3a volume bandwidth storage’s 267 Mbps is an average — so multiplying it by the peak ratio 10,000 / 666 is the one move you must not make.

From the page rate directly: 10,000 x 100 KB x 8 is 8 Gbps of offered load. A 1 Gbps NIC is capacity, so that is eight NICs saturated — call it ten at 80% utilization. Parsing is 10,000 x 0.010 = 100 cores of demand, or 125 cores of capacity at the same 80%. Both easy.

The work is entirely in the frontier: 12,000-plus back queues, a prioritizer that spreads across hosts rather than depth-first into one, and a per-host cap that forces breadth. If the frontier only has 500 live hosts, ten thousand machines still fetch 417 pages a second.

“Why not just hash the URL to pick a shard?” Testing: whether the shard key was chosen or copied.

Because the invariant I have to enforce is per-server, not per-URL. Hashing on the URL puts one host’s pages on every shard, so every fetch would need a distributed lock on that host’s last_fetch_at — a coordination round trip on the hottest path in the system.

Hashing on the resolved IP makes each server the exclusive property of one shard, and politeness collapses to a local timestamp comparison. I pay for that with uneven shard load, which I bound with the per-host cap.

Note that I use the other key elsewhere: the URL-seen filter shards by hash(url), because dedup is per-URL. Two shard keys, each chosen to make the thing it protects local.

“Your bloom filter has a 1% false-positive rate. Is that fine?” Testing: whether you know what a false positive costs here.

No, and the reason is that the cost is invisible. In an LSM store a false positive is one wasted disk read. Here it is a URL declared already-seen that was never fetched, so the page never enters the corpus and nothing logs it.

At 10 bits per key the rate is 0.82%, which over 10 billion URLs is 82 million pages silently missing. Twenty bits per key gets that to 0.0067%, or 670,000 pages, and the extra RAM is 12.5 GB — about 6.5 million pages recovered per gigabyte. So I run at 20 bits, and I take the target rate to the product owner as a number of missing pages, not a percentage.

The other thing I would say unprompted: the filter degrades on a cliff. Put twice the design keys in it and the rate goes to 1.9%, a 283x jump, and the only symptom is a crawl that quietly shrinks. So I alert on inserted-key count against design capacity, not on any measured error rate — because there is no ground truth to measure against.

“Two URLs return the same article. How do you notice?” Testing: whether you reach for an exact hash.

Not with SHA-256, because the pages differ — one has a render timestamp, one has a different ad slot, one says “3 comments.” An exact hash has zero recall on that band, which is about 20% of the corpus, or 200 million pages a month of wasted fetch budget.

I use a 64-bit simhash over word shingles and call anything within Hamming distance 3 a duplicate.

The interesting part is the lookup. With 10 billion fingerprints, I split the 64 bits into six blocks and index every combination of three, which is 20 tables. Pigeonhole says at distance 3 at least three blocks are untouched, so one table must hit. Each probe returns about 4.7 candidates instead of the 152,000 a four-table split would return. That is 1.6 TB of index against 320 GB, and it removes 406 million comparisons a second at peak. Worth it.

“A site tells you Crawl-delay: 10. Do you honor it?” Testing: whether politeness is a value or a checkbox.

Yes, and I would say what it costs so the trade is explicit. The period becomes 10.2 seconds, so that host yields 0.098 pages/s and a million-page site takes 118 days. (102 is the same figure at the 1e5 drill divisor; a schedule is a result, so I would quote 118.)

If that site matters, the fix is not to ignore the directive. It is to get a sitemap, a feed, or a bulk export — which is a relationship, not a scheduler change.

The related thing I would flag: politeness has to be keyed on the resolved IP. Five thousand shared-hosting names on one box at 0.833 pages/s each is 4,165 requests a second at one server — a denial of service I would be responsible for, even though every individual host was polite.

“Your fetchers are at 5% utilization. What is wrong?” Testing: whether you know where the stall is.

Three candidates, in the order I would check them.

1. DNS. One blocking resolver at 100 ms per uncached lookup, against a million new hosts a day, is fully utilized on its own — and a synchronous getaddrinfo serializes the fleet behind it. The fetchers sit idle while resolution queues.
2. Host diversity. If the frontier is deep but narrow — a few hundred hosts with millions of URLs each — the politeness heap is legitimately empty most of the time and the workers are correctly doing nothing. That shows up as back queues in use far below the configured count.
3. The router blocking. If all back-queue slots are held by hosts whose next fetch is a second away, front-queue URLs for fresh hosts cannot get in.

The tell between them is whether hosts_in_flight is at its ceiling or on the floor.

“How often do you re-crawl?” Testing: whether “based on change rate” is a real policy.

I estimate a per-page change rate from observed inter-change intervals, but I do not allocate budget in proportion to it, because that is measurably the wrong policy.

Under Poisson changes, freshness is (1 - e^(-lambda T)) / (lambda T). Take a page changing 10 times a day and one changing every 10 days, with one fetch a day between them: proportional allocation scores 0.198 total freshness, uniform scores 0.956, and the optimum is 0.962 at a 33/67 split. Proportional is 4.8x worse, because fetches spent on a page that changes faster than you can ever track buy almost nothing.

So I ship uniform-ish, with a cap on how much any one fast-changing page can claim. Then I spend the effort on the split that actually matters: how much of the 333 pages/s goes to re-crawl versus discovery. At 50/50 the corpus takes 23 months to build — 20.0 if you leave it at the 1e5 divisor, and a build schedule is exactly the number to re-divide at 86,400 before saying it out loud. That is a product decision, not an engineering one.

Cheat sheet

Every result in the chapter, one line each, in the order you would say them at a whiteboard.

Related: 05 — Consistent Hashing is why the frontier shards on IP and the seen-set on URL; 06 — Key-Value Store derives the bloom-filter formula this chapter re-prices; 02 — Back-Of-The-Envelope is the estimation discipline throughout.