Chapter 9: Caching — The Fastest Query Is the One You Never Run

Curriculum: Distributed Systems from First Principles Chapter: 9 of 24 Part: 4 — Performance Prerequisites: Chapter 1 (latency numbers), Chapter 2 (buffer pool), Chapter 7 (hot spots), Chapter 8 (consistent hashing) Estimated reading time: 80–90 minutes

Opening

From Chapter 1: reading 1 MB sequentially from RAM takes about 250 microseconds. Reading that same 1 MB from an SSD takes 1,000 microseconds. Reading it from a spinning disk takes 20,000 microseconds. Fetching it over a network adds another 500–10,000 microseconds depending on distance. These numbers have a single implication: if you already have the data in RAM, you have nothing to gain from going anywhere else to get it. The fastest possible response to any read request is one that never leaves RAM — one where the answer is already sitting in memory, computed and ready. This is what a cache does. It trades memory (cheap, fast) for reduced trips to storage (expensive, slow). Done correctly, a cache absorbs 90–99% of read traffic before it reaches the database, collapsing the effective load on your most constrained resource. Done incorrectly, a cache fails at the precise moment you need it most — during traffic spikes — and the ensuing flood of fallthrough requests to the database takes down the whole system. This chapter is about both sides: how to make caches work, and how they fail.

Part 1: What Caching Actually Is — The Physical Picture

Let's be concrete before we're abstract. A cache is a process running on a server (or a set of servers) that stores key-value pairs in RAM. When your application needs a piece of data, it first asks the cache. If the cache has it (a cache hit), the data is returned directly from RAM — no disk read, no database query, no network round trip to the database server. If the cache doesn't have it (a cache miss), the application fetches from the database, stores the result in the cache, and returns it. The next request for the same data finds it in cache.

The latency improvement from Chapter 1's numbers: a cache hit replaces a ~10ms database round trip with a ~0.5ms cache round trip — a 20× speedup. More importantly: the database doesn't see the request at all. If your cache has a 95% hit rate, your database receives only 5% of the read traffic it would otherwise handle. You can serve 20× the read throughput with the same database hardware.

The canonical application-tier cache is Memcached or Redis. Both are in-memory key-value stores. Redis additionally supports richer data types (sorted sets, hashes, streams), persistence to disk, replication, and Lua scripting. Memcached is simpler, multi-threaded, and sometimes faster for pure string key-value workloads. For a new system, Redis is almost always the choice — its richer feature set enables patterns (leaderboards, pub/sub, rate limiting) that Memcached can't serve.

The database's own buffer pool (Chapter 2) is also a cache — it caches pages from disk in RAM. The difference: the buffer pool only caches raw pages; it can't cache the results of complex queries or computed aggregations. An application-tier cache stores the final, application-ready result: a serialised User object, a fully joined Order with its line items, a pre-computed leaderboard. The application-tier cache removes both the database I/O and the database CPU.

Part 2: Cache-Aside — The Pattern Everything Else Derives From

There are several strategies for keeping cache and database in sync. The most common, and the one you should understand first, is cache-aside (also called lazy loading).

In cache-aside, the application owns the cache explicitly. It checks the cache, handles misses, writes through, and manages invalidation. The cache is a passive store — it never fetches data on its own.

The write path deletes from cache rather than updating. This is deliberate. An update would require the application to compute the new cached representation and write it atomically with the database write — two operations that are hard to keep consistent. Deletion is simpler and safer: after deletion, the next read repopulates the cache with whatever the database actually says, which is always correct.

This produces a brief window after a write where the cache has no entry for K. Any reads during that window miss and hit the database — acceptable, because the database has the fresh data.

-- Example: fetching a user profile
-- Application code (pseudocode)

function get_user(user_id):
    cached = redis.get("user:" + user_id)
    if cached:
        return deserialize(cached)          -- cache hit
    
    user = db.query("SELECT * FROM users WHERE id = ?", user_id)
    redis.setex("user:" + user_id, 3600, serialize(user))  -- TTL 1 hour
    return user

function update_user(user_id, new_data):
    db.execute("UPDATE users SET ... WHERE id = ?", user_id, new_data)
    redis.delete("user:" + user_id)         -- invalidate cache

Cache-aside is the right pattern for most read-heavy workloads because: it's simple to reason about, it doesn't pollute the cache with data that's never read (only accessed data gets cached), and it's fault-tolerant — if the cache is down, the application just reads from the database directly (with degraded performance, not hard failure).

The weakness: the first request for any key after a cold start or invalidation is always slow (it hits the database). In most systems this is acceptable. In systems where every request must be fast (financial trading, real-time gaming), you need a warming strategy — pre-populating the cache before it goes live.

Part 3: Write-Through and Write-Behind — When the Cache Writes First

Cache-aside puts the application in control. Two alternatives shift write responsibility to the cache layer itself.

Write-through

In write-through, the application writes to the cache and the cache synchronously writes to the database before acknowledging the write.

The advantage: reads are always fast — the cache always has the current value (no invalidation needed, no cold misses after writes). The disadvantage: writes are as slow as the database — the cache doesn't improve write latency because it must wait for the database. Also, data that is written but never read pollutes the cache unnecessarily (you write it to cache even if no one will ever read it, wasting cache capacity).

Write-through is best when reads and writes are roughly balanced and you need strong read-after-write consistency: after a write, every subsequent read from the same application instance sees the new value.

Write-behind (write-back)

In write-behind, the application writes to the cache and the cache acknowledges immediately. The cache writes to the database asynchronously, in the background, after some delay or batching.

The advantage: write latency approaches cache speed (~0.5ms) rather than database speed (~10ms). For write-heavy workloads — time-series data, counters, activity logs — this is a significant improvement. The disadvantage: the window between the cache write and the database write is a window of data loss. If the cache crashes, any unflucked writes are gone. The database lags behind the cache.

Write-behind is appropriate when: some data loss is acceptable (analytics counters, non-critical logs), write throughput is the bottleneck, and the workload tolerates eventual durability. It is inappropriate when: the data is critical (financial records, user passwords, order states), regulatory compliance requires durability guarantees, or the application assumes that a write success means the data is durable.

The naming is sometimes confused: "write-through" and "write-back" come from CPU cache terminology where write-back is the default mode on most modern processors (L1/L2/L3 caches write to RAM asynchronously). In distributed systems, the same trade-off appears but with much larger durability windows and much higher stakes.

Part 4: TTL and Eviction — How the Cache Decides What to Forget

A cache has finite RAM. It must discard some entries to make room for new ones. Two mechanisms control this: TTL (time-to-live) and eviction policies.

TTL — time-based expiration

Every cache entry is assigned a TTL: a duration after which it is considered expired and will be discarded. redis.setex("user:42", 3600, data) stores the value with a 3600-second (1 hour) TTL. After one hour, Redis automatically deletes the key. The next request is a cache miss and re-fetches from the database.

TTL is the primary tool for managing cache-database consistency when you can tolerate brief staleness. The correct TTL is a business decision: how stale can this data be before it causes user-visible problems?

A user's profile photo can be stale for an hour — nobody will notice a 1-hour lag between updating their photo and seeing it on other users' screens. A tweet's like count can be stale for 30 seconds — Twitter users accept eventual consistency on counts. A bank account balance cannot be stale at all — it must always be freshly fetched from the authoritative source.

Setting TTL too short: cache entries expire quickly, hit rate decreases, database receives more traffic. Setting TTL too long: cache entries stay stale longer, data consistency suffers. There's no universal answer — every cache entry type has its own appropriate TTL based on the business requirements.

Eviction policies — what to discard when cache is full

When the cache is full and a new entry must be added, the cache must evict (remove) an existing entry. The choice of which entry to evict is the eviction policy.

LRU (Least Recently Used): Evict the entry that was accessed longest ago. The intuition: if you haven't needed something recently, you probably won't need it soon. LRU is the most common policy and performs well for workloads where recent data is more likely to be requested again (temporal locality — which is most web application workloads).

LFU (Least Frequently Used): Evict the entry that has been accessed the fewest total times. Better than LRU for workloads where some items are persistently popular (always accessed frequently) and others are only temporarily popular. LFU remembers long-term popularity; LRU forgets after inactivity.

FIFO (First In First Out): Evict the oldest-inserted entry, regardless of access pattern. Simple but rarely optimal — an entry inserted long ago might still be heavily accessed.

Random: Evict a random entry. Surprisingly competitive with LRU in some workloads (if the access pattern has little temporal locality, LRU offers no advantage over random). Simpler to implement with lower overhead.

LIRS / ARC (advanced policies): More sophisticated policies that distinguish between "recently used once" (likely to not be needed again) and "frequently reused" (likely to be needed again). Redis implements an approximation of LRU rather than exact LRU — it randomly samples a small set of keys and evicts the least recently used among them. This approximation is very close to true LRU in practice with much lower overhead.

Redis configuration: maxmemory-policy controls the eviction policy. Common choices: allkeys-lru (evict any key using LRU when full), volatile-lru (only evict keys with TTLs set, using LRU), allkeys-lfu, noeviction (return error when full — dangerous in production).

Part 5: The Three Cache Failure Modes — When Caching Makes Things Worse

A cache is not just a performance optimisation — it is a critical component that, when it fails, can cause failures worse than if the cache had never existed. The three classic failure modes are cache stampede (thundering herd), cache avalanche, and cache penetration.

Before reading on, watch it happen. The first tab expires one hot key; the third expires forty at once. Predict first, then the next two sections explain what you saw.

Cache Stampede (Thundering Herd)

A popular cache key expires. In the same millisecond, 10,000 concurrent requests all check the cache, all find a miss, all simultaneously query the database for the same data, and all attempt to write the result back to cache simultaneously.

t=0: Key K expires from cache
t=1ms: 10,000 requests arrive, all find cache miss for K
t=2ms: 10,000 requests query database for K simultaneously
       → database receives 10,000 queries where it normally receives 10
t=3ms: Database is overwhelmed, query latency spikes
t=5ms: Application timeouts begin
t=10ms: Database connection pool exhausted
t=15ms: Application returns errors
t=20ms: All 10,000 requests return to cache with K's value (race condition)
        Multiple writes race to set K in cache simultaneously

The database, accustomed to serving 10 queries per second for key K (with caching), suddenly receives 10,000 queries per second for the same key. This is the thundering herd. The database can't handle it. Latency spikes, timeouts accumulate, the connection pool exhausts, and the application starts returning errors — at exactly the moment when the system was working fine before the cache entry expired.

Solution 1 — Mutex/Lock on cache miss: When a cache miss is detected, acquire a distributed lock before querying the database. Only the first request acquires the lock and fetches from the database; all other concurrent requests for the same key wait or return a stale value. After the first request populates the cache, the lock is released and all waiting requests find a cache hit.

function get_with_lock(key):
    value = cache.get(key)
    if value: return value
    
    lock_acquired = cache.set_nx("lock:" + key, 1, ex=5)  -- atomic "set if not exists"
    if lock_acquired:
        value = db.query(key)
        cache.set(key, value, ttl=3600)
        cache.delete("lock:" + key)
        return value
    else:
        sleep(50ms)                 -- wait for lock holder to populate cache
        return cache.get(key)       -- retry cache (should hit now)

Solution 2 — Probabilistic Early Expiration (PER): Instead of all requests discovering the expiry at the same moment, have each request probabilistically decide to refresh the cache slightly before it expires. Requests near the TTL boundary have a small probability of treating the cache as a miss and refreshing early — before all 10,000 concurrent requests hit the boundary simultaneously. This staggers the refresh, preventing the stampede.

Solution 3 — Stale-while-revalidate: Serve the stale value immediately while asynchronously refreshing the cache in the background. The client gets a fast (slightly stale) response. The background job updates the cache. No database stampede.

Cache Avalanche

A cache avalanche occurs when a large number of cache entries expire at the same time, causing a sudden flood of misses across many different keys.

Imagine you populate a cache at system startup and give every key a 1-hour TTL. One hour later, every single key expires simultaneously. The application, suddenly missing every key, floods the database with queries for all of them at once. The database, which was comfortably serving 5% of traffic (with 95% cache hits), instantly receives 100% of traffic. It collapses.

t=0:00  System starts. All keys written with TTL=3600s.
t=1:00  ALL keys expire simultaneously.
         → Cache hit rate: 0% (everything expired)
         → Database receives 100% of read traffic
         → Database overwhelmed → system down

Solution 1 — TTL jitter: Instead of TTL = 3600, use TTL = 3600 + random(-300, 300). This spreads expirations across a 10-minute window rather than a single moment. The thundering herd is smoothed into a gentle increase in database load.

Solution 2 — Staggered warming: When populating the cache at startup, don't write all keys with the same TTL. Write different data categories with different TTLs, or write them in batches with small delays.

Solution 3 — Circuit breaker on the database: When cache miss rate spikes suddenly (a potential avalanche signal), a circuit breaker stops forwarding requests to the database and returns stale data or a fallback response. Better to return slightly stale data for 30 seconds while the cache repopulates than to crash the database.

Cache Penetration

Cache penetration is an attack (or programming error) where queries are made for keys that don't exist in either the cache or the database.

If a request comes in for user_id = 99999999 and no such user exists, the cache returns a miss, the application queries the database, the database returns empty, and nothing is written to cache (because there's nothing to write). The next identical request misses the cache again, queries the database again, and the cycle repeats. If an attacker sends millions of requests for non-existent user IDs, every single one bypasses the cache and hits the database.

Solution 1 — Cache negative results: When the database returns empty, write a "null" or "does not exist" sentinel value to the cache with a short TTL. redis.setex("user:99999999", 60, "NULL"). The next request for the same non-existent key finds the sentinel in cache, skips the database, and returns the appropriate "not found" response. TTL is short because a user might sign up and the "null" entry should expire.

Solution 2 — Bloom filter: Before querying the cache or database, check a bloom filter — a probabilistic data structure that answers "definitely not in set" or "probably in set." If the bloom filter says the user_id definitely doesn't exist, return "not found" immediately without touching the cache or database. Bloom filters have zero false negatives (if it says "not present," the key truly isn't there) and a configurable false positive rate (sometimes says "probably present" for absent keys — those still hit the database, but the false positive rate is tunable).

Two operational catches interviewers probe: every new key must be added to the filter at write time (or a brand-new user is told "not found" — a false negative you created yourself), and a plain bloom filter cannot delete — removing a key would clear bits shared with other keys. Deleted keys therefore stay "probably present" until you rebuild the filter periodically, or you use a counting bloom filter (or a cuckoo filter), which supports deletion at the cost of more memory.

This is particularly powerful for defending against targeted cache penetration attacks, where an adversary specifically crafts requests for keys that don't exist. The bloom filter is fast (O(k) hash computations, where k is the number of hash functions, typically 3–7) and memory-efficient (a bloom filter for 1 billion items with 1% false positive rate requires only ~1.2 GB of RAM).

Part 6: Cache Consistency — The Hardest Problem

Chapter 6 established that consistency is a spectrum. Caching sits firmly toward the "eventual" end of that spectrum. A cache is, by definition, a potentially stale copy of the authoritative data. Managing how stale it is, and whether staleness matters for your use case, is the central challenge of cache design.

The read-your-own-write problem

Alice updates her profile bio. The application writes to the database and deletes the cached profile. Alice immediately refreshes the page. The request hits a read replica (Chapter 5) that hasn't yet received the update from the primary. The replica's stale data is written to cache. Alice sees her old bio.

This is the read-your-own-write consistency violation. It's the intersection of replication lag (Chapter 5) and cache invalidation. The solution: for a brief window after writing, route reads for the same key to the primary rather than replicas, bypassing cache. Once the replica has caught up (typically within a second), normal cache reads resume. This is session-level read-your-own-write consistency.

Cache invalidation is hard

The famous quote attributed to Phil Karlton: "There are only two hard things in Computer Science: cache invalidation and naming things." The hardest part isn't the mechanics of invalidating a key — that's one Redis DEL command. The hard part is knowing when to invalidate.

Consider a social feed: when user Alice posts a new photo, which cached feeds need to be invalidated? Every one of Alice's followers' feeds. If Alice has 10,000 followers, and each follower's feed is a separate cache entry, a single post triggers 10,000 cache invalidations. At scale (Twitter-level: 100M users, some with millions of followers), this fan-out invalidation becomes its own distributed systems problem.

The industry-standard solution for social feeds: don't cache pre-computed feeds. Instead, cache individual posts and user data separately, and compute the feed on read from individual cached components. Each user's feed is assembled at read time from cached posts of the people they follow. The cache invalidation problem becomes: when Alice posts, invalidate her post list (one key). Feed computation is fast because it reads from in-cache individual components, not from the database.

Distributed cache consistency

When multiple application instances share a cache, a write from Instance A must invalidate the cache entry visible to Instance B. With a centralised cache (Redis), this is automatic — all instances share the same cache, and when Instance A deletes a key, Instance B's next read misses and re-fetches. This is the standard model.

The problem arises with local in-process caches (hashmaps in application memory). Each application instance has its own local cache. A write from Instance A deletes Instance A's local cache entry but has no knowledge of Instance B's or Instance C's local caches. Those instances continue serving stale data until their TTLs expire.

Local caches are faster (no network hop to Redis) but harder to invalidate correctly. The typical approach: use a very short TTL (seconds to tens of seconds) for local caches, and accept brief staleness. Use a pub/sub channel (Redis pub/sub, or a message queue) to broadcast invalidation events when writes occur — Instance A publishes "user:42 updated" to a channel; all instances subscribed to that channel delete their local copy of user:42.

Part 7: Solving the Celebrity Problem — Tiered Caching

Chapter 7 introduced the celebrity problem: a single shard receives overwhelming read traffic because a popular item (a celebrity's post) is on that shard. Consistent hashing (Chapter 8) doesn't help — it consistently routes all reads for that key to the same node.

The solution is tiered caching — multiple cache layers, each closer to the client, each absorbing more of the traffic before it reaches the next layer.

For the celebrity post, the CDN absorbs almost all reads worldwide. Only cache misses (first views, content updates, expired entries) reach the Redis layer. The database primary sees only writes and the occasional read on cache miss. The hot shard problem is neutralised by never letting most requests reach the shard in the first place.

The CDN introduces a new consistency trade-off: CDN caches can be hard to invalidate globally. When a post is deleted or edited, the CDN across 200+ points of presence must be purged. CDN providers offer programmatic cache invalidation APIs, but global purges can take seconds to minutes to propagate. This is why edit windows exist on platforms like Twitter/X — "you can edit within 30 minutes" — the window buys time for the CDN TTL to expire and for edited content to propagate.

Part 8: Redis Data Structures — Beyond Simple Key-Value

Redis is often described as a "key-value store," which dramatically undersells it. The values in Redis can be one of several data structures, each enabling patterns that a simple string cache cannot serve.

Sorted sets (ZSET): A set of members, each with an associated floating-point score, kept in sorted order by score. Operations: add a member with a score (ZADD), get members in score range (ZRANGEBYSCORE), get rank of a member (ZRANK). The canonical use case is a real-time leaderboard: ZADD leaderboard 9823 "user:42" sets user 42's score to 9823. ZREVRANGE leaderboard 0 9 returns the top 10 users in descending order. Redis maintains a skip list internally for O(log N) insertions and range queries.

Hashes: A hash is itself a key-value map stored as the value of a Redis key. HSET user:42 name "Alice" email "alice@example.com" score 9823. This stores a user object as a hash. You can update individual fields (HSET user:42 score 9824) without fetching and re-serialising the entire object. Useful for objects with many fields where you frequently update individual fields.

Sets: Unordered collections with O(1) membership testing and set operations (union, intersection, difference). Use case: tracking which users have seen a notification (SADD seen:notification:789 user_id), finding mutual friends (SINTER friends:alice friends:bob).

Lists: Ordered sequences supporting push/pop from both ends in O(1). Use case: activity feeds (append new events to a list, read the last N), producer-consumer queues (producers LPUSH, consumers BRPOP — blocking pop that waits if the list is empty).

HyperLogLog: A probabilistic data structure for counting distinct elements with a fixed memory footprint of 12 KB regardless of the number of distinct elements. PFADD visitors:today user_id adds a user visit; PFCOUNT visitors:today returns an approximate count of unique visitors with ~0.81% standard error. Used for: daily active user counts, unique IP tracking, impression counting. You cannot get exact counts from a HyperLogLog — that's the trade-off for using 12 KB instead of gigabytes.

Streams: A persistent, append-only log supporting consumer groups (multiple consumers reading different portions of the stream). Redis Streams are a simplified Kafka-like message queue built into Redis. Useful for: event sourcing at moderate scale, real-time notification delivery, activity logs.

These data structures make Redis a multi-purpose operational data store, not just a cache. A well-designed system might use Redis for: user session storage (hash), rate limiting counters (string with INCR), real-time leaderboards (sorted set), unique visitor counts (HyperLogLog), job queues (list), and notification delivery (pub/sub) — all in addition to its core use as a cache.

Part 9: When Not to Cache

Caching introduces complexity (invalidation, consistency, failure modes) and a new failure surface. Not every data access pattern benefits from a cache.

Don't cache if your hit rate will be very low. If your access pattern has no temporal locality — every request is for a different key that will never be requested again — a cache adds latency (the miss overhead) with no benefit. Batch analytics jobs scanning billions of unique records are the canonical example: every row is read once, the cache is always cold, and caching only adds overhead.

Don't cache highly volatile data with strict consistency requirements. If data changes every second and reads must always see the latest value, a cache with any TTL greater than 1 second is counterproductive. The cache adds complexity without improving consistency — and the invalidation machinery itself becomes the bottleneck.

Don't cache when the database is fast enough. If your database query returns in 2ms with a warm buffer pool (Chapter 2) and your SLA requires 50ms response times, caching adds complexity without meaningfully improving outcomes. Profile first. Cache only what's slow.

Don't cache across a consistency boundary you can't manage. If two services share a database but have separate caches, and Service A writes to the database, Service B's cache is now stale with no mechanism to invalidate it. Cache invalidation across service boundaries is extremely difficult. Each service should cache only data that it owns and writes. For data owned by another service, call that service's API (which manages its own cache) rather than caching the response yourself without an invalidation mechanism.

Vocabulary Map

Practice Problems

Problem 1 — Failure Analysis

Your Redis cache has 10 million keys, all set with a TTL of exactly 3,600 seconds (1 hour). The cache was cold-started at 09:00. At 10:00, all 10 million keys expire simultaneously (cache avalanche).

Your application normally handles 50,000 requests per second with a 97% cache hit rate. The database can handle 5,000 queries per second at acceptable latency (<50ms). Calculate: at 10:00, how many queries per second hit the database? How long until the cache is repopulated (assume each database response is cached and takes 5ms, and requests are uniformly distributed across all 10 million keys)? During the repopulation window, what percentage of requests get unacceptable latency?

Now design the fix: rewrite the cache population code using TTL jitter. What range of jitter values would spread the expiration over a 30-minute window? After your fix, what is the maximum queries-per-second spike to the database during the re-expiration window?

Problem 2 — Design from Scratch

Design the complete caching strategy for a Twitter-like social feed. The system has: 500 million users, 100 million daily active users, 500 million tweets per day, average user follows 300 accounts. The most common operations: post a tweet, load a user's home feed (last 100 tweets from followed accounts), view a user's profile.

For each operation, specify: what data to cache, what the cache key is, what TTL to use, what invalidation strategy to use, and which failure modes you must defend against. Pay particular attention to: a celebrity with 50 million followers posts a tweet (fan-out problem), a user's first tweet load after cold start (cache miss cascade), and a user editing a tweet (invalidation across multiple cache layers). Which operations are safe to cache with eventual consistency, and which require read-your-own-write guarantees?

Problem 3 — Synthesis

Connect caching to Chapter 5's replication lag and Chapter 6's consistency models.

Your write path: application writes user data to the Postgres primary. Your read path: application reads user data from a read replica (the primary is for writes only). You cache read results in Redis with a 5-minute TTL.

Trace the full staleness chain: a user updates their bio. The primary commits the write. The WAL record is sent to the replica. Replica apply lag is currently 2 seconds. The cache TTL for this user's profile is 4 minutes remaining.

How stale can the data served to a different user be in the worst case? In the best case? Draw the timeline showing: primary commit time, replica apply time, cache invalidation time (assuming write-path deletes from cache), and the window during which reads return stale data. Now introduce a bug: the write path forgets to delete from cache after writing to the primary. What consistency model does the system now provide to users reading the stale user's profile? How long is the staleness window? What is the correct fix and why is "just shorten the TTL" not a complete answer?

Problem 4 — Go Deeper

Redis uses an approximation of LRU rather than exact LRU. Exact LRU requires maintaining a doubly-linked list of all keys sorted by access time — O(1) access update, O(1) eviction, but O(N) memory overhead (each key needs prev/next pointers). Redis instead randomly samples 5 keys (configurable via maxmemory-samples) and evicts the least recently used among those 5.

From first principles: what is the expected quality of this approximation? If the cache has 1 million keys and you sample 5, what is the probability that your 5-sample pool contains the actual globally least-recently-used key? How does increasing the sample size from 5 to 10 to 50 improve accuracy? At what sample size does the approximation become practically indistinguishable from true LRU? What is the fundamental trade-off that makes Redis choose approximation over exactness — connect this to Chapter 1's memory hierarchy and the cost of pointer chasing in a doubly-linked list across potentially non-contiguous memory pages.

Problem 5 — Connect to Previous Chapters

Connect the bloom filter (cache penetration defence) to Chapter 3's index selectivity and Chapter 8's consistent hashing.

A bloom filter for a cache with 100 million keys uses 1% false positive rate. Memory required: ~120 MB (about 9.6 bits per key, with 7 hash functions — from m = −n·ln(p) / (ln 2)²). False positive rate means: 1% of requests for non-existent keys will be told "probably in set" and will still hit the database (but genuine misses are ~1% of total traffic, so this is rare).

First: connect this to Chapter 3's selectivity. A low-selectivity index on a boolean column has many duplicate values — the index is useless because too many rows match any given value. A bloom filter with high false positive rate is similarly useless — too many non-existent keys pass through to the database. What is the structural similarity between "selectivity of an index" and "1 - false_positive_rate of a bloom filter"? Both answer the same fundamental question — state it precisely.

Second: connect to Chapter 8's consistent hashing. A distributed cache with 8 nodes uses consistent hashing to partition keys. You want a bloom filter to protect against cache penetration. Do you use one global bloom filter (on the router/proxy) or per-node bloom filters? Trace the exact request path for a non-existent key in both architectures. What is the failure mode if you use per-node bloom filters and the routing layer sends a request to the wrong node (e.g., during a rebalancing event when the ring is inconsistent)?

What's Coming Next

You now have the full performance stack for reads: indexes (Chapter 3) speed up database queries, replication (Chapter 5) distributes reads across replicas, caching (this chapter) eliminates most database reads entirely, and tiered caching with CDNs eliminates even the application-tier cache for the hottest content. But all of this has focused on read-heavy workloads. What happens when writes are the bottleneck? Traditional B-Tree storage (Chapter 2) is optimised for reads — it pays a write amplification penalty to maintain sorted order. Chapter 10 introduces LSM Trees (Log-Structured Merge Trees): a fundamentally different storage engine that flips the trade-off, optimising for write throughput at the cost of read performance. LSM Trees power Cassandra, RocksDB, LevelDB, and parts of HBase — the storage engines behind many of the high-write distributed systems you've been reading about since Chapter 4.

Chapter 9 complete. Problem 2 (Twitter feed caching strategy) is the most valuable for interviews — it's a complete system design sub-problem that appears verbatim in FAANG interviews as a component of larger designs. Problem 3 (staleness chain through replication + cache) is the most technically dense — trace it with an actual timeline and specific timestamps before moving on. The connection between read-your-own-write consistency and replication lag is one of the most common sources of real production bugs.