Consistent Hashing

Consistent hashing is a technique that minimizes data movement when nodes are added or removed from a distributed system. It's fundamental to how modern distributed databases, caches, and load balancers scale—and a favorite topic in system design interviews.

When you're designing any system that distributes data across multiple servers (database sharding, distributed caches, load balancers), the question of "how do we decide which server handles which data?" becomes critical. Consistent hashing provides an elegant answer.

The Problem with Simple Hashing

The naive approach to distributing data across N servers is simple modulo hashing:

server = hash(key) % num_servers

This works well... until you need to add or remove a server.

Example: With 3 servers, hash(key) % 3 distributes keys. If you add a 4th server:

• Before: key_100 → hash(100) % 3 = 1 → Server 1
• After: key_100 → hash(100) % 4 = 0 → Server 0

The key moved! And it's not just one key—most keys change servers when you add or remove nodes:

This causes a "thundering herd" problem: sudden massive cache misses or data migration storms that can overwhelm your system.

How Consistent Hashing Works

Consistent hashing solves this by mapping both keys and nodes to positions on a circular hash ring (typically 0 to 2³²-1).

The algorithm:

1. Hash each node to a position on the ring
2. Hash each key to a position on the ring
3. Walk clockwise from the key's position to find the first node—that node owns the key

Example: As shown in the diagram, Key 1 at around 45° walks clockwise and finds Node B at ~120°. Key 2 at ~150° walks clockwise to Node C at ~225°. Key 3 at ~310° walks clockwise to Node A at ~330°.

Why It Minimizes Data Movement

The key insight: when you add or remove a node, only keys adjacent to that node on the ring are affected.

Adding a node: The new node takes over keys from its clockwise neighbor. Only those keys move—everything else stays put.

Removing a node: Keys from the removed node move to the next clockwise neighbor. Again, only those keys move.

With consistent hashing, the disruption from adding a node is proportional to 1/n rather than nearly 100%.

Virtual Nodes

Basic consistent hashing has a problem: nodes may not be evenly distributed on the ring, leading to unbalanced load. One node might own 50% of the key space while another owns 10%.

Virtual nodes solve this by giving each physical node multiple positions on the ring:

Physical Node A → Virtual nodes: A-0, A-1, A-2, A-3
Physical Node B → Virtual nodes: B-0, B-1, B-2, B-3
Physical Node C → Virtual nodes: C-0, C-1, C-2, C-3

Benefits:

• Better load distribution — More points on the ring = more even distribution
• Smoother rebalancing — Adding a node spreads its virtual nodes across the ring, taking small slices from many nodes instead of a large slice from one
• Heterogeneous capacity — Give more virtual nodes to more powerful servers

Common configurations:

• 100-200 virtual nodes per physical node is typical
• DynamoDB uses this approach for its partition management
• Cassandra implements virtual nodes (called "vnodes") with configurable count

Real-World Applications

Consistent hashing appears throughout distributed systems:

Distributed Caches (Memcached, Redis Cluster)

When a cache node fails, only keys on that node need to be re-fetched from the database. Without consistent hashing, a node failure would invalidate the entire cache.

Distributed Databases (Cassandra, DynamoDB)

Data is partitioned across nodes using consistent hashing. Adding capacity means spinning up new nodes—data automatically redistributes with minimal movement.

Load Balancers

Session-affinity load balancing (where requests from the same user should go to the same server) uses consistent hashing on user IDs or session tokens.

Content Delivery Networks (CDNs)

CDNs use consistent hashing to determine which edge server caches which content, ensuring requests for the same URL hit the same cache.

Implementation Considerations

When implementing or discussing consistent hashing in interviews, consider these points:

Replication and fault tolerance: In databases, keys are typically replicated to the next N nodes on the ring (e.g., the next 2-3 nodes clockwise). This provides redundancy without separate configuration.

Hash function choice: Use a well-distributed hash function like MD5 or MurmurHash. Poor hash functions create hotspots on the ring.

Ring membership management: Nodes need to agree on who's in the cluster. This typically involves a gossip protocol or a coordination service like ZooKeeper.

Handling hotspots: Consistent hashing distributes data evenly on average, but doesn't prevent hotspots from uneven access patterns. A celebrity's profile might be on one shard but receive 1000x the traffic. Solutions include replication, caching, or splitting hot keys.

Quick Reference

When to Use Consistent Hashing

Key Points for Interviews

• Problem: Simple hash % n causes massive data movement when n changes
• Solution: Hash keys AND nodes to positions on a ring; walk clockwise to find owner
• Benefit: Only ~1/n keys move when adding a node (vs ~100% with modulo)
• Virtual nodes: Multiple ring positions per physical node for better balance
• Used by: DynamoDB, Cassandra, Memcached, Redis Cluster, CDNs

What Interviewers Look For

1. Understanding the problem — You can explain why modulo hashing fails at scale
2. The ring concept — You can describe how keys and nodes map to a circular hash space
3. Minimal movement — You understand that only adjacent keys move during topology changes
4. Virtual nodes — You know how to improve load distribution
5. Real applications — You can connect the concept to actual systems (databases, caches, CDNs)