A session cache sits on three shard nodes. The intern places every key with hash % n. Product ships. One node dies. n is now 2. Almost every remainder changes. The cache is cold. Every key remapped. Nobody chose a slow hash. They treated the node set as a fixed modulus.
Consistent hashing puts keys and nodes on a ring: a key belongs to the first node clockwise, so join or leave remaps only that arc — not every key. Virtual nodes (many points per physical node) keep the arcs from going lopsided.
This post is that ring. Families and the catalog live on the Algorithms Roadmap. The hash that maps a string to an int is the same family as Hash Tables — buckets and collisions live there. This page owns what happens when the set of buckets changes. It is not Raft, not two-phase commit, and not a rate limiter.
The job is remap a neighbor, not every key
hash % n is a fine lookup while n is frozen. It is a disaster as a rebalance. Change n and the remainder is a different function. Keys that never lived on the dead node still move. The cache dumps. The shard map reshuffles. You paid a full remap to remove one box.
Success is smaller: when a node joins or dies, only the keys that hashed into its slice should move. The other nodes keep their keys. The intern’s modulus cannot say that. A ring can.
The modulus is not the hash. The modulus is the placement. Hash Tables already owns how a key hits a bucket. Do not re-open HashMap here.
Note: A planned, empty-cache rebuild can still use % n. This procedure is for a live ring that must survive a join or a death without moving everything.
Hash keys and nodes onto a circle
Hash every node to a point on a circle. Hash every key to a point on the same circle. Walk clockwise from the key. The first node you hit owns it. Past the last point, wrap to the first — that is the circle.
In Java that walk is a TreeMap<Integer, String>: ceilingEntry(keyHash) for the least point at or after the key, and if that is null, firstEntry(). Equality on a point counts — a key that hashes exactly onto a node belongs to that node.
Add a node: insert its point. It steals only the keys on the arc that now ends at the new point (the slice its clockwise successor used to own). Remove a node: delete its point. Its keys fall to the next clockwise neighbor. Nobody else moves.
Do not rehash the whole keyspace because n changed. The ring never used n as a divisor.
A walk: three nodes, then B dies
Hash range 0–99 so the diagram fits; wrap is ceiling-or-first, not % n. Nodes A @ 10, B @ 40, C @ 70. Five keys.
clockwise: 10(A) → 40(B) → 70(C) → wrap to 10(A)
keys:
k1 15 ceiling 40 → B
k2 25 ceiling 40 → B
k3 45 ceiling 70 → C
k4 75 ceiling null → first 10 → A
k5 5 ceiling 10 → A
remove B @ 40:
k1 15 ceiling 70 → C moved B→C
k2 25 ceiling 70 → C moved B→C
k3 45 still C
k4 75 still A
k5 5 still A
only (10, 40] moved — the arc B owned.
same five keys, intern's hash % n (A=0, B=1, C=2):
15%3=0 A 25%3=1 B 45%3=0 A 75%3=0 A 5%3=2 C
C dies, n=2 (A=0, B=1):
15%2=1 B moved 25%2=1 B stay 45%2=1 B moved
75%2=1 B moved 5%2=1 B moved
four of five remapped. the stay was luck, not the algorithm.Join is the inverse. Add D @ 20 while B still lives: D takes (10, 20]. k1 moves B→D. The other four stay. That is the whole claim.
Virtual nodes even the arcs
One point per physical node is a gamble. Unlucky hashes put A @ 2, B @ 3, C @ 90. Then A owns (3, 90] — almost the ring. B owns a sliver. C owns the wrap. Load follows the arc, not the org chart.
Give each physical node many points (virtual nodes): same name, several small slices. Remove A and those slices go to different clockwise neighbors — you do not dump A’s entire load on one successor.
one point: A@2 B@3 C@90 A owns most of the ring
three each: A@10,41,73
B@22,55,88
C@34,67,96
each owns three short arcs; death scattersLibraries (Ketama-style rings, Cassandra-style tokens) pick a large v so the slices look even. This post does not ship a cluster. The procedure is: many points, one physical name.
Note: Two virtual points that hash to the same int overwrite in a TreeMap. Production hashes into a wide space so collisions are rare. Do not Math.abs a hashCode() to “fix” negatives — Integer.MIN_VALUE stays negative, and you just folded the space.
Java: TreeMap ceiling, wrap to first
There is no java.util.ConsistentHash. The ring is a sorted map of point → physical name. Empty ring throws; lookup is one ceiling and a wrap.
static final class Ring {
private final TreeMap<Integer, String> ring = new TreeMap<>();
void addPoint(int point, String node) {
ring.put(point, node);
}
void addNode(String node, int... points) {
for (int p : points) {
ring.put(p, node);
}
}
void removeNode(String node) {
ring.values().removeIf(node::equals);
}
String owner(int keyHash) {
if (ring.isEmpty()) {
throw new IllegalStateException("empty ring");
}
var e = ring.ceilingEntry(keyHash);
if (e == null) {
e = ring.firstEntry();
}
return e.getValue();
}
}The walk above is three addPoint calls, then owner for each key, then removeNode("B") and the same lookups. Virtual nodes are addNode("A", 10, 41, 73) — same method, more points, same owner.
Note: ceilingEntry includes equality. A key that lands on 40 belongs to whoever sits at 40. values().removeIf drops every virtual point for that physical name. Do not leave orphan points after a death.
Complexity
Let n be physical nodes, v virtual points per node, P = n·v points on the ring. Families and how to read a table live on the Algorithms Roadmap. This is the bill for the ring, not a second Big-O lecture.
| What | Cost | Why |
|---|---|---|
| Lookup / owner | O(log P) | TreeMap ceiling |
| Add or remove one point | O(log P) | tree insert or delete |
| Remove a physical node | O(P) | scan values, or O(v log P) if you stored that node’s points |
| Keys remapped on one join/leave | ~1/n of keys | only the successor arc(s) |
hash % n remap | nearly all keys | the divisor changed |
Expected share of a node is 1/n once virtual points mix the ring. Quote O(log P) for a lookup, not O(1) from the hash-table post. The hash picked the point; the tree found the owner.
One sorted ring, wrap on a missing ceiling, no JDK consistent-hash type. Rebuilding a hash % n table after every membership change is the wrong default once the cache is hot.
When not to use a ring
Skip this placement when the job is not “survive a join or a death without moving every key.”
nnever changes. A batch job with a frozen worker count can% nand go home. The ring earns its keep on a live membership.- You needed consensus. Raft and two-phase commit agree on a log or a commit. They do not place cache keys. Out of scope here.
- You needed a rate limit. Burst-then-average and smooth-drain are a different systems pair. Do not put tokens on this ring.
- You needed a product ring. Cassandra tokens and Ketama are deployments of this idea. This lab is the circle and the virtual points, not a cluster to run.
- You wanted a HashMap lecture. Buckets, collisions, and expected
O(1)already live on Hash Tables. - You wanted a crypto hash. Any mix that spreads points is enough for the lab. MD5-as-Ketama and SHA as a security topic are not this page.
Move few keys when membership changes — that is the job. Rate limits, leader election, and sketches are other Wave 7 procedures. Do not open those labs here.
Cheat sheet
Job: place keys so join/leave remaps one arc, not every key
Procedure: hash keys and nodes onto a circle; first node clockwise owns the key
Join/leave: only keys in the new/dead node's arc move (contrast hash % n)
Virtual: many points per physical node so arcs stay even
Lab: TreeMap<Integer,String>; ceilingEntry, else firstEntry
Time/space: O(log P) lookup for P points; space O(P)
JDK: TreeMap; no ConsistentHash class
Not this: Raft, 2PC, token/leaky bucket, Cassandra/Ketama as a product, HashMapDo:
- Hash both keys and nodes. Own the key at the first clockwise point (ceiling, then wrap).
- Remap only the successor arc when a node joins or dies. Leave everyone else’s keys.
- Use virtual nodes so one unlucky point cannot own half the ring.
- Use
TreeMap.ceilingEntry; wrap withfirstEntrywhen ceiling isnull.
Don’t:
- Place with
hash % non a live node set and act surprised when a death remaps everything. - Skip virtual nodes and debug “why is A at 90% CPU.”
- Re-teach buckets and collisions. Point at Hash Tables.
- Ship this sketch and call it Cassandra, Ketama, or a consensus protocol.
Wrap-up
Consistent hashing replaces hash % n with a circle: nodes are points, keys are points, a key belongs to the first node clockwise. A death remaps only the keys on that node’s arc; a join steals only the slice the new point now ends. Virtual nodes split the ring so load is many small arcs instead of one fat gamble. It is not a cluster product, not Raft, and not a rate limiter. Hash both, ceiling, wrap.
The intern’s modulus was a lookup for a frozen n. The procedure is this ring. When the job is allow a burst then enforce an average rate, that is token bucket — not this placement.