Design a Distributed Cache (like Redis/Memcached)

• Distributed cache : an in-memory key-value store spread across many nodes that serves hot data at microsecond latency to reduce load on slower backing databases.
• Consistent hashing : distributes keys across nodes on a ring so adding or removing a node remaps only about 1/N of the keys.
• Eviction : removing data under memory pressure using policies like LRU (least-recently-used) or LFU (least-frequently-used).
• Write-through : updates cache and database together for consistency.
• Write-behind : writes to cache immediately and flushes to the database asynchronously for speed.
• Cache stampede : when a popular key expires and many requests miss simultaneously, all hitting the database; prevented with single-flight locks.

What is a distributed cache?

A distributed cache is an in-memory key-value store spread across many nodes that serves hot data at microsecond latency and shields a slower database from the flood of reads. It sits between the application and the database, absorbing the read load for frequently accessed data.

How does consistent hashing distribute keys?

Consistent hashing places both cache nodes and keys on a conceptual ring. A key is stored on the first node clockwise from its hash. When a node is added or removed, only the keys between it and its neighbour move, roughly 1/N of all keys, instead of remapping everything. Virtual nodes smooth out uneven distribution.

package com.bank.cache;

import java.util.TreeMap;

public class ConsistentHashRing {
    private final TreeMap<Integer, String> ring = new TreeMap<>();

    public String nodeFor(String key) {
        int hash = key.hashCode();
        var entry = ring.ceilingEntry(hash);  // first node >= key hash
        return (entry != null ? entry : ring.firstEntry()).getValue();
    }

    public void addNode(String node, int vnodes) {
        for (int i = 0; i < vnodes; i++)
            ring.put((node + "#" + i).hashCode(), node);
    }
}

How do eviction policies work?

Eviction decides what to drop when memory is full. LRU evicts the entry untouched for the longest time, which suits workloads with temporal locality. LFU evicts the entry accessed the fewest times, which suits workloads where some keys are permanently hot. A TTL expires entries after a fixed duration regardless of access.

package com.bank.cache;

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LruCache(int capacity) {
        super(capacity, 0.75f, true); // access-order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // evict least-recently-used
    }
}

What are the write policies?

Write-through writes to the cache and the database together on every write, so the cache is always consistent. Write-behind writes to the cache immediately and flushes to the database asynchronously, which is faster but risks losing recent writes if a node crashes before flushing.

package com.bank.cache;

import java.math.BigDecimal;

public class WritePolicies {
    // Write-through: safe for balances
    public void writeThrough(String key, BigDecimal value) {
        database.save(key, value);   // durable first
        cache.put(key, value);       // then cache reflects it
    }

    // Write-behind: fast for counters, NOT for money
    public void writeBehind(String key, long count) {
        cache.put(key, count);       // fast in-memory update
        asyncQueue.enqueue(key);     // DB write happens later
    }
}

How does cache invalidation keep data fresh?

TTL-based invalidation expires entries after a fixed duration so stale data self-heals, but allows brief staleness. Event-based invalidation deletes or updates the cache entry the instant the underlying data changes, which is precise and what I use for banking balances.

package com.bank.cache;

public class InvalidationStrategies {
    // TTL: simple, bounded staleness
    public void putWithTtl(String key, String value) {
        cache.put(key, value, Duration.ofSeconds(60));
    }

    // Event-based: precise, no staleness
    public void onTransferCompleted(String accountId) {
        cache.delete(accountId);  // next read reloads fresh from DB
    }
}

How do you prevent cache stampede?

Cache stampede happens when a very popular key expires and thousands of requests simultaneously miss the cache and hit the database. Prevention uses a single-flight lock so only one request rebuilds the value while others wait, plus staggered or probabilistic early expiration.

package com.bank.cache;

public class StampedeProtection {
    public String getProtected(String key) {
        String value = cache.get(key);
        if (value != null) return value;

        if (lock.tryLock(key)) {
            try {
                value = database.load(key);  // ONE DB call
                cache.put(key, value);
                return value;
            } finally { lock.unlock(key); }
        }
        return waitForCachePopulation(key); // others wait
    }
}

What should a senior engineer know?

In banking, lean toward write-through and event-based invalidation for anything resembling a balance. Accept slightly slower writes in exchange for never serving a wrong number. Combine strategies: cache-aside reads, write-through writes, event-based invalidation for correctness, and stampede protection on the hottest keys like interest rates.

What are common cache implementations?

Redis is the most popular, offering data structures beyond simple key-value (sorted sets, streams, pub/sub). Memcached is simpler and faster for pure key-value workloads. In AWS, ElastiCache provides managed Redis and Memcached clusters.