Consistent hashing vs rendezvous hashing

The decision

You have many keys and a changing set of servers, and you want a rule that says which server owns each key. A plain "hash mod N" moves almost every key when N changes. Consistent hashing puts servers and keys on a circle (the ring) and gives each key to the first server found moving forward from the key. Each server appears many times as virtual nodes, which are extra positions that even out the load. Rendezvous hashing, also called highest random weight, has no ring. For a key, it computes a score for every server, and the highest score wins. Both move only about 1/(N + 1) of the keys when the (N + 1)th server joins. They differ in lookup cost and evenness.

Choose consistent hashing (the ring) when

• You have hundreds of servers or more, and the lookup runs on every request. A lookup takes about log2(P) steps, where P is the number of positions.
• Servers own stored data and stream whole ranges when they join.
• You want replicas to be "the next distinct servers on the ring".

Choose rendezvous hashing when

• You have tens of servers, or up to a few hundred, and a lookup costs one hash per server.
• You want even load without tuning a number of virtual nodes.
• You want very little code. Every client with the same server list gets the same answer.
• You need the top k servers for a key (for replicas, or for a fallback when the first is down), because you sort by score.

The numbers that change the answer

Keys moved (calculation). Assumption: 100,000,000 keys, 10 servers, one server added.

• Hash mod N: 10 / 11 = 90.9% move = 90,909,091 keys.
• Ring or rendezvous: 1 / 11 = 9.1% move = 9,090,909 keys.

Evenness of the ring (calculation by simulation). With K random positions per server, the standard deviation of one server's share is about 1 / sqrt(K) of the average share. That is 10% for K = 100 and 3.2% for K = 1,000. My simulation of 10 servers gave 9.4% and 3.0%. With K = 1 it gave 90%, which is very uneven. For K = 100 the busiest server was on average 16% above the average share.

Evenness of rendezvous (calculation). Each key picks a server at random. Assumption: 100,000 keys, 10 servers. The relative spread of the load is sqrt((N - 1) / M) = sqrt(9 / 100,000) = 0.0095, which is 0.95%. A ring needs 1 / 0.0095 squared, which is about 11,000 virtual nodes per server, to match that.

When a server leaves (calculation). Assumption: 10 equal servers, 10% each.

• Ring with one position each: the next server takes all of it and doubles, from 10% to 20%.
• Ring with 100 virtual nodes, or rendezvous: the 10% spreads over 9 servers, 10 / 9 = 1.1 points each. Each goes from 10% to 11.1%.

Lookup cost (calculation). Assumptions: 1,000 servers, 1,000,000 lookups per second, one hash costs 50 ns, one binary search step costs 20 ns.

• Rendezvous: 1,000 hashes x 50 ns = 50,000 ns = 50 microseconds per lookup. At 1,000,000 per second that is 50 seconds of CPU per second = 50 cores.
• Ring with 100 virtual nodes: 100,000 positions, and log2(100,000) is about 17 steps. 17 x 20 ns = 340 ns per lookup, plus 50 ns to hash the key = 390 ns. At 1,000,000 per second that is 0.39 cores.
• With 20 servers, rendezvous costs 20 x 50 ns = 1 microsecond. That is fine.

So rendezvous is a poor fit for a hot path with many servers, and a good fit for small groups. A fix for big groups: hash each key into 1,024 fixed buckets. Run rendezvous for the buckets once per change of servers, and keep the result in a table. A lookup is then one table read.

Cited facts. Karger and others introduced consistent hashing in 1997, and a lookup can use binary search. Thaler and Ravishankar invented rendezvous hashing in 1996, and the basic version checks every server (see Sources).

What breaks with each choice

Ring.

• Too few virtual nodes gives uneven load, and a failure sends a whole range to one neighbour. Fallback: more virtual nodes, and watch the biggest server against the average.
• Ring changes must reach every client at about the same time. Two clients with different lists send the same key to different servers. Fallback: version the list, and let the old owner forward requests during a change.

Rendezvous.

• Lookup cost grows with the number of servers. Fallback: buckets plus a table, as above, or cache the answer.
• Adding a server needs every client to learn the new list. The same version fallback applies.

Both.

• A single hot key stays on one server. Hashing spreads keys, not requests for one key. Fallback: a copy of that key on several servers, or a short cache in front.

What it costs

• People. Rendezvous is about 10 lines of code. A ring with virtual nodes, versioning and tests is a small library. Assumption: 1 engineer-day against 1 to 2 engineer-weeks.
• Changing your mind. Moving between the two changes which server owns about every key. Treat it as a reshard: build a second table, copy data, switch, and keep the old one for a way back. Assumption: days for a cache, weeks for a database. A cache starts cold, so warm the new owners first.

How each level answers

SDE-1: Hash mod N moves almost all keys when N changes. Consistent hashing moves about 1 / N of them.

SDE-2: I use a ring with virtual nodes for a big cache cluster, because adding a node moves a small share. I use rendezvous for a small group, since it needs no tuning.

Senior: Going from 10 to 11 servers moves 9.1% of keys with either method, against 90.9% for mod. A ring needs about 100 virtual nodes for a 10% spread, and rendezvous gives about 1% with no tuning. But rendezvous with 1,000 servers at 1,000,000 lookups per second costs 50 cores, so I would bucket the keys first or use the ring. The failure is two clients with different server lists. The fallback is to version the list, and let the old owner forward requests.

Staff: The business cost here is a cache that goes cold: every moved key is a slow database read. So I ask who will run this, and I make the choice behind one shared library with a version number and a rollout tool. I choose the simpler method for small clusters. I plan the day the cluster grows past the point where lookup cost matters, and I switch then with a second table and a warm-up. I measure the keys moved per change, the biggest server against the average, and the cache hit rate after a change. If a normal scale-up keeps the hit rate above the target, the choice was right.

Say it in the interview

I would use rendezvous hashing for 20 cache servers. It moves 1 in 21 keys when we add one, gives even load with no tuning, and a lookup costs about 1 microsecond. At 1,000 servers and a million lookups per second, I would use a ring, or bucket the keys first. I would also version the server list.

Common mistakes

• Saying consistent hashing balances load by itself. With one position per server the spread is about 90 to 100%. You need virtual nodes.
• Saying either method fixes a hot key. They spread keys. A single key still lands on one server.
• Forgetting how clients learn about changes. A stale list sends keys to the wrong server and causes misses or duplicate data.

Sources

• Karger, Lehman, Leighton, Panigrahy, Levine and Lewin, "Consistent Hashing and Random Trees", ACM STOC 1997, DOI 10.1145/258533.258660 (the DOI was found through Wikipedia; the ACM page blocks automated checks). Summary of the idea, with the binary-search lookup and virtual nodes: https://en.wikipedia.org/wiki/Consistent_hashing (opens in a new tab) (checked 26 Oct 2026)
• Rendezvous hashing: invented by Thaler and Ravishankar at the University of Michigan in 1996; the basic lookup is linear in the number of servers; the top k servers can be chosen by score. https://en.wikipedia.org/wiki/Rendezvous_hashing (opens in a new tab) (checked 26 Oct 2026)
• The 1 / sqrt(K) spread is my own check, not a cited fact: a Python simulation of random points on a circle (1,000 to 4,000 runs for 10 servers; K = 100 and 1,000 on 10 and 100 servers matched 1 / sqrt(K) within 1 point).
• Server counts, key counts and times above are assumptions.