Skip to main content
← CONCEPTS / DISTRIBUTED SYSTEMS
An end-to-end domain learning journey

Distributed Web Crawler &
Mercator URL Frontier.

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.
Start the journey7 sections
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

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.

Full walkthrough · 7 stages
01
STAGE 01 · CORE INTUITIONfoundation

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.

STAGE 01 · CORE INTUITION

Core Intuition & Failure Mode

Core IntuitionIngress / BaselineFailure ModeScale ConstraintValidation GateBottleneck SignalProduction OutcomeTarget SLAexposes

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.

02
STAGE 02 · CORE MECHANICSfoundation

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.

STAGE 02 · CORE MECHANICS

Architectural Mechanics

ArchitecturalMechanicsInput StateCore EngineCore MechanismGuard & VerifyInvariant CheckProduction OutcomeOutput Statetransforms

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.

03
STAGE 03 · SAFE IMPLEMENTATIONintermediate

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, url
STAGE 03 · SAFE IMPLEMENTATION

Mercator Politeness Heap Scheduler

Mercator PolitenessHeapValidated InputCore EngineAtomic StepGuard & VerifyError / Retry GuardProduction OutcomeCommitted Resultexecutes

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.

04
STAGE 04 · SCALING & TRADE-OFFSintermediate

Throughput & Latency Trade-Offs.

Evaluate asymptotic bounds, cache locality, and tail-latency impact under peak load.

STAGE 04 · SCALING & TRADE-OFFS

Throughput & Latency Trade-Offs

ThroughputHot PathLatency Trade-OffsPartition / IndexValidation GateLatency / RAM BoundProduction OutcomeScaled Statebounds

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.

05
STAGE 05 · FAULT ISOLATIONadvanced

Blast-Radius & Failure Isolation.

Isolate shared resources, apply bounded queues, and prevent retry amplification.

STAGE 05 · FAULT ISOLATION

Blast-Radius & Failure Isolation

Blast-RadiusFault TriggerFailure IsolationIsolation BoundaryValidation GateFallback / QuarantineProduction OutcomeProtected Pathisolates

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.

06
STAGE 06 · RECOVERY & CONSISTENCYadvanced

Durability, Consistency & Recovery.

Use idempotent state transitions, atomic commits, and deterministic replay.

STAGE 06 · RECOVERY & CONSISTENCY

Durability, Consistency & Recovery

DurabilityConsistencyCheckpoint / LogRecoveryReplay / SyncValidation GateConsistency GateProduction OutcomeRecovered Stateverifies

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.

07
STAGE 07 · OBSERVABILITY & GUARDRAILSadvanced

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.

STAGE 07 · OBSERVABILITY & GUARDRAILS

Production Guardrails

ProductionGuardrailsTelemetry SignalCore EngineSLO ThresholdGuard & VerifyCircuit BreakerProduction OutcomeSafe Degradationtrips

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 · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why does Mercator split the URL Frontier into Front Queues and Back Queues?

Recommended Learning Flow