Concrete scenario
A cache fleet adds a node without wanting modulo hashing to remap most keys.
Mechanics
Place keys and weighted virtual nodes on a ring and route each key to its successor. Under uniform assumptions, adding one similarly weighted node moves an expected fraction near 1/(N+1), rather than the large fraction changed by modulo hashing.
Failure mode
A hot key remains hot, stale membership views route clients differently, and moved keys cause misses until warmed or replicated. Virtual nodes reduce expected skew but do not guarantee a fixed balance.
Trade-off
Consistent hashing limits topology-change movement and supports weighting, but requires membership distribution, replication, skew monitoring, and careful failure handling.
Worked example: modulo vs ring when adding a cache node
Suppose 10M cached keys sit on 10 nodes, and you add an 11th.
- hash(key) mod N: a key stays only if
h mod 10 == h mod 11, which holds for about 1 in 11 keys. So about 91% of keys (9.1M) move, and the cache hit rate collapses to about 9%. The database behind it absorbs a miss storm. - Consistent hashing: the new node takes over about 1/11 of the ring, so about 909k keys (9%) move, and hit rate dips only about 9 points.
How many virtual nodes?
With V virtual nodes per server, the standard deviation of load is roughly proportional to 1/sqrt(V).
| Vnodes per server | Approximate load spread (max vs mean) | Ring size for 10 servers |
|---|---|---|
| 1 | Often 2-3x the mean | 10 points |
| 10 | About 1.3-1.5x | 100 points |
| 100-256 | About 1.1x | 1,000-2,560 points |
Cassandra historically defaulted to 256 vnodes per node (num_tokens), and 4.0 changed the default to 16 with a smarter token allocator, trading perfect balance for faster repairs and streaming.
Lookup implementation
Store the vnode positions in a sorted array. To route a key, compute h = hash(key), binary-search for the first position at or after h, and wrap around to index 0 if past the end. That is O(log(N x V)), microseconds even for thousands of points. For replication, keep walking clockwise to collect the next R distinct physical nodes.
Alternatives
- Rendezvous (HRW) hashing: score every node with hash(key, node) and pick the highest. Also minimal movement, no ring to maintain, O(N) per lookup.
- Jump consistent hash (Google): no memory and perfectly balanced, but nodes can only be added or removed at the end. Good for numbered shards.
- Fixed slots: Redis Cluster uses 16,384 hash slots assigned to nodes, which is simpler and explicit to rebalance.
- Bounded loads (Google, Vimeo): consistent hashing with a capacity cap per node to limit hot-node overload.