2023, Vol. 55
随着大数据技术的飞速发展，传统的磁盘已经无法满足当前海量存储的性能需求[1-2]。与传统的磁盘相比，固态硬盘(solid state disk，SSD)没有机械装置，不易损坏[3]，在进行I/O操作的时候不存在寻址时间和旋转延迟，具有数据访问速度快、重量轻、体积小、抗震性能好、功耗低、噪声小等优点[4]。
NAND闪存是目前最常见且最具前途的存储介质之一，读、写操作速度快，适用于存储连续的数据。但是它与传统的磁存储介质不同，有着读写不对称、先擦除后写、闪存单元擦除次数有限的特点。这些特性导致NAND闪存在经过长时间的读写操作后，存储性能逐渐降低，同时也会缩短其使用寿命[5-7]。通过缓冲区管理技术来提高闪存存储性能、延长其使用寿命已经成为固态硬盘的一个研究热点[8]。
最近最少使用(least recently used, LRU)算法是经典的缓冲区页面置换算法，常被用于提高磁盘存储系统的性能，其工作原理是，在过去的访问请求中最频繁使用的页面也很可能在接下来的访问请求中频繁使用。因此，LRU记录每个页面的最近引用时间，并驱逐最近最少引用的页面，以提高页面的命中率。由于NAND闪存不同于磁盘的特性，传统的针对磁盘而设计的缓存替换算法已经不能应用于基于NAND闪存的固态硬盘上[9-11]。针对基于NAND闪存的固态硬盘，缓冲区管理策略应在保持良好命中率的同时，最小化写入操作和擦除操作次数以减少整体延迟。在LRU算法的基础上，结合闪存的特性，国内外提出了很多针对基于闪存的缓冲区管理算法的研究。这些算法大多以提高缓冲区命中率为目标，但是当替换缓冲区内的脏页面时，会产生脏页面的写回操作，每个页面包含脏闪存页的比例和被访问频率不同，导致了不同页面的写回操作代价各不相同，现有的替换算法没有考虑替换时的代价开销，从而没能充分发挥固态硬盘的性能。
1 相关工作 1.1 闪存存储系统与硬盘相比，闪存有以下特性。
1) 读写不对称。闪存有三种主要操作：读操作、写操作和擦除操作。读操作和写操作以页为单位进行，而擦除以块为单位进行。三种操作的速度不同，其中读速度最快，写操作其次，擦除操作最慢[16]。
2) 写前擦除。闪存不可以像磁盘一样直接在原数据上进行修改，如果要更新数据，需要将新数据写入其他空白页；已经写入数据的闪存页，必须先进行擦除使之变成空白页，才能再次写入数据。
3) 擦除次数有限。根据闪存单元的不同，闪存的擦除次数也不同，SLC的擦除次数约为100 000次，MLC的擦除次数约为5 000次，TLC的擦除次数约为1 000次。一旦超过最大擦除次数，闪存就会变得不再可靠，甚至无法使用。
图 1展示了基于闪存的SSD架构，它由主机系统、主机接口、DRAM缓冲区、闪存转换层(flash translation layer，FTL)和闪存阵列组成。主机系统包括针对不同场景的应用程序和用于文件管理的文件系统[17]。闪存转换层位于文件系统与闪存之间，为文件系统提供了虚拟的磁盘，可以使得固态硬盘表现出类似磁盘的行为，从而使得面向磁盘开发的应用程序不需要任何修改，就可以直接运行在以固态硬盘作为存储介质的存储系统上。
|
图 1 基于闪存的SSD架构图 Fig. 1 Flash-based SSD architecture |
在闪存存储系统中，通常会选择动态随机存取存储器(DRAM)作为闪存中的缓冲区。与闪存相比，DRAM能够直接在原数据上进行数据更新，因此在缓冲区中进行大量的数据读取，可以减少闪存的读、写操作。但是缓冲区的容量是有限的，为了能够最大限度地利用缓冲区空间，应该将频繁访问的数据加载到缓冲区中，并在缓冲区空间已满时把访问频率低的数据驱逐出去。
1.2 针对闪存设计的缓冲区管理算法Park等提出了针对NAND闪存的页面替换算法：CFLRU[12]。该算法优先选择缓冲区内最近最少使用的干净页面作为受害者页面，如果没有干净页面，则根据LRU策略选择脏页面作为受害者页面。首先驱逐干净页面能够降低内存的访问成本，但是无论访问频率如何，都优先驱逐干净页面，这将导致许久未访问的脏页面占据缓冲区空间，使缓冲区的命中率降低。
LRU-WSR[13]算法通过基于二次机会的“冷检测”对脏页面进行重新排序来增强LRU策略，在驱逐脏页面时优先驱逐冷脏页面，将访问频率高的脏页面尽可能保留在缓冲区中。但是若某段时间内只对干净数据页进行频繁访问，会导致热脏数据页很快置换出缓冲区，造成闪存的访问开销明显增加。算法同样没有考虑干净数据页面的访问频率，可能会导致热干净数据页先于冷干净数据页被置换出，降低缓冲区的命中率。
AD-LRU[14]算法使用冷、热LRU链表通过自适应机制对缓冲区页面进行管理。该算法设置了最小冷区域下限min_lc。如果冷区域容量大于或等于min_lc，在冷区域进行页面替换操作，否则，AD-LRU算法将从热区域选择受害者页面进行驱逐。但是AD-LRU算法总是优先替换干净的页面，同样会使缓冲区长期保留冷脏页面，导致空间浪费。
PR-LRU[15]算法通过使用参考概率选择候选页面作为受害页面来增强闪存的性能。在处理热页面和冷页面的过程中，PR-LRU算法把页面信息转换为该数据页被再次访问的概率，并选择概率最低的数据页作为受害页。但是算法没有在驱逐LRU列表中滞后置换新的冷页面，导致冷LRU列表长度不够时，刚进缓冲区的冷干净页面可能被很快置换出，从而增加了闪存的访问开销。
2 基于页面替换代价的缓冲区管理算法(PRC-LRU)基于页面替换代价的缓冲区算法，在LRU算法的基础上，既考虑稳定缓冲区的命中率，还要减少脏闪存页写回闪存的次数，从整体上把握页面写回闪存的代价，选择替换代价小的页面作为受害者页面驱逐到闪存中，从而提高闪存存储系统的整体性能。
基于页面替换代价的缓冲区管理算法的基本思想如下。
如图 2所示，PRC-LRU算法将缓冲区划分为工作区域和受害者区域两个部分，其中工作区域维护两个页面链表：干净页面链表(clean list, CL)和混合页面链表(mix list, ML)。干净页面链表存放未经过修改的页面，混合页面链表存放至少被修改过一次的页面，两个链表的长度可动态调整。受害者区域包含一个受害者页面链表(victim list, VL)，存放从工作区域迁移出来的页面，三个链表按照LRU原则进行页面排序, MRU(most recently used)端存放距离上次被访问时间最短的页面，LRU(least recently used)端存放距离最长的页面。另外设置一个计数器，用来记录页面的访问次数。
|
图 2 缓冲区结构图 Fig. 2 Buffer structure diagram |
当有新请求到来时，首先判断所请求的目标数据页是否在缓冲区内。如果目标数据页在缓冲区内，并且在工作区域中，将目标数据页返回上层应用，同时将数据页移动至所在链表的MRU端。
如果目标数据页在受害者区域中，同样根据数据页的页面状态和请求类型，将页面迁移至工作区域内相应链表的MRU端。如果工作区域没有空闲空间，通过公式(1)和公式(2)分别计算位于干净页面链表和混合页面链表LRU端的页面迁移代价，选择迁移代价小的页面迁移至受害者区域中页面链表的MRU端，再将请求的目标页插入工作区域内相应链表的MRU端。
| $ M_c=\frac{k P C_r}{T_c} \text {, } $ | (1) |
| $ M_m=\frac{P_d \times\left(C_w+C_e\right)}{T_d}, $ | (2) |
式中：Pd表示脏页面中含有的脏闪存页面的数目；P为页面中所有闪存页的数目；Cr为读操作的代价；Cw为写操作的代价；Ce为擦除操作的代价；Tc和Td分别表示干净页面链表和混合页面链表LRU端的页面距离上一次被访问的时间间隔。
如果目标数据页没有在缓冲区中，将数据页从闪存读入缓冲区内，根据数据页的页面状态和请求类型，将页面迁移至工作区域内相应链表的MRU端。如果缓冲区没有空闲空间，则扫描受害者页面链表，根据公式(3)和公式(4)计算页面的替换代价，选择替换代价最小的页面作为受害者页面驱逐入闪存中，再将目标数据页插入缓冲区内相应链表的MRU端。
| $ A U I=\left(\sum\limits_{i=1}^n\left(t_i^p-t_{i-1}^p\right)+t_1^p\right) / n, $ | (3) |
| $ R C(p)=\frac{P_d}{P} \times \frac{1}{A U I}, $ | (4) |
式中：AUI为页面被访问的平均时间间隔；RC为页面的替换代价；tip表示页面p第i次被访问的时间。
通常情况下，干净页面的迁移代价小于脏页面的迁移代价。当脏页面的迁移代价小于干净页面的迁移代价时，说明距离脏页面上一次被访问的时间已经足够长，此时应该将许久未被访问的脏页面迁移到受害者区域内，等待再一次被访问或者逐出缓冲区。受害者页面链表中替换代价最小的页面，说明其平均访问间隔比较长，短时间内再一次被访问的概率低，另外所含脏闪存页的比例也不高，驱逐入闪存中产生的能耗较低。算法1为PRC-LRU的伪代码。
算法1 PRC-LRU
输入：当前请求页(p)，干净页面链表(CL)，混合页面链表(ML)，受害者页面链表(VL)，工作区域(WR)，受害者区域(VR)。
输出：请求页。
1. IF p is in buffer
2. IF p is in WR
3. AdjustList(CL, ML)
4. ELSE IF p is in VR
5. Insert p into WR
6. AdjustList(CL, ML)
7. IF WR is full
8. PageMigration()
9. pagef=p
10. Insert p into WR
11. AdjustList(CL, ML)
12. END IF
13. END IF
14. END IF
15. IF p is not in buffer
16. Insert p into WR
17. AdjustList(CL, ML)
18. IF buffer is full
19. PageEviction()
20. pagef=p
21. Insert p into WR
22. AdjustList(CL, ML)
23. END IF
24. END IF
通过计算页面的替换代价，选择替换代价最小的页面作为受害者页面。由于缓冲区内的页面大小一般是4 kB~16 kB，而闪存页一般为512 B~2 kB，因此，我们可以将从缓冲区驱逐出来的页面划分为多个闪存页写入闪存中。
如图 3所示，假设内存页的大小为4 kB，闪存页的大小为512 B，一个内存页则可以划分为8个闪存页。数据未被修改的闪存页为干净闪存页，数据被修改过的闪存页为脏闪存页。
|
图 3 受害者页面划分示意图 Fig. 3 Victim page division diagram |
根据公式(5)计算闪存页被访问的频率，确定一个阈值，访问频率高于阈值的脏闪存页称为热脏闪存页，访问频率低于阈值的脏闪存页称为冷脏闪存页。
| $ V F(d)=\frac{count_d}{current\_time - visit\_time_d}, $ | (5) |
式中：countd为闪存页的访问次数；current_time为系统当前时间；visit_timed为闪存页d进入缓冲区的时间。将热脏闪存页和冷脏闪存页以簇为单位分别存放并写入闪存中，干净闪存页直接丢弃，不再写回闪存。这样不仅减少了干净闪存页写入闪存的冗余操作，还将多个随机、小的写入操作转换为一个有顺序、大的写入操作，降低了延迟，减少了闪存的写入操作。
3 性能评价本次实验采用Flash-DBsim[18]平台模拟一个128 MB的基于NAND闪存的固态硬盘，设置每个数据页的大小是2 kB，每个物理块包含64个数据页，擦除次数为10万次，读速度为25 μs/页，写速度为200 μs/页，擦除速度为1.5 ms/block。根据文献[19]生成四种符合Zipf分布的测试用例，访问请求次数为300万次，如表 1所示，其中局部性x/y指x%的操作集中在y%的数据页上[20-21]。例如Trace1的局部性为60/40，表示60%的操作集中在40%的数据页上。本文将从命中率、写操作次数、运行时间三个方面来比较和分析CFLRU、LRU-WSR、AD-LRU、PR-LRU、PRC-LRU这五种基于闪存的缓冲区管理算法的性能。
|
表 1 测试数据集的信息 Tab. 1 Information about the test dataset |
命中率是评判缓存性能最常用也是最重要的标准之一。图 4给出了在四种不同测试数据集和不同缓冲区容量的条件下，PRC-LRU算法和已有的四种缓冲区管理算法的命中率情况。不同负载下的实验结果表明，这五种算法的命中率都随着缓冲区容量的增加而提升，到达一定程度时命中率将趋于饱和。
|
图 4 不同缓冲区大小下的缓冲区命中率 Fig. 4 Buffer hit ratio of various buffer cache sizes |
Trace 1~4的实验结果表明，本文提出的PRC-LRU算法在大多数情况下都保持较高的命中率，与CFLRU、LRU-WSR、AD-LRU、PR-LRU相比，命中率分别提升了26.4%、15.4%、9.2%和9%。这是因为在选择逐出缓冲区的受害者页面时，不再总是优先驱逐干净页面，而是通过先计算页面的迁移代价，再经过二次选择，充分考虑页面的访问频率，最终将访问频率高的页面留在缓冲区内，避免了刚进入缓冲区的干净页面被换掉，并且将许久未访问的脏页面逐出缓冲区，释放了缓冲区空间，提高了缓冲区的命中率。
3.2 写操作次数由于闪存读写速度相差较大，并且有写前擦除和异地更新的特性，因此减少闪存的写操作数量对提高闪存存储系统的性能尤为重要。图 5描述了五种算法在四种测试数据集下随着缓冲区容量变化的闪存写操作次数的对比情况。从图 5中可以看到，对于所有的工作负载，随着缓冲区容量的增大，不同算法的写操作次数均呈现降低的趋势，这是由于当缓冲区容量增大时，命中率会变高，保留在缓冲区中的页面也会相应增加。
|
图 5 不同缓冲区大小下的闪存写操作次数 Fig. 5 The flash write count of various buffer cache sizes |
Trace 1~4的实验结果表明，本文提出的PRC-LRU相对于CFLRU、LRU-WSR、AD-LRU、PR-LRU算法，在减少写操作的次数方面有着较为明显的优势，且操作次数分别为CFLRU、LRU-WSR、AD-LRU、PR-LRU的43.5%、30.9%、63.9%、88.9%。原因如下：1) PRC-LRU算法具有较高的缓冲区命中率，读写操作大部分在缓冲区内进行，因此在闪存中直接进行的物理写操作次数相对较少；2) PRC-LRU算法在选择逐出缓冲区的受害者页面时，充分考虑了页面的读、写代价和擦除代价，给脏闪存页较多且更新较为频繁的页面赋予了较高的替换代价，使其能够留在缓冲区中；3) 将受害者页面驱逐进闪存中时，将页面分割为多个小的闪存页，干净闪存页直接丢弃，减少写回闪存的冗余操作，再将脏闪存页根据页面的热度值分别写入闪存中，将多个随机的、小的写操作转化为一个顺序的、大的写操作，因此降低了闪存的写操作数量。
3.3 运行时间图 6描述了五种算法在四种测试数据集下随着缓冲区容量变化的系统运行时间对比情况，系统的运行时间主要包括闪存的读、写延迟和擦除延迟。从图 6可以看出，所有算法在缓冲区容量较小时，运行时间的差异较小，随着缓冲区容量的增大，AD-LRU、PR-LRU、PRC-LRU算法的整体运行时间明显低于其他算法。由于闪存的读、写、擦除操作存在不同的延迟，总延迟受到写操作和擦除操作的影响较大，这导致了在Trace 4下五个算法的运行时间差异较小。
|
图 6 不同缓冲区大小下的运行时间 Fig. 6 The runtime of various buffer cache sizes |
Trace 1~4的实验结果表明，本文提出的PRC-LRU的运行时间分别是CFLRU、LRU-WSR、AD-LRU、PR-LRU的运行时间的41.5%、32.4%、59.6%、81.8%。虽然在计算页面的迁移代价和置换代价时，会带来时间上的开销，但是通过提高缓冲区命中率，减少直接作用到NAND闪存设备的读、写和擦除操作次数，以及使访问热度相近的闪存页一起写回闪存，减少垃圾回收的操作数量，使运行时间缩短，弥补了计算带来的时间开销。
4 结束语本文提出了一种基于页面替换代价的缓冲区管理算法(PRC-LRU)。该算法在选择受害者页面时，优先考虑页面的替换代价，在保持缓冲区命中率的同时减少了闪存的写操作次数，提高了闪存存储系统的性能。
| [1] |
LEE Y, PARK J, RYU J, et al. AxFTL: exploiting error tolerance for extending lifetime of NAND flash storage[J]. IEEE transactions on computer-aided design of integrated circuits and systems, 2020, 39(11): 3239-3249. DOI:10.1109/TCAD.2020.3013070 (  0) |
| [2] |
LIU C, WANG Q, CHU X, et al. ESetStore: an erasure-coded storage system with fast data recovery[J]. IEEE transactions on parallel and distributed systems, 2020, 31(99): 2001-2016. ( 0) |
| [3] |
MAIS N, HISHAM A. Secure-stor: a novel hybrid storage system architecture to enhance security and performance in edge computing[J]. IEEE access, 2021, 99: 92446-92459. ( 0) |
| [4] |
李雪筠, 叶靖, 黄正峰, 等. 基于PUF的硬件辅助软件认证方法[J]. 郑州大学学报(理学版), 2021, 53(1): 88-94. LI X Y, YE J, HUANG Z F, et al. PUF-based hardware-assisted software authentication method[J]. Journal of Zhengzhou university (natural science edition), 2021, 53(1): 88-94. ( 0) |
| [5] |
LI J, XU X F, CAI Z G, et al. Pattern-based prefetching with adaptive cache management inside of solid-state drives[J]. ACM transactions on storage, 2022, 18(1): 1-25. ( 0) |
| [6] |
HAN K, SHIN D. Remap-based Inter-partition copy for arrayed solid-state drives[J]. IEEE transactions on computers, 2022, 71(7): 1640-1654. DOI:10.1109/TC.2021.3099694 ( 0) |
| [7] |
WANG S, LU Z Y, CAO Q, et al. BCW: buffer-controlled writes to HDDs for SSD-HDD hybrid storage server[C]//The 18th USENIX Conference on File and Storage Technologies. Berkeley: USENIX Press, 2020: 253-266.
( 0) |
| [8] |
刘素, 刘惊雷. 一种从偏好数据库中学习CP-nets结构的并行算法[J]. 郑州大学学报(理学版), 2020, 52(2): 71-76. LIU S, LIU J L. A parallel algorithm for learning CP-nets structure from the preference database[J]. Journal of Zhengzhou university (natural science edition), 2020, 52(2): 71-76. ( 0) |
| [9] |
ZHOU Y, WU Q L, WU F. Remap-SSD: safely and efficiently exploiting SSD address remapping to eliminate duplicate writes[C]//The 19th USENIX Conference on File and Storage Technologies. Berkeley: USENIX Press, 2021: 187-202.
( 0) |
| [10] |
CAO C M, YE M, XUE J J, et al. Reprogramming 3D TLC flash memory based solid state drives[J]. ACM transactions on storage, 2022, 18(1): 1-33. ( 0) |
| [11] |
YUAN Y, ZHANG J, HAN G, et al. DPW-LRU: an efficient buffer management policy based on dynamic page weight for flash memory in cyber-physical systems[J]. IEEE access, 2019, 6(7): 58810-58821. ( 0) |
| [12] |
PARK S, JUNG D, KANG J, et al. CFLRU: a replacement algorithm for flash memory[C]//The International Conference on Compilers, Architecture and Synthesis for Embedded Systems. New York: ACM Press, 2006: 234-241.
( 0) |
| [13] |
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. DOI:10.1109/TCE.2008.4637609 ( 0) |
| [14] |
JIN P, YI O, LI Z, et al. AD-LRU: an efficient buffer replacement algorithm for flash-based databases[J]. Data & knowledge engineering, 2012, 72: 83-102. ( 0) |
| [15] |
YUAN Y, SHEN Y, LI W, et al. PR-LRU: a novel buffer replacement algorithm based on the probability of reference for flash memory[J]. IEEE access, 2017, 5: 12626-12634. ( 0) |
| [16] |
DU C, YAO Y, ZHOU J, et al. VBBMS: a novel buffer management strategy for NAND flash storage devices[J]. IEEE transactions on consumer electronics, 2019, 65(2): 134-141. ( 0) |
| [17] |
ARASH T, JUAN G, MOHAMMAD S, et al. MQSim: a framework for enabling realistic studies of modern multi-queue SSD devices[C]//The 16th USENIX Conference on File and Storage Technologies. Berkeley: USENIX Press, 2018: 49-66.
( 0) |
| [18] |
JIN P, SU X, LI Z, et al. A flexible simulation environment for flash-aware algorithms[C]//The 18th ACM Conference on Information and Knowledge Management. New York: ACM Press, 2009: 2093-2094.
( 0) |
| [19] |
JOHNSON T, SHASHA D. 2Q: A low overhead high performance buffer management replacement algorithm[C]//The 20th International Conference on Very Large Data Bases. New York: ACM Press, 1994: 439-450.
( 0) |
| [20] |
YADGAR G, GABEL M, SHEHBAZ J, et al. SSD-based workload characteristics and their performance implications[J]. ACM transactions on storage, 2021, 17(1): 1-26. ( 0) |
| [21] |
刘翠梅, 杨璇, 贾刚勇, 等. 一种代价感知的细粒度闪存缓冲区替换算法[J]. 小型微型计算机系统, 2019, 40(5): 972-977. LIU C M, YANG X, JIA G Y, et al. Cost-aware fine grain replacement algorithm for buffer management in flash memory[J]. Journal of Chinese computer systems, 2019, 40(5): 972-977. ( 0) |