固态硬盘SSD内部管理算法研究综述

巴书法

摘要：固态硬盘英文缩写SSD（Solid State Drive）是一种以闪存（NAND Flash）为存储介质的存储设备。作为SSD核心技术之一，控制器内部管理算法FTL（Flash Translation Layer）负责地址映射，坏块管理，垃圾回收，磨损均衡等关键功能，管理算法的优劣直接影响SSD的性能和寿命。近年来，随着闪存（NAND Flash）技术的不断发展，FTL的算法也在不断演进，根据映射表的特点，将其划分页（Page）映射算法、块（Block）映射算法和页块混合映射算法。根据逻辑区域划分，可分为分区映射和全区映射，同时冷热数据分类存储也成为FTL的一个重要功能。该文介绍了近年来具有代表性的研究成果，并对于各类算法的优缺点以及在适配3D NAND所遇到的问题进行综述。为进一步设计更加完善的FTL算法提供指南。

关键词：固态存储; 闪存;冷热数据;地址映射; 垃圾回收; 磨损均衡

固态硬盘（SSD）是由控制器和闪存芯片（NAND）组成，利用闪存的区块存储特点进行读写操作，其凭借多项优点，如：响应快、带宽高、功耗低、工作温宽大，抗震性强，轻便等，广泛应用于数据中心，个人电脑，工控机，汽车电子，物联网等设备。随着超过100层3D NAND闪存的量产，SSD的容量变得越来越大，其单GB成本逐年降低，配合高速的SATA/PCIe接口，其性价比日益突出，SSD替代传统机械硬盘的趋势正在加速。

FTL是 SSD控制器的核心控制算法，其主要任务是管理逻辑地址到物理地址的映射，其次它还负责分离冷热数据，垃圾回收和磨损均衡等重要功能。由于闪存的操作方式为页（Page）写入，块（Block）擦除，在未擦除之前不允许覆盖写入，所以当SSD接受到主机的写入命令时，FTL负责将逻辑地址映射到对应的物理地址，并将用户数据写入到NAND闪存的有效页上，当NAND闪存完成编程（Program）后， FTL负责更新逻辑地址到物理地址的映射表。通过这种方式，SSD就能准确记录所有用户数据的准确物理位置。

FTL设计的合理性直接影响着SSD的性能和寿命，随着NAND制程以及SSD控制器硬件的不断改进，FTL的设计也在不断演进。本文对近年来FTL的主要研究结果以及经典FTL算法进行梳理，归纳，并对比各自的优缺点，同时结合3D NAND的最新特性，对设计下一代FTL所面临的问题进行分析与表述。

1 SSD相关基础理论知识

SSD是由控制器和一组NAND闪存芯片组成，其中控制器负责运行FTL，其为SSD的核心部件，内部由一个或者多个微处理器，NAND 闪存控制单元，ECC加解密模块以及负责数据传输的DMA组成，控制器通常支持多个通道并通过ONFI接口与外部的NAND闪存连接。

1.1闪存颗粒（NAND Flash）

1.1.1 NAND闪存的基本知识

闪存（NAND）是固态硬盘的主要存储介质，1989年首先由东芝提出NAND闪存的基础构架，它的基本存储单元为称为Cell。Cell是在晶闸管（MOSFET）的结构上添加了一层浮栅极用来捕获电子用来实现数据的存储。下图为NAND的Cell的结构和MOSFET的区别：

NAND闪存在写入数据的时候，通过往NAND的Cell单元注入不同数量的电荷量，Cell的导通的阈值电压Vt也会随之发生变化。通过这些不同Vt电压，就可以表示不同的数据。通俗的说，比如注入1库伦电荷之后电压为Vt=1V，充入2库伦的电荷之后电压为Vt=2V，充入3库伦的电荷之后电压为Vt=3V，充入4库伦的电荷之后电压为Vt=4V，我们就可以用1V表示00b，2V表示01b，3V表示10b，4V表示11b。NAND擦除的时候通过施加反向电压，将F/G中的捕获的电荷释放出去。

不同类型的NAND，其Cell单元存储比特数也不同，分为：

SLC NAND：一个Cell表示一个比特。

MLC NAND：一个Cell表示两个比特。

TLC NAND：一个Cell表示三个比特。

QLC NAND：一个Cell表示四个比特。

SLC NAND具有写入速度快，数据保持力强等优点，但容量比较低且价格比较高，一般适用于工业，航天，军工等特殊领域。MLC和TLC具有容量大，价格便宜，所以广泛应用于消费级固态存储设备上。随着NAND技术的不断进步，QLC NAND凭借其超大容量和极低的价格，逐渐在消费级产品被采用。

1.1.2 NAND闪存块组织结构和特点

NAND闪存的基本写入单位为页，每一个页由数据区（Data area）和冗余区（Spare area）组成，冗余区也叫做OOB（Out of Band）区域，它用来存储关键的元数据，数据区用来存储用户数据或者管理数据，设备在复位重新启动后，SSD固件会扫描元数据区域用来重建映射表或者恢复内部管理结构。元数据的存储通常分为紧邻存储和分立存储两种。NAND闪存的基本擦出单位为块（Block），一个物理块有多个页组成，通常为256，512或者1024个页。NAND闪存采用块擦除，页写入策略。为了提高NAND的并行操作速度，NAND通常都会将块分成不同的组，称为Plane。多个Plane能同时进行读写擦操作。

NAND操作具有以下特点：

①寫入单位为页，在块擦除之前不能进行重复写操作。

②块内必须按照页顺序写入，不能跳跃写入。

③擦除单位为块，块擦除会清空块内所有页的数据。

④随着块擦写次数的增加，数据保持能力会大大降低。

1.2固件地址映射算法

FTL最重要的工作就是完成逻辑地址到物理地址的映射。按照映射的粒度分类可以归为三类：

块（Block）映射算法：FTL的映射粒度为闪存的物理块，采用块映射算法最大的优点就是RAM占用量极低，同时拥有良好的顺序读写速度。它最大的缺点就是随机性能差，较高的写放大系数以及较低的垃圾回收效率。随着闪存的发展，物理块变得越来越大，现在单纯使用块映射的FTL如文献[1]已经很少采用。

页（Page）映射算法：FTL的映射粒度为页，此处的页大小可以为NAND的物理页大小的，也可以是4KB的数据单元。采用页映射的FTL需要为每一个页维护一条逻辑地址到物理地址的记录，比如采用4KB页映射，每一个4KB页需要4字节来记录逻辑位置到物理位置的映射。页映射算法具有良好的随机读写性能以及较低的写放大系数（WAF），缺点是内存占用量大。经典的采用页映射的FTL算法如文献[2][3]。

页块（Page/Block）混合映射算法：页块混合映射FTL将NAND物理块分成两个区域，数据区和缓存区，数据区采用块映射算法以减少映射表内存使用量，缓冲区采用页映射算法，它用来保存随机数据或者热数据。混合映射算法最大的优点就是具有良好的性能以及适中的内存使用率。但由于如果系统存在大量的随机写入，垃圾回收的效率会大大降低。文献[4][5]为典型的混合映射FTL算法。

2 经典FTL算法研究

本章将介绍几种FTL的经典算法，并分析各个算法的优缺点，为后续的研究打下基础。

2.1块映射的算法

Ban在文献[1]首先提出了针对NAND闪存设计的基于块的映射算法NFTL。它的基本思想是将磁盘的逻辑空间分成若干个逻辑块，每一个逻辑块映射到至少一个物理块，其中一个物理块称为主块（Primary Block），在主块中逻辑页在逻辑块中的偏移量跟物理页在物理块的偏移量相同，如果主机写入的邏辑地址之前已经写过，NFTL会重新申请一个物理块来保存新的数据，这个物理块叫做替换块（Replacement Block），替换块中的映射关系记录在替换块Page的OOB区域。这种映射算法只需要很少的RAM使用量来记录块映射关系。

上图是主机写入以下数据后的示意图：

LPN0～LPN5：A0～A5

LPN4：E1

LPN5：B1

块映射算法的优缺点如下：

优点：

①需要极少的RAM来保存块映射关系。

②算法实现简单，顺序读写性能突出。

缺点：

①随机读写效率低，性能差。

②读取性能差，最差情况需要扫描整个替换块。

③垃圾回收过多的Merge操作，导致写放大系数增大，NAND物理块损耗过快。

2.2页块的混合映射的算法

为了提高块映射算法的随机读写性能，并减少垃圾回收损耗。Kim提出了块页混合算法BAST文献[4]。Kim在块映射的基础上，增加了一个Log Buffer用来存储主机的写入数据， Log Buffer由固定数目的物理块组成，并使用页映射表来管理Log Buffer，为了加快读速度，BAST将页映射关系存储到RAM中。为了减少RAM的使用量BAST用块映射表来管理数据块。每一个逻辑块最多对应一个数据块和一个Log Buffer块。

当主机写入数据时BAST会根据要写入的LBA首先计算出其逻辑块号LBN，如果逻辑块有对应的Log Block，则将其写入到Log Block中，如果没有Log Block， BAST从Free Block中取出一个块作为Log Block，并将数据从页0开始写入到Log Block中。如果Log Block被写满或者Free Block Pool中的空闲块不足，则需要启动垃圾回收来释放被占用的物理块。垃圾回收将Data Blocks 和 Log Blocks的有效数据进行组合写入到一个新的Block中， 这个目标Block会转换为新的Data Block， 同时旧的Data Block和Log Block会被擦除放入到Free Block Pool。这在BAST称谓Merge操作。在随机写操作比较频繁的应用场景，会导致Log Block消耗过快，而且垃圾回收机制强迫进行Merge操作，导致Log Block空间利用率不足，严重影响系统的性能。为了解决这个问题，S.-W. Lee提出了全关联映射算法FAST文献[5]。所谓的全关联映射指的是所有的逻辑块共享Log Buffer。Log Block不在局限于特定的逻辑块。当主机写入数据时，数据先写入到Log Block中，然后通过垃圾回收转换为数据块。由于FAST的设计采用类似于CPU Cache的全关联映射策略，有效提高了Log Buffer的空间利用率。

页块混合映射算法的优缺点如下：

优点：

①对RAM资源要求不高，在有限的RAM资源情况下，由于Log Block采用页映射表记录，相比块映射算法随机写入性能得到明显改善。

②数据块采用块映射表记录，顺序读写性能突出。

缺点：

①如果随机写入频繁，由于Log Block的空间利用率低，其导致垃圾回收开销过大。

②垃圾回收过多的Merge操作，导致写放大系数增大。

2.3基于页映射的算法

A.Gupta提出了一种适用于NAND闪存的基于页的映射算法DFTL文献[3]。其成为当今SSD所应用最广泛的算法。

DFTL维护了全部逻辑页到物理页的映射表，并将页映射表保存在闪存的上，通过GTD进行映射表的追踪。当主机写入数据时，DFTL将数据按页写到数据块上，并将新的映射关系缓存在CMT上。CMT是在内存中开辟的临时缓冲区，当CMT写满以后，DFTL采用批量更新的算法将CMT中属于同一个GTD页的映射项一次更新到闪存上，从而减少系统的映射表更新消耗。DFTL的逻辑空间到物理空间的映射关系采用页映射表管理，逻辑页可以映射到任何物理页，有效提高了随机写入的性能，同时采用贪婪的垃圾回收机制，随着主机写入数据，当空闲块减少到一个设定的阈值后，垃圾回收启动并选中有效数据最少的数据块作为回收对象。DFTL将有效页搬移到一个新的数据块上，擦除旧的数据块。这种贪婪的垃圾回收机制配合页映射管理算法，使垃圾回收的效率大幅提高，有效避免了页块混合映射算法的Log Block空间利用率不足的问题。

在DFTL的基础上， 为了提高系统的健壮性，并缩减内存的使用量，DongZhe Ma提出的LazyFTL文献[4]，LazyFTL将用户数据分为三个区域，DBA，CBA和UBA。 DBA作为主存储区域用来存储已经完整写入的数据，UBA用来存储主机正在写入的热数据，CBA用来存储垃圾回收正在写入的冷数据。LazyFTL将全局映射表存储到MBA上，并通过GMD进行追踪。与DFTL相比，LazyFTL开辟了两个小区域CBA和UBA，其用来存储刚刚写入的数据，并使用UMT来缓存更新的映射表。LazyFTL通过Convert将Block N从CBA或者UBA区域转化到DBA区域，同时UMT中指向Block N的所有映射表被写入到MBA上。LazyFTL有效减少了设备掉电后的数据恢复时间。

页映射算法的优缺点如下：

优点：

①由于不需要Log Buffer，所有数据直接写到数据块中，不需要Merge操作，垃圾回收效率大幅提高。

②全部数据采用页映射关系，逻辑页可以映射到任何物理页上，系统响应时间快，性能最为突出。

③由于没有不必要Merge操作，写放大系数WAF得到有效控制，从而延长了SSD的使用寿命。

缺点：

①由于采用页映射关系，映射表通常是用户容量的千分之一。其会占用大量NAND闪存块用来存储全局映射表，导致用户可用空间减小。

②需要大量内存资源来缓存映射表以便加速系统的访问。

③由于取消了逻辑块和数据块的对应关系，逻辑页可以映射表任意物理页，当主机覆盖写大范围的逻辑空间时，物理块不能快速释放，其导致性能降低。

3 FTL算法面临的新问题和挑战

随着SSD的使用越来越普及，不同的应用场景对SSD的特性也有不同的要求，其对FTL的设计提出了新的挑战。同时随着NAND制程的演进以及最新纠错算法LDPC的使用。 FTL的设计也要针对这些变化做出相应调整。

（1）NAND閃存的Paired Page 问题

NAND Paired Page问题是指当一个NAND Cell的低页（LSB）已经编程完毕后，如果在编程高页（MSB）的数据时，如果发生掉电事件，其LSB中已经成功写入的数据也会被破坏掉。对于FTL的设计，如果没有考虑此问题，主机会看到之前已经写入成功的数据丢失掉，这通常不可接受的，会导致严重的数据丢失问题。

（2）先进制程闪存需要更复杂的出错处理

随着NAND闪存制程的发展，从一个Cell存储1个比特的SLC，到一个Cell存储2个比特的MLC，再到存储3个比特的TLC和存储4个比特的QLC，单位面积数据密度越来越大，其错误率也越来越高。

同时错误的类型也越来越复杂，如P/E cycle错误 Read Disturb错误等等，需要更复杂的FTL算法来处理这些错误，从而保证数据的正确性。

（3）FTL映射表需要更多的RAM资源

基于页的映射算法拥有良好的性能，以及高效的垃圾回收效率，其已经成为主流FTL映射算法，但是随着SSD容量的增大，页映射表所需要的RAM资源会随之增大，比如：4TB的SSD，如果4KB作为一个映射单元，4B来记录一条映射关系，全局映射表需要4GB的存储空间，如果CMT中只缓冲其中的千分之一的映射表，也需要近4MB的RAM空间，这对于很多控制器的设计来说是不可接受的。

（4）全局映射表存储块的磨损问题

FTL通常需要将全局映射表存储到NAND闪存的管理块上，由于控制器内部将部分更新的映射表缓存在CMT中，当SSD工作在一个随机写负载很重的环境中时，CMT中缓存的更新后的映射表项（Dirty Entry）会不断地被刷新到存储GMT的闪存块中，一次更新至少需要读一页映射表，并写入一页映射表。所以GMT物理块的磨损速度是用户数据的10倍甚至更多。如何减少全局映射表存储块的磨损是设计下一代FTL应该考虑的重要内容之一。

4 总结与展望

SSD替代传统HDD的速度正在加快，越来越多的SSD被用在数据中心，云计算，IoT设备，工控，汽车以及航空等领域。随着5G、AI等先进技术的快速发展，对存储需求不仅仅表现在大容量上，不同应用场景产生了多元化的需求，比如性能、功耗、散热、耐久度等方面，这对FTL的设计提出了新的挑战。本文对FTL的功能以及闪存的特性做了基本介绍，并分析了近些年几种经典FTL的实现方法以及优缺点，同时结合笔者的经验对将来FTL的设计所面临的挑战和问题提出了一些浅显的分析，希望对SSD FTL的设计提供一定的参考意义。

参考文献：

[1] A. Ban and R. Hasharon. Flash File System Optimized for Page-mode Flash Technologies， Aug.1999. United States Patent No. 5，937，425.

[2] A. Gupta， Y. Kim， and B. Urgaonkar. DFTL： A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings. ACM SIGARCH Computer Architecture News. Volume 37. Issue 1. March 2009. Pages 229–240.

[3] Dongzhe Ma， Jianhua Feng， and Guoliang Li. LazyFTL： A page-level flash translation layer optimized for NAND flash memory. SIGMOD ‘11： Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. June 2011. Pages 1–12

[4] Jesung Kim， Jong Min Kim， Sam H. Noh， et al. 2002. A space-efficient flash translation layer for compact flash systems. IEEE Transactions on Consumer Electronics. Volume 48. Issue 2. May 2002. Pages 366–375.

[5] S. Lee， D. Park， T. Chung， D. Lee， S. Park， and H. Song. A Log Buffer based Flash Translation Layer Using Fully Associative Sector Translation. ACM Transactions on Embedded Computing Systems. Volume 6. Issue 3. July 2007. Pages 18–es.