一种优化的闪存转换层的设计与实现*

王志奇，何欣霖

（成都三零嘉微电子有限公司，四川 成都 610041）

0 引言

固态硬盘（Solid State Disk，SSD）作为新型的存储介质，具有体积小、速度快、抗震性好以及温度适应性强等特点，被广泛应用于军工、车载、工控、电力以及医疗等领域。随着技术的不断成熟以及存储介质工艺的不断提升，固态硬盘逐渐普及到消费电子领域。该类硬盘主要由主控器和存储介质组成，目前大容量存储介质主要为NAND Flash。

NAND Flash 具有体积小、重量轻、功耗低[1]、抗震性强以及性能高等优点。但是，NAND Flash本身也存在缺陷，数据翻新时需要将数据按块擦除之后才能进行数据的再次写入。为了解决这个问题，设计了闪存转换层（Flash Translation Layer，FTL），将上层应用与存储介质独立开来，通过地址映射将NAND Flash 先擦后写的特性限制消除，后通过坏块管理、垃圾回收以及磨损均衡等功能配合，确保NAND Flash 的使用寿命，保证数据的安全。本文实现了一种优化的闪存转换层并在固态硬盘上进行实施部署，实现了固态硬盘的功能。

1 研究背景

1.1 NAND Flash

NAND Flash 最小的读写单位是页，擦除单位是块，每个块由多个页组成。每个页分为主区和备用区，主区用来存储用户的数据，备用区用户存储用户数据的ECC 校验码和闪存转换层的一些元数据信息。

NAND Flash 分为SLC、MLC[2]、TLC 以及3D NAND 等几种类型。这几种NAND Flash 都有共同的特点，块的擦除次数有限。其中，TLC 型NAND Flash 块擦除次数仅为1 000 次左右，所以闪存转换层会通过磨损均衡、垃圾回收以及坏块管理等功能显著的提升固态硬盘的使用寿命。

1.2 闪存转换层（FTL）

闪存转换层（FTL）主要功能是将NAND Flash抽象成块设备[3]和目前主流的磁盘设备操作方式进行兼容。闪存转换层既要保证读写的性能，也要保证NAND Flash的使用寿命，主要包含以下几个部分。

1.2.1 地址映射

地址映射负责将逻辑地址转换成实际的物理地址，对于NAND Flash 来说就是转换成物理页地址。根据映射粒度不同常用的地址映射算法有页映射、块映射和混合映射3 种。页映射的映射粒度是NAND Flash 的页，所以页映射表所占资源比较大，是该算法的主要缺点；块映射顾名思义就是映射粒度为块，优点是占用资源较小，但是在数据合并时会出现整块数据拷贝的问题，导致写入效率低下，典型代表是NFTL（NAND Flash Translation Layer）[4]；混合映射算法是对页映射和块映射的一种平衡，使得在资源占用尽量小的情况下达到符合设计的性能。

1.2.2 垃圾回收

随着用户的使用和更新，备用块被使用完成，这时必须触发垃圾回收以释放空块。垃圾回收策略是通过擦除包含无效数据的块来获得更多使用空间[5]。该操作对用户体验有着非常重要的影响，不当的垃圾回收可能会造成用户命令被阻塞而无法保证命令得到及时响应。

1.2.3 坏块管理

由于NAND Flash 的生产工艺特性，它不能保证所有存储空间在其生命周期内保持可用性，因此在NAND Flash 的生产和使用过程中会产生坏块。FTL 需要建立坏块表。该表是动态更新的查找表，可以识别所有NAND Flash 坏块，并将坏块信息添加到坏块列表中，并保证整个坏块列表得到不断维护和更新。

1.2.4 磨损均衡

在使用过程中存在用户数据和访问行为冷热不均的情况，导致NAND Flash 的某些物理块长期不被使用，而另一些物理块被频繁使用。随着使用时间的推移会出现某些块提前达到擦除次数而出现不稳定的情况，会影响整个NAND Flash 的使用寿命。为了解决这个问题，必须要采取某种策略使得对闪存的擦除操作尽可能均衡分布在整个存储介质上，这就是磨损均衡。

2 FTL 算法设计与实现

FTL 的主要功能是实现逻辑地址到NAND Flash的物理地址的转换。由于NAND Flash 的特点，所有块的生命周期如图1 所示。刚开始是一块空块，里面没有任何数据；在需要的时候被分配使用，写入数据成为有效数据块；数据被更新，由于不能直接更新，数据会被写到其他块上，这个块上的数据变为无效数据块；无效数据块被回收擦除掉，重新成为空闲块可以再次使用。

由于这些特性，不能将NAND Flash 所有块上都放上有效数据，必须有一部分块作为备用块，用来做为数据更新时的缓冲块，这部分块称为保留块。这是NAND Flash 提供的实际容量小于标称容量的原因。保留块的多少与FTL 的映射算法有关，所以不同的算法实现其有效容量会不相同。

图1 块生命周期变化

2.1 地址映射

固态盘中的映射管理机制是FTL 中非常重要的一个模块，直接影响实际固态盘的I/O 性能。目前的映射方式有页映射、块映射和混合映射几种。这些映射方式的基本单位即决定固态盘的固件程序能够操作的最小单元。粒度越大即操作的基本单位越小，其I/O 性能表现得越好。粒度越大，带来的问题是映射表越大，需要较大的SDRAM 存放映射表，所以需要一种相对最优的映射管理方式，既能保证映射机制提供较好的I/O 性能，又不能带来太大的开销。在FTL 设计中，涉及的地址映射算法是对性能和资源开销的一个折中处理，即在不影响性能的情况下，只消耗相当少一部分资源。

本文设计的FTL 中，地址映射采用的是页映射方式。页映射表是一种全相联模式，记录所有逻辑页到物理页的映射关系[6]，其性能是最好的。由于传统的页映射机制占用资源太多，本文为解决这个问题设计了一种优化算法。它不是所有的映射表项都存入SRAM 中，而是动态地根据工作负载载入或载出映射所需的表项。同时，它在NAND Flash介质上维护全盘的映射表的完整镜像，如图2 所示。将物理页分为data-pages 和translation-pages，其中data-pages 存放在I/O 中访问的真实数据，而translation-pages 则存放逻辑-物理的地址映射表。同理，data-BLOCKs 和translation-BLOCKs 则分别由这两种pages 组成。

图2 页映射框架

由于不是所有的表项都存储在SRAM 中，必然会存在部分映射表的载入和载出操作。映射的地址处理机制：如果对所要处理的I/O 请求，其所需的映射信息存在于SRAM 中的CMT（Cached Mapping Table），那么将直接用这个已存在的映射信息；如果该映射信息不存在SRAM 中，那么需要从NAND Flash 介质中取出，即需从Translation BLOCKS 中取出映射信息后载入CMT。另外，需要根据CMT 的工作状态和替换算法，将部分失效或不经常访问的映射信息载出，写入translations blocks 中。

2.2 垃圾回收

垃圾回收最初由John M[7]提出，分为主动垃圾回收和被动垃圾回收两种。被动垃圾回收是指在使用过程中因为保留块全部都被使用，必须回收一部分保留块以供使用。此时需要使用最快的方法进行垃圾回收，即选择有效页数最少的块，以保证拷贝数量最少，提高回收效率。主动垃圾回收一般是在空闲时，通过主动回收释放一些保留块，以提升后续写操作时的性能。这时垃圾回收是以能够将有效数据整理得更有序为准，需要考虑到数据的冷热等因素。

选用回收目标块时采用模糊策略。为了保证对计算资源及缓存资源最少占用时达到较好的效果，本文设计的算法对此进行了优化，将所有块按有效页数划分为不同级别，如图3 所示，可以根据回收的目标选择合适的目标块进行垃圾回收。

图3 有效页分级情况

L0～L3 链表均为双向链表，每次数据更新引起表项变化时，都将需要将目标块向双向链的头部移动。这样越靠近双向链的头部的块越是最近访问的块，其存储的数据可能是热数据；越靠近双向链尾部的块越是最长时间没访问，其存储的数据相对要冷一些。这样通过双向链的头尾可以表示一部分冷热数据的特征，作为垃圾回收时的选择参考因素之一。

2.3 坏块管理

初次使用NAND Flash 时，块擦除之前要读取坏块信息构建坏块表，否则将擦除初始化的固有坏块信息。

对NAND Flash 的写入、读取操作，必须首先查找坏块表，判断该块是否为坏块，避免在坏块上进行各种操作。同时，在读取和写入操作后，需要判断操作的状态，判断是否有新的坏块产生。若产生了坏块，则必须将该块数据翻新到新的块中，同步更新坏块表。为了达到该效果，坏块模块需要检测每次操作NAND Flash 时ECC 的错误状态。当ECC 错误的位数将要超过设定的门限值时，将该块信息加入到坏块表中，同时触发主动垃圾回收过程，将数据更新到新的块中。

2.4 磨损均衡

本文提出了一种磨损均衡的算法，主要遵从两个原则：物理块中存放不经常更新的数据；存放冷热数据的物理块要经常进行数据交换。

把NAND Flash 在逻辑上分成热池和冷池两部分，分别用来存放经常访问的数据和不经常访问的数据。用两个队列定位热数据和冷数据，队列按照它们已被擦除的次数进行排列。对于队列Q，函数H+(Q)和H-(Q)分别返回最大和最小列表头部的块。对于块B，EC(B)是指它的擦除次数。起初，块随机分配在两个池中，定义参数TH为擦除次数的阈值。TH越小，所有的块之间的使用就越均衡。

该算法主要包括3 个步骤：

（2）为了避免使热池中的数据变得不活跃或是冷池中的数据变得活跃，在一定时间之后检查表达式是否成立，如成立，则交换相应的块；

（3）由于可能有块进行之前的操作，因此要引入EEC（Effective Erase Cycle）表示经过第一步操作后的有效擦除次数，所以引入队列和，分别用来标志热池和冷池中的EEC属性。在一定擦除操作完成后，检查表达式如成立，交换队列中的块。

2.5 高速缓存

使用固态盘内的RAM 作数据传输的缓存，利用数据访问的时间和空间局部性原理，系统在一段时间内可能会对同一块数据进行反复的读写，而写缓存管理可以不用立即将新的数据写入NAND Flash而是推迟一段时间后再写。这不仅降低了写请求的响应时间，而且减少了固态盘读写的次数。此外，读写请求的分布还具有空间局部性，连续的多个请求可能合并成一笔读写操作，提高了固态盘操作的效率。

缓存的替换策略主要是决定哪些将从缓存中清除。缓存中最常用的有最近最少用（Least Recently Used，LRU）、使用频率最小（Least Frequently Used，LFU）等算法。基于对缓存空间划分的技术，在逻辑上，缓存包含一个数据块栈，最经使用的块压入栈顶，每个数据块有自己的引用数，即被调用的次数。当某块第一次调用缓存，其引用数初始值为0。由于缓存分为MRU（Most Recently Used）段、LRU 段和中间段，当缓存命中即数据块在缓存中时，引用数保持不变。也就是说，如果该块在MRU 段中再次或多次被调用时，引用数保持不变。只有当该块从LRU 段调入MRU 段时，引用数才加1。与LRU 算法不同的是，当缓存失败时，选择MRU 段以外应用数最小的数据块进行替换。如果可选块不止一块时，应用LRU 算法，淘汰其中最近最少使用的块。

3 试验结果与分析

本文实验平台是一块固态硬盘开发板，该开发板容量为512 GB，NAND 控制器具有4 个通道，可并行处理NAND 命令，SRAM 大小为1 MB，DDR 容量为512 MB，采用高速的SATA 接口和主机进行通信。

通过主机应用程序DiskGenius 工具可以看到固态硬盘被系统正常识别，如图4 所示，SSD512GB的磁盘即为测试目标磁盘。

用HD Tune Pro 工具对硬盘做性能测试，测试结果如图5 所示。

图4 被系统识别的固态硬盘

图5 磁盘性能测试结果

通过测试结果可以看出，顺序读写的性能比较高，但是随机读写的性能比较差。4 kB 的IOPS 表现不理想，主要是因为随机读写时缓存的命中率会变低，映射表更新次数过多导致性能损失严重，这是后续需要继续优化的地方。

4 结语

在基于NAND Flash 的存储系统内，往往因为有限的资源而无法采用页映射机制。本文对传统的页映射机制进行优化，将映射表分成两部分分别存储在RAM 中和NAND Flash 中，通过载入和载出实现映射表的存储和更新。同时，为了保证高速的I/O 响应，本文还设计了高速缓存模块，使得固态硬盘具有较好的顺序读写性能。本文设计的闪存转换层仍存在不足，读写性能和映射表的载入载出频率以及高速缓存的命中率有很大的关联，需要改进算法，以减少映射表的更新次数和提高缓存的命中率。