Cheng Li
Fred Douglis
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.
- A. Badam and V. S. Pai. SSDAlloc: Hybrid SSD/RAM Memory Management Made Easy. NSDI, 2011. Google Scholar
Digital Library
- L. A. Belady. A Study of Replacement Algorithms for a Virtual-storage Computer. IBM Syst. J., 1966. Google ScholarDigital Library
- L. Breslau et al. Web Caching and Zipf-like Distributions: Evidence and Implications. INFOCOM, 1999.Google ScholarCross Ref
- M. Busari and C. Williamson. ProWGen: A Synthetic Workload Generation Tool for Simulation Evaluation of Web Proxy Caches. Comput. Netw., 2002. Google ScholarDigital Library
- P. Cao and S. Irani. Cost-aware WWW Proxy Caching Algorithms. USITS, 1997. Google ScholarDigital Library
- F. Chen, D. A. Koufaty, and X. Zhang. Understanding Intrinsic Characteristics and System Implications of Flash Memory Based Solid State Drives. SIGMETRICS, 2009. Google ScholarDigital Library
- J. Dean and L. A. Barroso. The Tail at Scale. Commun. ACM, 2013. Google ScholarDigital Library
- G. Einziger and R. Friedman. TinyLFU: A Highly Efficient Cache Admission Policy. IEEE PDP, 2014. Google ScholarDigital Library
- Y. Hu et al. Performance Impact and Interplay of SSD Parallelism Through Advanced Commands, Allocation Strategy and Data Granularity. ICS, 2011. Google ScholarDigital Library
- A. Jaleel et al. High Performance Cache Replacement Using Re-reference Interval Prediction (RRIP). ISCA, 2010. Google ScholarDigital Library
- M. Jeon et al. Workload Characterization and Performance Implications of Large-Scale Blog Servers. ACM TOW, 2012. Google ScholarDigital Library
- S. Jiang and X. Zhang. LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance. SIGMETRICS, 2002. Google ScholarDigital Library
- H. Jo et al. FAB: Flash-aware Buffer Management Policy for Portable Media Players. IEEE TOCE, 2006. Google ScholarDigital Library
- R. Karedla, J. S. Love, and B. G. Wherry. Caching Strategies to Improve Disk System Performance. Computer, 1994. Google ScholarDigital Library
- S. Kavalanekar et al. Characterization of Storage Workload Traces from Production Windows Servers. IISWC, 2008.Google ScholarCross Ref
- H. Kim and S. Ahn. BPLRU: A Buffer Management Scheme for Improving Random Writes in Flash Storage. FAST, 2008. Google ScholarDigital Library
- C. Li et al. Nitro: A Capacity-Optimized SSD Cache for Primary Storage. USENIX ATC, 2014. Google ScholarDigital Library
- N. Megiddo and D. S. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. FAST, 2003. Google ScholarDigital Library
- Micron MLC SSD Specification, 2013. http://www.micron.com/products/nand-flash/.Google Scholar
- S. Muralidhar et al. f4: Facebook's Warm BLOB Storage System. OSDI, 2014. Google ScholarDigital Library
- D. Narayanan, A. Donnelly, and A. Rowstron. Write Off-loading: Practical Power Management for Enterprise Storage. FAST, 2008. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. Ouyang et al. SDF: Software-defined Flash for Webscale Internet Storage Systems. ASPLOS, 2014. Google ScholarDigital Library
- V. Phalke and B. Gopinath. An Inter-reference Gap Model for Temporal Locality in Program Behavior. SIGMETRICS, 1995. Google ScholarDigital Library
- D. Qin, A. D. Brown, and A. Goel. Reliable Writeback for Client-side Flash Caches. USENIX ATC, 2014. Google ScholarDigital Library
- M. K. Qureshi et al. Adaptive Insertion Policies for High Performance Caching. ISCA, 2007. Google ScholarDigital Library
- J. T. Robinson and M. V. Devarakonda. Data Cache Management Using Frequency-based Replacement. SIGMETRICS, 1990. Google ScholarDigital Library
- M. Rosenblum and J. K. Ousterhout. The Design and Implementation of A Log-structured File System. ACM TOCS, 1992. Google ScholarDigital Library
- Samsung Server SSD Specification. www.samsung.com/serverssd/, 2015.Google Scholar
- SanDisk SATA Solid State Drives. http://www.sandisk.com/enterprise/sata-ssd/, 2015.Google Scholar
- M. Saxena, M. M. Swift, and Y. Zhang. FlashTier: A Lightweight, Consistent and Durable Storage Cache. EuroSys, 2012. Google ScholarDigital Library
- H. Shim, P. Shilane, and W. Hsu. Characterization of Incremental Data Changes for Efficient Data Protection. USENIX ATC, 2013. Google ScholarDigital Library
- Y. Smaragdakis, S. Kaplan, and P. Wilson. EELRU: Simple and Effective Adaptive Page Replacement. SIGMETRICS, 1999. Google ScholarDigital Library
- L. Sonneborn and F. Van Vleck. The Bang-Bang Principle for Linear Control Systems. SIAM J. Control, 1965.Google Scholar
- L. Tang et al. RIPQ: Effective Photo Caching Algorithm for Facebook. FAST, 2015.Google Scholar
- J. Wang and Y. Hu. WOLF--A Novel Reordering Write Buffer to Boost the Performance of Log-Structured File System. FAST, 2002. Google ScholarDigital Library
- J. Wilkes et al. The HP AutoRAID Hierarchical Storage System. SOSP, 1995. Google ScholarDigital Library
- Y. Zhou, Z. Chen, and K. Li. The Multi-Queue Replacement Algorithm for Second Level Buffer Caches. USENIX ATC, 2001. Google ScholarDigital Library
Index Terms
- Pannier: A Container-based Flash Cache for Compound Objects
Recommendations
Pannier: Design and Analysis of a Container-Based Flash Cache for Compound Objects
Special Issue on FAST 2017 and Regular PapersClassic 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 SystemsEvicting 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