The governing arithmetic: two inequalities

When does a cache pay for itself, and how far does the layer below come to depend on it?

Two short inequalities run this mechanism. Every topic later is a resolution of one of them.

Amortization: does the cache pay?

Use these symbols:

• P = the cost to produce one version of the cached object (for example, to run a query).
• S = the saving for each read that is served from the cache.
• λ (lambda) = the rate of reads on the object.
• w = the rate of writes that invalidate it (make it wrong) — the churn rate.

One cached version lives for 1/w time units on average, and during that time it serves λ/w reads. Call R = λ/w the reuse factor (reads per version). The cache pays if and only if

The value of one version is (λ/w)·S − P, and it must be positive.

The ratio P/S is a threshold: the number of reads you need before the cache is worth building. The inequality contains a lesson that practitioners often get wrong:

A million reads per second against a table written a million times per second cannot be cached usefully. A hundred reads an hour against an immutable file can. Caching converts a read-rate problem into a write-rate problem.

Leverage: how much do you depend on the cache?

If the cache sustains hit rate h, the layer below is asked for only (1 − h)λ requests per second. Sooner or later someone will size that lower layer for exactly that smaller load. Then the cache has leverage

against the backing store. At h = 95% the leverage is 1/0.05 = 20 to 1. At h = 99% it is 1/0.01 = 100 to 1. And look at what happens at the top: a drop from h = 0.99 to h = 0.98 changes the load below from 0.01λ to 0.02λ. A one-point drop in hit rate at 99% doubles the load on the layer below.

Hit rate is leverage, and leverage is fragility. This is how an optimization quietly turns into a load-bearing dependency that appears on no dependency diagram. It is exactly what happened to Ifeoma's database when the cache was restarted.