Caching, System Design Masterclass

Name: System Design Masterclass
Availability: InStock

The Secret Behind Every Fast Website

Here's a number that should bother you: reading from a database takes about 1-10 milliseconds. Reading from an in-memory cache takes about 0.1 milliseconds. That's 10-100x faster.

Now multiply that by thousands of requests per second. If your API makes 5 database queries per request and you're handling 10,000 requests per second, that's 50,000 database queries per second. Your database is crying. Your users are waiting. Your cloud bill is growing.

But here's the thing. A large share of those queries are asking for the exact same data. Ten thousand people loading your homepage are all fetching the same featured products, the same trending posts, the same navigation menu. Yet your database dutifully executes the same query 10,000 times, returning the same result each time.

How large a share depends entirely on your traffic, and anyone who quotes you a single percentage for every application is guessing. What is not a guess is the shape: on almost every read-heavy site, a small number of items are requested enormously more often than the rest. That skew is what makes caching work at all.

Caching says: "Why not do that work once, store the result somewhere fast, and serve it from memory for the next 9,999 requests?"

This isn't a nice-to-have optimization. It's a fundamental architecture pattern, and the companies you use every day depend on it completely. Netflix's cache layer alone absorbs upwards of 30 million requests every second at peak. Facebook built a system called TAO whose own paper says it processes a billion reads a second. Both numbers are in the last slide of this lesson, with their sources.

Take those two figures seriously for a moment. Every one of those reads that the cache answers is a read the database never sees. Remove the cache and that traffic does not disappear, it lands somewhere else.

What Is Caching?

Caching is storing a copy of data in a faster storage layer so future requests for that data can be served without going to the slower original source.

The analogy that makes this click: imagine you're a librarian. Someone asks you for a popular book. You walk to the back of the library, find it on the shelf (10 minutes), bring it to the front desk. Five minutes later, someone else asks for the same book. Do you walk all the way to the back again?

No. You keep a copy on a shelf behind the front desk. Next time someone asks, you grab it in 5 seconds instead of 10 minutes.

That shelf behind the front desk? That's your cache.

In software, the "slow source" is usually a database, an external API, or an expensive computation. The "fast copy" lives in memory (RAM), either on the same server (local cache) or on a dedicated caching server like or Memcached.

Storage Tier	Speed	Cost	Capacity
CPU Cache (L1/L2)	~1 nanosecond	$$$$$	Kilobytes
RAM (application memory)	~100 nanoseconds	$$$$	Gigabytes
In-memory cache (Redis)	~0.1 millisecond (+ network)	$$$	Gigabytes-Terabytes
SSD (database storage)	~0.1-1 millisecond	$$	Terabytes
Hard Drive (HDD)	~5-10 milliseconds	$	Petabytes
Network call (API)	~10-200 milliseconds	$	Unlimited

Caching is fundamentally a trade-off: you sacrifice freshness and memory for speed. The cached data might be slightly stale (more on that soon), and you're using RAM to store it, but the performance gain is dramatic.

Cache Hit vs Cache Miss

The two fundamental paths through any caching system, and understanding these is the key to designing effective caches.

The Cache Hierarchy. Closer Is Faster

Caches exist at every level of a system, from the CPU to the edge. Each layer trades capacity for speed. Understanding this hierarchy helps you decide where to cache what.

Caching Strategies. Where to Cache

Caching isn't one thing, it happens at multiple layers of your system, and each layer serves a different purpose.

Browser Cache

The user's browser stores static assets (CSS, JavaScript, images) locally. When they revisit your site, the browser serves these from disk instead of downloading them again. Controlled via headers like Cache-Control: max-age=31536000. Cost: free. Impact: massive.

CDN Cache

A Content Delivery Network caches your content at edge servers around the world. A user in Tokyo gets your files from a server in Tokyo, not from your origin server in Virginia. CloudFront, Cloudflare, and Fastly are popular choices. This is the single most effective caching layer for static and semi-static content.

There is a second layer inside a that people miss, and it changes the arithmetic completely.

A funnel in three bands drawn to the share of traffic that survives to each. The top band, Tier 1 Edge PoPs, is full width and labelled 100 percent of requests arrive here, carrying the real logos of Cloudflare with 310 plus PoPs, CloudFront with 600 plus edges, Fastly and Akamai. It narrows into a middle band, Tier 2 Regional shield, labelled one shield per region with a note that 50 PoP misses collapse into 1. That narrows again into a small band at the bottom, Tier 3 Origin, labelled 2 to 5 percent of total traffic and marked your server. — ArchitectureFigure 2. Each band drawn to the traffic that reaches it
A miss at the edge does not go straight to you. It goes to a regional shield, and every edge in that region shares it, so fifty separate misses for the same object collapse into a single request to your server. The bands are drawn to scale on purpose: by the time traffic reaches the bottom, a well configured CDN is passing you only a few percent of what arrived. Cloudflare's own figure for turning the shield on is a 60 to 90 percent cut in origin traffic.

The Hardest Problem in Caching

There's a famous saying in computer science: "There are only two hard things in computer science: cache invalidation and naming things." Phil Karlton said that, and every engineer who's dealt with stale cache data knows exactly what he meant.

Cache invalidation is the problem of knowing when your cached data is outdated and needs to be refreshed.

You cache a product price at $49.99. The product team changes it to $39.99 in the database. But your cache still says $49.99. Users see the wrong price. If they buy, do they pay the cached price or the real price? Either way, someone's unhappy.

There are three common approaches:

Time-To-Live (): Every cached item has an expiration time. "Cache this for 60 seconds, then fetch fresh data." Simple, predictable, but the data can be stale for up to the TTL duration. If your TTL is 5 minutes, a price change takes up to 5 minutes to reflect.

TTL	Best For	Staleness Risk
5 seconds	Real-time dashboards	Very low
60 seconds	API responses, session data	Low
5 minutes	Product catalogs, search results	Moderate
1 hour	Blog posts, configuration	Low impact

Cache-Aside vs Read-Through vs Write-Through

These are the three fundamental caching patterns. Interviews love asking about them because they reveal whether you understand the trade-offs, not just the concept.

Cache-Aside (Lazy Loading) The most common pattern. Your application code is responsible for the cache:

Check the cache. If data exists (hit), return it.
If data doesn't exist (miss), fetch from database.
Store the result in cache.
Return the data.

The cache only gets populated when someone actually requests the data. This means cold starts can be slow (every first request is a miss), but you only cache data that's actually being used, no wasted memory on data nobody's requesting.

SketchFigure 9. Cache-aside, drawn the way you would on a whiteboard

Follow the arrows and notice who is doing the work: the application. It talks to the cache, and separately it talks to the database. and the database never speak to each other at all, and neither knows the other exists.

That is what makes cache-aside simple to reason about and simple to get subtly wrong. Your code owns every decision, including the one in step 5, which is the step the next figure turns into a bug.

Caching Patterns Compared

Cache-Aside, Read-Through, and Write-Through each make a different trade-off between freshness, complexity, and performance. This side-by-side view captures the decision that matters in practice.

Caching Gotchas That Burn Teams

Cache stampede (thundering herd). A popular cache key expires. Suddenly, thousands of concurrent requests all miss the cache at the same instant and all hit the database together. Your database buckles under the sudden load. The fix: lock the cache key so only one request fetches from the database while the others wait, or use "stale-while-revalidate", serving the slightly stale data while refreshing in the background.

Two isometric blocks drawn to scale against each other. A small flat green slab is labelled about 500 per second, what the table was built for. Beside it a tall red column many times its height is labelled 4,000 queries inside 200 milliseconds. A line beneath reads that only one of them was needed and the other 3,999 compute the identical answer. — IsometricFigure 12. One key expires, four thousand queries arrive
The two blocks are the same table in the same second. The short one is the load it was sized for. The tall one is what actually lands the moment a popular key expires.
The detail that makes this maddening is at the bottom: every one of those queries is computing the same answer. One of them was necessary. The other 3,999 are duplicated work that arrives as a spike precisely when you can least absorb it.
That is why the fix is not a bigger database. It is making sure only one request does the work while the rest wait for it.

A sequence diagram with three lifelines: Request A which arrives first, the cache, and Requests B to Z which arrive microseconds later. Request A asks for the popular key and misses, then sets a short lock on it. Requests B to Z ask for the same key, miss, but find the lock held and wait rather than querying. Request A writes the fresh value, and the cache then returns it to everyone who was waiting.

How the Giants Cache

Facebook / Meta built TAO (The Associations and Objects cache) because even Memcached wasn't enough on its own. TAO caches the social graph: who is friends with whom, who liked what, who posted where. Their paper, published at USENIX ATC in 2013, states that TAO "can process a billion reads and millions of writes each second", running on thousands of machines over many petabytes of data.

That is the paper's own sentence, and it is worth quoting exactly rather than rounding up. A billion reads per second is already an extraordinary number, and "billions" is a different claim that the paper does not make.

Twitter uses extensively for caching timelines. When you open the app, your timeline is not assembled on the spot by querying hundreds of accounts you follow. It was computed earlier and cached. When someone you follow posts, that post is pushed into the cached timeline of each of their followers, a pattern called fan-out-on-write.

The trade is worth naming, because it is the reason this comes up in interviews. Fanning out on write makes reads cheap and writes expensive: one post by an account with a million followers becomes a million cache updates. That is fine until the account has a hundred million followers, which is why the very largest accounts are usually handled a different way and merged in at read time.

Netflix uses EVCache (built on Memcached) across their . They cache user profiles, playback positions, recommendation results, and much else. Their own engineering writing puts EVCache at upwards of 30 million requests per second at peak, across tens of thousands of Memcached instances, with typical hit rates above 99%.

Note the hit rate. Ninety-nine percent means that for every hundred reads, ninety-nine never reach a database at all. That is what people mean when they say a cache is load-bearing infrastructure rather than an optimisation.

Stack Overflow is the useful counterexample, because they went the other way. They cache aggressively in local memory on each web server rather than reaching for a shared Redis or Memcached tier, and they have written publicly about running the whole site on a famously small number of very powerful machines.

That works for them for a specific reason, and it is the reason worth taking away: their most-cached data is the same for everyone. A rendered question page does not differ per user, so ten servers each holding their own copy wastes some memory and creates no correctness problem. The moment your cached data is per-user, that arithmetic inverts and a shared cache wins.

Quick Check

Knowledge Check

4 questions - Score 80% to pass

Your cache has a TTL of 5 minutes. A product price changes in the database. What's the worst-case scenario for how long users see the stale price?

A popular cache key expires at exactly 12:00:00. 5,000 requests arrive simultaneously, all requesting that key. What problem might occur?

You're choosing between local application cache (in-memory HashMap) and a distributed cache (Redis). Which factor would make you choose Redis?

Which caching pattern would you choose for data that is read 1000x per second but updated once per hour?

An isometric stack of five slabs, smallest at the top and largest at the bottom, each labelled with its latency: L1 and L2 CPU cache at 1 nanosecond, L3 CPU cache at 10 nanoseconds, application RAM at 100 nanoseconds, Redis as the shared cache at 0.1 milliseconds, and the database at 1 to 10 milliseconds. Each slab is drawn wider and deeper than the one above it to show that each step down holds far more data. A note underneath says the CDN is not on this ladder because it is measured as a round trip from the user rather than as access time from the server. — IsometricFive tiers on one axis, drawn to scale
Every slab is a place your data can live. The higher a slab sits, the faster you reach it and the smaller it is. The top slab, the CPU cache, answers in about a nanosecond and holds almost nothing. The bottom slab, the database, takes about a million times longer and holds everything. That trade is why caching is a design decision instead of a switch you flip: you are choosing what is small and hot enough to earn a place near the top.
The CDN is missing on purpose. It belongs in the hierarchy, just not on this axis. Every tier here is measured as how long the server waits to read the data. A CDN number, the familiar 5 to 50 milliseconds, is measured as how long a user's request takes to reach the nearest edge and come back. Put both on one ladder and the picture starts arguing with itself, because a 5 to 50 millisecond CDN would look slower than a 1 to 10 millisecond database, which is nonsense: a CDN hit means the database is never touched at all. The CDN is about distance. This figure is about depth.

Your application server stores frequently accessed data in its own memory. A Python dictionary, a Node.js Map, a Java HashMap. Blazing fast (no network hop), but the cache is per-server, if you have 10 servers, each one builds its own cache independently, which means wasted memory and potential inconsistencies.

A dedicated caching server (or cluster) that all your application servers share. is the most popular choice. It sits between your application and your database, and all servers read from and write to the same cache. This solves the consistency problem of local caches, everyone sees the same cached data.

Two approaches side by side, both showing the same 100 keys and the same change of three servers becoming four. On the left, labelled modulo hashing with the formula hash of key modulo server count, a ten by ten grid of 100 squares has about 75 of them coloured red to mark keys that moved, with a note that about 75 of 100 keys land on a different server and every one is a miss. On the right, labelled consistent hashing, a ring is drawn with four server points on it and one short arc highlighted in red between two of them, labelled only this arc moves, about 25 keys. Real logos for Redis Cluster, Cassandra and DynamoDB sit below the ring. — ArchitectureFigure 5. The same change, under two different rules
Picking a server with `hash(key) % server_count` works perfectly until the count changes. Add one server to three and the divisor becomes four, so nearly every key computes a different answer: about 75 of these 100 keys move, and every one of those is now a miss that has to be refetched from the database, all at once.
puts servers at points on a ring and walks each key clockwise to the next one. Adding a server only steals the arc behind it, so only about 25 keys move and the rest never notice. At three servers that is 75 against 25; at a hundred servers, adding one moves roughly one percent. That widening gap is the entire reason the ring exists, and it is why Redis Cluster, Cassandra and DynamoDB all use it.
One detail worth carrying: each server sits at around 256 points on the ring rather than one. With a single point each, an unlucky position would leave one server owning half the keyspace.

Most databases have built-in caching. Postgres uses shared_buffers to cache frequently accessed data pages in RAM. MySQL has its query cache (though it's been removed in MySQL 8.0 because it caused more problems than it solved at scale). This is the "free" caching layer, it happens automatically, but it's limited to what fits in the database server's RAM.

A recorded psql session against a stock PostgreSQL 14 with shared_buffers at its 128 MB default. Two tables with the same columns are queried, a small one of 200,000 rows taking 16 MB and a big one of 1,200,000 rows taking 95 MB. Each is scanned three times with EXPLAIN ANALYZE BUFFERS. On the small table run 1 reports shared hit=3 read=1471, then runs 2 and 3 both report shared hit=1474 with no reads at all. On the big table run 1 reports shared hit=77 read=8824, run 2 hit=173 read=8728 and run 3 hit=269 read=8632, so the reads barely fall across all three. — RecordedFigure 8. The database caching for you, and where it quietly stops
The small table stops touching disk entirely after one read. Its 1,471 blocks move into the pool and stay there, so the next two runs are pure hits. That is a real cache working for free, and it is why a slow query often looks fast the second time you try it in a console.
Now look at the big table, because the surprising part is not that it is slower. It is **95 MB against a 128 MB pool, so it fits**, and it still reads from disk on every single run. The reads go 8824, 8728, 8632: barely moving.
The reason is a deliberate piece of Postgres design worth carrying with you. A sequential scan over more than about a quarter of `shared_buffers` is given a small ring buffer of its own, around 256 KB, precisely so that one large scan cannot evict everything else in the cache on its way past. Postgres is protecting the pool from your query. Your data fitting in memory is not the same as your data being cached, and no amount of adding RAM changes that particular behaviour.

A cache entry drawn as three fields: key user:42, value a JSON object, and expires_at a unix timestamp. Beside it a note reads that no timer is created, that setting a TTL writes one timestamp into the entry, and that nothing is scheduled and nothing fires at 300 seconds. Below, a horizontal band is split into three stages: LIVE, served on every read; EXPIRED, still in RAM, for as long as nothing touches it; and DELETED, memory returned. The boundary into the deleted stage is annotated with two ways it can happen, a read arriving and finding it expired which is passive, or the sampler happening to pick it, twenty times a second, which is active. — ArchitectureFigure 6. An expired entry is not a deleted entry
Setting a TTL does not start a countdown. It writes a single timestamp into the entry and nothing else happens. No timer exists, nothing is scheduled, and nothing fires when the clock passes 300 seconds.
The entry is removed only when something happens to notice: a read arrives and finds it expired, or a background sampler happens to pick it. Until one of those occurs it is still sitting in RAM, taking up space, simply no longer served.
That amber stretch has no fixed length. A key nobody reads can sit expired for hours, which is how a cache full of expired keys still manages to run out of memory.

Write-Through / Write-Behind: When data changes in the database, immediately update the cache too. Write-through updates the cache synchronously (in the same operation). Write-behind updates the cache asynchronously (in the background). This keeps the cache always fresh, but adds complexity to every write operation.

Three isometric stacks drawn to scale, each slab representing one second of acknowledged writes held in volatile memory. The first stack is a single slab labelled 1 second of writes at risk, annotated Redis AOF with appendfsync everysec. The second is five slabs labelled 5 seconds at risk, annotated Linux page cache, the default. The third is ten slabs labelled 10 seconds at risk, annotated as the lesson's own example of a 10 second flush. — IsometricFigure 11. What the database has never heard of
Every slab is one second of writes your application has already told the user succeeded, sitting in memory that has not reached durable storage. If the process dies, that is what is gone, and the database never knew those writes existed.
The stacks are drawn to scale because the relationship is the point: the flush interval is a straight multiplier on how much you can lose. with `appendfsync everysec` risks about a second. The Linux page cache defaults to around five. A ten second flush risks ten.
Your write rate is set by your traffic. The interval is the half you actually choose, and choosing it is choosing how much data you are willing to lose.

Event-Based Invalidation: When data changes, publish an event ("product-price-changed"). A listener receives the event and deletes or updates the relevant cache entry. This is the most flexible approach but requires an event system (like or Redis Pub/Sub).

A hand-drawn diagram with a downward time arrow and two columns, writer and reader. Step 1, the writer deletes user:42 from the cache. Step 2, the reader gets user:42 and misses. Step 3, the reader selects from the database and reads the old row, because the write has not committed yet. Step 4, the writer updates the database and the new row commits. Step 5, in red, the reader sets user:42, writing the old value back into the cache. A red annotation labels step 5 as the write that undoes the invalidation. Beneath, the cache holds the old value while the database holds the new one. — SketchFigure 10. Every step succeeds and the cache still ends up wrong
Read the five steps in order. Nobody makes a mistake. Nothing returns an error. Every operation does exactly what it was asked to do.
The reader missed the cache and went to the database *before* the writer's update committed, so it read the old row. Then it did the normal, correct thing at the end of a cache-aside read: it wrote what it found back into the cache. That write landed after the invalidation, so it undid it.
The cache now holds the old value, the database holds the new one, and nothing anywhere is going to notice. It stays wrong until the TTL expires, which is the real argument for a TTL even when you have proper invalidation, and the reason people reach for versioned keys where correctness genuinely matters.

A decision flowchart. The first question asks whether you can tolerate the data being stale for a while. If yes, the answer is that a TTL is enough. If no, it asks whether you control every code path that writes the data. If you do, the answer is to delete the key on write and keep a TTL as a backstop. If you do not, the answer is to publish an event on change and let a listener invalidate. — FlowchartFigure 12. Two questions decide which approach you need
Start from what your data tolerates rather than from the list of techniques. If some staleness is genuinely fine, a TTL alone is the entire answer and you can stop there.
If it is not fine, you have to actively remove the key when the data changes, and that only works if every writer goes through code you control. When writers are outside your reach, a published event is what carries the news instead.
Keep the TTL even when you invalidate actively. It is the backstop for the day your invalidation silently fails, and figure 10 is what that day looks like.

Read-Through The cache itself is responsible for loading data on a miss. Your application only talks to the cache, never directly to the database. If the cache doesn't have the data, it fetches from the database, caches it, and returns it. This simplifies application code but means the cache needs to know how to query your database.

Write-Through Every write goes through the cache to the database. When you update data, the cache is updated first, then the database. The cache is always up to date, but writes are slower because they hit two systems. This eliminates the stale data problem at the cost of write .

Pattern	Read Performance	Write Performance	Data Freshness	Complexity
Cache-Aside	Great (after warm-up)	Normal (writes skip cache)	Stale until	Low
Read-Through	Great (after warm-up)	Normal	Stale until TTL	Medium
Write-Through	Great (always warm)	Slower (double write)	Always fresh	Medium

A three-row matrix. Cache-aside: your application talks to the database, stale until TTL, and you own every step including the race. Read-through: the cache talks to the database, stale until TTL, and the cache must know your schema. Write-through: the cache talks to the database on write, always fresh, and every write pays for two systems. — FigureFigure 16. The real difference is who owns the logic
Read the second column first and the rest follows from it. Cache-aside puts your application in charge of both systems. Read-through moves that job into the cache, which then has to know how to fetch your data. Write-through keeps the cache correct by making every write pay for it.
Nobody picks one of these in the abstract. You start at the top row, then find the one piece of data that genuinely cannot be stale, and give that piece write-through.

A sequence diagram with three lifelines: application, the cache, and the database. The first four numbered arrows show cache-aside: the application asks the cache and gets a miss, then the application itself queries the database, then the application writes the value back. The next three show read-through with the same opening call, but this time the cache queries the database on the application's behalf and returns the value already stored. — SequenceFigure 17. The same miss, handled by two different parties
The application code looks nearly identical in both halves. What differs is who handles the miss.
Under cache-aside your code sees the miss and deals with it, which is why the race in figure 10 is your bug to prevent. Under read-through the cache never lets your code see a miss at all, so that race becomes the cache's problem instead of yours. Neither is free: one gives you control and the bugs that come with it, the other takes both away.

A chart over 120 seconds after a cache was emptied. One line, the cache hit rate, starts at zero and climbs steeply, flattening near 95 percent within about a minute. A second dashed line, load reaching the database, is its mirror: it starts at 100 percent and falls away to near 5. A note in the early high region reads that everything misses, so everything is a database query. — ChartFigure 18. An empty cache is a database problem
At second zero every read misses, so every read becomes a query, and your database briefly carries traffic it never normally sees. The hit rate climbs as real traffic repopulates the popular keys, and within about a minute the load has fallen away.
The danger is the timing. A cache is usually empty because you just restarted something, which is exactly the moment your system is least able to absorb a spike. This is why you never flush a production cache all at once, and never restart every cache node together.

The first request to miss takes a short lock on that key. Everyone arriving behind it sees the lock and waits instead of querying. The winner fetches once, writes the value, and everybody waiting is served from it.

Four thousand identical queries become one, and nobody outside noticed anything.

The lock needs its own expiry, and that detail is not optional. If the request holding it dies mid-fetch, the key must not stay locked forever, or you have turned a brief spike into a permanent outage.

A hand-drawn cache cluster of four nodes. Thin arrows go to nodes 1, 3 and 4, while a thick red arrow goes to node 2, which is drawn in red and labelled as holding the key trending:post. A red note reads one key, most of the traffic, and a line beneath reads that consistent hashing spread the keys evenly but cannot spread one key. — SketchFigure 15. Even spreading does not help when one key is the traffic
distributes keys across nodes evenly and does that job well. But a single key lives on a single node, by definition. If that one key is a celebrity post or a flash-sale item, one node is taking most of your reads and the others are idle.
Adding nodes does not help, because the key does not split. The fix is to stop it being one key: copy the hot value onto several keys and pick one at random, or cache it locally on every application server for a few seconds.

Three overlapping circles labelled read often, changes rarely, and expensive to produce, with the central overlap marked cache this. Beneath, a row of three pair-failures: read often and cheap to make, which is a network hop that saves nothing; read often and changes constantly, where you will never get a hit; and rarely read but expensive, which is rent on memory nobody visits. — FigureFigure 19. Three conditions, and you need all three
Only the centre is worth caching, and the row underneath is why. Each pair is a specific way of wasting effort rather than a partial win: cheap data gains you nothing but a network hop, fast-changing data never survives to be hit, and rarely-read data is memory you are renting for nobody.
Before adding a cache, say all three out loud about your data. If you cannot name all three, you are adding a moving part for nothing.

A straight descending line on a chart, with cache hit rate on the horizontal axis and requests still reaching the database on the vertical axis. A dashed horizontal rule at 10 percent is labelled as what a 90 percent hit rate leaves you. Two notes read that the line is straight because load is exactly what the cache did not answer, and that at 90 percent, five more points halves what is left. — ChartFigure 20. Every point of hit rate is a point of load removed
The line is straight, because the two quantities are the same quantity: whatever the cache did not answer went to the database.
What compounds is not the line, it is what each point is worth. At a 50% hit rate half your reads still hit the database. At 90% it is one in ten. Going from 90 to 95 does not sound like much, and it halves what is left again. That is why the usual advice is 90 rather than 70, and why below 50 a cache is often just a moving part that has not earned its place.

A hand-drawn comparison. On top, shared data drawn as a single green box labelled 1 entry, annotated that 1,000,000 users read it. Below, per-user data drawn as a row of yellow boxes trailing into an ellipsis, annotated in red as 1,000,000 entries. A line beneath reads that it is the same feature, and the second one needs memory proportional to your users. — SketchFigure 21. Per-user caching changes the arithmetic
One shared entry serves a million people. A million personal entries serve one person each. Same feature, and completely different memory bills.
The hit rate suffers too, and that is the part people miss. A shared entry can be hit by everybody, so it earns its place quickly. A per-user entry can only ever be hit by one person, so most of them expire having been read once or not at all.
Per-user caching is not wrong. It is expensive in a way shared caching is not, and the usual answer is to cache the shared parts of a page and assemble the personal bits per request.

Memory pressure. Your cache has finite memory. When it fills up, something has to go. LRU (Least Recently Used) eviction is the most common policy, the item that hasn't been accessed the longest gets evicted. But if you don't size your cache correctly, you'll constantly evict and reload data, turning your cache into a bottleneck instead of an accelerator.

A hand-drawn diagram of a full cache holding three keys. Key A has 1,000 reads and was last read 10 minutes ago. Keys B and C have 1 read each and were both last read just now. A fourth key is arriving so one must be evicted. A red diagonal line strikes through key A. Two notes explain the disagreement: LRU says evict A, because it is the oldest last-use, throwing away the single most popular key for two keys read once. LFU says evict B or C, because their counter of 1 loses to A's 1,000. — SketchFigure 13. Same cache, same instant, different victims
LRU asks only one question: what was touched longest ago? Here that is A, the key with a thousand reads, and it gets thrown out to make room for two keys that have been read once each. This is **cache pollution**: a scan of one-time reads flushing the keys that were earning their place.
LFU counts instead of timing, so it keeps A and evicts one of the newcomers, which is clearly right here.
It is not simply better, though, and the honest reason is worth knowing before an interview. A counter remembers forever. A key that was enormously popular last week keeps its high count and squats in the cache long after anyone stopped asking for it, while genuinely hot new keys cannot get in.

A recorded redis-server session. 4,000 keys of 1.2 KB are loaded into a 4 MB cache with the allkeys-lru policy. CONFIG GET maxmemory-samples returns 5. INFO stats reports evicted_keys 2019. The session then asks how many of the 100 oldest cold keys are still alive, noting that true LRU evicts oldest first so the answer must be 0, and reports 7 of 100 survived. It then asks the same of the 100 newest, where true LRU must answer 100, and reports 100 of 100 survived. — RecordedFigure 14. Approximate LRU, measured rather than described
does not implement true LRU, and this is what that means in practice rather than in a footnote.
True LRU allows exactly one answer to each of these questions. Of the 100 oldest keys, 0 should have survived. Of the 100 newest, all 100 should have. Redis got the second one exactly right and the first one wrong by seven.
The reason is `maxmemory-samples`, which is 5 by default. When Redis needs to evict, it does not scan every key to find the true oldest. It samples five at random and evicts the oldest of those. That is enormously cheaper and almost always close enough.
Run it again and that first number moves a little. That wobble is the entire meaning of the word approximate, and it is why the policy is fast enough to use at all.

Two bins under the same 8 MB cap, measured on memcached 1.6.45. Slab class 2 has a chunk size of 120 bytes with 8,738 chunks per 1 MB page, and reports 200 items live and 0 evicted, drawn as many thin green rows. Slab class 23 has a chunk size of 13,880 bytes with 75 chunks per page, and reports 525 items live and 1,475 evicted, drawn as five wide red bars each with a small grey tail. A legend shows each red bar as 12,000 bytes of value plus 1,880 bytes nothing can use, and arrows mark the evictions leaving class 23. — ArchitectureFigure 15. Memcached splits memory by size, and LRU runs inside each split
Memcached does not run one LRU over all your keys. It sorts them into size classes and runs a separate LRU inside each one.
Look at what that produced here. Every one of the 1,475 evictions came out of class 23. Class 2 lost nothing at all, even though its items were written first and never read again, which is precisely what a global LRU would have evicted first.
The grey tails are the second lesson. A 12,000 byte value stored in a 13,880 byte chunk wastes 1,880 bytes that nothing else can use. The size class you land in is the only pool you ever compete for, and it is decided by how big your value happens to be.

Cache inconsistency in distributed systems. You have 10 servers, each with a local cache. You update a product name in the database. 9 servers still have the old name cached. Different users see different names depending on which server they hit. This is why distributed caches (Redis) are preferred for data that must be consistent across servers.