Nobody buys enough memory for the dataset. Memory is sized to the part of the data the traffic actually touches, which is usually a small fraction of it, and the question is not whether the data fits but how many of the reads do. Given a hot fraction and the share of traffic it takes, the hit rate is a piecewise-linear function of what you cache — with a knee where the hot region runs out, and the knee is where the budget is decided.
Core ideas
One hard idea — the denominator is the working set and not the dataset — and then the shape of the curve that idea produces, and what the curve is a model of.
Five terabytes of timelines with a tenth of it taking 90% of the reads needs 444.44 GB of memory for an 80% hit rate: 4/45 of the data, 8.89%. The dataset size sets what caching everything would cost and is otherwise not the relevant quantity. The question a memory budget answers is how many reads are served, and reads are not distributed over the data the way bytes are.
Inside the hot region every gigabyte buys the same number of hits, and outside it every gigabyte buys far fewer. Caching the whole hot 10% costs 500 GB and buys 9/10 of the reads; pushing the target to 95% costs 2.75 TB, because the extra five points have to be bought out of the cold region at the cold region’s price. A target chosen without looking at the knee is a budget decision made by accident.
10% of the data taking 90% of the reads is an input here, measured over some window, and it moves: a release, an import, a story everyone reads at once. The model also assumes every key inside each region is equally popular, which is false in detail and is what makes the curve two straight lines rather than a smooth one. “Cache Size and Hit Rate” replaces the stated fraction with a popularity exponent and derives the same shape instead of asserting it.
The material
What a working set is, the two-segment curve a stated skew produces, and where the money goes.
The working set is the portion of the data that the traffic touches over a window. A workload with hot fraction f and hot share s has f of its bytes taking s of its reads; caching a fraction c of the data gives a hit rate h(c), and the memory needed for a target h is the dataset times the c that reaches it.
The two numbers f and s are what makes caching work at all. If reads were spread evenly over the data, caching c of it would buy c of the hits and a cache would be exactly as useful as it was large — which is to say, not useful, because you cannot afford a cache the size of the data. Skew is the whole business case.
Both branches are straight lines and they meet at (f, s), which is the knee. The first has slope s/f — here 9, so each point of cached data buys nine points of hit rate — and the second has slope (1−s)/(1−f), here 1/9. A factor of eighty-one between the price of a hit before the knee and after it, and it changes at a single point.
With f = 10% and s = 90%, a target of 80% is inside the hot region, so c = 0.1 · 80/90 = 4/45, which is 8.89% of the data, or 444.44 GB. Less than half a terabyte of memory serves four reads in five out of a five-terabyte store. That ratio — and not the absolute figure — is why caches exist.
Caching the entire hot region costs 500 GB and gives a hit rate of 9/10. Ask for 95% instead and the memory needed is 11/20 of the data, 2.75 TB. The first ninety points of hit rate cost half a terabyte; the next five cost more than four times that again, because they are bought from a region where reads are spread thinly over a lot of bytes.
This is the shape of every cache-sizing conversation worth having. The target hit rate is a choice, it has a price, and the price is wildly non-linear in the target. A team that asks for “99%” because it sounds rigorous has usually asked for the whole dataset in memory without noticing; a team that reads the knee off the curve first asks for a number it can pay for.
Two things, and both are visible in the shape of the curve. Within the hot region every key is equally popular, and within the cold region every key is equally popular — which is what makes each branch a straight line, and it is not true of any real workload. And the split into two regions is itself a simplification of a smooth popularity curve. The model is right about the two things this lesson claims — that a small cache buys a large hit rate, and that there is a knee — and it is an approximation about everything else.
The other assumption is quieter: f and s were measured over some window and are being used as though they were properties of the system. They move. The honest report says which window they came from, exactly as a read/write ratio does, and treats them as ranged factors when they are carried into a product.
“Cache Size and Hit Rate”, on Caching and Hit Rates, replaces the stated pair with a Zipf popularity exponent, from which the same curve is derived rather than asserted — and the knee softens into a genuine curve with diminishing returns everywhere. This lesson is the version that can be done on an envelope, and it gets the two structural facts right.
Interactive
Size the cache to the hot fraction, not to the dataset
Method
Measure the skew, find the knee, choose the target knowing what it costs.
What is wanted is the fraction of keys taking a large share of the reads over a window — a question about access logs. Any reasoning that starts from how the data is distributed has answered a different question, and a cache sized from it will be sized to the dataset.
The knee sits at (f, s): caching the hot fraction buys the hot share, and here that is 500 GB for 9/10 of the reads. Everything to the left of it is cheap and everything to the right is expensive, so the knee is the fact a target should be chosen against.
For a target at or below s, the fraction needed is f · h/s; past it, f + (1−f)(h−s)/(1−s). Multiply by the dataset for the gigabytes. Keeping the fraction as an exact ratio — 4/45 — makes the arithmetic checkable and the answer scalable.
444.44 GB on its own is unauditable. 444.44 GB for 80%, given 10% of the data taking 90% of the reads, can be argued with — and the argument will be about the skew, which is the right place for it.
Reduce the hot share in the lab and watch the memory needed climb. The skew is the input the answer is most sensitive to and the one most likely to drift, so a sizing that does not say what a weaker skew would cost has not been stress-tested at all.
One dataset, one skew, two targets — one on each side of the knee.
The three lines at the bottom are the lesson. Nine reads in ten for a tenth of the storage is why a cache is worth having; the jump from there to 95% costing most of the dataset is why a target hit rate is a budget decision and not an aspiration.
Notice that 80% cost less than the whole hot region. Targets below the hot share are bought at the cheap slope, and there is no reason to cache the entire hot region unless the target requires it — which is the practical content of “caching is not all-or-nothing”.
For a faded rehearsal, take the lab’s catalogue example: 200 GB with 5% hot at 75% of reads, and a 95% target. The supplied first move is that 95% > 75%, so the target is past the knee and the second branch applies. Work out the fraction, the gigabytes, and what caching just the hot region would have bought — then check all three in the lab, and say which of the two inputs you would go and measure again.
You should be able to turn a dataset size, a hot fraction, a hot share and a target hit rate into gigabytes, locate the knee and say what it costs, explain why the points past it are so much more expensive, and name the two assumptions the piecewise-linear model rests on.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.