# Caching Strategy: [Service or data domain]

> Building-block decision record for adding or changing a cache in front of
> a database or service. It covers where the cache sits, the read and write
> pattern (cache-aside, read-through, write-through, write-behind), keys and
> time to live, invalidation, stampede control, cold start, failure modes and
> the metrics that prove the cache works. Concepts draw on "Scaling Memcache
> at Facebook" (Nishtala et al., NSDI 2013), on the probabilistic early
> recomputation analysis of Vattani et al. (VLDB 2015) and, for HTTP caches,
> on RFC 9111 HTTP Caching (June 2022) and RFC 5861. Replace every
> `[bracketed]` value and every row marked *Example*. Worked examples use
> Quillmere, an invented book-review and reading-list platform shared by the
> other building-block templates in this category.

<!--
Guidance: How to use this template
- Write one record per cached data class (for example "book detail page"
  or "user session"), not one per technology. Two data classes with
  different staleness tolerance need two rows in section 3, often two
  records.
- Start from the source of truth: how many misses per second can it
  survive? That number sets the minimum hit ratio (section 4) and decides
  how much stampede and cold-start protection you need.
- Fill section 5 (invalidation) before section 6 (stampede control): most
  cache incidents are stale data or a herd after a mass expiry, not a slow
  cache.
- For the full design of a shared cache tier (nodes, slot maps, gutter
  pools, regions) use the Distributed Cache System Design template
  (`system-design/design-distributed-cache`); this record is the per-use
  decision that sits on top of it.
-->

## Document control

<!-- Guidance: Record who owns the cached data and who owns the cache tier; they are often different teams and both must agree to the invalidation contract. -->

| Field | Value |
|---|---|
| Document ID | [CACHE-REC-001] |
| Data class cached | [*Example:* Book detail (title, authors, rating summary, cover URL)] |
| Source of truth | [*Example:* `catalog` PostgreSQL primary, read replicas] |
| Cache technology and tier | [*Example:* Shared in-memory key-value cluster, in-process L1 per pod] |
| Version | [0.1] |
| Status | [Draft / In review / Approved / Implemented / Superseded] |
| Owner (data) | [@catalog-lead] |
| Owner (cache tier) | [@platform-lead] |
| Reviewers | [@sre], [@security] |
| Last updated | YYYY-MM-DD |
| Classification | [Internal] |
| Related | Distributed Cache System Design (`system-design/design-distributed-cache`), CDN System Design (`system-design/design-cdn`), Resilience and Load Shedding Design (`system-design/resilience-load-shedding-design`) |

### Approvals

| Role | Name | Decision | Date |
|---|---|---|---|
| Data owner | [@name] | [Approved / Changes requested] | YYYY-MM-DD |
| Cache tier owner | [@name] | [Decision] | YYYY-MM-DD |
| SRE | [@name] | [Decision] | YYYY-MM-DD |

### Revision history

| Version | Date | Author | Change summary |
|---|---|---|---|
| 0.1 | YYYY-MM-DD | [@name] | First draft |
| 0.2 | YYYY-MM-DD | [@name] | *Example:* Switched from update-on-write to delete-on-write after a stale rating incident |

## 1. Problem and goal

<!-- Guidance: Say why a cache is needed at all. Valid reasons are latency, protecting the source from read load, cost, or availability when the source is down. "It might be faster" is not a reason; a cache adds a second copy of data that can be wrong. -->

[Problem statement. *Example:* Book detail reads peak at 40,000 requests
per second during evening hours. The catalog database can serve about
3,000 reads per second at an acceptable p99 latency. Without a cache the
page cannot meet its 150 ms p99 target and the database saturates.]

| Goal | Target | How measured |
|---|---|---|
| *Example:* Protect the source | Database reads at or below 3,000 per second at peak | Database query rate dashboard |
| *Example:* Latency | Book detail p99 at or below 150 ms | Service latency histogram |
| *Example:* Freshness | Rating summary at most 10 minutes stale, title and authors at most 60 seconds after an edit | Staleness probe (section 9) |
| [Goal] | [Target] | [Measure] |

## 2. Placement

<!-- Guidance: Name every layer that holds a copy. Each extra layer multiplies the paths by which stale data can survive an update. Pitfall: an in-process cache added later by another team, with its own TTL, that nobody lists here. -->

| Layer | Holds | TTL | Invalidated by | Notes |
|---|---|---|---|---|
| *Example:* Browser and CDN (HTTP cache) | Rendered public book page | `max-age=60`, `stale-while-revalidate=30` | Expiry only | Public data only; never personalised fields |
| *Example:* In-process L1 per pod | Book detail object | 5 s | Expiry only | Absorbs hot keys; short TTL bounds staleness |
| *Example:* Shared cache cluster (L2) | Book detail object | 600 s with plus or minus 10% jitter | Delete on write (section 5) | Main protection for the database |
| [Layer] | [Data] | [TTL] | [Mechanism] | [Notes] |

For HTTP caches, the freshness model, `max-age`, `s-maxage`, `no-store`,
`private` and serving stale responses are defined in RFC 9111 (sections
4.2 and 5.2); `stale-while-revalidate` and `stale-if-error` are defined in
RFC 5861 (sections 3 and 4). Check that every proxy and CDN in the path
honours the directives you rely on.

## 3. Read and write pattern

<!-- Guidance: Pick one pattern per data class and say why. Most systems use cache-aside with delete-on-write because it is simple and fails safe. Write-behind is the only pattern that can lose acknowledged writes; it needs a durability argument. -->

| Pattern | How it works | Good for | Risks |
|---|---|---|---|
| Cache-aside (look-aside) | Application reads cache, on miss reads source and fills cache; on write updates source then deletes the key | Most read-heavy data | Race between a slow fill and a delete can leave stale data; mitigate with leases or versioned sets |
| Read-through | Cache library loads from source on miss | Uniform loaders, fewer code paths | Hides source latency from callers; loader must be idempotent |
| Write-through | Write goes to cache and source in the same request path | Data read right after write | Write latency is the sum of both; partial failure leaves the two out of step |
| Write-behind (write-back) | Write goes to cache, flushed to source later | Counters, high write rates where loss is acceptable | Acknowledged writes lost if the cache node fails before flush |
| Refresh-ahead | Cache refreshes popular keys before they expire | Predictable hot keys | Wasted work on keys that are no longer read |

Decision for this data class: [Pattern and reason. *Example:*
Cache-aside with delete-on-write for book detail. Writes are rare (about
200 per second) and correctness after an author edit matters more than
the cost of one extra miss.]

## 4. Capacity and hit ratio

<!-- Guidance: Derive the minimum hit ratio from the source capacity, not from a wish. Minimum hit ratio = 1 - (safe source reads per second / peak reads per second). Then size memory for the working set with headroom for fragmentation and growth. -->

| Input | *Example* value | Source |
|---|---|---|
| Peak reads | 40,000 per second | Traffic dashboard, last 30 days |
| Safe source reads | 3,000 per second | Load test of catalog primary and replicas |
| Minimum hit ratio | 1 - 3,000 / 40,000 = 92.5% | Derived |
| Target hit ratio | 95% (source sees 2,000 reads per second) | Chosen with 1,000 reads per second margin |
| Hot working set | 2,000,000 keys | Distinct books read in a 24-hour window |
| Average entry size | 2,048 B value plus about 100 B key and overhead | Sampled serialised objects |
| Memory for working set | 2,000,000 x 2,148 B = 4.30 GB (4.0 GiB) | Derived |
| Memory with 30% headroom | 5.2 GiB | Derived |

Source load at other hit ratios, *Example*:

| Hit ratio | Source reads per second | Within 3,000? |
|---|---|---|
| 90% | 4,000 | No |
| 92.5% | 3,000 | At the limit |
| 95% | 2,000 | Yes |
| 98% | 800 | Yes |

A cold cache sends all 40,000 reads per second to the source, 13.3 times
its safe capacity. Section 7 covers how to avoid that.

## 5. Keys, TTL and invalidation

<!-- Guidance: Define the key format, what changes it, and the full path from a write in the source to the removal of every cached copy. Prefer delete over update on write: a delete that races with a fill loses at most one fill, an update that races can install old data for a full TTL. -->

**Key format:** [*Example:* `book:v3:{book_id}`. The `v3` segment is the
schema version; bumping it on a format change makes old entries
unreachable without a mass delete.]

**TTL:** [*Example:* 600 s with plus or minus 10% random jitter, so
entries written together expire between 540 s and 660 s instead of in
one second.]

**Invalidation path:**

```mermaid
sequenceDiagram
  participant W as Catalog writer
  participant DB as Catalog database
  participant CDC as Change stream reader
  participant C as Shared cache
  W->>DB: UPDATE book 42 (commit)
  DB-->>CDC: Change event for book 42
  CDC->>C: DELETE book:v3:42
  Note over C: Next read misses and refills from the database
```

| Rule | *Example* decision |
|---|---|
| Who deletes | A change stream reader on the database commit log, not the writing service, so every write path (admin tools, migrations, batch jobs) is covered |
| Delete retries | Retried with backoff until acknowledged; failures alert after 5 minutes |
| Race with a slow fill | Fills carry a lease token issued on the miss; a delete cancels outstanding leases, so a fill started before the delete is rejected |
| Bulk changes | Schema change bumps the key version; no mass delete |
| Regions | Each region's change reader deletes in its own region's cache |

The lease idea (a token on miss that a later delete invalidates) and
commit-log driven deletes are described in the NSDI 2013 memcache paper.
The commit-log approach is covered in more depth by the CDC Pipeline System
Design template (`system-design/design-cdc-pipeline`).

## 6. Stampede and hot-key control

<!-- Guidance: A stampede (thundering herd) happens when many requests miss the same key at once, typically after expiry or a delete of a popular key. Estimate it: herd size is roughly requests per second on the key multiplied by recompute time. -->

*Example:* the most popular book receives 5,000 reads per second and a
fill takes 200 ms. Without protection about 5,000 x 0.2 = 1,000 requests
reach the database for one key during each refill.

| Control | How it works | *Example* setting |
|---|---|---|
| Request coalescing (single flight) | One request per key per process performs the fill; others wait for it | On in L1 and in the loader |
| Lease on miss | The cache gives one client a lease to fill; others get "retry shortly" or a stale value | Lease wait 10 ms, maximum 3 retries |
| Serve stale while refreshing | Keep the expired value for a short grace period and refresh in the background | 30 s grace |
| Probabilistic early refresh | Each read refreshes early with a probability that grows as expiry approaches, so one reader usually refreshes before expiry (Vattani et al., VLDB 2015) | Beta 1.0, recompute time stored with the value |
| TTL jitter | Spread expiry of entries written together | Plus or minus 10% |
| Hot-key replicas | Copy a very hot key under several suffixes or in L1 | L1 5 s for top 1,000 keys |

A common form of early refresh, written as code:

```text
on read(key):
  value, delta, expiry = cache.get_with_meta(key)
  # delta = seconds the last recompute took, beta >= 1.0 refreshes earlier
  if value is missing or now() - delta * beta * ln(random()) >= expiry:
      value = recompute_and_set(key)
  return value
```

`ln(random())` is negative, so the subtraction moves the check point
earlier by a random amount scaled by the recompute time.

## 7. Cold start and cache failure

<!-- Guidance: Plan for an empty cache (new cluster, region failover, flush) and for a cache that is down. Pitfall: treating the cache as optional while the source cannot survive its absence. -->

| Scenario | Effect without control | Control | *Example* decision |
|---|---|---|---|
| New or flushed cluster | Source sees full read load | Warm from a peer cluster or from logs of recent keys before taking traffic | Warm the top 500,000 keys, then shift traffic in 10% steps |
| One cache node lost | Its share of keys misses at once | Small standby pool with short TTL, as in the NSDI 2013 gutter idea, or replicas | Standby pool of 2 nodes, 10 s TTL |
| Whole cache down | Up to 40,000 reads per second at source | Load shedding and a circuit breaker in front of the source | Shed non-logged-in traffic first; see `system-design/resilience-load-shedding-design` |
| Cache slow, not down | Timeouts pile up threads | Short cache timeout, treat as miss with a rate cap | 20 ms timeout, fall back for at most 2,000 reads per second |

## 8. Security and privacy

<!-- Guidance: A cache is a data store. Apply the same classification, encryption and access rules as the source, and make sure personalised data never lands in a shared HTTP cache. -->

- [ ] Shared HTTP caches receive only public responses; personalised
      responses carry `Cache-Control: private` or `no-store` (RFC 9111
      section 5.2.2).
- [ ] Cache keys for user data include the user or tenant ID, so one user
      cannot read another's entry.
- [ ] Network access to the cache cluster is restricted to the services
      that need it, with authentication and transport encryption where
      supported.
- [ ] Deleting a user's data (erasure request) deletes or expires their
      cached copies within a stated time: [*Example:* 10 minutes].
- [ ] Secrets and tokens are not cached unless the cache is approved for
      that classification.

## 9. Metrics and alerts

<!-- Guidance: Measure the outcome (source load, staleness), not only the cache itself. A 99% hit ratio means little if the misses are all for the most expensive keys. -->

| Metric | *Example* alert threshold | Why |
|---|---|---|
| Hit ratio per data class | Below 93% for 10 minutes | Approaches the 92.5% minimum from section 4 |
| Source reads per second | Above 2,700 for 5 minutes | 90% of safe capacity |
| Fill latency p99 | Above 300 ms | Herd size grows with fill time |
| Invalidation lag (commit to delete) | Above 5 s p99 | Freshness target |
| Staleness probe | Probe value older than target | Writes a known record and reads it back through the cache |
| Evictions per second | Sudden rise of 3 times baseline | Working set grew or memory shrank |

## 10. Decisions and open items

<!-- Guidance: Record each decision with its reason and link larger ones to an ADR (`architecture/adr-full`). -->

| ID | Decision or open item | Reason | Owner | Status |
|---|---|---|---|---|
| CD-01 | *Example:* Cache-aside with delete-on-write | Simple, fails safe, writes are rare | @catalog-lead | Decided |
| CD-02 | *Example:* Change stream drives deletes | Covers every write path | @platform-lead | Decided |
| CD-03 | *Example:* Rating summary uses TTL only, no delete | 10-minute staleness accepted by product | @product | Decided |
| CD-04 | *Example:* Evaluate warm-up tooling for region failover | Cold start is 13.3 times source capacity | @sre | Open |
| [CD-NN] | [Item] | [Reason] | [@owner] | [Status] |

## Glossary and references

<!-- Guidance: Keep definitions short so readers from other teams can review the record. -->

| Term | Meaning |
|---|---|
| Hit ratio | Share of reads answered by the cache without reaching the source |
| TTL | Time to live: how long an entry may be served before it expires |
| Stampede (thundering herd) | Many concurrent misses on one key that overload the source |
| Lease | Token given to one client on a miss, allowing it to fill the key; invalidated by a later delete |
| Cold start | Period when the cache is empty and the source sees most reads |

References:

- Nishtala R. et al., "Scaling Memcache at Facebook", 10th USENIX
  Symposium on Networked Systems Design and Implementation (NSDI '13),
  2013, pages 385 to 398,
  https://www.usenix.org/conference/nsdi13/technical-sessions/presentation/nishtala
  (leases, commit-log invalidation, gutter pool, cold cluster warm-up).
- Vattani A., Chierichetti F., Lowenstein K., "Optimal probabilistic cache
  stampede prevention", Proceedings of the VLDB Endowment 8(8), 2015,
  pages 886 to 897, https://doi.org/10.14778/2757807.2757813.
- RFC 9111, HTTP Caching (STD 98, June 2022),
  https://www.rfc-editor.org/info/rfc9111.
- RFC 5861, HTTP Cache-Control Extensions for Stale Content (Informational,
  May 2010), https://www.rfc-editor.org/info/rfc5861.
- Related templates: Distributed Cache System Design
  (`system-design/design-distributed-cache`), CDN System Design
  (`system-design/design-cdn`), Partitioning and Sharding Guide
  (`system-design/partitioning-sharding-guide`), Replication and
  Consistency Models (`system-design/replication-consistency-models`),
  Back-of-Envelope Estimation (`system-design/back-of-envelope-estimation`).

## Standard and licence note

Based on the publicly described techniques in the NSDI 2013 memcache paper
and the VLDB 2015 stampede paper, and on RFC 9111 and RFC 5861 for HTTP
caching semantics; no standard governs application cache design. The text,
tables, numbers and examples are original to this collection, and
Quillmere is an invented organisation. Check the current RFC status and
the documentation of the cache software you adopt. Template licence: MIT.