Consistent Hashing: How Distributed Systems Route Data Without Rethinking Everything

The problem with modulo hashing

The obvious way to distribute data across N nodes is hash(key) % N. It works until you change N. Add one node to a 10-node cluster and nearly every key maps to a different node — you're rebalancing almost everything. For a cache, that means a thundering herd of misses. For a database, it means a migration that can take hours.

Consistent hashing solves this. When N changes, only 1/N of the keys need to move, not all of them.

The ring

Imagine a circle with 2^32 points (or any large integer space). You hash each node's identifier to place it on the ring. To find which node owns a key, hash the key and walk clockwise until you hit a node.

Ring (0 → 2^32):

  Node A at position 100
  Node B at position 300
  Node C at position 700

  Key K hashes to 250 → walks clockwise → owned by Node B

When you add Node D at position 400, only the keys between 300 and 400 (previously owned by C) move to D. Everything else stays put.

When you remove Node B, only the keys between 100 and 300 move to C. No other node is affected.

Virtual nodes

A naive ring gives uneven distribution. If the three node positions happen to cluster, one node gets most of the keyspace. The fix is virtual nodes (vnodes): each physical node gets multiple positions on the ring.

Node A → positions 100, 520, 800
Node B → positions 200, 450, 900
Node C → positions 300, 600, 1000

With 100–200 virtual nodes per physical node, the keyspace distributes almost uniformly. When you add a new physical node, it claims a fraction of each existing node's virtual ranges instead of one large contiguous chunk.

Replication

Most systems replicate each key to the next N nodes clockwise, not just the first. Cassandra uses this: each key has a replication factor (RF) and is written to the primary node and RF-1 replicas walking clockwise from it. Read requests can be satisfied by any replica, trading consistency for availability depending on quorum settings.

Where you'll see this in production

Amazon DynamoDB uses consistent hashing internally to partition data across storage nodes. The partition key is hashed and placed on the ring; DynamoDB manages virtual nodes transparently.

Apache Cassandra exposes the ring directly. The nodetool ring command shows each node's token position. When you add a node you specify its token (or let the system auto-assign it to balance the ring).

Redis Cluster uses a fixed 16,384-slot hash ring. Each slot is assigned to a node. When you scale out, you migrate slots (and their keys) to the new node — a smaller, discrete version of the same idea.

Memcached client libraries like ketama implement consistent hashing in the client, not the server. The client maintains the ring and routes requests accordingly.

What consistent hashing does not solve

• Hot keys. If one key receives disproportionate traffic, consistent hashing cannot help — you still need caching, read replicas, or key sharding at the application level.
• Cross-node transactions. Distributing keys across nodes makes multi-key atomic operations expensive. You need distributed transactions (two-phase commit) or you redesign to avoid them.
• Imbalance at small N. With 3 nodes and 100 vnodes each, the distribution is reasonable. With 3 nodes and 3 positions, it is not.

The practical takeaway

Consistent hashing is the mechanism that lets clusters grow and shrink without a full reshuffle. You do not need to implement it from scratch — every major distributed datastore provides it. What you do need to understand is the tradeoff it makes: you accept a small amount of key movement (one node worth) in exchange for not moving everything. That tradeoff is usually the right one.