一种代价感知的细粒度闪存缓冲区替换算法

刘翠梅,杨 璇,贾刚勇,韩光洁

1(常州机电职业技术学院 信息工程学院,江苏 常州 213164)2(河海大学 物联网工程学院,江苏 常州 213022)3(杭州电子科技大学 计算机学院, 杭州 310018)

1 引 言

基于闪存的固态硬盘是近年来出现的一种新型存储设备.这种存储设备不仅有优秀的带宽,并且还有良好的随机或者顺序I/O性能.性能远远优于传统的机械硬盘,更重要的是闪存具有更低的耗电量,而且因为没有可移动部件,因此闪存具有比机械硬盘更好的可靠性[1].

现在,闪存固态硬盘已经慢慢成为大型服务器,便携计算机、移动终端、手持设备等的各种设备上的存储部件.然而闪存的异地更新、先擦后写、擦写有次数限制,写操作时间远大于读操作时间等特性需要有效解决,以提高闪存的效率.针对闪存的特征,闪存的缓存替换算法能够解决其中的读写代价异构性和寿命有限性特征,从而可以有效的提高闪存的性能和寿命.所以闪存的缓存替换算法是目前研究的一个热点[2].

传统针对机械磁盘的缓存替换算法不能满足闪存的上述挑战.大多数算法只关注命中率的提高而忽视了替换过程闪存读写操作代价的异构性.目前针对闪存已经提出了多种缓存替换算法,如CF-LRU[4],LRU-WSR[5],AD-LRU[3]等,这些算法优先从闪存缓冲区中替换出干净页,从而可以减少写入闪存页的数量,降低替换代价.然而现有的这些算法往往优先替换干净页,导致脏页长时间保留在缓冲区中,从而引起干净页的抖动现象,即刚调入缓冲区就被替换的现象,严重降低了缓冲区的命中率,增加闪存的读写操作,降低闪存性能.而且冷脏页长期驻留缓冲区,浪费了宝贵的缓冲区资源,降低系统的性能.

为了解决现有闪存缓冲区替换算法存在的问题,本文提出了一个代价感知的细粒度缓冲区替换算法(FSO-LRU),这个算法不但考虑系统的命中率,同时关注如何有效的减少写和擦除操作.这个算法可以由下面的几点来介绍.

本文提出的代价感知的细粒度缓冲区替换算法不仅考虑到各页的访问频率和冷热特征,同时也考虑到了在页替换的时候读写代价的异构性特征,优先替换代价小的干净页.

同时,代价感知的细粒度缓冲区替换算法还考虑了各页的重用概率,重用概率越高,替换代价越大,重用概率越低,替换代价越小.从而优先替换重用概率低的页.

结合读写代价的异构性特征和重用概率,决定闪存缓冲区的替换.

本文采用闪存模拟平台来对提出的代价感知的细粒度缓冲区替换算法进行评价.在不同负载下对比多种替换算法,实验结果表明代价感知的细粒度缓冲区替换算法具有很好的命中率和较少的擦除/写操作

2 相关工作

2.1 闪存存储系统

基于闪存的固态盘,是由一种基于闪存芯片的新型半导体存储设备.闪存主要分为NOR型闪存、NAND型闪存,这些闪存都是基于浮栅场效应管作为存储单位,改变了传统存储系统的特性.目前使用较多的是NAND型闪存,本文也是针对NAND型闪存进行研究.

相对于传统硬盘,基于闪存的固态盘有如下特性：

没有机械延迟,比如没有寻道时间.

运用一种写时擦除机制来进行数据的更新,传统硬盘如果运用这种机制就代价太大.

读、写、擦除操作有着不一样的延迟.读操作最快,擦除操作最慢.

闪存具有擦除限制,SLC、MLC、TLC有着不同的擦除限制SLC大约可擦出100000次、MLC大约可擦除5000次、TLC大约可擦除1000次.当闪存芯片达到擦除阈值的时候,存储数据将变得不可靠.其中,SLC(Single Level Cell)表示一个存储单元存储一个信息,MLC(Multi Level Cell)表示一个单元可以存储两个信息.

闪存芯片的操作过程比较独特,每个闪存单元相对独立,众多的闪存芯片综合形成闪存存储系统.为了统一管理所有的闪存芯片,固态盘中给出了一个统一的软件层次,叫做文件转换层(File Translate Layer).文件转换层的主要功能是实现将上层文件系统所有的请求通过地址映射、操作分类等,转换为各个单元的闪存操作[7].

为了提高闪存存储单元的性能,固态盘中有一个缓冲区用于缓存闪存数据,从而减少对闪存单元的读写操作,有利于闪存性能的提升和寿命的延长.图1给出了闪存的整体架构[8].

图1 闪存的整体架构Fig. 1 Framework of flash

2.2 传统的缓存替换策略

缓存管理可以说是固态硬盘里面的一个关键部分,缓冲区能够加速闪存数据的访问,同时减少对闪存的读写操作,也就有效降低闪存的擦除过程,从而对固态盘的性能和寿命起到很好的提升.通常,我们假定有两级存储系统,主存和外部(第二级)存储系统.它们在逻辑上都被组织成一组逻辑页的形式,逻辑页是两级存储之间的唯一交换单元.当上层模块请求页面时,如果数据页没有在缓存中,缓存管理必须从二级存储设备读取数据.如果没有可用的页框,必须选择一些页面淘汰.缓存替换策略的好坏决定缓存管理的性能[9].

传统替换算法主要关注于命中率,因为在机械磁盘中,读操作和写操作的代价是一致的,高命中率就等于低代价,也意味着高性能.许多算法因此被提出.他们大多基于最近最久未使用(LRU)算法,或者最近最少使用算法[10].

所有传统的算法都没有考虑闪存的读写不对称性[11].然而,减少闪存的读写次数,不仅有助于减少运行时间,还可以延长固态盘的使用寿命.因此近些年来缓存替换算法大多研究如何减少写操作次数.

2.3 现有的闪存缓冲区替换算法

CFLRU是第一个基于闪存的缓存算法.它把LRU分为工作区和和Clean-First区域,该区域有个窗口大小w,替换总是发生在Clean-First区域中的最近最少使用干净页面中,因此减少了写操作的数量.如果没有干净页面在Clean-First区域中,那么CFLRU会退化成LRU.所以CFLRU有下列问题：

窗口大小必须根据不同的负载进行调整,不能适应不同的负载,因此根据这个原因,提出了一种动态调整窗口大小的根据周期性的读写比例来动态的调整窗口大小.但是这在真实场景中是不够的,这是因为引用的局部性和缓冲区大小对窗口w大小有着实质的影响；

CFLRU优先替换干净页,从而造成冷脏页长时间留在缓存中,导致系统命中率的下降；

需要在Clean-First区域中找寻干净页来进行替换,带来了额外的开销；

CFLRU同LRU一样,没有考虑访问频率的影响.

LRU-WSR算法首先将数据进行冷热划分,将仅仅只有一次访问的数据划分为冷数据,将多次访问的数据划分为热数据.因为脏数据替换时需要写回操作,代价较高,同时热数据重用的概率较大,因此LRU-WSR优先替换冷数据,尽量长时间的保留热脏数据,减少对闪存的写操作,从而降低了闪存的开销,提高性能.

AD-LRU算法首先将缓冲区划分为冷区和热区,冷区由仅仅一次访问的缓存页组成,热区由访问过至少2次以上的缓存页组成.然而,冷区和热区的大小是根据数据访问的情况动态的变化的.AD-LRU算法给出了一个冷、热区的阈值,当冷区的存储空间大于等于阈值,替换发生在冷区,否则,热区中的数据页被替换.

读写代价的非一致性已经融合到现有的缓冲区替换算法中,但是没有细粒度的考虑闪存缓冲区中各页的重用性,重用性越高,被重复读写的概率越高,替换代价就越大；重用性越低,被重复读写的概率越低,替换代价就越小.只有在替换时结合了缓冲区各页的读写异构性和重用性才能保证替换代价最低,才能提高系统的性能.

为了提高系统的性能,降低写闪存的次数和延长闪存寿命,本文提出了代价感知的细粒度闪存缓冲区替换算法,不但考虑闪存读写操作的异构性,而且结合闪存缓冲区中各页的重用性.

3 代价感知的细粒度闪存缓冲区替换算法(FSO-LRU)

基于闪存的缓存替换算法,我们不仅需要考虑到命中率,还要考虑到写闪存代价.替换干净页可以减少写操作的数量,从而减少了负载运行的时间.但是传统的算法不总是替换干净页.CF-LRU和LRU-WSR总是优先从缓存中选择干净页进行替换.AD-LRU将缓冲区分成冷、热两个区,但是没有考虑替换的代价问题,所以会导致干净页可能刚进入缓存区就被替换；冷脏页长时间在缓冲区中,浪费资源.基于这些原因,命中率可能会受很大影响.

因此,本文考虑在传统的最近最久未使用算法(LRU)上结合替换代价、访问频率、以及数据的局部性用以降低写入代价,同时提高缓存命中率.

代价感知的细粒度闪存缓冲区替换算法的思想如下：

用4个LRU队列来存储数据访问的频率和最近访问,分别分为热-干净队列、热-脏队列、冷-干净队列、冷脏队列.冷LRU队列存储只访问一次的页；热队列用于存储访问超过一次的页.所以,热-干净队列存储访问次数超过一次且没有被修改过的页；热-脏队列用于存储访问次数超过一次但被修改过的页；冷-干净队列存储访问次数为一次且没有被修改过的页；冷-脏队列用于存储访问次数为一次但被修改过的页.

4个队列的大小是动态调整的,当一个冷页被再次访问时,这时这个页就根据其脏或者干净属性被替换到热队列中去.此时,对应的冷队列中的长度就减少,相应热队列的长度就增加.

在进行淘汰的时候,我们在四个队列中选择一个页进行替换.替换的依据是根据不同的代价与访问频度来进行替换,替换的页依据公式(1)进行选择.

prob=recency*cost(cc,cd,hc,hd),select_P

=min(cc,cd,hc,hd)

(1)

如公式(1)所示,recency表示该页面最近访问的频率,cost(cc,cd,hc,hd)表示选择一个页面的代价,其中cc表示冷干净页,cd表示冷脏页,hc表示热干净页,hd表示热脏页,而替换的代价通常情况是costcc

如图2所示,4个LRU链表构成了整个代价感知的细粒度闪存缓冲区替换算法的核心.当在一个冷干净链表中命中一个页面时候,将该页依据读写不同替换到相应的页面中去.这里假设将页面替换到热干净链表中去.那么这样热干净队列长度增加,冷干净页面长度减少,从而实现了链表长度的动态增减.

图2 四个LRU列表Fig.2 List of four LRUs

页面替换总是发生在LRU链表尾部,当每次找寻得时候,我们会从四个LRU链表里面找一个该种属性最近没有被访问的元素来进行选择.根据其替换的代价和最近访问的时间来计算出替换该链表LRU页的代价.从中选择最小替换代价的页把其进行替换.如果在进行选择替换的时候,里面其中有一个或者两个队列为空,那么我们就从非空的队列里进行选择替换.算法1给出了本文提出的FSO-LRU算法的伪代码.

Algorithm1：FSO-LRU

data：Lcc,Lcd,Lhc,Lhd,Lmeans list

ifpis inL(cc,cd,hc,hd)then//pis in the buffer

AdjustList(L(cc,cd,hc,hd))

else//pis not in the buffer

ifthere is free space in the bufferthen

adjustLccorLcdand putpinto its MRU

else

victim=SelectVictim(L(cc,cd,hc,hd))

ifvictim is dirtythen

WriteDirty(P)

图2说明了一个页面中如果命中,应该如何进行调整.算法2给出了页面在不同列表中的调整过程.如果在冷链表中命中了,需要调整链表的位置,把这个页面移动到热链表中.比如,一个页原本是冷干净页,现在对这个页面进行了读操作,那么原来的冷干净页就被移动到热干净链表中去；如果对该页进行了一个写操作,那么原来的页面就被移动到热脏页列表中.

Algorithm2：AdjustList

data：Lcc,Lcd,Lhc,Lhd,Lmeans list

ifpis inLccthen

movep// movepmeans adjust lru lists by its operation and feature

elseifpis inLcdthen

movep

elseifpis inLhcthen

movep

elseifp is inLhdthen

movep

算法3选择驱逐页的时候依据公式(1)从每个链表里面的LRU中选出最代价最小的页进行替换,保留替换代价大的页,从而减少擦除/写操作的目的.

Algorithm3：SelectVictim

data：Lcc,Lcd,Lhc,Lhc,Lmeans list

prob(cc,cd,hc,hd)=recency*cost(cc,cd,hc,hd)

select_P=min(cc,cd,hc,hd)

victim=select_P

FSO-LRU 与CF-LRU、LRU-WSR、AD-LRU都具有减少写操作总体目标.FSO是一个新的设计,它与其他几种算法的不同具体如下所示：

1)FSO-LRU 考虑了访问的频度,以及替换页面所需要的代价.这是CF-LRU和LRU-WSR没有考虑过的.AD-LRU虽然考虑了页面所命中的频度,但是没有考虑到替换替换页的代价与频度的一个关系.

2)CF-LRU会优先替换工作区域的干净页.如果没有找到页面的话会替换工作区的脏页,此时CF-LRU就可能退化为LRU.

3)LRU-WSR虽然避免了冷脏页长时间驻留内存,但是没有考虑干净页的冷热属性.而且找寻替换页的代价相对较大.

4)AD-LRU将缓冲区分为热区和冷区.其中冷热区域是动态调整的.其中冷区域容量有一个下界min_lc,因此,当冷区域大小小于min_lc时,替换总是发生在热区域.AD-LRU总是替换干净页,无法避免干净页刚进入缓冲区就被替换的情况,冷脏页长期留在内存,浪费了宝贵的资源,降低了命中率.

4 实验与性能评价

该部分先介绍实验的设计,然后通过实验得到了代价感知的细粒度闪存缓冲区替换算法获得最佳性能的参数配置,最后通过对比现有的几种典型算法来评价本文提出的FSO-LRU算法的性能.

4.1 实验设计

本文基于Flash-DBSim[6]模拟器实现了FSO-LRU算法,同时为了实现对比,在该模拟器中也实现LRU、LRU-WSR、AD-LRU几个现有的典型缓冲区替换算法.Flash-DBSim模拟器具有许多优点,包括平台的开放性,能支持各种不同的算法等,是目前使用较多的模拟器平台.

表1给出了本文采用的闪存配置参数.文中模拟一个容量大小为128MB的NAND固态盘,页面的大小为2KB,每个数据块中有64个页,读操作的代价,写操作的代价已经擦除操作的代价在表中给出,同时参考了现在主流NAND固态盘的参数.

为了尽可能模拟真实固态盘的数据页的访问模拟,我们产生了4种符合Zipf分布的测试数据.表2给出了4组数据集的特征,其中读/写比例的参数给出了数据集中读操作所占的比例以及写操作所占的比例,如Trace1的读/写比例90%/10%表示Trace1中90%的操作是读操作,10%的操作是写操作.局部性的参数给出了数据集的局部性特征,比如Trace1中局部性是60%/40%,其所表示的含义是指60%的操作集中在40%的数据页中.为了评价算法的性能,本文主要针对以下几个参数进行对比：

表1 NAND固态盘的配置参数Table 1 Characteristic parameters of NAND flash

1)命中率：对比闪存系统总体的命中率；

2)物理读操作(读闪存)的次数：读操作次数部分反映了缓存替换算法有没有考虑读操作；

3)物理写操作(写闪存)的次数：写操作次数是缓存替换算法优劣的一个重要指标；

4)运行时间：缓存替换算法总体性能的综合体现.

表2 测试数据集的统计信息Table 2 Statistical information about test data

在对CF-LRU进行性能比较的时候参数W设置为0.5,在对AD-LRU的性能进行比较的时候.

4.2 FSO-LRU最佳参数设置

结合页替换的真实代价以及实验结果,本文将代价感知的细粒度闪存缓冲区替换算法的参数设置如下：cold_clean_cost=0.1,cold_dirty_cost=1.5,这个是冷链表的代价.hot_clean_cost=0.7,hot_dirty_cost=3.5,min_lc=0.其中min_lc是参考AD-LRU进行设置.实验表明min_lc=0时实验效果最好.

4.3 命中率

图3给出了不同缓冲区替换算法的命中率.基于实验数据可以发现：基于数据访问频度和数据冷热性的算法比没有考虑数据访问频度的算法在命中率上有更好的表现.我们从图中可以看出代价感知的细粒度闪存缓冲区替换算法在数据局部性较差(Trace 1)的情况下,比其他同类算法有着更高的命中率.缓冲区大小为5MB时,在数据集为Trace 1的试验中,代价感知的细粒度闪存缓冲区替换算法比其他相似的算法有着更高的命中率.AD-LRU缓冲区替换算法的时间的命中率大约在34%,LRU算法的命中率大约在27%,而我们提出的代价感知的细粒度闪存缓冲区替换算法缓冲区替换算法的命中率大约在35%左右,比LRU算法高了接近7.5%.如果数据的局部性更好一些,在数据Trance4中,我们可以看到代价感知的细粒度闪存缓冲区替换算法在缓存大小为4M的时候,命中率高达77.9%,而普通的LRU,命中率只有57.8%.因此我们可以看出代价感知的细粒度闪存缓冲区替换算法在局部性较好的负载中,具有巨大优势.

图3 在不同数据集上的命中率比较Fig. 3 Comparisons of hit rates on different data sets

4.4 闪存读次数分析

图4给出了不同的缓冲区替换算法在物理闪存读操作上的不同表现结果.实验数据同样表明：基于数据访问频度和数据冷热性的算法比没有考虑数据访问频度以及冷热属性的缓冲区替换算法在物理页读操作的参数上表现得更好.

图4 在不同数据集上读闪存次数Fig. 4 Comparisons of flash read times on different data sets

在缓存大小为4MB的情况下,代价感知的细粒度闪存缓冲区替换算法在Trace 1数据集中的读闪存次数约为2150k次,而LRU的读闪存次数大约为2300k次,AD-LRU读闪存次数大约为2220k次.

4.5 物理写操作次数

图5给出不同缓存替换算法在写操作次数这个参数上的性能表现.实验数据结果表明结合数据访存频度和数据冷热特征的缓存替换算法比其他算法表现得更好,具有更少的物理写操作次数.

图5 在不同数据集上写闪存次数Fig. 5 Comparisons of flash write times on different data sets

在缓存大小为5MB的情况下,代价感知的细粒度闪存缓冲区替换算法在Trace 1数据集中的写闪存次数约为125次,而LRU的读闪存次数大约为362次,AD-LRU读闪存次数大约为276次.

5 结束语

随着闪存越来越普及,闪存的使用寿命和I/O性能以通过改善缓存替换算法来进行改善.NAND闪存的读写速度和传统的DRAM读写时间还是有差距的,所以采用缓存是有必要的.我们需要减少写闪存的次数,根据闪存的读写不对称性,因此我们提出了四链表形式的代价感知的细粒度闪存缓冲区替换算法,动态的调整四个队列的长度,以及访问时间远近的信息,以及替换代价,我们动态的选择队列中的替换页.保证了命中率以及写操作数的减少.

然而本文的一个研究假设是闪存固态盘的读写代价比是固定的.然而,现实中读写代价比可以是动态调整的.所以,之后研究工作会重点考虑读写代价比非固定的设备上分析代价感知的细粒度闪存缓冲区替换算法的性能表现,从而为不同读写代价别的设备确定最优的参数组合.