Definition
- Hash ring – both keys and nodes are mapped onto a fixed circular hash space; each key belongs to the first node found clockwise.
- Minimal movement – adding or removing a node moves only the keys in that node's arc, about K/N of all keys, instead of a near-total reshuffle.
- Virtual nodes – each physical node is hashed to many positions on the ring, smoothing out uneven arcs and allowing weighted assignment for heterogeneous hardware.
- Modulo hashing problem –
hash(key) % Nchanges almost every assignment when N changes, making online scaling impractical. - Production use – underpins Dynamo-style stores, Cassandra, Redis clusters, and distributed caches.
Imagine National Bank of India placing all accounts around a clock face, and each shard sits at a spot on the clock. An account is handled by the next shard clockwise. If the bank opens a new shard, only the accounts in that one arc move: everyone else stays put. Virtual nodes are like giving each shard many spots around the clock so no single shard accidentally ends up with a giant arc.
Understanding the Concepts
Why is modulo hashing a problem for scaling?
With plain modulo hashing, changing the node count reshuffles almost every key.
package com.bank.sharding;
public class ModuloHashDemo {
public static void main(String[] args) {
int oldNodes = 4;
int newNodes = 5;
int moved = 0;
for (int key = 0; key < 10000; key++) {
int oldShard = Math.abs(key) % oldNodes;
int newShard = Math.abs(key) % newNodes;
if (oldShard != newShard) moved++;
}
System.out.println("Keys moved: " + moved + " / 10000");
// Output: Keys moved: ~8000 / 10000 (80% reshuffled!)
}
}
For a live banking system, moving 80% of data during a scale-out is catastrophic.
How does consistent hashing work?
Both nodes and keys are hashed onto the same circular ring. A key is owned by the first node found clockwise from the key's position.
package com.bank.sharding;
import java.util.*;
public class ConsistentHashRing {
private final TreeMap<Long, String> ring = new TreeMap<>();
public void addNode(String node) {
long hash = hash(node);
ring.put(hash, node);
}
public void removeNode(String node) {
long hash = hash(node);
ring.remove(hash);
}
public String getNodeForKey(String key) {
long hash = hash(key);
Map.Entry<Long, String> entry = ring.ceilingEntry(hash);
if (entry == null) {
entry = ring.firstEntry(); // wrap around the ring
}
return entry.getValue();
}
private long hash(String value) {
// Use a good hash function (MD5, MurmurHash, etc.)
return value.hashCode() & 0xFFFFFFFFL;
}
}
How does adding a node minimize data movement?
Adding a node inserts one point on the ring and steals only the arc between it and the previous node.
Before adding Node D:
Node A (0°)
│
▼
───────●──────────────────────────●─── Node B (120°)
│ │
│ keys in this arc │
│ belong to Node B │
│ │
───────●──────────────────────────┘
Node C (240°)
After adding Node D at 60°:
Node A (0°) Node D (60°)
│ │
▼ ▼
───────●───────────●──────────────●─── Node B (120°)
│
Only keys between A and D
move from B to D
= K/N of total keys
What is a virtual node?
A virtual node is one of many ring positions assigned to the same physical node.
package com.bank.sharding;
import java.util.*;
public class VirtualNodeHashRing {
private final TreeMap<Long, String> ring = new TreeMap<>();
private final int virtualNodes;
public VirtualNodeHashRing(int virtualNodes) {
this.virtualNodes = virtualNodes;
}
public void addNode(String physicalNode) {
for (int i = 0; i < virtualNodes; i++) {
long hash = hash(physicalNode + "#" + i);
ring.put(hash, physicalNode);
}
}
public void removeNode(String physicalNode) {
for (int i = 0; i < virtualNodes; i++) {
long hash = hash(physicalNode + "#" + i);
ring.remove(hash);
}
}
public String getNodeForKey(String key) {
long hash = hash(key);
Map.Entry<Long, String> entry = ring.ceilingEntry(hash);
if (entry == null) entry = ring.firstEntry();
return entry.getValue();
}
private long hash(String value) {
return value.hashCode() & 0xFFFFFFFFL;
}
}
With 150 virtual nodes per physical node, ownership is split into many small arcs that average out to an even share.
Why do virtual nodes improve balance?
With few points per node, one node can accidentally own a much larger slice of the ring.
Without virtual nodes (3 physical nodes): Node A: 45% of keys ◄── hotspot! Node B: 30% of keys Node C: 25% of keys With 150 virtual nodes per physical node: Node A: 33.2% of keys Node B: 33.5% of keys Node C: 33.3% of keys ◄── balanced!
Heterogeneous nodes can be weighted by giving bigger machines more virtual nodes.
How does consistent hashing enable replication?
Walk clockwise from the key's position to the next N distinct physical nodes for replicas.
Key K hashed to position 45° → Primary: Node A (next clockwise physical node) → Replica 1: Node B (next distinct physical node) → Replica 2: Node C (next distinct physical node)
This is how Cassandra places replicas automatically.
How does National Bank of India use consistent hashing?
Pankaj routes sharded accounts by account id on a consistent-hash ring.
package com.bank.sharding;
public class AccountRouter {
private final VirtualNodeHashRing ring;
public AccountRouter() {
ring = new VirtualNodeHashRing(150);
ring.addNode("shard-mumbai-1");
ring.addNode("shard-delhi-1");
ring.addNode("shard-bangalore-1");
}
public String getShardForAccount(long accountId) {
return ring.getNodeForKey(String.valueOf(accountId));
}
// Adding a new shard relocates only ~K/N accounts
public void addShard(String shardName) {
ring.addNode(shardName);
}
}
What should a senior engineer know?
- Consistent hashing underpins Dynamo-style stores, Cassandra, and many distributed caches.
- Pick enough virtual nodes to keep load variance low (100-200 per physical node is common).
- Use a good hash function (MurmurHash3, xxHash) to avoid clustering.
- Replication is free by walking to the next N distinct physical nodes.
- When removing a node, the departing node's keys redistribute to its clockwise neighbor.
Visual Overview
Consistent Hash Ring with Virtual Nodes:
0°
│
A#2 ─●── B#1
/ \
C#3 A#1
│ │
B#2 C#1
\ /
A#3 ─●── B#3
│
180°
A, B, C = physical nodes
A#1, A#2, A#3 = virtual nodes for A
Key K hashed to 45° ──▶ next clockwise = A#1 ──▶ physical Node A
Adding Node D:
Insert D#1, D#2, D#3 at their hash positions
Only keys in D's arcs move to D
All other keys stay put
Key Takeaway
Consistent hashing maps both keys and nodes onto a single circular hash space, and each key is owned by the first node found clockwise. The payoff is that adding or removing a node moves only the keys in that node's arc, about K/N of all keys, instead of the near-total reshuffle that modulo hashing causes when the node count changes.
A virtual node is one of many ring positions assigned to the same physical node. By giving each physical node 150 positions, its ownership is split into many small arcs that average out to an even share, preventing hotspots. Bigger machines can receive more virtual nodes for weighted assignment.
This is the technique behind Dynamo-style stores, Cassandra, and many distributed caches. It also gives replication for free by walking clockwise to the next few distinct physical nodes.
At the National Bank of India, Pankaj routes sharded accounts by account id on a consistent-hash ring with 150 virtual nodes per shard. Adding a shard relocates only the small fraction of accounts in the new shard's arcs rather than every account.
Remember one sentence: consistent hashing moves only K/N keys when nodes change, and virtual nodes give each physical node many ring spots for even balance.
---