Concepts
Consistent hashing
Intuition
Imagine a big clock face where every position stands for a possible piece of data, and each machine you own gets one or more spots on that clock. To find where a piece of data lives, you start at its spot and walk clockwise until you hit the first machine — that machine owns it. If you add or remove a machine, only the data between it and its neighbor moves; everything else on the clock stays exactly where it was. That's the whole trick: instead of a formula like "divide the data by the number of machines" (which reshuffles almost everything the moment the machine count changes), you place both data and machines on the same ring and let position decide ownership.
How it works
Consistent hashing arranges nodes on a logical ring by hashing each node's identifier (or, in Dynamo's case, multiple identifiers) into the same hash space used for keys. A key is assigned to the first node reached by walking clockwise from the key's own hash position. Because ownership is purely a function of ring position, adding or removing a node only affects the keys that fall between it and its immediate predecessor on the ring — the rest of the mapping is undisturbed, which is what keeps redistribution cost proportional to the size of the change rather than the size of the dataset. Dynamo builds replication directly on top of this: for a given key it walks clockwise from that key's position and replicates onto the next N-1 distinct physical nodes it finds, forming a "preference list" that any node can compute locally without asking a coordinator. To avoid uneven load from an unlucky random placement of a small number of physical nodes, Dynamo gives each physical machine multiple positions on the ring (virtual nodes), which smooths out load distribution and lets more powerful machines claim proportionally more of the ring by holding more tokens.
In practice
This is the partitioning scheme underneath Amazon's Dynamo and it was carried over almost directly into Apache Cassandra (co-created by a Dynamo author) and into Riak and Voldemort, all of which needed to add or remove capacity without triggering a full data reshuffle. Reach for consistent hashing whenever you're building a horizontally scalable store where nodes join and leave routinely and you cannot afford an operation that touches the entire dataset every time the cluster size changes; the virtual-node variant is what you add once you notice load is uneven across physical machines.
Use it in a design
Practice the cases that rely on this concept in the System Design school.