Design a Web Crawler (Googlebot)

Target: 1B pages/month

Average crawl rate:
  1,000,000,000 / (30 days × 86,400 sec) ≈ 385 pages/sec

Re-crawl budget (2-week full refresh):
  1B pages / (14 days × 86,400 sec) ≈ 827 pages/sec for re-crawl alone

Combined (new + re-crawl):
  ~1,200 pages/sec sustained
  Peak (burst during off-hours): ~2,000 pages/sec

Per-fetcher throughput:
  Average page fetch: ~2 sec (DNS + TCP + TLS + download + parse)
  Pages/sec per worker: 0.5
  Workers needed: 1,200 / 0.5 = 2,400 concurrent fetcher threads

Implication:
  → ~50 machines with 50 threads each, or fewer with async I/O
  → Async fetchers (epoll/io_uring) can handle 200+ concurrent connections per core

Per-page estimate:
  Raw HTML (compressed)  : ~100 KB average (gzip reduces ~500KB → ~100KB)
  URL metadata           : ~500 bytes (URL, fetch time, status, headers)
  Extracted text         : ~20 KB (stripped HTML)
  ─────────────────────────────
  Total per page         ≈ 120 KB compressed

Monthly storage:
  1B pages × 120 KB = 120 TB/month (raw content)
  URL metadata only: 1B × 500 B = 500 GB/month

Annual storage:
  ~1.4 PB/year for full content
  ~6 TB/year for URL metadata alone

Implication:
  → Object storage (S3/GCS) for page content — cheap, durable, append-only
  → Hot metadata in a database (URL status, last-crawl time, priority)
  → Cold content archived after 90 days to cheaper storage tier

Inbound (fetching pages):
  1,200 pages/sec × 500 KB (uncompressed avg) = 600 MB/s = 4.8 Gbps
  With gzip (most servers support it): ~120 MB/s = ~1 Gbps

Outbound (to object storage):
  1,200 pages/sec × 100 KB (compressed) = 120 MB/s = ~1 Gbps

DNS queries:
  1,200 unique domains/sec worst case (if every page is a new domain)
  Realistic with caching: ~100 DNS queries/sec (90%+ cache hit rate)

Implication:
  → Need 2-4 Gbps network capacity across the fetcher fleet
  → DNS caching is critical — without it, DNS becomes the bottleneck
  → Connection pooling per domain reduces TCP/TLS handshake overhead

Known URLs (after months of crawling):
  ~10 billion URLs discovered (most of the web)
  Active frontier (pending crawl): ~2 billion URLs

Per-URL entry in frontier:
  URL hash (for dedup)   : 8 bytes (64-bit fingerprint)
  Priority score         : 4 bytes
  Domain ID              : 4 bytes
  Last-seen timestamp    : 8 bytes
  ─────────────────────────────
  ≈ 24 bytes per entry (metadata only; full URL stored separately)

Frontier memory:
  2B entries × 24 bytes = 48 GB (metadata fits in RAM on a single large box)
  Full URLs (avg 100 chars): 2B × 100 B = 200 GB (needs disk or distributed)

Implication:
  → Frontier metadata can live in-memory on a beefy machine (64-128 GB RAM)
  → Full URL strings stored on disk (RocksDB / LevelDB) with in-memory index
  → Bloom filter for "already seen" check: 10B URLs × 1.2 bytes = ~12 GB

type CrawlTask = {
  taskId: string;              // Idempotency key for dedup on retry
  url: string;                 // Fully normalized URL to fetch
  domainId: string;            // Hash of the domain — used for rate-limit bucketing
  priority: number;            // 0 (highest) to 100 (lowest)
  allowedDelaySec: number;     // Min seconds between requests to this domain
  robotsRules: {
    disallowPaths: string[];   // Paths we must NOT fetch
    crawlDelay: number | null; // Explicit delay from robots.txt
  };
  retryCount: number;          // How many times this URL has been attempted
  maxRetries: number;          // Give up after this many failures
  fetchDeadlineMs: number;     // Timeout for the entire fetch operation
};

type FetchResult = {
  taskId: string;
  url: string;
  domainId: string;
  status: "success" | "failed" | "robots_blocked" | "timeout" | "dns_error";
  httpStatus: number | null;       // null if connection failed
  headers: Record<string, string>; // Content-Type, Last-Modified, ETag
  body: Buffer | null;             // Raw HTML bytes (null on failure)
  contentHash: string;             // SHA-256 of body — for content dedup
  fetchedAt: string;               // ISO timestamp
  latencyMs: number;               // Total fetch time (DNS + TCP + TLS + download)
  redirectChain: string[];         // All intermediate URLs if redirected
};

type ParseResult = {
  sourceUrl: string;
  discoveredUrls: NormalizedUrl[];  // Extracted + canonicalized outgoing links
  pageMetadata: {
    title: string;
    description: string;
    language: string;
    contentType: string;           // text/html, application/pdf, etc.
    lastModified: string | null;   // From HTTP header or <meta> tag
    canonicalUrl: string | null;   // <link rel="canonical"> if present
  };
  contentFingerprint: string;      // SimHash for near-duplicate detection
  outboundLinkCount: number;       // Used for PageRank-style priority scoring
};

type NormalizedUrl = {
  url: string;                     // Fully resolved, canonicalized URL
  anchorText: string;              // Text of the <a> tag — useful for relevance
  domainId: string;                // Pre-computed domain hash
  isInternal: boolean;             // Same domain as source?
};

Total time per page (end-to-end): ~2-3 seconds

0.0ms   ─  Frontier dequeue (in-memory priority queue)
0.1ms   ─  Rate-limit check (per-domain token bucket)
5ms     ─  DNS resolution (cached — 0.1ms hit, 50ms miss)
50ms    ─  TCP + TLS handshake (pooled connections skip this)
500ms   ─  HTTP response download (avg 500KB page)
100ms   ─  HTML parsing + link extraction
50ms    ─  URL normalization + Bloom filter check (per discovered URL)
20ms    ─  Content hash computation (SHA-256)
10ms    ─  SimHash computation (near-duplicate fingerprint)
100ms   ─  Object storage write (async, non-blocking)
10ms    ─  Metadata DB update
          ─────────────────────────────────────
          ~850ms on cache-hit DNS + pooled connection
          ~2,500ms on cold start (new domain, no connection pool)

Implication:
  → With 2,400 concurrent workers, we achieve 1,200 pages/sec
  → Connection pooling per domain cuts 50-100ms per fetch
  → DNS caching cuts 45ms per fetch on average

Queue: [url1.com/a, url1.com/b, url1.com/c, url2.com/x, url1.com/d, ...]

Problem 1 — Politeness violation:
  If a page has 100 outgoing links to the same domain, all 100 get
  enqueued consecutively. The crawler hammers that domain with 100
  requests in seconds → gets IP-banned.

Problem 2 — No priority:
  A newly discovered link to nytimes.com/breaking-news sits behind
  10,000 links to some random blog's archive pages. Important pages
  wait hours while garbage gets crawled first.

Problem 3 — Starvation:
  Popular domains with millions of pages dominate the queue.
  Small but important domains never get crawled.

FRONT QUEUES (priority-based):
  ┌─────────────────────────────────────────┐
  │ Queue 0 (highest): breaking news, homepages, sitemaps     │
  │ Queue 1 (high):    recently changed pages, high PageRank  │
  │ Queue 2 (medium):  normal discovery, internal links       │
  │ Queue 3 (low):     deep archive pages, low-authority      │
  └─────────────────────────────────────────┘
  
  Biased selection: Queue 0 gets 40% of dequeues, Queue 1 gets 30%, etc.

BACK QUEUES (domain-based):
  ┌─────────────────────────────────────────┐
  │ Bucket[hash("nytimes.com")]:  [url1, url2, url3]          │
  │ Bucket[hash("github.com")]:   [url4, url5]                │
  │ Bucket[hash("blog.xyz")]:     [url6]                      │
  └─────────────────────────────────────────┘
  
  Each bucket has a "next_allowed_fetch_time" timestamp.
  Dequeue: pick the bucket with the earliest allowed time → pop one URL.

FLOW:
  New URL → Priority Scorer → Front Queue (by priority)
  Front Queue → Router (by domain hash) → Back Queue
  Back Queue → Rate Limiter → Fetcher

// Each frontier partition owns domains where hash(domain) % N == partitionId
class FrontierPartition {
  // In-memory: domain scheduling state (~40 bytes per domain)
  domainSchedule: Map<string, {
    nextAllowedFetchTime: number;  // Unix ms
    pendingCount: number;
    crawlDelay: number;            // From robots.txt
    priority: number;              // Aggregate domain priority
  }>;

  // On-disk (RocksDB): full URL queue per domain
  // Key: `${domainId}:${priority}:${urlHash}`
  // Value: serialized CrawlTask
  urlStore: RocksDB;

  // In-memory: min-heap of domains sorted by nextAllowedFetchTime
  // Only domains with pendingCount > 0 are in the heap
  readyHeap: MinHeap<{ domainId: string; readyAt: number }>;

  dequeue(): CrawlTask | null {
    // Pop domain with earliest readyAt that's <= now
    const domain = this.readyHeap.peekMin();
    if (!domain || domain.readyAt > Date.now()) return null;

    // Fetch highest-priority URL for this domain from RocksDB
    const task = this.urlStore.getHighestPriority(domain.domainId);

    // Update domain's next allowed time
    domain.readyAt = Date.now() + domain.crawlDelay;
    this.readyHeap.decreaseKey(domain);

    return task;
  }
}

priority = w1 × pageRankScore        // Domain/page authority (0-1)
         + w2 × freshnessDecay         // How stale is our copy? (0-1)
         + w3 × changeFrequency        // How often does this page change? (0-1)
         + w4 × depthPenalty           // Deeper pages get lower priority (0-1)
         + w5 × discoveryRecency       // Recently discovered = boost (0-1)

Typical weights:
  w1 = 0.3  (authority matters most)
  w2 = 0.25 (freshness is critical for news/dynamic sites)
  w3 = 0.2  (frequently changing pages need more attention)
  w4 = 0.15 (shallow pages are usually more important)
  w5 = 0.1  (slight boost for newly discovered URLs)

Examples:
  nytimes.com/          → 0.3×0.9 + 0.25×0.8 + 0.2×0.95 + 0.15×1.0 + 0.1×0.5 = 0.81
  random-blog.com/p/123 → 0.3×0.1 + 0.25×0.2 + 0.2×0.05 + 0.15×0.3 + 0.1×0.3 = 0.16

// Thread 1:
fetch("https://example.com/page1")  // blocks 2 sec
fetch("https://example.com/page2")  // blocks 2 sec
fetch("https://example.com/page3")  // blocks 2 sec

Throughput: 0.5 pages/sec per thread
For 1,200 pages/sec: need 2,400 OS threads
Memory: 2,400 threads × 1MB stack = 2.4 GB just for stacks
Context switching: catastrophic at 2,400 threads

Problems:
  → OS thread limit (~10K per process)
  → Context switch overhead dominates CPU time
  → No connection reuse between requests to same domain
  → No timeout handling — one slow server blocks the thread forever

class AsyncFetcher {
  // Connection pool: reuse TCP+TLS connections per domain
  private connectionPool: Map<string, ConnectionPool>;
  
  // Event loop handles 500+ concurrent requests per process
  private inFlight: Map<string, PendingRequest>;
  private maxConcurrent = 500;

  async fetch(task: CrawlTask): Promise<FetchResult> {
    // Get or create pooled connection for this domain
    const conn = await this.connectionPool
      .getOrCreate(task.domainId, { maxIdle: 5, idleTimeout: 30_000 });

    // Non-blocking fetch with timeout
    const response = await Promise.race([
      conn.get(task.url, {
        headers: { "User-Agent": "EventLoopedBot/1.0" },
        followRedirects: 5,
        maxResponseSize: 10_000_000, // 10MB cap
      }),
      timeout(task.fetchDeadlineMs),
    ]);

    return buildFetchResult(task, response);
  }
}

// 50 machines × 10 processes × 500 concurrent = 250,000 in-flight
// At 2 sec avg latency: 250,000 / 2 = 125,000 pages/sec capacity
// We only need 1,200/sec — massive headroom for bursts

class DomainAwareFetcher {
  // This fetcher owns domains where hash(domain) % fleetSize == myId
  private myDomains: Set<string>;
  
  // Per-domain state (local — no distributed coordination needed)
  private domainState: Map<string, {
    connectionPool: ConnectionPool;
    tokenBucket: TokenBucket;        // Rate limiter
    avgLatencyMs: ExponentialMovingAvg;
    consecutiveErrors: number;
    backoffUntil: number;            // Exponential backoff on errors
  }>;

  async fetch(task: CrawlTask): Promise<FetchResult> {
    const state = this.domainState.get(task.domainId);

    // Adaptive throttling: if domain is slow, reduce concurrency
    if (state.avgLatencyMs.value > 5000) {
      state.tokenBucket.setRate(0.2); // Slow down to 1 req/5sec
    }

    // Exponential backoff on consecutive errors
    if (state.consecutiveErrors >= 3) {
      state.backoffUntil = Date.now() + Math.min(
        1000 * Math.pow(2, state.consecutiveErrors),
        3600_000 // Max 1 hour backoff
      );
      return { ...task, status: "backoff" };
    }

    // Token bucket: respect robots.txt Crawl-delay
    await state.tokenBucket.acquire();

    const startTime = Date.now();
    const result = await this.doFetch(task, state.connectionPool);
    
    // Update adaptive state
    state.avgLatencyMs.update(Date.now() - startTime);
    if (result.status === "success") {
      state.consecutiveErrors = 0;
    } else {
      state.consecutiveErrors++;
    }

    return result;
  }
}

# Example robots.txt for nytimes.com
User-agent: *
Disallow: /search
Disallow: /admin
Crawl-delay: 2

User-agent: EventLoopedBot
Allow: /
Crawl-delay: 1

Sitemap: https://www.nytimes.com/sitemap.xml

─────────────────────────────────────

Crawler behavior:
1. Before first fetch to any domain → GET /robots.txt
2. Parse rules for our User-Agent (fall back to *)
3. Cache with 24h TTL (refresh daily)
4. On every URL dispatch: check path against Disallow rules
5. Honor Crawl-delay as minimum interval between requests
6. Fetch sitemap URLs → add to frontier with high priority

Edge cases:
  - robots.txt returns 404 → assume everything is allowed
  - robots.txt returns 5xx → retry 3 times, then assume disallow-all (safe default)
  - robots.txt > 500KB → reject (likely not a real robots.txt)
  - Crawl-delay > 60s → respect it, but deprioritize the domain

Parameters:
  n = 10 billion URLs (expected total over crawler lifetime)
  p = 0.01 (1% false positive rate — acceptable for crawling)

Optimal bit array size:
  m = -(n × ln(p)) / (ln(2))² 
  m = -(10B × ln(0.01)) / (ln(2))²
  m ≈ 95.8 billion bits ≈ 12 GB

Optimal hash functions:
  k = (m/n) × ln(2) = 9.6 × 0.693 ≈ 7 hash functions

Lookup time: O(k) = O(7) — constant time, ~100 nanoseconds
Insert time: O(k) = O(7) — constant time

Trade-off:
  → 1% of new URLs are falsely rejected (re-discovered next cycle)
  → 0% of seen URLs are falsely accepted (no duplicates slip through)
  → 12 GB RAM vs 80 GB for a full hash set — 6.7× savings

class UrlDeduplicator {
  // Layer 1: In-memory Bloom filter (12 GB, 1% FP rate)
  private bloomFilter: BloomFilter; // 10B capacity

  // Layer 2: Persistent hash store (RocksDB on SSD)
  // Key: 64-bit URL fingerprint, Value: empty (existence check only)
  private hashStore: RocksDB;

  async isNew(url: string): Promise<boolean> {
    const fingerprint = xxhash64(normalizeUrl(url));

    // Fast path: Bloom filter says "definitely not seen" → it's new
    if (!this.bloomFilter.mightContain(fingerprint)) {
      return true; // Guaranteed new
    }

    // Slow path: Bloom filter says "maybe seen" → verify against disk
    // This happens for ~1% of genuinely new URLs (false positives)
    // and 100% of actually-seen URLs (true positives)
    const exists = await this.hashStore.exists(fingerprint);
    return !exists;
  }

  async markSeen(url: string): Promise<void> {
    const fingerprint = xxhash64(normalizeUrl(url));
    this.bloomFilter.add(fingerprint);
    await this.hashStore.put(fingerprint, EMPTY_VALUE);
  }
}

Input URLs that all point to the SAME page:
  https://Example.COM/path/page.html
  https://example.com/path/page.html?utm_source=twitter&utm_medium=social
  https://example.com/path/page.html#section-3
  https://example.com/path/../path/page.html
  https://www.example.com/path/page.html
  http://example.com/path/page.html

Normalization steps (in order):
  1. Lowercase scheme and host       → https://example.com/...
  2. Remove default port (80/443)    → strip :443 from HTTPS URLs
  3. Remove fragment (#...)          → #section-3 is client-side only
  4. Remove tracking parameters      → strip utm_*, fbclid, gclid, etc.
  5. Sort remaining query params     → ?b=2&a=1 → ?a=1&b=2
  6. Resolve path (../ and ./)       → /path/../path/ → /path/
  7. Remove trailing slash           → /path/ → /path (configurable)
  8. Handle www subdomain            → www.example.com → example.com (configurable)
  9. Decode unnecessary percent-encoding → %41 → A

Output: https://example.com/path/page.html

function computeSimHash(htmlContent: string): bigint {
  // 1. Extract text content (strip HTML tags, scripts, styles)
  const text = extractVisibleText(htmlContent);
  
  // 2. Tokenize into shingles (overlapping n-grams)
  const shingles = generateShingles(text, 3); // 3-word shingles
  
  // 3. Hash each shingle and accumulate weighted bit vector
  const vector = new Array(64).fill(0);
  for (const shingle of shingles) {
    const hash = xxhash64(shingle);
    for (let bit = 0; bit < 64; bit++) {
      vector[bit] += (hash >> BigInt(bit)) & 1n ? 1 : -1;
    }
  }
  
  // 4. Convert to binary fingerprint
  let fingerprint = 0n;
  for (let bit = 0; bit < 64; bit++) {
    if (vector[bit] > 0) fingerprint |= (1n << BigInt(bit));
  }
  return fingerprint;
}

function isNearDuplicate(hash1: bigint, hash2: bigint): boolean {
  // Hamming distance: count differing bits
  const xor = hash1 ^ hash2;
  let distance = 0;
  let bits = xor;
  while (bits > 0n) {
    distance++;
    bits &= bits - 1n; // Clear lowest set bit
  }
  return distance <= 3; // ≤3 bits different = near-duplicate
}

Strategy: Re-crawl every URL every 7 days

Budget consumed by re-crawl:
  1B URLs / (7 × 86,400 sec) = 1,653 pages/sec
  Total budget: 1,200 pages/sec
  → Re-crawl alone EXCEEDS our total capacity!

Even at 14 days:
  1B URLs / (14 × 86,400 sec) = 827 pages/sec
  → 69% of budget on re-crawl, only 31% for new discovery

The real problem:
  - 80% of pages haven't changed since last crawl (wasted fetches)
  - 5% of pages change hourly but only get checked weekly (stale)
  - No differentiation between nytimes.com/breaking and archive.org/1998

function computeRecrawlInterval(url: UrlMetadata): number {
  const { lastCrawled, lastChanged, crawlCount, changeCount } = url;

  // Change rate: what fraction of crawls found changes?
  const changeRate = changeCount / Math.max(crawlCount, 1);

  // Base interval from change rate
  let intervalHours: number;
  if (changeRate > 0.8) intervalHours = 6;       // Changes almost every time → 6h
  else if (changeRate > 0.5) intervalHours = 24;  // Changes often → daily
  else if (changeRate > 0.2) intervalHours = 72;  // Changes sometimes → 3 days
  else if (changeRate > 0.05) intervalHours = 168; // Rarely changes → weekly
  else intervalHours = 720;                        // Almost never → monthly

  // Decay: if we haven't seen a change in a while, slow down
  const hoursSinceChange = (Date.now() - lastChanged) / 3_600_000;
  if (hoursSinceChange > intervalHours * 3) {
    intervalHours = Math.min(intervalHours * 2, 720); // Double, cap at 30 days
  }

  return intervalHours;
}

// Result: news homepages crawled every 6h, blog archives every 30 days
// Budget savings: ~60% fewer re-crawls vs fixed interval

// The scheduler allocates the total crawl budget across priority tiers
const TOTAL_BUDGET_PER_SEC = 1200;

const TIER_ALLOCATION = {
  CRITICAL: 0.30,  // 360/sec — homepages, news, sitemaps
  HIGH:     0.25,  // 300/sec — frequently changing, high PageRank
  MEDIUM:   0.20,  // 240/sec — moderate change rate
  LOW:      0.15,  // 180/sec — rarely changing pages
  DISCOVERY: 0.10, // 120/sec — brand new URLs never crawled before
};

function computePriority(url: UrlMetadata): { tier: Tier; score: number } {
  // Multi-signal scoring
  const importanceScore = 
    0.35 * url.pageRank +                    // Authority
    0.25 * url.changeFrequency +             // How often it changes
    0.20 * freshnessDecay(url.lastCrawled) + // How stale our copy is
    0.10 * url.inboundLinkCount / MAX_LINKS + // Popularity
    0.10 * (url.isHomepage ? 1 : 0);         // Homepages always matter

  // Assign to tier based on score
  const tier = importanceScore > 0.7 ? "CRITICAL"
    : importanceScore > 0.5 ? "HIGH"
    : importanceScore > 0.3 ? "MEDIUM"
    : "LOW";

  return { tier, score: importanceScore };
}

// Freshness decay: exponential — urgency grows over time
function freshnessDecay(lastCrawledMs: number): number {
  const hoursSinceCrawl = (Date.now() - lastCrawledMs) / 3_600_000;
  const expectedInterval = getExpectedInterval(url); // From change history
  return 1 - Math.exp(-hoursSinceCrawl / expectedInterval);
  // Returns 0 when just crawled, approaches 1 as staleness grows
}

First crawl:
  GET /article/123 HTTP/1.1
  Host: example.com

  Response:
  200 OK
  ETag: "abc123"
  Last-Modified: Sat, 25 May 2026 10:00:00 GMT
  Content-Length: 45000
  [... 45KB of HTML ...]

Re-crawl (conditional):
  GET /article/123 HTTP/1.1
  Host: example.com
  If-None-Match: "abc123"
  If-Modified-Since: Sat, 25 May 2026 10:00:00 GMT

  Response (unchanged):
  304 Not Modified
  [no body — saves 45KB of bandwidth]

  Response (changed):
  200 OK
  ETag: "def456"
  [... new content ...]

Savings at scale:
  If 80% of re-crawls return 304:
  → 80% × 500KB avg page = 400KB saved per re-crawl
  → At 800 re-crawls/sec: 320 MB/sec bandwidth saved
  → ~2.5 Gbps saved — more than our total inbound capacity!

TRANSIENT (retry with backoff):
  - DNS timeout           → retry after 30s (DNS might be overloaded)
  - TCP connection reset  → retry after 60s (server might be restarting)
  - HTTP 500/502/503      → retry after 5min (server error, likely temporary)
  - HTTP 429 Too Many Requests → respect Retry-After header, or backoff 10min
  - Network timeout       → retry after 2min (congestion or slow server)

PERMANENT (do not retry):
  - HTTP 404 Not Found    → mark URL as dead, remove from frontier
  - HTTP 410 Gone         → mark URL as permanently removed
  - DNS NXDOMAIN          → domain doesn't exist, blocklist
  - robots.txt disallow   → respect indefinitely (check again in 24h)
  - Content too large     → skip (>10MB is likely not a web page)
  - Invalid SSL cert      → skip (security risk)

AMBIGUOUS (limited retries):
  - HTTP 403 Forbidden    → might be rate-limited, retry 2× then give up
  - Connection refused    → server might be down, retry 3× over 24h
  - Redirect loop         → mark as broken after 5 redirects
  - Malformed response    → retry once, then mark as unparseable

function computeRetryDelay(retryCount: number, baseDelay: number): number {
  // Exponential: 1min, 2min, 4min, 8min, 16min, 32min (cap)
  const exponentialDelay = baseDelay * Math.pow(2, retryCount);
  const cappedDelay = Math.min(exponentialDelay, 32 * 60 * 1000); // 32 min max

  // Jitter: ±25% randomization to prevent thundering herd
  const jitter = cappedDelay * 0.25 * (Math.random() * 2 - 1);
  return cappedDelay + jitter;
}

// Retry budget per URL
const MAX_RETRIES = 5;
const BASE_DELAY_MS = 60_000; // 1 minute

// After 5 retries: 1min + 2min + 4min + 8min + 16min = 31 min total wait
// If still failing after 31 minutes → mark as dead, move on

FRONTIER STATE TO PRESERVE:
  - URL queue contents (2B entries, ~200 GB on disk)
  - Per-domain scheduling metadata (50M domains, ~2 GB)
  - Bloom filter state (12 GB)
  - In-flight tasks (currently being fetched)

CHECKPOINT STRATEGY:
  1. RocksDB WAL (Write-Ahead Log):
     - Every enqueue/dequeue is logged before execution
     - On crash: replay WAL from last checkpoint
     - Checkpoint interval: every 5 minutes
     - WAL size between checkpoints: ~500 MB

  2. Bloom filter snapshots:
     - Serialize to disk every hour (12 GB write)
     - On crash: load last snapshot + replay URL discoveries from WAL
     - Acceptable: some URLs re-fetched (Bloom filter slightly stale)

  3. In-flight task recovery:
     - Tasks dispatched to fetchers have a "lease" timeout (5 min)
     - If fetcher doesn't ACK within lease → task returns to queue
     - Duplicate fetches are harmless (idempotent operation)

RECOVERY TIME:
  - RocksDB restart: ~30 seconds (replay WAL)
  - Bloom filter reload: ~60 seconds (mmap from disk)
  - Total recovery: < 2 minutes
  - Pages lost during crash: ~2 min × 1,200/sec = ~144,000 pages
    (re-discovered on next crawl cycle — acceptable)

Cost of headless browser rendering:
  - Memory: ~200 MB per browser tab (Chrome)
  - CPU: 2-5 seconds to render a JS-heavy page
  - Throughput: ~0.3 pages/sec per tab

To hit 1,200 pages/sec with rendering:
  - Need 4,000 concurrent browser tabs
  - Memory: 4,000 × 200 MB = 800 GB RAM
  - Machines: ~25 machines with 32 GB each (just for rendering)
  - Cost: ~$50K/month in compute alone

vs. static HTML fetching:
  - Memory: ~5 MB per concurrent connection
  - CPU: negligible (just network I/O)
  - Throughput: 500+ pages/sec per machine
  - Cost: ~$2K/month for the same throughput

Reality: only ~15-20% of the web requires JS rendering.
Rendering everything wastes 80% of your budget on pages that don't need it.

function needsRendering(html: string, url: string): boolean {
  // Heuristic 1: Very little visible text relative to HTML size
  const visibleText = extractVisibleText(html);
  const textRatio = visibleText.length / html.length;
  if (textRatio < 0.05) return true; // Less than 5% text → likely JS-rendered

  // Heuristic 2: Framework markers
  const frameworkMarkers = [
    'id="root"',           // React
    'id="app"',            // Vue
    'id="__next"',         // Next.js (but SSR pages are fine)
    'ng-app',              // Angular
    'data-reactroot',      // React
  ];
  const hasFramework = frameworkMarkers.some(marker => html.includes(marker));
  
  // Heuristic 3: Very few outgoing links extracted
  const linkCount = (html.match(/<as+[^>]*href/gi) || []).length;
  if (hasFramework && linkCount < 3) return true;

  // Heuristic 4: Known JS-heavy domains (learned from history)
  if (isKnownJSDomain(url)) return true;

  return false;
}

// Domain classification (updated after every crawl batch)
enum RenderingTier {
  STATIC = "static",           // Raw HTML has full content — no rendering needed
  PARTIAL_JS = "partial_js",   // Some pages need rendering, some don't
  FULL_JS = "full_js",         // All pages require rendering
}

class RenderingRouter {
  // Learned classification per domain (persisted)
  private domainTier: Map<string, {
    tier: RenderingTier;
    confidence: number;        // 0-1, based on sample size
    sampleSize: number;
    lastUpdated: number;
  }>;

  // Rendering pool: shared headless browser instances
  private renderPool: BrowserPool; // 200 tabs across 10 machines

  async route(task: CrawlTask, rawHtml: string): Promise<string> {
    const domain = this.domainTier.get(task.domainId);

    if (domain?.tier === "STATIC" && domain.confidence > 0.9) {
      return rawHtml; // Skip rendering — domain is known static
    }

    if (domain?.tier === "FULL_JS" && domain.confidence > 0.9) {
      return await this.renderPool.render(task.url, {
        waitUntil: "networkidle",
        timeout: 10_000,
        blockResources: ["image", "font", "media"], // Save bandwidth
      });
    }

    // Unknown or partial — use per-page heuristic
    if (needsRendering(rawHtml, task.url)) {
      const rendered = await this.renderPool.render(task.url, {
        waitUntil: "networkidle",
        timeout: 10_000,
      });
      this.updateDomainClassification(task.domainId, true);
      return rendered;
    }

    this.updateDomainClassification(task.domainId, false);
    return rawHtml;
  }
}

RENDERING POOL SIZING:
  Target: render 200 pages/sec (15-20% of total crawl rate)
  Avg render time: 5 seconds per page
  Concurrent tabs needed: 200 × 5 = 1,000 tabs

  Per machine (32 GB RAM):
    - 50 tabs × 200 MB = 10 GB for browsers
    - 22 GB for OS + buffers
    - Throughput: 50 / 5 = 10 pages/sec per machine

  Fleet: 1,000 / 50 = 20 machines for rendering

OPTIMIZATIONS:
  1. Block unnecessary resources:
     - Images, fonts, media → don't load (saves 60% bandwidth)
     - Third-party scripts (analytics, ads) → block
     - Only load first-party JS needed for content

  2. Tab recycling:
     - Reuse tabs across renders (avoid cold-start overhead)
     - Kill and recreate tabs every 50 renders (prevent memory leaks)

  3. Timeout and abort:
     - Hard timeout: 10 seconds (if not rendered by then, use raw HTML)
     - Network idle detection: stop waiting once no requests for 500ms

  4. Caching:
     - Cache rendered output for pages that rarely change
     - Share browser cache across tabs for same-domain resources

THROUGHPUT METRICS:
  pages_fetched_per_sec          — Are we hitting our 1,200/sec target?
  pages_parsed_per_sec           — Is the parser keeping up with fetchers?
  urls_discovered_per_sec        — Is the crawl still finding new content?
  urls_enqueued_per_sec          — Is the frontier growing or shrinking?

ERROR METRICS:
  fetch_error_rate               — % of fetches that fail (target: <5%)
  dns_failure_rate               — DNS resolution failures (target: <0.1%)
  timeout_rate                   — Fetches that exceed deadline (target: <3%)
  http_4xx_rate                  — Client errors (404s, 403s)
  http_5xx_rate                  — Server errors (indicates target site issues)
  robots_blocked_rate            — URLs rejected by robots.txt

QUEUE HEALTH:
  frontier_depth                 — Total pending URLs (should be stable, not growing unbounded)
  frontier_oldest_task_age       — How long has the oldest URL been waiting?
  in_flight_tasks                — Currently being fetched (should match worker count)
  retry_queue_depth              — URLs waiting for retry (growing = problem)

RESOURCE METRICS:
  bloom_filter_fill_ratio        — How full is the Bloom filter? (>80% = time to resize)
  content_store_write_rate       — MB/sec to object storage
  dns_cache_hit_rate             — Should be >90% (below = new domain explosion)
  connection_pool_utilization    — Are we reusing connections effectively?

FRESHNESS METRICS:
  avg_page_staleness_hours       — How old is our average cached page?
  recrawl_304_rate               — % of re-crawls that return "not modified"
  pages_changed_on_recrawl       — % of re-crawls that found new content

CONTENT QUALITY:
  duplicate_content_rate         — % of fetched pages that are near-duplicates
                                   (target: <5%; higher = dedup is failing)
  empty_page_rate                — Pages with <100 chars of visible text
                                   (target: <2%; higher = crawling JS shells without rendering)
  language_distribution          — Are we crawling the languages we want?
  domain_diversity               — How many unique domains per hour?
                                   (low = stuck on a few sites)

CRAWL TRAP DETECTION:
  urls_per_domain_histogram      — Flag domains with >100K pending URLs
  url_depth_distribution         — Flag URLs with path depth > 10
  url_pattern_entropy            — Low entropy = generated URLs (calendar traps)
  pages_with_no_outlinks         — Dead ends (might be error pages)

FRESHNESS QUALITY:
  time_to_first_crawl            — How quickly do we crawl newly discovered URLs?
                                   (target: <4 hours for high-priority)
  recrawl_found_change_rate      — When we re-crawl, how often was it worth it?
                                   (target: >20%; lower = wasting budget on static pages)
  important_page_staleness       — Max staleness for top-1000 domains
                                   (target: <24 hours)

Capacity: ~0.1 pages/sec (sync, single-threaded)
Storage: SQLite handles ~1M rows before slowing down
Memory: Queue grows unbounded if discovery > fetch rate

Breaking points:
  → At 100K URLs in queue: memory pressure
  → At 1M stored pages: SQLite writes slow to 10/sec
  → At 10 pages/sec target: need async I/O (single thread can't keep up)
  → At multiple domains: need politeness (currently hammers one domain)

Trigger to evolve: "I need more than 10K pages/day"

Capacity: ~10-50 pages/sec
Storage: Postgres handles 100M rows; local disk holds ~10 TB
Memory: 32 GB handles frontier of ~50M URLs

Breaking points:
  → At 50M frontier URLs: need disk-backed queue (RAM limit)
  → At 100 pages/sec: single machine's network saturated (~50 MB/sec)
  → At 10B seen URLs: Bloom filter needs 12 GB (still fits, but tight)
  → At 100M stored pages: local disk I/O becomes bottleneck

Trigger to evolve: "I need more than 1M pages/day, or I need fault tolerance"

Capacity: ~400 pages/sec (100M/month)
Storage: S3 handles unlimited; Postgres sharded for metadata
Frontier: 5 partitions × 64 GB = handles 2B URLs

Breaking points:
  → At 1,200 pages/sec: need 50+ fetcher machines
  → At 10B URLs: Bloom filter needs distributed or partitioned approach
  → At 50M domains: robots.txt cache needs its own service
  → At multi-region: need geo-local fetching for latency

Trigger to evolve: "I need 1B pages/month with global coverage"