Что такое Consistent Hashing
Коротко:
Consistent Hashing — algorithm для distributing keys across nodes, где adding/removing node moves только ~1/N keys (не all). Базис distributed caches (Memcached, Redis Cluster), CDN (Akamai routing), DB sharding. Key insight: hash nodes и keys на circle (ring), key goes to closest node clockwise. Virtual nodes (vnodes) balance load.
Ниже: подробности, пример, смежные термины, FAQ.
Подробности
- Hash both keys and nodes на common space (e.g. SHA-1 → 0..2^160)
- Each key → closest node clockwise on ring
- Adding node: only keys between previous node и new одно reshuffle
- Virtual nodes: 1 physical node = 100-200 virtual points on ring → better balance
- Alternative: Rendezvous Hashing (simpler, comparable properties)
Пример
// 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 aroundСмежные термины
Больше по теме
Часто задаваемые вопросы
Где используется?
Redis Cluster (16384 slots), Memcached client-side sharding, DynamoDB partitioning, Cassandra, Akamai CDN, любые distributed caches.
Consistent Hashing vs Range Sharding?
Range — сортируется, easy range queries. Consistent — лучше balance, auto-reshuffle. Для large-scale — consistent.
Rendezvous hashing — лучше?
Rendezvous simpler, O(n) per lookup vs O(log n). Для small N — comparable. Для huge clusters — consistent hashing win.