counter-stacks · research · also counter stack, counter stack stream

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

  1. Wires, Ingram, Drudi, Harvey and Warfield. Characterizing Storage Workloads with Counter Stacks. OSDI 2014, pp. 335-349, sections 3-6. (accessed 2026-11-18)
  2. Hesela. Exact synthetic identity and initial-state counterexamples with explicit denominators. (accessed 2026-11-18)
  3. Hesela. Bounded exact distinct-count matrix and LRU scoring evaluator. (accessed 2026-11-18)

Further reading

  1. USENIX. OSDI 2014 publisher record, authors and proceedings metadata. (accessed 2026-11-18)
  2. Hesela. Independent LRU oracle and exhaustive short-trace checks. (accessed 2026-11-18)
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.

JSON: /data/terms/counter-stacks.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Counter Stacks. Hesela. 2026-11-18. https://hesela.dev/terms/counter-stacks/