The Optimal Caching Problem
External
- https://www.coursera.org/learn/algorithms-greedy/lecture/VMnNW/application-optimal-caching
- An anomaly in space-time characteristics of certain programs running in a paging machine by Bélády https://dl.acm.org/doi/10.1145/363011.363155
Internal
Overview
The optimal caching problem can be solved with a greedy algorithm. A cache is a small fast memory.
The Problem
The problem consists in processing a sequence of "page requests". When a page that does not exist in cache is requested, the page must be brought from the big slow memory into the fast memory, and that constitutes a cache miss, or a "fault". As long as there is sufficient space left in cache, a fault triggers a simple page load. When the cache fills up, a fault causes an existing page to be evicted. The question is what page should be evicted from the cache to minimize the number of fault on the long term.
The Bélády Theorem
The theorem says that a natural greedy algorithm ("furthest-in-the-future") is an optimal algorithm for the optimal caching problem, minimizing the caching misses. "Furthest in the future" algorithm evicts the element that will be requested furthest in the future. This algorithm is not actionable because we - of course - do not know the future, so the algorithm is not implementable. However, this is a useful result to know because serves as a guideline for practical algorithm. The Least Recently Used (LRU) eviction algorithm looks in the past and assumes that what was requested recently will also be requested recently, so we want it in the cache, and as result we evict the element that was requested least recently.