一种基于请求分类的闪存转换层控制方法

摘要

本发明公开了一种基于请求分类的闪存转换层控制方法，包括以下步骤：步骤S1：根据文件系统的操作请求以及地址请求频率，在内存中相应设置多个地址映射缓存表；步骤S2：闪存转换层获取文件系统的操作请求，并对其解析以确定该操作请求类型；步骤S3：根据该操作请求类型按照不同优先级顺序在多个地址映射缓存表中查找该操作请求的逻辑页地址，直至命中相应的地址映射项；步骤S4：根据操作请求结果更新内存中地址映射缓存表。与现有技术相比较，本发明更加细粒度地对请求进行划分有利于快速命中映射项，以及在映射项剔除时可以分类剔除，从而加快剔除速度，以及快速分拣出必须更新的映射项，避免了无需更新映射项的更新。

权利要求

1.一种基于请求分类的闪存转换层控制方法，其特征在于，包括以下步骤：步骤S1：根据文件系统的操作请求以及地址请求频率，在内存中相应设置多个地址映射缓存表；

步骤S2：闪存转换层获取文件系统的操作请求，并对其解析以确定该操作请求类型；

步骤S3：根据该操作请求类型按照不同优先级顺序在多个地址映射缓存表中查找该操作请求的逻辑页地址，直至命中相应的地址映射项；

步骤S4：根据操作请求结果更新内存中地址映射缓存表；

所述步骤S1中，地址映射缓存表至少包括不频繁访问随机读缓存表IR_RCMT、频繁访问随机读缓存表FR_RCMT、不频繁访问随机写缓存表IW_RCMT、频繁访问随机写缓存表FW_RCMT、连续缓存表SCMT和全局转换页映射表GTD；

当操作请求为连续读请求时，执行以下步骤：

首先判断是否对连续读请求的地址页映射解析完成，如果完成就结束；

如果没有解析完成，则对请求中的下一个逻辑页地址在SCMT中查找，如果命中，则根据这个映射项信息中的物理页地址读取数据区域中的数据页到内存中；如果没有命中，首先把SCMT这页转换页写入到转换块区域的空闲页中，然后更新GTD；再通过GTD先找到这个映射项所处的转换页，再把这个转换页读取到内存中并覆盖SCMT表；

当操作请求为连续写请求时，执行以下步骤：

首先判断是否对连续写请求的地址页映射解析完成，如果完成就结束；

如果没有解析完成，则先把写请求的一页数据写入到数据区域的空闲页中，再对请求中的逻辑页地址在SCMT中查找，如果命中，则把这条映射项中的物理页地址更新为刚写入的物理页的地址；如果没有命中，把SCMT这页转换页写入到转换块区域的空闲页中并更新GTD；再通过GTD先找到这个映射项在哪个转换页中，再把这个转换页读取到内存中并覆盖SCMT表。

2.根据权利要求1所述的基于请求分类的闪存转换层控制方法，其特征在于，当操作请求为随机读请求时，地址映射缓存表的优先级顺序依次为FR_RCMT、IR_RCMT、FW_RCMT、IW_RCMT、SCMT；

如果无法在内存中的地址映射表中找到相应的地址映射项，则通过GTD找到含有这个映射项的转换页，读取该转换页到内存。

3.根据权利要求1所述的基于请求分类的闪存转换层控制方法，其特征在于，当操作请求为随机写请求时，地址映射缓存表的优先级顺序依次为FW_RCMT、IW_RCMT、FR_RCMT、IR_RCMT、SCMT；

如果无法在内存中的地址映射表中找到相应的地址映射项，则通过GTD找到含有这个映射项的转换页，读取该转换页到内存。

4.根据权利要求1所述的基于请求分类的闪存转换层控制方法，其特征在于，当IW_RCMT溢满时，执行以下步骤：把SCMT写入到空闲转换页中，同时更新GTD；

根据转换页中逻辑页地址的分块特性，计算IW_RCMT中哪部分映射项在一个转换页中的占的比例最大；

把该转换页读取到内存并覆盖掉SCMT；

最后把那部分映射项从IW_RCMT中剔除并更新到SCMT中并结束。

5.根据权利要求1所述的基于请求分类的闪存转换层控制方法，其特征在于，当IR_RCMT溢满时，执行以下步骤：直接剔除IR_RCMT的尾节点。

6.根据权利要求1所述的基于请求分类的闪存转换层控制方法，其特征在于，当FR_RCMT溢满时，执行以下步骤：搬移FR_RCMT的尾节点到IR_RCMT的头节点。

7.根据权利要求1所述的基于请求分类的闪存转换层控制方法，其特征在于，当FW_RCMT溢满时，执行以下步骤：搬移FW_RCMT的尾节点到IW_RCMT的头节点。

说明书

一种基于请求分类的闪存转换层控制方法

技术领域

[0001] 本发明涉及存储技术领域，尤其涉及一种用于固态存储设备的基于请求分类的闪存转换层控制方法。

背景技术

[0002] 随着计算机与网络的不断普及，人们对计算机的速度要求越来越高，而制约计算机速度的一个很关键的因素就是存储介质的速度。传统个人电脑的大容量存储介质是机械硬盘，但是由于其存在机械旋转结构，其读写速度提升十分有限且抗震性不好。相比于HDD(Hard Disk Drive)，SSD具体读写速度快、抗震性好、低功耗等优点。目前常见的SSD主要基于NAND flash，而NAND flash的物理结构与传统的磁存储介质不同，主要区别有：1)闪存只提供页粒度的读与写，块粒度的擦除。2)当页不是空页，闪存不能对页进行覆盖写，需要先对页所在块进行擦除之后才能往这页中写数据。3)闪存的结构从大到小依次是die、plane、block、page。4)闪存的擦除次数有限，达到一定数量后会变成坏块，无法再使用。

[0003] 基于闪存与传统磁介质的差异，闪存中使用闪存转换层(FTL)管理闪存。FTL位于文件系统和闪存驱动层之间，对用户完全透明，并为上层文件系统提供块设备的操作接口，对当前文件系统读写操作与闪存的读写擦操作提供适配功能。由此，现有技术中提出基于需求的页级地址映射(DFTL)，DFTL将经常用到的部分映射项存放在内存SRAM(Static Random Access Memory)中，而把整个映射表保存在闪存中。也即通过地址映射缓存机制解决了页级地址映射表产生的大量内存开销。

[0004] DFTL中的物理块被逻辑地分为两类：数据块(data  block)和地址转换块(translation block)。数据块用于存储数据，转换块用于保存页级地址映射表。每个地址转换块中的页成为地址转换页(translation page)，每个页包含了一定数量的逻辑页号到物理页号的页级地址映射项。为定位到最新的转换页，内存中维护了一个全局转换页映射表(global translation directory，简称GTD)。同时，在内存中使用地址映射缓存(cached mapping table，简称CMT)，以缓存在转换页中频繁访问的地址映射项。

[0005] 但是DFTL中的CMT只考虑了请求的时间局部性，没有考虑请求的空间局部性，降低了缓存的命中率。另外CMT的LRU单一映射项的剔除策略有可能会触发转换页的频繁更新操作和垃圾回收操作，也即，任何请求操作导致CMT缓存溢满时，都会触发闪存中转换页的更新操作，极大降低了系统的速度和寿命。因此如何选择性地缓存映射项，如何对映射项剔除，以及如何垃圾回收，对提升SSD的性能很关键。闪存转换层算法的好坏直接影响到SSD的读写性能的优劣。

[0006] 故，针对目前现有技术中存在的上述缺陷，实有必要进行研究，以提供一种方案，解决现有技术中存在的缺陷。

发明内容

[0007] 有鉴于此，确有必要提供一种基于请求分类的闪存转换层控制方法，从而能够改善随机读写的速度，并提高闪存的使用寿命。

[0008] 为了克服现有技术的缺陷，本发明的技术方案如下：

[0009] 一种基于请求分类的闪存转换层控制方法，包括以下步骤：

[0010] 步骤S1：根据文件系统的操作请求以及地址请求频率，在内存中相应设置多个地址映射缓存表；

[0011] 步骤S2：闪存转换层获取文件系统的操作请求，并对其解析以确定该操作请求类型；

[0012] 步骤S3：根据该操作请求类型按照不同优先级顺序在多个地址映射缓存表中查找该操作请求的逻辑页地址，直至命中相应的地址映射项；

[0013] 步骤S4：根据操作请求结果更新内存中地址映射缓存表。

[0014] 优选地，所述步骤S1中，地址映射缓存表至少包括不频繁访问随机读缓存表(IR_RCMT)、频繁访问随机读缓存表(FR_RCMT)、不频繁访问随机写缓存表(IW_RCMT)、频繁访问随机写缓存表(FW_RCMT)、连续缓存表(SCMT)和全局转换页映射表(GTD)。

[0015] 优选地，当操作请求为随机读请求时，地址映射缓存表的优先级顺序依次为FR_RCMT、IR_RCMT、FW_RCMT、IW_RCMT、SCMT；

[0016] 如果无法在内存中的地址映射表中找到相应的地址映射项，则通过GTD找到含有这个映射项的转换页，读取该转换页到内存。

[0017] 优选地，当操作请求为随机写请求时，地址映射缓存表的优先级顺序依次为FW_RCMT、IW_RCMT、FR_RCMT、IR_RCMT、SCMT；

[0018] 如果无法在内存中的地址映射表中找到相应的地址映射项，则通过GTD找到含有这个映射项的转换页，读取该转换页到内存。

[0019] 优选地，当操作请求为连续读请求时，执行以下步骤：

[0020] 首先判断是否对连续读请求的地址页映射解析完成，如果完成就结束；

[0021] 如果没有解析完成，则对请求中的下一个逻辑页地址在SCMT中查找，如果命中，则根据这个映射项信息中的物理页地址读取数据区域中的数据页到内存中；如果没有命中，首先把SCMT这页转换页写入到转换块区域的空闲页中，然后更新GTD；再通过GTD先找到这个映射项所处的转换页，再把这个转换页读取到内存中并覆盖SCMT表。

[0022] 优选地，当操作请求为连续写请求时，执行以下步骤：

[0023] 首先判断是否对连续写请求的地址页映射解析完成，如果完成就结束；

[0024] 如果没有解析完成，则先把写请求的一页数据写入到数据区域的空闲页中，再对请求中的逻辑页地址在SCMT中查找，如果命中，则把这条映射项中的物理页地址更新为刚写入的物理页的地址；如果没有命中，把SCMT这页转换页写入到转换块区域的空闲页中并更新GTD；再通过GTD先找到这个映射项在哪个转换页中，再把这个转换页读取到内存中并覆盖SCMT表。

[0025] 优选地，当IW_RCMT溢满时，执行以下步骤：

[0026] 把SCMT写入到空闲转换页中，同时更新GTD；

[0027] 根据转换页中逻辑页地址的分块特性，计算IW_RCMT中哪部分映射项在一个转换页中的占的比例最大；

[0028] 把该转换页读取到内存并覆盖掉SCMT；

[0029] 最后把那部分映射项从IW_RCMT中剔除并更新到SCMT中并结束。

[0030] 优选地，当IR_RCMT溢满时，执行以下步骤：

[0031] 直接剔除IR_RCMT的尾节点。

[0032] 优选地，当FR_RCMT溢满时，执行以下步骤：

[0033] 搬移FR_RCMT的尾节点到IR_RCMT的头节点。

[0034] 优选地，当FW_RCMT溢满时，执行以下步骤：

[0035] 搬移FW_RCMT的尾节点到IW_RCMT的头节点。

[0036] 与现有技术相比较，本发明提供的基于请求分类的闪存转换层控制方法，对传统DFTL算法的改进，具有以下技术效果：

[0037] 1)根据请求分类缓存并执行不同的优先级，更加细粒度地对请求进行划分有利于快速命中映射项，以及在映射项剔除时可以分类剔除，从而加快剔除速度，以及快速分拣出必须更新的映射项，避免了无需更新映射项的更新。

[0038] 2)为减少转换页的读写开销，只对IW_RCMT进行聚簇更新，即将属于同一转换页中的映射项进行聚簇，延长了需要更新的映射项在内存中的时间，减少转换块中转换页的更新次数。

附图说明

[0039] 图1为本发明中闪存转换层地址映射原理示意图。

[0040] 图2为本发明文件系统操作请求的解析流程图。

[0041] 图3为随机读请求命令流程图。

[0042] 图4为随机写请求命令流程图。

[0043] 图5为连续读请求命令流程图。

[0044] 图6为连续写请求命令流程图。

[0045] 图7为IW_RCMT映射项满时剔除策略流程图。

[0046] 图8为IR_RCMT映射项满时剔除策略流程图。

[0047] 图9为FR_RCMT映射项满时剔除策略流程图。

[0048] 图10为FW_RCMT映射项满时剔除策略流程图。

[0049] 图11为无效页垃圾回收的示意图。

[0050] 图12为本发明动态垃圾回收机制示意图。

[0051] 图13为本发明静态垃圾回收机制示意图。

[0052] 如下具体实施例将结合上述附图进一步说明本发明。

具体实施方式

[0053] 以下将结合附图对本发明提供的一种基于请求分类的闪存转换层控制方法作进一步说明。

[0054] 参见图1，所示本发明中闪存转换层地址映射原理示意图，闪存被分为2部分：数据块区域和转换块区域。内存SRAM中存储着多种用于地址转换的表，这些表都是依据文件系统的操作请求以及地址请求频率进行分类的，也即将现有技术中DFTL单一的缓存转换表(CMT)至少分为以下类型：不频繁访问随机读缓存表(Infrequent Read Random Cached Mapping Table，IR_RCMT)、频繁访问随机读缓存表(Frequent Read Random Cached Mapping Table,FR_RCMT)、不频繁访问随机写缓存表(Infrequent Write Random Cached Mapping Table,IW_RCMT)、频繁访问随机写缓存表(Frequent Write Random Cached Mapping Table，FW_RCMT)、连续缓存表(Sequential Cached Mapping Table，SCMT)，再运用最近最少使用(Least Recently Used，LRU)策略增加频繁访问映射项在内存中的停留时间来提高缓存的命中率，运用聚簇策略减少转换页擦除与更新次数。其中，GTD用于记录转换块区域中每个转换页的地址映射信息，FR_RCMT用来缓存被请求了两次以上(包括两次)的随机读请求的映射信息，IR_RCMT用来缓存只被请求了一次的随机读请求的映射信息，FW_RCMT用来缓存被请求了两次以上(包括两次)的随机写请求的映射信息，IW_RCMT用来缓存只被请求了一次的随机写请求的映射信息，SCMT用来缓存转换块区域中某一转换页中的连续逻辑页地址映射信息。在图1中，DLPN和DPPN分别表示数据的逻辑页地址和物理页地址，MVPN和MPPN分别表示转换块区域中转换页的逻辑页地址和物理页地址。FR_RCMT，IR_RCMT，FW_RCMT，IW_RCMT的结构体中包含一个键值对(Key为逻辑页地址，Value为物理页地址)和指向下一条映射项的指针。映射项搜索查找的时候先从链表的头节点开始搜索(默认头节点为最近访问的映射项)。以下对上述地址转换的表进行详细介绍：

[0055] 1)IR-RCMT(Infrequent Read Random Cached Mapping Table不频繁访问的随机读缓存映射表)

[0056] IR-RCMT是用来缓存不频繁访问的随机读请求的逻辑页地址到物理页地址的映射项，IR-RCMT的数据结构是一个单向链表的结构，每个节点存储着逻辑页地址到物理页地址的映射信息和下一个节点的地址。IR-RCMT链表的头节点始终存储着最新首次访问的随机读请求的映射项信息。

[0057] 当有随机读请求(请求单独的一页16KB的数据大小)到来，当请求递交到IR-RCMT的时候，会从IR-RCMT的头节点开始遍历查找该请求的逻辑页地址是否在IR-RCMT中，如果遍历搜索到这个逻辑页地址后，再根据这个逻辑页地址对应的物理页地址把数据页从数据块区域中读取出来，同时把链表中的这条映射项搬移到IR-RCMT的链表的头节点。

[0058] 当有随机写请求(请求单独的一页16KB的数据大小)到来，会把这一页数据直接写在数据块区域的任何一个空闲页中。当请求递交到IR-RCMT的时候，会从IR-RCMT的头节点开始遍历查找该请求的逻辑页地址是否在IR-RCMT中，如果遍历搜索到这个逻辑页地址后，会更新这个逻辑页对应的物理页地址信息，同时把链表中的这条映射项搬移到IW-RCMT的链表的头节点。

[0059] 当随机读请求映射项不在IR_RCMT时，则依次到FW_RCMT(Frequent Write Random Cached Mapping Table)，IW_RCMT(Infrequent Write Random Cached Mapping Table)、SCMT(Sequential Cached Mapping Table)中查询。当随机写请求映射项不在IR_RCMT时，则到SCMT中查询。

[0060] 当IR_RCMT满时，把链表尾节点的映射项剔除。因为IR_RCMT为读请求的映射项，所以可以直接剔除，不用把映射项信息更新到转换页中。

[0061] 2)FR_RCMT(Frequent Read Random Cached Mapping Table频繁访问的随机读缓存映射表)

[0062] FR_RCMT是用来缓存频繁访问的随机读请求的逻辑页地址到物理页地址的映射项，FR-RCMT的数据结构是一个单向链表的结构，每个节点存储着逻辑页地址到物理页地址的映射信息和下一个节点的地址。FR-RCMT链表的头节点始终存储着最新被多次访问的随机读请求的映射项信息。

[0063] 当有随机读请求到来，当请求递交到FR-RCMT的时候，会从FR-RCMT的头节点开始遍历查找该请求的逻辑页地址是否在FR-RCMT中，如果遍历搜索到这个逻辑页地址后，再根据这个逻辑页地址对应的物理页地址把数据页从数据块区域中读取出来，同时把链表中的这条映射项搬移到FR-RCMT的链表的头节点。

[0064] 当有随机写请求到来，会把这一页数据直接写在数据块区域的任何一个空闲页中。当请求递交到FR-RCMT的时候，会从FR-RCMT的头节点开始遍历查找该请求的逻辑页地址是否在FR-RCMT中，如果遍历搜索到这个逻辑页地址后，会更新这个逻辑页对应的物理页地址信息，同时把链表中的这条映射项搬移到IW-RCMT的链表的头节点。

[0065] 当随机读请求映射项不在FR_RCMT时，则依次到IR_RCMT，FW_RCMT，IW_RCMT、SCMT中查询。当随机写请求映射项不在FR_RCMT时，则依次到IR_RCMT、SCMT中查询。

[0066] 当FR_RCMT满时，把链表尾节点的映射项搬移到IR_RCMT链表的头节点。

[0067] 3)FW_RCMT(Frequent Write Random Cached Mapping Table频繁访问的随机写缓存映射表)

[0068] FW_RCMT是用来缓存频繁访问的随机写请求的逻辑页地址到物理页地址的映射项，FW-RCMT的数据结构是一个单向链表的结构，每个节点存储着逻辑页地址到物理页地址的映射信息和下一个节点的地址。FW-RCMT链表的头节点始终存储着最新被多次访问的随机写请求的映射项信息。

[0069] 当有随机写请求到来，会把这一页数据直接写在数据块区域的任何一个空闲页中。当请求递交到FW-RCMT的时候，会从FW-RCMT的头节点开始遍历查找该请求的逻辑页地址是否在FW-RCMT中，如果遍历搜索到这个逻辑页地址后，会更新这个逻辑页对应的物理页地址信息，同时把链表中的这条映射项搬移到FW-RCMT的链表的头节点。

[0070] 当有随机读请求到来，当请求递交到FW-RCMT的时候，会从FW-RCMT的头节点开始遍历查找该请求的逻辑页地址是否在FW-RCMT中，如果遍历搜索到这个逻辑页地址后，再根据这个逻辑页地址对应的物理页地址把数据页从数据块区域中读取出来，同时把链表中的这条映射项搬移到FW-RCMT的链表的头节点。

[0071] 当随机读请求映射项不在FW_RCMT时，则依次到IW_RCMT、SCMT中查询。当随机写请求映射项不在FW_RCMT时，则依次到IW_RCMT、FR_RCMT、IR_RCMT、SCMT中查询。

[0072] 当FW_RCMT满时，把链表尾节点的映射项搬移到IW_RCMT的链表头节点。

[0073] 4)IW_RCMT(Infrequent Write Random Cached Mapping Table不频繁访问的随机写缓存映射表)

[0074] IW_RCMT是用来缓存不频繁访问的随机写请求的逻辑页地址到物理页地址的映射项，IW-RCMT的数据结构是一个单向链表的结构，每个节点存储着逻辑页地址到物理页地址的映射信息和下一个节点的地址。IW-RCMT链表的头节点始终存储着最新首次访问的随机写请求的映射项信息。

[0075] 当有随机写请求到来，会把这一页数据直接写在数据块区域的任何一个空闲页中。当请求递交到IW-RCMT的时候，会从IW-RCMT的头节点开始遍历查找该请求的逻辑页地址是否在IW-RCMT中，如果遍历搜索到这个逻辑页地址后，会更新这个逻辑页对应的物理页地址信息，同时把链表中的这条映射项搬移到FW-RCMT的链表的尾节点。

[0076] 当有随机读请求到来，当请求递交到IW-RCMT的时候，会从IW-RCMT的头节点开始遍历查找该请求的逻辑页地址是否在IW-RCMT中，如果遍历搜索到这个逻辑页地址后，再根据这个逻辑页地址对应的物理页地址把数据页从数据块区域中读取出来，同时把链表中的这条映射项搬移到FW-RCMT的链表的尾节点。

[0077] 当随机读请求映射项不在IW_RCMT时，则到SCMT中查询。当随机写请求映射项不在IW_RCMT时，则依次到FR_RCMT，IR_RCMT、SCMT中查询。

[0078] 当IW_RCMT满时，先把SCMT写入到空闲的转换页中，同时更新GTD。再计算出哪个转换页中的映射项在IW_RCMT占的比例最多。然后把这转换页读取到内存并覆盖掉SCMT，最后把指定的占比最多的映射项组合从IW_RCMT中剔除，并更新到SCMT。

[0079] 5)SCMT(Sequential Cached Mapping Table连续缓存映射表)

[0080] SCMT的大小是16KB(一个页的大小)，可以存放2000个地址映射项，是用来缓存GTD在转换块区域中一个转换页中的所有逻辑页地址到物理页地址的映射项信息，是用数组的形式来存储映射项信息。

[0081] 当有随机写请求到来且请求的映射项在SCMT中时，先在数据块区域中的空闲页中写入写请求页，然后更新SCMT中这条映射项信息，最后把这条映射项复制到IW_RCMT链表的尾部。当有随机读请求到来且请求的映射项在SCMT中时，就可立即根据映射项中的物理页地址读取数据页，并把这条映射项信息复制到IR_RCMT的链表的头部。当随机读请求映射项不在SCMT时，则通过GTD(Global Translation Directory)在转换块区域中查找到含有这一映射项的转换页，并读取到内存中替换掉原来的SCMT，再在SCMT中执行随机读请求。当随机写请求映射项不在SCMT时，则通过GTD在转换块区域中查找到含有这一映射项的转换页，并读取到内存中替换掉原来的SCMT，再在SCMT中执行随机写请求。

[0082] 6)GTD(Global Translation Directory全局转换页映射表)

[0083] GTD是用来存放转换块区域中所有转换页中首个逻辑页地址到转换页物理地址的映射项信息，是用数组来存放映射项信息。当IW_RCMT映射项存储满之后，需要通过聚簇剔除(会选取表中在转换页中占的比例最大的那部分映射项组合作为剔除对象)映射项来更新一个转换页的映射项信息，进而更新GTD的信息。

[0084] 基于上述在内存中设置的多种地址映射缓存表，本发明提出一种基于请求分类的闪存转换层控制方法，包括以下步骤：

[0085] 步骤S1：根据文件系统的操作请求以及地址请求频率，在内存中相应设置多个地址映射缓存表；

[0086] 步骤S2：闪存转换层获取文件系统的操作请求，并对其解析以确定该操作请求类型；

[0087] 步骤S3：根据该操作请求类型按照不同优先级顺序在多个地址映射缓存表中查找该操作请求的逻辑页地址，直至命中相应的地址映射项；

[0088] 步骤S4：根据操作请求结果更新内存中地址映射缓存表。

[0089] 具体的，参见图2，所示为文件系统操作请求的解析流程图，文件系统操作请求分为随机读请求，随机写请求，连续读请求，连续写请求。当文件系统发起读写请求，本发明通过判断请求的数据大小是否超过闪存页(16KB)的大小来判断请求是否是连续请求，同时结合请求的读写类型来最终得出具体的哪个请求。

[0090] 参见图3，所示为随机读请求命令流程图，当随机读请求来请求一个逻辑页地址对应的物理页地址映射信息的时候，会依次在FR_RCMT、IR_RCMT、FW_RCMT、IW_RCMT、SCMT中查找这个逻辑页地址的映射项信息，就相当于对随机读请求来说，FR_RCMT、IR_RCMT、FW_RCMT、IW_RCMT、SCMT查找的优先级是依次递减的。根据时间局部性原理：频繁访问的缓存表的优先级是高于不频繁访问的缓存表，对随机读请求来说读缓存表的优先级是高于写缓存表的优先级。这样对不同的表分不同的查找优先级来实现查找能有效减少查找时间，提高响应速度。

[0091] 当对FR_RCMT的单向链表通过遍历查找到含有这个随机读的逻辑页地址映射信息的时候，会把这个映射信息搬移到FR_RCMT这个单向链表的头节点。根据读写的时间局部性，再次访问这个映射信息的概率是比较高的。当下次再次查找这个映射信息的时候，可在链表靠前的部分直接找到这个映射项信息。又由于FR_RCMT的大小是固定的，当FR_RCMT满了之后，需要对链表尾节点搬移到IR_RCMT的链表的头节点中。这样搬移的映射项也是最近最少访问的映射项，每次访问都进行动态调整映射项在链表中的位置，从而保证留下来的映射项是被访问概率相对高的。

[0092] 当对IR_RCMT的单向链表通过遍历查找到含有这个随机读的逻辑页地址映射信息的时候，会把这个映射信息搬移到FR_RCMT的头节点。根据时间局部性原理，访问之前近期的映射项概率是比较大的。这样当下次还有随机读请求时，同时我们又把之前访问过的映射项信息搬移到FR_RCMT的头节点中。当按照表的优先级来查找映射项信息的时候，可以快速地在高优先级的FR_RCMT表中查找到这个映射项，而不用遍历FR_RCMT链表之后，再在IR_RCMT中查找。此操作是映射项优先级升级，这样操作后能提升映射项命中的速度。

[0093] 当对FW_RCMT的单向链表通过遍历查找到含有这个随机读的逻辑页地址映射信息的时候，会把这个映射信息搬移到FW_RCMT的头节点。之所以不把这个映射项信息搬移到读缓存表中，是因为读缓存表的剔除策略是直接剔除，不需要把映射项信息更新到转换页中，而写缓存表的剔除策略是需要把映射项信息更新到转换页中。所以只能是读缓存表中的映射项搬移到写缓存表中，不能把写缓存表中的映射项搬移到读缓存表中。这个请求是随机读请求，所以没有必要把映射项搬移到写缓存表中。

[0094] 当对IW_RCMT的单向链表通过遍历查找到含有这个随机读的逻辑页地址映射信息的时候，会把这个映射信息搬移到FW_RCMT这个单向链表的头节点。这样操作也是因为表的优先级问题，把最近读访问的映射项信息优先级提升。

[0095] 当对SCMT的单向链表通过遍历查找到含有这个随机读的逻辑页地址映射信息的时候，会把这个映射信息搬移到IR_RCMT这个单向链表的头节点。相当于是说当随机读请求一个单独的页地址映射的时候，如果这个地址映射信息在连续映射缓存表中，就把这个映射项单独抽取出来放入到IR_RCMT中，也就是说对这个映射项的优先级提升。之所以这么做，是因为地址映射请求是具有时间局部性的，在不久的将来访问这个地址映射项信息的概率比访问未访问过的映射项信息的概率大。

[0096] 当无法在内存中的地址映射表中找到这条映射信息，则通过内存中的GTD，根据逻辑页地址号找到这个地址映射信息在转换块中的哪个转换页中(注：转换页中逻辑页地址是按顺序依次递增的，比如一个页中能存储100个映射项信息，那么第一个转换页存储着逻辑页地址1-100的映射项信息，第二个转换页中存储着101-200的逻辑页地址映射项信息，以此类推。GTD中按顺序存储着转换页的物理地址，如GTD中的第一项存储着第一个转换页的物理地址，第二项存储着第二个转换页的物理地址，以此类推。举例：当要请求的逻辑页地址是55，知道55>＝1&&55<＝100，那么就知道映射项信息在第一个转换页中。根据GTD的第一项中的物理地址，找到转换块中的转换页，并读取到内存中，再对这个转换页中的转换项遍历查找，找到这个逻辑页地址55对应的物理页地址)。找到这个转换页后，先把SCMT这个转换页写入到转换块区域中的空闲转换页中，同时更新GTD。再把刚才查找到的转换页读取到内存中，并覆盖掉SCMT。通过把含有此次随机读请求的映射项的转换页搬移到SCMT中，是考虑到空间局部性原理与时间局部性原理。就是说再次访问最近请求映射项附件的映射项信息的概率是比较大的，能有效提高缓存命中率。

[0097] 参见图4，所示为随机写请求命令流程图，当随机写请求来请求一个逻辑页地址对应的物理页地址映射信息的时候，会依次在FW_RCMT、IW_RCMT、FR_RCMT、IR_RCMT、SCMT中查找这个逻辑页地址的映射项信息，就相当于对随机写请求来说，FW_RCMT、IW_RCMT、FR_RCMT、IR_RCMT、SCMT查找的优先级是依次递减的。根据时间局部性原理：频繁访问的缓存表的优先级是高于不频繁访问的缓存表，对随机写请求来说写缓存表的优先级是高于读缓存表的优先级。这样对不同的表分不同的查找优先级来实现查找能有效减少查找时间，提高响应速度。

[0098] 当对FW_RCMT的单向链表通过遍历查找到含有这个随机写的逻辑页地址映射信息的时候，会把这个映射信息搬移到FW_RCMT这个单向链表的头节点。根据读写的时间局部性，再次访问这个映射信息的概率是比较高的，当下次再次查找这个映射信息的时候，可在链表靠前的部分直接找到这个映射项信息。又由于FW_RCMT的大小是固定的，当FW_RCMT满了之后，需要对链表尾节点搬移到IW_RCMT的链表的头节点中，这样搬移的映射项也是最近最少访问的映射项，每次访问都进行动态调整映射项在链表中的位置，从而保证留下来的映射项是访问概率相对高的。

[0099] 当对IW_RCMT的单向链表通过遍历查找到含有这个随机写的逻辑页地址映射信息的时候，会把这个映射信息搬移到FW_RCMT这个单向链表的头节点。由于时间局部性原理，访问之前的映射项概率是比较大的。这样，当下次还有随机写请求时，同时我们又把之前访问过的映射项信息搬移到FW_RCMT的头节点中，这样在按照表的优先级来查找映射项信息的时候，可以快速的在高优先级的FW_RCMT的表中查找到这个映射项，而不用遍历完这个FW_RCMT链表之后，再在IW_RCMT中查找，可以说是映射项优先级升级，此操作也能提升映射项命中的速度。

[0100] 当对FR_RCMT的单向链表通过遍历查找到含有这个随机写的逻辑页地址映射信息的时候，会把这个映射信息搬移到IW_RCMT这个单向链表的头节点。之所以不把这个映射项信息搬移到读缓存表中，是因为读缓存表的剔除策略是直接剔除，不需要把映射项信息更新到转换页中，而写缓存表的剔除策略是需要把映射项信息更新到转换页中。所以只能是读缓存表中的映射项搬移到写缓存表中，不能把写缓存表中的映射项搬移到读缓存表中。这个是随机写请求，所以要把映射项搬移到写缓存表中。

[0101] 当对IR_RCMT的单向链表通过遍历查找到含有这个随机写的逻辑页地址映射信息的时候，会把这个映射信息搬移到IW_RCMT这个单向链表的头节点。这个操作原因也是因为表的优先级问题，把最近写访问的映射项信息优先级提升。

[0102] 当对SCMT的单向链表通过遍历查找到含有这个随机写的逻辑页地址映射信息的时候，会把这个映射信息搬移到IW_RCMT这个单向链表的头节点。相当于是说当随机写请求一个单独的页地址映射的时候，如果这个地址映射信息在连续映射缓存表中，就把这个映射项单独抽取出来放入到IW_RCMT中，也就是说对这个映射项的优先级提升。之所以这么做，是因为地址映射请求是具有时间局部性的，在不久的将来访问这个地址映射项信息的概率比访问没有访问过的映射项信息的概率大。

[0103] 当无法在内存中的地址映射表中找到这条映射信息，则通过内存中的GTD，根据逻辑页地址号找到这个地址映射信息在转换块中的哪个转换页中。找到这个转换页后，先把SCMT这个转换页写入到转换块区域中的空闲转换页中，同时更新GTD。再把刚才查找到的转换页读取到内存中，并覆盖掉SCMT。通过把含有此次随机写请求的映射项的转换页搬移到SCMT中，是考虑到空间局部性原理与时间局部性原理。就是说再次访问最近请求映射项附件的映射项信息的概率是比较大的，能有效提高缓存命中率。

[0104] 参见图5，所示为连续读请求命令流程图，当请求是连续读请求时，首先判断是否对连续读请求的地址页映射解析完成，如果完成就结束。如果没有解析完成，则对请求中的下一个逻辑页地址在SCMT中查找。如果命中，则根据这个映射项信息读取数据区域中的数据页到内存中。如果没有命中，首先把SCMT这页转换页写入到转换区域的空闲页中，然后更新GTD。再通过GTD先找到这个映射项在哪个转换页中，再把这个转换页读取到内存中并覆盖SCMT表(因为SCMT的大小就是一个转换页的大小)，遍历查找这个请求的逻辑页地址对应的物理页地址，找到后根据物理页地址把数据页读入到内存中。假如对连续读请求的第一次页地址映射能在SCMT中查找到，那么根据空间局部性原理，下一个页地址映射一般都会在SCMT中查找到。如果第一次页地址映射不能在SCMT中查找到，首先把SCMT的一页转换页写入到转换区域的空闲页中，然后更新GTD。再通过GTD把含有这个映射项的转换页读取到内存并覆盖掉SCMT。当对下一页地址映射查找的时候，同样根据空间局部性原理，很大概率能在SCMT中查找到这个映射项。此操作同时结合了空间局部性机制和预读取机制，加快了连续读请求的访问速度。每次解析完一个地址映射后，会把剩余的地址页映射解析数减一，下一个逻辑页地址加一，直到地址映射解析完。

[0105] 参见图6，所示为连续写请求命令流程图，当请求是连续写请求时，首先判断是否对连续写请求的地址页映射解析完成，如果完成就结束。如果没有解析完成，则先把写请求的一页数据写入到数据区域的空闲页中。再对请求中的逻辑页地址在SCMT中查找，如果命中，则把这条映射项中的物理页地址更新为刚写入的物理页的地址。如果没有命中，首先把SCMT这页转换页写入到转换区域的空闲页中，然后更新GTD。再通过GTD先找到这个映射项在哪个转换页中，再把这个转换页读取到内存中并覆盖SCMT表，遍历查找这个请求的逻辑页地址，找到后更新对应的物理页地址。假如对连续读请求的第一次页地址映射能在SCMT中查找到，那么根据空间局部性原理，下一个页地址映射一般都会在SCMT中查找到。如果第一次页地址映射不能在SCMT中查找到，首先把SCMT这页转换页写入到转换区域的空闲页中，然后更新GTD。再通过GTD把含有这个映射项的转换页读取到内存并覆盖掉SCMT。当对下一页地址映射查找的时候，同样根据空间局部性原理，很大概率能在SCMT中查找到这个映射项。此操作同时结合了空间局部性机制和预读取机制，加快了连续写请求的地址映射更新速度。每次解析完一个地址映射后，会把剩余的地址页映射解析数减一，下一个逻辑页地址加一，直到地址映射解析完。

[0106] 参见图7，所示为IW_RCMT映射项满时剔除策略流程图，首先判断IW_RCMT是否已经填满了，如果没有就结束。如果满了，则先把SCMT这页转换页写入到空闲转换页中，同时更新GTD。然后根据转换页中逻辑页地址的分块特性，计算IW_RCMT中哪部分映射项在一个转换页中占的比例最大。然后把这个转换页读取到内存并覆盖掉SCMT。最后把那部分映射项从IW_RCMT中剔除并更新到SCMT中并结束。这里在剔除IW_RCMT中的映射项的时候，使用了聚簇的思想。根据转换页中的逻辑数据页地址是连续的，且转换页中的逻辑数据页地址数是一定的。分拣出IW_RCMT中哪部分连续的逻辑数据页地址在转换页中占的比例最大，把这个转换页覆盖掉SCMT。这样IW_RCMT剔除的时候可以一次最大效率地把映射项剔除出去，减少了对Flash的操作次数，延长了Flash的寿命。

[0107] 参见图8，所示为IR_RCMT映射项满时剔除策略流程图，首先判断IR_RCMT是否满，如果没有满则结束。如果满了，则直接剔除IR_RCMT的尾节点。IR_RCMT是单向链表，内存中会保存头节点指针和尾节点指针。对读缓存映射项的剔除是直接剔除映射项，不需要把映射项信息更新到转换页中。只针对必须更新的映射项进行更新，避免无分类、笼统的更新，从而可以减少对Flash的转换页的更新操作次数，延长Flash的寿命。

[0108] 参见图9，所示为FR_RCMT映射项满时剔除策略流程图，首先判断FR_RCMT是否满，如果没有满则结束。如果满了，则搬移FR_RCMT的尾节点到IR_RCMT的头节点。对FR_RCMT的剔除操作不是直接剔除，而是把链表尾节点搬移到次优先级的IR_RCMT的头节点。这样做是为了尽量把高优先级的映射项保留在内存，因为请求具有时间局部性，所以高优先级的映射项再次被访问的概率比低优先级的映射项被访问的概率大。所以宁愿低优先级的缓存映射表腾出空间来存放高优先级的映射项。如此操作尽量使缓存中的映射项优先级比较高，可以提高请求的命中率。

[0109] 参见图10，所示为FW_RCMT映射项满时剔除策略流程图，首先判断FW_RCMT是否满，如果没有满则结束。如果满了，则搬移FW_RCMT的尾节点到IW_RCMT的头节点。对FW_RCMT的剔除操作不是直接剔除，而是把链表尾节点搬移到次优先级的IW_RCMT的头节点。如此操作的原因也是跟对FR_RCMT映射项满剔除时操作的原因一样。

[0110] 参见图11，所示为本发明技术方案对无效页垃圾回收的示意图，其中相对图1，内存中的表格再增加了4个表格，分别是BECT(Bolck Erase Count Table，块擦除次数表)，BIPCT(Block Invalid Page Count Table，块无效页个数表),BIPBT(Block Invalid Page Binary Table，块无效页二进制表)和GCCMT(Garbage Collection Cached Mapping Table，垃圾回收缓存映射表)。每个表的具体作用如下：

[0111] 1)BECT

[0112] BECT分为两部分，一部分是数据块区域中块的擦除次数信息，另一部分是转换块区域中块的擦除次数信息。因为两部分操作类似，以数据块区域块的擦除次数信息来讨论。BECT的数据结构是一维数组，数组下标就是块号，数组中存的数据就是对应块的擦除次数信息。垃圾回收的时候会对数据块区域中的某一块进行了擦除，BECT中的对应的块号的擦除次数加一。

[0113] 2)BIPCT

[0114] BIPCT的数据结构跟BECT一样的。BIPCT数组中存的是对应块的无效页数。当收到写请求的时候，先把写请求的一页数据写入到数据块区域的空闲页中，同时根据无效的物理页地址推算出对应的物理块号，再对BIPCT中的对应下标的数组中存的数据加一。

[0115] 3)BIPBT

[0116] BIPBT是一维数组，下标为块号，数组存储的数据是二进制数组。以二进制的位置表示页在块中的位置，以二进制的数值来表示页是有效页还是无效页，0表示无效，1表示有效。当BIPCT中数据改变的时候，相应的BIPBT中的数据也相对应地改变。

[0117] 4)GCCMT

[0118] GCCMT主要用来缓存块回收时，里面有效页搬移后的最新映射项信息。当垃圾回收块的时候，通过查询BIPBT找到哪些页是有效，哪些页是无效。当一个有效页搬移到别的块中的空闲页时，先根据有效页的逻辑页地址号在内存中的映射表(FW_RCMT、IW_RCMT、FR_RCMT、IR_RCMT、SCMT)中查找对映的映射项，如果找到，则直接根据随机写一页的策略更新这条映射项；如果没有找到，就把这条最新的映射项信息写入到GCCMT中。

[0119] 本发明采用动态垃圾回收和静态垃圾回收来达到对无效页回收，提供可用的块给系统。因为垃圾回收对数据块区域和转换块区域都需要且策略基本一样，这里只讨论数据块区域的垃圾回收策略。动态垃圾回收是指当系统正在读写操作的时候触发的垃圾回收，静态垃圾回收是指当系统空闲的时候触发的垃圾回收。

[0120] 参见图12，所示为动态垃圾回收流程图。当空闲块少于某个最少空闲块数量MinNum的时候才触发。分两种情况操作：1)当系统在随机写的时候触发垃圾回收。2)当系统在连续写的时候触发垃圾回收。不管是哪种情况的动态垃圾回收，都只回收根据(x1*BIPCT+x2*BECT)计算出来值最大的一块物理块，其中x1和x2分别是对BIPCT和BECT的权重值(实际权重值设多少，可分情况讨论，动态赋值。动态设置可以充分考虑在不同情况下，垃圾回收的时候应该更看重块中无效页数最多还是擦除次数最少来选择进行回收的块。)。连续写和随机写的原子操作都是对一页的写，这里不区别处理这两种情况。当系统在写的时候触发垃圾回收，垃圾回收过程如下，根据BIPBT找到这块中哪些页是有效的，然后把其中一个有效页写到别的块的空闲页中，并更新BIPBT和BIPCT。然后在FW_RCMT，IW_RCMT，FR_RCMT，IR_RCMT与SCMT中查看是否有相应的逻辑页地址映射项，如果有，则根据随机写请求策略来完成映射项的修改操作；如果没有命中，则把这个映射项信息写入到GCCMT中。连续搬移有效页直到有效页搬移完毕，这样就腾出一块新的空闲块了。此时GCCMT中存储的是有效页搬移之后的映射项信息，是需要更新到转换块中的映射项信息。那什么时候对GCCMT中的映射项信息剔除到转换页中呢？在随机写的时候有两种时刻来触发GCCMT剔除映射项，一种是系统空闲时刻对GCCMT中的映射项进行聚簇更新，直到GCCMT空闲比例高于一定值X(具体X值，可以动态设置，如空闲比例75％)。另一种就是多次对块进行垃圾回收之后，再对下一个目标块进行垃圾回收会使GCCMT溢出的时候，就先对GCCMT中的信息进行聚簇剔除到转换页中，直到GCCMT空闲比例高于一定值X。

[0121] 参见图13，所示为静态垃圾回收流程图。静态垃圾回收与动态垃圾回收原理基本相似，但是触发时机不同。静态垃圾回收是当系统空闲的时候且当块的最大无效页数达到一定值或者系统空闲块数少于某个最大阈值(MaxNum)，才对块进行垃圾回收且仅回收一块。垃圾回收过程与动态垃圾回收相似，这里不再赘述。那什么时候对GCCMT中的映射项信息剔除到转换页中呢？当回收完一块的时候，就对GCCMT中的映射项进行聚簇剔除到转换页中，直到GCCMT空闲比例高于一定值X。

[0122] 综上，垃圾回收结合块中无效页数与块擦除次数来决定回收哪个块，可以根据不同的应用场景来进行动态设计，通过调参可以使系统更加优化。同时在搬移有效页后，映射项信息先在内存中的除GCCMT的映射表中查找，如果命中则直接更新这个映射项，否则就把这个映射项加入到GCCMT中。这样操作可以充分利用读写时内存产生的映射项缓存信息，从而减少往GCCMT中添加映射项的数量，避免内存中有重复的映射项信息存在。对GCCMT映射项剔除的时候，采用了聚簇剔除的策略，能较少对flash的操作次数，延长flash的寿命。GCCMT剔除结束的标志是空闲比例达到一定值X，这个X可以动态设置，一般不会设成100％，因为GCCMT采用聚簇剔除策略来增加空闲比例的时候，GCCMT中的映射项有一部分是比较零散的，无法聚簇成一组比较大的映射项组进行剔除，所以只要空闲比例达到一定值X就可以结束了。这考虑到聚簇剔除的最佳使用场景。在动态垃圾回收的时候，只在系统空闲或者GCCMT几乎满的时候才进行回收，使系统程序与垃圾回收交替执行，考虑了系统主程序的响应时间要短。静态垃圾回收触发条件是系统空闲且系统空闲块数少于MaxNum或者系统块的最大无效页数达到某个阈值，且只回收一块。这样可以有效避免在系统空闲的时候对那些有效页多无效页少的块盲目进行垃圾回收，从而有效避免了盲目增加块的擦除次数导致SSD的使用寿命减少。这种使用缓存的分策略的垃圾回收机制，对GCCMT分策略缓存聚簇剔除到转换块中，能在系统空闲的时候自动垃圾回收，充分利用系统空闲时间进行垃圾回收，对用户使用是透明的，用户体验度好。在系统高速读写触发动态垃圾回收的时候，与系统主程序交替执行，只少量回收垃圾块，能有效保障系统主程序响应的实时性，不至于因为大规模的垃圾回收，导致系统响应慢或无响应。

[0123] 采用上述技术方案，本发明基于请求分类策略对现有技术DFTL算法的改进，具有以下技术效果：

[0124] 1)采用分类策略思想，将地址映射缓存分为FR_RCMT，IR_RCMT，FW_RCMT，IW_RCMT和SCMT，分别用于缓存访问频繁的随机读请求的映射项，访问不频繁的随机读请求的映射项，访问频繁的随机写请求的映射项，访问不频繁的随机写请求的映射项和连续请求的映射项。更加细粒度地对请求进行划分有利于快速命中映射项，以及在映射项剔除时可以分类剔除，从而加快剔除速度，以及快速分拣出必须更新的映射项，避免了无需更新映射项的更新。还有就是对不同的请求类型，各个映射项缓存表的优先级顺序是根据请求类型相应调整的，让映射项在缓存表中尽快命中。并且通过动态调整内存中映射项的优先级，使高优先级映射项在内存中停留时间更长，映射项命中率更高，速度更快。

[0125] 2)为减少转换页的读写开销，只对IW_RCMT进行聚簇更新。即将属于同一转换页中的占比对多的映射项集进行聚簇，延长了需要更新的映射项在内存中的停留时间，减少转换页的更新次数，从而延长存储介质的寿命。

[0126] 以上实施例的说明只是用于帮助理解本发明的方法及其核心思想。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以对本发明进行若干改进和修饰，这些改进和修饰也落入本发明权利要求的保护范围内。

[0127] 对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。