大块NAND闪存的转换层优化算法设计

秦晓安

（安徽商贸职业技术学院电子信息工程系，安徽芜湖241002）

大块NAND闪存的转换层优化算法设计

秦晓安

（安徽商贸职业技术学院电子信息工程系，安徽芜湖241002）

通过运用大块NAND研究闪存转换层的基本原理，针对物理闪存中的数据块和更新块，利用地址混合映射的方法，对逻辑块号和页号进行拆分，区分更新块的热门页及数据块的冷门页，使用改进的优化算法根据其空闲程度进行部分、完全或交换合并优化，最后通过实验对存储利用率和缓存大小影响进行性能分析，实验数据表明：运用该算法可以有效提高NAND闪存存储效率.

NAND闪存；闪存转换层；地址映射；垃圾回收

NAND闪存是一种比硬盘驱动器更好的存储方案，这在不超过4GB的低容量应用中表现得犹为明显.随着人们持续追求功耗更低、重量更轻和性能更佳的产品，NAND正被证明极具吸引力[1].

通过对NAND Flash的存储及操作特性的研究，发现通用文件系统不能直接用于管理Flash设备[2].最近，一种新型NAND闪存存储器已经问世，称之为大块NAND，它可以提供高密度及高性能的大块数据传输.在大块NAND闪存存储器中，每页由2 K字节主数据区和64字节空闲区组成，其中1块由64页组成.但是大块NAND有一个使用限制：在一个块中，页写必须按照从页0到页63的顺序，块中随机页写是被禁止的.

NAND闪存不同于磁盘或是SRAM和DRAM，与读操作相比，写操作需要更长的时间.因为在写操作之前经常需要先进行擦除操作，所以擦写操作时间会更长.大块NAND闪存存储器的另外一个局限是单位块的擦写，极限是大约100 000到1 000 000次，而且必须先擦后写.因此，本文研究改进的办法尽可能地减少擦写操作次数，以提高整体性能和延长大块NAND闪存的寿命.

1 算法研究

1.1 基本原理

闪存转换层（FTL）是NAND闪存存储器的软件中间层，它的主要作用是用来消除上层对于NAND闪存存储器先擦后写的限制[3]，其中最主要的两个部分是地址映射和垃圾回收.地址映射的主要工作是将目标逻辑页与对应的物理页进行映射，根据所映射的颗粒度大小，可以分为页映射和块映射；垃圾回收是指擦除特定块进行回收空白页的过程.

随着NAND闪存存储容量的增加，页映射需要更多RAM，这将会导致很严重的成本问题.比如，一个4G字节的NAND闪存，页映射需要8M字节的RAM用来管理映射表，而块映射只需要128 K字节.所以，一些基于块映射的闪存转换层改进机制被广泛应用于NAND闪存的存储系统.

通常根据块的用途，可以把物理闪存中的块分为D-blocks（数据块）和U-blocks（更新块）[4].当一个写操作发生、且写操作无法在所要求的D-block完成时，闪存转换层会将新数据写入U-block同时置原D-block为无效.一旦U-block被分配出来，接下去原D-block上的写操作就会被重定向到相关的U-block上.当U-block写满之后，闪存转换层可以分配一个新的U-block或者通过合并U-block和原D-block生成一个新的D-block.虽然有许多不同的块映射闪存转换层实现，区别主要来自如何管理D-blocks和U-blocks，如什么时候分配多少U-blocks给一个D-block，或者合并操作如何完成.

1.2 算法实现

在垃圾回收过程中，首先挑选拥有最大序号的U-block的D-block为目标块，将所有的有效页拷贝到最后一个U-block.接着最后的U-block将成为新的D-block.因为页总是被合并入最后一个U-block，所以只有部分合并和交换合并操作.替换块机制存储空间利用率很差，特别是当块中只有部分页被频繁更新时.且这种机制不适用于大块NAND闪存，由于块中的页无法进行随机写操作.

由于闪存转换层只使用少量的U-block，额外的映射开销会比较小.当所有的U-block都被使用了，部分U-block会与对应的D-block进行合并以释放出新的空闲U-block.由于D-block是被in-place方式管理的，完全合并会用来将out-of-place转换为in-place.另外，即使D-block中一页更新，也需要一个完整的U-block，类似于替换块机制，U-block的空间使用率还是比较低.

块级别的空间局部性通常存在于，当两个或者多个相邻逻辑块被文件系统分配给同一文件或者一些元数据，如FAT、目录、i-node或者bitmap.因此，如果几个相邻逻辑块共享一个U-block，U-block的存储利用率会提高.

U-block被相关的块用来利用块级别的时间局部性和空间局部性.一旦U-block被分配给块，接下来的块的写请求被从第一页开始按顺序记录到U-block中.这种out-of-place机制同样适用于块中必须从第一页到最后一页顺序写的大块NAND闪存存储器.当U-block中没有空闲页的时候，新的U-block被分配给块.

因为大块NAND闪存存储器单页空闲区域的容量限制，整个页表会被分成4个独立的PT.PMD的作用就是定位每个PT的最新位置，最新PMD的位置信息被PGD所管理.PGD储存在主存储中，而PMD和PT被储存在空闲区域中.因为PGD的条数等于逻辑块数，所以PGD的存储占用与其他块级别的闪存管理层机制是相当的.

图1举例说明了地址映射的过程.假设想找到逻辑块17中逻辑页12的物理地址.逻辑块号被拆为块号4及PGD序号1，逻辑页号又可以拆分为PMD序号0及PTE序号12.如图所示，从块4及PGD 1中找到逻辑块17最新的PMD.PMD被从空闲区域中读出，从第一个名录找到PT0的位置，PT0保存有PTE0到PTE15的信息.最终数据的位置可以从PT0中的PTE12读到.

图1 地址映射的过程

在拆分结束后，进行合并操作.具体操作方法是首先找到一个物理块没有任何有效页.如果这样的块存在，擦除该块并分配给新块.如果所选的块为D-block，则针对U-block交换合并成D-block.如果这一步不成功，其次找到新块中含有最少最近改写的U-block，如果D-block含有足够的空闲页，则进行部分合并.在其他的情况下，从新块中挑选两个含有最少有效页的D-block，然后执行完全合并.完全合并后，新块被重新组成：新的块和U-block成为了D-block，原先的D-block被擦除后被用作空闲U-block.

这种做法的理由是U-block通常含有热门页，而D-block含有冷门页.因此，将冷门页一起放在D-block中对于未来的垃圾回收是十分理想的.当完全合并后，块被重新组成：新的块和U-block成为了D-block，原先的D-block被擦除后被用作空闲U-block.这样可以将块中更新频率接近的页放入一个D-block中.因为两个D-block所含的有效页数可能超过空闲块中可以存储的页数，完全合并将一直进行到所有的有效页都被处理完.

如前一小点所述，由于维护映射信息的限制，分配给新块的U-block和D-block数量不能超过8个.因此，当尝试为超级块分配第9个物理块时，同样的垃圾收集将被执行以用来回收一个物理块.

当一个逻辑页被更新，更新后的页映射信息依然存放在空闲区域中.比如，假如上一段例子中的逻辑页被更新了，PTE12将指向逻辑页将要被写入的位置，第一个PMD条目将指向同样的物理页，因为拥有了新的PT0.当页中被写入了修改过的PMD和PT0，第二个PGD条目也将被改为指向新的地点.由于更新的PMD和相对应的PT不管何时页被更新了都被储存在闪存存储中，因而可以保证PMD和PT的每个条目始终指向有效页.

因为每次读、写或拷贝一页的时候，都应该读出PMD和对应的PT，所以采用缓存的方式来减少闪存读操作的次数.缓存条目包括PMD和对应的4条被用来记录单块逻辑块页映射信息的PT.缓存条目的数量是固定的，使用最近最少使用（LRU）替换的机制来管理这些条目[5].这样的缓存机制类似于日志块机制和FAST中使用的机制.实验显示少量的缓存条目工作得非常好.

2 性能分析

2.1 存储利用率

存储利用率是影响闪存转换层性能的一个很重要的因素，因为较低的存储利用率会导致更频繁的垃圾回收[6].为了研究每种闪存转换层算法的存储利用率的影响，统计了每个U-block已写页的数量（当一个块被选为垃圾回收的目标块时）.图2显示了PC场景下统计的累积分布（CDF）.

图2 PC场景下统计的累积分布（CDF）

图2显示了大部分的目标块，或已满了或只占用不到4页.因为大块NAND闪存物理块有64页，图中的数值显示的都是已写页块所占的百分比.在日志块机制下，当它们被选作垃圾回收的目标块时，大约65%的块是完全被使用的.如预期一致，由于提高了共享的程度，与日志块机制相比FAST显示了更好的存储利用率.FAST下完全使用块百分比上升到了75%.

完全使用块所占百分比在块机制下大约为85%，明显比FAST利用率更高.因为FAST中U-block是被所有的逻辑块共享的，而在块机制中这些是只在同一块中的逻辑块间共享的.测试显示这是由于FAST算法中的一个缺点造成的.FAST使用顺序的日志块以优化顺序写，不像其他随机日志块，这种顺序日志块是被分配给特定的逻辑块，这与日志块机制相同[7].如果基于顺序操作的预测错了，顺序日志块会被合并即使没有写满.块机制不会有这样的问题，因为一个块中若干相邻逻辑块总是共享一个U-block.因此，可以看到所介绍的块机制是利用块级别空间局限性更加有效和更加健全的方法.

图3根据完全合并、部分合并和交换合并操作类型详细对比了擦除操作的执行时间.

图3 不同类型合并操作对比擦除操作的执行时间

通过图3可以发现，与FAST机制相比块机制中72%以上的擦除操作是由于交换合并.这是因为一方面，块机制在多个逻辑块之间共享D-block和U-block，且同时使用out-of-place机制来管理所有的物理块，提高了交换合并的几率.另一方面，由于完全合并造成的擦除操作数量显著减少.当U-block中的页不是顺序的，日志块机制和FAST需要完全合并操作以满足in-place机制维护D-block.然而，块机制可以转换U-block为一个新的D-block，很简单将一个完全合并转化为交换合并.

2.2 缓存大小的影响

图4显示了缓存条目从16到1 024缓存命中率的变化.注意最小缓存大小下对于所有类型请求缓存命中率高于93%.这显示了测试中很高的块级别的时间局部性及页级别的空间局部性.

缓存条目从16到1 024，命中率只最多提高了1.2%.因此16个缓存条目在多数情况下已经足够.

图4 缓存条目从16到1024缓存命中率的变化

3 结语

针对大块NAND闪存存储器只能先擦后写的局限，研究基于块映射的闪存转换层进行改进，仍然使用原有块映射技术，但是允许块中的逻辑页自由映射到任一分配的物理块.这种混合映射技术具有细颗粒度地址映射的灵活性，同时将空间消耗降低到粗颗粒度映射级别.通过与原有技术进行性能对比，实验表明，优化的算法不仅降低了垃圾回收的的次数，而且提高了交换合并的几率用以取代代价很大的完全合并.

[1]互动百科.NAND闪存[EB/OL].(2010-02-03)[2014-07-22].http: //www.baike.com/wiki/NAND%E9%97%AA%E5%AD%98.

[2]唐卫明.大容量NAND闪存存储管理研究[D].长沙：国防科学技术大学,2009.

[3]刘芳，刘志龙，肖侬，等.一种基于数据压缩的高效闪存转换层设计[J].计算机研究与发展,2011(S1):317-321.

[4]Park C,Cheon W,Kang J,etal.A reconfigurable FTL(flash translation layer)architecture for NAND flash-based applications[J]. ACM Transactions on Embedded Computing Systems(TECS). 2008,7(4),Article38.

[5]郁志平，刘伟，彭虎,等.一种混合映射闪存转换层的设计与实现[J].计算机工程,2014(2):300-303.

[6]赵培.闪存的存储管理及索引方法研究[D].武汉：华中科技大学,2011.

[7]Leventhal A.Flash storage memory[J].Communications of the ACM,2008,51(7):41-57.

【编校：王露】

Optim ization Design for the Conversion of Bulk NAND Flash Layer

QIN Xiao'an
(Department of Electronic Information Engineering,Anhui Business College of Vocational Technology,Wuhu,Anhui 241002,China)

Based on thebasic principleofbulk NAND flash translation layer,taking into consideration the block of data in flashmemory and physicalupdate block,using themethod ofmixedmapping address,the logicalblock numberand page numberwere split to distinguish popular page ofdata block from unpopular ones;using optimization algorithm to come up with the optimized solution based on its idle degree so as to decidewhether to improve partly or totally,or exchange data. Performance analysiswas carried out through the experimentof storage utilization and cache size influence,which shows that the algorithm can effectively improve theefficiency ofNAND flashmemory.

NAND flashmemory;flash translation layer;addressmapping;garbage collection

TP301.6

A

1671-5365(2014)12-0099-03

2014-07-24修回：2014-08-14

秦晓安(1982-)，男，讲师，硕士，研究方向为嵌入式、程序算法

时间：2014-08-22 15:23

http://www.cnki.net/kcms/detail/51.1630.Z.20140822.1523.002.htm l