Course contentsShow
← System Design
Lesson 1854 of 1,91944. Real-World System: Web CrawlerFree lesson

Distributed URL Deduplication

Implement consistent hashing to partition URL deduplication across multiple crawler nodes at scale.

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

  1. Hash the URL: Apply a hash function to the normalized URL: hash("http://example.com/page") → 12345678
  2. Map to Ring Position: This hash value corresponds to a point on the ring
  3. Find Responsible Node: Walk clockwise on the ring until you hit a node; that node owns this URL's deduplication state
  4. 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.