Counter Stacks
Counter Stacks estimates LRU miss-ratio curves using compact histories of distinct-block counts over overlapping time intervals.
Mechanism: counters start at different times; finite differences reveal reuse in the ideal exact matrix. The practical method combines downsampling, pruning and HyperLogLog. Its retained stream supports time slicing, shifting and workload combination. [1]
Joining has a boundary: the paper's addition-based operation assumes disjoint block sets. Counter estimation error is separate from this identity assumption. [1]
Constructed example: two streams each read their single block twice, interleaved. Each stream reports one distinct block whether their blocks are shared or different. In a one-entry LRU cache, the shared-block merge misses 1/4 requests; the disjoint merge misses 4/4. Adding counts gives two in both cases, which is wrong for the shared union. Counts alone cannot recover the missing overlap information. [3]
Window example: score only the last AB of ABAB in a two-entry cache. Keeping the preceding AB as warm-up gives 0/2 misses; replaying the last AB from empty gives 2/2. Neither denominator includes warm-up requests. State the initialization separately from the scoring window. [3]
Limits: a compact locality summary is not a lossless trace or a prediction of storage latency. The linked evaluator is a bounded exact teaching model, not practical Counter Stacks, a device benchmark or a replication of the paper's accuracy results. [4]
Relations
- related
- Working set, Reuse distance, Miss-ratio curve
Citations
- Wires, Ingram, Drudi, Harvey and Warfield. Characterizing Storage Workloads with Counter Stacks. OSDI 2014, pp. 335-349, sections 3-6.
- Hesela. Exact synthetic identity and initial-state counterexamples with explicit denominators.
- Hesela. Bounded exact distinct-count matrix and LRU scoring evaluator.
Further reading
- USENIX. OSDI 2014 publisher record, authors and proceedings metadata.
- Hesela. Independent LRU oracle and exhaustive short-trace checks.
Sources & caveats
- Source review covers the original method, joining assumption and evaluation limits. The USENIX proceedings identify the October 2014 conference; no invention date is asserted.
- Synthetic evidence uses exact integer counts. No author code, MSR traces, probabilistic counters or measured speedup are reproduced.