System Design Key Concepts
What hashing does for a distributed system
A distributed cache or database often holds more data than any single machine can store, so the data is split across many servers. That split is called sharding. The hard part is deciding which server owns a given piece of data. You need a rule that is deterministic, so every client computes the same answer, and cheap, so it can run on every read and write.
The obvious rule is to hash the key and take the remainder modulo the number of servers: server = hash(key) % N. Hashing turns an arbitrary key like user_100 into a number, and the modulo folds that number into the range 0 to N-1, which is exactly the set of server indices. With three servers, a key whose hash is 8 lands on server 2, and a key whose hash is 12 lands on server 0. As long as N stays at 3, every lookup is correct and the load spreads evenly.
What breaks when the server count changes
Servers do not stay put. They crash, which drops N, and you add capacity, which raises N. The trouble is that N sits in the denominator of every mapping, so changing it rewrites almost the entire table at once.
Take the key whose hash is 8. With three servers it maps to server 2, because 8 mod 3 is 2. Add a fourth server and the same key maps to server 0, because 8 mod 4 is 0. Nothing about the key changed, yet its home moved. Work through the whole keyspace and roughly three out of four keys end up on a different server after a single addition. Every one of those keys is now a cache miss that falls through to the database, so a routine scale-up turns into a stampede that can take the system down.
Consistent hashing and the hash ring
Consistent hashing keeps the same hash function but changes what you do with the result. Instead of folding the hash into N buckets, you map every hash onto a fixed circle, usually the range 0 to 2³² − 1 wrapped end to end. This circle is the hash ring.
Both servers and keys live on the ring. You hash a server's identifier, often its IP address, to place the server at a point on the circle. You hash a data key the same way to place the key at its own point. To find which server owns a key, start at the key and walk clockwise until you reach the first server. That server owns the key. Because the size of the ring never changes, adding or removing a server moves only the keys near that one server instead of rewriting the whole table.
Adding and removing servers
Suppose servers A, B, and C sit on the ring and you add server D, which hashes to a point between C and A. By the clockwise rule, the only keys affected are the ones that fall in the gap between C and D. Those keys used to walk clockwise past D's position to reach A, and now they stop at D instead. Every key owned by B, and every key still owned by A beyond D, stays exactly where it was.
On average a single change moves about K/N keys, where K is the total number of keys and N is the number of servers. Removing a server is the mirror image: its keys roll forward to the next server clockwise, and nothing else moves.
The clockwise rule is efficient, but placing each server at a single random point rarely divides the ring evenly. Hash three servers onto the circle and they can land close together, leaving one long stretch with no server in it. Whichever server sits at the clockwise end of that stretch inherits all of its keys. In a bad layout one server can own most of the ring while the others sit nearly idle, which recreates the very hotspot you were trying to avoid.
Virtual nodes
Virtual nodes fix the skew. Instead of hashing a physical server to one point, you hash it to many points, often a hundred or more, by appending a counter to its name and hashing each variant, such as ServerA#1, ServerA#2, and so on. Each of those virtual nodes is a separate position on the ring, and every one of them routes back to the same physical machine.
Scattering many small points per server averages out the randomness. A physical server's share of the ring becomes the sum of many small arcs spread all over the circle, so every server ends up with a near-equal portion of the load. When you add a machine, its virtual nodes drop into gaps all around the ring and pull a little work from many existing servers at once, which keeps the transfer smooth.
Fault tolerance and replication
Consistent hashing decides where a key lives, but on its own it keeps a single copy, so losing one server loses its data. Real systems pair the ring with replication. The first server clockwise from the key is the coordinator, and the system also stores copies on the next servers clockwise from it, skipping virtual nodes that map back to a machine already holding a copy. The ordered list of servers responsible for a key is its preference list.
With a replication factor of three, a key written to server A is also copied to B and C, the next two distinct servers clockwise. If A fails, a read for that key simply continues clockwise to B, which already holds the data, so the failure stays invisible to the client.
Where consistent hashing shows up
Consistent hashing underpins many large distributed systems:
- Amazon DynamoDB and Apache Cassandra partition data across nodes using a hash ring with virtual nodes, which lets them scale horizontally and replicate along the ring for availability.
- Content delivery networks such as Akamai spread cached objects across edge servers, so a single edge failure reroutes only its share of traffic to the next node instead of disrupting the whole fleet.
- Memcached client libraries often implement consistent hashing in the client, so adding or removing a cache server reshuffles only a fraction of keys rather than emptying the entire cache.
When to reach for it in an interview
Reach for consistent hashing when you are designing a stateful service that has to scale horizontally and whose membership changes often. A distributed cache, a key-value store, or a sharded database all fit, especially when nodes are added, lost, and replaced routinely and moving most of the data on every change would blow your latency budget.
It is the wrong tool for stateless load balancing. If you are spreading independent HTTP requests across interchangeable web servers, round robin or least-connections is simpler and works just as well, because there is no per-key state that has to stay on a particular machine.
Summary
Modulo hashing is simple but brittle: it ties every key's location to the server count, so changing that count reshuffles almost everything. Consistent hashing breaks that tie by placing keys and servers on a shared ring and assigning each key to the first server clockwise, which confines the damage of any single change to one server's neighborhood. Virtual nodes keep the distribution even, and replicating along the ring makes it fault tolerant. Together these turn a fragile mapping into the backbone of distributed data stores that scale out and survive failures without constant, disruptive data movement.