Efficient MRC construction with SHArdS

Carl A. Waldspurger, Nohhyun Park, Alexander Garthwaite, Irfan Ahmad

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

122 Scopus citations

Abstract

Reuse-distance analysis is a powerful technique for characterizing temporal locality of workloads, often visualized with miss ratio curves (MRCs). Unfortunately, even the most efficient exact implementations are too heavyweight for practical online use in production systems. We introduce a new approximation algorithm that employs uniform randomized spatial sampling, implemented by tracking references to representative locations selected dynamically based on their hash values. A further refinement runs in constant space by lowering the sampling rate adaptively. Our approach, called SHARDS (Spatially Hashed Approximate Reuse Distance Sampling), drastically reduces the space and time requirements of reuse-distance analysis, making continuous, online MRC generation practical to embed into production firmware or system software. SHARDS also enables the analysis of long traces that, due to memory constraints, were resistant to such analysis in the past. We evaluate SHARDS using trace data collected from a commercial I/O caching analytics service. MRCs generated for more than a hundred traces demonstrate high accuracy with very low resource usage. MRCs constructed in a bounded 1 MB footprint, with effective sampling rates significantly lower than 1%, exhibit approximate miss ratio errors averaging less than 0.01. For large traces, this configuration reduces memory usage by a factor of up to 10,800 and run time by a factor of up to 204.

Original languageEnglish
Title of host publicationProceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015
PublisherUSENIX Association
Pages95-110
Number of pages16
ISBN (Electronic)9781931971201
StatePublished - 1 Jan 2015
Event13th USENIX Conference on File and Storage Technologies, FAST 2015 - Santa Clara, United States
Duration: 16 Feb 201519 Feb 2015

Publication series

NameProceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015

Conference

Conference13th USENIX Conference on File and Storage Technologies, FAST 2015
Country/TerritoryUnited States
CitySanta Clara
Period16/02/1519/02/15

Fingerprint

Dive into the research topics of 'Efficient MRC construction with SHArdS'. Together they form a unique fingerprint.

Cite this