基于数据更新间隔的NAND闪存垃圾回收算法

doi:10.19678/j.issn.1000-3428.0061274

摘要/Abstract

摘要： 闪存因具有速度快、体积小等优点而广泛应用于数据存储领域，为提高NAND闪存的垃圾回收效率、延长闪存使用寿命，提出一种基于数据更新间隔的垃圾回收算法UIGC。计算闪存中空闲页的分散度，将其作为垃圾回收触发条件。从垃圾回收效率和磨损均衡效果2个方面出发，综合考虑块中无效页年龄累计和以及块中有效页比例，使用动态回收块选择和静态回收块选择相结合的策略来选择目标回收块，根据回收块中有效页数据更新间隔判断有效页热度，同时提出数据更新稳定性的概念来划分有效页的数据更新状态，将具有不同热度和更新状态的有效页数据分别存储在不同的空闲块中，从而提高块中数据的同步更新概率。实验结果表明，UIGC算法相较于CAT、FaGC等现有垃圾回收算法具有更优的垃圾回收效率和磨损均衡效果，并能有效延长闪存使用寿命。

关键词: NAND闪存垃圾, 磨损均衡, 更新间隔, 数据热度, 更新稳定性, 数据分离, 文件系统

Abstract: Flash memory is widely used in the field of data storage, owing to its high speed and compact volume.In this study, we propose a garbage collection algorithm called UIGC based on data update interval to improve the garbage collection efficiency of NAND flash memory and prolong the service life of flash memory in general.The proposed approach calculates the dispersion of empty free pages in flash memory as the trigger condition for garbage collection. With the two design aims of garbage collection efficiency and wear balance performance, the proposed approach comprehensively considers the cumulative age sum of invalid pages and the proportion of effective pages in a block. Additionally, our approach combines dynamic and static collection block selection to select a target collection block and judge the effective page heat according to the data update interval of effective pages therein.Furthermore, the concept of data update stability is proposed, which is used simultaneously to divide the data update status of effective pages, and the effective page data with different heat and update statuses are stored in different idle blocks to improve the synchronous update probability of the data in the blocks.The experimental results show that the proposed UIGC algorithm exhibited better garbage collection efficiency and wear balance performance than existing garbage collection algorithms, such as CAT and FaGC, and that it can effectively prolong the service life of flash memory.

Key words: NAND flash memory garbage, wear leveling, update interval, data heat degree, update stability, data partition, file system

中图分类号:

TP316.2

余进, 严华. 基于数据更新间隔的NAND闪存垃圾回收算法[J]. 计算机工程, 2022, 48(3): 54-59.

YU Jin, YAN Hua. Garbage Collection Algorithm for NAND Flash Memory Based on Data Update Interval[J]. Computer Engineering, 2022, 48(3): 54-59.

https://www.ecice06.com/CN/Y2022/V48/I3/54

图/表 7

20220330200536

20220330200540

20220330200543

20220330200546

20220330200550

20220330200553

20220330200557

参考文献

[1] 杜晨杰, 姚英彪.一种面向闪存固态盘的页级缓冲区管理算法[J].计算机工程, 2018, 44(7):54-59. DU C J, YAO Y B.A page-level buffer management algorithm oriented flash solid state disk[J].Computer Engineering, 2018, 44(7):54-59.(in Chinese)
[2] ZHU G, HAN J, SON Y.A preliminary study:towards parallel garbage collection for NAND flash-based SSDs[J].IEEE Access, 2020, 8:223574-223587.
[3] SEO S B, KIM W, KWON S J.Efficient page collection scheme for QLC NAND flash memory using cache[J].International Journal of Advanced Computer Science and Applications, 2018, 9(11):458-461.
[4] HUANG M, WANG Y, LIU Z Q, et al.A garbage collection aware stripping method for solid-state drives[C]//Proceedings of the 20th Asia and South Pacific Design Automation Conference.Washington D.C., USA:IEEE Press, 2015:11-23.
[5] 张靖君, 王玲.混合映射方式下NAND闪存垃圾回收算法[J].小型微型计算机系统, 2019, 40(10):2139-2142. ZHANG J J, WANG L.NAND flash garbage collection algorithm in hybrid mapping mode[J].Journal of Chinese Computer Systems, 2019, 40(10):2139-2142.(in Chinese)
[6] HE J, JIA G, HAN G, et al.Locality-aware replacement algorithm in flash memory to optimize cloud computing for smart factory of industry 4.0[J].IEEE Access, 2017, 5:16252-16262.
[7] LIU Z, REN S.Garbage collection technique using erasure interval for NAND flash memory-based storage systems[J].Advances in Computational Sciences and Technology, 2018, 11(5):417-431.
[8] KIM S H, CHOI J H, KWAK J W.PBGC:proxy block-based garbage collection for index structures in NAND flash memory[J].IEICE Transactions on Information & Systems, 2016, 99(7):1928-1932.
[9] KIM M, CHUN M, HONG D, et al.RealWear:improving performance and lifetime of SSDs using a NAND aging marker[J].ACM SIGMETRICS Performance Evaluation Review, 2021, 48(3):120-121.
[10] KANKANI N, TRUONG L T.Variable bit encoding per NAND flash cell to extend life of flash-based storage devices and preserve over-provisioning[EB/OL].[2021-01-05].https://www.freepatentsonline.com/y2016/0342344.html.
[11] QIN M, MATEESCU R, WANG Q, et al.Garbage collection algorithms for meta data updates in NAND flash[C]//Proceedings of 2019 IEEE International Conference on Communications.Washington D.C., USA:IEEE Press, 2019:125-145.
[12] LUO Q, FANG X, SUN Y, et al.Self-learning hot data prediction:where echo state network meets NAND flash memories[J].IEEE Transactions on Circuits and Systems I:Regular Papers, 2020, 67(3):939-950.
[13] WU M, ZWAENEPOEL W.eNVy:a non-volatile, main memory storage system[J].ACM SIGOPS Operating Systems Review, 1994, 28(5):86-97.
[14] ATSUO K, SHINGO N, HIROSHI M.A flash-memory based file system[M].San Diego, USA:USENIX Association, 1995.
[15] CHIANG M L, CHANG R C.Cleaning policies in mobile computers using flash memory[J].Journal of Systems & Software, 1999, 48(3):213-231.
[16] YAN H, YAO Q.An efficient file-aware garbage collection algorithm for NAND flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics, 2015, 60(4):623-627.
[17] YAN H, HUANG Y, ZHOU X, et al.An efficient and non-time-sensitive file-aware garbage collection algorithm for NAND flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics, 2019, 64(1):73-79.
[18] 杨智, 严华.Yaffs2文件系统中NAND Flash块选择策略的改进[J].四川大学学报(自然科学版), 2016, 53(6):1278-1282. YANG Z, YAN H.Improvement on block selection policies of NAND Flash in Yaffs2 file system[J].Journal of Sichuan University(Natural Science Edition), 2016, 53(6):1278-1282.(in Chinese)
[19] 于万钧, 张海军, 刘全.一种基于NAND闪存高效的页面替换算法[J].现代电子技术, 2017, 40(16):53-56. YU W J, ZHANG H J, LIU Q.An efficient page replacement algorithm based on NAND flash memory[J].Modern Electronic Technology, 2017, 40(16):53-56.(in Chinese)
[20] HARBY A A, FAHMY S F, AMIN A F.More accurate estimation of working set size in virtual machines[J].IEEE Access, 2019, 7:94039-94047.
[21] 李恒恒, 胡泽明, 岳春生, 等.基于YAFFS2的静态磨损均衡算法设计[J].计算机应用研究, 2016, 33(4):1091-1095. LI H H, HU Z M, YUE C S, et al.Design of static wear-leveling algorithm based on YAFFS2[J].Application Research of Computers, 2016, 33(4):1091-1095.(in Chinese)
[22] LIN M, CHEN S.Efficient and intelligent garbage collection policy for NAND flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics, 2013, 59(3):538-543.
[23] AKSENOV S V, SAVAGEAU M A.Parameter estimation and random number generation from a Zipf-related Lerch distribution[J].Social Science Electronic Publishing, 2018(6):196-225.

选择文件类型/文献管理软件名称

选择包含的内容