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.
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.
