The Ring Needs a Thousand Points

When you spread keys over servers with hash(key) mod n, adding one server moves almost every key: going from 100 to 101 servers moved 99% of them in my runs, a hundred times the 1% that has to move. Consistent hashing is the family of schemes that move only that 1%. There are several, and they're usually compared on paper. I measured six of them on two things: how lopsided the busiest server gets, and how many keys move when a server joins or leaves, compared with the minimum.

The short version: the classic hash ring is badly lopsided unless you give each server hundreds to thousands of points, and the exact amount follows a clean formula. Rendezvous and jump hashing are as even as random assignment and move exactly the minimum. Maglev, Google's table-based scheme, moved 1.5 to 6.6 times the minimum. Capping each server's load works, but it costs extra moves unless you also use many points.

The schemes

• Ring (Karger et al., 1997): each server hashes to v points on a circle; a key goes to the next point clockwise. Lookups are a binary search.
• Rendezvous (Thaler and Ravishankar, 1996): score every server against the key and take the highest. Even and minimal, but a lookup touches every server.
• Jump (Lamping and Veach, 2014): a few lines of arithmetic that pick a bucket from 0 to n−1 in about ln n steps, with no table at all. The catch is that buckets are numbered, so you can only add or remove the last one.
• Maglev (Eisenbud et al., 2016): each server walks its own pseudo-random permutation of a lookup table, and they take turns claiming slots until the table is full. A lookup is one array read.
• Bounded loads (Mirrokni, Thorup and Zadimoghaddam, 2018): a ring where no server may hold more than c times the average; a key whose server is full keeps walking clockwise. HAProxy ships it as hash-balance-factor.

Every run used a million random keys with 10, 100 or 1,000 servers and 20 seeds per setting, about 1,600 runs in all. "Keys moved" compares the assignment before and after one server joins (or a random one leaves) with the minimum: the newcomer's fair share, or the departed server's own keys.

The ring is lopsided, exactly as predicted

With one point per server, the busiest of 100 servers carried 5.3 times the average load; of 1,000 servers, 7.2 times. Arc lengths between random points on a circle are far from equal, and the busiest server is the one that drew the longest arc.

This has an exact answer. With v random points per server, the shares of the circle follow a Dirichlet distribution with every parameter equal to v, so the busiest server's load is the largest of n Gamma(v) draws divided by their mean. The dashed curves are that formula, computed numerically; 30 of the 33 simulated settings are within two standard errors of them and the rest within three. A good back-of-the-envelope version is 1 + √(2 ln n / v): for 16 or more points it was within 7% of the measured value. Flip it around and you get the points you need: about 2 ln n / ε² to keep the busiest server within 1 + ε of average. For 100 servers and 10% that's about 900 points each, and 1,024 points measured 1.08×.

Busiest server's share of the ring divided by the average share, mean of 20 seeds.

Sixteen points per server is a common setting (it's Cassandra's default since 4.0), and with random placement it leaves the busiest of 100 servers at 1.67 times average. Cassandra pairs it with an allocator that places new points deliberately rather than at random, which is the right fix; random placement at 16 points isn't good enough.

More points stop helping at some point, because the keys themselves are random too. With 1,000 keys per server, even perfectly random assignment leaves the busiest server at about 1.10× average, and the ring reaches that at about 1,000 points per server. Past roughly as many points as each server has keys, you're paying memory for nothing.

Points also decide who inherits a dead server's keys. With one point, all of them land on a single neighbor, which doubles that neighbor's load. With 16 points, they spread over about 15 servers; with 256 points over 91 of the remaining 99.

Rendezvous and jump are as good as it gets

Both hit the floor set by key randomness: the busiest of 100 servers held 1.026× and 1.024× average against a random-assignment benchmark of 1.025×, and adding a server moved 0.995× and 1.006× the minimum. On balance and movement there is nothing left to improve. The costs are elsewhere. Rendezvous scores every server on every lookup: at 1,000 servers a run took 5.4 seconds against 0.3 for jump. Jump can't remove an arbitrary server, only the last bucket, so it suits numbered shards rather than a pool of machines that fail at random.

Maglev trades movement for speed

Maglev's table spread keys as evenly as rendezvous did. But adding a server to 100 moved 1.55 times the minimum with its usual 65,537-slot table, and going from 1,000 to 1,001 servers with a 100,003-slot table moved 6.6 times the minimum: 0.66% of all keys instead of 0.1%. Removing a server moved about the same. When the server list changes, the turn-taking that fills the table plays out differently from the start, so slots change hands between servers that were never involved.

A bigger table helps. For 100 servers, a 10,007-slot table moved 2.6× the minimum, 65,537 moved 1.55× and 655,373 moved 1.14×. Small tables are worse: at 1,009 slots, ten per server, a join moved 4.4× the minimum. Maglev is built for packet load balancers, where a lookup must be one memory read and a few extra moved connections are tolerable; that's a sensible trade, but it is a trade.

A load cap costs moves unless you have points

The bounded-loads ring does what it promises: the busiest server never exceeded the cap. The price shows up on change. Keys that overflow a full server spill onto its neighbors, and when the server count changes, the cap changes with it and the spills land differently. I modeled it as reassigning the keys in a fixed order after each change.

Keys moved when a 101st server joins, as a multiple of the minimum. 20 seeds each; values under 1 are the newcomer drawing less than its fair share. From 1.5 up with 100 points, and from 2 up with 16, the cap is never reached.

With one point per server the ring is so uneven that a tight cap is reached constantly, and a 1.25× cap moved 6.9 times the minimum. With 100 points the ring is already within about 1.27×, so the same cap almost never bites and costs 1.05×; even a 1.1× cap costs only 1.23×. Points do the bulk of the balancing, and the cap trims the tail.

What I'd use

• Numbered shards that only grow or shrink at the end: jump. Even, minimal and no memory.
• A few dozen to a few hundred servers that come and go: rendezvous. A lookup over 100 servers is cheap, and you get the best possible balance and movement.
• A ring: give it at least 2 ln n / ε² points per server for the evenness you want, or place points deliberately. If you also need a hard cap, add bounded loads on top of the points, not instead of them.
• Maglev when lookup speed is everything, with the biggest table you can afford, knowing that changes move several times the minimum.

Limits: uniform random keys with equal weights and equal-capacity servers, so this is the best case for every scheme; skewed key popularity adds its own imbalance on top. Maglev and the bounded-loads ring are my JavaScript implementations from the papers' descriptions, and the load cap is applied by reassigning in a fixed order, not to live traffic. Jump uses a different per-key random generator than the paper, with the same distribution.