Consistent Hashing for Key-Value Stores
What you'll learn: How consistent hashing minimizes data movement when nodes join or leave a distributed key-value store cluster.
The Problem with Simple Partitioning
In the previous lesson, you learned that distributed key-value stores partition data across nodes. A naive approach uses hash(key) % N to decide which node stores a key, where N is the number of nodes. But what happens when you add or remove a node? Almost every key gets reassigned to a different node—a massive data shuffle.
How Consistent Hashing Works
Consistent hashing solves this by mapping both keys and nodes onto a conceptual ring (imagine a clock face numbered 0 to 2^160).
- Each node is assigned a position on the ring using a hash function
- Each key is also hashed to a position on the ring
- A key is stored on the first node found clockwise from the key's position
The magic: When you add a node, only keys between the new node and its predecessor need to move. When you remove a node, only that node's keys redistribute to its successor. Instead of reshuffling everything, consistent hashing limits movement to roughly 1/N of the data.
Virtual Nodes
Real implementations use "virtual nodes"—each physical server gets multiple positions on the ring. This ensures more even data distribution and prevents hotspots when the cluster is small.
Why This Matters
Redis Cluster, Amazon DynamoDB, and Apache Cassandra all use consistent hashing variants. Without it, scaling operations would cause massive disruptions as terabytes of data shuffle across the network.
Key Takeaway: Consistent hashing minimizes data movement during cluster changes by mapping keys and nodes to a ring structure, redistributing only the affected portion instead of rehashing everything.