Consistent hashing changes how keys map to servers so that adding or removing a node moves as few
keys as possible: about 1/N instead of (N−1)/N.
Place both servers and keys on a circular hash space, 0 to 2³²−1. To find a key’s owner, hash the key to a position and walk clockwise to the first server you meet. Adding a server only steals keys from the segment immediately behind it. Removing one hands its segment to the next server clockwise. Everything else stays put.
With only a few servers, random ring positions produce lopsided segments. One server owns half the ring, another a sliver. The fix is to give each physical server many positions, typically 100–200 virtual nodes, so the law of averages flattens the load. More virtual nodes buy smoother balance and cost you a larger ring table.
Amazon DynamoDB and Apache Cassandra partition data this way. Discord uses it to route sessions, and CDNs like Akamai use it to pin content to edge caches. Any system that adds and removes nodes without reshuffling the whole dataset is leaning on consistent hashing.
Source: Alex Xu, System Design Interview Vol 1, Ch. 5
Answer to reveal the explanation. Nothing is scored.
1You route cache keys with hash(key) % N. One of 10 nodes dies. Roughly how many keys remap?
Changing N from 10 to 9 changes the modulo result for about (N−1)/N ≈ 90% of keys. They all miss cache at once and stampede the database.
2How does consistent hashing bound the damage when a node is added or removed?
Keys and servers share one hash ring. Adding or removing a node reassigns only the keys on the affected segment, about 1/N, not the whole keyspace.
3What problem do virtual nodes solve?
A handful of physical servers at random ring positions own arcs of very uneven size. Giving each server 100–200 virtual positions averages the load out.