SHARDS
SHARDS estimates cache miss-ratio curves by hashing block identities into a sample and scaling their observed reuse distances.
Selection: at a fixed threshold, every reference to a selected block is retained. Sampling individual requests is not equivalent. Distances are scaled by 1/R, where R is the location-sampling rate. [1]
Memory: a fixed rate does not bound tracked identities. Fixed-size SHARDS lowers its threshold, removes excluded identities and rescales earlier histogram counts. This rescaling is approximate, not exact removal of each discarded block's history. [1]
Interpretation: the published LRU evaluation uses fixed-size blocks and treats reads and writes alike. Its capacity-averaged error is not a guarantee at every cache size or for a new workload. [1]
Other policies: miniature simulations scale both the reference stream and cache capacity, then run the chosen policy. An LRU histogram alone does not predict ARC or LIRS behavior. [2]
Normalization: N requests at location rate R give expected sample count N*R, not necessarily observed count Ns. SHARDSadj adds N*R-Ns to the first histogram bucket. Miniature simulations divide misses by N*R instead of Ns. This correction does not guarantee accuracy. [1] [2]
Constructed example: A,A,B,B,A,A,B,B has 2/8 cold-start LRU misses at two slots. Keeping all references to A gives 1/4 at one slot; keeping every other request gives 4/4. This illustrates different sampling units, not SHARDS accuracy. [3]
Relations
- related
- Reuse distance, Miss-ratio curve, Kosmo
Citations
- Waldspurger, Park, Garthwaite and Ahmad. Efficient MRC Construction with SHARDS. FAST 2015, pp. 95-110; sections 2.1-2.3, 3.3 and 4.3.
- Waldspurger, Saemundson, Ahmad and Park. Cache Modeling and Optimization using Miniature Simulations. USENIX ATC 2017, pp. 487-498; sections 3.1-3.2.
- Hesela. Constructed sampling-unit and request-normalization examples: exact LRU ledgers and explicit denominators.
Further reading
Sources & caveats
- Primary-source synthesis with a deterministic constructed illustration. No original traces, author implementation, performance benchmark or reproduction of published SHARDS error rates.
- Normalization follows FAST 2015 section 4.3.3 and ATC 2017 section 3.1.1. The nine-A/one-B illustration uses chosen samples, not a randomized accuracy evaluation.