Holding the C most popular keys gives a hit rate of H(C, s)/H(N, s), the same ratio the previous lesson computed, read as a function of C. It is a curve that rises steeply and then flattens, so the cache size a target requires is read off it rather than scaled: at N = 50 and s = 2, ninety per cent costs five keys and ninety-nine costs twenty-eight.
Core ideas
The formula is the previous lesson’s, with k renamed C and read backwards. What is new is the shape of the curve and what the shape implies.
The idealisation is that the cache holds exactly the C most popular keys and never anything else. Then a request hits when its key is in the top C, which happens with probability H(C, s)/H(N, s). Real caches approximate this badly or well depending on the policy, which is Replacement Policies on a Trace; this lesson is the ceiling they aim at.
At N = 50 and s = 2 the first key alone gives 61.533%, five keys give 90.061%, twenty-eight give 99.060% and forty-seven give 99.923%. The marginal value of a key falls with its rank because its probability does, so each further nine costs several times the cache of the one before.
Doubling a cache does not double its hit rate and cannot: the hit rate is bounded by 1 and the curve is concave. Going from 90% to 99% here takes the cache from 5 keys to 28, which is 5.6 times the memory for 9 percentage points — and, by Hit Rate and Backend Load, a tenfold cut in backend load, which is what you were buying.
The material
One formula read as a function of C, the scan that inverts it, and what this replaces from Capacity Estimation.
For a Zipf workload over N keys with exponent s, a cache holding the C most popular keys has hit rate h(C) = H(C, s)/H(N, s), for C from 0 to N.
h(0) = 0 and h(N) = 1. Between them h is strictly increasing and concave: each additional key adds p_{C+1}, and the probabilities are decreasing, so the increments shrink.
That is the whole model, and the assumption inside it is worth naming: the cache holds the right C keys. No online policy knows which those are, so h(C) is an upper bound on what a cache of C slots achieves on this workload, reached only if the popularity ranking is stable and the policy is good.
To find the smallest C reaching a target h, add probabilities in rank order until the running total crosses it. No formula is needed and none exists in closed form for integer C; the lab runs the scan over exact fractions, so the C it reports is the smallest one, not the smallest one up to rounding.
From 90% to 99% the cache goes from 5 keys to 28: twenty-three more keys, 5.6 times the memory. From 99% to 99.9% it goes from 28 to 47, and the catalogue only has fifty keys in it — past that point you are not caching, you are copying.
Put the two courses together and the trade is visible. Five keys of cache cut the backend load by a factor of ten (from 100% to 10% of λ); twenty-eight keys cut it by a hundred. The second factor of ten cost 5.6 times the memory of the first. Whether that is a good deal depends entirely on what the backend was doing at the higher load, which is the ρ of Hit Rate and Backend Load.
“Memory and the Working Set” sized a cache by stating a hot fraction — assume ten per cent of the data is hot, multiply by the row size, buy that much memory. That is a serviceable estimate and it is an assumption. Here the hot fraction is a result: it comes out of N and s, and at N = 50 and s = 2 the ten per cent that lesson assumed turns out to deliver 90.061%, which is either lucky or a coincidence depending on the workload.
So the honest procedure is the other way round from the one that course taught: measure the skew, choose the hit rate you need from what the backend can take, and let the curve tell you the cache size. If the skew is unknown, bracket it — compute the required C at s = 1 and at s = 2 and carry both numbers, which is the error bar Capacity Estimation asked you never to drop.
One caution about the flattening. The curve says the last nine is expensive in memory; it does not say the last nine is worthless. Whether it is worth buying is a question about the backend, and there the same nine is a tenfold cut in load every time. Read the two curves together or you will talk yourself out of a cache that was about to save a database.
Interactive
Read the C off the curve, and see what the next nine costs
Method
The target comes from the backend, not from the cache. Everything after that is a scan.
Decide what backend load the backend can take, divide by λ, and that is your miss rate. A backend that can serve 500 rps under 10 000 rps of traffic needs 1 − h ≤ 1/20, so h ≥ 95%. Choosing 99% because it sounds professional sizes the cache from a slogan.
N is the distinct keys touched, s is the skew. Both are measurements. If you have a rank-frequency sample, fit s roughly by comparing the top key’s share against the table; if you have nothing, bracket s between 1 and 2 and carry both answers.
Add p₁, p₂, p₃, … until the total reaches h. The C at which it crosses is the answer, and it is an integer — there is no interpolating a cache to two and a half keys.
Compute C for your target and for one nine beyond it. If the second number is a small multiple of the first, buy it now; if it is most of the catalogue, you have found the point where this workload stops rewarding memory and the answer is a different design.
The scan is a running sum over exact fractions. Only the crossings are written out here; the lab shows every step.
Five keys reach ninety per cent and twenty-eight reach ninety-nine. Notice that the second figure is more than half the catalogue: on a workload this small, the last nine means keeping most of the data, and the word “cache” has stopped being accurate.
For a faded rehearsal, keep N = 50 and set s = 1. The supplied first move is that the head is much flatter, so every target costs more; find the C for 90% and for 99% at that skew and state the ratio between them. Then say, in one sentence, what the two skews together tell you about how confident you can be in a cache size when s is only known to within a point.
The lab draws the curve with the target line across it and the required C marked, and the red bar under the axis is the distance between the ninety and the ninety-nine. Move the skew slider and watch that bar grow.
You should be able to compute h(C) for a given C, scan to the smallest C reaching a target hit rate, express that C as a share of the catalogue, and state what the next nine costs in keys and buys in backend load.
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.