第3章 闪存转换层

《闪存数据库概念与技术》

厦门大学数据库实验室  林子雨  编著

（本网页是第3章内容，全书内容请点击这里访问本书官网，官网提供本书整本电子书PDF下载）

第3章 闪存转换层

闪存转换层（Flash Translation Layer），简称FTL，位于文件系统与闪存之间，为文件系统提供了虚拟的磁盘，可以使得固态盘表现出类似磁盘的行为，从而使得面向磁盘开发的应用程序（比如数据库应用）不需要做任何修改，就可以直接运行在以固态盘作为存储介质的存储系统上。

理解FTL机制是设计出性能优良的闪存数据库的关键，根据是否采用FTL机制以及采用什么样的FTL机制，闪存数据库在设计上就会衍生出许多不同的技术路线，比如，设计面向DBMS的FTL、采用FTL并修改面向磁盘的DBMS的部分模块和抛弃FTL并修改面向磁盘的DBMS的部分模块等等。因此，在介绍闪存数据库之前，有必要首先介绍FTL机制的概念和相关方法。

本章将详细介绍FTL的基本功能，并且重点阐述FTL的多种映射机制。

3.1   FTL的功能

FTL的基本功能包括地址映射、垃圾回收、磨损均衡和断电恢复等，本节将分别给予简要介绍。

3.1.1     功能概述

NAND闪存的读写特性和磁盘有很大区别，比如NAND闪存存在“写前擦除”的限定，闪存中擦除操作的粒度要比写操作的粒度大许多等等，那么，类似固态盘的闪存设备是如何做到表现出类似磁盘的行为的呢？这个功能是通过FTL（Flash Translation Layer）实现的。

FTL位于文件系统与闪存之间（如图[FTL](a)所示[ChoudhuriG07]），为文件系统提供了虚拟的磁盘，文件系统可以像使用磁盘一样来使用闪存。FTL的实现方式主要有两种：（1）由宿主系统直接在闪存上以软件方式实现FTL，比如存储棒（Memory Stick）就采用了这种方式，这种方式可以使得宿主系统能够根据应用特点优化存储管理策略，从而获得更好的性能；（2）对于许多基于闪存的设备而言（比如闪存固态盘），FTL会被设计成一个控制器（如图[FTL](b)所示），封装在设备里面，控制器包含一个低端的处理器或微控制器以及少量的SRAM。如图[FTL](c)所示，控制器主要负责完成两种功能：（1）把来自文件系统的读写请求，转换成针对闪存的读写请求，这里需要进行地址映射；（2）进行垃圾回收。

图[FTL] FTL机制原理

具体而言，作为固态盘的最核心的组件，FTL的主要功能是提供逻辑地址到物理地址的映射、断电恢复、垃圾回收和磨损均衡。FTL机制通过提供上述功能，隐藏了闪存的特性，提供了一个虚拟的磁盘，使得上层应用不需要任何修改就可以直接使用基于闪存的存储设备。但是，这也增加了额外的代价，比如，FTL为了对更新（重写）操作隐藏“写前擦除”的限定，提供了地址映射功能，这就需要消耗更多的存储空间来维护地址映射表，而且需要及时准备好闪存中可用的空闲块，一般而言，FTL机制会在闪存中保留一定数量的日志块作为更新（重写）操作的临时存储。同样，垃圾回收和断电恢复机制也都涉及一定的代价。

3.1.2     地址映射

FTL扮演的一个主要角色就是提供LBA（逻辑块地址）到PBA（物理块地址）的映射，这个功能是由FTL映射表来实现的。FTL映射表需要维护两种类型的数据结构：一个是直接的映射（即从LBA到PBA的映射），另一个是反向映射，用来在失败恢复的时候重新构建得到直接映射。也就是说，直接映射是从逻辑块地址到物理块地址的映射，而反向映射则是物理块地址到逻辑块地址的映射。反向映射是存储在闪存上的，直接映射也是存储在闪存上，并且有一部分会被放入RAM内存用来提高地址映射的查找速度。如果访问请求所需要的那部分直接映射不在RAM中，就必须在需要的时候把它从闪存交换到RAM中。对于采用页级别映射的FTL机制而言，在地址映射表中，与一个逻辑页s对应的映射表条目T[s]的值为<b₀,p₀>，其中，b₀表示闪存中的物理块号，p₀表示闪存中的物理页号，物理页p₀的OOB区域中会同时保存逻辑页s的逻辑页号和页面有效标志位。

图[FTL-address-mapping]给出了FTL的地址映射的一个实例。从图中可以看出，在页映射表中，左边一列表示了LPN（Logical Page Number：逻辑页面编号），右边一列表示了<PBN,PPN>，其中，PBN（Physical Block Number）表示物理块编号，PPN(Physical Page Number)表示物理页编号。地址映射表中的一个映射条目{0,<0,1>}，表示LPN为0的逻辑页被映射到闪存中的第0块（PBN=0）中的第1页（PPN=1）。有一个逻辑页（LPN=3），原来的旧值是127（图中用虚线划掉表示是旧值），原来的映射条目是{3,<0,2>}（图中用虚线划掉表示是旧的映射条目内容），表示该页被映射到闪存中的第0块第2页。当这个页（LPN=3）发生了更新以后，新的值是299，闪存采用异地更新，因此，需要把新的值299写入到新的空闲页中，这里假设新值299被写入到第1块（PBN=1）第7页（LPN=7）中，然后去修改地址映射表，把LPN=3对应的映射条目，由{3,<0,2>}更新成为{3,<1,7>}。

图[FTL-address-mapping] FTL的地址映射

每次设备重新启动时，都会扫描闪存物理块中的信息，读取OOB区域中的数据，重新构建FTL映射表。因为逻辑页会被不断更新，因此，逻辑页到物理页的映射不是固定不变的，也需要不断更新，这就导致映射表是不断变化的。当逻辑页s发生更新时，FTL会把更新后的逻辑页写入到新的闪存物理页p₁（假设p₁属于闪存物理块b₁），并把映射条目T[s]的值修改为<b₁,p₁>。FTL接受各种读写数据请求以后，通过查找映射表，就可以把被请求数据的逻辑地址映射转换成这些数据在闪存中的物理存储地址。这样，FTL就可以把写操作引导到闪存中那些已经擦除过的空闲页面，从而对上层应用隐藏了闪存的“写前擦除”的限制，也大大减少了写操作之前的擦除操作的次数，提升了闪存性能。地址映射的方式包括页级别映射、块级别映射和混合映射，每种映射方法都有不同的优缺点。为了加快逻辑地址到物理地址的映射，在系统运行过程中，FTL映射表通常都会被读取到SRAM中。但是，FTL映射表通常较大，往往无法一次性全部放入SRAM。比如，对于1GB的NAND闪存而言，如果采用页级别映射，每个映射表条目为8字节，那么，FTL映射表的大小就是1GB/512B*8=16MB。

闪存设备每次启动时，都会扫描闪存物理块中的信息，读取OOB区域中的数据，重新构建FTL映射表。在早期闪存容量较小时，这种地址映射表的重构过程不会影响闪存设备的性能。但是，随着闪存容量的不断增大，扫描整个闪存空间的时间开销越来越大，从而使得地址映射表的重构过程时间越来越长。为了加速闪存设备的启动过程，可以采用一些改进策略，主要包括[Xiang09]：

（1）快照技术：一旦系统关闭，就把SRAM中的地址映射信息的快照写入闪存，为了能够在系统启动时能够迅速读取快照的内容来重构地址映射表，还需要在闪存中专门开辟一个区域来存储快照的存储地址；当系统正常关闭时，这种方式可以明显提高系统重启的速度，但是，当系统发生故障后重新启动时，为了保证地址映射表的正确构建，仍然需要重新扫描整个闪存物理空间。

（2）日志技术：基于日志的技术可以提高系统故障时的地址映射表重构速度，在该技术中，任何针对SRAM中的地址映射信息的修改，都会导致相应地生成日志记录来记录这些修改，当日志记录的数量累积到一定程度的时候，就可以批量写入到闪存的专门区域。当系统正常关闭后启动时，就可以直接到闪存中为日志存储专门开辟的区域去读取日志信息，完成地址映射表的重构。当系统发生故障后重启时，地址映射表的重构需要扫描两个方面的内容，即日志区域和一部分闪存物理空间。基于日志的技术，可以有效提高系统发生故障后的重启速度，因为，它不需要扫描整个闪存物理空间，而只需要扫描一部分闪存物理空间和日志区域。不过需要指出的是，虽然只需要扫描一部分闪存物理空间，但是，扫描的工作量仍然和闪存中的数据量成正比，当数据量较大时，扫描的时间开销也会相应增加。

这里还需要进一步指出的是，把闪存存储设备上的块以线性方式进行映射，可能会带来副作用，即导致不同闪存块之间的不均衡磨损。某些块会被较多地执行擦除操作，另一些块则可能会被较少地执行擦除操作。被频繁擦写的块，会很快到达擦除次数上限，成为坏块，导致整个闪存设备访问速度较慢或者寿命缩短。因此，必须设计相应的“磨损均衡”策略。

3.1.3     垃圾回收

闪存采用“异地更新”的方式，当对某个闪存页面进行更新时，只需要把新数据写入到一个新的“空闲块”（已经擦除过的块）中，并通过更新元数据，把原来的物理页面设置为“无效”。这样，新数据可以快速写入到新块中，不会涉及代价高昂的擦除操作。但是，闪存的空间是有限的，可用的空闲块的数量也是有限的，随着系统的运行，闪存中的无效页的数量会越来越多，空闲页就变得越来越少，当空闲块消耗到一定程序时，FTL就必须启动垃圾回收过程，回收那些处于无效状态的页，对一些块执行擦除操作从而生成可用的空闲块。垃圾回收结束后，需要在适当的时机更新FTL映射表。

如果一个块只包含有效页，则垃圾回收过程可以不用考虑这个块。垃圾回收过程主要针对两种情形：第一，块中全部是无效页；第二，块中有一部分是有效页，有一部分是无效页。如果块中只包含无效页，那么，只要简单执行擦除操作即可，实时上，由于异地更新，上面的第二种情形更加常见。也就是说，如果在页上执行更新，那么，在任何时间点，闪存的擦除块往往会同时包含有效页和无效页。如果一个擦除块包含了有效页，那么，执行擦除操作可以有两种选择：（1）把擦除块b中的有效页首先拷贝到内存中，对该块b执行擦除操作，然后再把内存中的有效页回写到已经擦除过的这个块b中；（2）把擦除块b中的有效页直接拷贝到其他具有空闲页的块中，然后对块b执行擦除操作。

对于第一种选择，如果擦除块b中的有效页被拷贝到内存中、并且已经对块b执行了擦除操作以后，在把内存中的这些有效页再次拷贝回块b之前，发生了系统故障（比如断电），那么，这些有效页就会丢失，无法恢复。因此，为了保证数据库的一致性，通常会在闪存数据库中使用第二种选择。由于第二种选择需要额外的空闲块来放置有效页，因此，执行垃圾回收操作时，必须保证闪存中还有一定数量的空闲块。

对于第二种选择，在擦除操作执行之前，必须把这些有效页拷贝到闪存的其他位置。对于一个轻度负载的设备而言，这种额外的拷贝开销可以忽略不计。但是，在一个过载的设备上，需要大量的被擦除过的可用擦除块，这时这种开销就必须被考虑进来。对于擦除块的回收而言，一个最好的情形是：在擦除时刻，擦除单元中的所有页都是无效的。当数据访问模式具有高度局部性时，这种情况有可能发生，比如，当一个文件被一页一页地顺序更新。在这种情况下，每个页写（page-write）操作，会引起大约P/E个擦除操作，其中，P是页的大小，E是擦除单元的大小。对于擦除单元回收而言，一个最坏的情形是：所有待回收的擦除单元中都只包含一个无效页。当设备快满、数据访问模式分散在不同的擦除单元中时，就有可能发生这种情况。在这种情况下，几乎每个页写操作，都会引起一个擦除操作。在最好和最差的情形之间，还存在许多中间情况，因此，如果仅仅给定页写操作的频率，是无法准确判断擦除操作的频率的。这时，就需要同时考虑更多的关于工作负载的特性信息。

3.1.4     磨损均衡

一个闪存块被擦除的次数是有限制的，通常可以擦除1万到10万次[AgrawalPWDMP08]，一旦超过这个限定次数，闪存就会变得不稳定甚至损坏，会引起频繁的数据读写错误。一般而言，一旦某个块的擦除次数达到预定的门槛，厂商为了保证产品存储数据的安全性，都会把该块设置为“无效”，即使这个块还可以继续使用。因此，为了最大程度地延长固态盘的寿命，应该尽量延迟第一个损坏块的到来时间，这就需要有效的磨损均衡策略[GalT05][JungCJKL07]，即让擦除操作均匀地分布在不同的闪存块上，而不让某一部分块被过多地执行擦除操作。从设备的寿命来说，如果特定的算法减少了擦除次数f倍，设备的预期寿命在理论上就会增加f倍。典型的磨损均衡策略主要包括[Xiang09]：（1）基于阈值的控制方法[LofgrenNT03]：当块之间的擦除次数差距超过事先设定的阈值时，就启动回收过程，收回擦除次数最少的闪存块，从而实现更好的磨损均衡，这种做法的代价是，可能会在一定程度上降低垃圾回收的效率；（2）移动数据页的方法[KimL99]：在各擦除块之间周期性地移动数据页，避免一些具有较低更新频率的块的擦除次数过低，从而使得不同块之间具有比较均衡的擦除次数；（3）基于双队列的损耗均匀控制方法[Chang07]：当某个块的擦除次数过多时，就把冷数据（很少被访问的数据）存储在该块中，由于冷数据的访问频率很低，因此，就可以降低该块在未来一段时间内的擦除频率。

3.1.5     断电恢复

一方面，固态盘中通常都会配置少量易失的SRAM，用来存储地址映射表，加快逻辑地址到物理地址的转换过程，提高请求响应速度。但是，当发生断电的时候，SRAM中的信息会立即丢失。另一方面，闪存存在擦除操作，这不仅降低了闪存性能，还可能引起数据一致性问题。因为，在对某个块执行擦除操作时，需要把该块中有效的数据复制出来，然后写入到其他新块中，但是，如果这个过程发生断电，就有可能发生数据丢失，对于一些掌上电子产品而言，发生这种情形的概率并不小。此外，当闪存块的大小和系统所采用的块大小不同时，断电故障也可能出现副作用。假设闪存块大小为128KB，存储系统使用4KB大小的块，为了把4KB的数据更新到128KB的闪存块中，就需要首先把闪存块中的128KB数据全部拷贝到内存中，在内存中完成4KB数据的更新，然后，再把更新后的128KB数据写入到闪存。如果在内存更新的过程中发生了断电，那么，内存中的数据就会全部丢失。因此，FTL必须设计相应的断电恢复机制。

3.2   FTL的映射机制

固态盘的硬件设计细节（尤其是FTL机制），通常是生产商的商业机密，不会对外公开。但是，在学术界，研究人员已经提出了许多FTL机制[ChungPPLLS06][LeePCLPS07] [KimKNMC02] [KangJKL06]，其中，地址映射方法是研究的核心内容。

根据映射单元的粒度，现有的FTL机制可以分成四大类：页级别、块级别、混合和变长映射：

• 页级别的FTL机制：比如LazyFTL[MaFL11]、DFTL[GuptaKU09]；
• 块级别的FTL机制：比如文献[ChoudhuriG07]中的方法；
• 混合FTL机制：比如LAST[LeeSKK08]、BAST[KimKNMC02] 、A-SAST (Adaptive SAST) [KooS09]、 HFTL[LeeYL09]、SAST[LeePCLPS07]、SuperBlock FTL[KangJKL06]和文献 [ChungPPLLS06][KangJKL06]中的方法；
• 变长映射机制：比如文献[ChangK04]中的方法。

3.2.1     页级别的FTL机制

本节介绍页级别的FTL机制的基本原理，并介绍典型的相关研究。

3.2.1.1      机制概述

在采用页级别的FTL机制[KawaguchiNM95]中，请求的逻辑页面可以被映射到闪存空间中的任何物理页面，因此，这种机制非常灵活，而且具有很高的闪存页面利用率。图[FTL-page-mapping]给出了页级别映射示意图，为了简化问题描述，这里省略了块号，实际上，当每个块中所包含的页数确定以后，可以很容易根据页号计算出块号，比如，如果每个块包含4个页，那么，逻辑页0,1,2,3就在第0块中，逻辑页4,5,6,7就在第2块中，逻辑页i就在第i/4块中，其中，i表示页号，i/4表示整除操作。从图中可以看出，对于一个逻辑页i（即逻辑页号LPN为i）而言，可以在页映射表中找到与该页对应的映射条目，映射条目<逻辑页号i,逻辑页号k>就表示逻辑页i被映射到物理页k上。

图[FTL-page-mapping] 页级别映射示意图

对于包含很多小数据量的写操作而言，这种细粒度的地址映射方法是灵活高效的，但是，它也存在明显的缺陷，就是页面映射表会很大，导致映射表无法全部放入SRAM。例如，一个16GB的闪存需要大约32MB的SRAM空间，来存储一个页级别的映射表。在固态盘产品中，通常会设计一个较小容量的SRAM，用来存储FTL的映射表，SRAM的访问速度要比闪存快许多，把映射表存放到SRAM中可以大大提高页面映射过程的速度，从而提高固态盘的读写速度。但是，SRAM的价格要比闪存贵一个数量级，因此，固态盘中配备的SRAM的容量通常很有限。而闪存的容量正随着技术进步不断增加，让固态盘中的SRAM的容量也随着闪存容量的增加而保持线性增加，是不经济也不现实的。

一旦页面映射表太大，无法一次性全部放入SRAM，就会严重影响固态盘的读写速度。因为，只有一部分映射表条目可以放入SRAM，其他映射表条目必须保存到闪存空间中。当来自系统的数据读取请求到达时，如果被请求的逻辑页面编号恰好已经在SRAM的映射表中，就可以直接根据逻辑页面到物理页面的映射，找到数据在闪存中的物理存储位置后读取数据；但是，如果被请求的逻辑页面编号不在SRAM的映射表中，FTL机制就必须到闪存空间中找到相应的映射表条目，读取后获得逻辑页面对应的物理页面地址，然后去该物理地址读取数据。为了获得最好的性能，可能还需要采用合适的缓存替换策略，来决定是否用刚才访问过的映射表条目来替换SRAM中的映射表条目，这就带来了额外的开销。

3.2.1.2      典型研究

第一个页级别FTL机制是由Ban[Ban95]在1995年提出的，同时申请了专利，并且在几年后被PCMCIA采纳为NOR闪存的标准[Intel98]。这里需要指出的是，目前的很多FTL机制都被申请了专利，不仅美国如此，在其他大多数欧洲和亚洲国家也都是如此。但是，Ban提出的页级别FTL机制，是针对NOR闪存的，无法直接应用到NAND闪存上，因为，NOR闪存是以字节为单位进行读写操作，而NAND闪存则只能以页为单位进行读写操作。

对于一个页级别的映射机制而言，它是很难在NAND类型的闪存上布置的，因为，它们只能以页为单位进行读写操作。只要映射表的任何部分发生修改，就需要被立即写入到闪存，这会严重影响性能。为了降低对性能的影响，一种可能的处理方式是可以考虑把脏数据暂时保存在SRAM中，只有当它将被交换出去的时候，才把它写入闪存。但是，这样做就会带来丢失关键信息的风险，可能会使系统处于不一致的状态，因为，SRAM是易失性存储器，一旦断电就会丢失全部信息。为了解决这个问题，文献[MaFL11]提出了LazyFTL，这种机制会在闪存中保留两个小区域，并且采用惰性方式对页级别的映射表进行更新，即经过一段时间满足特定条件时才进行更新，这样就有效减少了更新映射表的次数，降低了对性能的影响。图[LazyFTL]显示了LazyFTL机制的体系结构，从中可以看出，LazyFTL把整个闪存划分成四个区域：数据块区域（DBA）、映射块区域（MBA）、冷块区域（CBA）和更新块区域（UBA）。除了MBA以外，所有分区都存放用户数据。

图[LazyFTL] LazyFTL机制

在LazyFTL机制中，DBA中的页面是通过页级别的映射表进行跟踪的，整个映射表被称为全局映射表GMT（Global Mapping Table）。GMT是以页的方式组织，并且存储在MBA中。在SRAM中会开辟一块小的缓存，它采用LRU或者类似的算法进行缓存管理，从而可以为GMT中被频繁访问的部分提供快速引用。SRAM中存储的另外一个表被称为全局映射目录GMD（Global Mapping Directory），它记录了GMT的所有有效映射页的物理地址。CBA被用来容纳冷块，UBA被用来容纳更新块。

LazyFTL和原来的页级别的FTL机制[Ban95]的主要区别在于，LazyFTL保留了两个小分区，即CBA和UBA，用来延迟对GMT的更新操作，这些更新操作是由写请求和无效页移动导致的。和整个闪存的容量比起来，CBA和UBA是很小的。此外，LazyFTL会在CBA和UBA这两个区域之上，构建另外一个页级别的映射表——更新映射表UMT（Updating Mapping Table）。UMT可以被实现成一个哈希表，或者一个二叉搜索树，从而支持高效的插入、删除和修改。UMT中的条目的数量是很小的，因此，这些操作不会带来多少额外的开销。由于UMT是保存在SRAM中的，因此，CBA和UBA不能太大，这就意味着，CBA和UBA总会出现写满的情形，这时就需要执行一个转换操作，在所有CBA或者UBA中已经填满的块中，选择一个转换代价最小的块作为牺牲品，然后把它转换成正常的DBA。

UBA中的一个块，被称为当前更新块CUB，是用来处理写请求的。当一个CUB被写满时，另外一个空闲块会被分配成为新的CUB。类似地，在CBA中，会有一个当前的冷块CCB，用来处理移动的数据页。事实上，LazyFTL把CBA中填满的冷块和UBA中填满的更新块这二者进行同等对待和处理。换句话说，CBA和UBA的相对大小是可以进行动态调节的。如果热数据的比例上升，UBA就会扩展。如果空间利用率增加，CCB就会比CUB更快地被填满，这样，CBA就会扩大。通过这种方式，LazyFTL就可以根据访问机制的变化而动态自我调整。

3.2.2     块级别的FTL机制

3.2.2.1      机制概述

对于块级别的FTL而言，一个逻辑页面编号通常首先被分解成一个逻辑块编号和一个块内偏移量，然后，只需要把这个逻辑块编号转换成一个物理块编号，块内偏移量是不变的，最后，采用一些搜索算法来寻找目标页。图[FTL-block-mapping]给出块级别地址映射示意图，对于一个逻辑页i而言，首先需要计算得到该页的逻辑块号j和块内偏移量（假设为1），然后，到块映射表中，找到相应的映射条目<逻辑块号j，物理块号m>，表示逻辑块j被映射到物理块m上，接着到物理块m中找到块内偏移量为1的物理页k，因此，逻辑页i最终被映射到物理页k上。

图[FTL-block-mapping] 块级别地址映射示意图

可以看出，这种方法和传统的页式虚拟内存中的地址映射机制[SilberschatzC98]是类似的。块级别映射机制的优点是，映射表的规模要比页级别的FTL机制小很多，很容易放入到SRAM中，比如一个16GB的闪存只需要大约512KB大小的映射表；此外，小规模的映射表也降低了转换代价和能耗，很适合应用在掌上电子产品中。此外，块级别映射表的大小，不会像页级别映射表那样随着闪存容量的增加而线性增加，因为，更高存储容量的闪存一般也会采用更大尺寸的块。但是，由于块内的逻辑页码偏移量是固定的，因此，对于一个给定的逻辑页，它在物理块中只能位于具有相同偏移量的、某个特定的物理页内，这就会导致为一个逻辑页在物理块中找到合适的物理页的概率降低，由此将产生两个问题：（1）空间浪费；（2）垃圾回收的代价增加[GuptaKU09]。此外，这种机制的读、修改和写操作的开销都很大，即使只是对块的一部分进行更新操作的时候，也需要很大的代价。比如，假设在原来的地址映射表中，有一个逻辑块L被映射到闪存中的物理块P_A上面，一个写操作打算更新逻辑块L中的某个页p，并假设页p在块L内的块内偏移量是d。为了完成这个更新操作，FTL机制会更改逻辑块到物理块的映射，把逻辑块L重新映射到闪存中新的空闲物理块P_B上面，然后，在物理块P_B中找到具有相同的块内偏移量d的一个页q，在页q上面执行更新操作。与此同时，块P_A中其他页都要被复制到这个新的块P_B中。可以看出，块级别的FTL机制的更新操作代价是较大的。因此，和采用其他映射方法的FTL机制相比，块级别FTL机制的性能是很有限的。

总的来说，块级别映射大大减少了映射表的大小，但是，它的挑战在于如何最小化在一个块内部寻找一个页的开销。因此，块映射不支持随机写操作，也不能支持高效的更新操作。

3.2.2.2      相关研究

         为了消除块级别FTL机制中更新操作的昂贵代价，文献[Ban95][MTD]提出了NFTL机制，该机制采用了替换块的策略，采用NFTL这个名称，是因为这种FTL机制是为NAND类型的闪存设计的。Ban在1999年为两种块级别的NFTL机制申请了专利[ChoudhuriG07]，即NFTL-1和NFTL-N。 NFTL-1要求每个闪存页都存在OOB区域，而NFTL-N则是针对那些没有OOB区域的闪存。

3.2.2.2.1        NFTL-1机制

在NFTL-1机制中，一个逻辑页号（LPN）会被分成两个部分：逻辑块号（LBN）和块内页偏移量，LBN和LPN都从0开始编号，块内第1个页的偏移量为0。比如，假设闪存有4个块，每个块包含4个页。对于LPN=5的页而言，它的LBN为1，块内页偏移量为1。

当一个逻辑块第一次执行写操作时，系统会为这个逻辑块第一次被分配一个物理块，这个物理块被称为“主块”。逻辑块中的每个逻辑页的第一次写操作，就在与该逻辑块对应的主块中执行，逻辑页会被写入到主块相应的位置，即要求一个逻辑页在逻辑块中的块内偏移量应该和它对应的物理页在物理块中的块内偏移量相同。当一个页被重写（overwritten）的时候，NFTL-1首先为相关的逻辑块分配一个替换块（如果还没有分配到替换块的话），然后从替换块的第一个可用空闲页位置开始，按照顺序写入重写页。由于页面是以异地（out-of-place）方式写入替换块，因此，NFTL-1需要在替换块中以反向的顺序查找所有OOB区域，从而找到一个被请求页的最新版本。需要指出的是，在NAND闪存中，OOB区域采用了不同的寻址算法，它专门为快速引用进行了优化处理，因此，这个搜索过程的开销较低。

这里给出一个实例解释NFTL-1机制的工作过程（如图[NFTL-1]所示）。假设闪存有4个块，每个块包含4个页。现在有一个操作序列op₁,op₂,op₃,op₄,op₅,op₆，每个操作的格式为“操作类型+LPN(逻辑页号)+数据”。比如，op₁表示把数据A写入到LPN=5的页面中。这个操作序列的执行过程如下：

（1）操作op₁首先到达，由于每个块的大小为4，因此，LPN=5的页所属的块的LBN(逻辑块号)为1。系统查找映射表，发现不存在LBN=1对应的映射条目，因此，立即为LBN=1的逻辑块分配一个物理块，物理块的PBN（物理块编号）为b₀，并把该条映射写入到映射表。物理块b0是逻辑块1的“主块”，op₁的写操作针对的页的LPN是5，该页在逻辑块内的页面偏移量是1（即块中的第2个页），NFTL-1要求把数据写入到主块中具有相同块内偏移量的物理页上，因此，op₁的数据A会被写入到物理块b₀的第2个页中，并在该页的OOB区域中写入LPN的值（即5），同时把页面有效标志位设置为“有效”。

（2）当op₂到达以后，系统根据LPN=5计算得到其所属的逻辑块的LBN是1，查找映射表，发现已经存在LBN=1对应的映射条目，读取映射条目，找到LBN=1的逻辑块对应的物理块为b₀，然后，根据块内偏移量，找到物理块b₀内的第2个页，读取该页的OOB区域，发现该页的有效标志位已经被设置，说明已经被写入数据，由此可以判定op₂操作是针对同一个页的更新操作。这时，系统会为LBN=1的逻辑块分配一个物理块b₁，这个物理块被称为“替换块”，主块b₀中会记录与之关联的替换块b₁的信息；然后，系统把op₂操作的数据A₁写入到替换块b₁的第一个空闲页上，由于这时块b₁的所有页都为空闲页，所以数据A₁会被写入到块b₁中的第1个页（该页在块b₁内的块内偏移量为0）。

（3）依此类推，op₃到达以后，由于NFTL-1要求把数据写入到主块中具有相同块内偏移量的物理页上，因此会把数据B写入到主块b₀的第4个页中。op₄的数据A₂会被写入到替换块b₁的第一个空闲页上，由于块b₁的第1个页此前已经被写入数据A₁，因此，数据A₂会被写入到替换块b₁中的第2个页。同理，op₅的数据B₁会被写入到替换块b₁中的第3个页。

（4）当读取操作op₆到达后，它要读取LPN=7的页，该页对应的逻辑块的LBN为1，查找映射表，可以得到对应的主块的PBN为b₀，根据主块b₀中记录的信息，可以找到其对应的替换块的PBN为b₁，系统会在替换块b₁中反向搜索每个页的OOB区域，检查其中记录的LPN的值是否为7，块b₁中第一个被找到的页中就包含了LPN=7的页的最新版本的数据。如果块b₁中没有找到LPN=7的页，系统就到主块b₀中寻找并读取数据。这里在块b₁中正好可以找到LPN=7的页的最新版本的数据，即块b₁中的第3个页，因此，从该页中读出数据B₁。

图[NFTL-1] NFTL-1机制的一个实例

3.2.2.2.2        NFTL-N机制

NFTL-N是针对那些没有OOB区域的闪存而设计的。在NFTL-N机制中，映射表负责执行从逻辑块地址到物理块地址的映射。当一个逻辑块第一次被分配一个物理块时，这个物理块被称为“主块”。当以后再对这个逻辑块的某个页执行更新操作时，该FTL机制会为相应的逻辑块分配一个新的物理块，这个新的物理块被称为“替换块”，然后在替换块的相应位置写入该页，即页在逻辑块中的块内偏移量应该和它在物理块中的块内偏移量相同。每个主块都会有一个替换块，主块上的更新都被写入到替换块上。由于一个页会被多次更新，因此，对于一个替换块而言，它自身也会有相应的替换块。

为了方便确定最新版本的数据和可用的空闲页，NFTL-N机制会为所有属于同一个逻辑块的替换块建立一个链表。对于读操作而言，通过在链表中进行查找，就可以找到最近一次更新的页；对于写操作而言，可以在链表中找到具有相同的块内偏移量的第一个空闲页。对于包含频繁更新操作的负载而言，该FTL机制会频繁地生成相应的替换块，而闪存的空间是有限的，可能会很快被消耗殆尽。因此，当更新操作找不到可用的空闲页时，就会执行一个合并操作，回收那些没有包含最新版本数据的页，具体方法是：找到所有链表中最长的链表，把所有最近更新的页从各个替换块中复制到链表中的最后一个替换块中，这个替换块就成为原来的逻辑块所对应的新的物理块。这个合并操作过程完成以后，原来逻辑块对应的旧的物理块和链表中的替换块（除了最后一个替换块），都会被擦除，成为可用的空闲块。

这里给出一个实例解释NFTL-N机制的工作过程（如图[NFTL-N]所示）。仍然假设闪存有4个块，每个块包含4个页。操作序列op₁,op₂,op₃,op₄,op₅,op₆的含义与上面的NFTL-1的实例完全相同。这个操作序列的执行过程如下：

（1）操作op₁首先到达， LPN=5的页所属的块的LBN为1。系统查找映射表，发现不存在LBN=1对应的映射条目，因此，立即为LBN=1的逻辑块分配一个物理块，物理块的PBN（物理块编号）为b₀，并把该条映射写入到映射表，同时，为LBN=1的逻辑块建立一个“块链表”，把主块b₀增加到块链表中。物理块b₀是逻辑块1的“主块”，op₁的写操作针对的页的LPN是5，该页在逻辑块内的页面偏移量是1（即块中的第2个页），NFTL-1要求把数据写入到物理块中具有相同块内偏移量的物理页上，因此，op₁的数据A会被写入到物理块b₀的第2个页中

（2）然后，操作op₂到达，系统根据LPN=5计算得到其所属的逻辑块的LBN=1，查找映射表，发现已经存在LBN=1对应的映射条目，读取映射条目，找到LBN=1的逻辑块对应的块链表，链表中找到第一个块为b₀，然后，根据块内偏移量，找到物理块b₀内的第2个页，发现该页已经被写入数据，由此可以判定op₂操作是针对同一个页的更新操作。这时，系统会为LBN=1的逻辑块再分配一个物理块b₁，这个物理块被称为块b₀的“替换块”，并把替换块b₁添加到为LBN=1的逻辑块建立的“块链表”中，即添加到链表中块b₀的后面；然后，系统把op₂操作的数据A₁写入到替换块b₁中具有相同块内偏移量的页上，即写入到块b₁中的第2个页。

（3）接着，操作op₃到达，是针对LPN=7的页的写入操作，该页对应的LBN为1。根据映射表，找到LBN=1的逻辑块对应的块链表，链表中找到第一个块为为b₀，块b₀中与LPN=7的页具有相同块内偏移量的页是块b₀的第4个页，该页仍然处于空闲状态，没有写入数据，因此把数据B写入块b₀的第4个页中。

（4）然后，操作op₄到达，LPN=5的页所属的块的LBN为1，查找映射表，找到LBN=1的逻辑块对应的块链表，链表中找到第一个块为b₀，但是，块b₀中具有相同块内偏移量的页（即第2个页），已经写入数据，因此，继续沿着链表查找到第二个块b₁，但是，块b₁中具有相同块内偏移量的页（即第2个页），也已经写入数据，而这时已经搜索到链表的尾部，已经找不到其他可用的块，因此，系统会再新分配一个替换块b₂，加入到链表中，即放在链表中块b₁的后面，然后，在块b₂中具有相同块内偏移量的页（即第2个页）中，写入数据A₂。

（5）当操作op₅到达，查找到与LPN=7的页对应的块链表，链表中找到第一个块为b₀，块b₀中与LPN=7的页具有相同块内偏移量的页是块b₀的第4个页，但是，已经写入数据，因此，继续沿着链表寻找到第二个块b₁，块b₁中与LPN=7的页具有相同块内偏移量的页是块b₁的第4个页，该页仍然处于空闲状态，没有写入数据，因此，把数据B₁写入块b₁的第4个页中。

（6）最后，当操作op₆到达时，查找到与LPN=7的页对应的块链表，然后，从链表的尾部b₂开始，在链表中反向搜索，寻找第一个具有相同块内偏移量并且不为空的页。可以看出，块b₂中找不到满足该条件的页，块b₁中正好可以找到满足该条件的页，即块b₁中的第4个页，这个页就是LPN=7的页的最新版本的数据，因此，从该页中读取出数据B₁。

图[NFTL-N] NFTL-N机制的一个实例

3.2.2.2.3     针对NFTL-1的改进

文献[ChoudhuriG07]的研究发现，在NFTL-1机制中，有两类重要的“元数据”信息，会被频繁地访问。第一，要频繁地检查一个给定的页是否包含有效的数据，这是一个布尔型信息，存放在闪存页的OOB区域中，因此，如果把反映一个页是否有效的状态信息，从OOB区域中复制出来放入到RAM中，就可以避免大量的OOB数据读取。第二，要确认与一个主块对应的替换块的信息。RAM中的数据读写速度，要明远远高于闪存中的数据读写速度。

从闪存页的OOB区域中读写数据的开销，虽然要比从闪存的数据区域中读写数据的开销要低很多，但是，在频繁访问的情况下，OOB数据读取的累积代价是不能被忽略的。表[OOB]显示了两种闪存芯片的各种性能参数，可以看出，OOB读写代价是一个需要考虑的因素，它会影响NFTL-1机制的整体性能。

表[OOB] 两款NAND闪存产品的特性参数

Characteristics         Toshiba 16MB       Samsung 16MB

Block size               16384（bytes）         16384（bytes） Page size                 512（bytes）           512（bytes） OOB size                   16（bytes）           16（bytes） Read Page                 52（usec）             36（usec） Read OOB                 26（usec）             10（usec） Write Page                 200（usec）           200（usec） Write OOB                 200（usec）           200（usec） Erasc                     2000（usec）           2000（usec）

 

因此，把这些频繁被访问的信息放入到RAM中，可以有效提高FTL机制的整体性能。为了降低对上述两类元数据信息频繁访问带来的开销，作者引入了两种技术方案，即查找表和页缓存：

• 查找表：维护一个RAM中的数据结构，可以实现快速的元数据信息查找；
• 页缓存：充分利用时间局部性，缓存最近访问的页。

3.2.2.2.3.1        查找表

查找表技术中，采用了两种类型的RAM数据结构：替换块表和页状态位图。其中，替换块表提供了对替换块信息的快速访问，可以加快为一个指定的主块寻找对应的替换块的过程，而页状态位图则可以看成是一个关于每页状态的指示器，可以加快检查一个页是否包含有效数据的过程。

替换块表是根据虚拟块地址来进行索引的。对于一个给定的虚拟块，它在替换块表中的条目（entry），是一个替换块的物理地址（如果该虚拟块的替换块存在的话）。有了替换块表以后，与替换块相关的元数据信息，就可以直接从高速的RAM中读取，节省了大量的OOB数据读取开销。具体而言，替换块表可以在以下情形中避免闪存的OOB数据读取开销：

（1）为了检查替换块的存在，每个页读操作会导致OOB数据读取；

（2）针对一个页的重写，需要从主块的OOB区域中获取到替换块的物理地址；

（3）在垃圾回收过程中，每个需要被合并的主块，都需要从OOB区域中获取到替换块地址。

页状态位图是根据每个页的块内偏移量进行索引的。对于一个给定的页偏移量，页状态位图中的“1”，就表示相应的页已经被至少写入一次，“0”则表示相应的页从来没有被写入过。也就是说，页状态位图就是每页有效标志位在RAM中的一份拷贝。

页状态位图可以避免很多OOB数据读取开销。具体而言，主要包括两类OOB数据读取开销：

（1）每个写请求会读取OOB数据，来确定写请求应该到主块还是替换块中去执行；

（2）每个读请求会检查OOB数据，来确定一个非法读请求的可能性。

由于页状态位图避免了上述两种OOB数据读取开销，因此，它加速了读操作和写操作。

替换块表的空间开销和FTL映射表的空间开销是一样的。页状态位图的空间开销是最小的，每个页只需要一位。因此，对于一个给定大小为S的闪存，假设它的块大小为B，页大小为P，那么，替换块表就有（S/B）个条目。页状态位图就有(S/P)位。例如，对于一个1GB闪存，它的页大小是512KB，块大小是8KB，每个条目是4B，那么，就需要（2³⁰/2¹³）*4=512KB的RAM内存空间，页状态位图需要（2³⁰/（2⁹*8）=256KB的RAM内存空间。

3.2.2.2.3.2    页缓存

页缓存是一个可配置的缓存，它会保存最近写入的页的物理地址<块号,页号>。这个映射信息可以用来直接定位一个页，而不需要读OOB数据，这就避免了可能产生的OOB数据读取开销。实际上，为了定位一个页，有时候需要很多次OOB数据读取操作，在最坏的情况下，可能需要读取替换块中每个页的OOB数据（OOB中记录了一个页的LPN），来确定是否包含一个指定的页，使得OOB数据读取次数会等于块中的页数。但是，和查找表方法不同，页缓存依赖于时间局部性。和查找表类似，页缓存的条目也是那些早已经存在于OOB区域中的数据的备份。因此，就没有必要把这些信息刷新到闪存中。页缓存可以改进一个页的逻辑地址到物理地址映射的时间，主要发生在以下情形：（1）在一个页的读请求期间；（2）由一个合并操作引发的读操作期间。而且要注意的是，在这两种情形下的收益，都来自于时间局部性。

3.2.3     混合FTL机制

3.2.3.1      机制概述

混合FTL机制充分吸收了页级别和块级别映射的优点，既具备了页级别的高效和灵活性，又融合了块级别的映射表小、管理开销小的特点，从而可以有效处理比一个块小的写操作，并降低页级别地址映射的存储开销。混合FTL机制把逻辑块分成两类：数据块和日志块，前者采用块级别映射，用来存储数据，后者采用页级别映射，用来存储更新。数据块的数量较多，而日志块的数量较少，通常只占到闪存总空间的3%左右[LeeSKK08]，因此，日志块采用页级别映射后，映射表的规模也很小，完全可以放入到SRAM中。所有日志块构成日志缓冲区，当一个更新操作需要对数据块进行更新时，只需要把更新写入到日志缓冲区中，并把数据块中相应的数据设置为“无效”，而不需要擦除原来的数据块，这就可以大大减少对数据块所要执行的擦除操作的总次数。在把逻辑更新页写入到日志块中的物理页的时候，逻辑更新页所对应的逻辑页面编号也会被同时写入到物理页的备用区域，而且写入备用区域的代价是几乎可以忽略不计的。当一个读请求到达时，必须首先检查日志块中是否已经存在被请求的页，如果日志块中已经存在该页，就直接将该页内容返回给读请求，该页数据在数据块中相应的旧版本就会被隐藏掉。当一个逻辑页被多次反复更新时，日志块中就会存在与该逻辑页对应的多个物理页，按照更新操作的先后顺序依次记录每一次更新操作，由于后面发生的更新会被记录在日志块中靠后的物理页中，因此，只要在日志块中从后往前扫描，就可以找到最新版本的物理页。

在混合FTL机制中，需要用日志块记录更新操作，当日志块消耗殆尽时，日志块中的一些数据就必须被刷新到数据块中，从而释放出可用的日志块空间。这就需要一个合并操作，即对数据块中的有效数据和日志块中的日志数据进行合并，写入到一个空的数据块中。

合并操作通常包含三种类型：切换合并、部分合并和完全合并。

（1）切换合并

图[switch-merge] 切换合并

切换合并通常针对“顺序写入”的情形，图[switch-merge]显示了切换合并的过程。在t₀时刻，有一个数据块B₁，包含了四个页面，逻辑页面编号（LPN）分别是0、1、2和3，每个页面都已经写入了数据，因此，B₁中每个页面的数据区域都用灰色背景进行标识，表示该页当前处于“有效”状态。在t₀和t₁时刻之间，发生了针对数据块B₁的四个页面的四次顺序更新操作。混合FTL机制中，对数据块的更新操作都会被记录在日志块中，因此，在t₁时刻，日志块B₂记录了上述四个顺序更新操作；这时数据块B₁中每个页面的数据区域都用黑色背景进行标识，表示该页当前处于“无效”状态，日志块B₂中的每个页面的数据区域都用灰色背景进行标识，表示该页面当前处于“有效”状态。在t₁时刻之后，发生了切换合并，即直接把块B₂从日志块变成数据块，同时，要擦除数据块B₁，使得B₁再次成为空闲的数据块，可以再次用来写入其他数据，这里B₁中的每个页面的数据区域用白色背景标识，表示该页面当前处于“擦除/空闲”状态，擦除以后每个页面的逻辑页面编号都变成了Φ。图[switch-merge]显示了在t₂时刻切换合并操作结束后各个块的状态。从上述过程可以看出，切换合并的代价很低，只需要一个擦除操作，但是，需要严格的前提条件，即只有当一个数据块中的所有页面都是顺序更新（即从第一个逻辑页到最后一个逻辑页依次进行更新）的时候，才可以进行切换合并。

（2）部分合并

         部分合并针对“部分顺序写入”的情形，图[partial-merge]显示了部分合并的过程。在t₀时刻，有一个数据块B₁，包含了四个页面。在t₀和t₁时刻之间，发生了针对数据块B₁的前三个页面的三次顺序更新操作，即分别更新了逻辑页面编号为0、1和2的三个页面，而逻辑页面编号为3的页面并没有发生更新。在t₁时刻，日志块B₂记录了上述三个顺序更新操作。在t₁时刻之后，发生了部分合并操作，即把数据块B₁中的有效页（LPN=3）复制到日志块中，然后，执行一个切换操作，让日志块B₂变成一个数据块，同时对数据块B₁执行擦除操作，成为空闲页。图[partial-merge]显示了在t₂时刻部分合并操作结束后各个块的状态。从上述过程可以看出，部分切换不仅需要一个擦除操作，还需要一个额外的复制操作，因此比切换合并代价高。使用部分合并的前提条件是，顺序更新操作没有执行满一个块。

图[partial-merge] 部分合并

（3）完全合并

完全合并通常是针对“随机写入”的情形，图[full-merge]显示了完全合并的过程。在t₀时刻，有两个数据块B₁和B₂。在t₀和t₁时刻之间，发生了针对数据块B₁的两个页面（LPN=0和LPN=1）的更新操作，同时还发生了针对数据块B₂的两个页面（LPN=4和LPN=5）的更新操作，这四个更新操作的先后顺序是依次更新LPN为4、0、5和1的页面。更新结束后，在t₁时刻，日志块B₃按照更新的先后顺序依次记录了上述四个随机更新操作，这时，B₃中的四个页面都处于“有效”状态，而数据块B₁的两个页面（LPN=0和LPN=1）和数据块B₂的两个页面（LPN=4和LPN=5），则因为已经被更新过而处于“无效”状态。在t₁时刻之后，又先后发生了针对不同三个页面（LPN=4、LPN=2和LPN=5）的更新操作，由于这里假设一个块只包含四个页，而日志块B₃已经填满，因此，必须把这三个更新操作依次记录到新的日志块B₄当中。需要注意的是，在第二次更新LPN为4的页面时，因为此前已经对该页更新过一次，它的最新版本的数据已经在日志块B₃中（而不是数据块B₂中），因此，需要在日志块B₃中把LPN=4的页面更改为“无效”，并把最新版本的数据写入到日志块B₄中。对于LPN=5的页面而言，也是发生了二次更新，处理方法和LPN=4的页面相同。在t₂时刻，日志块B₄记录了上述三个更新操作，因此，B₄中的前三个页面都处于“有效”状态，而B₄中还剩余一个页面，该页面没有写入数据，因而处于“擦除/空闲”状态。在t₂时刻之后，又发生了针对LPN=4的页面的第三次更新操作，该操作会被记录到日志块B₄中的最后一个空闲页里面，同时，日志块B₄中第一个页面（LPN=4）被设置为“无效”。在t₃时刻，日志块B₄中已经记录了刚才发生的更新。在t₃时刻之后，发生了完全合并操作，具体方法是：选择日志块B₃作为牺牲日志块，同时为本次完全合并操作分配一个新的空闲数据块B₅，然后，把数据块B₁中的有效页（LPN=3）、日志块B₃中的有效页（LPN=0，LPN=1）、日志块B₄中的有效页（LPN=2），分别复制到新的空闲数据块B₅中，最后，擦除数据块B₁和日志块B₃，这两个块又成为空闲块。需要注意的是，把日志块B₄中的有效页（LPN=2），复制到新的空闲数据块B₅中以后，需要把日志块B₄中的这个页（LPN=2）更改为“无效”。图[full-merge]显示了，在t₄时刻完全合并操作完成以后，各个数据块和日志块的状态。从上述过程可以看出，完全合并操作需要多个复制操作和擦除操作，代价比较高，要明显高于切换合并操作和部分合并操作。完全合并操作应用于随机更新操作较多的场合。

图[full-merge] 完全合并

      上面描述的只是关于完全合并的一个非常简单的实例，实际上，完全合并可能要更加负载，代价更高。比如，在经过一系列的各种合并操作以后，可能会出现一个日志块和数据块之间的“循环关联”，也就是说，一个被选中牺牲的日志块可能包含和多个数据块相关的更新，而这些数据块又包含和多个日志块相关的更新过的页面。这种情形下，完全合并的代价就会变得非常高，反过来，它又会影响到后续其他操作的性能，不管后续操作是顺序操作还是随机操作。

正因为完全合并具有很高的代价，大多数基于日志缓存的混合FTL机制重点研究解决的问题，就是如何减少完全合并操作的数量。比较典型的方法是，对数据块进行划分，分成冷块和热块[HsiehK06]。被频繁访问的数据被保存在热块中，通常会包含大量的无效页，而冷块则包含被很少访问的数据。在垃圾收集时使用热块，减少了有效页面的复制开销，因此，也就降低了完全合并的开销。不过，这种做法也只是在一定程度上缓解完全合并的问题，并没有从根本上解决这个问题，因此，文献[GuptaKU09]的大量实验测试表明，在一些比较复杂的负载类型下，各种混合FTL机制的性能表现都不尽人意。

3.2.3.2   典型研究

3.2.3.2.1   BAST

文献[KimKNMC02]在2002年提出的BAST (Block-Associative Sector Translation)，是第一个混合FTL机制。BAST的主要目标就是，在有限的SRAM下，能够实现高效的小数据量类型的写操作和较长的顺序写操作。为了达到这个目的，作者采用了页级别映射的日志块和块级别映射的数据块，针对数据块的更新操作都被记录到日志块中。BAST采用“块关联映射”（block associative mapping），每个数据块都与唯一一个特定的日志块关联，即每个日志块只能容纳来自同一个逻辑块的页。为了提高性能，BAST把日志块的页级别映射表存放到SRAM中，同时，BAST还可以在发生断电时保证所存储的数据的一致性。BAST的读性能要比块级别FTL好，因为，SRAM的速度要比闪存的速度高好几个级别。当访问模式主要是顺序写时，BAST可以提供高效的垃圾回收过程，因为，这种情形涉及大量的低代价的切换合并。

3.2.3.2.1.1        BAST机制的写操作过程

图[BAST] BAST机制的写过程

下面重点介绍BAST机制中的写操作执行的过程，从而对该机制的技术细节有更好的理解。

假设闪存中只有两个日志块和若干数据块，每个块包含四个页。现在假设有一个更新序列U₀,U₁,U₀,U₀,U₄,U₅,U₆,U₇,U₄,U₅,U₆,U₇，其中，U_i表示对LPN=i的页面进行更新操作。U₀执行时，首先根据LPN=0计算出该逻辑页所在的逻辑块的LBN（逻辑块编号）为0，计算方法是：LPN除以每个块包含的页数，得到的商就是LBN；其次，在面向数据块的块级别映射表中找到LBN=0的逻辑块所对应的物理块的PBN（物理块编号）为3；再次，计算出物理块内的物理页的块内偏移量为0，计算方法是：用LPN除以每个块包含的页数，得到的余数就是偏移量。最后，根据PBN=0和块内偏移量0，把U₀写入到PBN=0的物理块内的第1个页内（第1个页的块内偏移量为0）。同理，可以把第二个到达的更新U₁写入到PBN=0的物理块内的第2个页内。

当第三个更新U₀到达时，是执行对LPN=0的逻辑页的第二次更新操作，因为此前在数据块中已经保存了该逻辑页中旧版本的数据，因此，本次更新操作会被记录到日志块中，具体方法是：BAST首先查找是否已经存在和LBN=0的逻辑块对应的日志块，发现不存在，就会把第一个日志块（PBN=30）分配给该逻辑块，专门用于记录与该逻辑块相关的更新操作，接着把更新操作记录到该日志块的第一个空闲页内，由于当前日志块的所有页面都是空闲页，因此，更新会被记录到第一个页中；最后，对面向日志块的页级别的映射表进行更新，写入一个新条目，即LBN=0,PBN=30,LPNs={0}，表示与LBN=0的逻辑块相关的所有更新操作都被记录在PBN=30的日志块中，并且该日志块中当前已经记录了一次针对LPN=0的逻辑页的更新操作。

当第四个更新操作U₀到达时，又是针对LPN=0的逻辑页的第三次更新操作。因此，会被记录到PBN=30的日志块中的第二个页中，然后，对页级别映射表进行更新，即把条目“LBN=0,PBN=30,LPNs={0}”更新为即“LBN=0,PBN=30,LPNs={0,0}”。

当第五、六、七和八个更新操作U₄,U₅,U₆,U₇依次到达时，会被依次记录到PBN=4的数据块中。当第九个更新操作U₄到达时，这是对LPN=4的逻辑页的第二次更新操作，此前已经在数据块中存在旧版本数据，因此，本次更新会被记录在日志块中。LPN=4的逻辑页所在的逻辑块的LBN为1，BAST首先查找是否已经存在和LBN=1的逻辑块对应的日志块，发现不存在，就会把第二个日志块（PBN=40）分配给该逻辑块，专门用于记录与该逻辑块相关的更新操作。这里需要特别注意的是，BAST机制的设计中，只允许一个日志块容纳来自同一个逻辑块的更新操作，因此，第一个日志块（PBN=30）是专门分配给LBN=0的逻辑块使用的，不能用来记录针对LBN=1的逻辑块的更新操作，所以，这里才会分配第二个日志块（PBN=40）给LBN=1的逻辑块使用。分配到日志块后，更新操作U₄,会被记录到PBN=40的日志块中，并对页级别映射表进行更新。依此类推，接下来的另外三个更新操作U₅,U₆,U₇也会被依次记录到PBN=40的日志块，更新完成后的页级别映射表相应的条目为“LBN=1,PBN=40,LPNs={4,5,6,7}”。

假设此后还有其他的更新操作到达，PBN=5的数据块会被写满。PBN=5的数据块中的物理页所对应的逻辑页，如果发生了再次更新操作，就又需要把这些操作记录到日志块中，需要为它分配一个新的日志块。但是，之前已经假设最多只有两个数据块，因此，这里就必须从PBN=30和PBN=40的日志块中选择一个日志块作为牺牲品，具体过程如下：首先分配一个空闲的数据块（假设PBN=9），然后把牺牲日志块（假设PBN=30）和它对应的数据块（假设PBN=3）中的最新版本的数据都复制合并到该空闲数据块中（根据情况不同，可能发生切换合并、部分合并或完全合并），然后擦除PBN=30的数据块和PBN=3的日志块，让这两个块成为空闲块，最后，要修改块级别的映射表，即把“LBN=0，PBN=3”这个条目修改为“LBN=0，PBN=9”，同时，还要修改页级别的映射表，即删除即“LBN=0,PBN=30,LPNs={0,0}”这个条目。

3.2.3.2.1.2        BAST的缺陷

BAST的缺陷主要体现在以下几个方面：

• BAST在面对小数据量的随机写请求时，日志缓冲区的利用率就会大大降低，因为，即使更新数据块的一个页面，也需要使用整个日志块。日志块对于减少“写前擦除”次数的作用很大，降低了日志块的利用率，也就等于降低了日志块对于闪存性能提升的作用。文献[LeePCLPS07]的研究发现，对于BAST而言，当日志块的数量少于“热块”（被频繁更新的块）的数量时，日志块的利用率很低，因为，日志块会很快成为被替换掉的牺牲品，根本没有时间让其他更新来把块中剩余的页面填满；另外，在日志块的数量保持不变时，负载类型越随机，BAST的日志缓冲区利用率就越低。
• 对于BAST而言，由于采用“块关联映射”，当对数据块中的某个页进行更新时，这个更新操作只能被引导到与该数据块关联的特定数据块上面去执行，而不能引导到其他日志块上面。这会导致日志块的利用率较低，同时也增加了完全合并的开销。而且，在有限的闪存空间限制下，BAST会很容易耗光可用的替换块，从而不得不启动回收进程，回收那些还没有被占用的块。因此，BAST中替换块的利用率在理论和实践上都是很低的。而且，在一个给定的时间窗口内对一个块进行频繁更新操作，会导致频繁发生合并操作，这也会导致写操作数量的增加。
• 由于日志块数量有限，频繁随机写操作，还可能会导致“块抖动”问题[LeePCLPS07]（和内存页面抖动问题是类似的，请参见例子1），因而无法获得好的性能。当对一个数据块执行一个更新操作时，如果不存在与该数据块对应的日志块，就需要从已有的日志块中选择一个作为牺牲品，把该日志块和与之关联的数据块执行合并操作（很多情况下会发生完全合并操作），然后擦除该日志块，供当前的更新操作使用。如果日志块的数量有限，那么这种选择牺牲品的替换操作会频繁地发生。

例子1：这里以一个实例来阐述BAST存在的“块抖动”问题。假设闪存中只有两个日志块，每个日志块包含四个页。这里假设这八个逻辑页面对应的数据都已经保存在闪存的物理块中，而且这些块都已经填满。现在假设有一个更新序列U₀,U₄,U₈,U₁₂,U₀,U₄,U₈,U₁₂，其中，U_i表示对LPN=i的页面进行更新操作，并且不同的i分别来自不同的块。执行完U₀以后，日志块B₀记录了本次更新，B₀被放入到SRAM缓存中。接着执行完U₁以后，需要使用另一个日志块B₁来记录本次更新，因为即使更新数据块的一个页面，也需要使用整个日志块；B₁被放入到SRAM缓存中以后，这时缓存已经填满，没有剩余空间。接着执行完U₈以后，需要使用一个新的日志块B₃来记录本次更新，B₃应该被放入缓存，但是，此前缓存已经填满，因此，就必须采用适当的替换策略，把B₁和B₂中的其中一个驱逐出缓存，然后把B₃放入缓存。在执行后续的每个更新以后，都会发生类似的块替换问题，这就导致了“块抖动”问题。

3.2.3.2.2  FAST

为了解决块抖动问题，文献[LeePCLPS07]提出了一种新的混合FTL机制——FAST(Fully Associative Sector Translation)。和BAST不同的是，FAST没有采用“块关联映射”，而是采用“完全关联映射”（fully associative mapping），即允许日志块被所有的数据块共享，从而改进了日志块的利用率，而且只有在日志缓冲区没有剩余空间的时候，才会启动垃圾回收过程。这种方法有效地消除了块抖动问题，并且在面对随机负载时也可以提高垃圾回收效率。为了增加部分和切换式合并的比例，减少合并操作的开销，FAST为顺序更新专门确定了一个顺序日志块，而其他日志块则用来执行随机写操作。作者的实验表明，在最好的情况下，在存取时间和擦除操作的次数方面，FAST都要比BAST降低50%以上。

FAST的缺陷体现在以下几个方面：

• 这种方式带来的性能优化效果也十分有限，因为，在现代的多线程环境下，一个顺序写操作通常会被随机写和其他顺序写操作打断。因此， FAST不能容纳多个数据流，并且它也没有提供任何特定的机制来处理随机数据流中存在的时间上的局部性。
• 虽然FAST尽可能地延迟了垃圾收集的时间，但是，回收一个单个的日志块所耗费的时间，会比BAST更长[MaFL11]。

3.2.3.2.3  LAST

通常而言，在通用的计算机系统中存在的典型的负载，是随机写和顺序写的混合。因此，LAST[LeeSKK08]机制从混合负载中分离出顺序负载，从而可以对顺序负载执行更多的、低代价的切换合并和部分合并，提高整体性能。图[LAST]显示了LAST机制的体系架构。LAST机制对日志块区域进行了功能分段，分成顺序日志缓冲区（包含多个顺序日志块）和随机日志缓冲区（包含多个随机日志块）。

在顺序日志缓冲区，LAST采用了和BAST类似的“块关联映射”，即每个顺序日志块只和一个数据块对应，因为，块关联映射比较适合顺序访问类型的负载。LAST设计多个顺序日志块可以充分利用负载的空间局部性，较长的请求会被写入到顺序日志块，从而有利于执行部分或者切换式合并，这就可以尽力缓解FAST的缺陷，因为在FAST中只有一个顺序日志块。

在随机日志缓冲区，LAST采用了和FAST类似的“完全关联映射”，因为，这种方式更加适合随机访问类型的负载，尤其是对于那些具有很高的时间局部性的随机负载而言更是如此。LAST进一步把随机日志块分成热块和冷块，来减少完全合并代价，即将被写入的热数据，会被放入热块中，其他的写请求则由冷块来服务。LAST依赖一个外部的局部性探测机制来确定顺序写和随机写。

LAST机制的缺陷是：作者自己也意识到，当小数据量的写操作具有顺序的局部性时，他们提出的局部探测器可能无法有效地确定这种顺序写操作。实际上，即使一个探测器非常智能，在测试基准上可以有效区分顺序和随机IO，但是，在运行时刻，面对各种复杂的应用环境时，也会遇到大量的问题导致无法有效区分顺序和随机IO。例如，在缓冲池中缓存数据就会极大改变物理数据访问模式。

图[LAST] LAST机制的体系架构

3.2.3.2.4   SuperBlock

SuperBlock机制[KangJKL06]和FAST不同，并不允许日志块被所有的数据块共享，而是在N个数据块中共享最多K个日志块。该机制还充分利用了工作负载中存在的块级别的空间局部性，会把连续的逻辑块合并成一个超级块，在超级块内部，采用页级别的映射。该机制还把超级块内部的热块和冷块做了区分，从而可以充分利用请求数据流中的时间局部性。但是，采用超级块机制后，属于N个逻辑块的页可能被分布到N+M个物理块中（M表示额外分配给超级块的更新块的数量），因此高效地维护映射表信息就成为一个具有挑战性的问题。为此，该机制把映射表被保存到超级块的备用区域，当用户数据被写入到闪存的数据区域时，最新的页面地址映射信息也会被写入到闪存的备用区域，因此，不会引起额外的闪存空间开销和操作开销。

SuperBlock机制的缺陷体现在以下几个方面：

• 由于备用区域的大小限制，Superblock采用了三级地址映射方法，从而可以把映射信息保存到有限的备用区域中，这样就需要最多搜索三个备用区域来寻找一个被请求的页，需要一定的代价。
• 该机制采用固定的超级块大小，为了适应不同的工作负载类型，就需要显式地对超级块大小进行调整。
• 该机制只对冷块和热块进行了区分，却没有对块内的冷页和热页进行区分。
• 需要花费一定的代价来维护一个超级块内部的页级别的映射信息。

3.2.3.3    其他相关研究

与SuperBlock一样，SAST[LeePCLPS07]也是在N个数据块中共享最多K个日志块，而且不同的数据块集合，会竞争日志块。SAST包含了调优的过程，在使用之前需要进行调优，这意味着，当访问模式发生变化时，它的性能就会恶化。A-SAST (Adaptive SAST) [KooS09]是一个针对SAST的优化版本，它放松了一个数据块集合中可以共享的日志块的最大数量的限制，可以对数据块集合进行动态划分和合并。

HFTL[LeeYL09]首先利用热数据探测方法（基于哈希的热数据区域标识技术）对冷热数据进行区分，然后，对热数据采用扇区映射机制，而对冷数据采用基于日志块的机制。但是，当访问模式变化时，一些热页需要被交换出来，这就需要额外的开销。

3.2.4  变长映射

文献[ChangK04]的作者对两种典型负载进行了连续跟踪：（1）普通用户电脑上的操作（包括网页浏览、邮件收发、文档编辑和游戏等）和（2）多媒体文件存储系统。通过对跟踪结果的分析，作者观察到：（1）小尺寸的写操作具有很强的空间局部性；（2）批量写操作一般都会顺序访问磁盘。对于多媒体存储而言，绝大多数写操作都是批量的顺序操作。因此，作者认为闪存管理机制需要可变的粒度来适应不同的访问模式，而传统的方法通常采用固定的粒度，即采用两个固定的表来执行地址映射和空间管理。由此，文献[ChangK04]在2005年提出了一种变长的映射机制。变长映射机制会把变长的、连续的逻辑页映射到闪存中的物理页。当访问模式发生变化时，可以进行粒度的动态调整。

变长映射机制的缺点是：由于不同映射单元的尺寸并不相同，而且是动态变化的，映射表只能存放在一些特定类型的搜索树中，由此导致的后果就是，相对于其他FTL机制而言，变长映射表的查找代价比较大，因为，在其他FTL机制中，映射表就是一个非常简单的地址数组。

3.2.5     关于不同映射机制的讨论

对于一个采用了固态盘的存储系统而言，不管它采用什么样的FTL映射方式，这个存储系统都应该保证操作的可靠性，也就是说，脏数据（即发生了更新的数据）在操作返回前应该被刷新到闪存中。因此，设计FTL机制必须以保证操作可靠性作为提高性能的前提。在此前提下，为了设计一个高效的FTL机制，首先应该考虑映射粒度。在所有的FTL机制中，页面级别的映射，是最有效和高效的映射粒度，但是，映射表开销较大。块级别的映射都无法对冷数据和热数据进行区别对待，因此，在垃圾回收过程中，必须对冷数据进行不必要的移动，增加了存储系统的整体开销。变长映射虽然可以动态调整映射的粒度，但是，地址翻译的高复杂性是一个不容忽视的致命缺陷。混合映射比较灵活，因为通过对LBA进行分区，或者共享日志块，可以尽量避免代价高昂的完整合并操作。但是，需要指出的是，无论设计得多么细致，混合映射机制都无法完全消除完整合并。

3.3   双模式FTL

在过去几十年里，磁盘在存储系统中占据了举足轻重的地位，这是因为磁盘遵循了两条简单的标准，从而对上层应用表现出了稳定的性能：第一，数据存储如果在逻辑地址空间内具有局部性，那么在物理地址空间上也可以保持这种局部性；第二，顺序访问要比随机访问快许多。由于Unix的出现，接口的稳定性和磁盘特性的稳定性，确保了主要的数据库系统设计原则的长久有效性，这些设计原则包括：（1）以页作为基本的IO单元，在磁盘和内存中都用页来访问数据；（2）避免随机访问（比如查询处理算法），尽量采用顺序访问（比如聚类）。

随着闪存的出现，闪存存储设备已经开始在企业存储系统中发挥着越来越重要的作用。但是，与磁盘设备具有一致稳定的性能不同的是，闪存设备不仅自身无法提供稳定一致的性能，而且不同闪存设备之间的性能差异也较大。例如，对于FusionIO[FusionIO]而言，随机写的速度要比读速度快。而在许多三星闪存设备上，随机写的速度要比读速度慢许多。对于一些闪存设备而言，性能会随着时间变化，因为，这些闪存设备的性能和历史IO模式有关。比如，INTEL X25-M的性能的变化幅度会达到一个数量级，而其性能的高低取决于设备是否采用随机写。如果让一个数据库的设计建立在一个性能不断变化的存储系统上，要想获得较好的性能是很难的。

但是，数据库设计者和闪存设备设计者毕竟属于两个不同的领域，二者有着各自的设计目标。对于数据库设计者而言，他们会竭力控制由自己发起的IO标准，通常会首先对高效和低效的IO模式进行明确的界定和区分，从而使得他们可以调整分配策略、数据表示或者查询处理算法，以便更好地适应底层的存储系统。为了获得更好的性能和稳定的行为，数据库群体甚至不惜以增加设计复杂性为代价。对于闪存设备设计人员而言，比如SSD设计者，会竭力隐藏闪存的各种内部特性，提供和磁盘一样的标准接口，从而和磁盘供应商进行竞争。不同闪存设备设计者之间也会相互竞争，设计更好的FTL来改善性能，并且隐藏自己的设计决策来保护他们自己的优势。实际上，闪存芯片早已经提供了对高效模式和低效模式之间的明确区分，页读操作和一个块内部的顺序页写操作，就属于高效模式，而就地更新操作就属于低效模式。闪存设备应该对上层应用暴露这种区分，而不是竭力以高效模式的性能为代价来减少低效模式带来的负面影响，比如以降低读性能为代价来获得改进的随机写性能。

由此可以看出，数据库设计者和闪存设备设计者之间缺乏有效的合作，导致采用闪存存储设备的数据库系统无法获得最佳的性能。闪存设备隐藏了闪存内部的特性，为数据库系统提供了标准的接口，数据库系统无法了解闪存设备的内部工作机制，因此，无法为闪存设备提供最优的IO模式，而闪存设备自身进行性能优化时，又完全不考虑上层数据库应用的IO模式特性，块分配和垃圾回收工作可能存在一定的盲目性，无法为数据库系统提供稳定的IO行为。

因此，当前闪存设备的复杂性和透明性对于数据库管理而言是很不合适的。数据库设计者和闪存设备设计者之间必须建立合作，保证闪存数据库获得较好的性能。现在的问题就是二者如何合作。也就是说，DBMS如何为闪存设备优化自己的IO模式？闪存设备如何才能保证为DBMS提供稳定的IO行为？

针对上述问题，Bonnet等人[BonnetB11]提出了双模式闪存设备的概念，即采用双模式FTL的闪存设备，并认为当前的闪存设备应该朝着双模式闪存设备发展，这种发展方向对于数据库机器的设计者而言是十分重要的，比如Oracle Exadata或者Neteeza TwinFin，这些数据库机器必须采用适合自己的闪存设备，才能提供高性能的数据库服务。实际上，如果按照双模式闪存设备的理念，数据库群体是可以使得闪存设备的发展朝着符合自己商业化数据库系统利益的方向进化的。

双模式FTL包括两种模式：

• 第一种模式：禁止更新和随机写操作，可以为顺序写、顺序读和随机读操作保证提供最优的性能；
• 第二种模式：可以支持更新和随机写操作，但是不能保证提供最优的性能，只能尽量提供好的性能。

双模式FTL的两种模式都是和闪存芯片存在的4种约束有关的。闪存芯片存在严重的性能约束：

• 约束C1：写操作必须以页为单位执行；
• 约束C2：写前擦除；
• 约束C3：在一个块内必须进行顺序写操作；
• 约束C4：有限的生命周期。

尽管闪存芯片的发展趋势是，闪存芯片的每个单元可以存储更多的位，处理时间更短（比如25纳秒），页尺寸更大，一个块内包含更多的页数量，生命周期更短，但是，所有这些发展趋势都没有违反性能约束C1到C4。

如图[Bimodal-FTL]所示，如果采用第二种模式的FTL，那么DBMS就不必处理C1到C3的约束，也就是说，DBMS可以向闪存设备提交任何模式的IO，必须由闪存设备自己来处理C1到C4的约束。如果采用第一种模式的FTL，那么DBMS就必须处理C1到C3的约束，也就是说，DBMS不能自己提交包含就地更新和随机写操作的IO。而FTL则会保证把遵循C1到C3的约束的IO，直接提交给底层的闪存芯片。在这种模式下，闪存设备的FTL会处理约束C4，即提供磨损均衡功能。实际上，一个DBMS是无法执行磨损均衡（约束C4）的，磨损均衡功能必须由FTL来提供。磨损均衡对于确保闪存设备的寿命而言，绝对是必须的。闪存设备生产商绝对不会提供一个只经过几分钟频繁的写入操作后就会报废的产品。为了支持磨损均衡，闪存设备的FTL机制必须实现某种形式的块映射，从而让擦除操作均匀地分布到不同的块上。那么，FTL可以取得的最优映射是什么呢？

一个映射是最优的，当以下条件成立时：

(a)块的查找操作是在闪存控制器的缓存中执行的；

(b)块内部的页的偏移量可以直接根据逻辑地址计算得到，即在一个块内会顺序写入连续的逻辑地址。

很显然，顺序写操作会导致最优的映射。另外，半随机写操作，也就是随机写操作被顺序地映射到不同的逻辑块上面，也会导致一个最优的映射。一个闪存块，如果它的映射是最优的，那么，就称它为“最优块”。一个最优块从来不会被垃圾回收，因为，在最优映射中，顺序写操作不会在一个块中产生任何废弃的页。

当采用第一种模式时，DBMS已经可以保证处理C1到C3的约束，那么，FTL就必须保证为遵循C1到C3约束的这些逻辑块提供最优的映射。当采用第二种模式时，DBMS提交给闪存设备的逻辑块不必遵循C1到C3约束，允许任意的IO模式，因此，这些逻辑块会被映射到一个或者多个物理闪存块中，并非采用最优的映射。

图[Bimodal-FTL] 双模式FTL机制示意图

双模式闪存设备可以为DBMS设计提供一个稳定和最优的性能基础。现有的一些研究工作，着力研究提供数据库顺序写这种IO模式，这样就可以弥补低端固态盘的较差的随机写性能。这些技术可以被应用在双模式FTL中，从而充分发挥顺序写操作的最优性能。同时，一些专门为闪存芯片设计的技术[2][17]，对于当前的固态盘而言仍然存在许多不足之处，但是，这些技术可以很自然地应用到双模式FTL中，因为它们只会生成最优块，符合双模式FTL中的第一种模式标准，双模式FTL可以保证为这种模式提供最优的性能。

3.4   本章小结

本章内容首先介绍了FTL的功能，包括地址映射、垃圾回收、磨损均衡、断电恢复等；然后，详细介绍了FTL的各种映射机制，包括页级别FTL机制、块级别FTL机制、混合FTL机制和变长映射机制；最后介绍了一种双模式FTL，它可以使得数据库设计者和闪存设备设计者之间建立合作，保证闪存数据库获得较好的性能。

FTL机制对于闪存数据库而言非常重要，它可以把一个闪存设备模拟成一个类似磁盘的块设备，从而使得以前面向磁盘开发的DBMS，不用任何修改就可以直接运行在具备FTL功能的闪存设备上。但是，由于大多数FTL机制都是针对文件系统开发的，并没有考虑数据库系统的IO特点，因此，简单地把传统的DBMS移植到闪存设备上，是无法充分发挥闪存的优良特性的，比如针对闪存特性，对DBMS或FTL机制进行相应的修改，从而获得最优的性能。这些内容将在后续章节中介绍。

3.5   习题

• 阐述FTL的主要功能并说明每种功能的具体含义。
• 分别说明页级别、块级别和混合FTL机制以及变长映射的各自优缺点。
• 说明BAST 机制中为什么会出现“块抖动”问题，应该设计什么机制来缓解该问题？
• 阐述双模式闪存设备的概念以及双模式FTL中的两种模式的具体含义。