13 min read

Sharding a URL Frontier Across Crawl Workers

Once a crawl outgrows a single process, the frontier — the queue of URLs still waiting to be fetched — has to live somewhere every worker can read from, and every worker has to agree on which host it owns. Get the assignment rule wrong and two workers hammer the same origin at the same moment, defeating whatever rate limit either of them thinks it is enforcing. This page is part of Orchestrating Distributed Crawls Across Workers and shows the exact consistent-hash implementation that assigns whole hosts to workers, so per-host politeness survives horizontal scaling instead of being the first thing it breaks.

Frontier URL to Worker Shard Assignment Diagram showing a queued frontier URL reduced to its registered domain, that domain hashed onto a consistent-hash ring of worker virtual nodes, and the URL pushed to the queue of the nearest clockwise worker. Frontier URL queued URL shop.example.com/cart extract host Extract Host registered domain shop.example.com hash(host) Consistent-Hash Ring nearest clockwise worker assign Worker Shard Queue redis LPUSH queue:worker-1

Environment Isolation and Dependencies

Pin the hashing and Redis client libraries before the ring goes anywhere near production traffic. A silent version bump in the domain-parsing library is the most common source of a ring that assigns hosts differently on two workers running "the same" code.

# /opt/audit/frontier_shard — absolute working directory for the ring builder
export PYTHONPATH=/opt/audit/frontier_shard
export SHARD_WORKERS="worker-0,worker-1,worker-2,worker-3"
export SHARD_VNODES=150
export SHARD_REDIS_DSN="redis://redis.internal:6379/0"
# requirements.txt — pin every direct dependency
redis==5.0.4
tldextract==5.1.2

set -euo pipefail
cd /opt/audit/frontier_shard
python3 -m venv .venv
.venv/bin/pip install --quiet -r requirements.txt

SHARD_WORKERS is the ordered set of worker identifiers every process in the fleet must agree on. Change it in exactly one place — a config repo, not a per-worker environment file — because a ring built from a different worker list on two hosts is two different rings, and hosts will silently double-process.

Implementation

The ring assigns work in two stages: reduce a URL to its registered domain, then walk a sorted list of hashed virtual-node positions to find the first worker at or after that domain's own hash position. Virtual nodes exist so that each physical worker owns many small, scattered arcs of the ring instead of one large contiguous arc — without them, one worker can end up owning a disproportionate share of hosts purely by chance.

#!/usr/bin/env python3
# /opt/audit/frontier_shard/shard_frontier.py
"""
Assign each frontier URL to a worker shard via consistent hashing on the
registered domain (eTLD+1), then push it onto that worker's Redis queue.
"""

import bisect
import hashlib
import os
import sys

import redis
import tldextract  # pinned: tldextract==5.1.2

VNODES_PER_WORKER = int(os.environ.get("SHARD_VNODES", 150))
WORKERS = os.environ["SHARD_WORKERS"].split(",")
REDIS_DSN = os.environ.get("SHARD_REDIS_DSN", "redis://redis.internal:6379/0")

r = redis.Redis.from_url(REDIS_DSN, decode_responses=True)


def _ring_hash(key: str) -> int:
    """Map any string onto the 0-2**32 ring using a stable, non-cryptographic hash."""
    digest = hashlib.md5(key.encode("utf-8")).hexdigest()
    return int(digest[:8], 16)  # top 32 bits of the digest — ample spread for this ring size


def build_ring(workers: list[str], vnodes: int) -> tuple[list[int], dict[int, str]]:
    """Hash `vnodes` virtual copies of each worker onto the ring and sort the positions."""
    ring_map: dict[int, str] = {}
    for worker in workers:
        for v in range(vnodes):
            pos = _ring_hash(f"{worker}#{v}")
            ring_map[pos] = worker
    sorted_positions = sorted(ring_map)
    return sorted_positions, ring_map


def registered_domain(url: str) -> str:
    """Reduce a URL to its registered domain (eTLD+1), not the full hostname.
    www.shop.example.com and checkout.shop.example.com both resolve to
    shop.example.com, so a site's subdomains never split across workers."""
    ext = tldextract.extract(url)
    return f"{ext.domain}.{ext.suffix}"


def assign_worker(host_key: str, positions: list[int], ring_map: dict[int, str]) -> str:
    """Walk clockwise from the host's ring position to the first worker vnode."""
    pos = _ring_hash(host_key)
    idx = bisect.bisect_right(positions, pos) % len(positions)
    return ring_map[positions[idx]]


def enqueue(url: str, positions: list[int], ring_map: dict[int, str]) -> str:
    host = registered_domain(url)
    worker = assign_worker(host, positions, ring_map)
    r.lpush(f"frontier:{worker}", url)
    return worker


if __name__ == "__main__":
    positions, ring_map = build_ring(WORKERS, VNODES_PER_WORKER)
    for line in sys.stdin:
        target_url = line.strip()
        if not target_url:
            continue
        assigned = enqueue(target_url, positions, ring_map)
        print(f"{target_url} -> {assigned}")

A few details matter more than they look:

  • _ring_hash uses MD5 truncated to 32 bits, not a cryptographic property — it only needs to spread strings evenly, and MD5 is fast and available everywhere without a native extension.
  • build_ring runs once per worker process at startup, not per URL. Every worker must construct it from the same SHARD_WORKERS list and SHARD_VNODES value, or two workers will disagree about who owns a given host.
  • registered_domain is the single most important line in the file. Hashing urlsplit(url).hostname instead would let www.shop.example.com and checkout.shop.example.com land on different workers, which is exactly the split this whole design exists to prevent.
  • assign_worker uses bisect_right with a modulo wrap so a hash position past the last virtual node wraps back to the first one on the ring — the ring has no start or end.
  • enqueue pushes to a queue named after the worker, not a shared queue with a routing header, so a worker only ever needs to BRPOP its own key and never has to inspect a message to know if it owns it.

Verification and Smoke Test

Two properties matter: the same host must always resolve to the same worker (determinism), and no worker should own a wildly disproportionate share of hosts (balance).

set -euo pipefail
cd /opt/audit/frontier_shard

.venv/bin/python - <<'PY'
from shard_frontier import build_ring, assign_worker, registered_domain
import collections

WORKERS = ["worker-0", "worker-1", "worker-2", "worker-3"]
positions, ring_map = build_ring(WORKERS, 150)

sample_hosts = [f"site-{i}.example.com" for i in range(2000)]

# 1. determinism — repeated lookups must agree
first_pass = {h: assign_worker(h, positions, ring_map) for h in sample_hosts}
second_pass = {h: assign_worker(h, positions, ring_map) for h in sample_hosts}
assert first_pass == second_pass, "FAIL: same host resolved to different workers on repeat lookups"
print("PASS: deterministic host-to-worker assignment")

# 2. balance — no worker should own more than ~2x the average share
counts = collections.Counter(first_pass.values())
avg = len(sample_hosts) / len(WORKERS)
worst = max(counts.values())
assert worst < avg * 2, f"FAIL: worker owns {worst} hosts, more than 2x the {avg:.0f} average"
print(f"PASS: max worker share {worst} vs average {avg:.0f} — {dict(counts)}")

# 3. rebalance cost — adding a worker should remap roughly 1/N of hosts, not all of them
positions5, ring_map5 = build_ring(WORKERS + ["worker-4"], 150)
after = {h: assign_worker(h, positions5, ring_map5) for h in sample_hosts}
moved = sum(1 for h in sample_hosts if first_pass[h] != after[h])
fraction = moved / len(sample_hosts)
assert fraction < 0.35, f"FAIL: adding one worker remapped {fraction:.0%} of hosts"
print(f"PASS: adding a 5th worker remapped {fraction:.0%} of hosts (expected roughly 20%)")
PY

Expected output:

PASS: deterministic host-to-worker assignment
PASS: max worker share 512 vs average 500 — {'worker-0': 489, 'worker-1': 512, 'worker-2': 498, 'worker-3': 501}
PASS: adding a 5th worker remapped 21% of hosts (expected roughly 20%)

If the balance check fails, raise SHARD_VNODES before touching anything else — more virtual nodes per worker is almost always the fix for lopsided ring ownership, not a different hash function.

Failure Modes

A hot host dominates one worker's queue depth

Consistent hashing balances the count of hosts per worker, not the volume of URLs behind each host. A single retailer with 400,000 product pages can outweigh every other host assigned to its worker combined, so that worker's queue never drains while its neighbors sit idle.

# diagnostic: compare queue depth across workers
for w in worker-0 worker-1 worker-2 worker-3; do
  echo -n "$w: "; redis-cli -u "$SHARD_REDIS_DSN" LLEN "frontier:$w"
done
# fix: split the oversized host's own frontier by path prefix and treat each
# prefix as an independent hash key, rather than rebalancing the whole ring

Rebalancing storm after removing a worker without virtual nodes

A ring with one position per physical worker (no virtual nodes) concentrates each worker's departure onto a single neighbor, which then inherits that worker's entire arc at once instead of a spread share from every remaining worker.

# diagnostic: rebuild the ring with and without the departing worker, measure remap fraction
.venv/bin/python -c "
from shard_frontier import build_ring, assign_worker
before_pos, before_map = build_ring(['worker-0','worker-1','worker-2','worker-3'], 1)
after_pos, after_map = build_ring(['worker-0','worker-1','worker-2'], 1)
hosts = [f'site-{i}.example.com' for i in range(2000)]
moved = sum(1 for h in hosts if assign_worker(h, before_pos, before_map) != assign_worker(h, after_pos, after_map))
print(f'{moved/len(hosts):.0%} remapped with 1 vnode per worker')
"
# fix: redeploy with SHARD_VNODES=150 (or higher) so departures spread across
# every remaining worker instead of concentrating on one neighbor

Hashing the full URL instead of the host

If _ring_hash is applied to the whole URL rather than the output of registered_domain, every page of a host scatters across the fleet essentially at random. Per-host rate limiting managed under managing crawl budget and rate limiting then has no single worker to enforce against, because four workers can each believe they are the only one talking to that origin.

# diagnostic: check whether URLs from one host land on more than one queue
.venv/bin/python -c "
import redis
r = redis.Redis.from_url('$SHARD_REDIS_DSN', decode_responses=True)
for w in ['worker-0','worker-1','worker-2','worker-3']:
    sample = r.lrange(f'frontier:{w}', 0, 50)
    hosts = {u.split('/')[2] for u in sample if '://' in u}
    print(w, sorted(hosts)[:5])
"
# fix: redeploy shard_frontier.py with the registered_domain() reduction in
# place before enqueue(), then drain and re-shard the existing queues

FAQ

Why hash the registered domain instead of the full URL?

Hashing the full URL scatters pages from the same host across every worker, so several workers can end up hitting the same origin at once with no single worker able to enforce a per-host rate limit. Hashing the registered domain guarantees every page under a host lands on one worker, which is what makes per-host politeness possible in the first place.

How many virtual nodes should each worker get?

100 to 200 virtual nodes per worker is a reasonable default for fleets of 4 to 64 workers. Too few leaves visible gaps on the ring and skews load toward whichever worker happens to own the largest arc; too many adds negligible balance improvement past a few hundred while making the in-memory ring larger to rebuild on every worker join or leave.

What happens to in-flight URLs when I add or remove a worker?

Consistent hashing only remaps the arc adjacent to the worker that joined or left, roughly 1/N of all hosts, not the whole frontier. URLs already pushed onto a queue stay there and drain from whichever worker currently owns that queue name; only newly discovered URLs use the freshly rebuilt ring, so a rolling worker restart never requires draining or replaying the entire frontier.

Can a hot host still overload a single worker even with correct hashing?

Yes. Consistent hashing balances the number of hosts per worker, not the number of URLs behind each host, so one very large site can still dominate a single worker's queue depth. Pair host-level sharding with the per-host rate limiting described in managing crawl budget and rate limiting, and consider splitting a single oversized host's frontier by path prefix if it consistently outweighs every other host assigned to that worker combined.