System Design: [Distributed cache name]

Reference design for a shared, in-memory distributed cache tier that sits in front of databases and services in read-heavy workloads. It covers the cache-aside (look-aside) pattern, leases against stale sets and thundering herds, invalidation across clusters and regions, consistent hashing and slot maps, hot keys, warm-up of cold clusters, and failure handling with a small standby ("gutter") pool. Concepts draw on "Scaling Memcache at Facebook" (Nishtala et al., NSDI 2013); the text and the worked design are original. It follows the structure of the System Design Document template. Replace every [bracketed] value and every row marked Example.

Document control

Approvals

Revision history

Contents

1. Overview
2. Requirements
3. Capacity estimation
4. API design
5. Data model
6. High-level design
7. Detailed design
8. Scalability and performance
9. Reliability, security and operations
10. Trade-offs and alternatives
11. Delivery plan and risks
12. Appendices

1. Overview

1.1 Problem statement

[Example: Each service runs its own cache cluster with its own conventions. Writers update cache values after writing the database, and races leave stale profiles for hours. When a popular item expires, thousands of requests miss at once and the database falls over. A single cache node failure moved a third of the keys to other nodes and caused a cascade of misses.]

1.2 Proposed solution

[Example: A shared cache tier of stateless-looking, memory-only cache servers, organised in clusters per region. Clients use cache-aside: read the cache, on a miss read the database and fill the cache with a lease token so that stale fills are rejected and only one client per hot key refills it at a time. Writers never set values; they delete keys, and deletes are also generated from the database commit log and fanned out to every cluster and region. Keys map to servers through a versioned slot map. A small gutter pool absorbs traffic for failed servers so their keys do not move. New clusters warm up by reading through a warm cluster.]

1.3 Decisions requested from reviewers

1.4 45-minute interview path

2. Requirements

2.1 Core functional requirements

2.2 Non-functional requirements

2.3 Below the line (out of scope)

• [Example: Durable storage; the cache may lose any data at any time (see system-design/design-distributed-kv-store for durable key-value storage)]
• [Example: Transactions or compare-and-set across keys]
• [Example: Caching personalised HTML at the edge (handled by the CDN)]
• [Example: Strong consistency for money or inventory; those reads go to the database]
• [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

3.2 Hit ratio and database load

At $h = 0.98$, $D = 10^{7} \times 0.02 = 200\,000$ database reads/s; at $h = 0.90$, $D = 1\,000\,000$/s. Consequence: a drop of 8 points in hit ratio multiplies database reads by five and breaks NFR-04, so the design spends most of its complexity keeping the hit ratio stable when keys expire (leases), when nodes fail (gutter) and when clusters are new (warm-up).

3.3 Nodes

Consequence: the tier is throughput-bound, not memory-bound, so choose instances with more CPU and network per GB, and use the spare memory (66 nodes x 64 GB, about 4.2 TB against a 1 TB working set) to cache a longer tail and raise the hit ratio.

3.4 Network and fan-out

Total read bandwidth is $10^{7} \times 500$ B $= 5$ GB/s, about 76 MB/s per node, which is modest. Fan-out is the real cost: with 100 keys spread over 66 nodes, the expected number of distinct nodes touched is

Consequence: a page waits for the slowest of about 52 parallel requests, so tail latency of single nodes dominates (incast). Batch per node, cap outstanding requests per client, and group keys that are read together (same hash tag) where the data model allows it.

3.5 Hot keys

A viral item read 1 million times per second exceeds one node's 200 000 ops/s by five times. Consequence: hot keys need replication (several copies under suffixed keys) or a client-side L1 cache with a 1 s TTL; with 2 000 web servers each refreshing once per second, the cache tier sees about 2 000 reads/s for that key instead of 1 million.

3.6 Summary

4. API design

4.1 Client operations

4.2 Read path in code

def read_profile(user_id):
    key = f"profile:v3:{user_id}"
    r = cache.lease_get(key)
    if r.hit:
        return r.value
    if r.wait:                      # another client holds the lease
        sleep_ms(r.retry_after_ms)  # short backoff, then one retry
        r2 = cache.get(key)
        if r2.hit:
            return r2.value
    value = db.read_profile(user_id)          # one database read
    if r.token:
        cache.lease_set(key, value, r.token, ttl=3600)
    return value

Write path: commit the database transaction, then delete(key). The commit log consumer (7.3) deletes the same key again everywhere; deletes are idempotent, so the duplicate is harmless.

4.3 Admin API

5. Data model

5.1 Keys and values

Keys follow {namespace}:{schema_version}:{entity_id}[:{variant}], for example profile:v3:918273 or feed:v2:918273:page1. The schema version in the key lets a deploy that changes the value format read new keys while old ones expire. Values carry a small header:

Server-side lease state is kept in memory per key: token, issued time, and whether a delete has invalidated it.

5.2 Storage choices

5.3 Access patterns

6. High-level design

7. Detailed design

7.1 Deep dive: caching pattern and write handling

Choice: B. Reason: deletes are safe under any interleaving and any duplication, which matters because deletes arrive from writers and again from the commit log; the remaining race (a reader fills a value it read before the write) is closed by leases in 7.2.

7.2 Deep dive: leases against stale sets and thundering herds

Two problems happen on a miss:

• Stale set: reader A misses and reads version 1 from the database; writer B commits version 2 and deletes the key; A then sets version 1, which stays until TTL.
• Thundering herd: a hot key is deleted or expires; thousands of readers miss at once and all query the database.

Choice: D. Reason: one mechanism fixes both problems at the server that sees every request for the key.

1. On a miss, the server returns a lease token bound to the key.
2. A delete of that key invalidates outstanding tokens, so a fill based on an older read is rejected.
3. The server issues at most one token per key per interval (Example 2 s); other clients get a short wait hint and retry, by which time the lease holder has usually filled the value.
4. For data classes that tolerate it, the server keeps a recently deleted value and returns it marked stale instead of wait, so readers never block.

Set the lease interval and wait hint from measured database read latency for the namespace; a hint shorter than the database read creates repeated retries.

7.3 Deep dive: invalidation across clusters and regions

Several clusters per region each hold the full key space, and replica regions read from replica databases. A delete must reach every copy.

Choice: C plus the writer's own local delete and a TTL safety net. Reason: the commit log is the only place every committed change appears exactly once in order, so invalidations become as reliable as replication; the writer's local delete gives read-your-writes in its own cluster.

In replica regions the replica database may lag; a reader that misses could fill the cache from a replica that has not yet seen the write. Two measures:

• Deletes in replica regions are produced from the replica's commit log, so they arrive after the replica has applied the change.
• For read-your-writes, the writer sets a short-lived remote marker for the key in the regional pool before writing; a reader in that region that misses and finds the marker reads from the primary region's database instead of the local replica. The marker is removed when the change replicates or by TTL.

7.4 Deep dive: partitioning, failure handling and warm-up

Key distribution options:

Choice: D. Reason: explicit slot moves make rebalancing a planned, observable operation, hot slots can be moved alone, and the map version lets routers detect stale routing.

Failure options:

Choice: C. Reason: failures stay contained to a pool sized for them, other nodes keep their keys and hit ratios, and the database sees only the first miss per key. A permanent replacement is done by a planned slot-map change.

Cold cluster warm-up: a new or emptied cluster reads misses from a warm cluster in the same region and adds the value locally, instead of going to the database. Deletes to the cold cluster use a short hold-off (Example 2 s) during which adds are refused, so a value that the warm cluster has not yet invalidated cannot be copied in; a refused add sends the reader to the database. Turn warm-up off when the cold cluster's hit ratio stabilises.

7.5 How real systems do it

How real systems do it (paraphrased, not copied). Nishtala and colleagues describe Facebook's memcache deployment in "Scaling Memcache at Facebook" (NSDI 2013). The cache is a demand-filled look-aside cache and writers delete rather than update. Memcached hands out leases on misses: a delete invalidates the token so late fills are refused, and tokens for a key are issued only every few seconds so most concurrent readers wait briefly instead of hitting the database. A small Gutter pool, around one percent of cache servers, takes over for failed servers with quickly expiring entries, avoiding the rehashing that can cascade. Invalidations come from daemons that tail the database commit log and are batched through routers. Rarely accessed items can share one regional pool, new clusters warm up from existing ones using deletes with a hold-off, and replica regions use remote markers to send reads of just-written keys to the master region. This template reuses the ideas, not the text or figures.

8. Scalability and performance

Latency budget for one get (NFR-01, Example): client library 0.05 ms, router hop 0.2 ms, server 0.05 ms, network 0.3 ms, headroom 0.4 ms. Remove the router hop for the hottest services by running the router as an in-process library.

9. Reliability, security and operations

9.1 Failure-mode table

9.2 Security

9.3 Observability

10. Trade-offs and alternatives

11. Delivery plan and risks

11.1 Milestones

11.2 Rollout and rollback

[Example: Migrate one namespace at a time behind a flag that chooses the old or new client library. Rollback flips the flag; both tiers receive deletes during migration so neither serves stale data after a switch.]

11.3 Risks

12. Appendices

12.1 Open questions

12.2 Glossary

12.3 Related templates

• Distributed Key-Value Store System Design (system-design/design-distributed-kv-store): durable storage, when a cache is not enough.
• CDC Pipeline System Design (system-design/design-cdc-pipeline): commit-log stream that drives deletes.
• Distributed Lock and Coordination Service System Design (system-design/design-distributed-lock-coordination): slot map and configuration storage.
• Resilience and Load Shedding Design (system-design/resilience-load-shedding-design): protecting the database when the cache fails.
• Back-of-Envelope Estimation (system-design/back-of-envelope-estimation): method behind section 3.

12.4 References

Standard and licence note

Based on the publicly described techniques in the NSDI 2013 memcache paper cited in 12.4 and on common industry practice; no standard governs cache tiers. This is a reference design to adapt, with illustrative numbers marked Example. Original text written for this collection; sources were used as inspiration only and no text, figures or diagrams were copied. Check the current documentation of the cache software you adopt. Template licence: MIT.