eMRC: Efficient Miss Ratio Approximation for Multi-Tier Caching


Zhang Liu, University of Colorado Boulder; Hee Won Lee, Samsung Electronics; Yu Xiang, AT&T Labs Research; Dirk Grunwald and Sangtae Ha, University of Colorado Boulder


Many storage cache allocation methods use the miss ratio curve (MRC) to improve cache efficiency. However, they have focused only on single-tier cache architectures and require the whole MRC as input for cache management, while modern datacenters embrace hierarchical caching architectures to maximize resource utilization. Generating the MRC for multi-tier caches—we call it the miss ratio function—is far more challenging due to different eviction policies and capacities in each cache tier. We introduce eMRC, a multi-dimensional miss ratio approximation technique, to enable efficient MRC generation for multi-tier caching. Our approach uses a novel multi-dimensional performance cliff removal method and convex hull approximation technique to efficiently generate a multi-dimensional MRC without cliffs using a small number of sampling points. To demonstrate the benefits of eMRC, we designed ORCA, a multi-tier cache management framework that orchestrates caches residing in different hierarchies through eMRC and provides efficient multi-tier cache configurations to cloud tenants with diverse service level objectives. We evaluate the performance of our eMRC approximation technique and ORCA with real-world datacenter traces.

FAST '21 Open Access Sponsored by NetApp

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {264862,
author = {Zhang Liu and Hee Won Lee and Yu Xiang and Dirk Grunwald and Sangtae Ha},
title = {{eMRC}: Efficient Miss Ratio Approximation for {Multi-Tier} Caching},
booktitle = {19th USENIX Conference on File and Storage Technologies (FAST 21)},
year = {2021},
isbn = {978-1-939133-20-5},
pages = {293--306},
url = {https://www.usenix.org/conference/fast21/presentation/liu},
publisher = {USENIX Association},
month = feb

Presentation Video