(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 202010913153.0
(22)申请日 2020.09.03
(71)申请人 杭州电子科技大学
地址 310018 浙江省杭州市经济技术开发
区白杨街道2号大街1158号
(72)发明人 姚英彪 包杰丞 孔小冲 杜晨杰
徐欣
(74)专利代理机构 浙江千克知识产权代理有限
公司 33246
代理人 周希良
(51)Int.Cl.
G06F 12/02(2006.01)
G06F 3/06(2006.01)
G06F 16/22(2019.01)
(54)发明名称一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法(57)摘要本发明属于固态硬盘数据存储技术领域，具体涉及一种基于布隆过滤器和二级LRU(Least Recently Used)表的固态硬盘热数据识别方法，主要通过布隆过滤器和二级LRU表级联实现；布隆过滤器用来将输入的请求逻辑页号筛选掉冷数据，得到粗热数据；二级LRU表用来进行冷热判断从粗热数据中精确识别出热数据，从而将冷数据和热数据区分。本发明将两种识别算法的优势相结合，弥补对方的不足；此外，二级LRU表与固态硬盘闪存转换层的地址映射模块相结合，并无额外开销。总体上能够综合考虑数据访问的频率以及时间特性，针对不同类型的负载都能有效提 升热数据识别准确率。权利要求书1页 说明书5页 附图3页CN 112052190 A 2020.12.08
C N 112052190
A
1.一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，其特征在于，包括以下步骤：
S1、将写请求的逻辑页号LPN输入至布隆过滤器，将数据分为冷数据和粗热数据；
S2、检测布隆过滤器的衰减周期N是否达到；若是，则衰减布隆过滤器的计数器值；
S3、将步骤S1得到的粗热数据的LPN输入至二级LRU表进行处理，并判断粗热数据的LPN 是否在二级LRU表中命中；其中，所述二级LRU表包括热表和候选表；若没有在二级LRU表中命中，则转至步骤S4；若在二级LRU表的热表中命中，则转至步骤S5；若在二级LRU表的候选表中命中，则转至步骤S6；
S4、将相应的粗热数据判定为冷数据，并将其LPN插入到候选表的表头；
S5、将相应的粗热数据判定为热数据，并将其LPN提升到热表表头；
S6、将相应的粗热数据判定为冷数据，并将其LPN从候选表中提升到热表的表头。
2.根据权利要求1所述的一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，其特征在于，还包括以下步骤：
S7、在往二级LRU表插入新表项时，若热表已满，则将热表中最后一项剔除到候选表表头；若候选表已满，则直接将候选表最后一项剔除。
3.根据权利要求1或2所述的一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，其特征在于，所述布隆过滤器采用2个独立的哈希函数。
4.根据权利要求3所述的一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，其特征在于，所述步骤S1包括：
S11、选取两个独立的哈希函数；
S12、使用两个独立的哈希函数对写请求的逻辑页号LPN进行哈希运算，得到两个哈希值；
S13、根据得到的哈希值，在哈希表中到对应的两个计数器，并将两个个计数器的值都加1；
S14、若LPN对应的两个计数器都满足粗热数据要求，即标志位为1，则判定为粗热数据；否则，判定为冷数据。
5.根据权利要求4所述的一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，其特征在于，所述布隆过滤器采用的两个独立的哈希函数分别采用对LPN直接取模和将LPN对折相加平方后再取模的计算函数。
6.根据权利要求5所述的一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，其特征在于，所
述哈希表中每一项都设置一个4位计数器，其中最高2位为标志位，即标志位Flag＝bit3|bit2，哈希表长度设置为211。
7.根据权利要求6所述的一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，其特征在于，布隆过滤器衰减周期N＝212。
8.根据权利要求1所述的一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，其特征在于，所述步骤S2包括：
S21、对当前服务请求数量n进行计数，即n＝n+1；
S22、比较n和N的大小关系，若n＝＝N，则将布隆过滤器的所有计数器的值往右移动一位，并重置n为0。
权 利 要 求 书1/1页CN 112052190 A
一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别
方法
技术领域
[0001]本发明属于固态硬盘数据存储技术领域，具体涉及一种基于布隆过滤器和二级LRU(Least Recently Used)表的固态硬盘热数据识别方法。
背景技术
[0002]近年来，随着NAND存储器技术研究的不断进步，以NAND闪存为存储介质的固态硬盘SSD，凭借其读写速度快、功耗低、体积小、防震抗摔、便于携带等等优点，已经在许多领域开始取代传统机械硬盘。
[0003]闪存具备三大特性：1)以页(page)、块(block)、平面(plane)的结构进行组织，基本操作为读、写、擦除；页是读/写的基本单位，块是擦除的基本单位；三种操作的响应时间读最快，写次之，擦除最慢。2)写入数据前必须进行擦除，即不支持原地更新。3)闪存每个存储单元的编程/擦除(P/E)次数有限，意味着超过擦除次数后该存储单元存储数据不再可靠，即寿命有限。针对以上特性，为了适应当前文件系统，一般要提供一个中间软件转换层实现对闪存的管理，称为闪存转换层FTL(Flash Translation Layer)。
[0004]FTL一般由地址映射、垃圾回收和磨损均衡三个模块组成。地址映射负责将来自文件系统的逻辑地址转换为闪存中的物理地址；垃圾回收负责将回收块中的有效数据复制到新的物理块中，擦除回收块后重新利用；磨损均衡负责保证每个块的磨损速率尽量一致，防止部分块因磨损过快而提前损坏。
[0005]为了实现高效的垃圾回收，避免对有效数据的频繁复制移动造成大量的开销，FTL 需要把频繁更新的数据(即热数据)和非频繁更新的数据(即冷数据)区分开，即热数据识别。热数据识别，一方面可以将识别出的热数据集中存放在同一个块中以提高垃圾回收效率，有效减小对有效数据的复制移动所造成的开销；另一方面，热数据识别可以将热数据分配到擦除次数较少的块中，防止某些块因为频繁擦除导致磨损过快，改善闪存的磨损均衡，延长使用寿命。
[0006]热数据识别技术对提升SSD的性能，延长其使用寿命有着至关重要的作用。内存开销和热数据识别准确度是衡量一个热数据识别算法的关键指标。由于热数据识别算法和垃圾回收以及磨损均衡密切相关，因此SSD中的大多数热数据识别算法只考虑识别热的写请求。经典的识别算法如DAM(直接地址法)，其主要思想是给每一个页分配一个计数器，通过记录请求的访问次数来记录每一个页的访问情况。一定时间内如果计数器大于设定的阈值则判定为热数据，否则为冷数据。为每个页分配一个计数器，需要大量的内存空间，这限制了其在实际产品中的应用。基于布隆过滤器的识别算法，利用哈希函数将逻辑页地址映射到哈希表中进行计数。虽然只占用很小的内存空间，但是其存在假阳的问题，因此很容易造成误报，对识别准确度造成影响，且没有很好地综合考虑请求的频率和时间特性。基于LRU 原则的热数据识别技术，其性能易受到表长的影响，且冷数据容易提升到热表中，这不仅造成误报率，还会加快将热数据从热表中剔除，造成部分漏报率。其他一些算法，如基于请求
大小、访问模式等。这些方法考虑因素比较单一，没能综合考虑负载的局部性特征，热数据识别的准确
度不高。
发明内容
[0007]基于现有技术中存在的上述不足，本发明提供一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法。该方法在一定内存开销情况下，有效提高热数据识别准确率。[0008]为了达到上述发明目的，本发明采用以下技术方案：
[0009]一种基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，包括以下步骤：[0010]S1、将写请求的逻辑页号LPN输入至布隆过滤器，将数据分为冷数据和粗热数据；[0011]S2、检测布隆过滤器的衰减周期N是否达到；若是，则衰减布隆过滤器的计数器值；[0012]S3、将步骤S1得到的粗热数据的LPN输入至二级LRU表进行处理，并判断粗热数据的LPN是否在二级LRU表中命中；其中，所述二级LRU表包括热表和候选表；若没有在二级LRU 表中命中，则转至步骤S4；若在二级LRU表的热表中命中，则转至步骤S5；若在二级LRU表的候选表中命中，则转至步骤S6；
[0013]S4、将相应的粗热数据判定为冷数据，并将其LPN插入到候选表的表头；[0014]S5、将相应的粗热数据判定为热数据，并将其LPN提升到热表表头；
[0015]S6、将相应的粗热数据判定为冷数据，并将其LPN从候选表中提升到热表的表头。[0016]作为优选方案，基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，还包括以下步骤：
[0017]S7、在往二级LRU表插入新表项时，若热表已满，则将热表中最后一项剔除到候选表表头；若候选表已满，则直接将候选表最后一项剔除。
[0018]作为优选方案，所述布隆过滤器采用2个独立的哈希函数。
[0019]作为优选方案，所述步骤S1包括：
[0020]S11、选取两个独立的哈希函数；
[0021]S12、使用两个独立的哈希函数对写请求的逻辑页号LPN进行哈希运算，得到两个哈希值；
[0022]S13、根据得到的哈希值，在哈希表中到对应的两个计数器，并将两个个计数器的值都加1；
[0023]S14、若LPN对应的两个计数器都满足粗热数据要求，即标志位为1，则判定为粗热数据；否则，判定为冷数据。
[0024]作为优选方案，所述布隆过滤器采用的两个独立的哈希函数分别采用对LPN直接取模和将LPN对折相加平方后再取模的计算函数。
[0025]作为优选方案，所述哈希表中每一项都设置一个4位计数器，其中最高2位为标志位，即标志位Flag＝bit3|bit2，哈希表长度设置为211。
[0026]作为优选方案，布隆过滤器衰减周期N＝212。
[0027]作为优选方案，所述步骤S2包括：
[0028]S21、对当前服务请求数量n进行计数，即n＝n+1；
[0029]S22、比较n和N的大小关系，若n＝＝N，则将布隆过滤器的所有计数器的值往右移动一位，并重置n为0。
[0030]本发明与现有技术相比，有益效果是：
[0031]本发明的基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，能够将两种识别算法的优势相结合，弥补对方的不足；此外，二级LRU表与固态硬盘闪存转换层的地址映射模块相结合，并无额外开销。总体上能够综合考虑数据访问的频率以及时间特性，针对不同类型的负载都能有效提升热数据识别准确率。
附图说明
[0032]图1是本发明实施例的基于布隆过滤器和二级LRU表的热数据识别方法的流程图；[0033]图2是本发明实施例的布隆过滤器模块示意图；
[0034]图3是本发明实施例的二级LRU表模块示意图；
[0035]图4是本发明实施例的布隆过滤器对数据进行初步识别流程示意图。
[0036]图5是本发明实施例的二级LRU表对粗热数据进行二次识别流程示意图。[0037]图6本发明实施例的热数据识别方法的应用实例的结果图。
具体实施方式
[0038]为了更清楚地说明本发明实施例，下面将对照附图说明本发明的具体实施方式。显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图，并获得其他的实施方式。
[0039]如图1所示，本发明实施例的基于布隆过滤器和二级LRU表的固态硬盘热数据识别方法，主要通过布隆过滤器和二级LRU表级联构架来实现。布隆过滤器用来将输入的请求逻辑页号筛选掉冷数据，得到粗热数据；二级LRU表用来进行冷热判断从粗热数据中精确识别出热数据，从而将冷数据和热数据区分。
[0040]如图2所示，本发明实施例的布隆过滤器采用2个独立的哈希函数，哈希表中每一项都设置一个4位计数器，其中最高2位为标志位，即Flag＝bit3|bit2)，哈希表长度设置为211，布隆过滤器衰减周期N＝2
12。为实现该布隆过滤器，额外需要4KB的存储开销。[0041]如图3所示，本发明实施例的二级LRU表包括候选表和热表，表的每一项为请求的LPN，其中，候选表和热表各为512项，总共需要4KB的空间。需要指出的是，在SSD的闪存转换层中，无论是否有热数据识别，地址映射表表本身就是需要存储的，所以这个二级LRU表并不需要额外的存储空间。
[0042]本发明实施例以当前需要识别的写请求的LPN为4301为例，详细阐述本发明的热数据识别的流程，如图4所示，具体包括以下步骤：
[0043]步骤1：将写请求的逻辑页号LPN输入到布隆过滤器，经布隆滤波处理后将数据分成冷数据和粗热数据。其具体流程如下：
[0044]步骤1.1：选取合适的2个独立的哈希函数。本实施例中分别采用对LPN直接取模和将LPN对折相加平方后再取模的计算函数；
[0045]步骤1.2：使用这2个独立的哈希函数对相应的LPN进行哈希运算，得到2个哈希值；[0046]Hash_value1＝mod(4301,211)＝205
[0047]Hash_value2＝mod((43+1)2,211)＝1936
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议