第5章 闪存数据库存储管理

林子雨 1930

大数据之门

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

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

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

第5章 闪存数据库存储管理

和磁盘相比，闪存设备形状小，能耗低，抗震好，而且，由于闪存中不存在可转动的机械部件，因此，闪存设备具有更快的随机读速度。但是，闪存的写操作性能不具备明显的优势，尤其是随机写操作，会表现出较差的性能，因为闪存存在“写前擦除”的限制。频繁的随机写操作，会引起大量的擦除操作，不仅会严重恶化闪存写操作性能，还会大大缩短闪存的寿命。因此，面向闪存数据库的存储管理的主要任务，就是优化写操作模式，减少频繁随机写操作对闪存的影响。

目前已经有许多方法被提出来，用来优化闪存设备的写操作性能。由于把数据库中的数据存储到闪存中可以分为两种方法，即基于页的方法和基于日志的方法，因此，面向闪存数据库的存储管理方法也主要包括两大类：基于页的方法和基于日志的方法。

本章首先给出数据存储方法概述，然后分别介绍基于页的方法和基于日志的方法及其代表性研究，最后介绍两种其他方法，即基于页差异的日志方法和StableBuffer方法。

5.1   数据存储方法概述

把数据库中的数据存储到闪存中，可以采用两种方法：基于页的方法和基于日志的方法。

5.1.1     基于页的方法

在基于页的方法中[Ban95][LeePCLPS07][LeeSKK08]，一个逻辑页会被存储到一个物理页中。内存中的逻辑页会不断接受更新，当一个更新后的逻辑页需要被刷新到闪存中时，整个逻辑页（包括变化的数据和没有发生变化的数据）都会被写入到一个物理页中，因此，基于页的方法的写操作性能比较差。当需要重构一个逻辑页时——把该页从闪存中读取到DBMS内存缓冲区中，就可以根据FTL中逻辑页到物理页的地址映射表，找到闪存中和该逻辑页对应的那个物理页，读取到内存中，也就是说，重构一个逻辑页时只需要读取一个物理页，因此，基于页的方法具有很好的读操作性能。

图[page-based-method]基于页的方法示意图

图[page-based-method] 基于页的方法示意图

图[page-based-method]演示了基于页的方法的基本过程。在初始阶段，闪存固态盘中存在4个DBMS数据页DP1,DP2,DP3,DP4，这4个页被读入内存的DBMS缓冲区中。随后，这4个页发生了更新，变成脏页。当需要把缓冲区内容刷新到闪存中时，需要把4个页驱逐出缓冲区，刷新到闪存中，因此，缓冲区中的4个DBMS数据页，会被依次驱逐出缓冲区，固态盘上的4个页会被依次更新。总体而言，这个过程更新了4个数据页，导致了4个数据页回写到闪存的写操作。

基于页的方法和DBMS的存储管理模块是松耦合的，不需要修改存储管理模块，而是在DBMS和闪存之间增加一个中间层FTL来实现，FTL会负责维护从逻辑页到物理页之间的地址映射。FTL可以作为固态盘控制器中的一个硬件来实现，也可以作为操作系统的一个软件来实现。

在基于页的方法中，有两种类型的更新机制[NathG10]——就地更新和异地更新，二者的主要区别在于逻辑页是否总是被写入到存储介质的同一个物理地址中。当一个逻辑页需要被刷新到存储介质中时，对于就地更新而言，逻辑页会写入到存储介质中它原来被读取的位置，但是，对于异地更新而言，逻辑页会写入到一个新的物理页中。对于闪存而言，一般采用异地更新方式。

5.1.2     基于日志的方法

在基于日志的方法中，一个逻辑页通常被保存到多个物理页中。一旦逻辑页被更新，这些更新对应的日志就会首先被放入到内存的写缓冲区中。当内存的写缓冲区满的时候，这些更新会被写入到一个物理页中。因此，当一个逻辑页被多次更新时，它的更新日志可能会被保存到多个物理页中。相应地，当需要创建一个逻辑页时，需要从存储介质中读取多个物理页，然后进行合并得到一个逻辑页。

图[log-based-method]基于日志的方法示意图

图[log-based-method] 基于日志的方法示意图

图[log-based-method]演示了基于日志的方法的基本过程。在初始阶段，闪存固态盘中存在4个DBMS数据页DP1,DP2,DP3,DP4，这4个页被读入内存的DBMS缓冲区中。随后，这4个页DP1,DP2,DP3,DP4发生了更新，更新操作会被分别记录到日志DP1Log, DP2Log, DP3Log，DP4Log中。当需要把缓冲区内容刷新到闪存中时，只需要把日志DP1Log, DP2Log, DP3Log，DP4Log依次写入到闪存中的日志页中即可，缓冲区中的数据页DP1,DP2,DP3,DP4直接被删除，不需要写入到闪存。因此，这个过程虽然更新了4个数据页，但是，并不需要把4个数据页回写到闪存，而只需要向闪存中写入一个日志页，这就大大减少了闪存写操作的数量。

基于日志的方法和DBMS存储模块是紧耦合的，必须对DBMS存储模块进行修改，从而能够探测到一个逻辑页的更新，因为，只有DBMS内部的存储模块才能够及时探测到数据更新。

基于日志的方法，只会把一个逻辑页中发生变化的数据以更新日志的形式写入到缓冲区中，当缓冲区满时被刷新到闪存中。因此，和基于页的方法相比，当更新操作不是非常频繁时，基于日志的方法具有较好的写操作性能，但是，当更新操作非常频繁时，性能会降低许多，甚至还不如基于页的方法。此外，基于日志的方法的读操作性能较差，因为，当需要重构一个逻辑页时，由于更新日志很可能分散在多个不同的物理页中，这就需要从闪存中读取多个物理页进行合并得到一个逻辑页。

典型的基于日志的方法包括LFS(Log-structured File system) [RosenblumO92], JFFS (Journaling Flash File System) [Woodhouse01], YAFFS (Yet Another Flash File System) [Yaffs]和IPL(In-Page Logging) [LeeM07]，其中JFFS、YAFFS和IPL是面向闪存的方法。在LFS、JFFS和YAFFS中，一个逻辑页的更新日志可以被写入到闪存中任意的日志页中。而在IPL[LeeM07]中，更新日志必须被写入到闪存中特定的日志页中。

5.2   基于页的方法

基于页的方法和存储系统是松耦合的，它们通常借助于一个中间层FTL来实现，FTL会负责维护从逻辑页到物理页之间的地址映射。但是，现有的闪存FTL机制都是面向文件系统的，如果直接应用于DBMS，将无法发挥好的性能。因此，在闪存数据库应用中，必须研究面向DBMS的FTL机制。

5.2.1     面向文件系统的FTL机制无法直接应用于DBMS

FTL机制可以隐藏闪存的特性，让固态盘看起来像是一个虚拟的磁盘。因此，通过使用FTL方法，一个传统的基于磁盘的DBMS可以直接运行在固态盘上，而不需要任何修改。FTL机制提供了逻辑页到物理页的映射，在接收到来自DBMS发出的写请求以后，FTL会把该写请求导向到闪存中的一个处于擦除状态的空闲页上去执行；收到DBMS发出的读请求时，FTL会查找地址映射表，找到闪存中的物理页并读取数据。

在前面的第2章内容中，介绍了许多FTL机制[ChungPPLLS06][LeePCLPS07] [KimKNMC02] [KangJKL06]。但是，其中很多FTL机制并非是针对数据库负载模式而开发的，而是必须具备足够的通用性，从而能够支持各种类型的应用（尤其是文件系统）。这类主要面向文件系统的FTL算法如果直接应用到数据库负载上，将无法获得很好的性能。原因主要包括以下几个方面：

  • DBMS的负载和文件系统的负载具有很大的区别，前者具有更多的随机写操作。在许多情形下，文件系统的IO模式主要是读操作比较集中的负载，并伴有不频繁的文件顺序写操作，并且会表现出较好的空间和时间上的数据局部性。相反，数据库负载，尤其是OLTP负载，通常是随机分布的、很小数据量的写操作。虽然面向文件系统的FTL机制也考虑了随机写操作，但是，这些研究的重点还是在于从负载中区分出随机操作和顺序操作，然后对顺序操作进行重点性能优化。此外，虽然面向文件系统的FTL机制对随机写操作也设计了相应的优化策略，但是，文件系统中的随机写操作大都只是针对元数据，而且往往会表现出空间的局部性（LAST和SuperBlok等机制就充分利用了这个特性），而在执行典型的数据库负载时，DBMS所执行的写操作会分散到磁盘的整个物理地址空间[LeeM07]，由此也会带来更多的擦除操作。
  • MLC NAND闪存中存在特有的“耦合页问题”（paired page problem）[LeeKWCK09]。在MLC NAND闪存中，同一个存储单元中的多个位，会属于不同的页。对于一个两位的MLC NAND闪存而言，在文献[LeeKWCK09]中，作者把包含了来自同一个存储单元中的位的两个页称为“耦合页”。所谓的“耦合页问题”是指，在改变一个存储单元的某个位的状态时，如果发生断电，那么，这个存储单元中的其他位也会改变。这就意味着，在对一个页执行写操作的过程中如果发生了断电，不仅该页的写操作可能执行失败，由其他已经完成的写操作所写入到闪存中的其他页，如果与该页存在耦合页关系，也可能会被损坏，这破坏了数据库写操作的持久性。传统的针对磁盘的DBMS都可以保证写操作的持久性，也就是说，一旦写操作已经完成提交，此后即使发生了断电等意外情况，该写操作写入的结果都会被持久地保存。由于传统的DBMS是针对磁盘而不是闪存设计的，因此，也就不会考虑MLC NAND闪存中的“耦合页问题”（paired page problem）[LeeKWCK09]。因此，如果直接应用到闪存平台上，传统的DBMS就无法保证写操作的持久性，这会大大降低数据库系统的可用性。
  • 为了减少擦除操作的次数，FTL机制通常采用异地更新的方式，即对某数据项进行更新时，会把更新操作写到到新的空闲页中，并简单地把该数据项所在的原来的页设置为“无效”，旧数据就会被保留在原地，等到启动垃圾回收过程时才会被统一擦除。而对于传统的基于磁盘的DBMS而言，为了实现事务机制和灾难恢复机制，一般都会在执行更新操作的同时，把旧版本的数据记录在日志中。因为，这些基于磁盘的DBMS在设计时并不是针对闪存的特性设计的，不知道旧版本的数据可能仍然被保存在闪存的“无效”页中。由此带来的问题是，旧版本数据的重复存储，这既增加了不必要的写操作，也浪费了宝贵的闪存空间。
  • 数据库负载中包含了大量针对元组的更新操作，对于比较常用的混合FTL机制而言，每次更新操作都需要记录到日志块中，由于一个写操作的最小单元是一个页，因此，每次更新都要记录到一个空闲页中，由此带来的闪存空间开销也是很大的。而且，数据库元组的数据量通常都很小，每次对元组的更新都用空闲页来记录，也浪费了大量的闪存空间。

就目前的技术发展趋势来看，企业的大量数据库应用将会越来越多地部署到基于固态盘的存储系统上面。为了获得更好的数据库性能，非常有必要在成熟的、针对文件系统的FTL机制基础上，进一步研究针新的、对数据库负载的FTL机制。本书前面用大量篇幅介绍FTL机制，也是希望这些FTL基础研究的介绍能够有助于研究人员更好地设计开发面向DBMS的FTL机制。

5.2.2     面向DBMS的FTL机制

数据库负载的一个典型特性就是包含大量随机写操作，采用面向文件的FTL机制会带来大量的完全合并操作，需要高昂的垃圾回收代价。Gupta等人受到Translation Lookaside Buffer(TLB) [HennessyP03]的启发，提出了完全采用页级别映射的DFTL[GuptaKU09]。DFTL的核心思想很简单：绝大多数企业级别的工作负载，虽然包含大量分布在整个闪存物理空间的随机写操作，但是往往会表现出时间局部性，DFTL就是充分利用了闪存上有限的SRAM来存储最常用的映射，而其他比较少用的映射则保存在闪存上。

图[DFTL]DFTL机制

图[DFTL] DFTL机制

图[DFTL]给出了DFTL机制的设计方法。DFTL完全废除了日志块，只在闪存空间中设计了数据块和转换块。数据块中的“数据页”存储了数据，在读写操作期间会被不断更新；转换块中的“转换页”存储了逻辑地址到物理地址的映射信息。转换块大约只占到0.2%的闪存空间，从来不和数据块进行合并。整个逻辑地址到物理地址的映射集合，通常保存在闪存中的转换页内，被称为全局映射表。全局映射表通常较大，无法一次性放入SRAM，DFTL只把当前使用到得映射信息存放到SRAM中，这部分活跃的映射表被称为缓存映射表，每个映射表条目包含逻辑数据页编号DLPN和物理数据页编号DPPN。随着数据更新的不断发生，逻辑地址到物理地址的映射信息会不断发生变化，就需要修改转换页，而闪存实行的是异地更新，因此，各个新的转换页就会被分散存储到闪存中的不同位置。为了跟踪这些分散存储的转换页，DFTL设计了全局转换目录，并且保存在SRAM中，每个转换目录条目包含虚拟转换页编号MVPN和物理转换页编号MPPN。当外部读写请求到达时，如果请求的地址信息已经保存在SRAM中，就可以直接利用这个映射信息找到物理地址，到闪存中去读取数据。如果信息不存在于SRAM中，那么就需要从闪存中读取映射信息到缓存映射表中。随着读写操作负载的不断到达，读写操作所涉及的数据的地址空间分布也会不断演化，这就需要一些替换算法把SRAM中的一些映射条目替换掉，DFTL采用了分段LRU数组缓存算法。

DFTL具有以下几个方面的良好特性：（1）彻底消除了混合映射机制中存在的、代价高昂的“完全合并”操作，改进了随机写操作的性能；（2）充分利用了页级别的时间局部性来存储页面，这些页会被放在同一个数据块中被一起访问，这种机制就内在具备了对冷块和热块的区分，而不需要额外的机制来区分冷块和热块，因此可以更好地适应负载类型的变化；（3）更新操作可以在任何数据块上进行，因而提高了块利用率。作者利用一个金融机构的OLTP应用负载（包含大量随机写操作）进行测试，实验结果显示，平均响应时间改进了78%左右。作者还利用以读操作为主的TPC-H测试基准进行测试，实验结果显示，DFTL虽然引入了额外的开销，但是，仍然在平均响应时间方面改进了56%。

         DFTL机制的缺点是：虽然高效，却面临一个严重的可靠性问题，因为，如果系统发生崩溃，那么，所有在SRAM中被修改的信息将会丢失。在这种情形下，所有数据页中的备用区域，都需要被扫描，直到系统恢复到一个一致性状态。而且，随着闪存容量和密度的增加，这个重启延迟会变得令人无法接受。因此，当闪存要作为一个永久可靠的存储设备来用的时候，DFTL是不合适的。

5.3   基于日志的方法

各种面向闪存数据库的、基于日志的方法，都借鉴了已有的各种日志文件系统的原理（比如LFS、JFFS和 YAFFS）。下面首先介绍日志文件系统的原理，然后介绍几种面向DBMS的、基于日志的方法，包括LGeDBMS、A/P方法和IPL方法。

5.3.1     日志文件系统原理

日志文件系统根据原理可以划分成两大类：第一类是基于日志结构的日志文件系统，第二类是基于元数据的日志文件系统。表中给出了两种日志文件系统的特点比较。

表[log-file-system-comparison] 两种日志文件系统的特点比较

实现原理 优点 缺点
基于日志结构的日志文件系统 在磁盘上创建一个日志，并且跟踪记录文件内容的变化，任何文件的修改操作，都会以日志的形式追加写入到日志文件的尾部 当发生系统崩溃时，可以直接查找日志文件的尾部日志记录来处理崩溃 实现复杂，读性能差，存储空间的垃圾回收代价较大
基于元数据的日志文件系统 在磁盘上使用一个单独的区域来记录文件内容的更新，而且只会记录针对元数据的更新 日志是对正常的文件系统的扩展，容易实现；当系统发生崩溃时，只需要扫描少量日志记录就可以迅速恢复 当发生系统崩溃时，没有办法避免缓冲区内没有回写到磁盘的数据发生丢失的问题

上述两种日志文件系统中，基于日志结构的日志文件系统，采用了追加的方式写入日志记录，这种顺序写入方式比较适合闪存“异地更新”的特性，可以在闪存数据管理中得到较好的应用，因此，下面论述中的日志文件系统，仅指基于日志结构的日志文件系统。

基于日志结构的日志文件系统[RosenblumO92]采用日志的方式对文件进行管理，它会在磁盘上创建一个日志，并且跟踪记录文件内容的变化，任何文件的修改操作，都会以日志的形式被记录下来，即每次文件修改操作都会产生相应的日志，这些日志采用追加的方式写入磁盘中的日志文件，即每次都在日志文件的末端写入新的日志记录。通过遍历日志，就可以获得日志对应的文件的内容。

图[log-file-system]解释了日志文件系统的原理。假设这里按照时间顺序先后对文件内容进行了三次写操作，每次写操作都会产生一条日志，用来记录本次写操作的所有相关信息。下面按照时间顺序进行简单分析：

  • 在t1时刻，数据D1已经被写入到文件中，并产生了相应的日志记录（版本号为V1），这时通过扫描日志记录，可以重构得到文件的内容，即地址空间0~299里面的内容都来自版本号为V1的日志记录中的数据。
  • 在t2时刻，数据D2已经写入到文件中，并产生了相应的日志记录（版本号为V2），通过扫描日志记录，可以重构得到t2时刻文件的内容，即地址空间0~299里面的内容都来自版本号为V1的日志记录中的数据，而地址空间300~499里面的内容则来自版本号为V2的日志记录中的数据。
  • 在t3时刻，数据D3已经写入到文件中，并产生了相应的日志记录（版本号为V3），通过扫描日志记录，可以重构得到t3时刻文件的内容，即地址空间0~149里面的内容都来自版本号为V1的日志记录中的数据，而地址空间150~349里面的内容则来自版本号为V2的日志记录中的数据，地址空间350~499里面的内容则来自版本号为V3的日志记录中的数据。

图[log-file-system]日志文件系统原理

图[log-file-system] 日志文件系统原理

日志文件系统最大的优点是，具有极高的写性能，它可以把文件的修改操作以日志的形式顺序地写入磁盘，不需要额外的磁盘寻址开销，不仅加快了文件写入的速度，也加快了文件系统发生崩溃时的恢复速度。但是，日志文件系统也具有显著的缺点：（1）读性能差，因为文件的内容被分散存储到不同的日志记录中，需要在磁盘中扫描日志才能重构得到文件内容；（2）存储空间的垃圾回收代价较大。

5.3.2     LGeDBMS

文献[KimBLLJ06]提出了一个可用在基于闪存的嵌入式设备上的、微缩版本的DBMS——LGeDBMS，它借鉴了基于日志的文件系统[RosenblumO92]的设计原理，把整个数据库看成是一个单独的日志，所有的数据库更新操作都会被顺序地追加到日志的尾部。由于闪存实行的是异地更新，因此，基于日志的方法不会违反闪存的这种操作特性。而且，把固态盘用来写入追加日志，使得在执行写操作时可以充分利用固态盘优良的顺序写带宽。从而时间局部性就被转换成空间局部性，继而顺序读就被转换成随机读操作。这种转换有助于提升整体性能，因为，和磁盘不同的是，闪存可以提供相同的顺序读和随机读性能。下面解释上述两种转换的具体含义。如图[time-to-space-locality]所示，在t0时刻，日志中已经写入了三个物理闪存块B0,B1和B2，假设每个块只有四个页，在时间窗口[t0,t1]内，发生了一系列地更新U0,U1,U6,U9，其中，Ui中的i表示被更新页的LPN。所有的更新都会被顺序地追加到日志的尾部，更新U0,U1,U6,U9会被顺序追加到新的块B3中。四个更新U0,U1,U6,U9所涉及的页(LPN=0,1,6,9)，原本分别属于三个不同的块，LPN=0和LPN=1的页属于块B0，LPN=6的页属于块B1，而LPN=9的页则属于块B2。但是，可以看出，在更新后，属于时间窗口[t0,t1]内的更新U0,U1,U6,U9都被记录在同一个块B3中，所以说，时间局部性就被转换成空间局部性。对于一个顺序读取序列R0,R1,R2,R3而言（Ri表示读取LPN=i的页），原本LPN=0,1,2,3的四个页都属于同一个块B0，但是，经过四个更新U0,U1,U6,U9以后，LPN=2,3的两个页仍然属于块B0，而LPN=0,1的两个页目前已经属于另一个块B3，要完成顺序读取R0,R1,R2,R3，必须从块B0和块B3中分别读取对应的数据，所以说，顺序读被转换成随机读操作。

 图[time-to-space-locality]时间局部性转换成空间局部性图[time-to-space-locality] 时间局部性转换成空间局部性

5.3.3  A/P方法

为了让DBMS在闪存设备也可以获得理想的性能，文献[StoicaAJA09]也提出了一个基于日志的存储数据库页的追加打包算法（Append and Pack，简称“A/P”）。A/P方法在DBMS存储管理器的内部创建了一个抽象层，这个层位于逻辑数据组织和物理数据存储之间，可以为上层应用提供一个虚拟的块设备抽象。A/P方法把整个闪存设备看成一个日志结构，从缓冲区中被驱逐出来的、需要持久性存储的脏页，就会被顺序地追加写入到闪存中，并在内存中维护一个索引，这个索引就是数据库页ID和日志中的存储位置之间的映射。在发生数据更新时，闪存中之前版本的数据库页，不会被就地覆盖，而是在内存索引中在逻辑上被设置为“无效”即可。为了避免频繁的写操作，A/P方法会把脏页缓冲起来，等到满一个擦除块大小的时候，就顺序写入到和擦除块尺寸一样的闪存块中，从而优化写操作性能。

当可用闪存空间很低时，就无法继续执行追加页的操作，这时就必须回收那些被无效页占据的空间。A/P会把最近最少更新的逻辑页进行打包合并，打包方法是：从追加日志结构的头部开始，读取有效数据并打包，然后顺序地写回到追加结构的尾部。在通常情况下，一些有效页会分散到许多擦除块中，这就使得一个单独的打包操作可以回收大量的空间。

对于典型的OLTP负载而言，会包含频繁发生更新的“热数据”和很少发生更新的“冷数据”。作者研究发现，如果把具有类似更新频率的数据放置在一起，空间回收时就可以实现所需移动的页的数量最小化。为此，A/P方法设计了两个级别的数据集。第一个数据集存储了热的数据库页，而第二个数据集则存储了冷的数据库页。打包的方法是：从热数据集的头部开始读取有效数据，然后顺序地追加到冷数据集中，因为，对于那些已经到达热数据集头部的页而言，已经很长时间没有被更新过了，因此，最有可能成为冷数据。另外，冷数据也会存在更新，只不过更新频率比较低而已，当这种更新发生时，这个页会被再次像其他页一样被追加到热数据集的尾部。

A/P 方法的缺陷：该方法通过使用一个新的数据布局，把随机写操作替换成顺序写操作，并且会连续地把被驱逐的DBMS数据页写入到闪存空间中。DBMS数据页在闪存中的写入位置，会通过映射表被映射到具体的DBMS数据页。但是，这种方法不足以解决由于频繁写操作引起的闪存固态盘寿命问题，它只是简单地替换访问模式，并没有减少些操作的数量，因此，不能延长闪存固态盘的寿命。

5.3.4     IPL方法

5.3.4.1      IPL方法概述

正如文献[LeeKWCK09]的研究所指出的那样，基于日志的方法的优点是，不管什么写操作模式，都可以取得较好的性能，但是，也有明显的缺陷，主要表现在以下几个方面：

  • 无法避免许多小数据量的日志写操作。因为数据库负载中会包含很多的元组级别的更新，这类更新操作所涉及的数据量通常都很小；当频繁地发生这种小数据量的更新时，很快就会耗光空闲页，因此，就需要频繁地调用垃圾回收程序，带来许多擦除操作。一个更新操作的平均延迟，会随着代价高昂的擦除操作的频繁执行而增加，这就会成为整个数据库服务器的性能瓶颈；
  • 以牺牲读操作性能换取写操作性能的优化。当从数据库中读取的一个数据页的时候，当前版本的数据页必须被重新创建，方法是把日志中的更新记录全部应用到之前版本的旧数据页上面。因为和数据页相关的日志记录会被分散到日志的各个部分，因此，创建数据库页的最新版本时，需要扫描整个日志，代价很大；因此，这种顺序日志方法，虽然优化了写性能，却是以牺牲读性能为代价的，数据库的整体性能未必可以得到改善；
  • 基于日志的方法无法解决前面介绍过的“耦合页问题”。

为了克服上述基于日志的方法的缺陷，文献[LeeM07]提出了“页内日志”方法——IPL（In-page logging）方法，把数据和日志放在一起存储，即把一个数据页和它的日志记录存放在闪存的同一个物理地址空间中（存放在同一个擦除单元中），从而避免了在写事务日志时的额外写操作。IPL把每个块中的页划分成固定数量的数据页和日志页。一个逻辑页的更新日志，只会被写入到包含了这个逻辑页所对应的物理页的块中。因此，当重新创建一个逻辑页时，IPL就只需要读取数据页（物理页）和位于同一个物理块中的日志页。当块中没有可用的空闲日志页时，IPL会把块中的数据页和日志页进行合并，然后，把合并后的页写入到一个新的块中，旧的块就会被擦除和垃圾回收。IPL减少了重建一个逻辑页时需要从闪存中读取的日志页的数量，因为，由于存在合并操作，日志页的数量不会无限增长。IPL的性能和其他基于日志的方法是类似的，因为IPL继承了基于日志的方法的优点和缺点。

5.3.4.2      IPL方法的核心思想

IPL方法的核心思想主要体现在以下两个方面：

第一，把一个数据页和它的日志记录存放在闪存的同一个物理地址空间中，加快数据页重构速度。

由于闪存存在“写前擦除”的限制，即使对一个页中的某条记录进行更新，都会导致包含该更新的页的整体失效，需要写一个新版本的页到闪存中可用的已经擦除的空闲页中。为了避免这一点，IPL只会把页的更新以日志的形式写入到闪存中，而不是每次更新都写入整个页。

在传统的顺序日志方法中 (比如LFS)，所有日志记录都必须被顺序地写入到一个存储介质。但是，这种日志类型需要考虑的一个问题是，每当需要从数据库中读取一个页时，必须重构该页的最新版本数据，重构的方法是，把存储在日志中的更新记录应用到这个页的前一个版本上，从而得到该页的最新版本数据。由于属于这个数据页的日志可能是分散存储的，只有对整个日志进行扫描才可以找到所有相关的更新日志，因此，重构数据页的操作代价很大。

但是，闪存是纯粹的电子设备，不存在任何机械部件，分散的日志写操作不会产生明显的性能惩罚，因而，也就没有必要对日志记录进行顺序存储。所以，与传统的顺序日志方法不同的是，在IPL方法中，更新操作的日志记录并不会被顺序地追加到日志的尾部，而是分散地存储到不同的闪存空间中。IPL把数据页及其对应的日志记录保存在同一个闪存物理空间中，也就是放在同一个擦除块中，这种设计方法可以带来明显的好处——加快了当前版本数据页的重构速度，因为，只需要扫描同一个物理空间中的日志记录，而不需要扫描所有的日志记录。

第二，闪存读带宽比写带宽大得多，写操作和擦除操作比读操作代价高很多，可以设计方法尽量避免写操作和擦除操作，即使以增加读操作的代价为前提。

根据数据库中的“写前记录日志”（wrtie-ahead-logging，简称WAL）协议，更新操作的日志记录必须在写操作完成之前被写入到持久稳定的存储介质上（比如闪存）。而闪存的写操作的最小单元是页，即使是小数据量的更新也需要使用整个空闲页，空闲页用尽后还会启动垃圾回收过程，包含大量写和擦除操作。因此，为了记录日志而进行的频繁的、小量的闪存写操作，会带来明显的闪存开销。为了避免频繁的日志写操作，从而减少写操作和擦除操作的次数，IPL在内存中设置了缓冲区，更新日志会临时存放到内存缓冲区中，只有当缓冲区写满一页或者一个脏数据页已经被驱逐出缓冲区的时候，该日志记录才会被写入到闪存中。多个日志记录可以被一次性执行写操作，写入到闪存日志区域中，因此，就可以避免频繁的写操作和擦除操作。但是，在IPL方法中，需要对读操作进行重新定义，增加了读操作的代价。当一个数据页需要从闪存中读取时，该数据页的当前版本必须被临时创建，创建的方法是：从闪存中读取该数据页对应的更新日志记录，然后，把这些更新应用到之前版本的数据页上。这种针对读操作的新定义，很显然会增加读操作的开销。但是，大量实验证明，这种方法最终是值得的，它可以大幅度改善数据库的整体性能，因为大大减少了写和擦除操作。

5.3.4.3    IPL的设计

图[IPL]IPL的设计

图[IPL] IPL的设计

如图[IPL]所示，在IPL方法中，闪存的每个擦除单元都被分割成两个部分，即数据区域和日志区域，前者包含若干数据页，后者包含若干日志页。在内存缓冲区中，每个数据页（逻辑页）在“变脏”的时候（即发生了更新），IPL存储管理器就会为之临时分配一个日志页，用来记录该页发生的更新。如果内存日志页中的日志记录满了，或者当一个脏数据页被驱逐出缓冲区时，内存中与该页对应的日志记录就会被写入到闪存中，即被写入到闪存中与该数据页对应的日志页中，这样，数据页和它的更新日志记录就可以存放到闪存的同一个擦除单元中，加快数据页的重构速度。由于有了内存中的日志页作为缓冲区，属于一个数据页的多个更新日志记录可以被一次性写入到闪存中，因此，就可以避免频繁的擦除操作。当内存中的日志记录被写到闪存的日志区域以后，这个内存中的日志页就可以释放掉。需要注意的是，当一个脏页被驱逐出内存时，没有必要把这个脏页的内容写入到闪存中，因为，所有针对这个脏页的更新，都已经写入闪存中的日志。因此，闪存中前一版本的数据页没有发生任何变化，只是在日志中增加了更新日志记录。当一个数据页需要从闪存中读取时，需要临时创建该数据页的当前版本，方法是，从闪存中读取该数据页对应的更新日志记录和前一版本的数据页，然后，把这些更新应用到前一版本的数据页上。

一个内存中的日志页，只能存储有限数量的日志记录，当一个日志页满时，其内容就会被刷新到闪存中相应的日志页中。由于闪存中每个擦除单元的可用日志页的数量都是有限的，如果某个擦除单元中的数据页更新非常频繁，那么，这个擦除单元就会很快消耗完日志页。这个时候，IPL存储管理器就会触发一个进程，对日志页和与之关联的数据页进行合并。如果在一个擦除单元中已经不存在可用的日志页，IPL存储管理器就会分配一个空闲的擦除单元，然后，把更新日志应用到之前版本的数据页，从而得到最新版本的数据页，并把它写入到新的擦除单元，最后，释放掉旧的擦除单元。

5.3.4.4      IPL方法的缺陷

IPL方法的缺陷表现在以下几个方面[LeeKWCK09]：

  • 首先，没有解决小数据量的日志随机写操作问题。虽然IPL方法设置了缓冲区避免了频繁的日志写问题，改进了性能，但是，由于日志和对应的数据页要一起存放，这意味着把顺序日志写操作转换成了随机日志写操作，留下了更大的随机写问题，而相关研究[BouganimJB09]已经证明随机写会严重恶化闪存性能；
  • 其次，当写请求集中在特定的块中时，IPL方法可能表现出很差的性能。因为，这种情况下，一个块的更新操作会很快耗光日志区间中的空闲页，然后启动垃圾回收过程，执行数据块和日志块的合并操作，就会涉及大量的写操作和擦除操作，代价很大；
  • 再次，IPL要求针对某个数据页的更新操作的日志记录只能被写入到闪存中的日志区域，而且必须被写入到与该数据页相关联的日志块中。由于MLC NAND闪存要求对一个页进行顺序写入，因此，IPL这种日志写入方式就会导致一个块中的许多空闲页可能无法被利用，造成不必要的空间浪费；
  • 另外，IPL提出了它自己的存储管理器，必须为每个数据页分配一个称为“内存日志页”的内存空间。如果一个数据页被缓冲区管理器驱逐，只需要把内存中的日志页写入到闪存的日志区域，而不需要写入整个数据页。因为日志页要比数据页小，因此，IPL存储管理器可以明显减少页写操作。但是，如果针对一个数据页的多个日志页被写入到闪存的日志区域，那么，当需要从闪存中读取一个数据页时，就需要从闪存中读取多个日志页。
  • 最后，无法解决“耦合页问题”。

5.3.5     ICL方法

Roh等人[RohLP10]提出了一种新的基于日志的方法，这里我们称它为“ICL方法”，因为，该方法采用了ICL（InCremental Logging）日志。ICL方法是为了解决OLTP应用环境下存在的“面向写的问题”，即频繁的写操作会缩短闪存固态盘寿命的问题。ICL方法的目标就是尽量减少针对闪存的写操作的数量，而且以适当增加读操作为代价。该方法通过ICL日志机制把随机写操作转换成顺序写操作，同时减少了页写操作。

5.3.5.1      ICL方法概述

ICL方法设计了一个DBMS写操作优化层，这个层包含了一个日志缓冲区（称为“写操作优化缓冲区”）、相应的日志空间和一个内存映射表。写操作优化缓冲区WOB（Write Optimized Buffer）位于DBMS缓冲区和固态盘之间，可以用来减少页写操作。写操作优化缓冲区会收集每个DBMS数据页的脏区域，并把这个脏区域转变为日志。这个日志包含了两个部分，即日志头部和日志内容。日志头部包含了用来确定被驱逐DBMS数据页的信息，以及DBMS数据页内部被更新区域的<位移,尺寸>。日志的内容，就是DBMS数据页中被更新的元组或者被更新的部分。当写操作优化缓冲区满时，它会把日志刷新到称为“ICL日志空间”的闪存日志空间中。在ICL机制中，和一个DBMS数据页对应的ICL日志中的日志内容是递增的，这样，在读取一个最新的DBMS数据页时，只需要读取一个日志页，这个日志页包含了针对这个DBMS数据页的最新日志。ICL方法设计了映射表来维护从每个DBMS数据页到与之对应的日志页的映射。很显然，每个被驱逐的DBMS数据页所生成的更新日志的大小，会明显小于整个DBMS页的大小。因此，写操作优化缓冲区在有限的内存空间内就可以缓存大量的DBMS页写操作。

5.3.5.2      ICL日志

这里将通过对传统日志和ICL日志的比较，来阐释ICL日志的优点。假设对于缓冲区中的4个数据页DP1,DP2,DP3,DP4，每个数据页上面都发生了一次更新，采用传统日志的方法，会为4个数据页分别生成4个日志DP1Log1, DP2Log1, DP3Log1, DP4Log1，然后，DP1,DP2,DP3,DP4上又发生一次更新，又生成4个日志DP1Log2, DP2Log2, DP3Log2, DP4Log2。如图[ICL-log-traditional]所示，当需要把缓冲区中的内容刷新到闪存中时，系统把DP1Log1, DP2Log1一起写入到闪存中的日志页LP1中，把DP3Log1, DP4Log1一起写入到闪存中的日志页LP2中，把DP1Log2, DP2Log2一起写入到闪存中的日志页LP3中，把DP3Log2, DP4Log2一起写入到闪存中的日志页LP4中。这里假设日志页LP1,LP2,LP3,LP4中剩余的空间被上述4个数据页以外的其他数据页的日志所占用。可以看出，当采用传统的日志方法时，在对4个数据页发生8次更新时，只会导致4个日志页的写操作。

图[ICL-log-traditional]传统的日志写入过程示意图

图[ICL-log-traditional] 传统的日志写入过程示意图

采用传统的日志时，与某个DBMS数据页对应的日志，可能会被分散到不同的日志页中，引起额外的读取代价。比如，在图[ICL-log-traditional]中，与数据页DP1对应的日志DP1Log1和DP1Log2，分别被分散存储在两个日志页LP1和LP3中。这样，在读取数据页DP1的最新版本时，就需要从闪存中读取原来旧版本的DP1和两个日志页LP1和LP3，从而获得旧版本的DP1和两个更新日志DP1Log1和DP1Log2，然后对三者进行合并得到新版本的数据页。这种方法在读取一个数据页的当前版本时，需要较高的读取代价。

ICL日志可以较好地解决这个问题。一旦写操作优化缓冲区WOB要把缓冲区中的日志刷新到闪存中的一个新的日志页中，它就会把闪存中与该DBMS数据页对应的之前的日志拷贝到内存中。然后，WOB把当前的日志和原来的日志一起写入到闪存中新的日志页中去。如图[ICL-log]所示，WOB在执行第一次刷新操作时，把属于DP1的日志DP1Log1和属于DP2的日志DP2Log1写入到闪存中的LP1日志页中。同理，还需要把分别属于DP3和DP4的日志DP3Log1, DP4Log1写入到闪存中的LP2日志页中。在第一次刷新操作中，不会引起对之前日志的拷贝，因为，DP3和DP4不存在之前的日志。但是，在第二次刷新操作中，WOB会拷贝之前的日志，因为，它必须把分别属于DP1和DP2的日志DP1Log2, DP2Log2写入到闪存中，而DP1和DP2在LP1中已经存在之前的日志DP1Log1和DP2Log1。因此，需要首先把闪存中之前的日志DP1Log1和DP2Log1拷贝出来，然后再把DP1Log1和新日志DP1Log2一起写入到闪存中的日志页LP3中，并把DP2Log1和新日志DP2Log2也一起写入到闪存中的日志页LP3中。同理，在日志页LP2中的DP3和DP4的日志，即DP3Log1, DP4Log1，也会被拷贝出来，DP3Log1和DP3Log2会被一起写入到闪存的日志页LP4中，DP4Log1和DP4Log2也会被一起写入到闪存的日志页LP4中。

图[ICL-log]ICL日志写入过程示意图

图[ICL-log] ICL日志写入过程示意图

虽然一个ICL日志的大小是不断增加的，但是仍然具备减少页写操作的能力。减少页写操作的机制，就要把可能多的DBMS数据页写操作转换成相对较小的日志，并且一次性把这些日志刷新到闪存的一个日志页中。通过这种方式，许多针对DBMS数据页的写操作，都可以被缩减成为一个日志页写操作。在ICL中唯一发生变化的是，对于每次刷新操作，日志的大小都是不断增加的。只要一个ICL日志的大小还小于一个DBMS数据页，就仍然可以获得性能收益。如果一个ICL日志的大小增加到不会带来收益的时候，就应该执行ICL合并操作。已经增加到足够大的ICL日志，会被合并到相应的DBMS数据页中，并释放回收ICL日志空间以供后续使用。释放回收ICL日志空间的过程，并不需要实际的页写操作，因为，日志页只需要被逻辑地设置为失效，根本不需要物理的重写操作。

这里需要关注的一个核心问题是，拷贝之前的日志这个过程到底需要多大的页读代价。在最坏的情形下，在每次需要把新的日志刷新到闪存中时，可能在闪存中都已经存在与之对应的之前的日志，而且都是存储在不同的日志页中。即使在这种最坏的情形下，由拷贝操作引起的额外读取代价，不会大于日志页的最大读取数量，即WOB刷新到闪存中的新日志的总数量（等于被驱逐的DBMS数据页的数量）。和采用传统日志的方法以及IPL方法相比，ICL方法额外的读代价相对较小。

5.3.5.3      采用ICL日志以后读取DBMS数据页的过程

采用ICL日志以后，读取一个DBMS数据页的最新版本的过程，可以按照下面的方法进行。首先，写操作优化层WOB读取DBMS数据页，如果这个DBMS数据页存在相应的ICL日志，它就读取包含这个ICL日志的日志页。其次，它会从这个日志页中抽取属于该DBMS数据页的ICL日志。再次，检查WOB中的日志，如果存在属于该DBMS数据页的日志，则这些日志也会被抽取出来，它们和来自日志页的ICL日志一起被刷新到这个DBMS数据页中。最后，DBMS数据页被读取到DBMS缓冲区中，得到该页的最新版本。

采用ICL日志以后，读取最新版本DBMS数据页的过程的代价，要比采用传统的日志低许多。在采用ICL日志的情况下，这种读取过程只需要读取一个日志页。在图[ICL-log] (b)中，读取每个DBMS数据页最新版本时，都只需要读取一个日志页，比如，读取数据页DP1时，只需要读取一个日志页LP3，因为，属于DP1的日志DP1Log1和DP1Log2都存放在日志页LP3中；同理，读取数据页DP2，DP3和DP4的最新版本时，也只需要分别读取日志页LP3，LP4和LP4。

5.4   基于页差异的日志方法

Kim等人[KimWS10]提出了基于页差异的日志方法——PDL（page-differential logging）。一个页差异是指闪存中的原始页和内存中的当前页之间的差异。下面首先给出PDL方法概述，并给出一个实例，然后介绍该方法的设计原则。

5.4.1     PDL方法概述

在PDL方法中，一个逻辑页会被存储成闪存中的两个物理页，即一个原始页和一个差异页。原始页包含了整个逻辑页的数据（它可能是旧版本数据，因为逻辑页可能会在得到原始页后发生更新），差异页包含了原始页和当前逻辑页之间的差异部分。闪存中的一个差异页，是一个物理页，但是，这个物理页可以包含来自多个逻辑页的差异部分。因此，多个逻辑页对应的差异页（假设每个差异页的大小都小于一个闪存物理页），可以被存放在同一个物理页中，构成一个大的差异页。因此，某个逻辑页对应的差异页，可能并不是一个完整的物理页，而只是一个物理页中的一个片段。

当需要计算差异页时，只需要从闪存中读取原始页，并把原始页和内存缓冲区中的当前逻辑页进行比较，计算得到差异部分，然后把差异部分写入到内存写缓冲区中，当缓冲区满时再把这些差异内容写入到闪存中。

当需要从闪存中重构一个逻辑页时，需要从闪存中读取两个页，即一个原始页和一个差异页，然后，把二者进行合并得到一个逻辑页。

PDL方法和基于页的方法、基于日志的方法都有很大的不同，主要体现在以下几个方面：

（1）基于页的方法会把整个逻辑页（包括变化和没有变化的数据）都写入闪存。基于日志的方法会把针对这个逻辑页的所有更新都以更新日志的形式写入闪存，这意味着，如果一个数据项发生了多次更新，就会向闪存写入多条更新日志。实际上，在重构一个逻辑页时，如果按照日志写入闪存的时间顺序进行反向扫描，最先扫描到的更新日志肯定对应着数据的最新版本，其他旧版本的更新日志就是无用的，根本就不需要扫描。存储这些旧版本的更新日志，不仅浪费更多的闪存空间，也增加了重构逻辑页时的闪存扫描开销。PDL方法则和基于页的方法、基于日志的方法这二者具有较大的不同。PDL方法可以通过计算得到差异页，而不需要维护所有的更新日志，也就是说，即使一个逻辑页被更新过许多次，PDL方法也只会把逻辑页和原始页的差异部分写入到差异页中。而且，PDL方法只计算一次差异，也就是当更新后的页需要被刷新到闪存中时才去计算一次差异，这要比基于日志的方法节省很多闪存存储空间。例如，假设一个逻辑页中的某个数据项在内存中更新过了两次，先从aaaaaa更新到bbbbba，然后再更新到bcccba。基于日志的方法会记录两个变化bbbbb和ccc，而差异页中只会包含差异内容bcccb。此外，PDL方法在计算差异时，只需要从闪存中读取原始页到内存缓冲区中，把原始页和内存中的当前页进行比较，就可以计算得到差异内容，这个过程的代价相对较小，因为，闪存中读操作的速度要远快于写操作和擦除操作的速度。

（2）当从闪存中重构一个逻辑页时，PDL方法比基于日志的方法需要更少的读操作，因为，PDL方法至多需要读取两个页，即一个原始页和一个差异页（即包含差异的一个页）。而基于日志的方法则可能需要读取多个物理页，因为，一个逻辑页对应的更新日志内容可能被分散存储在多个物理页中，从闪存中重构一个逻辑页时，需要从多个物理页中读取更新日志的内容，然后进行合并得到逻辑页。

（3）当需要把一个更新后的逻辑页刷新到闪存中时，PDL方法比其他两种方法需要更少的写操作，因为，PDL方法只写入差异部分的内容。此外，PDL也改善了闪存的寿命，因为，更少的写操作意味着更少的擦除操作。

（4）PDL方法和DBMS存储管理模块是松耦合的，而基于日志的方法是紧耦合的。基于日志的方法需要修改DBMS的存储模块，这样才能保证及时探测到系统中发生的数据更新，因为，只有DBMS的内部存储模块才能够探测到这些数据变化。而PDL方法不需要修改DBMS的数据存储模块，因为，它是在DBMS存储模块的外部计算数据差异，只需要对闪存中的原始页和内存中的当前页进行比较，即可计算得到差异。

5.4.2     PDL方法的一个实例

图[PDL]显示了一个PDL的例子，假设有一个逻辑页p，它在闪存中的原始页用base_page(p)表示，闪存中的原始页和内存中的当前页之间的差异用differential(p)表示，写入到闪存中的差异页用page_differential(p)表示。图[PDL(a)]显示了在内存中的逻辑页l1和l2的初始状态，即从闪存中读取物理页p1和p2，放入内存，分别得到逻辑页l1和l2。

图[PDL(a)]内存中逻辑页的初始状态

图[PDL(a)] 内存中逻辑页的初始状态

图[PDL(b)]显示了逻辑页l1和l2发生更新后计算和存储差异页的过程。当l1和l2需要被刷新到闪存中时，就需要计算和存储差异页，具体而言，需要执行下面的三步操作：

（1）从闪存中分别读取与逻辑页l1、l2对应的原始页base_page(l1)（即p1）、base_page(l2)（即p2）；

（2）把逻辑页l1与它的原始页base_page(l1)进行比较，计算得到逻辑页l1的差异部分differential(l1)；把逻辑页l2与它的原始页base_page(l2)进行比较，计算得到逻辑页l2的差异部分differential(l2)；

（3）把差异内容differential(l1)和differential(l2)分别写入到内存的写缓冲区中；当缓冲区满的时候，缓冲区中的这些差异内容就会被写入到物理页p3中，把差异内容differential(l1)写入p3以后可以得到与逻辑页l1对应的差异页page_differential(l1)，同理，把差异内容differential(l2)写入p3以后可以得到与逻辑页l2对应的差异页page_differential(l2)，也就是说，同一个物理页p3中包含了来自两个不同逻辑页l1和l2的差异页，即page_differential(l1)和page_differential(l2)。

 图[PDL(b)]逻辑页发生更新后计算和存储差异页的过程

图[PDL(b)] 逻辑页发生更新后计算和存储差异页的过程

图[PDL(c)]显示了从闪存中重构逻辑页l1的过程，即把逻辑页l1对应的原始页base_page(l1)（即p1）和物理页P3中与逻辑页l1对应的差异页内容page_differential(l1)从闪存中读取出来，进行合并后就可以得到逻辑页l1。

图[PDL(c)]重构逻辑页的过程

图[PDL(c)] 重构逻辑页的过程

5.4.3     PDL方法的设计原则

为了保证获得好的读写操作性能，PDL方法在设计时遵守了三个原则，这些原则克服了基于页的方法和基于日志的方法的缺点，具体如下：

  • 原则1（只写入差异）：当一个逻辑页需要被刷新到闪存中时，只写入差异部分；
  • 原则2（至多写入一个页）：当一个逻辑页需要被刷新到闪存中时，至多写入一个物理页，即使这个逻辑页在内存中已经被多次更新；
  • 原则3（至多读取两个页）：当从闪存中重新创建一个逻辑页时，至多需要读取两个物理页。

PDL方法完全符合上述三条设计原则，具体如下：

首先，在PDL方法中，当一个更新过的逻辑页需要被刷新到闪存中时，通过比较内存中的当前逻辑页和闪存中的原始页之间的差异，就可以计算得到差异页，然后把差异页写入到写缓冲区中，当缓冲区满时再写入到闪存。因此，PDL方法符合“只写入差异”的原则。

其次，当一个逻辑页只是被简单地更新时，PDL方法只会更新内存中的逻辑页，而不会记录日志，直到被更新的逻辑页需要被写入到闪存中时，才去计算得到差异页并写入闪存。因此，PDL方法满足了“至多写入一个页”的原则。理论上，差异部分的大小可能会大于一个物理页。但是，实际上只有当一个页中的大部分都被更新时，相应得到的差异页的大小才会比一个物理页大。这种情况还是可能发生的，因为，差异页不仅包含更新后的数据，而且包含一些元数据，比如位移和长度。在这种情形下，PDL会抛弃被创建好的差异页，并且把更新过的逻辑页自身写入到闪存中作为一个新的原始页，从而满足“至多写入一个页”的原则。在这种情形下，PDL就会演变成为和基于页的方法一样。

最后，当需要从闪存中重新构建一个逻辑页时，PDL方法可以从闪存中读取该页对应的原始页和差异页，然后，把原始页和差异页进行合并得到逻辑页。在一些情况下，如果逻辑页在原始页生成后没有发生过更新，那么，PDL方法只需要读取一个物理页，即原始页，而不需要读取差异页。也就是说，PDL方法至多需要读取两个物理页，因此，PDL符合“至多读取两个页”的原则。

当闪存中不存在更多空闲空间的时候，废弃的页就会被垃圾回收，PDL方法会选择一个块进行垃圾回收。由于块中可能包含有效的原始页或者差异页，因此，在擦除块之前，PDL方法会把那些有效页转移到一个新的块中，这些新块是为垃圾回收过程保留的。但是，对于差异页而言，PDL方法只把多个有效的差异页转移到一个新的差异页中，也就是相当于执行了压缩。PDL方法比基于页和基于日志的方法需要更少的写操作，因为，它满足了“只写入差异”和“至多写入一页”的原则。因此，PDL方法要比其他方法包含更少的垃圾回收操作，从而可以取得更好的性能。

5.5   StableBuffer

在闪存存储管理中，如果要使用基于日志的方法（比如IPL）和PDL方法，通常需要通过下面两种方式中的一种：第一种方式，绕过FTL机制，直接对底层的闪存芯片进行访问；第二种方式，修改闪存设备的驱动程序，也就是需要修改FTL机制，从而让FTL机制提供对日志的支持。但是，对于商业化的闪存设备而言，这两种方式并非总是可以做到的，因为，FTL机制通常固化封装在闪存设备内部，无法绕开FTL机制直接访问底层的闪存芯片，也无法对FTL机制进行修改。因此，这就使得基于日志的方法的应用受到一定的限制。

针对这个问题，Li等人[LiXCH10]提出了StableBuffer，它可以充分利用独特的闪存设备写模式，来优化写操作集中的DBMS应用（比如OLTP）的性能。StableBuffer可以作为DBMS缓冲区管理器的一个插件模块，它对于底层的闪存设备而言也是透明的，因此，可以直接应用到闪存数据库中。

5.5.1     StableBuffer的基本原理

一些关于闪存数据库的IO性能的研究（比如文献[BouganimJB09][ChenKZ09]）表明，闪存设备的写操作性能，不仅和简单的参数有关，比如访问类型（顺序或随机）和粒度（页的大小），而且还和“写模式”紧密相关。所谓的写模式，是指一个写操作序列所具备的特征，比如，如果一个写操作序列属于顺序写模式的一个实例，那么，这个序列中的所有写操作在地址空间上是顺序执行的。测试基准uFLIP的结果[BouganimJB09]显示，一个普通的写操作，如果随机地写入到整个闪存空间，那么就会表现出较差的性能，比如OLTP应用中的写操作通常就是随机的，会很容易成为闪存设备上的性能瓶颈。但是，确实存在几种“不是那么随机”的写模式，通过利用闪存设备的写操作局部性和写操作并行性，仍然可以获得较高的性能。典型的两种模式如下：

  • 集中写：是指只针对一个集中区域的随机写操作。这里所谓的“集中区域”，是指逻辑地址空间中的一个小区域。例如，一个预分配的小于4MB的文件内部，就可以看成是一个集中区域。
  • 分区写：是指分区顺序写操作。例如，一个写操作序列“6,21,7,22,8,23,…”，就是分区写模式的一个实例。这种写操作序列表面上看起来类似于随机写，但是，实际上，它是两种顺序的写操作序列的混合，即序列“6,7,8…”和序列“21,22,23…”的混合，这两个序列对应着地址空间中的两个分区。

表[uFLIP-IO-pattern]给出了在两种不同的写模式下面的写操作响应时间，包含了在两种闪存设备上测量得到的顺序和随机写操作时间[BouganimJB09]。可以看出，和普通的、非高效的随机写操作相比较而言，这些闪存设备具有三种高效的写模式，即顺序写、集中写和分区写。比如，对于Mtron SATA 7035-016而言，普通的随机写操作的延迟高达9ms，而顺序写的延迟只有0.4ms，集中写和分区写这两种特殊类型的随机写操作的延迟也分别只有0.8ms和0.6ms。

表[uFLIP-IO-pattern] 两种固态盘上的写操作响应时间

固态盘产品品牌型号 顺序写

(ms)

 随机写
普通写(ms) 集中写(ms) 分区(ms)
Mtron SATA 7035-016 0.4 9 0.8 0.6
Samsung MCBQE32G5MPP 0.6 18 0.9 1.2

为了充分利用上述三种高效的写模式的优势，StableBuffer方法在设计时（如图[StableBuffer-overview]所示），采用了一个闪存中预分配的专用临时存储空间，称为“StableBuffer”，每当DBMS发生页写操作时，不是立即把该页写入到闪存中的实际目标地址，而是把该页临时写入到闪存中的StableBuffer中。然后，采特定的方法对StableBuffer中的写模式进行识别，当探测到高效的写模式时，再把高效的写模式刷新到闪存中的目标地址中。但是，这里需要注意一个问题，有一些写操作序列可能本来就属于高效的写模式，很显然，这些写操作不应该被缓存到StableBuffer中来探测发现高效的模式，而是应该直接被写入到闪存的目标地址中。对于这个问题，StableBuffer方法假设一个DBMS缓冲区管理器是足够智能的，可以识别这些属于高效写模式的事务，并且确定如何高效地响应它们的读写请求。已有的研究文献（比如DBMIN[ChouD85]），已经证明了这点是可以做到的，即可以在DBMS缓冲区管理器中捕获这些属于高效写模式的事务。因此，和足够只能的缓冲区管理器进行合作，就可以避免在采用StableBuffer时对顺序写操作模式造成的性能恶化。

现在来解释一下为什么StableBuffer方法可以获得更好的性能。让我们来考虑一个在Mtron SATA7035-016闪存设备上的页写操作，该设备的写操作性能参数可以参见表[uFLIP-IO-pattern]。采用StableBuffer方法以后，把一个页p写入到闪存的目标地址，需要包含两个属于高效模式的写操作和一个随机读操作：

  • 第一个写操作是指把页p写入到闪存中的StableBuffer中。由于StableBuffer是一个比较小的集中区域，随机写入和顺序写入一样快，因此，这个写操作是一种高效的写操作。
  • 第二个写操作是指把页p刷新写入到闪存中的目标位置。因为在StableBuffer方法中，发生刷新操作时，会把探测到高效的模式刷新写入到闪存中，因此，这个写操作也是一种高效的写操作。
  • 一个随机读操作是指从StableBuffer中读取页p。因为，在StableBuffer方法中发生刷新时，必须从闪存的StableBuffer中读取一个页，然后把它写入到闪存的目标地址。

基于表[uFLIP-IO-pattern]的测量结果，两个高效的写模式的最差的代价是0.8+0.8=1.6ms。随机读操作通常要比一个顺序写操作代价小，也就是小于0.4ms。因此，上述过程的总代价大约是1.6+0.4=2.0ms。另一方面，如果我们没有采用StableBuffer方法，而是直接把页p从DBMS缓冲区中刷新到闪存的目标地址，它往往很可能是一个随机写操作，代价会高达9ms。

综上所述，虽然StableBuffer把同一个页执行了两次写入操作和一个随机读操作，但是，由于这两个写操作遵循了高效的写模式，因此，总代价仍然要比不采用StableBuffer直接刷新的策略改进了4.5倍。

5.5.2     StableBuffer的设计位置

StableBuffer的作用就是临时缓冲和收集写操作，从而探测和发现一些高效的写模式，比如，顺序写、集中写和分区写，因此，一个很容易想到的思路是，在内存中设置一个写操作缓冲区，对随机写操作进行临时缓存，也就是说，写缓冲区用作一个“写操作收集器”来收集写操作，并记录它们的顺序，用来进行性能优化。但是，这种方法存在两个方面的局限性。首先，需要消耗可观数量的缓冲区空间，而这些空间本来可以分配给DBMS的，这就会明显牺牲读操作的性能，并且会让缓冲区管理变得更加复杂。其次，由于内存是易失性存储介质，因此，如果采用强制的缓冲区策略，那么，当一个事务提交时，缓冲区中的写操作必须被强制地写入到稳定的存储器中；而如果采用非强制的缓冲区策略，则又必须提供一些额外的机制（比如日志），来保证写操作的持久性。

基于上述原因，StableBuffer在设计时，并没有被放在内存缓冲区中，而是在闪存中专门开辟一个小的临时空间。StableBuffer可以放在为DBMS存储保留的空间中，或者，如果DBMS存储是以文件的形式进行管理的话，StableBuffer也可以被简单地实现为一个预先分配的临时文件。这个小的临时空间，就可以被看作是一个“集中区域”，测试基准uFLIP的结果[BouganimJB09]显示，对于大多数闪存设备而言，针对一个集中区域（大小为4MB-16MB）的随机写操作，几乎和顺序写操作的速度一样快。因此，为了获得高效的写操作性能，StableBuffer的大小被限制为一个集中区域的大小，即4MB-16MB。

图[StableBuffer-overview]StableBuffer方法示意图

图[StableBuffer-overview] StableBuffer方法示意图

5.5.3     StableBuffer管理器

5.5.3.1      StableBuffer管理器的体系架构

图[StableBuffer-Manager-Architecture]显示了StableBuffer管理器的体系架构，主要包括以下几个组成部分：读取器（Reader）、写入器（Writer）、刷新管理器（Flush Manager）、模式识别器（Pattern Recognizer）、StableBuffer转换表（StableBuffer Translation Table）和槽位图索引（Slot Bitmap）。

StableBuffer管理器的各个组成部分的主要功能如下：

  • 读取器：负责响应从闪存中读取数据的请求；
  • 写入器：负责完成把DBMS缓冲区中被驱逐的页写入到闪存的过程；
  • 模式识别器：负责对临时存储在StableBuffer中的页进行模式识别，从中探测发现一些高效的写模式，比如顺序写、集中写和分区写；
  • 刷新管理器：负责把临时存储在StableBuffer中的页，以高效的写模式，刷新到闪存的目标地址中；
  • StableBuffer转换表：负责维护页的目标地址D到StableBuffer中的槽O的映射；
  • 槽位图索引：用来维护StableBuffer中的所有槽的状态信息，即可用或不可用。

图[StableBuffer-Manager-Architecture]StableBuffer管理器的体系架构

图[StableBuffer-Manager-Architecture] StableBuffer管理器的体系架构

5.5.3.2      StableBuffer管理器的数据结构

在介绍StableBuffer管理器的具体操作之前，需要了解一下StableBuffer管理器中使用到的两种数据结构，即StableBuffer转换表和槽位图索引。

（1）StableBuffer转换表

StableBuffer包括许多个槽（slot），每个槽可以容纳一个页，例如，给定一个4MB的StableBuffer，一个页大小是4KB，那么，StableBuffer就可以包含1024个槽。StableBuffer转换表是一个内存中的表，维护了StableBuffer空间里的槽编号和目标页地址这二者之间的映射。例如，如果一个页的目标地址是0x123456ab，它被存储在StableBuffer的第32个槽，那么，StableBuffer转换表中就会有一个条目为<0x123456ab,32>。图[StableBuffer-Manager-Architecture]中的StableBuffer转换表示例性地给出了三个条目，即<0x123456ab,32>、<0x1234579a,37>和<3452a8cd,342>。在执行页的读写操作时，StableBuffer读取器和写入器经常需要根据一个页的目标地址在StableBuffer转换表中进行查找，以判定该页是否在StableBuffer中以及在什么位置。为了支持基于目标页地址的高效的页查找，StableBuffer转换表被设计成一个哈希表，哈希表的键是一个页的目标地址。

（2）槽位图索引

槽位图索引负责维护StableBuffer中所有槽的状态信息，从而可以快速查找StableBuffer中的可用槽。槽位图索引中的每个位，代表了一个StableBuffer槽的状态，“1”表示相应的槽是可用的，“0”表示已经被占用。为了进一步加速可用槽的查找过程，StableBuffer还维护了一个可用槽的指针来指向下一个可用槽。

（3）额外的元数据

StableBuffer转换表和槽位图索引等数据结构都是在内存中维护的，但是，内存是易失性存储介质，断电或系统崩溃时就会丢失信息，因此，为了保证数据库数据的一致性，能够在系统发生失败时恢复到正确的状态，StableBuffer还设计了一些额外的元数据，比如目标地址和时间戳。

额外的元数据会和每个页一起被存放在StableBuffer中，因此，当系统发生失败的时候，就可以恢复数据。在把一个页写入到StableBuffer中之前，实际的目标地址和时间戳，将会被嵌入到页头中。一旦系统发生了失败，就可以扫描StableBuffer，读取这些元数据来重构StableBuffer转换表。具体而言，在需要重构StableBuffer转换表时，需要一个槽一个槽地扫描StableBuffer。对于槽O中的每个页，假设它的时间戳是tSO，它的目标地址是D，目标地址D中的当前页的最近更新的时间戳是tSD，需要对tSO和tSD进行比较，如果tSO≤tSD，就说明这个页一定已经被刷新到目标地址中，因此，就可以把第O个槽的位图索引信息设置为可用状态。否则，即tSO>tSD，这就意味着该页在系统崩溃时还没有被刷新到闪存的目标地址D中，因此，就需要把这个槽标记为占用状态，并且在StableBuffer转换表条目中插入一个新的条目<D,O>。

5.5.3.3      StableBuffer管理器的读写操作

（1）页读操作

StableBuffer管理器的读取器负责执行页读操作，在收到针对目标地址D的页的读操作请求时，读取器会通过哈希方式查找StableBuffer转换表。如果在StableBuffer转换表找到一个条目<D,O>，就读取StableBuffer的槽O中的页；否则，就直接到闪存的目标地址D中读取页。可以看出，在任何一种情况下，都只需要一次闪存IO，唯一增加的开销是StableBuffer转换表的查找操作；但是，由于StableBuffer转换表是以哈希表的形式实现的，因此，这个查找操作的开销很小。

（2）页写操作

      StableBuffer管理器的写入器负责执行页写操作。当DBMS写缓冲区要把一个目标地址为D的脏页p驱逐出DBMS缓冲区时，写入器会首先在该页头部中增加一些元数据。然后，它会查找StableBuffer转换表，如果在某个槽O中找到目标地址D，就更新这个页。否则，即在StableBuffer转换表中找不到目标地址为D的条目，则写入器会在StableBuffer中找到一个空的可用槽，这可以通过查找可用槽指针来实现。如果可用槽指针是null，说明StableBuffer是满的，就会激发一个刷新进程来释放一些已经被占用的槽。当一个槽O’被释放以后，这个页p就会被写入到槽O’中，并生成一个新的条目<O’,D>插入到StableBuffer转换表中。最后，如果位图索引中还可以找到可用槽的话，可用槽指针会指向下一个可用槽，否则，可用槽指针设置为null。可以看出，在写一个新页时，只会引起一次闪存IO，但是，需要额外的开销来释放StableBuffer转换表中已经被占用的槽来获得可用槽。

5.5.3.4      StableBuffer管理器的模式识别操作

StableBuffer中收集了大量的写操作序列，StableBuffer管理器的模式识别器需要对这些写操作序列进行分析，探测发现高效的写模式，比如顺序写、集中写和分区写。

StableBuffer方法采用了两种不同的方法来识别高效的写模式，即按需识别方法和增量识别方法。按需识别模式，是在需要执行刷新操作的时候才去识别确定高效的写模式。而增量识别模式的方法，则需要不断维护关于写模式的辅助信息，每次执行针对闪存设备的写操作的时候，都需要去更新这些信息，在接收到一个页刷新请求时，可以使用辅助信息来确定高效的写模式。

（1）按需识别方法

按需识别的方法，可以很容易通过在StableBuffer转换表上的排序扫描来实现。对于不同的写模式而言，按需方法的识别不同写模式的过程如下：

  • 识别顺序写模式：通过对StableBuffer转换表中记录的目标地址进行扫描和排序，就可以很容易确定顺序写模式。多个写操作的地址相邻时，就可以构成一个地址连续的写操作序列，由此，可以形成若干个地址连续的写操作序列。具备最长连续地址的多个写操作序列，就可以被判定为“顺序写”。
  • 识别分区写模式：对StableBuffer转换表中记录的目标地址进行扫描和排序，通过对排序后的目标地址进行分析，就可以识别分区写模式。每个连续的地址序列，就是一个分区。大小相同的分区会被分到一个组，具有最多写操作数量的组，就可以在执行刷新操作时成为优先被选择的组。
  • 识别集中写模式。采用一个滑动窗口对排序后的页目标地址进行扫描，就可以探测到集中写模式。滑动窗口的大小，是和闪存设备的集中写区域大小相同的。在扫描的时候还同时需要维护一些额外的信息，包括：（1）滑动窗口的起始位置；（2）滑动窗口内的目标地址的数量。最后，包含最密集目标地址的滑动窗口就可以被确定下来，这个窗口内的操作序列就属于集中写模式。

（2）增量识别方法

增量识别方法的目标是，把确定高效写模式的代价分摊到大量写操作之中。这种方法会为增量识别高效写模式的候选实例维护一些辅助数据结构。每当一个页被插入到StableBuffer中，或者从StableBuffer中删除时，辅助数据结构都会发生更新。有了这些辅助数据结构的帮助，任何时候都可以高效地发现高效写模式。增量识别方法对于后面将要介绍的StableBuffer管理器的主动刷新操作而言是必须的，因为，主动刷新操作在任何时候一旦被触发，就要求必须可以立即获得高效写模式的实例，把它们刷新到闪存目标地址中，而按需识别方法是无法支持这一点的，只有增量识别方法才有能力做到立即为刷新操作提供高效写模式的实例。增量方法识别不同写模式的具体过程如下：

  • 识别顺序写模式：为了识别顺序写模式的实例，需要维护一个集合SL={S1,S2,…,Si,…}，它包含了连续地址区间，其中，Si=(addrmin,addrmax)，表示一个地址区间。集合SL中的各个Si是根据Si中的addmin的升序顺序进行排列的。每当插入或者删除一个地址addr，就会触发一个在SL上的二分搜索，找到距离addr最近的Si。对于一个插入操作，如果可以在已有的地址区间的基础上形成一个更长的地址区间，那么，可以把addr插入到距离它最近的Si；否则，就单独创建一个只包含addr的新的地址区间。对于一个删除操作，包含addr的Si会被分裂成两个地址区间。可以看出，每个Si都是一个顺序写操作模式的候选实例。
  • 识别分区写模式：为了增量地识别分区写模式的候选实例，需要维护一个基于集合SL的额外的数据结构{P1,P2,…,Pl,…}，其中，Pl会跟踪SL中的所有大小为l的Si，例如，P3维护了一个指针集合，这些指针指向大小为3的所有Si。每个Pl代表了分区写模式的一个候选实例。在发生一个页的插入或者删除操作时，在更新完SL以后，还需要继续更新受到影响的Pl。
  • 识别集中写模式：为了识别集中写模式的实例，需要维护一个关于集中写簇的集合FL={F1,F2,…,Fi,…}，其中，Fi=(addrmin,addrmax,setaddr)，表示落入区间[addrmin,addrmax]的地址的集合为setaddr，并且，addrmin和addrmax之间的距离，小于闪存设备集中区域的大小，因此，每个Fi是集中写模式的一个候选实例，多个Fi会根据addrmin进行升序排序。当插入一个新的地址addr时，就在FL上执行一次二分搜索，来找到最近的簇Fi。然后，如果可能的话，需要把地址addr合并到找到的Fi中，否则，为addr创建一个新的Fi。相反，对于一个删除操作而言，会把addr从相应的簇中删除。在StableBuffer方法中，集中写簇的识别，是采用贪婪算法实现的，这样可以降低计算代价，不过会牺牲簇的质量。为每个插入和删除操作更新辅助数据结构的时间复杂度是O(logn)，其中，n是存储在StableBuffer中页的数量。每个数据结构的空间复杂度是O(n)。由于StableBuffer的大小通常很小，因此，空间需求是可以接受的。

（3）两种模式识别方法的比较

和按需识别方法相比，在执行刷新操作时，增量识别方法可以更加快速地确定高效的写模式，因此，增量识别方法可以取得更短的写操作响应时间。但是，增量识别方法为每个写操作都引入了一定的维护辅助信息的额外代价，因此，增量识别方法的总体代价往往高于按需识别方法，吞吐量也不如按需识别方法。此外，增量识别方法是在增量维护写模式的信息，而这个过程中，每次增量维护时，始终只能获得在维护发生时间点之前已经产生的写操作序列的信息，而无法获得在维护时间点之后产生的时间序列信息，因此，总体而言，它只是根据局部信息而不是全局信息来确定高效的写模式实例，因此，返回结果的质量可能不如按需识别方法。相反，按需识别方法在刷新操作时才会执行，相对于增量识别方法而言，在这个时间点，按需识别方法已经可以获得所有写操作序列的信息，因此，它可以根据全局信息而不是局部信息来确定高效的写模式实例，返回结果的质量较高。

5.5.3.5      StableBuffer管理器的刷新操作

StableBuffer管理器的刷新操作，负责把临时存储在StableBuffer中的页，以高效的写模式，刷新到闪存的目标地址中。这里需要重点解决的问题就是，什么时候把StableBuffer中的页刷新到闪存的目标地址中？

对于页刷新操作执行的时机的选择，StableBuffer方法采用了两种方式，即被动方式和主动方式。

（1）被动方式

在被动方式中，对于一个写操作而言，如果在StableBuffer中已经没有额外的空间，那么，就可以把最佳写模式的实例刷新到目标地址中。一旦刷新操作被启动，被动方式会从候选实例集合中选择某些写模式的一个实例，然后对实例中包含的页执行刷新操作，写入到闪存的目标地址中。当采用按需写模式识别方法时，高效写模式的候选实例是通过扫描StableBuffer转换表来临时生成的。当采用增量写模式识别方法时，高效写模式的候选实例已经被增量地维护，因此，可以立即获得最佳写模式的实例。

（2）主动方式

         在主动方式中，在任何写操作执行时，如果满足一定的条件，就可以把高效写模式的实例刷新到闪存目标地址中。在主动方式中，刷新管理器会一直在后台运行，用来探测发现高效写模式的候选实例。因此，主动方式内在地要求模式识别器采用增量识别的工作方式。对于任何写模式实例，它都会被增量地维护，一旦发生了变化，刷新管理器就会被触发。刷新管理器会检查受到影响的写模式实例是否符合刷新操作的条件，主要是根据该写模式实例的大小和类型来决定的。对于写模式x的某种类型，会采用一个刷新门槛值ɵ，只有大小高于门槛值ɵ的实例才会被刷新到闪存的目标地址中。

5.6   本章小结

本章内容首先给出了数据存储方法概述，主要介绍了基于页的方法和基于日志的方法；然后，介绍基于页的方法，即DFTL，它采用了面向DBMS的FTL机制，充分利用了页级别的时间局部性来存储页面，并且更新操作可以在任何数据块上进行，提高了块利用率；接下来，介绍了基于日志的方法，包括LGeDBMS、A/P方法、IPL方法和ICL方法等；再接下来，介绍了基于页差异的日志方法，即PDL方法；最后，介绍了StableBuffer，它可以充分利用独特的闪存设备写模式，来优化写操作集中的DBMS应用（比如OLTP）的性能。

5.7   习题

  • 把数据库中的数据存储到闪存中，可以采用两种方法，即基于页的方法和基于日志的方法，请阐述这两种方法的各自特点。
  • 分析为什么需要设计面向DBMS的FTL机制。
  • 阐述PDL方法的基本原理，以及它和基于页的方法、基于日志的方法的不同之处。
  • 分析为什么StableBuffer方法可以获得较好的性能。