Design a Distributed Cache

We are designing a Distributed Cache. You are the candidate and I am the interviewer.

The Product Service reads product p_42 tens of thousands of times per second. The Product database can answer every request, but a 20 ms database round trip consumes a connection, CPU, and I/O every time. Most callers would accept a copy that is a few seconds old.

Putting that copy in memory changes the common path:

Without cache                         With a cache hit

Product Service                       Product Service
      │                                     │
      ▼                                     ▼
Source DB: ~20 ms                      Cache: 1–2 ms
                                            │ miss only
                                            ▼
                                       Source DB

The gain is not merely 18 ms. At a high hit rate, repeated work leaves the database. The new dependency can also fail, return stale bytes, evict a popular key, or send a million simultaneous misses into Product DB.

That is the real interview problem:

How do we make repeated reads fast without letting disposable memory become a new source of truth or a new way to overload the database?

Before drawing a cluster, I would ask the questions that change the answer.

1. Clarify the contract

I would start with one question at a time:

• Is the cache the source of truth, or is the database?
• Which operations are required: GET, PUT, DELETE?
• Do entries expire with a TTL?
• What happens when a node runs out of memory?
• Are values opaque bytes or typed objects?
• How large are keys and values, and how many hot keys exist?
• Must a write be visible on every replica immediately?
• Can we lose cache data and refill from the database?
• Are clients in one region?

If the interviewer does not answer, I would state assumptions and invite challenge:

Role                       Internal remote in-memory key-value cache
Source of truth            Product DB; cache is disposable derived state
Core operations            GET, PUT, DELETE
Optional operations        MGET/MPUT, compare-and-set, increment
TTL                        seconds to hours; every entry is evictable
Consistency                bounded staleness and misses are acceptable
Durability                 not required; data can be rebuilt from DB
Clients                    same-region application services
Keys                       opaque strings, bounded length
Values                     opaque bytes; average ~1 KB; max ~1 MB
Scale example              100 million keys; ~10 million requests/second peak
Latency goal               p50 1–2 ms; p99 under 10 ms at the client boundary
Availability goal          approximately 99.99% useful responses
Excluded                   transactions, scans, queries, pub/sub
Also excluded              treating this cache as a lock service by default

These are planning numbers, not hardware promises. Key popularity, value-size mix, TLS, reconnect storms, and node loss can invalidate a neat spreadsheet. We must benchmark representative workloads.

The most important assumption is ownership:

Product DB owns p_42.
The cache owns only a temporary copy.
A miss means "no usable copy here," not "the product does not exist."
A timeout is not a miss.

If we later need a session store that must survive a node crash, or a lock service that must not grant two owners, those are different products. Calling them “cache” does not make their correctness cheaper.

2. Requirements, retention, and edge cases

Functional requirements

The service should:

1. Get a key and optionally get many independent keys.
2. Put bytes with an optional TTL.
3. Delete a key.
4. Expire entries whose TTL has passed.
5. Evict entries when a node is out of memory.
6. Route a key to the node that currently owns it.
7. Survive individual node loss without becoming a database incident.

Atomic increment and compare-and-set are useful but optional. They operate on one key. They do not create a database transaction.

Non-functional goals

Read latency         p50 near 1–2 ms; p99 < 10 ms, same-region client boundary
Throughput           millions of GETs/second with headroom for skew
Availability         useful responses even when some nodes fail
Scalability          add or remove nodes while moving only a subset of keys
Memory efficiency    metadata and fragmentation are part of capacity
Fault tolerance      a node crash is a miss spike, not a correctness bug
Consistency          eventual / bounded stale is acceptable for product copies

The latency target includes client pooling and network time, not only a hash-table lookup. A lookup may take microseconds while a saturated connection pool waits milliseconds.

Edge cases to keep in mind

• Two clients put the same key concurrently.
• A client times out after a successful put and retries.
• A popular key expires and 100,000 requests miss together.
• An attacker requests random keys that never exist.
• Millions of keys share nearly the same TTL.
• One celebrity key receives hundreds of thousands of GETs/second.
• A node is added or removed while traffic continues.
• The client has a stale view of cluster membership.
• The entire cache cluster is down while Product DB is already busy.
• A replica is behind the primary after failover.

3. Estimate scale before choosing nodes

Use round numbers that expose the bottleneck. An interviewer may propose:

Keys                              100 million
Average value                     1 KB
Peak requests                     10 million/second
Read/write mix                    roughly 10:1
Replication                       one replica

Raw data is not RAM

100,000,000 × 1 KB ≈ 100 GB of values

That 100 GB does not fit in 100 GB of RAM. Each entry also stores:

key bytes                         ~40 B
value                             1,024 B
TTL, version, flags, size         ~40 B
hash-table slot / pointers        ~24 B
allocator / fragmentation         often 15–30%

A plausible in-memory size is about 1.3–1.5 KB per 1 KB value:

100 GB values × 1.35               ≈ 135 GB primary
One replica                        × 2  ≈ 270 GB
30% operational headroom           / 0.70 ≈ 385 GB provisioned RAM

The multiplier is deliberately a range. Slab size classes, load factor, large values, and deleted-entry churn dominate it. Measure bytes per live item after churn.

Throughput may bind before bytes

Ten million requests/second is a different problem from 100 GB. If 90% are GETs:

Peak GET                           ≈ 9,000,000/s
Peak PUT/DELETE                    ≈ 1,000,000/s
Response payload at 1 KB           ≈ 9 GB/s before headers and TLS

If a node can sustain perhaps 200,000–400,000 GETs/second at the target tail latency after TLS, pooling, and eviction work, QPS implies tens of nodes even when memory would fit on fewer machines. Hot keys make averages meaningless: one key can saturate one node while the rest are idle.

A realistic first cluster might therefore be sized for the worse of memory, QPS, NIC, and one-zone loss, then load-tested. 100 GB and 10M QPS are interview-scale illustrations, not a purchase order.

Peak matters more than average. A 4× daily peak, a deploy, or a celebrity event can turn a comfortable average into a database incident.

4. Start with one machine

Do not begin with a hash ring. Begin with the smallest design that works:

Product Service
      │
      ▼
Single-node cache
      │ miss
      ▼
Product DB

How would you implement the cache on one machine?

A hash table, often called a HashMap, maps a key to an entry:

HashMap<Key, Entry>

Entry
-----
key
value
expires_at
size
optional version

GET hashes the key, finds the bucket, compares key bytes, checks TTL, and returns the value. Average time is O(1). PUT and DELETE are also O(1) on average.

Hashing only narrows the search to a bucket. Different keys can collide, so the implementation still compares key bytes—or a fingerprint plus key bytes—before returning data. A collision must slow the lookup, not return the wrong product.

This design is excellent until memory fills, the process restarts, or the machine dies. Those three limits create the rest of the interview.

5. Run out of memory: local eviction

What happens when the cache is full?

TTL removes entries that the caller declared stale. It does not protect a node that is storing too many still-valid entries. We need an eviction policy: a rule for which live entry to drop so a new one can enter.

Common choices:

LRU, least recently used, is the interview default because recency is a decent proxy for “will be read again soon.”

LRU with a HashMap and a doubly linked list

A HashMap alone cannot evict the oldest used key in O(1). Scanning every entry is O(n). The standard combination is:

HashMap:  key → pointer to list node
List:     most recently used  ↔  ...  ↔  least recently used

GET p_42
  1. map lookup → node
  2. detach node from the list
  3. attach it at the MRU end
  4. return value

PUT p_42 when full
  1. if key exists, update and move to MRU
  2. else insert at MRU
  3. if over capacity, remove the LRU tail
  4. delete that tail key from the map

The map gives O(1) lookup. The doubly linked list gives O(1) removal and promotion because each node already knows its neighbors. Expected complexity:

GET, PUT, DELETE, Evict → O(1) average

Exact global LRU on a huge multithreaded table is a scalability trap: every hit mutates shared ordering. Production nodes often use approximate LRU, sampled candidates, or sharded lists. The interview structure still matters: each cache node runs its own local eviction. We do not maintain one globally synchronized LRU list across the cluster. Recency is a per-node memory decision, not a cluster-wide consensus problem.

LFU or TinyLFU-style admission can retain repeatedly popular keys better than pure recency when scans pollute LRU. Start with LRU, then measure.

6. Why one server is not enough

Why can’t one cache server handle the entire workload?

Memory     385 GB does not fit one typical application box
CPU        10M QPS exceeds one event loop / core set
NIC        9 GB/s of useful payload saturates a single 25–100 GbE path
Restart    emptying 100 million keys creates a DB storm
Failure    one process is one availability domain

We add nodes:

Node 1    Node 2    Node 3    Node 4

The new question is not “how do we store a key?” It is:

Which node should contain product:p_42?

7. Naive partitioning: hash(key) % N

The first attempt is modulo hashing:

node = hash(key) % N

Example:

hash("product:p_42") % 4 = 2
→ Node 2

While N is fixed, this distributes keys reasonably. Then we add Node 5 because memory or QPS grew:

hash(key) % 4     versus     hash(key) % 5

Changing the divisor remaps most keys. Roughly (N-1)/N of keys choose a new remainder. The cluster looks empty. Almost every GET misses. Product DB receives a near-total cache-miss spike.

That is the concrete problem consistent hashing exists to solve. We do not introduce it because it is a famous diagram. We introduce it because hash % N makes membership change a full-cache flush.

8. Consistent hashing

Imagine the output of a hash function as a circle. That circle is the hash ring.

Place both nodes and keys on the same circle:

                 Node A
                    ●
              /           \
             /             \
         Node D             Node B
             \             /
              \           /
                 Node C

A key belongs to the next node clockwise. If hash("product:p_42") lands just after Node A, the owner is Node B:

hash("product:p_42")
        ↓
       key
        ●
        ↓ clockwise
      Node B

When we add Node E between A and B, Node E takes only the keys on the arc that previously ended at B. The other arcs do not move.

Before:  (A → B] owned by B
After:   (A → E] owned by E
         (E → B] owned by B

Contrast:

hash % N              almost all keys remap when N changes
consistent hashing    only keys on the affected arc remap

If we have 100 nodes and add one, on the order of 1/100 of keys should move, not 99%. The database still sees extra misses on the moving slice. That is recoverable. A full remap is not.

Lookups walk the ring to the successor. In code this is usually a sorted token array plus binary search, not a literal circle.

Replicas, if we add them later, can be the next distinct nodes clockwise, skipping the same rack or zone. The ring is a placement function. It is not yet a durability guarantee.

9. Virtual nodes: make the ring less lumpy

One physical node, one ring position is rarely even:

Node A owns a huge arc
Node C owns a tiny arc

Uneven arcs mean uneven memory, uneven QPS, and hot nodes. Hash quality helps, but a handful of points on a circle still cluster.

Give each physical node many positions, called virtual nodes or tokens:

A1 A2 ... A200
B1 B2 ... B200
C1 C2 ... C200

Each virtual node owns a small arc. A physical node’s load is the sum of its tokens. With enough tokens, those sums concentrate around the mean.

product:p_42 → token B173 → physical Node B

How many virtual nodes? Too few and load stays lumpy. Too many and the placement map is large and membership changes move many tiny shards. Hundreds per node is a common starting range; the right number is measured with the real key distribution.

Weighted nodes receive more tokens if they have more tested capacity. Advertised RAM alone is a weak weight: a box with more memory and a slower NIC should not receive proportionally more hot GET traffic.

When Node B is removed, its tokens disappear and each of those small arcs passes to the next remaining token. Only those keys move. Rebalancing should copy or lazily refill that subset, not the whole cluster.

10. Who computes the hash: the cache client

Who performs consistent hashing?

If every Product Service instance must know Node B owns p_42, hashing belongs in a cache client library:

Product Service
      │
      ▼
Cache Client
      │  consistent hashing + connection pool + deadline
      ├── Node 1
      ├── Node 2
      └── Node 3

The application calls GET("product:p_42"). It should not choose a node.

Three routing designs appear in interviews:

The baseline is official clients for direct routing and an optional proxy for unsupported languages. Node forwarding is a bounded compatibility path, not the normal path.

The client caches a placement map: tokens, nodes, and a monotonically increasing epoch. No GET synchronously asks a control plane. If the control plane is down, cached maps still route. Membership changes pause; cache traffic does not.

A stale client may hit the old owner. That node can serve during migration, return MOVED(new_owner, epoch), or reject a write if it has been fenced. The client refreshes once with jitter and keeps the original deadline. Unbounded redirects are a bug.

11. Replication, even though data is disposable

Node 2 crashes. Every key it owned is gone.

The database is still the source of truth, so this is not silent data loss in the business sense. It is a miss storm. If Node 2 held 25% of hot keys, Product DB may see a 25% traffic spike plus reconnects and retries.

That is why we replicate a cache we are allowed to lose:

product:p_42
  Primary  → Node 2
  Replica  → Node 3   (different zone)

Replication factor is the number of copies. Factor 2 means one primary and one replica. Factor 3 costs another full memory copy and more write bandwidth. For disposable product data, one cross-zone replica is a strong default. It survives one node and usually one zone, not a regional wipe or a correlated bug.

Replication is for availability and miss-rate control, not for making the cache authoritative.

12. Acknowledge the primary, copy in the background

Synchronous replication:

Client
  │
  ▼
Primary
  ├── replica 1
  └── replica 2
          │
          ▼
         ACK

The client waits until copies exist. Failover loses fewer recent puts. Every put inherits replica and cross-zone tail latency. A slow replica becomes a slow cache.

Asynchronous replication:

Client
  │
  ▼
Primary applies and ACKs
  │
  └── replica copy happens after the response

Puts stay fast. A primary crash can lose a put that already returned STORED. The next GET misses or sees an older value and refills from Product DB.

For this product cache we prefer asynchronous, primary-acknowledged replication:

The caller already accepted that cache bytes may disappear.
Spending cross-zone tail latency on every put buys little extra truth.
It does buy a smaller miss spike after failover, which we still want—
but not at the cost of turning every write into a distributed commit.

A stricter namespace, such as short-lived session blobs that are painful to recompute, may choose to wait for one replica. At that point ask whether the component is still a cache.

Reads go to the primary by default so a writer usually reads its own put while ownership is stable. Replica reads are for stale-tolerant mode, failover, or a detected hot key. Document that even primary reads are not a database isolation level.

13. Read path and cache-aside

GET product:p_42:

Product Service
      │
      ▼
Cache Client → consistent hash → Node 2 primary
      │
      ▼
in-memory lookup + TTL check
      │
     HIT → return bytes

On miss, a generic cache does not have to know how to load a product. The application implements cache-aside:

GET cache
  ├── HIT  → return
  └── MISS
        │
        ▼
     GET Product DB
        │
        ▼
     PUT cache with TTL
        │
        ▼
     return product

Cache-aside keeps the cache generic and the database authoritative. The cache can be flushed, restarted, or wrong; Product DB still has p_42. The cost is duplicated miss logic in every service and a stampede risk when many callers miss together.

Read-through would let the cache fetch the database. That centralizes policy but couples a byte store to schemas, credentials, and every source’s failure mode. A product-specific gateway may do it. The shared cache should not pretend opaque bytes know how to load themselves.

Write-through updates database and cache in one application step. Write-behind acknowledges the cache and writes the database later. Write-behind is dangerous here: we already said cache state is disposable. Do not put Product DB truth behind a memory that may vanish.

14. Write path and the stale-cache problem

A put into the cache alone is not a product update. The usual application write is:

1. UPDATE Product DB   p_42 = Bob
2. DELETE cache key    product:p_42

The next read misses and loads Bob. Updating the cache in place (PUT the new value) is faster for readers but races more ways and can write a value the database later rolled back.

Prefer invalidation over silent cache updates for a general-purpose cluster:

UPDATE DB
    ↓
DELETE cache

not:

DELETE cache
    ↓
UPDATE DB

The second order has a famous race:

Writer: DELETE cache
Reader: MISS, reads DB, still sees Alice
Writer: UPDATE DB to Bob
Reader: PUT Alice back into cache

The cache now stores Alice while the database stores Bob.

The first order is better but not perfect:

Reader: MISS, reads DB Alice
Writer: UPDATE DB to Bob
Writer: DELETE cache
Reader: PUT Alice

This stale-set race still exists. Mitigations include source versions on PUT so an older fill cannot overwrite a newer tombstone, a second delayed delete after the write, short TTLs, or versioned invalidation events. None is free. Versions are strongest when Product DB exposes a monotonic entity version.

If many services must drop the key, a durable change log can fan out deletes. That log is not on the GET path. It exists because dual in-process deletes are easy to forget, not because every cache needs a global event bus.

15. TTL without a timer per key

Each entry stores expires_at. Clients send a duration; the server computes expiry from its clock so client clocks do not disagree.

Lazy expiration: on GET, if now >= expires_at, treat as miss and reclaim. Cheap, but unread expired keys occupy RAM forever.

Active expiration: a background job samples entries or walks a timing wheel and deletes expired keys in bounded batches. A timing wheel groups nearby deadlines into buckets so we do not run one operating-system timer per key.

Use both. Lazy expiration keeps the read path correct. Active expiration keeps memory honest.

TTL is a staleness bound, not a protocol for “delete everywhere instantly.” If invalidation is lost, the key still disappears when time passes. That is why disposable caches can tolerate missed deletes.

16. Hot keys: consistent hashing does not save Node 7

GET celebrity:123 at 500,000 QPS hashes to one token, therefore one primary:

Node 7  → 500,000 QPS
other nodes → quiet

The ring balanced keys, not request energy. One key can own almost all QPS.

Options, in increasing complexity:

1. A tiny process-local L1 with a short TTL so 500,000 GETs never all leave the app host.
2. Request coalescing so concurrent misses share one fill.
3. Serve bounded-stale replicas of that key.
4. Copy a detected hot key to extra read nodes.
5. Split the key into N equivalent copies only if any copy is interchangeable and invalidation can hit all of them. Unsafe for counters and CAS.

Moving the partition to another node moves the fire. Adding cluster capacity does not help if 100% of the heat is one key.

17. Cache stampede

A popular key expires. 100,000 in-flight GETs all see MISS and all query Product DB.

100,000 cache misses → 100,000 DB reads for the same row

This is a cache stampede or thundering herd.

Preferred behavior: single-flight / request coalescing. One caller becomes the filler. Others wait a bounded time for that result. If the fill fails, they error or retry with jitter; they do not all stampede again.

Distributed locks can elect the filler across processes, but lock expiry and lock-service failure recreate the herd. Start coalescing inside each application instance; add a shared lock only if many instances still overload the DB.

TTL jitter stops related keys from expiring on the same millisecond. Soft/hard TTL (stale-while-revalidate) serves slightly stale bytes while one caller refreshes. Cap how long stale data may be served.

18. Cache penetration

An attacker or a bug requests random-key-1, random-key-2, … Keys that never exist never occupy the cache, so every request misses and hits Product DB.

Negative caching stores “not found” for a short TTL. Safe only if a newly created p_42 invalidates that negative entry. Otherwise a just-inserted product stays invisible.

A Bloom filter can say “this ID is definitely not in the known catalog.” False positives still reach the DB. False negatives must not occur if the filter is maintained correctly. Bloom filters fit large, relatively stable ID sets; fast create/delete makes them operationally fussy. Do not add one automatically.

Rate limits still belong at the edge. Negative caching without abuse control is not a security design.

19. Cache avalanche

One million keys receive a 10-minute TTL at deploy time. Ten minutes later they expire together. The cache is not empty because of a crash; it is empty because time aligned.

Add jitter:

TTL = 10 minutes + random(0, 60 seconds)

Warm new nodes gradually. Rate-limit fills. Prefer stale-while-revalidate for the hottest keys. Load-shed low-priority traffic before Product DB connections are gone.

20. One node fails

Simple architecture:

Node 2 primary dies
    ↓
clients miss those keys
    ↓
Product DB refills
    ↓
new owner is empty until traffic warms it

Acceptable at small scale. At 10M QPS it can be a database outage.

Production-grade path:

1. Failure detector: missed heartbeats / failed probes, not one lost packet
2. Promote Node 3 replica with a new ownership epoch
3. Fence Node 2: it must reject writes for the old epoch
4. Clients receive a map update or MOVED
5. Lost async puts become misses and refill from Product DB
6. Rebuild a new replica below foreground traffic limits

Split brain is two primaries accepting writes. Epochs or leases prevent it. If we cannot fence, we must not promote.

Do not run a heavyweight consensus protocol on every GET. Use membership/leases for ownership changes; keep the data plane on the cached map.

Stale replicas may miss the last async put. That is the trade-off we accepted in section 12. Prefer a miss over merging opaque values.

21. The whole cluster disappears

Naive fallback:

Application → cache miss → Product DB

At 9 million GETs/second that is not a fallback. It is an outage of a different system.

Protect the source:

• Circuit breaker that opens onto a reduced path: local L1, bounded stale, or errors—not unlimited DB.
• Admission / rate limits on miss fills.
• Load shedding of optional traffic.
• Serve last-known L1 values where the product allows staleness.
• When the cache returns, warm gradually. Do not replay 100 million keys.

A cache SLO that ignores database QPS caused by misses is an incomplete SLO.

22. Cold cache recovery

A restarted cluster contains zero keys. Do not SELECT * 100 million products.

Cold cache → request-driven population of whatever is actually read
Optional: prewarm a measured hot-key list at a bounded rate
Never: unbounded background load of the full catalog

Request-driven population matches cache-aside. Prewarming helps only for keys you can prove are hot and cheap to load. Watch Product DB QPS and error rate as the primary recovery gauge, not only cache CPU.

23. Optional L1 in the application

Product Service
      │
      ▼
L1 local memory   (tiny, short TTL, per process)
      │ miss
      ▼
L2 distributed cache
      │ miss
      ▼
Product DB

L1 wins when a small keyset is extremely hot or when even 1 ms remote GETs are too many. It costs duplicate memory, harder invalidation, and more stale copies. Invalidate L1 with short TTL plus explicit deletes on the write path when you can. If L1 holds user-specific data, do not treat it as a shared cluster.

Introduce L1 after a hot key or a remote-cache RTT shows up in traces. It is not a default box on the first whiteboard.

24. Multi-region only after one region works

India app  → India cache cell  → India DB read path
US app     → US cache cell     → US DB read path

Do not synchronously replicate ordinary cache entries across oceans. The point of a cache is local latency, and the bytes are disposable. Each region misses and fills from its authorized database path. Versioned invalidations may travel asynchronously if the staleness bound requires it.

If India fails, the US cell does not magically contain India’s hot set. Expect cold misses and protect the US database. Database multi-region write ownership is a separate design. The cache must not invent a second global primary for p_42.

25. LLD: one node, then the client

Single-node cache

CacheNode
---------
map: Key → Node
list: doubly linked LRU
capacity in bytes and in items

Node / Entry
------------
key
value
expires_at
size
prev, next

Get(key):
  node = map.get(key)
  if node is null or expired: delete if present; return MISS
  moveToFront(node)
  return HIT(value)

Put(key, value, ttl):
  reject if value too large
  if exists: update, moveToFront
  else: insert front
  while over capacity: evict(tail)
  replicate async if this node is primary

Delete(key):
  remove from map and list
  replicate tombstone/version async

Evict():
  remove LRU tail that is not pinned; O(1)

Sharded maps/lists inside one process keep LRU mutations off a single lock. Expiration sampling runs on a timer with a bounded batch.

Distributed client

DistributedCacheClient
----------------------
placement map + epoch
consistent hash (key → token → node)
connection pools per node
timeouts, bounded retries, hedging optional
serialization
failover: MOVED / timeout → refresh map once

The client does not implement product cache-aside. The Product Service does. The client only routes opaque operations.

26. API design

A production cache often uses a compact binary protocol over persistent TCP. HTTP is easier to show in an interview.

Request:

GET /v1/cache/product:p_42
Deadline-Ms: 8

Hit:

200 OK

{
  "status": "HIT",
  "value": "<opaque>",
  "ttl_remaining_ms": 247320
}

Miss:

404

{ "status": "MISS" }

Timeout must not be encoded as 404. Use 504 or a protocol-level TIMEOUT. Absence and uncertainty are different.

Put:

PUT /v1/cache/product:p_42
Content-Type: application/octet-stream
Ttl-Ms: 300000

<opaque bytes>

200 OK

{ "status": "STORED" }

Delete:

DELETE /v1/cache/product:p_42

200 OK

{ "status": "DELETED" }

Deleting a missing key is still success. MGET/MSET batch independent keys, group by destination node, and return per-key status so one slow shard cannot erase the others.

Oversized values return 413. Unauthenticated internal callers return 401. Prefer RPC/binary in production: fewer bytes, tighter timeouts, less HTTP parsing on the 10M QPS path. HTTP/gRPC proxies remain useful at a boundary.

27. The cache does not own the database

Product Service
      ├── Cache Client → distributed cache
      └── Product DB

A generic distributed cache should not open Product DB connections. That separation lets many services share one cache cluster without sharing one schema. Cache-aside, invalidation, versions, and stampede control live in the application or a thin product-specific library.

28. Observe outcomes, especially misses

Most important:

hit ratio / miss ratio
p99 GET latency at the client
Product DB QPS and errors caused by misses

A cache at 80% hit rate can still destroy the database if the remaining 20% of 9M QPS is 1.8M DB reads.

Also measure: p50/p95 GET and PUT, QPS per node, memory and fragmentation, eviction and expiration rates, hot keys, replication lag, connection count, timeouts, MOVED/redirects, epoch skew, and stampede coalescing. Alert on client p99, miss-driven DB load, unavailable token fraction, and eviction storms—not only CPU.

29. Failure scenarios

Retries use jitter and a budget. Retrying a PUT is usually safe if last-write-wins is acceptable. Retrying an increment is not. Timeouts never invent misses.

30. CAP, stated honestly

A cache of product copies can choose availability and partition tolerance with eventual consistency: during a partition, remaining nodes still serve their keys; some puts may be lost; readers may see stale bytes.

That is acceptable because Product DB remains the source of truth.

It is not acceptable for:

• inventory reservation;
• payment capture;
• a distributed lock that must have a single owner.

If an interviewer asks “is the cache AP or CP?”, answer with the workload, not a slogan. Session cache ≠ lock state ≠ product HTML fragment.

31. Do not casually turn the cache into a lock service

People remember:

SET lock:order:9 NX EX 30

That pattern is a best-effort mutex. It is not a complete lock service.

A lock needs:

• a unique owner token;
• TTL so a dead holder cannot block forever;
• extension only by the owner;
• fencing tokens so a paused holder cannot act after expiry;
• behavior under split brain that never grants two live owners if the resource is unsafe.

A general distributed cache optimized for AP product reads will get lock expiry, clock issues, and partitions wrong if you treat NX as a law of physics. If you need locks, design a lock service—or use the database’s transaction/locking—and keep this cache disposable.

32. Final architecture

Only now do the boxes earn their place:

                         Product Service
                              │
                              ▼
                         L1 Cache
                      (optional, tiny)
                              │
                              ▼
                       Cache Client
                   consistent hashing
                   pools, deadlines, maps
                              │
              ┌───────────────┼───────────────┐
              ▼               ▼               ▼
           Node 1           Node 2           Node 3
           Primary          Primary          Primary
              │               │               │
           Replica          Replica          Replica
           other AZ         other AZ         other AZ
              │               │               │
              └───────────────┼───────────────┘
                              │
                            MISS
                              │
                              ▼
                          Product DB
                       source of truth

Control plane publishes placement epochs off the GET path.
Invalidation events, if used, are async and optional.

Every arrow has a job:

• L1 absorbs extreme hot keys without a network hop.
• The client chooses a node without asking the control plane per request.
• Consistent hashing with virtual nodes maps keys to nodes so membership changes move a slice, not the world.
• A primary owns reads/writes; a replica exists to shrink miss storms, not to be truth.
• A miss returns to the application, which alone knows how to read Product DB.
• Nothing in the cache is allowed to silently replace Product DB.

33. Core flows

GET hit

1. Optional L1
2. Client hashes product:p_42 to a token and primary
3. Pooled GET under a deadline
4. Node map lookup, key compare, TTL check
5. LRU promotion
6. Return bytes

GET miss

1. Cache returns MISS (timeouts are separate)
2. Product Service single-flights p_42
3. One DB read under a miss budget
4. PUT with TTL jitter and optional source version
5. Waiters share the result

Product update

1. UPDATE Product DB to version N+1
2. DELETE cache key (and L1)
3. Optional durable invalidation to other cells
4. Delayed older PUT loses to version/tombstone

Node failover

1. Primary silent past detection threshold
2. Replica promoted at epoch+1; old primary fenced
3. Clients refresh maps
4. Missing async puts become DB refills
5. Replica rebuild is throttled

34. Interview-ready recap

Partitioning and hashing

Start:     hash(key) % N
Breaks:    adding a node remaps almost every key
Replace:   consistent hashing on a ring
Smooth:    virtual nodes / tokens per physical node
Route:     cache client with a versioned placement map

A key belongs to the first node clockwise from its hash. Adding a node steals only the preceding arc.

Replication and failover

One cross-zone replica, asynchronous primary ACK. Failover promotes with a fencing epoch. Lost recent puts are misses, not silent corruption of Product DB.

Cache-aside, TTL, eviction

Applications read cache then DB then PUT. TTL uses lazy plus bounded active expiration. Each node evicts locally with LRU (HashMap + doubly linked list, or an approximation). No global LRU.

Pathologies

Hot key          L1, coalesce, extra read copies; hashing will not save you
Stampede         single-flight + jitter + optional stale-while-revalidate
Penetration      short negative cache; Bloom filter only if the set fits
Avalanche        TTL jitter and staged warmup
Cluster down     shed and protect DB; never unlimited bypass
Cold start       request-driven fill; bounded hot-key prewarm

What to say in 45 minutes

0–5 min     DB is truth; cache is disposable; GET/PUT/DELETE/TTL
5–10 min    Scale: 100M × 1 KB is not 100 GB RAM; 10M QPS and skew
10–16 min   Single-node HashMap + LRU list; why one box fails
16–24 min   hash%N remap → consistent hashing → virtual nodes → client
24–30 min   Async replica, cache-aside, DB-then-delete invalidation
30–38 min   Hot keys, stampede, penetration, avalanche, failover
38–42 min   Cluster outage vs DB, L1, multi-region cells
42–45 min   LLD complexities, CAP, why this is not a lock service

A two-minute condensed answer

I would treat Product DB as source of truth and the cache as disposable memory. On one node, a HashMap plus a doubly linked list gives O(1) GET/PUT/DELETE and LRU eviction, with lazy and sampled TTL expiration. One machine cannot hold the RAM, QPS, or failure domain, so we partition. hash % N remaps almost every key when N changes, so we place nodes and keys on a consistent-hash ring and use virtual nodes to even out arcs. A client library routes GET(key) from a cached placement map.

We replicate asynchronously to another zone so a crash is not a full miss storm, accepting loss of recently acknowledged puts. Applications use cache-aside: miss, read DB, PUT with jittered TTL; writes update the database then delete the key. Hot keys need L1 or extra copies because hashing balances keys, not QPS. Stampedes use single-flight. The cache never becomes the database: if the cluster dies, we shed load rather than replay 10 million QPS into Product DB.

Likely follow-ups

• Why not hash % N with a lookup table of nodes?
• How many virtual nodes, and how do you measure imbalance?
• What does an ACK mean if replication is async?
• Why delete the cache after the DB write, not before?
• How do you fence a primary that paused and came back?
• When is write-through acceptable?
• How would you cache something that cannot be rebuilt?
• Why isn’t Redis lock enough for inventory?
• How do you find hot keys without counting every GET globally?
• What changes if values are 1 MB?

Senior-level insights

• Latency SLOs are client-boundary SLOs; hash lookup is not the tail.
• Memory overhead and fragmentation are first-class capacity.
• Average QPS hides the celebrity key.
• Consistent hashing solves remapping, not hot keys.
• Disposable data still needs replication to protect the database.
• Cache-aside plus DB-then-delete still has a stale-set race; name it.
• Exact global LRU is a coordination problem dressed as a list.
• A control plane may change placement without sitting on GET.
• Circuit breakers must reduce work, not redirect a herd.
• A cache that can lose data must not sell itself as a lock manager.

The compact mental model is the derivation itself:

Single-node HashMap
      ↓ memory / QPS / failure
Multiple nodes
      ↓ which node owns the key?
hash % N
      ↓ membership remaps everything
Consistent hashing + virtual nodes
      ↓ node death is a miss storm
Replication + fenced failover
      ↓ popular keys and aligned TTLs
Hot-key, stampede, avalanche controls
      ↓ remote RTT and celebrities
Optional L1
      ↓ geography
Independent regional cache cells
      ↓ always
Product DB remains the source of truth

For a broader framework on requirements, estimation, APIs, and interview communication, see the complete system design interview guide.