Skip to content
A Fast, Minimal Memory, Consistent Hash Algorithm 4 min

John Lamping, Eric Veach · arXiv (Google) 2014

A Fast, Minimal Memory, Consistent Hash Algorithm

Google's five line consistent hash: no memory, balanced buckets, and only the keys that must move do move. Add buckets and watch which keys jump.

Read the original paper

Algorithms · White Belt · Pro · 4 min read

A Fast, Minimal Memory, Consistent Hash Algorithm

Imagine a database split into shards, each on its own server. To find a key, you compute which shard owns it. That is easy. The hard part comes when you add a server. If the rule changes, most keys now point at a different shard, and nearly all your data has to move.

Consistent hashing solves this by changing the rule so that only a small share of keys move. Two Google engineers, John Lamping and Eric Veach, published a version of it in 2014 that fits in about five lines of code and needs no memory at all. The paper is short, and the trick inside it is delightful.

Jump consistent hash maps a 64 bit key to one of n buckets so that keys spread evenly, and when you add a bucket, only the keys that belong in the new one move. It needs no tables, runs in logarithmic time, and the whole algorithm is a short loop. The catch: buckets are numbered 0 to n minus 1, so you can only add or remove the last one.

What a good split looks like

A plain remainder, key mod n, spreads keys evenly. But it moves a lot of data when n changes. The paper's example is growing from 10 shards to 12. Balanced data over 12 shards only needs one sixth of the data to move. A remainder rule moves far more.

Adding shards with a plain remainder (key mod number of shards) reshuffles most of the data. A consistent hash moves only the share that has to move: 2 of 12 shards' worth, which is one sixth.

The paper names the two properties that matter for data storage. Balance: keys are spread evenly among buckets. Monotonicity: when buckets are added, keys only move from old buckets to new ones, never between old ones. The classic ring based method by Karger and colleagues gives both, but it needs memory for every bucket. To get an even spread it used about 1,000 points per bucket, for a standard deviation of 3.2% in the number of keys per bucket.

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 trick: compute when a key jumps
  • What you give 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.