Caching Strategy Template (Cache-Aside, Invalidation, Stampede Control)

Per-data-class cache decision: placement, read/write pattern, hit ratio and memory sizing, TTL, invalidation, stampede control, cold start

सिस्टम डिज़ाइनमानकScaling Memcache at Facebook (NSDI 2013); RFC 9111; RFC 5861caching strategyअपडेट किया गया 29 अक्टू॰ 2026

एडिटर में खोलें.md डाउनलोड करें

उपयोग कैसे करें: Use it when adding or changing a cache in front of a database or service. Fill the source capacity and minimum hit ratio first, then the invalidation path. The main pitfall is planning for a warm cache only, so a flush or cold region sends the full read load to the source.

प्रीव्यू

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.

Document control

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

[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

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

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

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

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:

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

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:

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

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

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

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

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

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.