A second cache behind the first sees only what the first one missed, so its hit rate is measured on a different population. The global miss rate is the product (1 − h₁)(1 − h₂) rather than a sum, and the mean latency is t₁ + (1 − h₁)(t₂ + (1 − h₂)t₃) — a conditional expectation, over three outcomes you can list.
Core ideas
One new object is introduced here and it is small: an expectation taken over a restricted set of outcomes. Everything it is used for on this page is a list of three.
The second level only receives requests the first level missed, so its hit rate is a fraction of those, not of all requests. Written out, h₂ is P(L2 hit | L1 miss). A dashboard showing 50% on L2 is telling you about half of the L1 misses, which at h₁ = 80% is 10% of all requests.
A request reaches the origin only if it missed both levels, and the second event is conditioned on the first, so the global miss rate is (1 − h₁)(1 − h₂). At 80% and 50% that is (1/5)(1/2) = 1/10, and the global hit rate is 9/10. Adding the two rates gives 130%, which is how you know that move is wrong.
E[X | B] is the expectation of X computed over only the outcomes in which B happened, with their probabilities renormalised by dividing by P(B). Here B is “missed L1”, and the outcomes number three, so every use of it is a finite list you can add up by hand.
The material
What the second level's number actually measures, the one definition this needs, and the three-row enumeration that settles it.
For a random variable X and an event B with P(B) > 0, the conditional expectation E[X | B] is the expectation of X computed over only the outcomes in which B happened, with their probabilities renormalised by dividing by P(B).
That is the whole definition, and it is all this lesson needs. Discrete Mathematics gives conditional probability in “Conditional Probability” and expectation in “Expected Value”; this combines them, and every use of it here is a finite enumeration of three outcomes rather than anything requiring machinery.
The reason it turns up is that the second cache level’s hit rate is not a number about requests. It is a number about the requests that reached it, which are exactly the ones that missed the first level.
A request is served by L1 with probability h₁. If it misses, it is served by L2 with probability h₂ = P(L2 hit | L1 miss). If it misses both it is served by the origin. The global hit rate is the fraction served by either cache and the global miss rate is the fraction reaching the origin.
Every request pays t₁ for the L1 lookup, whether or not it hits. The ones that miss pay t₂ on top for the L2 lookup. The ones that miss both pay t₃ on top of that. Reading the branch forwards gives the mean directly, and enumerating the three outcomes gives the same number as a check.
The three probabilities sum to 1 and the contributions sum to the mean, which is the check worth doing every time: if the column does not sum to 1, a conditional rate has been used as an unconditional one somewhere.
The first is adding the hit rates: 80% + 50% = 130%. It is easy to spot here because it exceeds 100%, and much harder to spot at h₁ = 40% and h₂ = 50%, where it gives a plausible 90% against a true global rate of 70%. Rates only add when the events are disjoint on the same population, and these are not on the same population at all.
The second is reading L2’s measured rate as a global one: “L2 is serving half our traffic.” It is serving half of the L1 misses, which is (1/5)(1/2) = 1/10 of all requests. The monitoring is not lying; it is answering a question about a population that the reader has substituted for another one.
Set h₂ = 0 — an L2 that never hits — and 20% of requests reach the origin for a mean of 12 ms. Raise h₂ to 50% and the origin share halves to 10% and the mean falls to 7 ms. The halving of origin load is the whole point, by Hit Rate and Backend Load; the 12 ms is what a level that never hits still costs, because every L1 miss pays t₂ on the way to an origin it was going to reach anyway.
That last clause is the cost of a second level and it is easy to overlook. A level that rarely hits adds its lookup time to every request that misses the level above and returns nothing for it. The arithmetic is (1 − h₁)t₂ of pure overhead against (1 − h₁)h₂t₃ of saving, and the level is worth having when h₂t₃ > t₂ — which at h₂ = 50%, t₃ = 50 ms and t₂ = 5 ms it comfortably is.
One assumption to name: h₂ is treated as a single number, but the population reaching L2 is not a random sample of traffic. It is precisely the unpopular keys, because the popular ones were absorbed above — which is why a second level’s hit rate is generally much lower than the first’s and why it cannot be predicted by pointing the Zipf curve at L2’s size.
Interactive
The second level's hit rate is conditional, so the misses multiply
Method
Establish which population each number was measured on before doing any arithmetic with it.
h₁ is over all requests; h₂ is over the requests that reached L2. If the monitoring reports L2’s rate as a share of all traffic instead, that is (1 − h₁)h₂ and you must divide by 1 − h₁ before using it as h₂.
(1 − h₁)(1 − h₂) is the fraction reaching the origin, and 1 − that is the global hit rate. Never add hit rates; if the answer can exceed 100% the method is wrong even when the particular answer does not.
L1 hit, L1 miss then L2 hit, both miss. Write the probability and the latency of each, multiply, add. Check that the probabilities sum to 1 — that check catches a conditional rate used unconditionally, which is the one error this lesson is about.
The mean is t₁ + (1 − h₁)(t₂ + (1 − h₂)t₃), not a weighted average of t₁, t₂ and t₃. An L1 hit costs t₁; an L2 hit costs t₁ + t₂; an origin fetch costs t₁ + t₂ + t₃.
Both routes to the same number: the enumeration, and the forwards read of the branch. They agree, and each catches a different mistake.
The probability column summing to 1 is the check that matters. Substituting h₂ for (1 − h₁)h₂ there makes the column sum to 13/10, and that is the same error as adding the rates, caught one line earlier.
For a faded rehearsal, take h₁ = 90%, h₂ = 50% and the same three latencies. The supplied first move is that the global miss rate is (1/10)(1/2); finish it, enumerate the three outcomes, compute the mean both ways, and then say what fraction of all requests L2 is actually serving. Compare that with what a dashboard reporting “L2 hit rate: 50%” would have led you to believe.
The lab draws the flow with each branch labelled as a share of all requests, and prints both wrong answers underneath so you can see them beside the right one rather than be told about them.
You should be able to state h₂ as a conditional probability, compute the global miss rate as a product, enumerate the three outcomes with their path latencies and probabilities, produce the mean by both routes, and say what share of all requests the second level actually serves.
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.