Distributed Web Crawler Architecture Deep Dive: Frontier, Politeness, Dedupe and Storage

This page opens each component of the Atlas Discovery crawler and shows how it works inside: data shapes, algorithms, state transitions and the places where one component's guarantee ends and the next one begins. It assumes you know what a crawler is; each new term is defined when first used.

Atlas Discovery in one paragraph. Atlas crawls public pages from three fictional publishers (news-a, docs-b, store-c at .example.test) to feed a search index. A URL is an address; an origin is scheme://host:port and is the unit of politeness; the frontier is the durable set of discovered URLs waiting to be fetched; a lease is a time-limited claim by a worker, carrying a fence token that lets storage reject stale writers; robots.txt is the publisher's published crawling preference. The tracked page throughout is U-104, news-a.example.test/articles/chip-supply. Assumed scale: 10 million successful fetches per day, about 116 per second.

The tables below are logical, not a mandated schema. They show which fields exist, why, and which constraint protects which invariant.

Two design choices deserve a reason. First, keeping raw_discovered_url beside normalized_url makes normalization reversible and auditable. Second, url_document separates the address from the content, because the same text can live at several addresses and one address can serve different text over time.

The state machine

The spec-level terminal states map as follows: FAILED covers retry-exhausted URLs (the retryable form is LEASED → DEFERRED with next_fetch_at in the future), BLOCKED and QUARANTINED are terminal until a policy or parser change, and SUPPRESSED is terminal until an opt-out is withdrawn.

The normalizer produces one identity for provably equal addresses and refuses to merge anything uncertain. The goal is stable identity with auditability, not the shortest key.

Trailing slashes, encoding, internationalised names and collisions

Trailing slash. /docs and /docs/ are different resources by the URL rules, and many servers redirect one to the other. Atlas does not strip slashes blindly. It records the redirect when it sees one and learns the origin's preferred form. Percent-encoding. %7e and ~ are equivalent (unreserved characters), so the normalizer decodes unreserved bytes and upper-cases the hex digits of the rest, but it never decodes %2F, because a slash inside a segment is not a path separator. Internationalised hosts. bücher.example.test becomes its ASCII (punycode) form before comparison, and mixed-script lookalike hosts are flagged for review rather than merged. Collisions. Two raw URLs that normalize to the same identity are a *collision*; the system keeps both raw spellings in discovered_from provenance, and an operator can list the collisions a rule produced. That list is how F02 is caught: a rule that suddenly creates thousands of collisions on one origin is suspicious.

Redirect and canonical relationships. A redirect is the server's statement that a fetch of A returned B, and it is evaluated as a new candidate (the fetch pipeline chapter). A canonical link is the page's claim about its preferred address and is only a hint. Neither rewrites the identity of A: the frontier keeps A, records A → B or A ~ B as an edge, and decides to merge only through repeated redirects confirming it or a matching content hash.

Failure behavior: a parser error rejects with a reason and never guesses. Internationalised hostnames are converted to their ASCII form so that visually similar names are compared reliably. rel=canonical is stored as a hint and may later add a *candidate* merge, but only content comparison (chapter 8) turns a hint into a decision.

The parser reduces a file into groups of rules for named user-agents. The evaluator finds the applicable group, then the best matching rule for a path.

Wildcard * and a dollar-sign end anchor are supported in patterns. Atlas picks the most specific user-agent group and does not merge groups of different agents. Fetching the file is itself a fetch: redirects are bounded and every hop is checked. Status handling is deliberate. 2xx: parse and cache for up to 24 hours or less if the origin sends shorter cache headers. 4xx: the file is unavailable, which RFC 9309 says means no crawl restrictions, so crawl normally (do still honor everything else). 5xx or network error: unreachable, so treat the origin as disallowed temporarily, reuse the last good copy for a bounded time and back the origin off. An oversize file is truncated at a limit and parsed as far as read, which the document says is acceptable at around 500 KiB.

Every verdict records policy_version. At claim time and after each redirect the claim transaction compares the URL's verdict version against the current one; a mismatch triggers a recheck before any connection. A Crawl-delay line is a hint from outside the standard; Atlas treats it as one input into the origin's rate, never as an authority that can raise the rate above the operator's cap.

The frontier combines two structures: the table of URLs and, derived from it, a priority-ordered view of origins that are due. The claim is the only operation that moves a URL toward the network.

The scheduler keeps origins in a min-heap keyed by next_eligible_at. Popping gives the origin that became due first. An origin with in_flight == max_in_flight, an active backoff_until or an exhausted budget is skipped and re-inserted with a later key. Inside an origin, URLs are ordered by priority, then by age. Aging adds a bonus for time waiting so that a low-priority origin cannot starve.

Aging and starvation caps. An origin's effective priority is base + age_weight × minutes_waiting, capped so aging cannot outweigh critical freshness work entirely. A hard starvation cap overrides everything: any origin with an eligible URL and no service for 30 minutes is moved to the front. Class quotas limit one class to a share of attempts while others have eligible work. Partitioning and host affinity. The frontier is partitioned by hash of origin_key, and each partition is served by schedulers that own whole origins, so an origin's bucket is only ever touched by one partition's claim transaction. Workers are stateless and may take work from any partition, but because they present the lease fence on commit, they need no affinity for correctness; affinity (keeping an origin's connections on one worker) only saves TLS handshakes.

LEASE is longer than the expected fetch time but not so long that a crashed worker delays recovery for minutes. A sweeper returns rows with lease_expires_at < now to ELIGIBLE and decrements in_flight. A worker finishing early renews nothing; one needing more time extends the lease with its fence token, and the extension fails if the fence changed.

The fetcher is a pipeline of small gates, each of which can stop the request before more expensive work begins.

Connect-time pinning means that the address the validator approved is the address the socket opens. Resolving the name a second time inside the HTTP library would let a rebinding attacker return a public address for validation and an internal one for the connection. IPv4-mapped IPv6 forms such as ::ffff:10.0.0.5 are unwrapped before checking. Redirect hops are capped at five and the sequence of normalized URLs is remembered to stop loops. Limits apply to bytes read after decompression: the reader aborts the stream at the cap rather than trusting Content-Length.

Timeouts and cancellation. Three separate limits apply: connect (a few seconds), time to first byte, and a total deadline for the whole response. When the deadline passes the fetcher cancels the read, closes the socket and records timeout; a result arriving after cancellation is ignored. TLS and SNI. The client sends the original hostname in SNI and verifies the certificate against that name, *while connecting to the pinned validated IP*; connecting by IP without the name would fail verification, and verifying against the IP would be wrong. Soft 404. A page that returns 200 with text like 'not found' is detected by comparing its extracted text and title against a stored fingerprint of the origin's error page, and by a very short text with no outlinks; it is stored with soft_404=true and excluded from the index, but it still counts against the fetch budget. Transfer encodings. Chunked bodies are read incrementally, and Content-Encoding decoding happens in the same size-limited stream.

The parser turns bytes into a document and a list of candidate links. Its output is evidence; later stages decide what to do with it.

It detects the character encoding (response header, byte-order mark, a meta tag, then a statistical guess) and records which method won. It extracts the visible text (excluding scripts and styles), title, headings, language, rel=canonical, robots meta directives and links with their anchor text. Relative links resolve against the <base> element if present, otherwise the final response URL after redirects, which is why the fetcher stores both. A nofollow marking influences priority and policy rather than being silently ignored, and frames and image-map links are optional extraction targets. Parse failures (broken markup is common) degrade to best-effort text with a parse_quality flag; a parser exceeding its time or memory budget quarantines the document.

Extraction confidence. Each document carries parse_quality (clean, repaired, partial) and text_ratio (visible text bytes over body bytes). A low ratio with a script-heavy body is the signal that feeds the render-lane decision. Raw HTML versus rendered DOM. Links found only after scripts run are tagged from_render=true; they enter the frontier like any other candidate but with lower initial priority because they cost more to confirm. Document types. HTML and plain text are parsed; PDF and feeds go to dedicated extractors behind the same limits; images, video and archives are skipped by the type allowlist. Malformed markup is handled by the parser's error-recovery rules, not by regexes, and never aborts the batch.

Extraction yield is also an observation: if a URL class suddenly returns almost no text, either the page changed, the site moved content into scripts (chapter 10) or the fetcher is receiving a block page. The parse stage therefore reports words extracted and links found per origin.

Three mechanisms answer three questions at three costs.

Content hashing needs a decision about *what* is hashed. Hashing raw HTML marks a page changed whenever an advertisement rotates. Atlas hashes normalized main text. When U-110 (/print) and U-104 produce the same text hash, both URLs reference one documents row and url_document records two provenance entries; the second URL is not dropped, so the discovery path and a possible canonical declaration are preserved.

Bloom filter sizing. A Bloom filter with *n* inserted items and false-positive rate *p* needs about m = −n·ln(p) ÷ (ln 2)² bits and (m ÷ n)·ln 2 hash functions. For one billion URLs at 1 percent that is roughly 9.6 billion bits, about 1.2 GB. Because a hit means 'maybe', the exact store confirms before any discard (diagram below). The filter's job is to remove most *lookups for new URLs*, never to remove URLs.

Recrawl turns the crawler from a snapshot into a monitor. Each page's history decides when it is due.

A conditional request carries the last ETag as If-None-Match and/or the last Last-Modified value as If-Modified-Since. A 304 response has no body, and the stored document stays current. A 200 is parsed and hashed; the page counts as changed only if the content hash differs. Servers vary: some give weak ETags, some change an ETag per request, some ignore conditional headers. Atlas therefore tracks per-origin validator reliability (how often a 200 followed by an equal hash happened) and, past a threshold, stops trusting validators there.

Estimating the change interval. For each page keep a smoothed estimate: after each recrawl, if the content hash changed, est = max(MIN, 0.5 × est) (come back sooner); if unchanged, est = min(MAX, 1.5 × est) (come back later). A page that changed three times in three visits converges to MIN in a few steps; a stable archive page reaches MAX in a few more. Importance. A score from inbound-link evidence, audience tier of the requesting tenant and whether downstream queries hit the page. Multi-tenant prioritization. Each tenant has a share of the recrawl budget; unused share flows to others, and a tenant cannot starve discovery because discovery has its own reserved fraction. Preventing storms. Intervals are jittered by ±10 percent, newly onboarded batches are spread over the interval using hash(url) mod interval as an offset, and recrawl enqueue is rate-limited per origin so a thousand pages becoming due at 09:00 do not become a burst. Staleness metrics. Freshness gap is now − last_changed_at_observed for pages known to have changed, reported as percentiles by priority class, plus the share of due pages that are overdue.

Budgeting: a fixed fraction of attempts is reserved for discovery, the rest is split into freshness classes. Recrawl candidates still pass through the origin bucket, so a very volatile site cannot override politeness by scoring highly.

Rendering is a separate service with its own contract: take a URL that has passed the same checks, return the post-script document or a failure.

Selection: for a page class, fetch raw HTML and rendered DOM for a sample and compare extracted words. If raw extraction recovers at least a chosen fraction (say 90 percent) of rendered text, render nothing. Otherwise the class is marked render-required. The render worker runs a headless browser in an isolated sandbox with no access to internal networks, a hard wall-clock limit, a memory cap and a cap on sub-requests. Every sub-request, including images, scripts and API calls the page makes, is routed through the same egress gate and counted against the same origin bucket; a page that makes forty requests uses forty units of politeness budget. If the lane is saturated, pages fall back to raw extraction and are marked render_skipped. Outputs are tagged rendered=true so downstream consumers can compare quality.

The write path crosses four systems and no shared transaction. Correctness comes from the order of operations and from idempotency at each boundary.

Reconciliation. A periodic worker compares three things: object-store keys with no referencing row older than a grace period (delete them), rows in FETCHED with no outbox event (insert the missing event), and index-ready counts against document counts per origin. Mismatches are alerts, not silent repairs, except for the two safe ones above. The index-ready event is written only after the document row exists, so no consumer ever sees an event for content that is not durable.

The outbox solves the dual-write problem: updating a database and publishing a message cannot be done atomically across two systems. Writing the event as a row in the same transaction guarantees an event exists if and only if the document row exists. The relay is at-least-once, so events are idempotent: the consumer stores processed event_ids or applies updates keyed by document id and content hash.

Politeness is a property of the origin even when the crawler runs in several regions, so each origin's bucket needs one owner at a time.

Partition key and hot partitions. The partition key is origin_key, because the origin's bucket is the coordination boundary. Skew arises when a single origin holds a huge share of URLs: its rows are heavy, but its *rate* is still capped by politeness, so the load it puts on the scheduler is small; the real hot spots are storage size and sweeper scans. The fix is to sub-partition a giant origin's URL rows by hash(url) while keeping one bucket row for the origin, so claims still serialize on that single row. Region choice follows network distance and residency; failover reassigns ownership with a higher token. A control plane assigns each origin to a region with an ownership token that increases on every reassignment (41, then 42). The bucket accepts a claim only if the presented token equals the current one. During a partition the old owner may keep working until its lease expires, so a bounded window of double scheduling exists. Large origins may be split into pre-allocated shares (for example, 60 and 40 percent of the cap) so that both regions can run without per-request coordination; the shares sum to the cap. The guarantee is therefore: fenced ownership with *bounded* overshoot, not a perfectly synchronized global counter.

Rules change: robots files are edited, publishers opt out, internal blocklists grow. The design records which version of which policy produced each decision.

policy_version is a monotonically increasing number per origin covering robots rules, suppressions and scope settings. A verdict is valid only for the version that produced it; the claim transaction rechecks if versions differ. Suppression (an opt-out or deletion request) outranks everything: it blocks the fetch, triggers deletion workflows and is itself retained as a record without the content it removed.

A crawler without reason codes is unexplainable. Every state change in the frontier carries one.

Operational formulas. Attempt rate = successes ÷ success ratio (115.74 ÷ 0.80 = 144.68 per second). Origin saturation = requests per second to an origin ÷ its cap; sustained values near 1.0 with rising 429s mean the cap is too high. Byte throughput = attempts × mean compressed bytes. Backlog age = now − next_fetch_at of the oldest eligible URL. Changed-page yield = changed pages ÷ recrawl attempts. Crawl coverage = distinct pages stored ÷ pages known to exist from sitemaps or samples. A falling 304 share with a stable changed-page yield means validators have degraded.

The crawler is an automated client with network reach and a store of third-party content, so it carries its own security and compliance duties.

A deletion request is processed as a small state machine: RECEIVED → VERIFIED → SUPPRESSED → DELETING → DELETED → AUDITED. Each step is idempotent and keyed by the suppression id, so a crash mid-deletion resumes rather than restarts. The suppression record outlives the deleted data, because it is what prevents the content from being fetched again. Identity of the requester is verified against the origin (for example, a token served at a known path) before any deletion happens, so a stranger cannot erase a publisher's pages from the index.

Each invariant below is a statement that must always hold, with the test that would catch a violation.