计算机科学技术学报 ›› 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.

PDF (PC)

45

补充材料

1

1、研究背景（context）：
近年来非易失内存已经开始实际应用，闪存、相变存储器已经应用非常广泛，ReRAM、STT-MRAM等也在逐渐接近产品化。这些非易失内存由于访问速度快，但价格较为昂贵，非常适合作为下层慢速存储设备的读缓存。但是这些非易失内存的写操作一般都存在一些挑战，包括写操作一般显著慢于读操作、写操作过多会提前损耗设备、写操作能耗过大等。因此，传统的缓存替换算法，如LRU和LFU等，会给非易失内存读缓存造成过大的写入压力，并不适合非易失内存。
2、目的（Objective）：
我们研究的目的是为非易失内存读缓存提出一种写高效的缓存算法，通过对长期热门数据的准确识别，在读缓存中长期保存长期热门数据，减少缓存数据块的交换，从而减小读缓存的写入压力，但同时能够保持较高的缓存命中率。
3、方法（Method）：
我们提出了一个长期热门数据的预测框架MacroTrend，追踪数据块在过去多个历史周期内的访问量变化规律，来准确挖掘长期热门数据。在对企业访问记录进行大量分析中，我们发现一些长期热门数据的历史访问量变化趋势的典型模式，包括稳定性模式S-pattern、连续性模式C-pattern、不规则模式I-pattern。如果数据块的历史访问量变化趋势符合越多的模式，那么它们越可能是长期热门数据。有别于已有缓存替换算法大都使用LRU等短期热门数据识别方法来选择数据，我们提出的新型写高效缓存替换算法MT采用了这种长期热门数据预测框架，从而比传统方法用更少的写入量得到更好的缓存命中率。
4、结果（Result & Findings）：
在基于实际企业访问记录的实验中，MT算法相对于经典的LRU算法可以减少平均95.3%的非易失内存读缓存的写入压力，同时缓存命中率比LRU提高24.0%。相对于同样提高缓存写效率的SieveStore算法，MT可以减少85.2%的写压力，同时将缓存命中率提升50.2%。
5、结论（Conclusions）：
结果说明MT算法在提升读缓存的写效率方面非常有效，主要原因是从热门数据选择方法上相对传统方法有了本质性的提升，通过准确识别长期热门数据，不需要频繁更新缓存数据，就可以得到更高的缓存命中率。MT算法在企业级存储系统中有广泛的应用场景，非常适应目前多种非易失内存器件快速发展、混合存储在企业中广泛应用的情况，有助于提升混合存储性能、延长非易失内存设备的使用寿命，以及降低其能耗。

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

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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[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
总访问量：