80%
of keys move when 4 servers become 5
Grow a cache from four nodes to five on a sale morning, and most reads fall through to the database. Only 20% had to move.
Hash servers and keys onto one ring. Walk clockwise.
A key belongs to the first server at or after its position. Every client with the server list gets the same answer, with no lookup service.
Server E joins between A and B. Mod N would move 80% of keys. The ring?
The trick
Only (A, E] moves, from B to E, about 1/(N + 1). Nothing moves between old servers.
One token each: one server holds 27.8%. With 256, none tops 11%.
Give each server many positions, node-3#0 to node-3#255. Its share becomes many small arcs, and the spread shrinks like 1/√V.
Who takes a dead server’s keys?
Bad: One token
One neighbour takes its whole arc, and may fall over too, a cascade.
Good: 256 tokens
All 9 survivors share it, 8–13% of its keys each.
Dynamo, Cassandra: copies on the next distinct servers
- First server clockwise coordinates the key
- Walk on, skipping servers already listed
- Stop at N distinct servers, the preference list
- Next in line covers a down replica
IPL final: one live-score key takes 10% of all requests. Add virtual nodes?
The catch
No. The ring balances keys, not traffic; that key still has one owner. Cache it locally or split it.
Remember
Hash nodes and keys onto one ring; a key goes to the first node clockwise. A join moves only its arc. Virtual nodes even the load; replicas take the next distinct nodes.