Что такое 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Смежные термины
Advantages of Consistent Hashing
Implementing Consistent Hashing
Consistent Hashing vs Other Load Balancing Techniques
Больше по теме
Часто задаваемые вопросы
Где используется?
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.
Запустить инструмент, который описан в этой статье
Бесплатный тариф — 20 мониторов, проверки раз в 5 минут, без карты. Платные тарифы — интервал от 1 минуты и проверки из нескольких регионов.