TL;DR
Consistent hashing maps both keys and servers onto a hash ring. When a server is added or removed, only the keys that fall between that server and its predecessor need to move — not all keys. Virtual nodes distribute load evenly when physical servers are few.
Why consistent hashing exists, how virtual nodes work, and a full Go implementation with benchmarks against modulo hashing.In this post, I'll walk through the key concepts with code examples drawn from real production implementations.
The Problem with Modulo Hashing
With N servers, assigning a key to server (hash(key) % N) works fine until N changes. Add or remove one server and N changes — now almost every key maps to a different server. For a cache, this means a near-complete cache miss storm on every scaling event.
The Hash Ring
Consistent hashing places both servers and keys on a conceptual ring of hash values from 0 to 2^32. A key is assigned to the first server encountered when traveling clockwise around the ring. Adding a server only affects the keys between the new server and its predecessor — all other keys remain assigned to the same servers.
Virtual Nodes
With few physical servers, the ring may be unevenly divided — one server handles 60% of keys, another handles 5%. Virtual nodes solve this: each physical server is mapped to multiple positions on the ring (e.g., server A → positions A-1, A-2, A-3, ..., A-150). With enough virtual nodes, load distribution becomes statistically uniform.
type ConsistentHash struct { replicas int ring map[uint32]string // ring position → server sorted []uint32 // sorted ring positions mu sync.RWMutex}func New(replicas int) *ConsistentHash { return &ConsistentHash{replicas: replicas, ring: make(map[uint32]string)}}func (c *ConsistentHash) hashKey(key string) uint32 { h := fnv.New32a() h.Write([]byte(key)) return h.Sum32()}func (c *ConsistentHash) Add(server string) { c.mu.Lock() defer c.mu.Unlock() for i := 0; i < c.replicas; i++ { pos := c.hashKey(fmt.Sprintf("%s-%d", server, i)) c.ring[pos] = server c.sorted = append(c.sorted, pos) } sort.Slice(c.sorted, func(i, j int) bool { return c.sorted[i] < c.sorted[j] })}func (c *ConsistentHash) Remove(server string) { c.mu.Lock() defer c.mu.Unlock() for i := 0; i < c.replicas; i++ { pos := c.hashKey(fmt.Sprintf("%s-%d", server, i)) delete(c.ring, pos) } // Rebuild sorted slice (filter deleted positions) newSorted := c.sorted[:0] for _, pos := range c.sorted { if _, ok := c.ring[pos]; ok { newSorted = append(newSorted, pos) } } c.sorted = newSorted}func (c *ConsistentHash) Get(key string) string { c.mu.RLock() defer c.mu.RUnlock() if len(c.ring) == 0 { return "" } pos := c.hashKey(key) // Binary search for the first ring position >= pos idx := sort.Search(len(c.sorted), func(i int) bool { return c.sorted[i] >= pos }) if idx == len(c.sorted) { idx = 0 // wrap around the ring } return c.ring[c.sorted[idx]]}Modulo vs Consistent: Key Redistribution
| Scenario | Modulo (% N) | Consistent (150 vnodes) |
|---|---|---|
| Add 1 server (4 → 5) | ~80% keys remapped | ~20% keys remapped |
| Remove 1 server (4 → 3) | ~75% keys remapped | ~25% keys remapped |
| Node failure | Full remap | Only successor takes over |
Real-World Usage
Cassandra, DynamoDB, Riak, and Memcached all use consistent hashing for shard assignment. Cassandra uses virtual nodes as "token ranges" — each physical node owns several non-contiguous token ranges, so adding a node redistributes from multiple predecessors simultaneously, spreading the rebalancing load.
When not to use it
Consistent hashing adds complexity for no benefit if you have a small, stable set of servers that rarely changes. A simple modulo hash or range partition is easier to reason about and operationally simpler when the shard count is fixed.