Part 7 of 8 · 3 min read
A complete walk-through
One example from setup to server failure, with numbers.
A complete walk-through
Think of putting everything together on a single small cache cluster and following it through a day.
Set-up. A cache cluster of 4 servers, each with 100 virtual nodes, 400 points on a ring of 2 to the power 32. The client library hashes each key and looks up the owner among the 400 points, using a sorted list and a binary search. A lookup for 400 points needs about 9 comparisons (log base 2 of 400 is about 8.6).
Normal day. 40,000 requests a second, spread evenly with a standard deviation of 10 percent: each server about 10,000 a second, between 9,000 and 11,000. The hit ratio is 95 percent, so the database sees 2,000 reads a second.
Server 3 fails.
- Clients notice failed connections and remove server 3's 100 virtual nodes from their ring.
- Its keys (25 percent of the key space) are now owned by servers 0, 1, 2, roughly a third each.
- The 75 percent of keys that were on servers 0 to 2 do not move. They keep their hits.
- The 25 percent that moved miss once each, then fill on their new owner. At the moment of failure, the hit ratio drops from 95 percent to about 0.75 × 95 + 0.25 × 0 = 71 percent, and the database load jumps from 2,000 to 40,000 × 0.29 = 11,600 reads a second, for a short time. As keys refill, it returns to about 2,000.
- Each of the three servers now carries about 13,333 requests a second.
Compare with hash mod N: N goes 4 to 3 and about 75 percent of keys move, so the hit ratio would fall to about 0.25 × 95 = 24 percent, and the database load to 40,000 × 0.76 = 30,400 reads a second, nearly three times worse than the ring.
Server 3 returns. Its virtual nodes are added back. It takes back its 25 percent from the three neighbours (about 8 percent from each). Those keys miss once on the returning server (which has an empty cache), then refill.
Ideas to soften the jump: warm the new server before it takes traffic; keep a short-lived second copy on the next server of the ring; limit the database with load shedding (Level 3, module 4).
Interview angle
Answer in your head first, then open it.
How do you spread keys over servers so that adding a server does not reshuffle everything?
Consistent hashing: servers and keys on a ring, the key goes clockwise to the first server. Only about 1 ÷ n of keys move.
What are virtual nodes?
Many ring positions per server. They even the load, spread a failure over many servers, and give bigger machines a bigger share. Give 100 to 200 as the usual range.
What happens when a node fails?
Its virtual nodes leave the ring and its keys go to the clockwise neighbours. Others keep their keys. Quote the miss spike and how to limit the database.
How do you place replicas?
Walk clockwise and take the next N distinct servers, preferably in different data centres.
Do databases use it?
Dynamo and Cassandra do, in forms of it. Many databases prefer fixed or dynamic partitions. Say why.
Check yourself:
- With 5 servers and a ring, one fails. About what share of keys move?
- With hash mod N and the same failure, about what share moves?
Words you will meet
| Word | Plain meaning |
|---|---|
| Rehashing problem | hash mod N moves most keys when N changes |
| Consistent hashing | Assigning keys so that few move when servers change |
| Hash space | The range of values a hash function can give |
| Hash ring | The hash space bent into a circle |
| Clockwise lookup | Walking forward from a key to the first server |
| Affected range | The stretch of ring whose keys move when a server joins or leaves |
| Virtual node | One of many ring positions that stand for one real server |
| Heterogeneity | Servers of different sizes taking shares to match their capacity |
| Standard deviation | A measure of how far values spread from the average |
| Replica walk | Choosing the next N distinct servers clockwise to hold copies |