Requirements
- Serve hot data from memory across many nodes.
- Scale capacity by adding nodes without reshuffling everything.
- Handle node failures gracefully.
High level design
Keys are distributed by consistent hashing, and clients route directly to the owning node.
- Sharding: consistent hashing maps each key to a node so clients know where to look.
- Eviction: each node bounds its memory and evicts with a policy such as least recently used.
- Write strategy: write through keeps the cache and database in sync, while write back batches updates for speed.
Bottlenecks
- Hot keys: one popular key overloads its node, so replicate hot keys across several nodes.
- Resize churn: adding nodes should move few keys, which consistent hashing with virtual nodes provides.
- Stale data: caches drift from the source, so set time to live values and invalidate on writes.
A cache miss falls through to the backing store and populates the cache on the way back.
Key idea
A distributed cache uses consistent hashing to shard keys across in memory nodes, with eviction, replication of hot keys, and invalidation keeping it fast and fresh.