Distributed URL Deduplication
You'll learn how to partition URL deduplication across multiple crawler nodes using consistent hashing, enabling horizontal scalability without duplication overhead.
The Challenge
As your web crawler scales to billions of URLs, a single Bloom filter or hash table becomes a bottleneck. You need multiple machines, each responsible for checking a subset of URLs. The key question: how do you ensure the same URL always routes to the same machine for its "seen" check?
Consistent Hashing Solution
Consistent hashing solves this by mapping each URL to a position on a virtual ring (0 to 2^32), then assigning that position to a specific deduplication node.
How It Works
- Hash the URL: Apply a hash function to the normalized URL:
hash("http://example.com/page") → 12345678 - Map to Ring Position: This hash value corresponds to a point on the ring
- Find Responsible Node: Walk clockwise on the ring until you hit a node; that node owns this URL's deduplication state
- Route Check Request: Send the "have we seen this URL?" query to that specific node
Implementation Pattern
normalized_url = normalize(raw_url)
hash_value = hash(normalized_url)
node_id = consistent_hash_ring.get_node(hash_value)
if dedup_clients[node_id].check_and_add(normalized_url):
# New URL, add to frontier
else:
# Already seen, skip
Benefits
- Even distribution: URLs spread uniformly across nodes
- Minimal reshuffling: Adding/removing nodes only affects adjacent ranges
- No coordination: Each crawler worker independently computes which dedup node to query
- Linear scaling: Double your nodes, double your dedup capacity
Key Takeaway:
Consistent hashing partitions the URL space across deduplication nodes, ensuring each URL always maps to the same checker while allowing horizontal scaling without central coordination.