The Mercator URL Frontier separates crawl priority (Front Queues) from per-host politeness (Back Queues) so high-priority domains are crawled fast without DDoSing any single origin server.
TL;DR30-second simplified summary▾
A naive FIFO queue of discovered URLs fails catastrophically at web scale: links from wikipedia.org cluster together and flood one host with thousands of concurrent requests (violating politeness and getting IP-banned), while high-value news pages wait behind millions of low-value forum links.
The Mercator URL Frontier splits scheduling into two stages: K Front Queues ordered by PageRank/freshness priority, and M Back Queues where a consistent-hash router maps every URL's hostname to exactly one Back Queue.
A min-heap of (next_allowed_fetch_ts, back_queue_id) ensures a worker never hits the same host twice within its politeness cooldown, while a distributed Bloom Filter / RocksDB seen-set deduplicates billions of URLs.
From patterns to decisions.
The Mercator URL Frontier separates crawl priority (Front Queues) from per-host politeness (Back Queues) so high-priority domains are crawled fast without DDoSing any single origin server.
Core Intuition & Failure Mode.
The Mercator URL Frontier separates crawl priority (Front Queues) from per-host politeness (Back Queues) so high-priority domains are crawled fast without DDoSing any single origin server.
Core Intuition & Failure Mode
1.Stage Objective: Understand the baseline failure mode.
2.Level (Foundation): The Mercator URL Frontier separates crawl priority (Front Queues) from per-host politeness (Back Queues) so high-priority domains are crawle
3.Operational Invariant: Understand the baseline failure mode.
Caption: Understand the baseline failure mode.
Architectural Mechanics.
The Mercator URL Frontier splits scheduling into two stages: K Front Queues ordered by PageRank/freshness priority, and M Back Queues where a consistent-hash router maps every URL's hostname to exactly one Back Queue.
Architectural Mechanics
1.Stage Objective: Trace the core mechanism end-to-end.
2.Level (Foundation): The **Mercator URL Frontier** splits scheduling into two stages: `K` **Front Queues** ordered by PageRank/freshness priority, and `M` **Back
3.Operational Invariant: Trace the core mechanism end-to-end.
Caption: Trace the core mechanism end-to-end.
Mercator Politeness Heap Scheduler.
import heapq
from collections import deque
class PolitenessFrontier:
def __init__(self) -> None:
self.back_queues: dict[str, deque[str]] = {}
self.ready_heap: list[tuple[float, str]] = []
def push(self, host: str, url: str, now: float) -> None:
if host not in self.back_queues:
self.back_queues[host] = deque()
heapq.heappush(self.ready_heap, (now, host))
self.back_queues[host].append(url)
def pop_ready(self, now: float) -> tuple[str, str] | None:
if not self.ready_heap or self.ready_heap[0][0] > now:
return None
_, host = heapq.heappop(self.ready_heap)
q = self.back_queues[host]
url = q.popleft()
if not q:
del self.back_queues[host]
return host, urlMercator Politeness Heap Scheduler
1.Stage Objective: Enforce 1-active-fetch-per-host and adaptive RTT politeness cooldowns.
2.Level (Intermediate): import heapq
3.Operational Invariant: Enforce 1-active-fetch-per-host and adaptive RTT politeness cooldowns.
Caption: Enforce 1-active-fetch-per-host and adaptive RTT politeness cooldowns.
Throughput & Latency Trade-Offs.
Evaluate asymptotic bounds, cache locality, and tail-latency impact under peak load.
Throughput & Latency Trade-Offs
1.Stage Objective: Quantify operational complexity and memory bounds.
2.Level (Intermediate): Evaluate asymptotic bounds, cache locality, and tail-latency impact under peak load.
3.Operational Invariant: Quantify operational complexity and memory bounds.
Caption: Quantify operational complexity and memory bounds.
Blast-Radius & Failure Isolation.
Isolate shared resources, apply bounded queues, and prevent retry amplification.
Blast-Radius & Failure Isolation
1.Stage Objective: Contain failures without cascading across tenants or nodes.
2.Level (Advanced): Isolate shared resources, apply bounded queues, and prevent retry amplification.
3.Operational Invariant: Contain failures without cascading across tenants or nodes.
Caption: Contain failures without cascading across tenants or nodes.
Durability, Consistency & Recovery.
Use idempotent state transitions, atomic commits, and deterministic replay.
Durability, Consistency & Recovery
1.Stage Objective: Preserve invariants across crashes and restarts.
2.Level (Advanced): Use idempotent state transitions, atomic commits, and deterministic replay.
3.Operational Invariant: Preserve invariants across crashes and restarts.
Caption: Preserve invariants across crashes and restarts.
Telemetry, Circuit Breakers & Failure Modes.
Track p99 latency, retry/conflict ratios, and saturation metrics; fail fast with bounded retries and circuit breakers whenever invariants degrade.
Production Guardrails
1.Stage Objective: Monitor tail latency, error budgets, and invariant violations in production.
2.Level (Advanced): Track p99 latency, retry/conflict ratios, and saturation metrics; fail fast with bounded retries and circuit breakers whenever invariants de
3.Operational Invariant: Bounded retries, telemetry alerts, and circuit breakers prevent cascading failures.
Caption: Bounded retries, telemetry alerts, and circuit breakers prevent cascading failures.
Practice: Make the trade-off yourself.
Why does Mercator split the URL Frontier into Front Queues and Back Queues?