Designing a Web Crawler: URL Frontier, Politeness Policies, and Distributed Scheduling at Scale

Most system design discussions treat a web crawler as a simple BFS loop: fetch a page, extract links, enqueue them, repeat. That framing works until you hit the real constraints. A crawler at scale has to respect hundreds of thousands of distinct hosts simultaneously, avoid hammering any single server, deduplicate billions of URLs without a linear scan, and coordinate dozens or hundreds of workers without central bottlenecks. Each of those problems has non-obvious solutions with real tradeoffs.

This article walks through the architecture of a production-grade crawler from the URL frontier inward, covering the components that most tutorials skip.

The URL Frontier

The frontier is the queue of URLs waiting to be fetched. At small scale a single priority queue works. At scale it breaks down for two reasons: you cannot enforce per-host politeness from a global priority queue, and a single data structure becomes a throughput bottleneck.

The standard architecture splits the frontier into two tiers.

Front queues are per-priority buckets. URLs come in with an assigned priority (based on PageRank estimate, domain authority, freshness signals, or topic relevance) and land in the corresponding front queue. A front queue selector reads from high-priority queues more often than low-priority ones, using a weighted round-robin or a simple probability distribution.

Back queues are per-host queues, each with a minimum next-fetch timestamp. The selector pulls from front queues and routes URLs into host-specific back queues. Workers pull from back queues only when the host’s next-fetch time has elapsed.

interface FrontierURL {
  url: string;
  host: string;
  priority: number;
  discoveredAt: number;
}

interface HostState {
  nextFetchAt: number;      // epoch ms
  crawlDelayMs: number;     // from robots.txt or default
  inFlight: number;         // active requests against this host
}

class URLFrontier {
  private frontQueues: Map<number, FrontierURL[]>;  // priority -> URLs
  private backQueues: Map<string, FrontierURL[]>;   // host -> URLs
  private hostStates: Map<string, HostState>;
  private readonly maxInFlightPerHost = 1;

  enqueue(item: FrontierURL): void {
    const priority = Math.min(Math.max(Math.floor(item.priority), 0), 9);
    if (!this.frontQueues.has(priority)) {
      this.frontQueues.set(priority, []);
    }
    this.frontQueues.get(priority)!.push(item);
  }

  // Called by the selector loop, not by workers directly
  drainFrontToBack(): void {
    for (const [priority, queue] of this.frontQueues) {
      while (queue.length > 0) {
        const item = queue.shift()!;
        if (!this.backQueues.has(item.host)) {
          this.backQueues.set(item.host, []);
        }
        this.backQueues.get(item.host)!.push(item);
      }
    }
  }

  dequeue(now: number): FrontierURL | null {
    for (const [host, queue] of this.backQueues) {
      if (queue.length === 0) continue;
      const state = this.hostStates.get(host);
      if (!state) continue;
      if (state.nextFetchAt > now) continue;
      if (state.inFlight >= this.maxInFlightPerHost) continue;

      state.inFlight++;
      return queue.shift()!;
    }
    return null;
  }

  markFetched(host: string, success: boolean): void {
    const state = this.hostStates.get(host);
    if (!state) return;
    state.inFlight = Math.max(0, state.inFlight - 1);
    // Back off longer on errors
    const delay = success ? state.crawlDelayMs : state.crawlDelayMs * 4;
    state.nextFetchAt = Date.now() + delay;
  }
}

The two-tier split solves the fairness problem. A surge of high-priority URLs from a single domain cannot starve other hosts because the back queue acts as a per-host buffer with its own scheduling clock.

BFS vs Best-First

Breadth-first search is the right default for broad web crawls. It ensures coverage across many domains before going deep into any one site, which prevents a single deep-link structure from consuming disproportionate queue capacity.

Best-first scheduling (prioritizing by estimated page quality) makes sense for focused crawls where you want high-value pages fast, accepting that you will miss low-value pages on the same domains. The tradeoff is queue churn: estimating priority requires some signal (link count, anchor text, domain score), which adds computation per URL.

A practical middle ground: use BFS within a host’s back queue, and use priority scoring across front queues to decide which domains get crawler attention. This keeps per-host ordering simple while still expressing inter-domain preference.

Politeness Policies

A crawler that ignores politeness gets banned. More importantly, a crawler that hammers a server is doing real harm. Two mechanisms govern politeness: robots.txt exclusion and crawl delays.

robots.txt Parsing

Robots.txt must be fetched before crawling any URL on a host. The parsed ruleset needs to be cached with a reasonable TTL (typically 24 hours), since fetching it on every request defeats the purpose.

interface RobotsRules {
  disallowedPaths: string[];
  crawlDelayMs: number | null;
  sitemapUrls: string[];
  fetchedAt: number;
  ttlMs: number;
}

class RobotsCache {
  private cache = new Map<string, RobotsRules>();
  private readonly defaultTTLMs = 24 * 60 * 60 * 1000;

  async getRules(host: string, userAgent: string): Promise<RobotsRules> {
    const cached = this.cache.get(host);
    if (cached && Date.now() - cached.fetchedAt < cached.ttlMs) {
      return cached;
    }

    const rules = await this.fetchAndParse(host, userAgent);
    this.cache.set(host, rules);
    return rules;
  }

  isAllowed(rules: RobotsRules, path: string): boolean {
    for (const pattern of rules.disallowedPaths) {
      if (this.matchesPattern(path, pattern)) return false;
    }
    return true;
  }

  private matchesPattern(path: string, pattern: string): boolean {
    // Wildcards (*) and end-of-string anchors ($) per RFC 9309
    const regex = pattern
      .replace(/[.+?^${}()|[\]\\]/g, '\\$&')
      .replace(/\*/g, '.*')
      .replace(/\$$/, '$');
    return new RegExp(`^${regex}`).test(path);
  }

  private async fetchAndParse(
    host: string,
    userAgent: string
  ): Promise<RobotsRules> {
    // Fetch https://host/robots.txt with a short timeout
    // Parse Disallow, Crawl-delay, Sitemap directives for matching user-agent
    // Return permissive defaults on 404 or fetch failure
    throw new Error('not shown');
  }
}

The important edge cases in robots.txt parsing: wildcard matching with *, the $ end-of-string anchor, and the user-agent matching order (most specific agent wins, * is the fallback). RFC 9309 is the current specification.

Per-Host Rate Limiting

Crawl delay from robots.txt is a floor, not a ceiling. A host specifying Crawl-delay: 1 means at least one second between requests from your crawler. In practice you should apply a minimum delay of 1-2 seconds even for hosts that do not specify one.

The back queue architecture handles this automatically via the nextFetchAt timestamp. The key implementation detail is that the delay clock starts when the previous response is received, not when the next request is sent. This ensures the server has recovered before the next hit.

For misbehaving hosts (5xx errors, connection resets, rate-limit responses), exponential backoff applies. A host returning 429 should not see another request for several minutes minimum. Tracking per-host error rates and adjusting crawl delay accordingly is the production behavior.

Content Deduplication

At scale, the same content appears at many URLs. Product pages with tracking parameters, mirrors, canonical URL variations, session tokens in query strings: without deduplication, you waste bandwidth and storage on identical content.

Deduplication happens at two levels: URL normalization before fetching, and content fingerprinting after fetching.

URL Normalization

URL normalization reduces structurally equivalent URLs to a canonical form before they enter the frontier.

function normalizeURL(raw: string): string | null {
  let url: URL;
  try {
    url = new URL(raw);
  } catch {
    return null;
  }

  // Force lowercase scheme and host
  url.hostname = url.hostname.toLowerCase();
  url.protocol = url.protocol.toLowerCase();

  // Remove default ports
  if (
    (url.protocol === 'http:' && url.port === '80') ||
    (url.protocol === 'https:' && url.port === '443')
  ) {
    url.port = '';
  }

  // Remove fragment (never sent to server)
  url.hash = '';

  // Strip known tracking parameters
  const trackingParams = new Set([
    'utm_source', 'utm_medium', 'utm_campaign', 'utm_term', 'utm_content',
    'fbclid', 'gclid', 'ref', 'source',
  ]);
  for (const key of [...url.searchParams.keys()]) {
    if (trackingParams.has(key)) url.searchParams.delete(key);
  }

  // Sort remaining query params for canonical ordering
  url.searchParams.sort();

  // Resolve path (removes dot segments)
  // URL constructor handles this, but verify no traversal
  const path = url.pathname.replace(/\/+/g, '/');
  url.pathname = path || '/';

  return url.toString();
}

URL normalization alone is not enough. Session tokens, pagination variants, and A/B test parameters still produce duplicate content under different URLs. That is where content fingerprinting comes in.

SimHash for Near-Duplicate Detection

An exact hash (SHA-256 of the body) catches identical pages. SimHash catches near-duplicates: pages that share 90%+ of their content but differ in timestamps, navigation labels, or ad copy.

SimHash works by hashing individual tokens in the document and summing their bit vectors, with the sign of each bit position determining the final hash. Pages with similar content produce hashes with similar bit patterns. Hamming distance between two SimHashes (number of differing bits) is the similarity metric.

type SimHash = bigint;

function tokenize(text: string): string[] {
  return text
    .toLowerCase()
    .replace(/[^\w\s]/g, ' ')
    .split(/\s+/)
    .filter(Boolean);
}

function fnv1a32(str: string): number {
  let hash = 2166136261;
  for (let i = 0; i < str.length; i++) {
    hash ^= str.charCodeAt(i);
    hash = (hash * 16777619) >>> 0;
  }
  return hash;
}

function simhash(text: string, bits = 64): SimHash {
  const tokens = tokenize(text);
  const weights = new Array(bits).fill(0);

  for (const token of tokens) {
    const h = fnv1a32(token);
    for (let i = 0; i < bits; i++) {
      const bit = (h >>> (i % 32)) & 1;
      weights[i] += bit === 1 ? 1 : -1;
    }
  }

  let fingerprint = 0n;
  for (let i = 0; i < bits; i++) {
    if (weights[i] > 0) {
      fingerprint |= 1n << BigInt(i);
    }
  }
  return fingerprint;
}

function hammingDistance(a: SimHash, b: SimHash): number {
  let xor = a ^ b;
  let count = 0;
  while (xor > 0n) {
    count += Number(xor & 1n);
    xor >>= 1n;
  }
  return count;
}

// Hamming distance <= 3 on 64-bit SimHash = near-duplicate
function isNearDuplicate(a: SimHash, b: SimHash): boolean {
  return hammingDistance(a, b) <= 3;
}

Storing and querying SimHashes at scale requires index structures that support Hamming distance lookup efficiently. The standard approach is to partition the 64-bit hash into k bands and use exact-match lookup within each band: if two hashes differ in at most d bits, at least one band will match exactly with high probability (locality-sensitive hashing). In practice, most teams store SimHashes in a distributed key-value store and query them with a background deduplication job rather than inline during crawling.

Distributed Coordination

A single crawler process cannot keep up with a production crawl. Parallelism requires partitioning the URL space across workers without creating hot spots or duplicate work.

Consistent Hashing for URL Assignment

Consistent hashing maps URLs to workers based on hostname. This ensures all URLs for a given host land on the same worker, which means per-host state (robots.txt cache, crawl delays, back queues) is local to one process.

import { createHash } from 'crypto';

class ConsistentHashRing {
  private ring = new Map<number, string>();  // hash -> workerId
  private sortedKeys: number[] = [];
  private readonly virtualNodes: number;

  constructor(virtualNodes = 150) {
    this.virtualNodes = virtualNodes;
  }

  addWorker(workerId: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const key = this.hash(`${workerId}:${i}`);
      this.ring.set(key, workerId);
    }
    this.sortedKeys = [...this.ring.keys()].sort((a, b) => a - b);
  }

  removeWorker(workerId: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const key = this.hash(`${workerId}:${i}`);
      this.ring.delete(key);
    }
    this.sortedKeys = [...this.ring.keys()].sort((a, b) => a - b);
  }

  getWorker(host: string): string {
    if (this.sortedKeys.length === 0) throw new Error('empty ring');
    const key = this.hash(host);
    const idx = this.bisect(key);
    const ringKey = this.sortedKeys[idx % this.sortedKeys.length];
    return this.ring.get(ringKey)!;
  }

  private hash(value: string): number {
    const buf = createHash('sha1').update(value).digest();
    return buf.readUInt32BE(0);
  }

  private bisect(target: number): number {
    let lo = 0, hi = this.sortedKeys.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.sortedKeys[mid] < target) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
}

When a worker leaves (crash or scale-down), consistent hashing reassigns only that worker’s hosts to neighbors. Without consistent hashing, a rebalance would redistribute all hosts, invalidating every robots.txt cache and crawl delay state simultaneously.

Virtual nodes (150 per worker is typical) smooth the distribution. Without them, a small number of workers leads to uneven load because real hash ring positions cluster.

DNS Resolution Caching

DNS resolution is frequently overlooked in crawler design. At high request rates, resolving every hostname for every fetch adds latency and hammers the DNS infrastructure. The fix is an in-process DNS cache with a TTL that respects the record’s TTL but floors it at a minimum (typically 30-60 seconds).

interface DNSRecord {
  addresses: string[];
  ttlMs: number;
  resolvedAt: number;
  currentIndex: number;  // for round-robin across addresses
}

class DNSCache {
  private cache = new Map<string, DNSRecord>();
  private readonly minTTLMs = 30_000;
  private readonly maxTTLMs = 5 * 60 * 1000;

  async resolve(hostname: string): Promise<string> {
    const cached = this.cache.get(hostname);
    if (cached && Date.now() - cached.resolvedAt < cached.ttlMs) {
      // Round-robin across multiple A records
      const addr = cached.addresses[cached.currentIndex % cached.addresses.length];
      cached.currentIndex++;
      return addr;
    }

    const record = await this.lookup(hostname);
    const ttlMs = Math.min(
      Math.max(record.ttlMs, this.minTTLMs),
      this.maxTTLMs
    );
    this.cache.set(hostname, { ...record, ttlMs, resolvedAt: Date.now(), currentIndex: 0 });
    return record.addresses[0];
  }

  private async lookup(hostname: string): Promise<Omit<DNSRecord, 'resolvedAt' | 'currentIndex'>> {
    // Use dns.resolve4 with TTL option in Node.js
    // dns.promises.resolve4(hostname, { ttl: true }) returns records with ttl field
    throw new Error('not shown');
  }
}

One detail worth getting right: when a fetch fails due to a connection error (not an HTTP error), it may indicate a DNS record that has gone stale before its TTL. Proactively re-resolving on connection failure, before applying backoff, avoids penalizing a host that simply migrated its IP.

Storage Pipeline

Fetched content needs to be stored, indexed, and made queryable. The storage pipeline typically has three stages:

Raw storage: The full HTTP response (headers + body) is written to blob storage (S3-compatible) keyed by a content-addressed hash. This is the source of truth. Re-processing does not require re-fetching.

Metadata store: URL, fetch timestamp, HTTP status, content hash, SimHash, extracted links, and response headers go into a database. This is the query layer for scheduling decisions (what to re-crawl, what is fresh).

Processing queue: A message on a topic (Kafka, Pub/Sub) triggers downstream processing: HTML parsing, link extraction, entity extraction, indexing. This decouples crawl throughput from indexing throughput, which frequently differ by an order of magnitude.

The content-addressed blob store is important for deduplication: two URLs that produce the same content hash share a blob. Storage cost scales with unique content, not unique URLs.

Tradeoffs

Design Decision	Option A	Option B	When to choose B
Frontier storage	In-process priority queue	Redis sorted sets	Multiple workers sharing one frontier, or restartable crawls
URL partitioning	Consistent hashing by host	Random assignment	Hosts do not need per-worker state isolation
Deduplication	Exact hash (SHA-256)	SimHash near-duplicate	Content varies slightly across URLs (ads, timestamps)
robots.txt caching	In-process TTL cache	Shared cache (Redis)	Workers share hosts (use with random assignment)
DNS caching	In-process	System resolver / dnscache	Consistency requirements or multi-process deployment
Back queue depth	Unbounded	Capped with backpressure	Memory pressure or fairness guarantees
Crawl scheduling	Periodic fixed interval	Adaptive based on change rate	Freshness requirements vary significantly by domain

Production Considerations

Seed URLs and bootstrap: A cold start from a seed list of high-authority domains bootstraps the link graph quickly. The frontier empties before the crawl saturates unless you continuously feed it from extracted links. Monitor frontier depth per priority tier as a leading indicator of crawl health.

Re-crawl scheduling: A page that changes daily should be recrawled daily. A static terms-of-service page can wait weeks. Change frequency estimation (comparing SimHash across fetches) drives adaptive scheduling. Exponential backoff for unchanged pages and more frequent fetching for high-churn pages is the production behavior.

Trap detection: Some sites generate infinite URL spaces: calendar pages with next/previous navigation, session tokens in paths, infinite scroll endpoints. Detecting URL traps requires tracking path depth per host and flagging hosts where frontier growth is unrelated to new unique content.

Politeness at restart: When a crawler restarts, it should not immediately fire all its pending back queues. Re-loading host state (last fetch time, crawl delay) from persistent storage before accepting any back queue dequeue is mandatory. Without this, a restart produces a thundering herd.

User-agent and crawl identification: Always use a descriptive user-agent string that includes a contact URL or email. This is not optional at production scale: site operators need a way to contact you about problems. Concealing a crawler’s identity is both unethical and counterproductive.

Closing

The interesting engineering in a web crawler is not the HTTP fetching. It is the data structures and coordination protocols that let you fetch politely, at scale, without duplicating work. The two-tier frontier, per-host back queues, consistent hashing, and SimHash deduplication each solve a distinct failure mode. Get any one wrong and the symptoms are subtle: slow crawl progress, unexplained bans, storage costs that grow faster than unique content, or workers that step on each other’s per-host state after a rebalance.

Build the URL normalization and robots.txt caching correctly from the start. They are the hardest to retrofit.