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.
Have you checked the wiki entry Cache algorithms as a starting point?
Also, Intro to Caching,Caching algorithms and caching frameworks part 1
If you can assume that a cache hit is much faster than a cache miss, you will find that overtime, even if you have only cache misses, using a cache will still be as fast or faster than not using a cache.
See below for the math:
Number of hits = NumRequests - #CacheMisses
AverageTime = ((NumRequests-#CacheMisses) * TimePerHit + #CacheMisses * TimePerMiss)/NumRequests
If we then assume that NumRequests is infinity (this is a limit problem, don't fear the calculus), we can see this:
AverageTime = Infinity*TimePerHit/Infinity - #CacheMisses*TimePerHit/Infinity + #CacheMisses*TimePerMiss/Infinity
Both terms with the #CacheMisses goes to zero, but the whole equation resolves to:
AverageTime = TimePerHit
Granted this is for when the number of requests is infinity, but you can see how this will easily speed up your system by using a cache.
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.