Consistent Hashing
Consistent hashing maps both data keys and servers onto a circular hash space so that adding or removing a server only redistributes a minimal fraction of keys, unlike traditional modular hashing which reshuffles nearly everything.
In traditional hashing (hash(key) % N), adding or removing a server changes N and remaps almost every key. Consistent hashing places servers and keys on a hash ring (0 to 2^32). Each key is assigned to the next server clockwise on the ring. When a server is added, only keys between the new server and its predecessor move. When removed, only that server's keys shift to the next server. With virtual nodes (each physical server maps to 100-200 points on the ring), load distribution becomes uniform. Used by DynamoDB, Cassandra, Akamai CDN, and memcached.
Tradeoffs
Strengths
- Minimal key redistribution when adding/removing servers (~K/N keys move vs ~K keys with modular hashing)
- Virtual nodes provide near-uniform load distribution
- Enables elastic scaling of caches, databases, and CDNs
- Simple to implement and reason about
Weaknesses
- More complex than simple modular hashing
- Virtual nodes increase memory overhead (ring metadata)
- Hot keys can still overload a single server regardless of hashing scheme
- Rebalancing during node additions still causes some cache misses
When to Use
- Distributed caches (memcached, Redis cluster)
- Database sharding where servers are added/removed dynamically
- CDN request routing
- Any system where minimizing redistribution during scaling is critical
When NOT to Use
- Single-server systems
- Systems with fixed, unchanging server counts (modular hashing is simpler)
- When all data fits in one node
Likely Follow-Up Questions
- How do virtual nodes improve load distribution?
- What happens to data when a node fails in a consistent hashing ring?
- How does consistent hashing enable replication in systems like DynamoDB?
- What's the difference between consistent hashing and rendezvous hashing?
- How would you handle hot keys in a consistent hashing scheme?
Related Concepts
Source: editorial — Based on Karger et al. 1997, DynamoDB paper, and Google Jump Consistent Hash paper