Designing a Distributed Cache with Consistent Hashing and Virtual Nodes
This article explores the challenges of distributed caching, specifically focusing on achieving consistent data placement and minimizing key reshuffling when scaling a cache cluster. It proposes using consistent hashing with virtual nodes as a robust solution to address these issues, demonstrating its benefits over naive hash-modulo approaches.
Read original on Dev.to #architectureThe Challenge: Consistent Data Placement in Distributed Caches
When building distributed applications, a common problem is efficient data caching across multiple service instances. Naive in-process caches lead to stale data and wasted memory when scaling. While external caches like Redis solve the 'shared' aspect, the crucial architectural challenge remains: how to consistently map cache keys to specific nodes in a dynamic cluster, and minimize data movement when nodes are added or removed.
Consistent Hashing with Virtual Nodes
The core insight for robust distributed caching is consistent hashing with virtual nodes. Instead of assigning each physical server a single point on a hash ring, each server is given many 'virtual' points or tokens. When a key needs to be cached or retrieved, it's hashed to a position on the ring, and then a clockwise walk identifies the first virtual node. The physical server owning that virtual node becomes the key's designated home.
- Uniform Load Distribution: Many virtual nodes per server help spread the load evenly across the cluster, reducing the likelihood of hotspots.
- Minimal Reshuffling: Adding or removing a server only affects keys mapped to its specific virtual nodes. This significantly reduces the percentage of keys that need to be remapped and potentially re-cached, compared to simple modulo-based hashing.
- Scalability and Resilience: The approach allows for graceful scaling up or down of the cache cluster without major performance degradation due to mass cache invalidations.
Impact of Virtual Nodes
With a sufficient number of virtual nodes (e.g., 50-200 per physical host), adding a new server to a 5-node cluster could redistribute as little as 2% of the keys, whereas a naive hash-modulo approach might reshuffle 20% or more, leading to a temporary spike in cache misses and backend database load.
Implementation Details (Go Example)
type ring struct {
hashedKeys []uint32 // sorted list of hash values
hashMap map[uint32]string // map hash -> node name
vnodes int // number of virtual tokens per physical node
}
func NewRing(nodes []string, vnodes int) *ring { /* ... */ }
func (r *ring) nodeForKey(key string) string {
h := fnv.New32a()
h.Write([]byte(key))
keyHash := h.Sum32()
// binary search for the first token >= keyHash
idx := sort.Search(len(r.hashedKeys), func(i int) bool {
return r.hashedKeys[i] >= keyHash
})
if idx == len(r.hashedKeys) {
idx = 0 // wrap around
}
return r.hashMap[r.hashedKeys[idx]]
}The core implementation involves a sorted list of hash values representing the virtual nodes on the ring, and a map to link these hash values back to their physical node names. Key lookups are performed efficiently using binary search on the sorted list. This structure ensures that key assignments are consistent and remapping is localized to only the affected virtual node ranges upon cluster changes.