CN106293521B - 一种映射粒度自适应的闪存转换层管理方法 - Google Patents

Abstract

本发明公开了一种映射粒度自适应的闪存转换层管理方法，包括：从文件系统接收数据请求，并判断该数据请求的类型是读请求还是写请求，如果是写请求，则根据该写请求的逻辑页号查询闪存存储空间的页映射表，以判断该写请求对应的逻辑页是否不是第一次写，如果是则根据页映射表中该逻辑页号对应的类型判断该逻辑页的类型是部分页面还是完整页面，如果是部分页面则将该部分页面对应的子页状态表中的子页状态设置为失效，判断写请求的大小是否大于闪存页的大小，如果是则从整页空闲队列的队首取出空闲的物理页，将写请求对应的数据写入该物理页中。本发明能够减少大容量闪存页访问造成的读写性能下降和存储空间浪费。

Description

一种映射粒度自适应的闪存转换层管理方法

技术领域

本发明属于固态盘存储技术领域，更具体地，涉及一种映射粒度自适应的闪存转换层管理方法。

背景技术

作为目前最广泛使用的外存储设备，机械硬盘的读写性能已经渐渐不能满足上层应用的需求，存储设备的性能已经成为计算机系统整体性能的瓶颈。为了提高计算机存储系统的性能，近年来，以与非型(NAND)闪存作为存储介质的固态硬盘获得了广泛的应用。固态硬盘具有高带宽、低延迟、低功耗、抗震性好、无噪音等特点，已经在消费级市场和企业级存储中部分替代机械硬盘，成为主要的存储设备之一。随着闪存制造工艺的进步，NAND型闪存芯片的存储密度越来越高，存储容量越来越大。作为闪存读写的基本单位，闪存页的容量也呈现逐渐增加的趋势。从早先的512字节，增加到4KB、8KB，现在已经出现了16KB页大小的单层单元(Single-Level Cell，简称SLC)和多层单元(Multi-Level Cell，简称MLC)NAND型闪存芯片，未来还可能增加到32KB甚至更大。

为了提供兼容机械硬盘的访问接口，固态硬盘通常采用闪存转换层(FlashTranslation Layer，简称FTL)向上层隐藏闪存的读、写、擦除操作。通过使用闪存转换层，大部分文件系统都可以直接应用在固态硬盘上。而常见文件系统的存储单位文件系统块(File System Block，简称FSB)的大小基本固定，通常都采用4KB的存储单位。闪存页的容量已经达到文件系统块的数倍。以16KB的闪存页为例，4个4KB的文件系统块才能填满一个闪存页。如果需要更新一个闪存页中4KB的数据，需要先将整个闪存页中16KB的数据读出，与4KB的更新数据合并后，再写入一个新的闪存页中。由表1可知，在2010年之前，主要NAND型闪存芯片的闪存页容量不超过4KB。此时，闪存页容量与文件系统块不匹配的矛盾并不凸显。随着闪存页容量的增加，大容量闪存页对读写性能的影响越来越明显，常用的闪存转换层方法并不能很好的解决这个问题。

表1 NAND型闪存和闪存页容量增大趋势

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种映射粒度自适应的闪存转换层管理方法(Mapping Granularity Adaptive Flash Translation Layer，简称MGA-FTL)，其目的在于，利用闪存单元可以被重复写入的特性，支持以闪存子页为粒度分配存储空间和对闪存页进行重复写入，提高了大容量闪存页的空间利用率和读写性能。MGA-FTL针对不同的文件系统请求的粒度，采用完整的闪存页或闪存页部分空间进行响应，即采用页级映射和子页级映射相混合映射的管理方法。当文件系统请求大小与一个闪存页大小相同时，分配一个完整的闪存页存储请求的数据；当文件系统请求大小小于一个闪存页大小时，分配闪存页中的一个子页来存储请求的数据，该闪存页中剩余的空间可以保留用于存储其他小于闪存页大小的请求；另外，本发明通过提出一种子页合并策略。子页合并策略根据该文件系统请求访问的频率，通过限制文件系统请求可以分布在不同闪存页中的数目，更好的减少请求的访问延迟，使系统达到更好的性能。

为实现上述目的，按照本发明的一个方面，提供了一种映射粒度自适应的闪存转换层管理方法，包括以下步骤：

(1)从文件系统接收数据请求，并判断该数据请求的类型是读请求还是写请求，如果是写请求，则进入步骤(2)，如果是读请求，则进入步骤(9)；

(2)根据该写请求的逻辑页号查询闪存存储空间的页映射表，以判断该写请求对应的逻辑页是否不是第一次写，如果是则转入步骤(3)，否则转入步骤(4)；

(3)根据页映射表中该逻辑页号对应的类型判断该逻辑页的类型是部分页面还是完整页面，如果是部分页面则将该部分页面对应的子页状态表中的子页状态设置为失效，然后转入步骤(4)，如果是完整页面则将完整页面对应的页状态表中的页状态设置为失效，然后转入步骤(4)；

(4)判断写请求的大小是否大于闪存页的大小(其通常是8kB或者16kB)，如果是则转入步骤(5)，否则转入步骤(6)；

(5)从整页空闲队列的队首取出空闲的物理页，将写请求对应的数据写入该物理页中，并将完整页面对应的页状态表中的页状态修改为全部有效，然后过程结束；其中整页空闲队列是系统初始化时建立的，用于分配空闲的物理页；

(6)判断写请求的分配策略是独占式分配还是共享式分配，如果是独占式分配转入步骤(7)，如果是共享式分配转入步骤(8)。

(7)根据页映射表中该逻辑页号对应子页映射表指针，找到该逻辑页号的子页映射表，将写请求对应的数据写入同一个物理页中。若页映射表中没有该逻辑页号的表项，则创建表项并在整页空闲队列的队首取出空闲的物理页进行分配。然后过程结束。

(8)从请求大小对应的部分页空闲的队首取出空闲的物理子页，将写请求对应的数据写入该物理子页中，并将部分页面对应的子页状态表中的子页状态设置为有效，然后过程结束；其中部分有效队列是根据整页空闲队列的使用情况动态建立的，用于响应部分页面数据大小的写请求；

(9)根据该读请求的逻辑页号对应的类型判断该逻辑页的类型是部分页面还是完整页面，如果是部分页面则转入步骤(10)，否则转入步骤(12)。

(10)根据子页映射表中该读请求的逻辑页号对应的物理子页号，读出物理子页中数据，并将该逻辑页的读次数计数器加1；

(11)根据该逻辑页的读次数计数器以及该逻辑页关联的物理页数量，判断是否需要合并分散的子页，如果需要则进行合并，然后过程结束，否则过程结束。

(12)根据页映射表中该读请求的逻辑页号对应的物理页号，读出物理页中数据，然后过程结束。

优选地，步骤(2)具体为，首先查询闪存存储空间的页映射表，并判断其中是否有写请求的逻辑页号，如果有则表示逻辑页不是第一次写，否则表示是第一次写。

优选地，页映射表结构包括两级索引的映射表，第一级为页映射表，表项包括逻辑闪存页号，该逻辑闪存页的映射类型和对应物理闪存页号，其中如果逻辑闪存页号对应映射类型是部分页面，则物理闪存页号表项指向一个第二级映射表，称为子页映射表，子页映射表表项包括逻辑闪存子页号，该逻辑闪存子页号对应物理闪存页号、闪存页中具体的物理闪存子页号、该逻辑页关联的物理页数量。

优选地，页状态表结构包括两级闪存页状态表，第一级为页状态表，表项包括物理闪存页号、物理闪存页的类型、以及物理闪存页状态，如果物理闪存页对应类型为部分页面，则状态表项指向一个子页状态表，该子页状态表包括物理子页号、子页对应状态、以及物理页对应的逻辑页的数量。

优选地，空闲页队列包括一个整页空闲队列和一个部分页空闲队列，整页空闲队列将所有状态为整页空闲的闪存页组成一条队列，部分页空闲队列分为3条子队列，每条队列下反别挂载空闲空间为4KB、8K和12KB大小的闪存页，这些闪存页之间的转化规则是，如果响应请求之后该闪存页中还有可用的空间，则再将其链入相应空闲容量的队列中。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：

1、本发明基于闪存页的重复写入特性，结合具体的闪存芯片访问接口和特性参数，提出了一种以闪存子页为粒度对大容量闪存页进行重复写入的方法，减少了主机和固态硬盘之间不必要的数据传输，进而提高了闪存存储空间的利用率。

2、本发明重新定义了闪存页的状态和状态转换图。增加了一个“部分有效”的闪存页状态，用于描述部分子页包含有效数据的闪存页。并且定义该状态和闪存页原有的“空闲”、“有效”和“过期”三个状态之间的转换关系，从能够对闪存页物理状态进行更为精细的描述。

3、本发明设计了针对子页级映射和页级映射进行优化的两级索引的地址映射表，在页级映射的基础上，通过动态内存分配的方式为子页映射表分配存储空间。采用子页级映射处理文件系统的小粒度读写请求，由此解决了文件系统读写单位小于闪存页容量的技术问题。

4、本发明提出了一种既充分利用大容量闪存页中的子页空间，又防止数据分布过于分散的方法，并针对该分配方案设计了子页合并和垃圾回收的方法。

附图说明

图1是闪存单元写入和写入禁止的示意图。

图2是本发明方法的数据结构示意图。

图3示出本发明方法的两级索引映射表。

图4示出本发明方法的闪存页状态转换图。

图5示出本发明方法的闪存页状态表。

图6示出本发明方法的可分配空闲页队列。

图7示出本发明方法的独占式与共享式子页分配方式。

图8示出本发明方法中限制LPN关联的PPN数量的示意图。

图9是本发明映射粒度自适应的闪存转换层管理方法的流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

本发明的目的在于，针对使用大容量闪存页的固态硬盘，优化闪存转换层的功能，减少大容量闪存页访问造成的读写性能下降和存储空间浪费。

在闪存页写操作时，同一闪存页中的所有闪存单元共享对应字线上写入电压(Programming Voltage，用符号Vp表示)。该电压使半导体衬底中的电子利用隧道效应穿过氧化层进入浮栅中。但是，如果提高衬底中导电沟道的电压，就可以减少氧化层上的电压降，从而防止电子利用隧道效应进入浮栅，如图1所示。图1(a)为处于写入状态的闪存单元，导电沟道电势低，穿过氧化层的电场强，电子容量发生隧道效应进入浮栅。图1(b)为处于写入禁止状态的闪存单元，导电沟道电势高，穿过氧化层的电场弱，电子不容易发生隧道效应进入浮栅。闪存转换层通常规定当一个闪存页被写入数据后，只有对该闪存页所在的闪存块进行擦除(擦除后为“1”状态)，才能再次向该闪存页写入数据。但是，根据上述的闪存单元写入禁止特性，如果闪存页某一位为“1”，在不擦除的情况下，可以将该位修改为“0”，直到闪存页中的不存在“1”为止。即闪存页是可以被重复写入的。闪存页重复写入时，只修改闪存页中的部分区域，不需要重新写入整个闪存页，减少了传输数据量和闪存存储空间的浪费，也相对增强了闪存的使用寿命。

为方便描述，下表2中列出了本发明中用到的符号和它们的说明。

表2 符号说明

两级索引映射表：

MGA-FTL是一种页级映射和子页级映射相混合的闪存转换层，通过页映射来处理普通粒度的文件系统请求，通过子页映射来服务小粒度的文件系统请求。映射表采用一级映射表为页映射表(Page Mapping Table，PMT)，二级映射表为子页映射表(SubpageMapping Table，SPMT)的方式。为了减小映射表的内存开销，二级映射表采用动态内存分配，即只有当逻辑页需要进行子页粒度的写入时，才为其分配二级映射表内存。

图3给出了两级索引映射表的一个实例情况。其中LPN为0、2、3的逻辑页对应完整的闪存页(类型为FP)直接进行页级映射，不需要二级映射表。LPN为1、4的逻辑页对应闪存页的部分子页，需要使用二级映射表。此时，页映射表表项中的PPN字段存放的是指向二级映射表的指针。在子页映射表中，保存了该逻辑页中的各个逻辑子页映射的物理页号(PPN)和物理子页号(PSPN)，除此之外，还记录了该逻辑页映射的物理页的数量(PPN Count)，用于在闪存页分配和合并时进行参考。对于不存在映射关系的逻辑地址，其物理地址在图中用“N/A”表示。

闪存空间状态信息转换：

通常在闪存转换层中，物理闪存页的状态包括空闲(Free)，有效(Valid)和无效(Invalid)三种。因为MGA-FTL需要表示一个闪存页中的部分子页有效这种新状态，所以添加了一个新的闪存页状态，部分有效(Part Valid，PV)，用于描述这种闪存页中以子页为单位存放数据的情形。添加此状态后，MGA-FTL共包含四个状态，即整页空闲(Full Free，FF)、整页有效(Full Valid，FV)、整页无效(Full Invalid，FI)和部分有效。图4给出了MGA-FTL中闪存空间状态信息转换关系。

MGA-FLT针对新的闪存空间状态信息转换，增加了两级闪存页状态表。图5给出了与图3相同存储情形下的两级闪存页状态表信息。两级闪存页状态表包括闪存页状态表(Page State Table，PST)和子页状态表(Subpage State Table，SPST)。图5中，PPN为0、2、3的物理页作为完整的闪存页使用，因此状态为全部有效(FV状态)；而PPN为1，4的物理页只使用了部分子页，因而引入了二级状态表。PPN为1的闪存页中，PSPN为0、1、2的子页保存了有效数据(V状态)，而PSPN为1的子页空闲(F状态)。PPN为4的闪存页的子页使用情况与其类似。除了记录物理子页的状态，还记录了该物理页对应的逻辑页的数量(LPN Count)。例如，物理页PPN 1中的数据来自于LPN 1和LPN 4，因此记为2。

闪存空闲空间分配算法：

在MGA-FTL中，可供分配的空闲空间包括1)处于FF状态的完整的空闲闪存页，2)处于PV状态，并包含空闲子页的闪存页。基于表2所对一个闪存页大小16KB和一个闪存子页大小4KB的假设，MGA-FTL将可分配的最大连续空间相同的闪存页组成一条队列，如图6所示，则FF状态的闪存页组成一条队列，PV状态的闪存页则分为三条不同的队列，分别用于响应4KB、8KB和12KB不同大小的子页请求。如果响应请求之后该闪存页中还有可用的空间，则再将其链入相应空闲容量的队列中。为方便描述，下文将这些闪存页队列分成成为FF队列、PV4KB队列、PV8KB队列和PV12KB队列。

当文件系统请求小于闪存页容量时，可以为其分配一个完整的FF状态的闪存页，也可以分配一个包含足够空闲空间的PV状态的闪存页。由此引入了两种不同的空闲空间分配策略：

1)独占式分配方式(Exclusive Allocation，简称EA)

即将同属于同一个逻辑页的逻辑子页分配到同一个物理页中，即该物理页被逻辑页独占，如图7(a)所示。独占式分配的优点在于减少了子页合并时的开销，但是造成了空间利用率较低。

2)共享式分配方式(Shared Allocation，简称SA)

即属于不同逻辑页的逻辑子页可以被分配到同一个物理页中，如图7(b)所示。共享式分配方式的优点在于子页空间利用率高，但是合并操作的开销较大。

两种分配方式各有其优缺点，MGA-FTL引入了一个参数——分配阈值(AllocationThreshold，简称AT)决定采用哪种分配方式，AT与FF状态的闪存页的比例(即空闲页比例，Free Page Ratio，简称FPR)相关，当FPR>＝AT时，系统中处于FF状态的空闲页充足，使用EA分配方式，直接分配空闲页用于响应子页请求。当FPR<AT时，不在消耗FF状态空闲页，转而使用SA分配方式，消耗PV状态的闪存页中的空闲子页。当系统中空闲页随着垃圾回收操作的进行由增加，FPR再次超过AT时，MGA-FTL重新使用EA分配方式。此外，在分配空闲空间时，还会考虑请求的空间局部性。

闪存空闲空间分配算法如图8所示。文件系统写请求分配物理地址时，分为分配完整的闪存页、采用独占式分配方法分配空闲子页、采用共享式分配方式分配空闲子页三种方式。其中，共享式分配又根据请求的大小，分别从闪存页空闲空间为4KB、8KB、12KB的三个队列中选取合适的闪存页。

碎片空间合并算法与无效数据回收算法：

MGA-FTL为了提高大容量闪存页的利用率，利用闪存页中未被写入的空闲区域来处理子页粒度的文件系统请求。这样做带来的问题是同一个逻辑页的数据可能分布到不同的物理页中，造成了闪存存储空间的碎片化。当对逻辑页进行读操作时，需要读取多个物理页，从而降低固态硬盘的读性能。

针对这个问题，MGA-FTL采用了限制一个逻辑页关联的物理页的数量(PPN Count，PC)的方法来进行优化，同时参考逻辑页的读次数(Read Count，RC)，其基本思路是：一个逻辑页的读次数越多，该逻辑页相关联的物理页越少。按照前文的假定，当采用16KB的闪存页且子页容量为4KB时，同一个逻辑页可能关联的物理页数量最多为4个。MGA-FTL规定如下：1)RC＝＝0，PC<＝4；2)0<RC<＝2，PC<＝3；3)2<RC<＝5，PC<＝2；4)RC>5，PC＝1。

当某一逻辑页没有被读过时，可以将它的子页写到多个物理页中；随着读次数的增加，关联的物理页数量减少；当该逻辑页被多次读之后，系统将只允许在一个物理页上存储该逻辑页，即使造成额外的空间浪费。如图8(a)所示，假设现有一个逻辑页LPN的四个子页LSPN 0～3分布在物理页PPN A和PPN B中。现在文件系统发出对该逻辑页的最后一个子页LSPN 3的写操作。当该LPN的都次数RC为0，则可以按照图8(b)中所示的方式，将LSPN 3写入PV4KB队列中的物理页PPN C的空闲子页中，而LSPN 2仍然保存在PPN B中，该LPN关联的物理页的数量变为3。但是，如果RC为4，PC不能大于2，即需要限制LPN关联的物理页的数量，此时可以按照图8(c)中的方式，将LSPN 2和LSPN 3写入到PV8KB队列中的物理页PPN D中，这样不会增加改LPN的PC计数，但是会造成一个子页的多余数据迁移。如果RC为10，则需要按照图8(d)中所示的，将LSPN 0～3全部拷贝到FF队列中的物理页PPN E中，此过程增加了3个子页的额外数据迁移，但是之后再对该LPN进行读操场时，只需要从PPN E中读取，减少了读操作的开销。

系统采用参数——垃圾回收阈值(Garbage Collection Threshold，简称GCT)来决定垃圾回收操作的触发时机。当空闲的闪存空间的比例低于GCT时，触发垃圾回收操作，选取包含较多无效数据的闪存块进行回收。

如图9所示，本发明映射粒度自适应的闪存转换层管理方法包括以下步骤：

(1)从文件系统接收数据请求，并判断该数据请求的类型是读请求还是写请求，如果是写请求，则进入步骤(2)，如果是读请求，则进入步骤(9)；

(2)根据该写请求的逻辑页号查询闪存存储空间的页映射表，以判断该写请求对应的逻辑页是否不是第一次写，如果是则转入步骤(3)，否则转入步骤(4)；具体而言，首先查询闪存存储空间的页映射表，并判断其中是否有写请求的逻辑页号，如果有则表示逻辑页不是第一次写，否则表示是第一次写；

如图3所示，给出了页映射表结构及列举了一个应用实例。页映射表结构包括两级索引的映射表，第一级称为页映射表，表项包括逻辑闪存页号(LPN)，该逻辑闪存页的映射类型(Type)和对应物理闪存页号(PPN)。如果逻辑闪存页号对应映射类型是部分页面(PP)，则物理闪存页号表项指向一个第二级映射表，称为子页映射表。子页映射表表项包括逻辑闪存子页号(LSPN)，该逻辑闪存子页号对应物理闪存页号(PPN)以及闪存页中具体哪个物理闪存子页号(PSPN)，除此之外，还记录了该逻辑页关联的物理页数量(PPN Count)，用于在闪存页分配和合并时进行参考。实例情况如图3中所示，逻辑闪存页号为0、2、3的逻辑页对应完整页面(类型为FP)直接进行页级映射，不需要二级映射表。逻辑闪存页号为1、4的逻辑页对应闪存页的部分子页，需要使用二级映射表。此时，页映射表表项中的物理闪存页号字段存放的是指向二级映射表的指针。

(3)根据页映射表中该逻辑页号对应的类型判断该逻辑页的类型是部分页面(Partial page，简称PP)还是完整页面(Full page，简称FP)，如果是部分页面则将该部分页面对应的子页状态表中的子页状态设置为失效，然后转入步骤(4)，如果是完整页面则将完整页面对应的页状态表中的页状态设置为失效，然后转入步骤(4)；

具体而言，子页状态表是在闪存页部分使用的状态下动态生成的，用于保存闪存子页的使用状态；其具体状态转换过程如图4所示；

如图5所示，给出了页状态表结构及图3中映射实例对应的状态表信息情况。页状态表结构包括两级闪存页状态表，第一级称为页状态表，表项包括物理闪存页号(PPN)，物理闪存页的类型(Type)和物理闪存页状态(State)。如果物理闪存页对应类型为部分页面(PP)，则状态表项指向一个子页状态表。子页状态表包括物理子页号(PSPN)和该子页对应状态(State)，此外还包括该物理页对应的逻辑页的数量(LPN Count)。对应实例情况如图5中所示，物理闪存页号为0、2、3的物理页作为完整的闪存页使用，因此状态为全部有效(FV状态)；而物理闪存页号为1，4的物理页只使用了部分子页，因而引入了二级状态表。物理闪存页号为1的闪存页中，物理子页号为0、1、2的子页保存了有效数据(V状态)，而物理子页号为3的子页空闲(F状态)。

(4)判断写请求的大小是否大于闪存页的大小(其通常是8kB或者16kB)，如果是则转入步骤(5)，否则转入步骤(6)；

(5)从整页空闲队列的队首取出空闲的物理页，将写请求对应的数据写入该物理页中，并将完整页面对应的页状态表中的页状态修改为全部有效；其中整页空闲队列是系统初始化时建立的，用于分配空闲的物理页；然后过程结束。

如图6所示，给出了闪存系统可分配空闲页队列示意图。空闲页队列包括一个整页空闲队列和一个部分页空闲队列。整页空闲队列将所有状态为整页空闲的闪存页组成一条队列；部分页空闲队列分为3条子队列，每条队列下反别挂载空闲空间为4KB、8K和12KB大小的闪存页。它们之间的转化规则是，如果响应请求之后该闪存页中还有可用的空间，则再将其链入相应空闲容量的队列中。

(6)判断写请求的分配策略是独占式分配(Exclusive Allocation，简称EA)还是共享式分配(Shared Allocation，简称SA)，如果是独占式分配转入步骤(7)，如果是共享式分配转入步骤(8)。

(7)根据页映射表中该逻辑页号对应子页映射表指针，找到该逻辑页号的子页映射表，将写请求对应的数据写入同一个物理页中。若页映射表中没有该逻辑页号的表项，则创建表项并在整页空闲队列的队首取出空闲的物理页进行分配。然后过程结束。

如图7所示，分配策略包括独占式分配，否则为共享式分配。独占式分配即将同属于同一个逻辑页的逻辑子页分配到同一个物理页中，该物理页被逻辑页独占。共享式分配允许不同逻辑页的逻辑子页被分配到同一个物理页中。

闪存空闲空间分配算法描述如图(8)所示。

(8)从请求大小对应的部分页空闲的队首取出空闲的物理子页，将写请求对应的数据写入该物理子页中，并将部分页面对应的子页状态表中的子页状态设置为有效；其中部分有效队列是根据整页空闲队列的使用情况动态建立的，用于响应部分页面数据大小的写请求。然后过程结束。

(9)根据该读请求的逻辑页号对应的类型判断该逻辑页的类型是部分页面还是完整页面，如果是部分页面则转入步骤(10)，否则转入步骤(12)。

(10)根据子页映射表中该读请求的逻辑页号对应的物理子页号，读出物理子页中数据，并将该逻辑页的读次数计数器(Read Count，简称RC)加1；

(11)根据该逻辑页的读次数计数器以及该逻辑页关联的物理页数量，判断是否需要合并分散的子页，如果需要则进行合并，然后转入(结束)；否则转入(13)。

具体而言，合并规则规定如下：1)RC＝＝0，PC<＝4；2)0<RC<＝2，PC<＝3；3)2<RC<＝5，PC<＝2；4)RC>5，PC＝1。

如图(9)所示，为合并操作的一个实例示意图。图8(a)所示，假设现有一个逻辑页LPN的四个子页LSPN 0～3分布在物理页PPN A和PPN B中。图8(b)所示，文件系统发出对该逻辑页的最后一个子页LSPN 3的写操作。当该LPN的都次数RC为0，将LSPN 3写入PV4KB队列中的物理页PPN C的空闲子页中，而LSPN 2仍然保存在PPN B中，该LPN关联的物理页的数量变为3。图8(c)所示，如果RC为4，PC不能大于2，将LSPN 2和LSPN 3写入到PV8KB队列中的物理页PPN D中。图8(d)所示，如果RC为10，将LSPN 0～3全部拷贝到FF队列中的物理页PPN E中。

(12)根据页映射表中该读请求的逻辑页号对应的物理页号，读出物理页中数据，然后过程结束。

实验结果表明，相比于普通页映射的闪存转换层方法，MGA-FTL有效地减少了闪存页容量增大带来的数据传输时间和闪存存储空间的浪费。在所测试的真实负载中，最多可以减少53％的请求平均响应时间，30％的固态硬盘写入放大和40％的闪存块擦除操作。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

Claims (5)

1.一种映射粒度自适应的闪存转换层管理方法，其特征在于，包括以下步骤：

(1)从文件系统接收数据请求，并判断该数据请求的类型是读请求还是写请求，如果是写请求，则进入步骤(2)，如果是读请求，则进入步骤(9)；

(2)根据该写请求的逻辑页号查询闪存存储空间的页映射表，以判断该写请求对应的逻辑页是否不是第一次写，如果是则转入步骤(3)，否则转入步骤(4)；

(3)根据页映射表中该逻辑页号对应的类型判断该逻辑页的类型是部分页面还是完整页面，如果是部分页面则将该部分页面对应的子页状态表中的子页状态设置为失效，然后转入步骤(4)，如果是完整页面则将完整页面对应的页状态表中的页状态设置为失效，然后转入步骤(4)；

(4)判断写请求的大小是否大于闪存页的大小，如果是则转入步骤(5)，否则转入步骤(6)；

(5)从整页空闲队列的队首取出空闲的物理页，将写请求对应的数据写入该物理页中，并将完整页面对应的页状态表中的页状态修改为全部有效，然后过程结束；其中整页空闲队列是系统初始化时建立的，用于分配空闲的物理页；

(6)判断写请求的分配策略是独占式分配还是共享式分配，如果是独占式分配转入步骤(7)，如果是共享式分配转入步骤(8)；

(7)根据页映射表中该逻辑页号对应子页映射表指针，找到该逻辑页号的子页映射表，将写请求对应的数据写入同一个物理页中，若页映射表中没有该逻辑页号的表项，则创建表项并在整页空闲队列的队首取出空闲的物理页进行分配，然后过程结束；

(8)从请求大小对应的部分页空闲队列的队首取出空闲的物理子页，将写请求对应的数据写入该物理子页中，并将部分页面对应的子页状态表中的子页状态设置为有效，然后过程结束；其中，部分页空闲队列是根据整页空闲队列的使用情况动态建立的，用于响应部分页面数据大小的写请求；

(9)根据该读请求的逻辑页号对应的类型判断该逻辑页的类型是部分页面还是完整页面，如果是部分页面则转入步骤(10)，否则转入步骤(12)；

(10)根据子页映射表中该读请求的逻辑页号对应的物理子页号，读出物理子页中数据，并将该逻辑页的读次数计数器加1；

(11)根据该逻辑页的读次数计数器以及该逻辑页关联的物理页数量，判断是否需要合并分散的子页，如果需要则进行合并，然后过程结束，否则过程结束；

(12)根据页映射表中该读请求的逻辑页号对应的物理页号，读出物理页中数据，然后过程结束。

2.根据权利要求1所述的闪存转换层管理方法，其特征在于，步骤(2)具体为，首先查询闪存存储空间的页映射表，并判断其中是否有写请求的逻辑页号，如果有则表示逻辑页不是第一次写，否则表示是第一次写。

3.根据权利要求1所述的闪存转换层管理方法，其特征在于，

页映射表结构包括两级索引的映射表，第一级为页映射表，表项包括逻辑闪存页号、该逻辑闪存页的映射类型和对应物理闪存页号，其中如果逻辑闪存页号对应映射类型是部分页面，则物理闪存页号表项指向一个第二级映射表，称为子页映射表；

子页映射表表项包括逻辑闪存子页号、该逻辑闪存子页号对应物理闪存页号、闪存页中具体的物理闪存子页号、该逻辑页关联的物理页数量。

4.根据权利要求1所述的闪存转换层管理方法，其特征在于，

页状态表结构包括两级闪存页状态表，第一级为页状态表，表项包括物理闪存页号、物理闪存页的类型、以及物理闪存页状态；

如果物理闪存页对应类型为部分页面，则状态表项指向一个子页状态表，该子页状态表包括物理子页号、子页对应状态、以及物理页对应的逻辑页的数量。

5.根据权利要求1所述的闪存转换层管理方法，其特征在于，

空闲页队列包括一个整页空闲队列和一个部分页空闲队列；

整页空闲队列将所有状态为整页空闲的闪存页组成一条队列；

部分页空闲队列分为3条子队列，每条队列下反别挂载空闲空间为4KB、8KB和12KB大小的闪存页，这些闪存页之间的转化规则是，如果响应请求之后该闪存页中还有可用的空间，则再将其链入相应空闲容量的队列中。