Constructing Cache Algorithm for Flash by Leveraging Page Reconstruction and Data Temperature Recognition

doi:10.3778/j.issn.1673-9418.2003014

Abstract

Abstract:

NAND flash based solid state disks (SSD) have better performance than magnetic disks and are gradually replacing hard disks in desktop systems. However, although DRAM is embedded in SSD as a buffer, SSD may also produce unstable write performance with continuous writing, because non-overwrite write and garbage collection(GC) operations are frequently triggered when physical pages are written. Aiming at this problem, a new flash buffer management strategy called PRLRU (least recently used algorithm by page reconstruction) is proposed, which manages the buffer through the page reconstruction mechanism and the data temperature recognition mechanism. The page reconfiguration mechanism combines pages with valid data that are less than one page size with other pages and then writes back to the flash memory to reduce the actual write operation by minimizing the number of non-overwrite write operations. The data temperature recognition mechanism performs temperature level marking on the cached pages, and then writes back the pages in a predetermined priority order. Test it with real workloads, the experimental results show that PRLRU can effectively improve SSD performance and prolong SSD lifetime. Compared with LRU, BPLRU and 2QW-Clock, the write performance of PRLRU is increased by 34.5%, 22.8% and 28.8%, respectively on average, the read performance increased by 12.5%, 10.6% and 8.3%, respectively on average, and the amount of garbage collection decreased by 10.5%, 8.7% and 6.3%, respectively on average.

Key words: flash, non-overwrite write operation, garbage collection operation, page reconstruction, data temperature identification

摘要：

基于闪存的固态盘（SSD）具有比磁盘更加优越的性能，并且在桌面系统中逐渐替代磁盘。但是，尽管在SSD中嵌入了DRAM作为缓存，闪存在不断写入的过程中也可能产生不稳定的写性能，主要是因为逻辑页写入时会频繁引发非覆盖写和垃圾回收操作。针对此问题，提出了一种叫作PRLRU的新型闪存缓存管理方法，通过页面重构机制以及数据温度识别机制来管理缓存区。页面重构机制把即将回写的有效数据未满一个整页大小的页与多个其他有效数据不足一个页大小的页进行数据重组后再回写至闪存，通过尽可能减少非覆盖写操作来达到减少实际写操作的目的。数据温度识别机制通过对缓存页进行温度等级标记，按预定优先级顺序回写缓存页。对真实负载进行测试，实验结果表明，PRLRU能够有效提高SSD性能并延长SSD使用寿命，与LRU、BPLRU和2QW-Clock三种算法相比，写性能平均分别提高了34.5%、22.8%和28.8%，读性能平均分别提高了12.5%、10.6%和8.3%，垃圾回收数量平均分别降低了10.5%、8.7%和6.3%。

关键词: 闪存, 非覆盖写, 垃圾回收, 页面重构, 数据温度识别

ZENG Xiangwei, DENG Yuhui. Constructing Cache Algorithm for Flash by Leveraging Page Reconstruction and Data Temperature Recognition[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(1): 84-95.

曾祥伟, 邓玉辉. 利用页面重构与数据温度识别的闪存缓存算法[J]. 计算机科学与探索, 2021, 15(1): 84-95.

References

[1] KIM H, AHN S. BPLRU: a buffer management scheme for improving random writes in flash storage[C]//Proceedings of the 6th USENIX Conference on File and Storage Tech-nologies, San Jose, Feb 26-29, 2008. Berkeley: USENIX Asso-ciation, 2008: 239-252.
[2] DENG Y H, ZHOU J P. Architectures and optimization methods of flash memory based storage systems[J]. Journal of Systems Architecture-Embedded Systems Design, 2011, 57(2): 214-227.
[3] WU S Z, LIN Y P, MAO B, et al. GCaR: garbage collection aware cache management with improved performance for flash-based SSDs[C]//Proceedings of the 2016 International Conference on Supercomputing, Istanbul, Jun 1-3, 2016. New York: ACM, 2016: 28.
[4] LU Y Y, SHU J W, ZHENG W M. Extending the lifetime of flash-based storage through reducing write amplification from file systems[C]//Proceedings of the 11th USENIX Conference on File and Storage Technologies, San Jose, Feb 12-15, 2013. Berkeley: USENIX Association, 2013: 257-270.
[5] DENG Y H. What is the future of disk drives, death or rebirth?[J]. ACM Computing Surveys, 2011, 43(3): 445-471.
[6] WU S Z, Mao B, Lin Y P, et al. Improving performance for flash-based storage systems through GC-aware cache manage-ment[J]. IEEE Transactions on Parallel and Distributed Sys-tems, 2017, 28(10): 2852-2865.
[7] LI F, LU Y Y, WU Z J, et al. ASCache: an approximate SSD cache for error-tolerant applications[C]//Proceedings of the 56th Annual Design Automation Conference 2019, Las Vegas, Jun 2-6, 2019. New York: ACM, 2019: 214.
[8] JI C, CHANG L P, WU C, et al. An I/O scheduling strategy for embedded flash storage devices with mapping cache[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(4): 756-769.
[9] SEOL J, SHIM H, KIM J, et al. A buffer replacement algorithm exploiting multi-chip parallelism in solid state disks[C]//Proceedings of the 2009 International Conference on Com-pilers, Architecture, and Synthesis for Embedded Systems, Grenoble, Oct 11-16, 2009. New York: ACM, 2009: 137-146.
[10] LU Y Y, SHU J W. Survey on flash-based storage systems [J]. Journal of Computer Research & Development, 2013, 50(1): 49-59.
陆游游, 舒继武. 闪存存储系统综述[J]. 计算机研究与发展, 2013, 50(1): 49-59.
[11] HU Y, JIANG H, FENG D, et al. Performance impact and interplay of SSD parallelism through advanced commands, allocation strategy and data granularity[C]//Proceedings of the 25th International Conference on Supercomputing, Tucson, May 31-Jun 4, 2011. New York: ACM, 2011: 96-107.
[12] GUPTA A, KIM Y, URGAONKAR B. DFTL: a flash transla-tion layer employing demand-based selective caching of page-level address mappings[C]//Proceedings of the 14th Inter-national Conference on Architectural Support for Program-ming Languages and Operating Systems, Washington, Mar 7-11, 2009. New York: ACM, 2009: 229-240.
[13] BAN A. Flash file system: U.S. Patent 5404485[P]. 1995-04-04 [2019-08-09]. https://www.google.com/patents/US5404485.
[14] LEE S W, PARK D J, CHUNG T S, et al. A log buffer-based flash translation layer using fully-associative sector transla-tion[J]. ACM Transactions on Embedded Computing Systems, 2007, 6(3): 18.
[15] LEE S, SHIN D, KIM Y J, et al. LAST: locality-aware sector translation for NAND flash memory-based storage systems[J]. ACM SIGOPS Operating Systems Review, 2008, 42(6): 36-42.
[16] MEGIDDO N, MODHA D S. Outperforming LRU with an adaptive replacement cache algorithm[J]. Computer, 2004, 37(4): 58-65.
[17] KIM H, SHIN D, JEONG Y H, et al. SHRD: improving spa-tial locality in flash storage accesses by sequentializing in host and randomizing in device[C]//Proceedings of the 15th USENIX Conference on File and Storage Technologies, Santa Clara, Feb 27-Mar 2, 2017. Berkeley: USENIX Association, 2017: 271-284.
[18] MAO B, WU S Z, JIANG H, et al. EDC: improving the perfor-mance and space efficiency of flash-based storage systems with elastic data compression[J]. IEEE Transactions on Par-allel and Distributed Systems, 2018, 29(6): 1261-1274.
[19] JUNG H, SHIM H, PARK S, et al. LRU-WSR: integration of LRU and writes sequence reordering for flash memory[J]. IEEE Transactions on Consumer Electronics, 2008, 54(3): 1215-1223.
[20] SHI L, LI J, XUE C J, et al. ExLRU: a unified write buffer cache management for flash memory[C]//Proceedings of the 9th ACM International Conference on Embedded Software, Taipei, China, Oct 9-14, 2011. New York: ACM, 2011: 339-348.
[21] JIN P, OU Y, H?RDER T, et al. AD-LRU: an efficient buffer replacement algorithm for flash-based databases[J]. Data & Knowledge Engineering, 2012, 72: 83-102.
[22] PARK S, JUNG D, KANG J, et al. CFLRU: a replacement algorithm for flash memory[C]//Proceedings of the 2006 Inter-national Conference on Compilers, Architecture, and Synthesis for Embedded Systems, Seoul, Oct 22-25, 2006. New York:ACM, 2006: 234-241.
[23] HE D, WANG F, FENG D, et al. 2QW-Clock: an efficient SSD buffer management algorithm[C]//Proceedings of the 22nd IEEE International Conference on High Performance Computing, Bengaluru, Dec 16-19, 2015. Washington: IEEE Computer Society, 2015: 47-53.
[24] JOHNSON T, SHASHA D. 2Q: a low overhead high perfor-mance buffer management replacement algorithm[C]//Procee-dings of the 20th International Conference on Very Large Data Bases, Santiago, Sep 12-15, 1994. San Mateo: Morgan Kau-fmann ,1994: 439-450.
[25] CHAN J C W, DING Q, LEE P P C, et al. Parity logging with reserved space: towards ef?cient updates and recovery in erasure-coded clustered storage[C]//Proceedings of the 12th USENIX Conference on File and Storage Technologies, Santa Clara, Feb 16-19, 2015. Berkeley: USENIX Association, 2014: 163-176.