Day 02 · System Design
Caching Strategies & Invalidation Patterns
How in-memory caches speed up reads, the main read/write patterns, and how to keep a cache consistent with the source of truth.
01Overview & core concept
A cache is a high-speed data storage layer (typically in-memory RAM) that stores a subset of transient data, serving subsequent read requests significantly faster than querying the primary persistent storage (e.g., disk-based relational databases). Caching improves read throughput and reduces end-to-end latency, but it introduces the challenge of keeping the cache consistent with the source of truth.
Faster reads
Serving hot data from RAM avoids disk I/O, joins, and index lookups on the primary database.
Synchronization cost
Every cache adds a second copy of the data, so you must decide how and when it is updated or invalidated.
02Architecture & request flow
┌──────────────────────┐
│ Application │
└──────┬────────┬──────┘
│ │
1. Check Cache │ │ 2. Cache Miss: Query DB
(Cache-Aside) │ │ 3. Populate Cache
▼ ▼
┌────────────┐ ┌─────────────────┐
│ In-Memory │ │ Primary DB │
│ Cache │ │ (Source of Truth│
│ (e.g. Redis│ │ e.g. Postgres) │
└────────────┘ └─────────────────┘Core write & read strategies
Cache-Aside (Lazy Loading)
Read: the application queries the cache; on a miss it queries the database and writes the result back to the cache. Write: the application writes directly to the database, then invalidates (deletes) or updates the corresponding cache key.
Read-Through / Write-Through
The application treats the cache as the primary data store. The cache itself is responsible for reading from, or synchronously writing to, the underlying database before acknowledging success.
Write-Behind (Write-Back)
The application writes solely to the cache. The cache asynchronously batches and persists writes to the database in the background. Highly performant for write-heavy workloads, but risks data loss if the cache node crashes before flushing.
Eviction policies
LRU (Least Recently Used)
Evicts items that have not been accessed for the longest time.
LFU (Least Frequently Used)
Evicts items with the lowest access count.
FIFO / TTL (Time-To-Live)
Evicts items after a fixed duration or in first-in-first-out order.
03Real-world example: Meta (Facebook) Scaling Memcached
Look-Aside Architecture
Facebook uses Memcached as a demand-driven look-aside cache alongside MySQL.
Leases to Prevent Cache Stampedes
When a cache miss occurs, Memcached issues a short-term "lease" token to the requesting client. Only the client with the lease may query MySQL and repopulate the cache, preventing thousands of concurrent web servers from querying the database for the same missing key.
Invalidation via Transaction Logs (McScribe / Wormhole)
MySQL commits trigger invalidation daemons that read the replication binlog and broadcast cache invalidation events to remote Memcached clusters asynchronously.
04Architectural trade-offs
| Dimension | In-Memory Cache (e.g., Redis) | Database Querying |
|---|---|---|
| Latency | Sub-millisecond (RAM). | 5–50+ milliseconds (disk I/O, joins, indexes). |
| Throughput | 100k+ operations/sec per node. | Limited by connection pools and disk bandwidth. |
| Consistency | Eventual consistency; stale reads can occur during concurrent updates. | Strong ACID consistency (if configured). |
| Cost | High cost per gigabyte (RAM). | Low cost per gigabyte (SSD/HDD). |
Failure modes & mitigations
Cache Stampede (Thundering Herd)
High concurrency on an expired key causes thousands of requests to hit the database simultaneously. Mitigation: mutex locks, probabilistic early expiration (XFetch), or background cache warmers.
Cache Penetration
Requests query keys that exist in neither the cache nor the database, continually bypassing the cache. Mitigation: cache null/empty values with short TTLs, or place a Bloom Filter in front of the cache.
Cache Avalanche
Many keys expire at the exact same second, or a cache cluster crashes, overwhelming the backend. Mitigation: add random jitter to TTL values (e.g., TTL = base_ttl + rand(0, 300)) and use clustered replication.
05Interview question & approach
How would you design a leaderboard system for an online gaming platform with 10 million active users that provides real-time top-100 rankings and user rank lookups?
Data Structure Selection
Propose Redis Sorted Sets (ZSET), which internally use a skip list and hash map (O(log N) inserts and rank lookups).
Read/Write Flow
Score updates: ZADD user_scores <score> <user_id> directly against Redis, with an asynchronous write to a persistent SQL database for audit logs. Top-N: ZREVRANGE 0 99 WITHSCORES fetches the top 100 players in sub-millisecond time. Individual rank: ZREVRANK user_scores <user_id>.
Partitioning & Sharding
If 10M active players exceed single-node memory/CPU bandwidth, shard the leaderboard by region/game-mode or tier partitions (e.g., rank ranges).
Resilience & Warmup
Explain how to reconstruct the Redis Sorted Set from database snapshots and write-ahead logs if a cache instance crashes.