Design a Distributed Cache (e.g. a Memcached/Redis-like system)
HardAsked at: Amazon, Meta, Google
Design the caching layer itself: a horizontally scalable key-value store that sits in front of a slower backing store, distributing keys across many cache nodes with minimal disruption as nodes are added/removed.
Request flow
Functional Requirements
- GET/SET/DELETE operations on arbitrary keys, with optional TTL.
- Automatically distribute keys across a cluster of cache nodes.
- Handle node additions/removals (scale-out, failure, maintenance) with minimal cache-wide disruption.
Non-Functional Requirements
- Extremely low latency (sub-millisecond) reads/writes.
- High throughput — this is meant to sit in the hot path in front of a slower DB.
- Even load distribution across nodes; graceful handling of hot keys.
- Availability favored over strict consistency — a cache is, by definition, a disposable/rebuildable copy of the source of truth.
Capacity Estimation
- Suppose we need to cache 500M hot keys at ~1KB average value size → ~500GB of data — spread across, say, 20 nodes with 32GB RAM each (leaving headroom for overhead), which is comfortably achievable.
- At 1M reads/sec fleet-wide across 20 nodes, that's 50,000 ops/sec per node — well within a single in-memory node's capability, confirming horizontal partitioning (not per-node optimization) is the main lever here.
Design Walkthrough
1. Partitioning keys across nodes
This is a direct application of consistent hashing: place both cache nodes and keys on a hash ring; each key is owned by the next node clockwise. When a node is added or removed, only the keys in the adjacent arc move, instead of a full reshuffle.
Use virtual nodes (each physical cache node gets many points on the ring) to keep load even, especially with a small number of physical nodes.
2. Client-side vs. proxy-based routing
Client-side (à la classic Memcached libraries): the client library itself knows the ring and computes which node owns a key, then talks to that node directly — lowest latency (no extra hop), but every client must embed and keep in sync a copy of the ring topology.
Proxy-based (à la Twemproxy/Envoy-style sidecars): clients always talk to a local proxy which knows the ring and forwards to the right backend node — simpler clients, centralizes ring-management logic, at the cost of one extra network hop.
3. Node failure & data loss
Because a cache is a rebuildable copy of the source of truth, the simplest and often correct answer is: on node failure, just let those keys miss and refill from the DB on next access (cache-aside) — no replication needed for correctness, only for performance/thundering-herd avoidance right after a failure.
If a stronger requirement exists (e.g. it's not purely a cache but also a session store where losing data logs users out), add replication: write each key to the next R nodes on the ring, and read from any one of them.
4. Eviction & memory management
Each node runs LRU (or LFU for skewed access patterns) locally to evict when memory is full — this is a per-node, in-memory concern independent of the cluster-wide partitioning scheme.
TTL expiry is handled per node, either lazily (check on access) or via a background sweep — lazy expiry is cheaper and is what most real caches default to.
Bottlenecks & Mitigations
- A single celebrity/hot key overwhelming one node despite even key distribution overall — mitigate by replicating just that hot key across several nodes and having clients pick one at random (a 'hot key splitting' technique).
- Ring topology changes (scale events) still cause some data movement and a temporary spike of cache misses against the backing store for the migrating keys — mitigate with gradual rebalancing and pre-warming.
Likely Follow-Up Questions
- How would you support atomic increment operations (e.g. a view counter) in a sharded cache? (Route the operation to the single owning node for that key and let it perform the increment locally/atomically — this is exactly why consistent hashing giving a deterministic single owner per key matters.)
- How would clients discover the current ring topology and get notified of changes? (A lightweight coordination service — e.g. ZooKeeper/etcd — holding the authoritative node list, with clients/proxies subscribing to changes.)
- How is this different from designing a distributed database? (A cache can drop data and rebuild from a source of truth, dramatically simplifying failure handling versus a database, which must never silently lose acknowledged writes.)