Component Architecture · Phase 2: Core Infrastructure
Caching Architecture & Critical Pathologies
Implement cache-aside, read-through, write-through, and write-back patterns while mitigating stampedes, avalanches, penetrations, and hot-key skew.
Primary specification: Scaling Memcache at Facebook (Nishtala et al.)
Lesson 10 of 33
1d streakThe Architectural Question
A database cluster collapses under read load during high-traffic events because cache misses bypass protection and directly bombard the underlying relational storage.
Core Engineering Objectives
- Caching strategies: Cache-Aside (Lazy Loading), Write-Through, Write-Back, and Refresh-Ahead
- Catastrophic pathologies: Cache Stampede (Thundering Herd), Cache Avalanche, Cache Penetration
- Mitigation algorithms: Singleflight mutex locking, probabilistic early expiration (XFetch), Bloom filters
Interactive system trace
Watch the architecture make its key decision
Switch scenarios, predict the next active component, and step through the request or failure path.
Fast path
Caching Strategies
The client requests product:42 and a fresh copy is already in Redis.
Application
product:42
Read request
Redis cache
v1 · fresh
Bounded by TTL
Database · source of truth
v1 · authoritative
Queried only after a miss
Database reads
0
Hit bypasses the database
Cache policy
TTL enabled
Freshness is explicit
Response state
In progress
Client contract is unchanged
The request reaches the API with key product:42.
Why it matters: The API owns a consistent read contract for both hits and misses.
1. What is it & Why it Matters
A distributed cache is a fast, in-memory key-value store (e.g., Redis, Memcached) positioned between application services and persistent databases. It trades memory cost for sub-millisecond read latency and protects databases from read saturation.
The Cache is NOT a Database
2. Invalidation Topologies & Hit-Rate Math
Cache-Aside (Lazy Loading)
Application queries cache first. On miss, it reads from DB, writes the result to cache, and returns. Simple and resilient to cache failure, but vulnerable to stampedes on cold keys.
Write-Through
Application writes data to the cache, which synchronously writes to the backing database before returning success. Guarantees consistency, but adds write latency.
Write-Behind (Write-Back)
Application writes to cache, which immediately acknowledges success and asynchronously flushes batches to the database. High write performance, but risks data loss if the node crashes before flushing.
| Cache Hit Rate | Incoming Read QPS | Cache Miss QPS (Hits Database) | Database Capacity Impact |
|---|---|---|---|
| 90.0% | 100,000 QPS | 10,000 QPS | Database must sustain 10,000 QPS |
| 98.0% | 100,000 QPS | 2,000 QPS | Database load reduced by 50x |
| 99.0% | 100,000 QPS | 1,000 QPS | Database load reduced by 100x |
| 0.0% (Cache Outage) | 100,000 QPS | 100,000 QPS | Database collapses instantly (100x traffic spike!) |
CACHE-ASIDE READ PATH (Lazy Loading with Probabilistic Early Refresh):
[Client] ---> 1. GET /product/123 ---> [API Gateway]
|
2. Query Cache (Redis)
|
+-------------------------+-------------------------+
| Cache Hit (< 1ms) | Cache Miss / XFetch Trigger
v v
[Return Cached Data] 3. Read Authoritative DB (PostgreSQL)
|
4. SET Key in Cache with TTL Jitter
|
5. Return DB Data to Client
SAFE WRITE PATH (Cache Invalidation on Mutation):
[Client] ---> 1. POST /product/123 ---> [API Gateway] ---> 2. Write & COMMIT in DB
|
3. DELETE Key from Cache (Invalidate)
(Never overwrite in cache directly to prevent races)3. The Four Deadly Caching Pathologies
- 011. Thundering Herd (Cache Stampede): A hot key cached by 20,000 RPS expires at t=0. All 20,000 requests experience a cache miss simultaneously and hammer the database with the exact same expensive query, crashing the DB.
- 022. Cache Penetration: Requests query non-existent keys (e.g.
GET /user?id=-9999or randomized UUIDs). The keys miss in cache and hit PostgreSQL. PostgreSQL returns NULL. Because nothing is cached, subsequent queries continue hammering PostgreSQL 100% of the time. - 033. Cache Avalanche: Millions of keys are populated during a midnight batch job with a uniform 24-hour TTL. At exactly 24:00:00, all keys expire simultaneously, diverting a tsunami of traffic to the database in the same second.
- 044. Hot Key Saturation: A celebrity with 50M followers posts an update. The key
feed:celebrityhashes to Redis Shard 3. Shard 3 receives 150,000 QPS, pinning its single-threaded CPU loop at 100% while Shards 1, 2, 4, and 5 sit idle at 2% CPU.
Core Interview Rule: Delete Cache Key, Never Update on Write
4. Evolved Defenses: XFetch Math, Bloom Filters & Leases
- 01XFetch Probabilistic Early Expiration: To eliminate cache stampedes without locking, readers evaluate: $-\delta \cdot \beta \cdot \ln(\text{rand}()) > (\text{expiry} - \text{now})$. Here, $\delta$ is computation time and $\beta$ is eagerness ($1.0$). As expiration nears, readers become increasingly likely to trigger an early refresh. It reduces synchronized expiry but does not guarantee that exactly one reader refreshes without additional coordination.
- 02Singleflight Mutex Locking: On cache miss, concurrent application threads coordinate via a local mutex or Redis lock so that only ONE thread queries the database; all other threads block and await the broadcasted result.
- 03Bloom Filter Penetration Shield: Place an in-memory Bloom filter at the ingress layer. Non-existent keys evaluate to 0 in bit positions and return HTTP 404 immediately (< 0.1ms), shielding both Redis and PostgreSQL.
- 04TTL Jitter for Avalanche Defense: Never use flat TTLs. Add random jitter: $\text{TTL} = \text{base} \pm \text{random}(0, 0.15 \times \text{base})$, spreading expirations across a uniform bell curve.
- 05Meta Invalidation Leases: Memcached issues a 64-bit lease token on miss. Writes back to cache succeed only if the lease remains unrevoked, preventing stale replica reads from overwriting newer writes.
Use it when
Deploy an L1 in-process cache (Caffeine) in front of an L2 distributed Redis cluster when individual hot keys exceed 20,000 QPS to prevent single-shard Redis CPU saturation.
Reconsider when
Avoid multi-tier L1/L2 caching when strict cross-node consistency is required, as L1 caches will hold stale data until local TTL expiration.
5. Eviction Policies & Decision Cheatsheet
| Policy | Memory Overhead | Hit Rate on Zipfian Loads | Resistance to Table Scan Pollution | Best Used For |
|---|---|---|---|---|
| LRU (Least Recently Used) | O(1) doubly-linked list pointers (~16B/entry) | Moderate (70–80%) | Zero (batch scans evict all hot keys) | General web API responses and user sessions |
| LFU (Least Frequently Used) | Frequency counters per key + buckets | High for static access | Poor (historical dead keys refuse to evict) | Static asset catalogs and long-lived metadata |
| Window TinyLFU (Caffeine / W-TinyLFU) | Small 4-bit Count-Min Sketch filter | State-of-the-Art (85–95%) | Near Perfect (evaluates admission frequency) | High-throughput JVM microservices and databases |
| Random Eviction | Zero memory overhead | Low (evicts active hot keys) | High (statistical immunity to sequential scans) | Uniform access patterns with memory constraints |
6. Active Recall Checkpoint
Active Recall Checkpoint
Why should an engineer delete a cache key after a database write rather than updating the cache value directly?
Hint: Think about out-of-order write races and database transaction rollbacks.
Show answer & explanation
Updating the cache directly creates two severe race conditions: 1) Out-of-order write race: Transaction A writes DB, then Transaction B writes DB. If B’s cache update arrives before A’s, the cache is left permanently stale with A’s old value. 2) Rollback phantom: If the cache is updated before the DB commits and the DB transaction aborts, the cache exposes uncommitted dirty data. Deleting the key after DB commit ensures future reads fetch authoritative committed state lazily, making the operation idempotent and self-healing.
Active Recall Checkpoint
What is Cache Penetration, and why does caching null values provide only partial protection compared to a Bloom filter?
Hint: What happens when an attacker requests millions of random, unique non-existent IDs?
Show answer & explanation
Caching null values only protects against repeated requests for the SAME non-existent key. If an attacker queries randomized IDs (e.g., random UUIDs), every request misses, queries the database, and stores a new null entry, exhausting Redis memory with useless keys. An ingress Bloom filter detects non-existence in O(1) time without allocating cache storage, rejecting queries before they ever touch Redis or the database.
Topic sizing snapshot
The four numbers that materially affect this architecture. Use them as bounds, not as a generic calculator embedded in every lesson.
Peak QPS
50,000 RPS read
5-Yr Storage
N/A (In-memory cache)
Bandwidth
5 Gbps cache network
Working Set RAM
128 GB Redis Cluster (80/20 Pareto)
Architectural Trade-Off Analysis
Compare latency, throughput, consistency, and operational complexity across core industry alternatives.
Architecture Decision Matrix
Multi-axis engineering evaluation and FAANG interview rules of thumb.
SQL (Postgres / MySQL)
Relational ACID Store
Structured schema, relational joins, ACID transactions, and strict foreign keys.
NoSQL (Cassandra / DynamoDB)
Distributed Non-Relational Store
Horizontal partition keys, denormalized documents/wide-columns, and tunable consistency.
| Evaluation Axis | SQL (Postgres / MySQL) | NoSQL (Cassandra / DynamoDB) | Details |
|---|---|---|---|
Latency | Moderate | Strong | |
Throughput | Moderate | Strong | |
Scalability | Moderate | Strong | |
Consistency | Strong | Moderate | |
Complexity | Strong | Moderate | |
Cost | Moderate | Strong |
When to Choose in an Architecture Interview
Choose SQL when ACID guarantees are non-negotiable (financial ledgers, payment processing, inventory checkout) or when query access patterns are unpredictable and require ad-hoc analytical joins.
Choose NoSQL when write volume exceeds single-node capacity (>20K writes/sec), data is unstructured/hierarchical (logs, telemetry, user feeds), or multi-region active-active replication is mandatory.
Never say "NoSQL is faster than SQL" without qualification. SQL with proper B-Tree indexes on indexed primary keys is lightning fast. NoSQL wins on horizontal write scaling, not inherent single-row read speed.
Production Postmortem & Verification
Production Incident Postmortem
- Trigger / Setup: A black friday sale key `deal:101` with an exact 60-minute TTL expires while 20,000 requests per second are reading it.
- Production Symptom: All 20,000 concurrent threads detect a cache miss simultaneously and hammer the MySQL database with complex queries, crashing the database within 500ms.
- Root Cause & Fix: Apply distributed singleflight mutexes or probabilistic early expiration (XFetch) so only one thread regenerates the cache while others wait or read stale data.
Acceptance Criteria & Outcomes
- Contrast Cache-Aside with Write-Through and Write-Back in terms of write latency and staleness.
- Demonstrate how a Bloom filter prevents Cache Penetration for non-existent database keys.
- Formulate TTL jitter strategies to prevent synchronized Cache Avalanche spikes.
Architectural & Technical Interview Review
Core FAANG Interview Questions
Q01What is a Cache Stampede (Thundering Herd) and how do you protect the origin database when a viral key expires?Click to reveal model answer →Hide answer ↑Request & Failure Flows
A cache stampede occurs when an intensely popular key (e.g. homepage newsfeed, flash sale item) expires from cache, and hundreds of concurrent incoming requests simultaneously experience a cache miss and hit the database at the exact same instant. Solve it with Mutex Locking (Single-Flight/Request Coalescing where only 1 worker queries DB while others wait), Probabilistic Early Expiration (XFetch algorithm), or Stale-While-Revalidate where stale data is served while background workers asynchronously refresh.
Q02Why is deleting a cache entry after committing a database transaction safer than updating the cache directly?Click to reveal model answer →Hide answer ↑Architecture Trade-offs
Updating the cache directly before or during a transaction risks race conditions: concurrent writes can interleave, leaving the cache populated with outdated state while the database commits newer state. Furthermore, if the DB transaction subsequently rolls back, the cache would contain uncommitted phantom data. Deleting the cache key after DB commit guarantees subsequent reads rebuild correct state from durable source of truth.
Q03How do you handle Cache Penetration when malicious users request non-existent keys (e.g. IDs that do not exist)?Click to reveal model answer →Hide answer ↑Requirements & Data Boundaries
Cache penetration bypasses the cache entirely and hammers the primary database. Mitigate it by: 1) Caching empty/null results with a short TTL (e.g. 60 seconds) so repeated misses hit RAM, and 2) Placing a Bloom Filter in front of the cache to immediately reject non-existent IDs without querying either Redis or the database.
Production Pitfalls & Anti-Patterns
Critical Failure Anti-Patterns
Cache Invalidation Race Conditions
Updating database and cache asynchronously without versioning or distributed locks can leave stale values cached indefinitely if an older update finishes writing after a newer update.
Production Mitigation: Invalidate/delete cache keys instead of updating them, and attach monotonic version timestamps to cached payloads.
Simultaneous Key Expiration Clumping
Setting the exact same TTL (e.g. 3600 seconds) on millions of items loaded in batch causes them to all expire at the exact same second, crushing the database.
Production Mitigation: Add random jitter to all TTLs (e.g. TTL = baseTTL + random(0, 300) seconds).
Unbounded Cache Growth and OOM Crashes
Writing without memory limits or eviction policies causes Redis to run out of RAM and crash or reject new writes.
Production Mitigation: Configure a strict maxmemory limit paired with an appropriate eviction policy such as allkeys-lru or volatile-lru.