Consistent Hashing

Tier 1 — Building Block

---

1. What Is It?

Consistent hashing is a distributed hashing scheme that maps both data keys and server nodes onto the same circular hash ring, so that when nodes are added or removed, only a minimal fraction of keys need to be remapped.

The problem it solves: in a naive modulo-based hash scheme (node = hash(key) % N), adding or removing one server changes N, which remaps nearly every key — causing a massive cache invalidation storm. In a system with 100 cache nodes, removing 1 node causes ~99% of keys to remap to a different node (not just the keys that were on the removed node). Consistent hashing reduces this to ~1/N of keys remapping — only the keys that lived on the removed node.

Without consistent hashing, scaling a distributed cache or database cluster requires either taking downtime to rehash everything or accepting a thundering herd as most cache keys become invalid simultaneously.

---

2. How It Works

The Hash Ring

1. Compute a hash of each server's identifier (e.g., hash("server-A")) to place it on a circular ring of integers from 0 to 2^32 - 1.
2. For each key, compute hash(key) to get a position on the ring.
3. Walk clockwise on the ring to find the first server node. That server "owns" this key.

-+ResetFullscreen

Visualized as a circle:

         0 / 360°
           |
  340° (C) *      * 87° (A)
              \  /
         *          *
        215° (B)

Key at 50°  → clockwise → 87° = Server A
Key at 150° → clockwise → 215° = Server B
Key at 280° → clockwise → 340° = Server C

Adding / Removing a Node

When Server D is added at position 160°:

• Keys between 87° and 160° that previously went to Server B now go to Server D
• Only ~1/N keys are remapped (just the slice of the ring that D now owns)

When Server B is removed:

• Keys that pointed to B (positions 87°–215°) now go to Server C (next clockwise)
• ~1/N keys remapped

Virtual Nodes (VNodes)

A single physical node on the ring creates an uneven distribution — some servers may own a large arc and get many more keys than others (hotspots). The solution: give each physical server multiple positions on the ring (virtual nodes).

Physical servers: A, B, C
Virtual nodes (3 per server): A1, A2, A3, B1, B2, B3, C1, C2, C3

Ring: [12: A1] [45: C2] [78: B3] [102: A3] [145: C1] [190: B1] [220: A2] [270: B2] [310: C3]

With VNodes:

• Key distribution is more uniform (law of large numbers)
• When a server is added, it takes small slices from many other servers (not one large chunk)
• More VNodes = smoother distribution but more memory overhead for the ring lookup table

Typical VNode count: 100–200 virtual nodes per physical server (used by Cassandra, Amazon DynamoDB).

-+ResetFullscreen

Lookup Algorithm

function get_server(key, ring):
    h = hash(key) % RING_SIZE
    for position in sorted(ring.positions):
        if position >= h:
            return ring[position]  # First node clockwise
    return ring[ring.positions[0]]  # Wrap around

Implemented efficiently as a sorted array with binary search: O(log N) lookup where N = number of virtual nodes.

---

3. Variants & Comparisons

Approach	How It Works	Pros	Cons	Best For
Modulo hashing (hash(key) % N)	Simple integer division	Zero overhead; O(1) lookup	Adding/removing 1 node remaps ~(N-1)/N of all keys — catastrophic for caches	Fixed-size clusters with no scaling
Consistent hashing (basic)	Keys and nodes on a ring; clockwise lookup	Adding/removing node remaps ~1/N keys	Uneven distribution without VNodes	Any horizontally scaled distributed system
Consistent hashing + VNodes	Multiple ring positions per physical node	Uniform distribution; graceful scaling	More memory for ring table; slightly more complex	Cassandra, DynamoDB, large distributed caches
Rendezvous hashing (HRW)	For each key, score all nodes by hash(key, node_i); pick max	No ring data structure needed; same minimal remapping	O(N) per lookup (must score all nodes)	Small cluster sizes; no ring management overhead
Jump consistent hash	Mathematical formula maps key to node index	O(1) compute; perfectly uniform	Only supports adding nodes (not arbitrary removes)	Stateless sharding with append-only scaling

---

4. When to Use It (and When NOT To)

Use Consistent Hashing When:

• Distributed cache cluster (Redis Cluster, Memcached with client-side sharding): Keys must route to the same node across all clients; nodes can be added/removed without full cache invalidation
• Database sharding with dynamic scaling: Shard assignment based on consistent hash of the partition key
• Load balancing with session affinity: Route requests from the same user to the same backend server (sticky sessions) — consistent hash of user ID or IP
• Distributed message queue partitioning: Route messages by producer ID to the same partition for ordering guarantees

Decision triggers:

• "If you need to add/remove cache nodes without a full cache miss storm → consistent hashing"
• "If you have a distributed key-value store that needs to rebalance without full resharding → consistent hashing + VNodes"
• "If you need O(log N) deterministic key-to-node routing without a centralized router → consistent hashing"

Do NOT Use Consistent Hashing When:

• Fixed small cluster with no scaling: hash(key) % N is simpler and fine
• Range queries dominate: Consistent hashing distributes by hash, destroying key ordering. Range queries (give me all keys from X to Y) don't work. For range-based access patterns, use range-based sharding (explicit shard boundaries by key range).
• You need a coordinator anyway: If you're already using ZooKeeper or etcd for cluster membership, you can store explicit key-to-node mappings there without consistent hashing.

Anti-patterns:

• Too few VNodes: 1 VNode per server causes severe hotspots. Use 100–200.
• Bad hash function: MD5/SHA1 truncated is fine. hash(key) = key % N for sequential integer keys creates severe uneven distribution. Use a good hash: MurmurHash3, xxHash.
• Ignoring hotspot keys: Consistent hashing distributes keys uniformly, but if 90% of traffic is for 1 key (celebrity problem), it doesn't help. You need explicit handling for hot keys (replication, local cache).

---

5. Real-World Usage

Apache Cassandra: Cassandra uses consistent hashing with virtual nodes (VNodes) to distribute data across the cluster. Each node is assigned 16 VNodes by default as of Cassandra 4.0 (256 in older 2.x/3.x versions) — token ranges on the ring. When you add a node, it claims tokens from existing nodes, redistributing ~1/N of their data. Cassandra's token-aware drivers route queries directly to the correct replica — no need for a central router.

Amazon DynamoDB: DynamoDB uses consistent hashing internally to distribute items across storage nodes. The partition key is hashed to determine placement. DynamoDB automatically splits hot partitions and rebalances across nodes. Users don't interact with the ring directly, but understanding consistent hashing explains why choosing a high-cardinality partition key (not country, which creates 200 partitions, but user_id, which creates millions) leads to even distribution.

Discord (distributed presence): Discord routes user presence data (online/offline status) using consistent hashing on user_id to determine which presence service pod owns each user. This ensures all messages about user X's presence go to the same pod, enabling efficient fan-out to friends without cross-pod coordination.

---

6. Interview Cheat Sheet

Key sentences to demonstrate depth:

1. "Consistent hashing maps both keys and nodes to a ring; adding or removing a node only remaps ~1/N keys — essential for distributed caches where a modulo rehash would cause a complete cache miss storm."
2. "Virtual nodes solve the uneven distribution problem: each physical server gets 100–200 positions on the ring, so key distribution follows the law of large numbers even with heterogeneous nodes."
3. "Lookup is O(log V) where V is total virtual nodes — implemented as a sorted array with binary search, finding the first position ≥ hash(key)."
4. "Consistent hashing doesn't help with hot keys — if one key gets 90% of traffic, it still goes to one node. Hot key handling requires explicit strategies: replicate the key or cache it locally."
5. "For range queries, consistent hashing is the wrong tool — hashing destroys key ordering. Use range-based sharding instead if your access pattern is 'give me all keys between X and Y'."

Common follow-up questions:

Question	Concise Answer
"What happens when a node crashes?"	Keys from the crashed node move clockwise to the next node. With replication factor R, Cassandra/Dynamo have R-1 replicas that can serve the data — no data loss. Without replication, data on the crashed node is unavailable.
"How many VNodes should you use?"	Cassandra 4.0+ defaults to 16 (older 2.x/3.x versions used 256), paired with the token-allocation algorithm for even distribution. More VNodes means more uniform distribution but more ring metadata and slower repair — which is why 4.0 lowered the default.
"How do you handle heterogeneous nodes?"	Assign more VNodes to stronger nodes (proportional to their capacity). A node with 2× the memory gets 2× the VNodes and thus 2× the key share.
"What hash function should I use?"	MurmurHash3 or xxHash: fast, uniform distribution, not cryptographic (no need for security). Cassandra uses Murmur3 by default. Avoid MD5/SHA1 (slow); avoid mod for sequential keys (bad distribution).
"Consistent hashing vs. range-based sharding?"	Consistent hashing = uniform distribution, no ordered range queries, easy rebalancing. Range sharding = ordered ranges (efficient range queries), risk of hotspots if range is skewed, manual rebalancing. Choose based on whether range queries are needed.

Connections to other building blocks:

• Sharding & Partitioning: Consistent hashing is the most common algorithm for determining shard assignment in distributed databases. Cassandra's token ring is consistent hashing.
• Caching Strategies: Distributed cache clusters (Redis Cluster, Memcached with twemproxy) use consistent hashing to route keys to cache nodes without a central registry.
• CDN: CDNs use consistent hashing internally to route requests to the same edge cache node for a given URL — maximizing hit rate across CDN nodes.
• Load Balancing: Consistent hash load balancing provides sticky sessions (same client → same server) without shared session state, based on client IP or session ID hash.
• Key-Value Store: Redis Cluster implements consistent hashing with 16,384 hash slots. Each master node owns a range of hash slots.