What is Consistent Hashing
Consistent Hashing — algorithm for distributing keys across nodes where adding/removing a node moves only ~1/N of keys (not all). Basis of distributed caches (Memcached, Redis Cluster), CDN (Akamai routing), DB sharding. Key insight: hash both nodes and keys onto a circle (ring); key goes to the closest node clockwise. Virtual nodes (vnodes) balance load.
Below: details, example, related terms, FAQ.
Details
- Hash both keys and nodes in common space (e.g. SHA-1 → 0..2^160)
- Each key → closest node clockwise on ring
- Adding a node: only keys between previous and new node reshuffle
- Virtual nodes: 1 physical node = 100-200 virtual points on ring → better balance
- Alternative: Rendezvous Hashing (simpler, comparable properties)
Example
// Pseudocode
function nodeForKey(key, ring):
h = hash(key)
for node in ring sorted by hash:
if hash(node) >= h: return node
return ring[0] // wrap aroundRelated Terms
Learn more
Frequently Asked Questions
Where is it used?
Redis Cluster (16384 slots), Memcached client-side sharding, DynamoDB partitioning, Cassandra, Akamai CDN, any distributed caches.
Consistent Hashing vs Range Sharding?
Range — sorted, easy range queries. Consistent — better balance, auto-reshuffle. For large-scale — consistent.
Is Rendezvous hashing better?
Rendezvous is simpler, O(n) per lookup vs O(log n). For small N — comparable. For huge clusters — consistent hashing wins.