计算机科学技术学报 ›› 2022,Vol. 37 ›› Issue (1): 207-230.doi: 10.1007/s11390-021-0178-6

所属专题: Computer Architecture and Systems

• • 上一篇    下一篇



  • 收稿日期:2019-11-13 修回日期:2021-01-25 接受日期:2021-05-21 出版日期:2022-01-28 发布日期:2022-01-28

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.

4、结果(Result & Findings):

关键词: 非易失内存, 固态硬盘, 缓存, 耐久性

Abstract: 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:一种具有高读写性能的缓存感知的动态学习索引[J]. 计算机科学技术学报, 2021, 36(4): 721-740.
[2] Anthony Kougkas, Hariharan Devarajan, Xian-He Sun. 使用多层数据缓冲和预取实现I/O加速[J]. 计算机科学技术学报, 2020, 35(1): 92-120.
[3] Naveen Kumar, Ashutosh Kumar Singh, Abdul Aleem, Shashank Srivastava. 命名数据网络中的安全攻击[J]. 计算机科学技术学报, 2019, 34(6): 1319-1350.
[4] Peng Zhao, Chen Ding, Lei Liu, Jiping Yu, Wentao Han, Xiao-Bing Feng. Cacheap:图计算可移植协同输入/输出优化[J]. 计算机科学技术学报, 2019, 34(3): 690-706.
[5] Wen-Guo Liu, Ling-Fang Zeng, Dan Feng, Kenneth B. Kent. ROCO:用固态盘做缓存来改进主机端感知的叠瓦式磁记录磁盘的性能[J]. 计算机科学技术学报, 2019, 34(1): 61-76.
[6] Ziqi Fan, Dongchul Park. 延长综合非易失性内存写入缓冲SSD使用时间[J]. 计算机科学技术学报, 2019, 34(1): 113-132.
[7] Jian Liu, Yun-Peng Chai, Xiao Qin, Yao-Hong Liu. 一种用于提高数据去重系统选择性恢复性能的高耐久性固态硬盘读缓存[J]. , 2018, 33(1): 58-78.
[8] Wei-Bo Chu, Li-Fang Wang, Ze-Jun Jiang, Alan Chin-Chen Chang. 采用多路随机缓存技术保护ICN网络用户隐私[J]. , 2017, 32(3): 585-598.
[9] Xiao-Dong Meng, Chen-Tao Wu, Min-Yi Guo, Jie Li, Xiao-Yao Liang, Bin Yao, Long Zheng. 一种基于标签频率的多级存储系统IO性能的改进方法[J]. , 2017, 32(2): 312-328.
[10] Dongchul Park, Ziqi Fan, Young Jin Nam, David H. C. Du. 一种提升数据去重备份储存读取性能的预读缓存器[J]. , 2017, 32(1): 26-40.
[11] Mei Li, Hong-Jun Zhang, Yan-Jun Wu, Chen Zhao. 一种用于内存键值缓存系统的紧凑型抗扫描缓存替换框架[J]. , 2017, 32(1): 55-67.
[12] En Wang, Yong-Jian Yang, Jie Wu, Fellow, IEEE, Wen-Bin Liu. 容迟网络中基于报文优先级的缓存调度方法[J]. , 2016, 31(6): 1228-1245.
[13] Bing Zhou, Jiang-Tao Wen. 重复数据删除系统元数据缓存效率提升研究[J]. , 2016, 31(4): 805-819.
[14] Yuan-Chao Xu, Hu Wan, Ke-Ni Qiu, Tao Li, Wei-Gong Zhang. 降低单级存储移动终端系统的同步开销[J]. , 2016, 31(4): 836-848.
[15] Jishen Zhao, Cong Xu, Tao Zhang, Yuan Xie. 优化带宽的非易失性混合缓存设计[J]. , 2016, 31(1): 20-35.
Full text



[1] . Online First Under Construction [J]. 计算机科学技术学报, 0, (): 1 .
[2] Zhi-Neng Chen, Chong-Wah Ngo, Wei Zhang, Juan Cao, Yu-Gang Jiang. 网络视频人脸—姓名关联:大规模数据库,基准实验和开放性问题[J]. , 2014, 29(5): 785 -798 .
[3] Fei Xia, De-Jun Jiang, Jin Xiong, Ning-Hui Sun. PCM内存系统研究综述[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. 高性能计算专用文件系统[J]. 计算机科学技术学报, 2020, 35(1): 4 -26 .
[5] Yu-Tong Lu, Peng Cheng, Zhi-Guang Chen. Tianhe-2数据存储与管理系统设计与实现[J]. 计算机科学技术学报, 2020, 35(1): 27 -46 .
[6] Reza Jafari Ziarani, Reza Ravanmehr. 推荐系统中的意外效应:系统文献综述[J]. 计算机科学技术学报, 2021, 36(2): 375 -396 .
[7] Bo-Han Li, Yi Liu, An-Man Zhang, Wen-Huan Wang, Shuo Wan. 实体消解中分块技术的综述[J]. 计算机科学技术学报, 2020, 35(4): 769 -793 .
[8] Lie-Huang Zhu, Bao-Kun Zheng, Meng Shen, Feng Gao, Hong-Yu Li, Ke-Xin Shi. 比特币系统的数据安全和隐私综述[J]. 计算机科学技术学报, 2020, 35(4): 843 -862 .
[9] 梁盾, 郭元晨, 张少魁, 穆太江, 黄晓蕾. 车道检测-新结果和调查研究[J]. 计算机科学技术学报, 2020, 35(3): 493 -505 .
[10] Lan Huang, Da-Lin Li, Kang-Ping Wang, Teng Gao, Adriano Tavares. 一个关于高级综合工具性能优化的综述[J]. 计算机科学技术学报, 2020, 35(3): 697 -720 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn