CN107832013A - 一种管理固态硬盘映射表的方法 - Google Patents

Abstract

本发明公开了一种管理固态硬盘映射表的方法，特征是包括设计固态硬盘的功能结构，将存储映射表的闪存页分为顺序存储和动态存储，为动态的闪存转换页建立索引，设计缓冲区写回策略，映射记录的查找流程和动态闪存转换页的合并等步骤。缓存中的脏数据给了第二次机会留在缓冲区，减少了写回操作。命中动态闪存转换页时一次读取一个闪存页的映射记录并全部加载到缓冲区中，提高了缓存的命中率。本发明的方法与传统的映射表管理方法相比，减少了对固态硬盘的读写次数，同时可以提高固态硬盘的寿命，缓冲区命中率的提高可以大大提升固态硬盘的性能。

Description

一种管理固态硬盘映射表的方法

技术领域

本发明属于固态硬盘技术领域，具体涉及管理固态硬盘地址映射表的方法。

背景技术

美国计算机协会出版的《2009年编程语言和操作系统的架构支持的国际会议的会议记录》(Proceedings of the 2009International Conference on ArchitecturalSupport for Programming Languages and Operating Systems，2009年，第229～240页)中所介绍的固态硬盘映射表的管理方法(DFTL:a flash translation layer employingdemand-based selective caching ofpage-level address mappings)，将固态硬盘的映射表存储到底层的闪存中，并将部分映射表放入到缓存中；当需要查找映射表时，首选在缓存中查找，如果没有命中就需要从闪存中读取一个页的映射表，并从中查找所需的映射记录，将其加载到缓存中；缓存中剔除一个脏的映射记录时，会先读取该映射记录所在的闪存页，修改其内容再重新写入。固态硬盘中闪存的最小读写单元是4KB，一个映射记录的大小只有8B，缓冲区中映射表都是按照一个映射记录(8B)来管理的，而闪存中保存的映射记录都是按照闪存的page(4KB)来管理的，这样当缓存区中的映射记录发生换进换出时，会造成很大的读放大和写放大效应；另一方面，存储映射表的闪存页中只有少数的映射记录是被频繁访问的，这对缓存的命中率也是有影响的。

发明内容

本发明的目的是提出一种管理固态硬盘映射表的方法，以避免现有技术的上述缺点，在保证较低额外开销的情况下，提升固态硬盘的性能，减少对固态硬盘的写入量，提升缓存中映射表的命中率。

本发明管理固态硬盘映射表的方法，其特征在于包括以下步骤：

第一步：设计固态硬盘的功能结构

将固态硬盘中存储数据的闪存分为两部分：一部分用以存储用户数据，另一部分用以存储映射表；将存储映射表的闪存页再分为两部分：一部分按序存储映射记录，后面称为In-order Translation Page，另一部分乱序动态地存放映射记录，后面称为DynamicTranslation Page，这部分的映射记录都是从缓冲区中替换出来的；固态硬盘的内存区域大致分为两部分，一部分用以缓存映射记录，称为CMT，另一部分保存映射表的映射记录，称为GTD；

第二步：为Dynamic Translation Page建立索引

Dynamic Translation Page的索引是存放在内存中的，每个DynamicTranslation Page的索引包括两部分，一部分是Bloom Filter,一部分是该闪存页中映射记录逻辑地址的最大值和最小值，Dynamic Translation Page的索引用来查找某个映射记录是否存在于某个物理的闪存页中；

第三步：缓冲区的写回策略

存储映射记录的缓冲区分为两部分：一部分为主缓冲区，后面称为CMT，另一部分为辅助缓冲区，后面称为Ghost-CMT，辅助缓冲区的大小通常为主缓冲区大小的1％-10％，且最小为一个闪存页的大小；当主缓冲区中替换出一个映射记录时，如果记录为干净的，则直接剔出缓冲区，如果为脏的映射记录，则将映射记录放入到辅助缓冲区；无论记录是在辅助缓冲区中命中还是在主缓冲区命中，都将该记录移到主缓冲区的头部；当辅助缓冲区变满的时候，批量写回一部分映射记录到闪存页中，这样的闪存页为Dynamic TranslationPage，批量写回的映射记录的数量为一个闪存页中存放的映射记录的数量，在写入一个Dynamic Translation Page到闪存上时，同时在内存中为它建立一个索引；

第四步：映射记录查找流程

当需要查找一个映射记录时，首先查找缓存，先查找主缓冲区，再查找辅助缓冲区；如果命中了缓冲区则直接返回，如果没有在缓冲区中命中，则查找DynamicTranslation Page的索引；如果通过索引确定在该记录所在的闪存页在DynamicTranslation Page区域，则从闪存中读出这个闪存页，并将该页中的全部映射记录都加载到缓冲区中；如果不在Dynamic Translation Page区域，则通过计算算出该映射记录所在的闪存页，然后读出该映射记录，并将该条记录加载到映射记录中；

第五步：映射记录的加载

当缓冲区没有命中时，从闪存中读取映射表，存储映射表的闪存页逻辑上分为两部分，一部分为In-order Translation Page，另一部分为Dynamic Translation Page；当要从Dynamic Translation Page中加载一个映射记录时，将该闪存页中的其他记录也同时加载到缓存中；

第六步：Dynamic Translation Page的合并操作

当Dynamic Translation Page的数量超过一定的阈值后，固态硬盘的主控将其合并到顺序存储区，同时在内存中删除Dynamic Translation Page的索引。

上述本发明固态硬盘映射表的管理方法，包括设计固态硬盘的功能结构，将存储映射表的闪存页分为映射记录顺序存储的闪存页和映射记录动态存储的闪存页，为动态的闪存转换页建立索引，设计缓冲区写回策略，映射记录的查找流程和动态闪存转换页的合并等步骤。缓存中的脏数据首先会被踢出到附加缓冲区中，给了第二次机会留在缓冲区，减少了写回操作的次数。命中动态闪存转换页时，一次读取一个闪存页的映射记录，并将该页内的所有映射记录都加载到缓冲区中，提高了缓存的命中率。本发明的方法与传统的映射表管理方法相比，减少了对固态硬盘的读写次数，同时可以提高固态硬盘的寿命，缓冲区命中率的提高可以大大提升固态硬盘的性能。

附图说明

图1为本发明中的固态硬盘的逻辑结构示意图；

图2为固态硬盘中In-order Translation Page的结构示意图。

图3为固态硬盘中GTD的结构示意图；

图4为固态硬盘中Dynamic Translation Page的结构示意图；

图5为固态硬盘中的Dynamic Translation Page的索引结构图；

图6为固态硬盘中映射记录的查找流程图。

具体实施方式

下面结合附图通过具体实施例对本发明固态硬盘映射表的管理方法作进一步的详细说明。

实施例1:

本发明固态硬盘映射表的管理方法的一个具体实施过程举例，包括以下步骤：

第一步：设计固态硬盘的功能结构

图1为本发明中的固态硬盘的逻辑功能结构示意图，上面的部分为动态随机存取存储器(图中标记为DRAM)，下面的部分为闪存(图中标记为flash)；与传统的做法一样闪存分为了两部分，分别用来存储用户数据(图中标记为User Page)和映射表(图中标记为Translation Page)，存储映射表的闪存页(Translation Page)又被分为两部分，一部分是顺序存储的映射表页(图中标记为In-order Translation Page)，另外一部分用来动态存储映射表页(图中标记为Dynamic Translation Page)。

图2给出了In-order Translation Page的结构示意图，如图2所示：每一个闪存页里面存储512个映射记录，每条映射记录包含两个字段，逻辑地址(图中标记为LPN)和物理地址(图中标记为PPN)，每个闪存页里面的映射记录都是连续递增的，而且所有映射记录都是按照逻辑地址升序方式存入到不同的闪存页中的。在本实施例中，将0-10000的逻辑地址分配给保存映射记录的闪存页(也就是Translation Page)，用户数据保存的闪存页的逻辑地址从10000开始，也就是说上层将请求发给固态硬盘时，主控都会自动将地址加上10000，然后再进行处理。Translation Page也有逻辑地址到物理地址的映射，这个映射记录比较小，直接保存在内存中，称为GTD。

图3为固态硬盘中GTD的结构示意图，如图3中所示，GTD的每条记录包含两个字段，一个字段是存储映射表的闪存页的逻辑地址(T-LPN)，另一个字段为其对应的物理地址(T-PPN)。所以当需要查找某个逻辑地址的映射记录时，首先将该地址减去所有In-orderTranslation Page的数量(在本实施例中为10000)，然后除以每个闪存页中保存的映射记录的个数(在这里为512)就可以得到该逻辑地址对应的映射记录所在的闪存页的逻辑地址，然后通过查找映射GTD就可以得出所在闪存页的物理地址。

图4给出了固态硬盘中Dynamic Translation Page的结构示意图，如图4中所示：每个Dynamic Translation Page中仍然是存储512个映射记录，与In-order TranslationPage不同的是，其中的映射记录都是乱序存储的，没有规律可行，每个映射记录仍然是包含两个字段逻辑地址(LPN)和物理地址(PPN)。如果一个映射记录在顺序存储的闪存页中，可以通过计算然后通过查找GTD得到，但是在动态存储的闪存页中时，就需要借助在内存中的索引来查找。

第二步：为Dynamic Translation Page建立索引

图5给出了Dynamic Translation Page的索引结构示意图，如图5所示：每条索引信息包含三部分，主键为存储映射记录的闪存页的物理地址(T-PPN)，后面是该物理地址对应的闪存页中所有映射记录的逻辑地址生成的Bloom Filter,最后一部分是该物理页中映射记录的逻辑地址的最大值和最小值(Max-Min)。通过这些索引信息，就可以比较精确的判断一个逻辑地址的映射记录是否存在某个物理页上。

第三步：缓冲区的写回策略

保存映射表的缓冲区分为CMT和Ghost-CMT,CMT占据了缓冲区的大部分空间，Ghost-CMT只是占据了很小的一部分空间，当CMT发生剔出时，如果是干净的记录就直接剔出，如果是脏记录，则直接放入到Ghost-CMT中。当Ghost-CMT满了时，会一次从Ghost-CMT中替换出512个映射记录(在这里一个闪存页中存放512个映射记录)。首先会分配一个可用的物理页用来写入替换出的512个映射记录，然后用这512个映射记录的逻辑地址生成一个Bloom Filter并求出这512个映射记录中逻辑地址的最大值和最小值，最后用即将要写入的物理页地址，Bloom Filter和最大值、最小值生成了一条索引信息，并记录到内存中，同时将Dynamic Translation Page写入到闪存中。

第四步：映射记录查找流程

图6给出了映射记录的查找流程示意图，如图6所示：对于一个逻辑地址，如果要查找它对应的物理地址过程①，首先查找缓存(包括CMT和Ghost-CMT)，也就是判断是否满足判断过程②的条件,如果在缓存中命中，那么直接返回同时更新缓存即可。如果没有在缓存中命中，这时就要先判断是否在Dynamic Translation Page中，也就是判断是否满足判断过程③的条件，这个过程需要遍历内存中Dynamic Translation Page的索引，对于每一个索引都首先判断该逻辑地址的值是否在索引中最大值和最小值之间，如果不在则继续遍历下一个，如果在就继续用Bloom Filter判断该逻辑地址是否在该闪存页中，如果在就根据物理地址读出该闪存页，然后在从中查找，如果没有查找到，说明Bloom Filter发生了误报，需要继续查找下一个索引。如果遍历完所有的索引后发现该映射记录都不在DynamicTranslation Page中，，那么映射记录就一定在In-order Translation Page中，这时按照传统的做法，通过计算得出存储该映射记录的逻辑地址，然后查找GTD得出物理地址过程④，然后直接从闪存上即可读出相应的闪存页过程⑤，最后从读出的数据中就可以得到所需的映射记录过程⑥。

第五步：映射记录的加载

当缓冲区没有命中时，需要从闪存中读取映射表。当从闪存中加载映射记录时，可能有两中情况，第一种情况是该映射记录位于In-order Translation Page中，这个时候只要读出该闪存页，并将改映射记录加载到缓存中。还有一种情况是该映射记录位于DynamicTranslation Page中，此时会将该闪存页读出，并将该页内的全部映射记录都加载到缓冲区中。当向缓缓冲区中加载一个映射记录，如果缓冲区中有空闲位置就直接加入，如果没有空闲位置，则先剔出一个记录再加载新的记录。

第六步：Dynamic Translation Page的合并操作

Dynamic Translation Page的数量是有上限的，当Dynamic Translation Page的数量达到阈值时就会将其和In-order Translation Page进行合并。合并操作尽可能在固态硬盘的空闲时间内完成，这样可以降低对整体性能的影响。进行合并时会一次读取多个Dynamic Translation Page，然后将其中原本属于同一个In-order Translation Page的所有记录一次更新到一个In-order Translation Page中。

本实施例中，将存储映射记录的闪存页分为In-order Translation Page和Dynamic Translation Page，并通过Bloom Filter和最大值，最小值信息为DynamicTranslation Page建立索引存放在内存中，同时将存储映射记录的缓冲区分为主缓冲区和辅助缓冲区，每次缓冲区发生写回操作时，都批量更新一个闪存页的映射记录到DynamicTranslation Page中，每次在Dynamic Translation Page读取映射记录时，都会将一个页的数据加载到缓冲区中。这样的设计不仅减少了缓冲区写回操作时的写放大问题，还同时提高了缓冲区命中率。

Claims (1)

1.一种管理固态硬盘映射表的方法，其特征在于包括以下步骤：

第一步：设计固态硬盘的功能结构

将固态硬盘中存储数据的闪存分为两部分：一部分用以存储用户数据，另一部分用以存储映射表；将存储映射表的闪存页再分为两部分：一部分按序存储映射记录，后面称为In-order Translation Page，另一部分乱序动态地存放映射记录，后面称为DynamicTranslation Page，这部分的映射记录都是从缓冲区中替换出来的；固态硬盘的内存区域大致分为两部分，一部分用以缓存映射记录，称为CMT，另一部分保存映射表的映射记录，称为GTD；

第二步：为Dynamic Translation Page建立索引

Dynamic Translation Page的索引是存放在内存中的，每个Dynamic TranslationPage的索引包括两部分，一部分是Bloom Filter,一部分是该闪存页中映射记录逻辑地址的最大值和最小值，Dynamic Translation Page的索引用来查找某个映射记录是否存在于某个物理的闪存页中；

第三步：缓冲区的写回策略

存储映射记录的缓冲区分为两部分：一部分为主缓冲区，后面称为CMT，另一部分为辅助缓冲区，后面称为Ghost-CMT，辅助缓冲区的大小通常为主缓冲区大小的1％-10％，且最小为一个闪存页的大小；当主缓冲区中替换出一个映射记录时，如果记录为干净的，则直接剔出缓冲区，如果为脏的映射记录，则将映射记录放入到辅助缓冲区；无论记录是在辅助缓冲区中命中还是在主缓冲区命中，都将该记录移到主缓冲区的头部；当辅助缓冲区变满的时候，批量写回一部分映射记录到闪存页中，这样的闪存页为Dynamic Translation Page，批量写回的映射记录的数量为一个闪存页中存放的映射记录的数量；在写入一个DynamicTranslation Page到闪存上时，同时在内存中为它建立一个索引；

第四步：映射记录查找流程

当需要查找一个映射记录时，首先查找缓存，先查找主缓冲区，再查找辅助缓冲区；如果命中了缓冲区则直接返回，如果没有在缓冲区中命中，则查找Dynamic TranslationPage的索引；如果通过索引确定在该记录所在的闪存页在Dynamic Translation Page区域，则从闪存中读出这个闪存页，并将该页中的全部映射记录都加载到缓冲区中；如果不在Dynamic Translation Page区域，则通过计算算出该映射记录所在的闪存页，然后读出该映射记录，并将该条记录加载到映射记录中；

第五步：映射记录的加载

当缓冲区没有命中时，从闪存中读取映射表，存储映射表的闪存页逻辑上分为两部分，一部分为In-order Translation Page，另一部分为Dynamic Translation Page；当要从Dynamic Translation Page中加载一个映射记录时，将该闪存页中的其他记录也同时加载到缓存中；

第六步：Dynamic Translation Page的合并操作

当Dynamic Translation Page的数量超过一定的阈值后，固态硬盘的主控将其合并到顺序存储区，同时在内存中删除Dynamic Translation Page的索引。