Consistent Hashing — Part 2: Internals & Implementation

maang.io System Design Series

What is this?

Back to the circular hotel lobby. In Part 1 the concierges stood at a few fixed spots and each served the guests who reached them going clockwise. Elegant — but if you only have four concierges and you drop them at random points around a big rim, you'll get unlucky: one concierge ends up owning a huge sweep of the lobby while another owns a sliver. The average is fine; any single arrangement can be lopsided.

The fix a real hotel would use: give each concierge many name badges and have them stand at many points around the rim at once — concierge A is at 12 o'clock and 4 o'clock and 9 o'clock, and so on. Now the lobby is chopped into lots of small arcs, the luck averages out, and every concierge ends up with roughly the same share. Those extra standing-points are virtual nodes, and they're the single most important internal idea in this chapter — the thing that turns the pretty Part 1 diagram into something you'd actually run in production.

The one-line idea: A physical server isn't one point on the ring — it's many points (virtual nodes). Scattering each server across the ring in dozens or hundreds of small arcs makes the load statistically even, and makes a server's departure spill smoothly onto many neighbors instead of dumping everything on one. Virtual nodes are what make consistent hashing balanced and graceful.

Let's open up the data structure first, then earn the virtual-node claim with real numbers.