Specific problem that comes up with distributed caches and sharded databases
When using simple hash-based distribution
hash(key) % Nto pick which server stores data- Adding or removing a server changes
N - Almost every key maps to a different server, have to move most data around
Consistent hashing fixes this by arranging both servers and keys on a virtual ring
- Hash each key and place on the ring
- Key belongs to next server you encounter going clockwise
- When new server is added, only the keys between that new server and the previous server need to move
- When server is removed, only its keys relocate to the next server on the ring
- Everything else stays put
Improvement
- Simple modulo hasing
- Adding one server to a 10-server cluster means moving 90% of data
- Consistent hashing
- Only move 10% (keys that belong to affected range)
Use
- Distributed caches like Memcached and Redis Cluster use it to distribute keys across cache nodes
- Distributed databases like Cassandra and DynamoDB use it for sharding
- Some load balancers use it to assign requests to backend servers in a way that’s stable when servers come and go
- CDNs use it to route requests to edge servers
Interview
- Rarely need to explain how consistent hashing works unless asked
- Distributed cache
- Enough to say “We’ll use consistent hashing to distribute data across cache nodes”
- Database sharding
- Enough to say “We’ll use consistent hashing for the shard key”
- Bring up when discussing elastic scaling
- If system needs to add or remove cache nodes or database shards based on load, mention consistent hashing as mechanism that makes this practical without massive data movement