Skip to content
Consistent Hashing and Random Trees 3 min

David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy · STOC 1997

Consistent Hashing and Random Trees

The 1997 idea that lets servers join and leave while moving only a few keys. Play with a hash ring and compare it with hash mod N.

Read the original paper

Algorithms · Yellow Belt · Pro · 3 min read

Consistent Hashing and Random Trees

Suppose you spread data over ten cache servers by computing hash(key) mod 10. It works nicely until the day you add an eleventh server. Now every key must be recomputed as mod 11, and almost all of them land on a different server. Every cache suddenly misses, and the databases behind them get flooded.

In 1997, a group of MIT researchers described a fix in a paper about relieving hot spots on the World Wide Web, the moments when a popular page gets far more requests than one server can handle. Their tool, consistent hashing, changed how almost every large caching and storage system spreads data.

Hash both servers and keys onto a circle. A key belongs to the first server clockwise from it. When a server joins or leaves, only the keys in one arc of the circle move, about 1 in N of them, instead of nearly all.

The problem with hash mod N

Ordinary hashing spreads keys evenly when the number of buckets never changes. The paper points out that on the Web the set of caches does change, and different clients may not even agree on which caches exist. Plain hashing breaks as soon as clients disagree, because changing the count changes almost every answer.

The authors want a hash scheme that is consistent: when buckets are added or removed, as few items as possible should change buckets.

The ring

Imagine the possible hash values laid out on a circle. Pick a hash function and use it twice: once to place each server on the circle, and once to place each key. To find where a key lives, start at its position and walk clockwise until you meet a server.

The ring. Servers (large colored dots) and keys (small circles) are both hashed to positions on a circle. A key is stored on the next server clockwise from its position.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 1 more diagram and 2 interactive elements to play with

  • The four properties
  • Where this shows up

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.