research-article

Open access

Pannier: A Container-based Flash Cache for Compound Objects

Authors:

Philip Shilane,

Grant WallaceAuthors Info & Claims

Middleware '15: Proceedings of the 16th Annual Middleware Conference

Pages 50 - 62

https://doi.org/10.1145/2814576.2814734

Published: 24 November 2015 Publication History

Abstract

Classic caching algorithms leverage recency, access count, and/or other properties of cached blocks at per-block granularity. However, for media such as flash which have performance and wear penalties for small overwrites, implementing cache policies at a larger granularity is beneficial. Recent research has focused on buffering small blocks and writing in large granularities, called containers, but it has not explored the ramifications and best strategies for caching compound blocks consisting of logically distinct, but physically co-located, blocks. Containers may have highly diverse blocks, with mixtures of frequently accessed, infrequently accessed, and invalidated blocks.

We propose and evaluate Pannier, a flash cache middleware that provides high performance while extending flash lifespan. Pannier uses three main techniques: (1) leveraging block access counts to manage cache containers, (2) incorporating block liveness as a property to improve flash cache space efficiency, and (3) designing a multi-step feedback controller to ensure a flash cache does not wear out in its lifespan while maintaining performance. Our evaluation shows that Pannier improves flash cache performance and extends lifespan beyond previous per-block and container-aware caching policies. More fundamentally, our investigation highlights the importance of creating new policies for caching compound blocks in flash.

References

[1]

A. Badam and V. S. Pai. SSDAlloc: Hybrid SSD/RAM Memory Management Made Easy. NSDI, 2011.

Digital Library

[2]

L. A. Belady. A Study of Replacement Algorithms for a Virtual-storage Computer. IBM Syst. J., 1966.

Digital Library

[3]

L. Breslau et al. Web Caching and Zipf-like Distributions: Evidence and Implications. INFOCOM, 1999.

[4]

M. Busari and C. Williamson. ProWGen: A Synthetic Workload Generation Tool for Simulation Evaluation of Web Proxy Caches. Comput. Netw., 2002.

Digital Library

[5]

P. Cao and S. Irani. Cost-aware WWW Proxy Caching Algorithms. USITS, 1997.

Digital Library

[6]

F. Chen, D. A. Koufaty, and X. Zhang. Understanding Intrinsic Characteristics and System Implications of Flash Memory Based Solid State Drives. SIGMETRICS, 2009.

Digital Library

[7]

J. Dean and L. A. Barroso. The Tail at Scale. Commun. ACM, 2013.

Digital Library

[8]

G. Einziger and R. Friedman. TinyLFU: A Highly Efficient Cache Admission Policy. IEEE PDP, 2014.

Digital Library

[9]

Y. Hu et al. Performance Impact and Interplay of SSD Parallelism Through Advanced Commands, Allocation Strategy and Data Granularity. ICS, 2011.

Digital Library

[10]

A. Jaleel et al. High Performance Cache Replacement Using Re-reference Interval Prediction (RRIP). ISCA, 2010.

Digital Library

[11]

M. Jeon et al. Workload Characterization and Performance Implications of Large-Scale Blog Servers. ACM TOW, 2012.

Digital Library

[12]

S. Jiang and X. Zhang. LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance. SIGMETRICS, 2002.

Digital Library

[13]

H. Jo et al. FAB: Flash-aware Buffer Management Policy for Portable Media Players. IEEE TOCE, 2006.

Digital Library

[14]

R. Karedla, J. S. Love, and B. G. Wherry. Caching Strategies to Improve Disk System Performance. Computer, 1994.

Digital Library

[15]

S. Kavalanekar et al. Characterization of Storage Workload Traces from Production Windows Servers. IISWC, 2008.

[16]

H. Kim and S. Ahn. BPLRU: A Buffer Management Scheme for Improving Random Writes in Flash Storage. FAST, 2008.

Digital Library

[17]

C. Li et al. Nitro: A Capacity-Optimized SSD Cache for Primary Storage. USENIX ATC, 2014.

Digital Library

[18]

N. Megiddo and D. S. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. FAST, 2003.

Digital Library

[19]

Micron MLC SSD Specification, 2013. http://www.micron.com/products/nand-flash/.

[20]

S. Muralidhar et al. f4: Facebook's Warm BLOB Storage System. OSDI, 2014.

Digital Library

[21]

D. Narayanan, A. Donnelly, and A. Rowstron. Write Off-loading: Practical Power Management for Enterprise Storage. FAST, 2008.

Digital Library

[22]

Y. Oh et al. Caching Less for Better Performance: Balancing Cache Size and Update Cost of Flash Memory Cache in Hybrid Storage Systems. FAST, 2012.

Digital Library

[23]

J. Ouyang et al. SDF: Software-defined Flash for Webscale Internet Storage Systems. ASPLOS, 2014.

Digital Library

[24]

V. Phalke and B. Gopinath. An Inter-reference Gap Model for Temporal Locality in Program Behavior. SIGMETRICS, 1995.

Digital Library

[25]

D. Qin, A. D. Brown, and A. Goel. Reliable Writeback for Client-side Flash Caches. USENIX ATC, 2014.

Digital Library

[26]

M. K. Qureshi et al. Adaptive Insertion Policies for High Performance Caching. ISCA, 2007.

Digital Library

[27]

J. T. Robinson and M. V. Devarakonda. Data Cache Management Using Frequency-based Replacement. SIGMETRICS, 1990.

Digital Library

[28]

M. Rosenblum and J. K. Ousterhout. The Design and Implementation of A Log-structured File System. ACM TOCS, 1992.

Digital Library

[29]

Samsung Server SSD Specification. www.samsung.com/serverssd/, 2015.

[30]

SanDisk SATA Solid State Drives. http://www.sandisk.com/enterprise/sata-ssd/, 2015.

[31]

M. Saxena, M. M. Swift, and Y. Zhang. FlashTier: A Lightweight, Consistent and Durable Storage Cache. EuroSys, 2012.

Digital Library

[32]

H. Shim, P. Shilane, and W. Hsu. Characterization of Incremental Data Changes for Efficient Data Protection. USENIX ATC, 2013.

Digital Library

[33]

Y. Smaragdakis, S. Kaplan, and P. Wilson. EELRU: Simple and Effective Adaptive Page Replacement. SIGMETRICS, 1999.

Digital Library

[34]

L. Sonneborn and F. Van Vleck. The Bang-Bang Principle for Linear Control Systems. SIAM J. Control, 1965.

[35]

L. Tang et al. RIPQ: Effective Photo Caching Algorithm for Facebook. FAST, 2015.

[36]

J. Wang and Y. Hu. WOLF--A Novel Reordering Write Buffer to Boost the Performance of Log-Structured File System. FAST, 2002.

Digital Library

[37]

J. Wilkes et al. The HP AutoRAID Hierarchical Storage System. SOSP, 1995.

Digital Library

[38]

Y. Zhou, Z. Chen, and K. Li. The Multi-Queue Replacement Algorithm for Second Level Buffer Caches. USENIX ATC, 2001.

Digital Library

Cited By

Bao NChai YQin XWang C(2022)MacroTrend: A Write-Efficient Cache Algorithm for NVM-Based Read CacheJournal of Computer Science and Technology10.1007/s11390-021-0178-637:1(207-230)Online publication date: 31-Jan-2022
https://doi.org/10.1007/s11390-021-0178-6
Yang JYue YRashmi K(2021)A Large-scale Analysis of Hundreds of In-memory Key-value Cache Clusters at TwitterACM Transactions on Storage10.1145/346852117:3(1-35)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1145/3468521
Tan YXu CXie JYan ZJiang HSrisa-an WChen XLiu D(2021)Improving the Performance of Deduplication-Based Storage Cache via Content-Driven Cache Management MethodsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.301270432:1(214-228)Online publication date: 1-Jan-2021
https://doi.org/10.1109/TPDS.2020.3012704
Show More Cited By

Index Terms

Pannier: A Container-based Flash Cache for Compound Objects
1. Software and its engineering
  1. Software creation and management
    1. Designing software
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems

Recommendations

Pannier: Design and Analysis of a Container-Based Flash Cache for Compound Objects
Special Issue on FAST 2017 and Regular Papers

Classic caching algorithms leverage recency, access count, and/or other properties of cached blocks at per-block granularity. However, for media such as flash which have performance and wear penalties for small overwrites, implementing cache policies at ...
Bucket-Based Expiration Algorithm: Improving Eviction Efficiency for In-Memory Key-Value Database
MEMSYS '20: Proceedings of the International Symposium on Memory Systems

Evicting expired keys for an in-memory key-value database is essential to save its memory resources and control its memory usage not exceeding its memory limit. Existing randomized expiration algorithms randomly sample keys from the key space ...
Design and Optimization of Large Size and Low Overhead Off-Chip Caches

Large off-chip L3 caches can significantly improve the performance of memory-intensive applications. However, conventional L3 SRAM caches are facing two issues as those applications require increasingly large caches. First, an SRAM cache has a limited ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Middleware '15: Proceedings of the 16th Annual Middleware Conference

November 2015

295 pages

ISBN:9781450336185

DOI:10.1145/2814576

General Chairs:
Rodger Lea
The University of British Columbia, Canada
,
Sathish Gopalakrishnan
The University of British Columbia, Canada
,
Program Chairs:
Eli Tilevich
Virginia Tech, USA
,
Amy L. Murphy
Bruno Kessler Foundation, Italy
,
Publications Chair:
Michael Blackstock
The University of British Columbia, Canada

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery
USENIX Assoc: USENIX Assoc
IFIP: International Federation for Information Processing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

Middleware '15

Sponsor:

ACM
USENIX Assoc
IFIP

Middleware '15: 16th International Middleware Conference

December 7 - 11, 2015

BC, Vancouver, Canada

Acceptance Rates

Middleware '15 Paper Acceptance Rate 23 of 118 submissions, 19%;

Overall Acceptance Rate 203 of 948 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
1,397
Total Downloads

Downloads (Last 12 months)132
Downloads (Last 6 weeks)19

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bao NChai YQin XWang C(2022)MacroTrend: A Write-Efficient Cache Algorithm for NVM-Based Read CacheJournal of Computer Science and Technology10.1007/s11390-021-0178-637:1(207-230)Online publication date: 31-Jan-2022
https://doi.org/10.1007/s11390-021-0178-6
Yang JYue YRashmi K(2021)A Large-scale Analysis of Hundreds of In-memory Key-value Cache Clusters at TwitterACM Transactions on Storage10.1145/346852117:3(1-35)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1145/3468521
Tan YXu CXie JYan ZJiang HSrisa-an WChen XLiu D(2021)Improving the Performance of Deduplication-Based Storage Cache via Content-Driven Cache Management MethodsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.301270432:1(214-228)Online publication date: 1-Jan-2021
https://doi.org/10.1109/TPDS.2020.3012704
Wijaya M(2020)Distributed proxy cache replacement algorithm to improve web server performanceJurnal Teknologi dan Sistem Komputer10.14710/jtsiskom.8.1.2020.1-58:1(1-5)Online publication date: 31-Jan-2020
https://doi.org/10.14710/jtsiskom.8.1.2020.1-5
Solaiman KAdnan M(2020)WLEC: A Not So Cold Architecture to Mitigate Cold Start Problem in Serverless Computing2020 IEEE International Conference on Cloud Engineering (IC2E)10.1109/IC2E48712.2020.00022(144-153)Online publication date: Apr-2020
https://doi.org/10.1109/IC2E48712.2020.00022
Tai AKryczka AKanaujia SJamieson KFreedman MCidon ADan TDahlia M(2019)Who's afraid of uncorrectable bit errors? online recovery of flash errors with distributed redundancyProceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference10.5555/3358807.3358891(977-991)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.5555/3358807.3358891
Eisenman ACidon APergament EHaimovich OStutsman RAlizadeh MKatti SLorch JYu M(2019)FlashieldProceedings of the 16th USENIX Conference on Networked Systems Design and Implementation10.5555/3323234.3323241(65-78)Online publication date: 26-Feb-2019
https://dl.acm.org/doi/10.5555/3323234.3323241
Zhou KSun SWang HHuang PHe XLai RLi WLiu WYang T(2019)Improving Cache Performance for Large-Scale Photo Stores via Heuristic Prefetching SchemeIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.2902392(1-1)Online publication date: 2019
https://doi.org/10.1109/TPDS.2019.2902392
Tan YXia WXie JXu CYan ZJiang HZhao YFu MChen XLiu D(2019)CDAC: Content-Driven Deduplication-Aware Storage Cache2019 35th Symposium on Mass Storage Systems and Technologies (MSST)10.1109/MSST.2019.00008(282-291)Online publication date: May-2019
https://doi.org/10.1109/MSST.2019.00008
Zhou KSun SWang HHuang PHe XLan RLi WLiu WYang T(2018)Demystifying Cache Policies for Photo Stores at ScaleProceedings of the 2018 International Conference on Supercomputing10.1145/3205289.3205299(284-294)Online publication date: 12-Jun-2018
https://dl.acm.org/doi/10.1145/3205289.3205299
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten