Theory of caching [closed]

Question

Is there a unified theory of caching? That is, collections of theorems and algorithms for constructing caches and/or optimizing for them?

The question is deliberately broad, because the results I am looking for are also broad. Formulas for maximum achievable speedup, metrics for caching algorithms, stuff like that. A university-level textbook would probably be ideal.

Answer 1

The vast majority of real-world caching involves exploiting the "80-20 rule" or Pareto distribution. See below for how it looks

This manifests itself in applications as:

• Much of the runtime is spent in the same piece of code (making code caches on CPUs effective)
• Often, when a variable is accessed, it will be accessed again soon (making data caches on CPUs effective)
• When a browser looks up a website's hostname once, it will access it quite frequently in the near future (making DNS caches effective)

Therefore, I would say the "theory of caching" is to use up just a few extra resources which are generally "rare" but "fast" to compensate for the most active repeated things you're going to do.

The reason you do this is to try to "level out" the number of times you do the "slow" operation based on the highly skewed chart above.

Answer 2

I talked to one of the professors at my school, who pointed me towards online algorithms, which seems to be the topic I am looking for.

There is a great deal of overlap between caching algorithms and page replacement algorithms. I will probably edit the WikiPedia pages for these topics to clarify the connection, once I have learned more about the subject.