Consistent hash ring
On the roadmap:Intermediate · step 3: Sharding
Route keys to nodes so that adding or removing a node moves only a small share of the keys.
In plain words
A way to decide which server owns which key, so that when a server joins or leaves, only a small slice of keys has to move instead of almost all of them.
Why it matters
With 'key mod number of servers', adding one server reshuffles nearly everything. A ring keeps most keys where they are, which is what makes growing a cache or database cluster safe.
Where you meet it
- Dynamo-style databases and Cassandra
- Cache clusters and client libraries that spread keys over many cache servers
- CDNs and load balancers that need the same user to reach the same server
You will be able to
- Explain why simple modulo hashing breaks when servers change
- Use virtual nodes to spread keys evenly
- Find the owner of a key with a binary search
In interviews
One of the most asked building blocks: distributed cache, sharded database, load balancing with sticky sessions.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- A 32-bit string hash with good mixing
- A ring of virtual nodes sorted by position
- Binary search with wrap-around to find the owner of a key
- add() and remove() for nodes
/** FNV-1a followed by a murmur-style finaliser, so similar strings land far apart. */
export function hash(s: string): number {
let h = 0x811c9dc5;
for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35); h ^= h >>> 16;
return h >>> 0;
}
export class HashRing {
private ring: { pos: number; node: string }[] = [];
constructor(private vnodes = 100) {}
add(node: string): void {
for (let k = 0; k < this.vnodes; k++) this.ring.push({ pos: hash(`${node}#${k}`), node });
this.ring.sort((a, b) => a.pos - b.pos);
}
remove(node: string): void {
this.ring = this.ring.filter((e) => e.node !== node);
}
/** First virtual node at or after the key's position, wrapping to the start. */
get(key: string): string | undefined {
if (this.ring.length === 0) return undefined;
const h = hash(key);
let lo = 0, hi = this.ring.length;
while (lo < hi) { const mid = (lo + hi) >> 1; if (this.ring[mid].pos < h) lo = mid + 1; else hi = mid; }
return this.ring[lo % this.ring.length].node;
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints consistent-hash-ring ok when everything passes. You need Node.js installed.
mkdir consistent-hash-ring && cd consistent-hash-ring
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Virtual nodes, as here, are standard. Production also weights them by machine size, so a bigger server owns more of the ring.
- To survive a failure, a key is stored on the next several distinct nodes around the ring, not just the first.
- A plain ring can still overload one node. Variants such as consistent hashing with bounded loads, rendezvous hashing and Maglev exist to even this out.
Ways to decide which server owns a key
| When a server is added or removed | Balance | Cost | Pick it when | |
|---|---|---|---|---|
| Consistent hash ring | Only about 1/N of the keys move | Even with enough virtual nodes | A sorted ring in memory, a binary search per lookup | Servers join and leave often, as in caches and sharded databases |
| Hash mod N | Almost every key moves | Perfectly even | One line of code | The number of servers never changes |
| Rendezvous hashing | Only about 1/N of the keys move | Very even | A score computed for every server on each lookup | The server count is small and you want simple code |
| Lookup table or directory | Whatever you decide | Whatever you decide | A table that must be kept in sync everywhere | You need full control over where data lives |
What it cannot do
Uneven without virtual nodes
With one point per server the split is lumpy. Many points per server smooth it out.
It does not see load
A very popular key still lands on one server, however even the ring is.
Replication needs its own rule
To keep copies, each key is also stored on the next few servers around the ring.
Everyone must agree on the members
If two clients disagree on which servers exist, they will send the same key to different places.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Return N distinct nodes for replication
- Weight nodes by capacity using different virtual node counts
- Measure how evenly keys spread as virtual nodes change