Journal of Computer Science and Technology ›› 2022, Vol. 37 ›› Issue (1): 207-230.doi: 10.1007/s11390-021-0178-6

Special Issue: Computer Architecture and Systems

• Regular Paper • Previous Articles     Next Articles

MacroTrend: A Write-Efficient Cache Algorithm for NVM-Based Read Cache

Ning Bao1,2 (鲍宁), Yun-Peng Chai1,2,* (柴云鹏), Member, CCF, Xiao Qin3 (秦啸), Senior Member, IEEE, and Chuan-Wen Wang1,2 (王传雯)        

  1. 1Key Laboratory of Data Engineering and Knowledge Engineering, Ministry of Education, Beijing 100872, China
    2School of Information, Renmin University of China, Beijing 100872, China
    3Samuel Ginn College of Engineering, Auburn University, Alabama 36830, U.S.A.
  • Received:2019-11-13 Revised:2021-01-25 Accepted:2021-05-21 Online:2022-01-28 Published:2022-01-28
  • Contact: Yun-Peng Chai E-mail:ypchai@ruc.edu.cn
  • About author:Yun-Peng Chai received his B.E. and Ph.D. degrees in computer science and technology from Tsinghua University, Beijing, in 2004 and 2009, respectively. He is currently an associate professor at School of Information, Renmin University of China, Beijing. His research interests include emerging storage techniques, cloud computing, and distributed systems. He is a member of CCF.
  • Supported by:
    This work was supported by the National Key Research and Development Program of China under Grant No. 2019YFE0198600 and the National Natural Science Foundation of China under Grant Nos.61972402, 61972275, and 61732014.

PDF (PC)

45

Supplement

1

The future storage systems are expected to contain a wide variety of storage media and layers due to the rapid development of NVM (non-volatile memory) techniques. For NVM-based read caches, many kinds of NVM devices cannot stand frequent data updates due to limited write endurance or high energy consumption of writing. However, traditional cache algorithms have to update cached blocks frequently because it is difficult for them to predict long-term popularity according to such limited information about data blocks, such as only a single value or a queue that reflects frequency or recency. In this paper, we propose a new MacroTrend (macroscopic trend) prediction method to discover long-term hot blocks through blocks' macro trends illustrated by their access count histograms. And then a new cache replacement algorithm is designed based on the MacroTrend prediction to greatly reduce the write amount while improving the hit ratio. We conduct extensive experiments driven by a series of real-world traces and find that compared with LRU, MacroTrend can reduce the write amounts of NVM cache devices significantly with similar hit ratios, leading to longer NVM lifetime or less energy consumption.

Key words: non-volatile memory (NVM); solid state disk (SSD); cache; enduranc;

[1] Leventhal A. Flash storage memory. Communications of the ACM, 2008, 51(7): 47-51. DOI: 10.1145/1364782.1364796.
[2] Lee B C, Ipek E, Mutlu O, Burger D. Architecting phase change memory as a scalable dram alternative. In Proc. the 36th Annual International Symposium on Computer Architecture, June 2009, pp.2-13. DOI: 10.1145/1555754.1555758.
[3] Xu C, Niu D, Muralimanohar N, Balasubramonian R, Zhang T, Yu S, Xie Y. Overcoming the challenges of crossbar resistive memory architectures. In Proc. the 21st International Symposium on High Performance Computer Architecture, February 2015, pp.476-488. DOI: 10.1109/HPCA.2015.7056056.
[4] Hosomi M, Yamagishi H, Yamamoto T et al. A novel nonvolatile memory with spin torque transfer magnetization switching: Spin-RAM. In Proc. the IEEE International Electron Devices Meeting, December 2005, pp.459-462. DOI: 10.1109/IEDM.2005.1609379.
[5] Grupp L M, Davis J D, Swanson S. The bleak future of NAND flash memory. In Proc. the 10th USENIX Conference on File and Storage Technologies, February 2012.
[6] Boboila S, Desnoyers P. Write endurance in flash drives: Measurements and analysis. In Proc. the 8th USENIX Conference on File and Storage Technologies, February 2010, pp.115-128.
[7] Xia F, Jiang D, Xiong J, Sun N. HiKV: A hybrid index key-value store for DRAM-NVM memory systems. In Proc. the 2017 USENIX Annual Technical Conference, July 2017, pp.349-362.
[8] Jiang L, Zhang Y, Yang J. ER: Elastic RESET for low power and long endurance MLC based phase change memory. In Proc. the 2012 ACM/IEEE International Symposium on Low Power Electronics and Design, July 2012, pp.39-44. DOI: 10.1145/2333660.2333672.
[9] Hirofuchi T, Takano R. RAMinate: Hypervisor-based virtualization for hybrid main memory systems. In Proc. the 7th ACM Symposium on Cloud Computing, October 2016, pp.112-125. DOI: 10.1145/2987550.2987570.
[10] Pritchett T, Thottethodi M. SieveStore: A highly-selective, ensemble-level disk cache for cost-performance. In Proc. the 37th Annual International Symposium on Computer Architecture, June 2010, pp.163-174. DOI: 10.1145/1816038.1815982.
[11] Huang S, Wei Q, Feng D, Chen J, Chen C. Improving flash-based disk cache with lazy adaptive replacement. ACM Transactions on Storage, 2016, 12(2): Article No.8. DOI: 10.1145/2737832.
[12] Megiddo N, Modha D S. ARC: A self-tuning, low overhead replacement cache. In Proc. the 2nd USENIX Conference on File and Storage Technologies, March 2003, pp.115-130.
[13] Chai Y, Du Z, Qin X, Bader D A. WEC: Improving durability of SSD cache drives by caching write-efficient data. IEEE Transactions on Computers, 2015, 64(11): 3304-3316. DOI: 10.1109/TC.2015.2401029.
[14] Wang L, Zhan J, Luo C et al. BigDataBench: A big data benchmark suite from Internet services. In Proc. the 20th International Symposium on High Performance Computer Architecture, February 2014, pp.488-499. DOI: 10.1109/HPCA.2014.6835958.
[15] Narayanan D, Donnelly A, Rowstron A. Write off-loading: Practical power management for enterprise storage. ACM Transactions on Storage, 2008, 4(3): Article No.10. DOI: 10.1145/1416944.1416949.
[16] Robinson J T, Devarakonda M V. Data cache management using frequency-based replacement. In Proc. the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, April 1990, pp.134-142. DOI: 10.1145/98457.98523.
[17] Lee D, Choi J, Kim J H, Noh S H, Min S L, Cho Y, Kim C S. On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies. In Proc. the 1999 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, May 1999, pp.134-143. DOI: 10.1145/301453.301487.
[18] O'neil E J, O'neil P E, Weikum G. The LRU-K page replacement algorithm for database disk buffering. ACM SIGMOD Record, 1993, 22(2): 297-306. DOI: 10.1145/170036.170081.
[19] Zhou Y, Chen Z, Li K. Second-level buffer cache management. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(6): 505-519. DOI: 10.1109/TPDS.2004.13.
[20] Jiang S, Zhang X. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. ACM SIGMETRICS Performance Evaluation Review, 2002, 30(1): 31-42. DOI: 10.1145/511399.511340.
[21] Jiang S, Chen F, Zhang X. CLOCK-Pro: An effective improvement of the CLOCK replacement. In Proc. the 2005 USENIX Annual Technical Conference, April 2005, pp.323-336.
[22] Bansal S, Modha D S. CAR: Clock with adaptive replacement. In Proc. the 3rd USENIX Conference on File and Storage Technologies, March 2004, pp.187-200.
[23] Karedla R, Love J S, Wherry B G. Caching strategies to improve disk system performance. Computer, 1994, 27(3): 38-46. DOI: 10.1109/2.268884.
[24] Gao H, Wilkerson C. A dueling segmented LRU replacement algorithm with adaptive bypassing. In Proc. the 1st JILP Workshop on Computer Architecture Competitions, June 2010.
[25] Morales K, Lee B K. Fixed segmented LRU cache replacement scheme with selective caching. In Proc. the 31st International Performance Computing and Communications Conference, December 2012, pp.199-200. DOI: 10.1109/PCCC.2012.6407712.
[26] Saxena M, Swift M M, Zhang Y. FlashTier: A lightweight, consistent and durable storage cache. In Proc. the 7th ACM European Conference on Computer Systems, April 2012, pp.267-280. DOI: 10.1145/2168836.2168863.
[27] Kgil T, Roberts D, Mudge T. Improving NAND flash based disk caches. In Proc. the International Symposium on Computer Architecture, June 2008, pp.327-338. DOI: 10.1145/1394608.1382149.
[28] Yang Q, Ren J. I-CASH: Intelligently coupled array of SSD and HDD. In Proc. the 17th International Symposium on High Performance Computer Architecture, February 2011, pp.278-289. DOI: 10.1109/HPCA.2011.5749736.
[27] Ren J, Yang Q. A new buffer cache design exploiting both temporal and content localities. In Proc. the 30th International Conference on Distributed Computing Systems, June 2010, pp.273-282. DOI: 10.1109/ICDCS.2010.26.
[30] Zhang Y, Soundararajan G, Storer M W, Bairavasundaram L N, Subbiah S, Arpaci-Dusseau A C, Arpaci-Dusseau R H. Warming up storage-level caches with bonfire. In Proc. the 11th USENIX Conference on File and Storage Technologies, February 2013, pp.59-72.
[28] Matthews J, Trika S, Hensgen D, Coulson R, Grimsrud K. Intel$^{\mbox{\textregistered }}$ Turbo Memory: Nonvolatile disk caches in the storage hierarchy of mainstream computer systems. ACM Transactions on Storage, 2008, 4(2): Article No.4. DOI: 10.1145/1367829.1367830.
[29] Bao N, Chai Y, Qin X. A write-efficient cache algorithm based on macroscopic trend for NVM-based read cache. In Proc. the 2019 Design, Automation and Test in Europe Conference and Exhibition, March 2019, pp.1245-1248. DOI: 10.23919/DATE.2019.8715276.
[30] Dai N, Chai Y, Liang Y, Wang C. ETD-Cache: An expiration-time driven cache scheme to make SSD-based read cache endurable and cost-efficient. In Proc. the 12th ACM International Conference on Computing Frontiers, May 2015, Article No.26. DOI: 10.1145/2742854.2742881.
[31] Xia Q, Xiao W. High-performance and endurable cache management for flash-based read caching. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(12): 3518-3531. DOI: 10.1109/TPDS.2016.2537822.
[32] Tang L, Huang Q, Lloyd W, Kumar S, Li K. RIPQ: Advanced photo caching on flash for Facebook. In Proc. the 13th USENIX Conference on File and Storage Technologies, February 2015, pp.373-386.
[33] Li C, Shilane P, Douglis F, Wallace G. Pannier: A container-based flash cache for compound objects. In Proc. the 16th Annual Middleware Conference, November 2015, pp.50-62. DOI: 10.1145/2814576.2814734.
[34] Oh Y, Lee E, Hyun C, Choi J, Lee D, Noh S H. Enabling cost-effective flash based caching with an array of commodity SSDs. In Proc. the 16th Annual Middleware Conference, November 2015, pp.63-74. DOI: 10.1145/2814576.2814814.
[35] Yang J, Plasson N, Gillis G, Talagala N, Sundararaman S, Wood R. HEC: Improving endurance of high performance flash-based cache devices. In Proc. the 6th International Systems and Storage Conference, June 2013, Article No.10. DOI: 10.1145/2485732.2485743.
[36] Li W, Jean-Baptise G, Riveros J, Narasimhan G, Zhang T, Zhao M. CacheDedup: In-line deduplication for flash caching. In Proc. the 14th USENIX Conference on File and Storage Technologies, February 2016, pp.301-314.
[37] Arteaga D, Cabrera J, Xu J, Sundararaman S, Zhao M. CloudCache: On-demand flash cache management for cloud computing. In Proc. the 14th USENIX Conference on File and Storage Technologies, February 2016, pp.355-369.
[38] Waldspurger C A, Park N, Garthwaite A T, Ahmad I. Efficient MRC construction with SHARDS. In Proc. the 13th USENIX Conference on File and Storage Technologies, February 2015, pp.95-110.
[39] Park S Y, Jung D, Kang J U, Kim J S, Lee J. CFLRU: A replacement algorithm for flash memory. In Proc. the 2006 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, October 2006, pp.234-241. DOI: 10.1145/1176760.1176789.
[1] Zhou Zhang, Pei-Quan Jin, Xiao-Liang Wang, Yan-Qi Lv, Shou-Hong Wan, Xi-Ke Xie. COLIN: A Cache-Conscious Dynamic Learned Index with High Read/Write Performance [J]. Journal of Computer Science and Technology, 2021, 36(4): 721-740.
[2] Naveen Kumar, Ashutosh Kumar Singh, Abdul Aleem, Shashank Srivastava. Security Attacks in Named Data Networking: A Review and Research Directions [J]. Journal of Computer Science and Technology, 2019, 34(6): 1319-1350.
[3] Peng Zhao, Chen Ding, Lei Liu, Jiping Yu, Wentao Han, Xiao-Bing Feng. Cacheap: Portable and Collaborative I/O Optimization for Graph Processing [J]. Journal of Computer Science and Technology, 2019, 34(3): 690-706.
[4] Wen-Guo Liu, Ling-Fang Zeng, Dan Feng, Kenneth B. Kent. ROCO: Using a Solid State Drive Cache to Improve the Performance of a Host-Aware Shingled Magnetic Recording Drive [J]. Journal of Computer Science and Technology, 2019, 34(1): 61-76.
[5] Ziqi Fan, Dongchul Park. Extending SSD Lifespan with Comprehensive Non-Volatile Memory-Based Write Buffers [J]. Journal of Computer Science and Technology, 2019, 34(1): 113-132.
[6] Jian Liu, Yun-Peng Chai, Xiao Qin, Yao-Hong Liu. Endurable SSD-Based Read Cache for Improving the Performance of Selective Restore from Deduplication Systems [J]. , 2018, 33(1): 58-78.
[7] Wei-Bo Chu, Li-Fang Wang, Ze-Jun Jiang, Alan Chin-Chen Chang. Protecting User Privacy in a Multi-Path Information-Centric Network Using Multiple Random-Caches [J]. , 2017, 32(3): 585-598.
[8] Xiao-Dong Meng, Chen-Tao Wu, Min-Yi Guo, Jie Li, Xiao-Yao Liang, Bin Yao, Long Zheng. A Hint Frequency Based Approach to Enhancing the I/O Performance of Multilevel Cache Storage Systems [J]. , 2017, 32(2): 312-328.
[9] Dongchul Park, Ziqi Fan, Young Jin Nam, David H. C. Du. A Lookahead Read Cache: Improving Read Performance for Deduplication Backup Storage [J]. , 2017, 32(1): 26-40.
[10] Mei Li, Hong-Jun Zhang, Yan-Jun Wu, Chen Zhao. MemSC: A Scan-Resistant and Compact Cache Replacement Framework for Memory-Based Key-Value Cache Systems [J]. , 2017, 32(1): 55-67.
[11] Bing Zhou, Jiang-Tao Wen. Improving Metadata Caching Efficiency for Data Deduplication via In-RAM Metadata Utilization [J]. , 2016, 31(4): 805-819.
[12] Mei-Ying Bian, Su-Kyung Yoon, Jeong-Geun Kim, Sangjae Nam, Shin-Dug Kim. A Unified Buffering Management with Set Divisible Cache for PCM Main Memory [J]. , 2016, 31(1): 137-146.
[13] Jishen Zhao, Cong Xu, Tao Zhang, Yuan Xie. BACH:A Bandwidth-Aware Hybrid Cache Hierarchy Design with Nonvolatile Memories [J]. , 2016, 31(1): 20-35.
[14] Ling-Da Li, Jun-Lin Lu, Xu Cheng. Retention Benefit Based Intelligent Cache Replacement [J]. , 2014, 29(6): 947-961.
[15] Chen Ding, Xiaoya Xiang, Bin Bao, Hao Luo, Ying-Wei Luo, and Xiao-Lin Wang. Performance Metrics and Models for Shared Cache [J]. , 2014, 29(4): 692-712.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] . Online First Under Construction [J]. Journal of Computer Science and Technology, 0, (): 1 .
[2] Zhi-Neng Chen, Chong-Wah Ngo, Wei Zhang, Juan Cao, Yu-Gang Jiang. Name-Face Association in Web Videos: A Large-Scale Dataset, Baselines, and Open Issues[J]. , 2014, 29(5): 785 -798 .
[3] Fei Xia, De-Jun Jiang, Jin Xiong, Ning-Hui Sun. A Survey of Phase Change Memory Systems[J]. , 2015, 30(1): 121 -144 .
[4] André Brinkmann, Kathryn Mohror, Weikuan Yu, Philip Carns, Toni Cortes, Scott A. Klasky, Alberto Miranda, Franz-Josef Pfreundt, Robert B. Ross, Marc-André Vef. Ad Hoc File Systems for High-Performance Computing[J]. Journal of Computer Science and Technology, 2020, 35(1): 4 -26 .
[5] Yu-Tong Lu, Peng Cheng, Zhi-Guang Chen. Design and Implementation of the Tianhe-2 Data Storage and Management System[J]. Journal of Computer Science and Technology, 2020, 35(1): 27 -46 .
[6] Reza Jafari Ziarani, Reza Ravanmehr. Serendipity in Recommender Systems: A Systematic Literature Review[J]. Journal of Computer Science and Technology, 2021, 36(2): 375 -396 .
[7] Bo-Han Li, Yi Liu, An-Man Zhang, Wen-Huan Wang, Shuo Wan. A Survey on Blocking Technology of Entity Resolution[J]. Journal of Computer Science and Technology, 2020, 35(4): 769 -793 .
[8] Lie-Huang Zhu, Bao-Kun Zheng, Meng Shen, Feng Gao, Hong-Yu Li, Ke-Xin Shi. Data Security and Privacy in Bitcoin System: A Survey[J]. Journal of Computer Science and Technology, 2020, 35(4): 843 -862 .
[9] Dun Liang, Yuan-Chen Guo, Shao-Kui Zhang, Tai-Jiang Mu, Xiaolei Huang. Lane Detection: A Survey with New Results[J]. Journal of Computer Science and Technology, 2020, 35(3): 493 -505 .
[10] Lan Huang, Da-Lin Li, Kang-Ping Wang, Teng Gao, Adriano Tavares. A Survey on Performance Optimization of High-Level Synthesis Tools[J]. Journal of Computer Science and Technology, 2020, 35(3): 697 -720 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved