Requests are not spread evenly over keys. Under a Zipf popularity the key of rank i is requested in proportion to 1/iˢ, and the share the top k keys carry is the ratio of two harmonic sums — an exact fraction, computable term by term. That ratio is far larger than k/N, and the gap between the two is the entire case for caching.
Core ideas
One assumption about the workload, one sum, and one comparison. The comparison is what the lesson is for: the uniform answer is the misconception, and it is computed here rather than described.
Sort the keys by how often they are requested. Under a Zipf law the i-th most popular key takes a share proportional to 1/iˢ, so rank 2 gets 1/2ˢ of what rank 1 gets, rank 10 gets 1/10ˢ. At s = 1 that is a tenth; at s = 2 it is a hundredth. s is the Zipf exponent, and it is the only thing on this course called s.
Probabilities must sum to 1, so p_i = (1/iˢ)/H(N, s) where H(N, s) = Σ 1/iˢ over i from 1 to N — the sigma notation of Algebra, summed exactly. H(20, 1) = 55835135/15519504. Dividing by it is the only step in this lesson that is not addition.
Adding the first k probabilities gives H(k, s)/H(N, s). At N = 50 and s = 2 the top five keys — a tenth of the catalogue — carry 90.06% of the requests, 9.01 times their share of the catalogue. Under uniform popularity they would carry exactly 10%. That multiple is what a cache is buying.
The material
Where the sum comes from, what it gives at two exponents, and the one figure on this course that is not exact.
Rank N keys from most to least requested. Under a Zipf popularity with exponent s ≥ 0, the key of rank i is requested with probability p_i = (1/iˢ)/H(N, s), where H(N, s) = 1 + 1/2ˢ + 1/3ˢ + … + 1/Nˢ is the generalised harmonic number.
s = 0 makes every key equally likely: H(n, 0) = n and p_i = 1/N. Larger s concentrates the requests on the head. Measured web and key-value workloads usually land between s = 0.7 and s = 1.2; this lesson uses integer exponents, for a reason given below.
Two things are being assumed and both are worth saying out loud. The first is the rank law itself, which is an empirical regularity rather than a theorem — workloads are measured and found to look like this, not derived and found to be this. The second is that the ranking is stable over the window you care about, which is false for news and true for a product catalogue.
Given the law, everything after it is addition. The share of the requests carried by the top k keys is the sum of the first k probabilities, and the normaliser cancels down to a ratio of two sums of the same shape.
H(5, 2) = 1 + 1/4 + 1/9 + 1/16 + 1/25 = 5269/3600. Dividing by H(50, 2) gives 90.06%: five keys out of fifty carry ninety per cent of the requests. One key on its own — two per cent of the catalogue — carries 61.53%, 30.77 times its share. Under uniform popularity those two numbers would be 10% and 2%.
A cache is worth building when a small store serves a large fraction of the requests, and the ratio H(k, s)/H(N, s) divided by k/N is exactly how much better than proportional you are doing. At N = 50 and s = 2 that multiple is 9.01 for the top five keys and 30.77 for the top one. At s = 0 it is 1 for every k, and a cache holding a tenth of the catalogue serves a tenth of the requests — which is the misconception, arrived at by computing it.
The multiple also shrinks as k grows, and that is the shape that decides how big a cache should be: the first key is worth thirty times its weight, the fiftieth is worth almost nothing. Cache Size and Hit Rate reads a required cache size off exactly this curve.
H(n, s) is a finite sum of fractions, so it is an exact rational and the lab computes it that way, term by term, over arbitrary-precision integers. What goes wrong is not accuracy but readability: H(50, 2) is a fraction whose numerator and denominator each run to forty-three digits, and a page that prints it has stopped communicating.
So the lab prints the exact fraction while the catalogue has at most fifty keys, and above that it switches to a rounded value, marks the figure with a ~, and says on its own face that it has switched. Drag N to 200 and the top two keys read ~25.865% of the requests — one per cent of the catalogue carrying a quarter of the traffic, 25.87 times its share — with the tilde there to tell you the sum is no longer exact. Every other number on this course is a fraction.
The exponent is an integer here for a related reason: at a fractional s every term 1/iˢ is irrational and there is no exact fraction to print at all. Real workloads have fractional exponents, and the right way to use this lesson on one is to bracket it — compute the share at s = 1 and at s = 2 and report the interval, rather than quote a rounded number with a confidence it has not earned.
Interactive
The top-k share as a ratio of harmonic numbers, exact while it is readable
Method
Rank, sum, divide, and then compare against the uniform answer, because the comparison is the result.
Rank 1 is the most requested. N is how many distinct keys the workload touches in the window, not how many rows exist in the database — a table of ten million rows with forty thousand distinct daily readers has N = 40 000.
H(k, s) = 1 + 1/2ˢ + … + 1/kˢ, as fractions. At s = 2 and k = 5 that is 1 + 1/4 + 1/9 + 1/16 + 1/25 = 5269/3600. Keep the fractions: the decimals here agree to four places and diverge after.
H(k, s)/H(N, s) is the share. If N is large enough that the sum is unreadable, the lab will round it and mark it; take the rounding as a signal to report an interval rather than a figure.
The share on its own sounds impressive and means little. 90.06% from 10% of the keys is 9.01 times proportional, and that multiple is what tells you whether a cache is worth building for this workload.
Five terms, one division, and one comparison. The comparison at the end is the only part a reader will remember.
The 9.01 is the number to carry away. It says that at this skew a cache is nine times more effective than its size suggests, and that is a statement about the workload, not about the cache.
For a faded rehearsal, take N = 20 and s = 1. The supplied first move is that H(20, 1) = 55835135/15519504; compute the share carried by the top two keys, which is ten per cent of that catalogue, and report it as a multiple of k/N. Then say what the same two numbers become at s = 0, and why.
The lab draws the rank curve with the top k shaded and the cumulative share over it, with the uniform line dashed across for comparison. Set s = 0 and watch the two lines meet: that is the misconception, drawn.
You should be able to write p_i for a Zipf workload, sum H(k, s) and H(N, s) exactly at an integer exponent, produce the top-k share as a fraction, and state it as a multiple of k/N.
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.