Consistent Hashing
You'll learn how consistent hashing minimizes data movement when scaling key-value stores up or down.
The Problem with Naive Hashing
In a key-value store with multiple nodes, you might naively distribute keys using node = hash(key) % number_of_nodes. This works—until you add or remove a node. Suddenly, the modulo changes, and almost every key maps to a different node, forcing massive data migration.
How Consistent Hashing Works
Consistent hashing maps both keys and nodes onto the same circular hash space (imagine a clock face from 0 to 2³²-1). Each node claims responsibility for the range of hash values between itself and the previous node on the ring.
When a key needs storage, you hash it, find its position on the ring, and walk clockwise to the nearest node.
Why It Minimizes Movement
Adding a node: Only keys in the range between the new node and its predecessor need to move—just one node's worth of data.
Removing a node: Only that node's keys move to its successor. All other keys stay put.
With naive hashing, adding the 4th node to a 3-node cluster remaps ~75% of keys. With consistent hashing, only ~25% move (roughly 1/N where N is the new total).
The Ring Analogy
Think of a circular parking lot where cars (keys) park at the first available spot clockwise from their assigned number. Adding a new parking attendant (node) only affects cars between the new attendant and the previous one—everyone else stays parked.
Key Takeaway: Consistent hashing places keys and nodes on a shared hash ring, ensuring that adding or removing nodes only redistributes keys from immediate neighbors, typically affecting just 1/N of the data instead of nearly all of it.