Web Crawler Politeness & Priority — Front Queues, Back Queues, Router, Traced

"Use a queue" is not an answer — a crawler needs two

Model the web as a directed graph: pages are nodes, hyperlinks are edges. Crawling is graph traversal, so the instinct is to reach for BFS with a FIFO queue. DFS is a poor fit immediately — the depth can be effectively unbounded, so a depth-first crawler wanders into one site forever. So BFS with a FIFO queue it is.

Except a single FIFO queue has two independent defects, and this is the part usually skipped:

• It is impolite. Most links on a page point back to the same host. Every link on a Wikipedia page is a Wikipedia link, so a FIFO queue fills with one host's URLs and the crawler's parallel workers all hammer that one server. Thousands of requests per second to one site is indistinguishable from a denial-of-service attack, and you will be blocked — correctly.
• It is indiscriminate. FIFO has no notion of value. A random forum post about Apple products and the Apple homepage arrive in arrival order, when the homepage plainly deserves to be crawled first.

These two problems pull in opposite directions. Politeness wants to slow down and spread across hosts; priority wants to rush the valuable URLs, which are often concentrated on a few big hosts. You cannot satisfy both in one queue with one ordering rule — which is exactly why the URL frontier is built as two stacked queue layers with a translation step between them.

Layer 1: front queues enforce priority

The prioritizer takes URLs and computes a priority from measures of usefulness — PageRank, website traffic, update frequency. Each front queue f1…fn holds one priority band.

The front queue selector then chooses which band to draw from: it picks randomly, with a bias toward higher-priority queues. That word "random" is doing real work. A strict "always drain the highest queue first" rule would starve the low-priority bands forever, and a crawler that never revisits low-value pages eventually has a stale index of exactly the long tail that makes a search engine comprehensive. Biased-random sampling gives the high band most of the throughput while guaranteeing the low band a nonzero share.

Layer 2: back queues enforce politeness

The rule to implement is: download one page at a time from any given host, with a delay between consecutive fetches. Three components achieve it:

• Queue router — guarantees that each back queue b1…bn contains URLs from one host only.
• Mapping table — maps each hostname to its queue, so the router knows where a URL belongs.
• Queue selector — maps each worker thread to one back queue; that worker downloads only from that queue, one URL at a time, sleeping a delay between tasks.

Trace the invariant: host → exactly one queue → exactly one worker → serialized fetches with a delay. Because the mapping is one-to-one at every hop, two workers can never be in flight to the same host simultaneously — politeness is a structural property of the data layout, not a rate check someone has to remember to call. That is what makes this design worth learning: the correctness argument is "there is only one worker that can touch this host," which is far stronger than "we check a counter first."

So the full frontier is: front queues manage prioritization, back queues manage politeness, and the router between them is where a priority-ordered stream is reshuffled into per-host streams.

Where the frontier actually lives

In a real search-engine crawl the frontier holds hundreds of millions of URLs. Neither extreme works: memory is not durable and not large enough; pure disk is too slow and becomes the crawl's bottleneck.

The answer is hybrid — the majority of URLs live on disk, with in-memory buffers for enqueue and dequeue that are periodically flushed. This is the same pattern as the key-value store's commit log plus memtable, for the same reason: buffer the random small operations in RAM, pay the disk in large sequential batches.

Freshness: the frontier's third job

Pages are added, edited and deleted continuously, so crawled data goes stale and pages must be recrawled. Recrawling everything is prohibitively expensive, so two strategies apply: recrawl based on a page's update history (a page that has never changed in a year does not need weekly visits), and recrawl important pages first and more often. Note that this reuses the priority machinery rather than adding new machinery — freshness is just priority with a time term.

The HTML downloader, and being a good citizen

The HTML downloader fetches pages over HTTP, and before fetching anything from a site it must consult robots.txt — the Robots Exclusion Protocol, by which a site declares what crawlers may download. A real fragment from Amazon's file:

User-agent: Googlebot
Disallow: /creatorhub/*
Disallow: /rss/people/*/reviews
Disallow: /gp/pdp/rss/*/reviews
Disallow: /gp/cdp/member-reviews/
Disallow: /gp/aw/cr/

Fetching robots.txt before every request would double your traffic and be its own kind of rudeness, so cache the file and refresh it periodically. Note the interaction with politeness: the robots.txt fetch itself must go through the same per-host serialization, or your politeness accounting is off by a factor of two.

Performance optimizations

• Distributed crawl — partition the URL space across many servers, each running many threads, each responsible for a subset.
• Cache DNS results — DNS resolution is a synchronous, often slow step; without a cache it dominates per-fetch latency.
• Locality — place crawl servers geographically near the hosts they crawl.
• Short timeouts — some servers never respond; a generous timeout means a worker (and therefore a whole host's queue) blocks on one dead URL.

Robustness and extensibility

Consistent hashing distributes load across downloaders so servers can be added or removed without reshuffling the whole space. Saving crawl state and data lets an interrupted crawl resume from checkpoint rather than restart. Exception handling and data validation keep one malformed page from killing a worker. For extensibility, the design admits new modules at the same seam — a PNG downloader for images, or a web-monitor module watching for copyright violations — because the frontier only produces URLs and does not care what consumes them.

Problematic content to detect and skip

• Redundant content — roughly 30% of the web is duplicated; compare hashes/checksums rather than full documents.
• Spider traps — pages generating infinite URL depth (endless calendar pages, /a/b/a/b/…). A URL-length or depth cap catches the general case; the pathological cases are usually handled by a manual exclusion list.
• Data noise — ads, scripts, spam markup with no informational value; filter them out rather than index them.

Which politeness mechanism, when

Mechanism	Guarantee	Why choose it	When it is wrong
Single FIFO queue	None	Trivial to build; fine for a one-site scrape	Any multi-host crawl — floods one host and ignores value
Global rate limiter	Total requests/sec	One knob protects you from overload	Does not protect any individual host — all your budget can still land on one server
Per-host token bucket	Per-host rate	No queue-per-host bookkeeping; flexible bursts	Concurrent workers can still overlap on one host unless you also lock; correctness depends on a check
Host→queue→worker binding	One in-flight request per host, structurally	Politeness cannot be violated by a forgotten check	Worker count is bounded by host count — crawling few hosts leaves workers idle

That last row is the honest cost of the frontier design: throughput is capped by host diversity. If you crawl 10 hosts you cannot usefully run 1,000 workers, no matter how much hardware you own. A crawler for a narrow domain may legitimately prefer per-host token buckets and accept the weaker guarantee.

Pitfalls

• Priority without randomization. Strict priority order starves low-priority queues indefinitely — the long tail is never crawled and never recrawled.
• Mapping hosts to queues by URL rather than hostname. example.com/a and example.com/b must land in the same queue; hashing the full URL silently destroys the entire politeness guarantee while looking correct.
• Politeness by IP versus by hostname. Many hostnames share one IP on shared hosting, so per-hostname politeness can still overwhelm a single physical server. Per-IP is stricter and slower.
• Frontier entirely in memory. Works in a demo, loses the whole crawl on restart, and cannot reach realistic scale.
• Long timeouts. One unresponsive host stalls its queue's worker, and since that worker serves only that host, that host's crawl stops entirely.
• Ignoring robots.txt caching. Correct but self-defeating — you double your request count against every host you are trying to be polite to.

Cost model — what dominates the bill

A crawler's cost is unusual in that the expensive resource is not compute or storage but politeness-bound wall-clock time, and the bill follows from how long the fleet must stay up.

Rough BOTE at the classic scale: 1 billion pages per month is about 1,000,000,000 / (30 × 24 × 3600) ≈ 400 pages/second average, so provision for a peak around 800/s. At ~500 KB per page that is ~500 TB/month of fetched content, and ingress is typically free while storage accumulates — at roughly $0.02/GB-month for warm object storage, 500 TB is about $10,000/month, growing every month you keep crawling. Five years of retention is ~30 PB, which is the line item that actually decides the architecture.

Now the politeness interaction: if courtesy allows one fetch per host per second, then sustaining 400 pages/second requires at least 400 distinct hosts in flight, and therefore at least that many back queues and workers. The fleet is sized by host concurrency, not by CPU — each worker is mostly idle, waiting on network and on its own politeness delay. This is why crawler workers are cheap, numerous, and I/O bound.

Dominant line item: long-term storage of crawled content (and its indexes), which compounds monthly. Second: the many small, mostly-idle worker instances kept alive to hold host concurrency.

Levers: deduplicate before storing — with roughly 30% of the web duplicated, content-hash dedup is a direct ~30% cut to the dominant line; tier aged crawls to cold storage; and let update-history-driven recrawl scheduling stop re-fetching (and re-storing) pages that never change, which cuts both bandwidth and storage growth at once.

Operability: the fingerprints of an impolite or stalled crawler

The failures here are distinctive because most of them show up as someone else's complaint. HTTP 429s and 403s clustered on a single host mean the host→queue mapping has broken for that host — usually the router keyed on something other than the bare hostname, so two queues now serve one site. Throughput far below target while every worker looks busy is the politeness ceiling being hit: you have fewer distinct hosts in flight than your target pages/second requires, and adding machines will change nothing. One back queue growing without bound means its worker is blocked — a hung connection with too generous a timeout, and that entire host's crawl has silently stopped while overall metrics look healthy.

Oldest-URL age climbing in the low-priority front queues is the starvation fingerprint, and it is invisible in queue-depth dashboards — depth can be stable while the bottom never moves, so track age, not just size. Fetch volume rising while unique-content volume stays flat means you are re-downloading duplicates or walking a spider trap; the giveaway for a trap specifically is growing URL length or path depth from one host. And a sudden drop in pages/second across all hosts with normal network health usually points at DNS — a cold or failing resolver cache turns every fetch into a resolution.

Signals worth having: per-host in-flight count (should never exceed one), 4xx/5xx rate grouped by host, per-back-queue depth and worker-blocked duration, oldest-URL age per priority band, unique-content ratio, DNS cache hit rate, and URL-depth distribution per host.

---

Re-authored for this guide from the Alex Xu Vol. 1 web-crawler chapter (URL frontier after the Mercator line of work); frontier diagram hand-authored as SVG. Deep dive complementing the existing "Designing a Web Crawler", "Designing a Web Crawler — Frontier, Dedup & Politeness, Traced" and "Web Crawler Freshness" pages — this one covers the two-layer queue mechanism itself.

I just read a lesson on **Web Crawler Politeness & Priority — Front Queues, Back Queues, Router, Traced** (System Design) and want to truly understand it. Explain Web Crawler Politeness & Priority — Front Queues, Back Queues, Router, Traced from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Web Crawler Politeness & Priority — Front Queues, Back Queues, Router, Traced** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Web Crawler Politeness & Priority — Front Queues, Back Queues, Router, Traced** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Web Crawler Politeness & Priority — Front Queues, Back Queues, Router, Traced** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.