#📝 Note: Consistent Hashing

#Overview

Consistent hashing is a distributed hashing scheme that minimizes key redistribution when nodes are added or removed from a cluster. Unlike modular hashing (key % N), which remaps nearly all keys when N changes, consistent hashing remaps only K/N keys on average (K = total keys, N = nodes).

#Core Idea

• Hash Ring: Both keys and nodes are hashed onto a circular ring (0 to 2^32 - 1)
• Key Assignment: A key is assigned to the first node encountered clockwise on the ring
• Virtual Nodes: Each physical node maps to 100-200 virtual nodes on the ring for even distribution
• Minimal Disruption: Adding/removing a node only affects keys in the adjacent ring segment

#How It Works

Hash Ring (simplified):

        Node A (hash=100)
           │
    ┌──────┴──────┐
    │             │
    │   Keys in   │
    │  range      │
    │  (300,100]  │
    │             │
Node C           Node B
(hash=300)      (hash=200)

Key "user:123" → hash = 150 → assigned to Node B (first node clockwise)
Key "user:456" → hash = 250 → assigned to Node C
Key "user:789" → hash = 50  → assigned to Node A

#Virtual Nodes

Aspect	Without Virtual Nodes	With Virtual Nodes (150/node)
Distribution	Uneven (depends on hash luck)	Near-uniform
Heterogeneous HW	Can't account for capacity	More vnodes for stronger machines
Node addition	Uneven key pickup	Smooth redistribution
Memory overhead	Low	Moderate (150 ring entries per node)

#When to Use

• Distributed caches — Memcached, Redis cluster for partition-aware routing
• Database sharding — Distribute data across DB nodes (Cassandra, DynamoDB)
• Load balancing — Consistent routing to backend servers (sticky sessions)
• Distributed storage — Key-to-node mapping in distributed file systems

#When NOT to Use

• Small clusters (< 5 nodes) — Simple modular hashing is sufficient and simpler
• Range queries needed — Consistent hashing scatters keys; use range partitioning instead
• Strict ordering — Keys are distributed by hash, not by natural order

#Trade-offs

• Pros: Minimal key redistribution (K/N); scales well; no central coordinator needed; supports heterogeneous nodes
• Cons: More complex than modular hashing; virtual nodes add memory overhead; rebalancing still has some cost; non-trivial to implement correctly

#Used In This Repo

• Key-Value Store (#3) — Core partitioning strategy for distributing keys across nodes
• Web Crawler (#12) — URL-to-crawler assignment for distributed crawling