Consistent Hashing
What you'll learn: How consistent hashing minimizes data reshuffling when adding or removing shards in a distributed system.
The Problem with Simple Hash-Based Partitioning
In traditional hash-based partitioning (Lesson 2687), you might map a key to a shard using hash(key) % N where N is the number of shards. This works, but there's a major issue: when you add or remove a shard, N changes, and suddenly almost every key maps to a different shard. Imagine needing to move 90% of your data just to add one new server—painful!
The Hash Ring Structure
Consistent hashing solves this by organizing shards on a conceptual hash ring (a circular space from 0 to 2³²-1, for example). Instead of mapping keys directly to shard numbers, both keys and shards are hashed to positions on this ring.
Here's how it works:
- Hash each shard to one or more positions on the ring
- Hash each data key to a position on the ring
- Walk clockwise from the key's position until you hit a shard—that's where the data lives
Analogy: Imagine a circular clock face. Your servers are placed at various hour marks, and each piece of data is assigned to "the next server clockwise from where it lands."
Why This Minimizes Movement
When you add a new shard, it only "captures" keys that would have belonged to the next clockwise shard—typically just 1/N of the total data. Similarly, removing a shard only affects its keys, which get redistributed to the next shard. Most keys stay exactly where they are.
Key Takeaway: Consistent hashing uses a hash ring structure to ensure that adding or removing shards moves only O(K/N) keys on average (where K is total keys and N is total shards), rather than rehashing the entire dataset.