The full picture
🎬 Consistent hashing: moving K/N keys instead of K
1 / 5Nodes and keys both hash onto one ring. A key belongs to the first node clockwise from it — so ownership is a property of the ring, not of the cluster size.
// Ring: hash -> physical node. Each node is placed at many points (vnodes).
private final NavigableMap<Long, String> ring = new TreeMap<>();
private static final int VNODES = 160;
void addNode(String node) {
for (int i = 0; i < VNODES; i++)
ring.put(hash(node + "#" + i), node); // many small arcs, not one big one
}
String nodeFor(String key) {
if (ring.isEmpty()) throw new IllegalStateException("empty ring");
Map.Entry<Long, String> e = ring.ceilingEntry(hash(key));
return (e != null ? e : ring.firstEntry()).getValue(); // wrap around the ring
}
// Removing a node deletes its VNODES entries; only those arcs are reassigned,
// and they scatter across all remaining nodes rather than landing on one neighbour.- Quantify the improvement — it's the whole point: with
% N, growing from 9 to 10 nodes remaps ~90% of keys; with consistent hashing, ~10%. For a cache that's the difference between a brief dip and a stampede that takes down the origin database. - Vnodes have a real cost: more ring metadata, more open connections, and range scans that were contiguous become fragmented across many small token ranges. Cassandra's default dropped from 256 to 16 tokens partly for this reason — a nice detail to know, and a reminder that defaults evolve with experience.
- Replication on the ring is 'walk clockwise and take the next N distinct physical nodes' — with rack/AZ awareness so the replicas don't all land in one failure domain. That last clause is what makes it production-grade rather than textbook.
- Alternatives worth naming: rendezvous hashing (highest-random-weight — pick the node maximizing
hash(key,node); simpler, naturally weighted, no ring to maintain) and jump consistent hash (tiny, fast, but only handles a shrinking/growing tail of buckets, so it can't express arbitrary removals). Mentioning rendezvous hashing signals real reading. - Fixed-partition assignment is the pragmatic alternative most databases actually use: create a large fixed number of partitions up front (Kafka topics, Elasticsearch shards, Riak's 256 vnodes) and move whole partitions between nodes. No hashing subtleties, trivially explicable rebalancing — the constraint is that the partition count is hard to change later.