Skip to content

Load balancing & consistent hashing · 6 of 6

Step 1 · The pattern

One point each, uneven shares

Four cache servers sit on the hash ring from the last lesson, each at one point. A point is just a hash, so the gaps are uneven. Cache 3 sits behind a long arc and owns 40% of the keys. Caches 1 and 4 own 15% each.

  • lookup
  • served

In short

Virtual nodes & hot keys: how it works and how it breaks

A hash ring gives each key to the next server clockwise. If every server sits at one point, that point is just a hash, so the gaps between servers are uneven: a server behind a long arc owns far more keys than one behind a short arc. It gets worse when a server leaves. Its whole arc passes to the single next server, which may already be the busiest, and that server can fall over in turn. Virtual nodes fix both problems. Each server is hashed onto the ring many times, so it owns many small arcs. Many small random pieces add up to nearly equal shares, and a departing server's pieces are next to many different servers, so everyone inherits a little. Virtual nodes balance keys, not requests. One very popular key still lives on one server and needs a different tool.

How this comes up in interviews

"Your hash ring has one point per cache server. One server holds far more keys than the others and falls over when its neighbour is removed. Why, and what do you change?"

Then they ask

  1. Key shares are now even, but one key goes viral and takes a large share of reads. Do virtual nodes help? What does?
  2. How do you choose the number of points per server, and what does a larger number cost?
  3. Some servers have more memory than others. How do you give them a larger share, and what happens when you change it?

A strong answer covers

  • With one point per server the gaps between points are uneven, so a server behind a long arc owns far more keys.
  • When a server leaves, its whole arc passes to the single next server clockwise, which may already be the busiest and can fall over in turn.
  • Virtual nodes hash each server onto the ring many times, so it owns many small arcs that add up to nearly equal shares.
  • A departing server's points sit next to many different servers, so every survivor inherits a little.
  • They balance keys, not requests. A hot key still has one owner and needs copies under several names, a split, or a short-lived local copy.

Points to cover, not a script. Say them in your own words and tie them to a system you have worked on.

On one page: the track cheat sheet.

Last updated: Research paper

Diagrams are our own simulations: the timings, rates and counts in them are illustrative, not measurements. Captions are original wording.