2 Consistent Hashing

You have 4 servers storing user data. You hash each user's ID and take hash % 4 to pick a server. It works perfectly -- until you add a 5th server. Now it's hash % 5, and almost every key maps to a different server. You'd need to move nearly all your data. At scale, that's a disaster.

Consistent hashing solves this by ensuring that adding or removing a server moves only a small fraction of keys.

Think first

You have N servers and use hash(key) % N to assign keys. You add one server. How many keys need to move, and how would you design a better scheme?

Background

Data partitioning -- distributing data across multiple nodes -- is fundamental to any scalable system. Two challenges arise:

1. Given a key, which node stores it?
2. When nodes join or leave, how do you minimize the data that needs to move?

The naive approach (hash(key) % N) solves #1 but fails catastrophically at #2. Every time N changes, most keys remap to different nodes.

Definition

Consistent hashing maps both data and nodes onto the same hash ring, so that each node is responsible for the keys between it and its predecessor on the ring. When a node is added or removed, only the keys in the affected range move -- everything else stays put.

How it works

Imagine the hash space as a ring (the output of the hash function wraps around). Each node is placed on the ring at a position determined by hashing its identifier. Each key is also hashed onto the ring, and it's stored on the first node you encounter walking clockwise from the key's position.

The ring is divided into ranges, each owned by a node. The start of a range is called a token:

Server	Token	Range
Server 1	1	1 – 25
Server 2	26	26 – 50
Server 3	51	51 – 75
Server 4	76	76 – 100

To find where a key lives: hash the key (e.g., MD5), map the result to the ring, and walk clockwise to the first node.

Why this is better: When a node is removed, only its keys move -- to the next node clockwise. When a node is added, it takes over a portion of the next node's range. Everything else is untouched.

The math

With simple hashing (hash % N), adding one node to a 100-node cluster remaps ~99% of keys. With consistent hashing, adding one node remaps only ~1/N of keys (~1%). At scale, this is the difference between a manageable migration and a system-wide storm.

The problem: uneven distribution

With basic consistent hashing, each node owns one range on the ring. This creates two issues:

• Hotspots: If keys aren't uniformly distributed, some nodes get far more data than others
• Expensive rebalancing: Adding a node only relieves load from one neighbor, not the whole cluster
• Slow rebuilding: If a node dies, only its replica nodes can provide the data -- a small set under heavy pressure

Virtual nodes (Vnodes): the fix

Instead of assigning each physical node one position on the ring, assign it many positions (virtual nodes). Each vnode owns a small range, and a single physical node might have 256 vnodes scattered across the ring.

Why vnodes matter

Problem	How vnodes solve it
Uneven load	Many small ranges per node averages out to even distribution
Slow rebalancing	Adding a node takes vnodes from many existing nodes, not just one neighbor
Heterogeneous hardware	Powerful machines get more vnodes; weaker machines get fewer
Faster rebuilding	Many nodes participate in rebuilding (each contributing a few vnodes), instead of overloading a few replicas

Interview angle

Consistent hashing is the default answer to "How do you distribute data across nodes?" Always mention vnodes as the refinement -- it shows you understand the practical limitations of the basic algorithm. The key phrase: "Consistent hashing with virtual nodes ensures even distribution and minimal data movement when the cluster changes."

Examples

Dynamo

Dynamo uses consistent hashing with vnodes as its core data distribution mechanism. Each key is hashed with MD5 to determine which vnode (and therefore which physical node) owns it. See Data Partitioning for the full details.

Cassandra

Cassandra adopted the same approach -- consistent hashing with vnodes -- directly from Dynamo. Each Cassandra node is assigned multiple tokens on the ring. The number of vnodes per node is configurable, allowing heterogeneous clusters.

Quiz

In a consistent hashing ring with virtual nodes, one physical node fails. What would happen if that node had only 1 vnode (basic consistent hashing) versus 256 vnodes?

Recovery would be faster with 1 vnode because less data needs to move.

With 1 vnode, all the failed node's data lands on a single neighbor (creating a hotspot and slow recovery). With 256 vnodes, the data is spread across many nodes, enabling parallel recovery and avoiding overloading any single node.

There would be no difference because consistent hashing already distributes data evenly.

With 256 vnodes, the recovery would be slower because more metadata needs to be updated.