Quest for Offline Optimality

The offline optimal performance, which is the best possible performance given full knowledge of the future requests, is a critical guide for cache algorithm development. The offline optimal algorithm for single-level caches is the classic Belady's MIN or OPT [4] which simply evicts the page with the furthest re-reference time. For four decades, the quest for a similar algorithm for multi-level caches has remained unfulfilled. Hit ratio, the performance metric that served us so well in single-level caches, loses its fidelity to performance in multi-level caches, where the benefit of a hit depends on which level it occurred in (e.g. two hits on a higher cache could be better than three hits on a lower cache.)

The average read response time is a much better performance metric, but is complicated in the presence of demotions and/or eviction-based reloading from disks. The inter-cache bandwidth usage is another important metric since many scenarios are bottle-necked by network resources [33]. It does appear that different policies would be optimal depending on which performance metric we use.

We now prove universal bounds for the single-path scenario as depicted in Figure 3 that simultaneously apply to both the average response time and inter-cache bandwidth metrics. The bounds apply to all algorithms irrespective of whether demotions, inclusion, or hints are used. Later, we explain extensions to compute the bounds for the multi-path scenarios as well.

$C_i$	Cache at level $i$, $i = 1,2,...,n$
$S_i$	Size of the cache $C_i$
$h_i$	Number of hits at $C_i$
$t_i$	Avg. round-trip response time from $C_i$
$t_m$	Avg. round-trip response time from disks
$\sigma_i$	Sequence of reads seen by $C_i$
$\sigma_m$	Sequence of reads (misses) seen by disks
$D_{c_i \rightarrow c_{i+1}}$	Number of demotions from $C_i$ to $C_{i+1}$

From Figure 3 and definitions above, the total response time is

$$totalRespTime = \sum_{i = 1}^{n} h_i\cdot t_i + \vert\sigma_m\vert\cdot t_m$$ (1)

and the inter-cache traffic between caches $C_i$ and $C_{i+1}$ is

$$interCacheTraf_{c_i \rightarrow c_{i+1}} = \vert\sigma_{i+1}\vert + \vert D_{c_i \rightarrow c_{i+1}}\vert$$ (2)

We define $hitOPT( \sigma, S)$ to be the number of hits produced by Belady's offline OPT policy on the request sequence $\sigma$ and a single-level cache of size $S$.