Module 4: Cache — The Read-Heavy Path

6. The working set and the 80/20 rule

Next →

Description

The previous lesson left you wanting a high hit ratio —0.90 or more— and a question on top: to achieve it, how much data do I have to cache? Enlace has 6 billion records (you computed them in module 2: 5 years at ~1 KB each, about 6 TB). If you had to put all of that in RAM to have a good hit ratio, the cache would be as expensive as it is unfeasible —6 TB of RAM cost a fortune—. The good news, and the topic of this lesson, is that you hardly need to cache any of it. The reason has a name: the 80/20 rule (or Pareto principle, or Zipf distribution in its formal version), which says that in systems like Enlace a small fraction of the data concentrates the enormous majority of the accesses. A few viral links take almost all the visits; the very long tail of links no one looks at contributes almost no reads.

That means you can get a 90% hit ratio by caching only the working set —the set of data that's really hot in a time window—, which is tiny compared to the total. This lesson defines the working set, explains why the 80/20 rule makes it small, and computes the real size of Enlace's working set in Python: how many entries, how many bytes each one, how much RAM in total. The result —~666,667 entries, ~333 MB— fits easily in a modest Redis, and that number is the one you carry to the lesson 8 project.

Connection to the module: lesson 5 proved that you want a high hit ratio; this one tells you how much RAM it costs to get it, and the happy answer is "little". It rests on the locality of lesson 4 (the hot stuff is a small subset) and on the pressure of lesson 2 (the ~333 M daily reads). The number you compute here —the working set's MB— is one of the two inputs of the project's sizing (the other is the target hit ratio of lesson 5). Without this lesson, "I need a cache" has no size; with it, it has a number in megabytes.

The library's books and the new-releases table

Think of it this way. A library has a hundred thousand books on its shelves. If you observe what people take out during a week, you discover something that repeats in every library in the world: most of the loans are of a few hundred titles —the new releases, the bestsellers, the semester's required readings—, while the vast majority of the hundred thousand books don't go out even once all week. It's not that the others don't matter: they're there for when someone requests them. But the traffic concentrates brutally on a tiny fraction of the catalog.

The smart librarian takes advantage of this. Instead of having to go to the back shelves for each loan, they put a new-releases table by the entrance with those few hundred hot titles. Since most people come precisely for those, most of the loans are resolved at the entrance table, without walking to the back. The table doesn't have even 1% of the catalog, but it serves 90% of the loans. And best of all: the table fits at the entrance precisely because it's small —it doesn't need to be a second library, just a shelf with the hot stuff—.

That new-releases table is your cache, and its size is the working set: the set of data that's hot now. The complete library (a hundred thousand books) is the database; the table (a few hundred titles) is the cache. The rule that makes the table fit —"few titles concentrate the loans"— is the 80/20 rule. And the question of this lesson is exactly the librarian's: how many titles do I have to put on the table to serve 90% of the loans? In Enlace, that calculation gives a few hundred thousand links and a few hundred megabytes —a table that fits comfortably at the entrance—.

The 80/20 rule says a small fraction of the data concentrates most of the accesses. That's why you don't cache everything: you cache the working set —the hot data in a window—, which is tiny compared to the total, and with it you get a high hit ratio using little RAM.

The 80/20 rule, with more precision

"80/20" is a nickname; the real shape of this concentration is a Zipf distribution (or power law), and it appears everywhere: the most-used words of a language, the most populated cities, the most-watched videos, the best-selling products. The idea: the most popular element receives much more traffic than the second, the second more than the third, and so on, with a very steep drop. The practical result is that a minority of elements hoards a majority of the events. The "80/20" is just a round way of saying it (20% of the data → 80% of the accesses), but in many real systems it's even more extreme: 10/90, or 1/50.

For a cache, this is excellent news, because it means the hit ratio rises fast with the first entries you cache and then flattens. Look at it this way: if you cache the hottest 1%, you already catch maybe 50% of the reads. If you cache the hottest 20%, you catch 90%. But to get from 90% to 99% you'd have to cache a much larger fraction —the long tail of links requested occasionally—, and that's where gaining hit ratio becomes expensive (exactly what you saw in lesson 5: the last points cost). The mental graph is a curve that rises steeply and then lies down: the first cached entries give almost all the hit ratio; the long tail gives less and less per MB added.

In Enlace, the concentration comes from two sources that reinforce each other. First, novelty: a just-created and shared link receives a burst of visits in its first hours or days (while the tweet, the email, the message circulates) and then cools off. Second, virality: of all the links, a few explode and receive orders of magnitude more visits than the rest. The two together produce a strong concentration: Enlace's hot working set on a day is, above all, the recent links and the few viral ones, not the 6 billion historical ones.

Computing Enlace's working set

Let's bring this down to a number. The concrete question: how many distinct entries do I need to cache to have a good hit ratio, and how much RAM do they take up? We're going to reason it out in steps and run it.

Step 1: how many links come "into play" each day? With 100M new links a month, about 100,000,000 / 30 ≈ 3,333,333 new links come in per day. Since the traffic concentrates on the recent links, the bulk of a day's hot working set is those new links (plus some viral ones from previous days that are still active).

Step 2: what fraction is really hot? Here we apply the 80/20 rule: not all of the day's new links are equally hot; the hottest 20% concentrates most of the reads. So the working set to cache to catch ~90% of the reads is on the order of 20% of the day's links: 0.20 × 3,333,333 ≈ 666,667 entries.

Step 3: how much does each entry weigh? A cache entry is short_code → long_url. The short_code is 7 bytes; the long_url is what weighs, ~500 bytes on average (the anchor number from module 2). With Redis's overhead (per-key metadata), an entry is around 500 bytes. Let's also compute with 200 and 1000 to see the range.

# working_set.py — working set size and cache memory
NEW_URLS_PER_MONTH = 100_000_000
new_links_per_day = NEW_URLS_PER_MONTH / 30
hot_fraction = 0.20                     # 80/20 rule: the hottest 20%

working_set = new_links_per_day * hot_fraction

print(f"new links/day      = {new_links_per_day:,.0f}")
print(f"working set (20%)  = {working_set:,.0f} entries\n")

for entry_bytes in (200, 500, 1000):
    mem_bytes = working_set * entry_bytes
    print(f"at {entry_bytes:>4} B/entry -> "
          f"{mem_bytes:,.0f} B = {mem_bytes/1e6:,.0f} MB = {mem_bytes/1e9:.2f} GB")

What to expect. With python working_set.py:

new links/day      = 3,333,333
working set (20%)  = 666,667 entries

at  200 B/entry -> 133,333,333 B = 133 MB = 0.13 GB
at  500 B/entry -> 333,333,333 B = 333 MB = 0.33 GB
at 1000 B/entry -> 666,666,667 B = 667 MB = 0.67 GB

There's the number we were looking for. A day's working set of Enlace is about 666,667 entries, and at ~500 bytes each they take up ~333 MB. Compare that with the 6 TB of the complete database: the cache needs ~333 MB to catch 90% of the reads, that is, about 0.005% of the total data size. That's the gift of the 80/20 rule made into a number: with five thousandths of a percent of the storage, in RAM, you resolve the enormous majority of the traffic. A Redis of 1 or 2 GB —cheap, common— is more than enough for this. You don't need to cache the 6 TB; you need to cache the ~333 MB that are hot.

How the window moves the number

The "666,667 entries" came from assuming the hot working set is 20% of a day of links. But "hot" depends on the window you choose: if links keep receiving visits for several days (not just the day they're created), your working set spans several days of hot ones, and it grows. Let's see it:

# window.py — the working set according to how many days of hot ones you retain
working_set_day = 666_667
entry_bytes = 500

for days in (1, 3, 7, 30):
    ws = working_set_day * days
    print(f"{days:>2} day(s) of hot ones -> {ws:>10,.0f} entries = "
          f"{ws*entry_bytes/1e9:.2f} GB")

What to expect. With python window.py:

 1 day(s) of hot ones ->    666,667 entries = 0.33 GB
 3 day(s) of hot ones ->  2,000,000 entries = 1.00 GB
 7 day(s) of hot ones ->  4,666,667 entries = 2.33 GB
30 day(s) of hot ones -> 14,000,000 entries = 7.00 GB

The window rules. If retaining one day of hot ones already gives you a good hit ratio, ~333 MB is enough. If your traffic keeps links hot for a week, you need ~2.33 GB. If a month, ~7 GB. All those numbers fit in RAM of a modern server (a Redis with 8 or 16 GB handles them), and none comes close to the 6 TB of the total. The design decision is: how much window of hot ones do I retain? And this is where the eviction of lesson 4 and the TTL of lesson 7 do their work: LRU automatically throws out the links that cooled off (the ones that left the hot window), keeping the cache full of the current stuff without you computing the window by hand. You give the RAM; LRU decides which day of hot ones fits.

Why this justifies the whole strategy

It's worth tying the threads together, because this lesson closes the module's argument. Lesson 2 said "you have to catch most of the ~4,000 reads/s before they reach the database". Lesson 5 said "with hit ratio 0.90 the latency drops to 5.9 ms and the database sees only 386/s". The question that remained —"but how much RAM does that 0.90 cost?"— is answered by this lesson: ~333 MB, thanks to the 80/20 rule concentrating the reads in a tiny working set. Without the 80/20 rule, caching would be unfeasible (you'd have to put 6 TB in RAM). With it, caching is very cheap and that's why it's the first tool you pull out in any read-heavy system. The cache works not by magic, but because real-world traffic is concentrated —and Enlace, with its viral and recent links, is more than concentrated—.

Common mistakes

Believing you have to cache all the data to have a good hit ratio. What happens: someone looks at Enlace's 6 TB and concludes they need 6 TB of RAM (impossible) or that "the cache is useless because it doesn't all fit". They discard the cache over a wrong calculation. Why it happens: it's assumed that the hit ratio depends on caching a large fraction of the data, when it depends on caching the hot data, which is a tiny fraction. How to detect it: if your RAM estimate for the cache comes close to the total size of the database, you're not using the 80/20 rule. How to fix it: compute the working set (the hot data in a window), not the total. In Enlace, ~333 MB (0.005% of the total) give hit ratio 0.90. The cache catches the concentrated traffic, not all the data.

Confusing "total data" with "hot data". What happens: someone sizes the cache by the database's size (6 TB) instead of by the working set (~333 MB), and requests a gigantic and very expensive Redis that's 99.99% wasted —full of cold links no one requests—. Why it happens: it's easy to think about "all the data" and forget that the traffic only touches a few. How to detect it: if your cache has much more memory than the working set needs, look at the hit ratio: if it's already high with a fraction of the RAM, the rest is unnecessary. How to fix it: size by the working set. More RAM than the working set needs hardly raises the hit ratio (the long tail contributes little), so you pay for memory that doesn't buy hits. Lesson 5 anticipated it: the last points of hit ratio are expensive precisely because they require caching the cold tail.

Forgetting that the hot window changes the size. What happens: someone computes the working set for "one day" and sizes the cache for 333 MB, but in their system the data stays hot for a week, so the real working set is 2.33 GB —and the cache, too small, evicts links that are still requested, lowering the hit ratio—. Why it happens: an arbitrary window is taken without verifying how long the data really stays hot. How to detect it: if the hit ratio is lower than expected and the eviction is high, your cache is smaller than the real working set. How to fix it: measure (or estimate with margin) how long the data stays hot and size for that window. And let LRU (lesson 4) do the fine-tuning: if you give it RAM for a week of hot ones, LRU will retain a week; if you give it for a day, it will retain a day. The window emerges from the size you give it.

Exercises

Exercise 1 — Recompute the working set with another fraction. The example used the hottest 20%. Recompute the working set and the memory (at ~500 bytes/entry) if in Enlace it were enough to cache the hottest 10% to have a good hit ratio, and if instead the hottest 30% were needed. Start from 3,333,333 new links a day.

See solution
  • At 10%: working set = 0.10 × 3,333,333 ≈ 333,333 entries. Memory = 333,333 × 500 ≈ 166,666,500 B ≈ **167 MB**.
  • At 20% (reference): 666,667 entries ≈ 333 MB.
  • At 30%: working set = 0.30 × 3,333,333 ≈ 1,000,000 entries. Memory = 1,000,000 × 500 ≈ **500 MB**.

All three numbers —167 MB, 333 MB, 500 MB— fit comfortably in RAM. The lesson: even if the hot fraction is double or triple the estimate, the cache is still small and cheap (it never comes close to the 6 TB of the total). That's the margin the 80/20 rule gives: even if you're wrong about the fraction, the working set is tiny compared to the complete data. Notice also the diminishing return: going from 10% to 30% (tripling the RAM, from 167 to 500 MB) probably raises the hit ratio only a few points, because you're caching ever-colder links —the long tail—.

Exercise 2 — The Pareto curve in numbers. Suppose this (simplified) access distribution for 5 links in an hour: L1 receives 500 visits, L2 receives 250, L3 receives 125, L4 receives 65, L5 receives 60. (a) How many visits are there in total? (b) If you cache only the 2 hottest links (L1 and L2), what hit ratio do you get? (c) What does this tell you about caching "the few hot ones"?

See solution
  • (a) Total: 500 + 250 + 125 + 65 + 60 = 1,000 visits.
  • (b) Caching L1 and L2: those two receive 500 + 250 = 750 visits of the 1,000. Hit ratio = 750 / 1,000 = **75%**. With only 2 of 5 links (40% of the links) you catch 75% of the visits.
  • (c) It shows the essence of the 80/20 rule: the accesses concentrate on the first elements, so caching "the few hot ones" (L1, L2) gives a disproportionately high hit ratio relative to how many links they are. Caching a third link (L3, with 125 visits) would raise the hit ratio to 875/1000 = 87.5% —each additional link contributes less, because the tail is colder—. This is the curve that rises steeply and lies down: the first cached data buys almost all the hit ratio; the last, less and less. In Enlace, with millions of links and a much more extreme concentration than this toy example, caching the hottest 20% is enough for 90%.

Exercise 3 — Why not cache the 6 TB? A colleague proposes: "Let's put Enlace's whole database (6 TB) in RAM to have 100% hit ratio and never go to disk". Give three reasons why this is a bad idea, relying on the 80/20 rule and on lesson 5.

See solution

Three reasons:

  1. Disproportionate cost. 6 TB of RAM cost orders of magnitude more than the ~333 MB the working set needs for hit ratio 0.90. You'd be paying to put in expensive RAM the very long tail of cold links almost no one requests —99.99% of the cache would be wasted on data that generates no traffic—.

  2. Diminishing return (lesson 5). Going from hit ratio 0.90 (with ~333 MB) to 1.00 (with 6 TB) lowers the average latency from 5.90 ms to 1.00 ms —an improvement of ~5 ms— in exchange for multiplying the RAM by ~18,000. The last points of hit ratio, which require caching the cold tail, are very expensive and buy very little. It's not worth it.

  3. The cache stops being a cache. A cache is a partial and disposable copy of the hot stuff; if you put all the data in it, it's no longer a cache, it's a second database in RAM —volatile, expensive, and without persistence—. You lose the advantage of the cache being small and cheap, which is exactly what the 80/20 rule makes possible.

The moral: 100% hit ratio isn't the goal —it's an expensive mirage—. The goal is a high hit ratio (0.90–0.95) at the lowest RAM cost, and the 80/20 rule says that's achieved by caching only the working set. Chasing 100% is fighting the long tail, which gives less and less per TB. A good cache design accepts that there will always be some misses and settles for catching the cheap bulk of the traffic.

Summary and next step

In this lesson you answered the question lesson 5 left open: for a hit ratio of 0.90, you do not need to cache Enlace's 6 TB, but only the working set —the hot data in a window—, which the 80/20 rule (Zipf distribution) makes tiny: a few viral and recent links concentrate most of the reads, like the new-releases table that serves 90% of the loans with less than 1% of the catalog. You computed it: ~666,667 entries, ~333 MB —about 0.005% of the total—, which fit comfortably in a modest Redis.

You saw that the window of "hot" moves the number (one day → 333 MB, one week → 2.33 GB), that all those sizes fit in RAM, and that LRU eviction (lesson 4) automatically adjusts which window it retains according to the RAM you give it. And you closed the module's argument: the cache is cheap and that's why it's the first tool of the read-heavy, because real traffic is concentrated.

Before moving on you should be able to: define the working set and distinguish it from "all the data"; explain the 80/20 rule and why it makes the cache small; reproduce the calculation (~666,667 entries → ~333 MB); and say why caching 100% of the data is a bad idea.

What comes next is the dark side of the cache, the problem we've been postponing: the copy the cache stores can become stale. In lesson 7 you'll see the TTL (automatic expiration) as a cheap safety net, the invalidation (deleting the entry when the database changes), why in Enlace this is easy (links hardly change) and where it gets hard, and the boundary with the asynchronous queue-based invalidation that lives in the events guide.

Resources

← Previous5. Hit ratio and average latencyNext →7. TTL and cache invalidation