Design a Distributed Cache: Consistent Hashing, Replication, and Failure Modes

You've scaled your database to 10 replicas and it's still melting under read load. The classic fix? A distributed cache. But slap a Redis cluster in front without understanding the internals, and you'll trade one fire for another—I've seen a misconfigured cache take down a payments service at 3am because of a thundering herd. Here's what everyone gets wrong: a distributed cache isn't just a faster hashmap. It's a distributed system with all the attendant failure modes—partitioning, replication lag, split-brain, and cascading failures. By the end of this, you'll design a cache that survives node failures, handles hot keys, and doesn't amplify load on your database. You'll know exactly when to use consistent hashing vs. a lookup service, how to pick replication factor, and what to do when your cache cluster goes split-brain.

Why You Can't Just Use a Hashmap: Partitioning Strategies

A single-node cache is trivial—just a hashmap with eviction. But when your dataset exceeds one machine's RAM, you must partition. The naive approach: hash(key) % N. Works until you add or remove a node—then almost every key remaps, causing a cache stampede. I've seen this bring down a social media feed service when they scaled from 5 to 6 nodes. The fix: consistent hashing. It maps keys to a ring of hash values; each node owns a range. Adding a node only remaps a fraction of keys. But consistent hashing has its own gotcha: uneven load if nodes are few. Solution: virtual nodes—each real node appears multiple times on the ring. This spreads keys more evenly. Here's a minimal implementation in Go:

// io.thecodeforge — System Design tutorial

package cache

import (
	"hash/crc32"
	"sort"
	"strconv"
)

type ConsistentHash struct {
	keys       []int          // sorted list of hash values
	hashMap    map[int]string // hash -> node ID
	replicas   int            // virtual nodes per real node
}

func NewConsistentHash(replicas int) *ConsistentHash {
	return &ConsistentHash{
		hashMap:  make(map[int]string),
		replicas: replicas,
	}
}

func (c *ConsistentHash) AddNode(nodeID string) {
	for i := 0; i < c.replicas; i++ {
		// Create virtual node key: "nodeID:i"
		vKey := nodeID + ":" + strconv.Itoa(i)
		hash := int(crc32.ChecksumIEEE([]byte(vKey)))
		c.keys = append(c.keys, hash)
		c.hashMap[hash] = nodeID
	}
	sort.Ints(c.keys)
}

func (c *ConsistentHash) GetNode(key string) string {
	if len(c.keys) == 0 {
		return ""
	}
	hash := int(crc32.ChecksumIEEE([]byte(key)))
	// Binary search for first hash >= key hash
	idx := sort.Search(len(c.keys), func(i int) bool { return c.keys[i] >= hash })
	if idx == len(c.keys) {
		idx = 0 // wrap around
	}
	return c.hashMap[c.keys[idx]]
}

Replication: How to Survive a Node Failure Without a Stampede

Partitioning alone is fragile. If a node dies, all its keys are gone. The database gets hammered. The naive fix: replicate each key to N nodes. But how? Write-through: write to all replicas synchronously—slower but consistent. Write-behind: write to one, async replicate—faster but risk data loss. In production, I use a quorum-based approach: write to W replicas, read from R replicas, with W+R > N. This gives tunable consistency. For a cache, eventual consistency is usually fine—set TTL and accept stale reads. But watch out: if you read from a replica that hasn't received the write yet, you get stale data. The fix: read-repair—on read, if a replica has a stale version, update it. Or just accept staleness within TTL. Here's a simple replication layer:

// io.thecodeforge — System Design tutorial

package cache

import (
	"sync"
	"time"
)

type CacheEntry struct {
	Value     string
	ExpiresAt time.Time
}

type ReplicatedCache struct {
	mu       sync.RWMutex
	data     map[string]CacheEntry
	replicas []*ReplicatedCache // other nodes (simplified)
	local    bool               // true for this node
}

func (c *ReplicatedCache) Get(key string) (string, bool) {
	c.mu.RLock()
	entry, ok := c.data[key]
	c.mu.RUnlock()
	if !ok || time.Now().After(entry.ExpiresAt) {
		return "", false
	}
	return entry.Value, true
}

func (c *ReplicatedCache) Set(key, value string, ttl time.Duration) {
	c.mu.Lock()
	c.data[key] = CacheEntry{Value: value, ExpiresAt: time.Now().Add(ttl)}
	c.mu.Unlock()
	// Async replicate to all replicas
	for _, r := range c.replicas {
		go r.setRemote(key, value, ttl)
	}
}

func (c *ReplicatedCache) setRemote(key, value string, ttl time.Duration) {
	c.mu.Lock()
	c.data[key] = CacheEntry{Value: value, ExpiresAt: time.Now().Add(ttl)}
	c.mu.Unlock()
}

Failure Detection and Cluster Membership: Gossip vs. Central Coordinator

How does a node know another node is dead? Polling a central coordinator (like ZooKeeper) is simple but creates a single point of failure and a bottleneck. Gossip protocols (like SWIM) are decentralized: each node periodically pings a random peer. If no response, it asks others to confirm. After a quorum of confirmations, the node is marked dead. I've used both. For caches under 50 nodes, a coordinator is fine—just make sure it's replicated. For larger clusters, gossip scales better. But gossip has a gotcha: false positives due to network hiccups. Use a suspicion mechanism: before declaring dead, wait for multiple rounds. Here's a minimal gossip failure detector:

// io.thecodeforge — System Design tutorial

package cache

import (
	"math/rand"
	"sync"
	"time"
)

type Node struct {
	ID      string
	Alive   bool
	mu      sync.Mutex
	members map[string]*Node
}

func (n *Node) StartGossip(interval time.Duration) {
	ticker := time.NewTicker(interval)
	go func() {
		for range ticker.C {
			n.gossipRound()
		}
	}()
}

func (n *Node) gossipRound() {
	// Pick a random member
	var target *Node
	n.mu.Lock()
	for _, m := range n.members {
		if m.ID != n.ID {
			target = m
			break
		}
	}
	n.mu.Unlock()
	if target == nil {
		return
	}
	// Ping target
	if !target.ping() {
		// Ask others to confirm
		n.mu.Lock()
		confirmations := 0
		for _, m := range n.members {
			if m.ID != n.ID && m.ID != target.ID {
				if !m.ping() {
					confirmations++
				}
			}
		}
		n.mu.Unlock()
		if confirmations >= 2 { // quorum
			target.mu.Lock()
			target.Alive = false
			target.mu.Unlock()
		}
	}
}

func (n *Node) ping() bool {
	// Simulate network call
	time.Sleep(time.Millisecond * 10)
	return n.Alive
}

Cache Eviction Policies: LRU, TTL, and the Thundering Herd

When memory fills, something must go. LRU evicts the least recently used key. But under a thundering herd—many requests for the same missing key—LRU can evict other hot keys, causing cascading misses. The fix: TTL-based eviction with random early expiration. Set a TTL and a jitter (e.g., TTL ± 10%). This spreads re-fetches over time. Also, use a 'lock around the cache' pattern: when a key is missing, only one request fetches from the database; others wait. Here's a Go implementation:

// io.thecodeforge — System Design tutorial

package cache

import (
	"sync"
	"time"
)

type Cache struct {
	mu    sync.Mutex
	data  map[string]string
	ttl   time.Duration
	locks map[string]chan struct{} // per-key lock
}

func (c *Cache) GetOrFetch(key string, fetch func() (string, error)) (string, error) {
	c.mu.Lock()
	if val, ok := c.data[key]; ok {
		c.mu.Unlock()
		return val, nil
	}
	// Key missing: check if another goroutine is already fetching
	if ch, ok := c.locks[key]; ok {
		c.mu.Unlock()
		<-ch // wait for fetch to complete
		c.mu.Lock()
		val := c.data[key]
		c.mu.Unlock()
		return val, nil
	}
	// This goroutine will fetch
	ch := make(chan struct{})
	c.locks[key] = ch
	c.mu.Unlock()

	val, err := fetch()
	if err != nil {
		c.mu.Lock()
		delete(c.locks, key)
		c.mu.Unlock()
		return "", err
	}
	c.mu.Lock()
	c.data[key] = val
	close(ch) // signal waiters
	delete(c.locks, key)
	// Set TTL with jitter
	time.AfterFunc(c.ttl+time.Duration(rand.Intn(int(c.ttl/10))), func() {
		c.mu.Lock()
		delete(c.data, key)
		c.mu.Unlock()
	})
	c.mu.Unlock()
	return val, nil
}

Consistency Models: When Stale Data Is Fine (and When It's Not)

Caches are inherently stale—that's the trade-off for speed. But how stale? Eventual consistency: after a write, all replicas converge eventually. Strong consistency: all replicas see the write before any read returns. For a cache, strong consistency kills performance—you'd need synchronous replication and quorum reads. In practice, most caches use eventual consistency with a TTL. But if you're caching user sessions or inventory counts, stale data can cause real bugs. The fix: use a version number or timestamp. On read, check if the cached version is newer than a threshold. If not, fetch from source. Here's a versioned cache:

// io.thecodeforge — System Design tutorial

package cache

type VersionedEntry struct {
	Value   string
	Version int64
}

type VersionedCache struct {
	data map[string]VersionedEntry
}

func (c *VersionedCache) Get(key string, minVersion int64) (string, bool) {
	entry, ok := c.data[key]
	if !ok || entry.Version < minVersion {
		return "", false
	}
	return entry.Value, true
}

func (c *VersionedCache) Set(key, value string, version int64) {
	c.data[key] = VersionedEntry{Value: value, Version: version}
}

When Not to Use a Distributed Cache

Distributed caches add complexity: network latency, consistency headaches, operational overhead. If your dataset fits in one machine's RAM, use an in-process cache (e.g., sync.Map in Go, ConcurrentHashMap in Java). If your read rate is low, a database with proper indexing is simpler. If you need strong consistency, a cache is the wrong tool—use a database with read replicas. I've seen teams add Redis to a 2-server setup and then spend weeks debugging split-brain. Don't be that team. Start simple, measure, then add a cache only when you have a proven bottleneck.

Interview Questions That Actually Get Asked

In system design interviews, you'll be asked to design a cache like Redis or Memcached. Expect these: 'How does consistent hashing handle node additions?' 'How would you replicate data across data centers?' 'What happens when a cache node fails and all requests go to the database?' 'How do you prevent a thundering herd?' 'When would you use a write-through vs write-behind cache?' The key is to discuss trade-offs: consistency vs. availability, latency vs. throughput, simplicity vs. scalability. Show you've thought about failure modes.