第9章 闪存数据库事务管理

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

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

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

第9章 闪存数据库事务管理

事务处理是DBMS的重要组成部分，事务机制可以保证数据库数据处理的原子性、一致性、隔离性和持久性，从而推动了数据库在商业领域的大规模成功应用。Jim Gray正是因为提出了著名的事务理论，从根本上解决了实际应用中的数据一致性和完整性问题，因而获得了1998年的图灵奖。不少研究人员也在事务方面的研究做出了巨大的努力，使得事务理论在不同的环境下（比如分布式数据库）不断得到完善。

事务恢复是数据库管理系统的重要功能，可以保证数据库的正确性和一致性。数据库在实际运行过程中，会不可避免地发生各种故障，比如操作系统故障、内存故障、CPU故障、外部设备故障、操作失误和断电等等，必须采取有效的措施才能够保证数据库的一致性和完整性。比较常见的事务恢复方法就是建立日志文件和建立镜像文件，生成原始数据的冗余备份，一旦发生故障，系统就可以从日志或镜像文件中恢复数据。

在绝大多数传统的面向磁盘的DBMS中，通常采用日志的方式进行事务恢复，当数据库发生比较频繁的更新时，会产生大量的小数据量的日志写入操作。磁盘可以以字节为单位进行写入，而闪存的最小写入单位是页，每次写入少量日志记录时，无法占满一页空间，下次写入新的日志记录时，需要再分配新的空白页进行日志写入。因此，频繁的小数据量的日志写入操作，不仅会浪费大量的闪存空间，也恶化了闪存的整体性能。此外，传统的DBMS都采用三阶段故障恢复方法，往往包含了大量的数据读取和反复更新操作，当采用闪存作为数据库的底层存储介质时，会导致大量的写操作和擦除操作，进一步恶化了数据库的性能。

综上所述，如果把现有的面向磁盘的DBMS的事务恢复方法直接应用到闪存数据库中，将无法获得好的数据库性能。

本章内容首先讨论了数据库事务恢复的概念和常用技术，介绍了两种应用最为广泛的传统数据库事务恢复方法，即基于日志技术的事务恢复方法和基于影子页技术的事务恢复方法；然后，分析了传统的数据库事务恢复方法在闪存数据库中的表现情况；最后，重点介绍了几种典型的闪存数据库事务恢复方法，包括基于日志技术的闪存数据库事务恢复方法，日志恢复技术与影子页恢复技术相结合的闪存数据库事务恢复方法。在介绍不同的闪存数据库事务恢复方法的同时，还分析了不同的事务恢复方法的优缺点。

9.1    事务的概念

数据库事务是数据库管理系统执行过程中的一个逻辑单元，是由有限个操作构成的一个操作序列。事务处理用以保证事务的顺利执行，即保证事务的原子性、一致性、隔离性和持久性。事务的原子性是指一个事务中的所有操作要么全部执行，要么全部都不执行；事务的一致性是指，如果在事务执行之前数据库是一致的，那么在执行事务之后数据库还是一致的；事务的隔离性是指即使多个事务并发执行，每个事务都感觉不到系统中有其他事务在执行；事务的持久性是指事务成功执行以后，它对数据库的修改是永久的，即使系统出现故障，数据库中的数据也不受影响。

事务恢复用以保证事务的原子性和持久性，是提高数据库可靠性的重要技术之一。事务恢复是指在系统发生故障或人工中止事务时，能够回滚到事务执行之前的状态，以此来确保事务的原子性与一致性。为了在系统发生故障或中止事务时，事务管理能够回滚到事务执行之前的状态，事务管理器需要跟踪事务的状态，以判断事务是否已经执行完毕，对于已经提交的事务，不用作任何特殊处理，对于没有执行完毕的事务，需要撤销中止事务所做的更改。

9.2   传统的事务恢复机制

在基于磁盘的数据库系统中有两种常用的事务恢复方法，即基于日志的恢复方法（write-ahead-logging，简写为WAL）和基于影子页技术（shadow paging）的恢复方法。

9.2.1   基于日志的恢复方法

基于日志的恢复方法要求在磁盘上的数据被更新之前先写入其更新日志，事务提交时先写入该事务的更新日志，再写入事务的提交日志。事务恢复时，通过是否存在事务提交日志来判断该事务是否已经提交。虽然基于日志的恢复方法中日志的写入较为频繁，但是，由于数据库中日志一般连续存储在一个独立区域，日志写入时磁盘几乎不需要寻道和旋转，因此，记录日志对系统性能的影响不大；另一方面，由于磁盘可以原位更新且更新操作代价和读取操作相比并不突出，因而故障恢复时Undo和Redo操作的代价不大。

9.2.2      基于影子页的恢复方法

基于影子页的恢复方法采用了与基于日志的恢复方法完全不同的方式处理数据的更新。在使用影子页技术作为事务恢复的数据库管理系统中，需要维护一个逻辑页与物理页之间的地址映射。当一个事务需要修改逻辑页时，系统将分配一个新的空闲页作为该物理页的影子页，将修改后的数据保存在影子页中，并在地址映射表中，将逻辑页映射到影子页上。提交事务时，将地址映射表写入到永久的存储设备中，并在之后回收无用的物理页。中止事务时，只需要简单地抛弃影子页和地址映射表的更新。相对于基于日志的恢复方法，基于影子页技术的恢复方法需要更少的写操作。

在使用磁盘作为外部存储设备的数据库系统中，基于影子页的恢复方法没有基于日志的恢复方法应用广泛，这是因为：1）影子页技术需要维护地址映射表；2）影子页技术采用异地更新的方式，而各个影子页分散在磁盘的各个位置，加大了磁盘的寻道开销；3）影子页技术会产生很多垃圾页，需要专门的垃圾回收机制回收这些垃圾页。

9.3    传统的事务恢复机制在闪存数据库中的表现

虽然在传统的数据库系统中，基于日志的恢复方法比基于影子页的恢复方法应用广泛，但是，在闪存数据库系统中，情况却正好相反，这是由闪存的内在特性决定的。因为闪存的读写代价不一致、异地更新和读写操作只能以页为单位等特性，WAL方法在闪存中会带来新的问题，而影子页的恢复方法中存在的问题却能迎刃而解。

传统的日志恢复方法并不适合直接应用在闪存上。一方面，闪存的写操作代价远高于读代价，频繁写入日志会严重影响系统性能，故障恢复时Undo和Redo操作的代价也较高；另一方面，事务提交日志通常需要及时写入，提交日志的长度一般很小，而闪存的读写操作是以页为单位，及时写入提交日志的代价相对较高，而且会降低日志空间的利用率。

闪存是使用影子页技术恢复方法的理想设备，这是因为：第一，影子页技术需要维护地址映射表，而闪存本身就需要维护地址映射表，所以，维护地址映射表的代价可以忽略不计；第二，影子页技术采用异地更新的方式，而闪存支持快速的随机访问，不存在寻道开销，能够显著提高影子页恢复方法的效率；第三，影子页恢复方法会产生很多垃圾页，需要垃圾回收机制回收这些垃圾页，而垃圾回收是闪存责无旁贷的事情。综上所述，闪存数据库系统更适合采用影子页方法来处理事务恢复。

9.4 代表性方法

目前，相关研究已经提出了一些面向闪存文件系统或闪存数据库的事务恢复方法，这些方法大多借鉴了影子页的思想，利用影子页技术在闪存设备中的天然优势，设计面向闪存的事务恢复方法，以此提高故障恢复的性能。与此同时，有部分研究针对数据库中存在的随机少量写操作提出了基于日志提交的存储管理办法，这类存储管理办法更适合采用基于日志提交的事务恢复方法。

基于影子页的事务恢复中，代表性方法有Transactional FTL、TxFlash和Flag Commit。其中，Transactional FTL是一种针对嵌入式数据库系统而设计的事务恢复方法，TxFlash是针对文件系统或数据库系统，设计了一种通用的事务处理机制。在Transactional FTL和TxFlash中，事务处理由底层存储负责，底层存储提供了与事务相关的接口，上层应用通过调用这些接口以实现事务操作。Flag Commit使用了SLC(Single Level Cell)型闪存支持部分页编程（partial page programming）技术的特点，在物理页的带外区(spare area)中存储事务提交标识，通过带外区中的事务提交标识跟踪事务的状态，判断一个该事务是否已经提交。

基于日志的事务恢复方法中，代表性方法有IPL(In-Page Logging)和OPL(Out-Page Logging)。IPL与OPL使用日志技术的存储管理办法，虽然它们记录日志的主要目的是进行数据更新，但由于这些日志被存储在非易失的闪存中，故同样可以用于事务恢复。IPL与OPL采用采用了相同的方法处理事务，但是，IPL需要底层存储设备提供部分页编程支持，OPL在提高日志空间利用率的同时，不需要部分页编程技术的支持，所以OPL也可以应用于不支持部分页编程的固态盘，因此，相对于IPL，OPL的可用范围更加广泛。

此外，HV-Recovery通过使用一种全新的日志记录方法，充分利用了闪存设备异地更新产生的逻辑页的历史版本，显著地提高了数据库恢复操作的性能。因为HV-Recovery需要写入日志，并且利用了闪存异地更新产生的逻辑页历史版本，所以，HV-Recovery可以看作是一种日志事务恢复方法和影子页事务恢复方法相结合的恢复方法。

9.4.1      Transactional FTL

文献[KimLJB08][LeeKWCK09]提出了一种新的FTL(Flash Transaction Layer)，即Transactional FTL，适用于使用MLC(Multilevel Cell Layer) NAND型闪存作为外部存储设备的嵌入式数据库系统。Transactional FTL在基本的FTL基础之上，提供了3个新的API以支持事务操作，这3个API分别是FTL_BeginTxn()，FTL_CommitTxn()和FTL_AbortTxn()。FTL_BeginTxn()返回一个事务ID，这个事务ID将作为FTL_CommitTxn() 和FTL_AbortTxn()调用的参数，FTL_CommitTxn()能够原子地执行事务。当系统非正常关闭或调用FTL_AbortTxn()时，Transactional FTL将自动撤销中止事务所做的修改，回滚到事务执行之前的状态。有了以上3个API以后，数据库系统不再需要使用日志或影子页技术，就能够方便地实现数据库级别的事务操作。

Transactional FTL借鉴了影子页的思想，为逻辑页的更新创建一个影子页，将更新后的数据写入到影子页中，事务提交时，在专门区域写入一条提交日志，通过是否存在提交日志来判断事务是否已经提交。该方法避免了频繁的小数据量日志写操作，从而大大减少了由此引起的MLC NAND闪存开销。在基于影子页的方法中，物理页的分配是基于事务的。当一个事务开始时，一个物理块被分配给这个事务，然后，该事务所有后续的写请求都会被导向到这个块中。这样，来自某个事务的逻辑上随机的写操作，会被转换成在一个块内物理上连续的写操作。这种做法和之前的其他方法具有很大的区别。在其他方法中，针对某个逻辑页的更新操作，不管是属于哪个事务，都会被引导到同一个物理页上面去执行，因此，会带来“耦合页”问题，即属于某个事务的写操作在执行过程中发生断电，会破坏同一个物理页中属于另一个事务的写操作已经写入的数据。而对于基于影子页的方法而言，就不存在耦合页问题，因为，所有不同的事务都写入不同的物理块中。某个事务所写入的块，和其他事务所写入的块没有任何关系。因而，一个事务的写操作在发生断电时，自然也就不会对其他事务写入的数据产生任何影响。

基于影子页的方法可以提供一致的写操作性能，即写操作性能和写操作的模式无关，因为，所有属于同一个事务的写操作都是在分配给该事务的块内按照先后顺序进行的。

下面简单介绍该方法的技术细节。如图[TransitionalFTL]所示，在该方法中，闪存中的块被分成四种类型：数据块、事务块、映射块和垃圾块。四种类型的块的具体作用如下：

• 数据块以列表的方式组织在一起，称为数据块列表，每次新创建的数据块都会被追加到列表的尾部。一个数据块只包含已经提交的数据，这就意味着，数据块中的数据代表了数据库在某个时刻的一致性状态。一个数据块包含若干个数据页，每个数据页包含数据区域和带外区，带外区域中存储了该物理页对应的逻辑页的编号LPN。往数据块中的写入一个新的页p_new时，如果该新页的LPN与已经存在的某个页p_old的LPN相同，那么，p_old会被设置为“无效”，从而使得系统中永远只有最新版本的数据页是处于“有效”状态的。
• 事务块包含了未提交的数据。当一个事务正在执行时，系统会为它分配一个事务块，该事务的写操作会在这个新分配的事务块上进行，而不是在数据块上进行。事务提交后，所有分配给该事务的事务块，都会变成数据块，并且追加到数据块列表的尾部。如果一个事务中止了，所有分配给该事务的块，都会变成垃圾块。
• 垃圾块只包含处于“失效”或“空闲”状态的页。当系统中不再有空闲块可以使用时，就会启动垃圾回收过程，回收后，就可以继续用作事务块、映射块或者数据块。
• 映射块是专门用来存放块映射表的，块映射表是块状态记录的集合，包含了闪存中每个块的当前状态，当一个事务提交或者中止时，块映射表就会被更新。

图[TransitionalFTL] Transitional FTL中块的组织方式

Transactional FTL为每一个更新事务分配一个“空闲”状态的垃圾块作为其事务块，事务提交时，将其更新过的所有逻辑页写入其事务块，然后在闪存的映射块中写入一条提交日志，将事务块转换为数据块。

如果在事务执行过程中系统发生故障，则需要重建闪存的地址映射表，在重建闪存的地址映射表时，直接忽略事务块，只考虑数据块，从而将逻辑页恢复到最近的己提交版本。Transactional FTL在故障恢复时不需要执行Undo和Redo操作，但仍然需要写入单独的提交日志，当系统中短事务较多时，提交代价仍然较大，且闪存空间利用率较低。

9.4.2    TxFlash

文献[PrabhakaranRZ08]通过修改现有的固态盘，提出了一种新的、支持事务操作的存储设备——Transactional Flash，简称TxFlash。TxFlash提供了一个支持原子地读写多个页的API，即WriteAtomic(p₁……p_n)，有了这个API以后，上层应用不再需要使用日志或影子页技术，就能够方便地实现数据库级别的事务操作。TxFlash的原理如图[TxFlash]所示。TxFlash与普通的闪存设备一样，需要FTL、垃圾回收机制和地址映射表等信息，但是，TxFlash在普通的闪存设备基础上，提供了一个支持原子地操作多个页的API（WriteAtomic），因此，文件系统与数据库系统可以通过调用该API，方便地实现事务操作。TxFlash为了提供事务支持，增加了一个事务提交逻辑（Commit Logic）和一个事务恢复逻辑（Recovery Logic），并且提供了事务的隔离性保证，确保没有冲突的写一个页。一旦事务提交，TxFlash将更新与该事务相关的所有页的地址映射信息。TxFlash的核心就是事务的提交逻辑与事务的恢复逻辑。事务的提交逻辑用于跟踪事务的状态；事务的恢复逻辑用于在系统发生故障时，判断系统中哪些页是已经提交的，哪些页是未提交的，在系统恢复过程中，重建已提交页的地址映射，忽略未提交的页，以此保证事务的原子性与一致性。

图[TxFlash] TxFlash设备的体系架构

TxFlash采用了两种事务提交逻辑，即SCC(Simple Cyclic Commit)算法和BPCC(Back Pointer Cyclic Commit)算法，这两种事务提交算法的思想基本是一样的。下面首先介绍SCC算法及其不足，然后再介绍BPCC算法。

SCC借鉴了影子页的思想，为每一个要修改的逻辑页创建一个影子页（影子页的数据结构如图[SCC-BPCC] (a)所示），将修改过的数据存在影子页中，在影子页的带外区中存放下一个影子页的物理地址(事务预先申请少量闪存页，从而可以在影子页被写入前就事先确定其在闪存上的位置)；事务提交时，在最后一个影子页的带外区中写入第一个影子页的物理地址，从而使得属于同一个事务的各影子页形成了一个环。通过是否存在环来判断事务是否已经提交，而不用写入事务提交日志，减少了日志的数量，因此，提高了事务提交的效率。

图[SCC-BPCC] SCC与BPCC算法中物理页格式

SCC算法中有一个重要的特性，即逻辑页的非最新版本一定是已提交的。也就是说，当要创建逻辑页的影子页时，必须确保闪存中没有中止事务所留下的未提交版本。SCC的这个特性对事务恢复以及写操作的性能有较大的影响。

当系统发生故障时，需要重新建立地址映射表，建立地址映射表的关键就是判断哪些页是已提交的（有效的），哪些页是未提交的（无效的）。在SCC中，逻辑页的非最新版本一定是已提交的，所以，事务恢复的关键就是将逻辑页映射到具有最高版本号的物理页或映射到拥有第二高版本号的物理页。如果拥有最高版本号的物理页是已提交的，则将逻辑页映射到该物理页；如果拥有最高版本号的物理页是未提交的，则说明该事务没有执行完毕，需要回滚到事务执行之前的状态，SCC只需要简单地将逻辑页映射到具有第二高版本号的物理页即可。综上所述，SCC中事务恢复的关键就是判断拥有最高版本号的物理页是否是已提交的。

下面通过一个例子来说明SCC算法中的事务恢复。如图[SCC-example]所示，A₁、B₂、C₁是普通的已提交的物理页，B₁是一个已经过时的物理页，C₂是一个不存在的页，D₁是一个已写入了数据、但其所在的事务还未提交的页，C₂是与D₁相关的事务下一次要写入的位置。令h_p为P的最高版本号，P_h为拥有最高版本号的页，Q_l为P_h.next，l为Q_l的版本号，h_Q为拥有最高版本号的页。

拥有最高版本号的页P_h是否是已提交版本，需要分三种不同的情况讨论。

第一种情况(h_Q > l)：h_Q大于l说明对于Q_l而言，有更新的提交版本Q_h，因此，P_h是已提交的。这是因为P_h与Q_l在一个环中，一个环中的页，要么都是已提交的，要么都是未提交的。如图4所示，A₁的next-link域指向B₁，而B的最新版本为B₂，在SCC中，非最新版本的页一定是已提交的，所以B₁是已提交的，而A₁的next-link域指向B₁，所以A₁也是已提交的。

第二种情况（h_Q < l）：因为l比Q的最高版本号h_Q还大，所以，Q_l是一个不存在的页，说明此次事务还未执行完，因此，P_h是未提交的。考虑图[SCC-example]中的D₁与C₂，D₁的next-link域指向C₂，而C的最新版本为C₁，所以，D₁是未提交的。

第三种情况（h_Q = l）：P_h的下一个影子页是拥有最高版本号的页，P_h是否已提交取决于Q_h是否已提交。通过递归地判断Q_h是否已提交来决定P_h是否已提交。考虑图4中的C₁与B₂，C₁的next-link域指向B₂，所以，C₁是否已提交取决于B₂是否已提交，而B₂的next-link域又指向了C₁，B₂与C₁形成了一个环，根据SCC算法的定义，B₂与C₁都是已提交的页。

图[SCC-example] SCC算法系统状态的一个实例

SCC算法实现相对比较容易，只需要简单地修改固态盘的垃圾回收机制和恢复机制就能实现SCC算法。但是，SCC算法要求所有非最新版本的页都是已提交的，也就是说，在一个事务写一个页时，必须擦除未提交的版本。这个要求增加了写操作的延迟，因此，TxFlash还可以采用另一种事务恢复算法BPCC。

BPCC的数据结构如图[SCC-BPCC] (b)所示。BPCC在SCC算法的基础上，增加了一个back-pointer域，用于指向逻辑页的上一个已提交版本，以此来跳过未提交的版本。BPCC算法的事务提交与SCC算法一样，通过判断属于同一个事务的影子页是否形成环来判断事务是否已经提交。BPCC的事务恢复也与SCC类似，BPCC使用与SCC一样的方法来判断拥有最高版本号的页是否已提交。如果拥有最高版本号的页是已提交的，则将逻辑页的地址映射到拥有最高版本号的页；如果拥有最高版本号的页是未提交的，则将逻辑页的地址映射到该页的上一个已提交版本。BPCC算法可以通过back-pointer获得逻辑页的上一个已提交版本，然而，在SCC算法中，逻辑页的非最新版本一定是已提交的，所以，如果拥有最高版本号的页是未提交的，则将逻辑页地址映射到拥有第二高版本号的物理页，这就是BPCC算法与SCC算法的主要区别。

TxFlash向上层应用提供了一个支持原子地操作多个页的API，上层应用可以通过调用该API方便地实现事务操作。但是，TxFlash存在如下问题：1）为了在影子页的带外区中存放下一个影子页的物理地址，需要预先申请少量闪存页，从而可以在影子页被写入前就确定将来其在闪存上的位置；2）为了保证数据的一致性，SCC算法在写入逻辑页的新版本前，需要擦除未提交的版本，增加了写操作的延迟，虽然BPCC算法通过在带外区中存储更多的信息解决了这个问题，但是，BPCC算法也增加了事务恢复与垃圾回收的复杂性；3）SCC与BPCC算法都由TxFlash实现，支持文件系统或数据库系统级别的事务处理，没有专门针对数据库系统进行优化，例如，没有考虑并发控制，而并发控制是数据库系统中的关键技术。

9.4.3      Flag Commit

文献[OnXCHH12]是第一篇专门研究闪存数据库事务恢复的文章，作者提出了应用于不同工作场景的两个事务恢复方法，分别是CFC（Commit-based Flag Commit）和AFC(Abort-based Flag Commit)。它们的基本思想都是使用影子页(shadow paging)技术实现事务的更新操作，当一个事务需要修改逻辑页时，系统将分配一个新的空闲页作为该逻辑页的影子页，将修改后的数据保存在影子页中，并在影子页的带外区保存逻辑页号、事务的ID和事务的提交标识等信息。提交事务或中止事务时，通过影子页的带外区中事务提交标识，就可以跟踪事务的状态。在事务的更新、中止、提交过程中，都没有写入任何日志，减少了日志的数量，因此也减少了写操作和擦除操作的次数，最后提高了事务恢复的整体性能。

CFC和AFC算法之所以能够利用影子页的带外区来跟踪事务的状态，是因为它们利用了SLC型闪存具有部分页编程的特征。所谓部分页编程，是指在不擦除物理页的情况下，修改物理页的带外区中的数据，即原地修改了物理页的带外区中的数据，从而实现了原地更新事务的状态。

在CFC与AFC算法中，事务的状态由属于这个事务的所有影子页的事务提交标识共同决定。CFC算法约定，当且仅当至少有一个影子页的事务提交标识为TRUE，这个事务才是已提交的，否则，该事务是未提交的。在CFC算法执行过程中，将所有影子页初始时的事务提交标识都设置为FALSE，事务提交时，将最后一个影子页的事务提交标识设置为TRUE。一个事务可能包含很多影子页，在最后一个影子页的事务提交标识由FALSE改为TRUE后，就标识该事务已顺利提交。如图[CFC-true]所示，图[CFC-true] (a)表示一个正在进行的事务或者一个已经终止的事务，图[CFC-true] (b)表示一个已提交的事务。

图[CFC-true] CFC算法的事务提交标识链表

为了实现CFC算法，内存中需要维护几个与事务相关的表，即事务表、脏页表和地址映射表，如图[CFC-example]所示。

图[CFC-example] CFC算法的一个实例

事务表(Transaction Table)维护每个事务的状态(Status)、该事务所涉及的影子页个数(NPage)以及最后一个影子页的地址(LastPage)。一个事务可能修改多个逻辑页，那么，就会创建多个影子页。在CFC中，将多个影子页通过影子页带外区的Link域链接成一个链表。在事务表中，用NPage跟踪影子页的个数，以方便在事务中止时，回收影子页；用LastPage跟踪最后一个影子页的地址，以方便在事务提交时，将LastPage的事务提交标识设置为TRUE。在实际运行过程中，事务表只保存活动的事务和已中止的事务。

脏页表(Dirty Page Table)保存了在事务执行之前，逻辑页所对应的物理页地址。保存逻辑页在事务执行之前的物理页地址，可以方便地在事务中止时，将逻辑页映射到事务执行之前的物理页，以此实现事务的回滚。

地址映射表(Direct  mapping  table)保存了逻辑页到物理页的映射信息。

在CFC算法中，带外区将包含以下数据域：逻辑页号（LBA）；逻辑页的版本号（Version #）；事务ID（XID）；指向前一个影子页的指针（Link）；事务提交标识（Flag Commit）。

下面将详细介绍CFC算法中，事务的更新、提交、中止过程。

更新事务：当一个事务更新逻辑页时，将执行下面4步。1）创建一个与逻辑页对应的影子页，并在影子页的带外区写入逻辑页号、版本号、事务ID、Link和事务的提交标识（初始时设置为FLASE）；2）如果事务表中没有该事务，就在事务表中创建一条记录，并初始化NPage为1，LastPage为影子页的地址。如果事务表中已经存在该事务，在事务表中修改该事务的影子页计数NPage，并将该事务的LastPage设为最新的影子页地址；3）在脏页表中写入一条记录，记录逻辑页在执行事务之前的物理页地址；4）在地址映射表中，修改逻辑页的映射信息，将逻辑页映射到影子页。重复执行上面的步骤，直到事务执行完成，或者中止事务。

提交事务：当提交事务时，将事务的LastPage的提交标识置为TRUE（在CFC中，事务中有一个影子页的提交标识为TRUE，则这个事务是已提交事务），在事务表中删除该事务，移除脏页表中的信息，在移除脏页表中信息的同时，将逻辑页之前对应的物理页标记为垃圾页。

中止事务：人工中止事务时，CFC将会撤销该事务所做的修改。CFC首先修改事务表中事务的状态信息，然后将该事务所创建的影子页标记为垃圾页，并将地址映射表中，逻辑页映射到事务执行之前的物理页地址。

CFC算法使用影子页技术实现事务的更新操作。当事务提交时，标记逻辑页在该事务执行之前所对应的物理页为垃圾页；当事务中止时，执行事务回滚操作，以保证数据的一致性与事务的原子性，与此同时，中止事务所产生的影子页将被标记为垃圾页。在数据库系统的运行过程中，空闲页逐渐减少，垃圾页逐渐增多，当空闲页少到一个预先设定的门槛时，将触发垃圾回收操作。垃圾回收操作将回收1）中止事务所产生的垃圾页，这些页是未提交的；2）已经提交的页，但是，之后又被其他事务标记为垃圾的页。对于第一种情况，直接回收即可，对于第二种情况，还需要维护事务的状态。

下面将详细分析CFC算法中垃圾回收的第二种情况。考虑这样一个场景，如图[CFC-garbage]所示，有一个事务修改了P₅，P₄，P₇和P₁，并且事务提交成功。根据CFC算法的定义，属于这个事务的所有影子页的事务提交标识至少有一个为TRUE，该事务为已提交的事务。根据CFC的事务更新过程，P₁的提交标识设置为TRUE。假设现在有另外一个事务将P₁标记为垃圾页，那么，垃圾回收机制就可以回收P₁。垃圾回收机制回收P₁以后，就剩下P₅，P₄和P₇，并且这三个页的事务提交标识都为FALSE。如果此时发生故障，事务恢复管理器将认为P₅，P₄，P₇属于一个中止事务。为了避免这种情况，CFC算法需要在回收P₁的时候，将P₇的事务提交标识改为TRUE。如果回收的不是P₁，而是位于链表中间的P₇，那么，还需要将P₄的事务提交标识设置为TRUE，把链表拆分成两个子链表，将它们当作两个不同的事务对待，并且要分别维护它们的状态。

图[CFC-garbage] CFC算法中的垃圾回收

从上面的分析可以看到，维护事务状态的代价很高，每次回收一个页，CFC都要判断是否需要修改该事务中其它页的事务提交标识，以维护事务的状态。考虑到事务的维护代价，文献[OnXCHH12]还提出了另一个算法——AFC，以降低已提交事务的维护代价。

AFC算法的基本思想如下：当且仅当一个事务的所有影子页中没有一个影子页的事务提交标识为FALSE时，该事务是已提交的。AFC算法中，事务的更新过程与CFC类似，只是在初始化时，将第一个影子页的事务提交标识设置为FALSE，将其他影子页的事务提交标识设置为TRUE，当事务提交时，将第一个影子页的提交标识改为TRUE，以此作为事务已提交的判断依据。

采用AFC算法以后，所有属于已提交事务的物理页的事务提交标识都为TRUE，当回收已提交事务的页时，不用任何额外的代价，就能维护该事务的状态，因为该事务的其他物理页的事务提交标识都为TRUE。虽然AFC算法不用维护已提交事务的事务状态，但是需要维护已中止事务的事务状态。如图[AFC-algorithm]所示，P₅、P₄、P₇和P₁是已中止事务的影子页，回收这些页。假设首先回收的是P₅，如果直接回收P₅，那么物理页P₄，P₇和P₁将会被认为是已提交事务的数据页，这是因为P₄、P₇和P₁的提交标识都为TRUE。所以，在回收P₅时，需要将P₁的提交标识设为FALSE。同理，在回收P₄时，也需要将P₁的事务提交标识设置为TRUE，将链表拆分成两个链表，并分别维护它们的事务状态。

图[AFC-algorithm] AFC算法中的垃圾回收

CFC算法和AFC算法的主要区别在于CFC的维护已提交事务的代价较大，AFC算法维护已中止的事务代价较大，在实际应用中，可以通过不同的工作场景以及不同的事务中断比例来选择。

CFC算法和AFC算法还可以通过记录日志的方式来提供No-Force策略的支持。数据库的No-Force策略是指在事务提交时，不用强迫刷新闪存中的脏页到外部存储器中。CFC和AFC算法支持No-Force策略的方法如下：将逻辑页的修改记录在日志中，在提交事务之前，先将缓冲区中的日志刷新到外部存储器中，此时，就算系统发生故障，也可以通过日记记录，将已提交的事务恢复。

CFC和AFC算法还能够支持数据库的并发操作，即支持多个事务同时读写同一条记录。CFC和AFC算法将每一个事务对数据所做的修改都记录在日志中，在并发的几个事务当中，其中一个事务提交时，都将缓冲区中的日志刷新到外部存储中，并写入一条事务提交日志。如果某个事务中止了对数据的修改，则通过日志文件中的记录，撤销该事务对数据的修改，保留其他事务对数据的更新。

    CFC和AFC算法通过在事务的影子页中跟踪事务的状态，减少了日志数量，从而减少了写操作和擦除操作的次数，在一定程度上提高了事务恢复的性能。但是，CFC和AFC算法只能用于支持部分页编程的SLC闪存设备中，然而，现在市面上的闪存设备大部分都采用容量更大、价格更低、但是不支持部分页编程的MLC闪存。此外，CFC和AFC算法为了支持No-Force策略和事务的并发操作，也需要写入日志记录，当写入的日志很多时，CFC和AFC策略将不能获得很好的事务恢复效率。

9.4.4   IPL

针对数据库中存在的“数据的细微随机更新”的特点，文献[LeeM07]提出了一种新的、适合闪存数据库的存储管理方法——IPL（In-Page Logging）。IPL通过采用基于日志的数据更新方法，能够较好地处理对数据的细微随机更新。虽然IPL记录日志的主要目的是进行数据更新，但由于这些日志被存储在非易失的闪存中，故同样可以用于事务恢复。

下面将简单地介绍IPL的思想，然后重点介绍IPL存储管理中的事务恢复机制。

IPL的基本思想如下：当缓冲区中的数据页被更新时，产生更新日志并在缓冲区中为其分配日志扇区（512B）来缓存日志；当数据页被驱逐出缓冲区时，并不将数据页写入闪存，而是将其日志扇区写入闪存中的日志页内，通过记录日志实现数据的更新。

在数据库运行过程中，当发生缓冲区“脱靶”，即访问的页面不在缓冲区中，需要到外部存储中读取该页时，IPL需要根据原始的数据页，以及日志页内与该页相关的更新日志构造该页的最新版本。在构造过程中，IPL需要扫描所有与该页有关的日志页，如果将所有的日志都存放在同一个地方，每构造一个数据页都需要扫描所有的日志，那么，数据页的构造代价将是非常巨大的。为了减少数据页的构造代价，IPL存储管理器将每一个闪存块分为数据区和日志区，如图[IPL-design]所示。日志区只记录该块中数据页的日志，以此来减少数据页的构造代价。

图[IPL-design] IPL的设计

图[IPL-design]给出了IPL的设计，假设一个闪存块为128k，一个数据页为8k。那么，一个闪存块包含15个数据页和1个日志页。每个日志扇区为（512B），则一个日志页包含16个日志扇区。这里需要注意的是，虽然闪存中的写操作的最小单位为页，但是IPL利用一部分NAND型闪存支持部分页编程技术，将一个日志页(8kb)分为16个扇区(512B)，每次可以只写入一个扇区，所需要的时间与写入一个页基本相同。

缓冲区中的每一个脏页都有一个与之相对应的日志扇区，一个日志扇区只能存放有限条日志记录，当日志扇区满或者与其对应的脏页被驱逐出缓冲区时，就将日志扇区写回闪存中的日志页中。如果某一块中的数据页反复被更新，那么该闪存块的日志扇区很快就会写满，此时，IPL存储管理器就会将闪存块中的数据页与日志页进行合并。合并的过程如下：首先分配一个新的空闲块，然后，将旧的闪存块中数据页与日志页进行合并，构造出最新的数据页，并将最新的数据页写入到新分配的闪存块中，最后，回收旧的闪存块。

IPL记录日志的主要目的是进行数据更新，但由于这些日志被存储在非易失的闪存中，故可以方便的支持事务恢复。为了支持事务操作，IPL只需要在的更新日志中加入事务编号、事务状态等信息。

事务提交时，对缓冲区中每个该事务更新过的逻辑页，将该页的日志扇区写入闪存中的相应位置，最后在系统日志区(闪存上的专门区域)写入一条事务提交日志即可。

事务中止时，对缓冲区中每个其更新过的逻辑页，撤销该事务的更新并删除日志扇区中该事务的更新日志，最后在系统日志区写入一条事务中止日志；对于该事务已经被写入闪存的更新日志不作处理。在重构数据页的过程中，IPL存储管理器忽略已中止的事务所产生的更新日志；在闪存块中的日志扇区写满时，需要将数据页与日志页进行合并，并写入到一个新的空闲块。在合并过程中，将己提交事务的更新日志应用到数据页上，忽略已中止事务所产生的更新日志，将当前活动事务的更新日志转移到新的日志页中。

IPL在故障恢复时不需要执行Undo和Redo操作，只需要扫描系统日志区以获取各事务的状态，如果事务是已提交的或者已中止的，则不需要执行任何操作，对于活动的事务，则在系统日志中加入一条记录，表明该事务已被中止，在构造数据页的时候，IPL管理器将忽略已中止事务的更新日志，以此完成事务的回滚，确保了事务执行的原子性。

IPL提出了一种新型的存储模式，这种存储模式稍做修改，就能够方便地支持事务操作。但是，IPL还存在以下问题：1）只能用于支持部分页编程的闪存设备；2）缓冲区中的日志扇区被相关的逻辑页独占，使大多数逻辑页在被换出时其日志扇区中的日志数量较少，故日志扇区被写入闪存时空间利用率较低，闪存中日志页的空间利用率也较低，导致需要写入的扇区数量仍然较多，而这又加快了块内日志空间耗尽的速度，引起了更多的合并和垃圾回收操作，从而影响了系统性能；3）将逻辑页与其日志存储在同一个块内，虽然有助于控制读取和合并代价，但各块内的日志空间大小相同，并未考虑数据更新频率的差异，造成空间浪费。

针对以上问题，文献[YueXJL10]提出了一种基于分离日志的闪存数据库系统存储管理方法，简称OPL。OPL令缓冲区中的日志块由多个逻辑页共享，当日志缓冲满时，集中写入到闪存的日志块中，因此，提高了空间利用率。并且，OPL将所有逻辑页的日志集中写入闪存的日志块内，而不是像IPL，使用部分页编程技术将日志写入逻辑页所在的块，降低了硬件依赖，因此，能够适用于更多的闪存设备。OPL与IPL一样，构造数据页时，需要扫描所有与数据页有关的日志页，但是，OPL使用打包算法将和同一个逻辑页相关的各日志存放到尽量少的日志页中，以减少读取逻辑页时需要读取的日志数量。OPL主要是针对IPL存储的空间利用不足的改进，对于事务操作的支持，OPL与IPL的思想一样，在此不再熬述。

IPL与OPL都是给出一种新型的存储模式，以提供性能较高的对数据库的操作，它所提出的恢复技术主要是针对这种新的存储方式的一种扩展。因此，IPL与OPL不能方便的扩展到现有的大量数据库中。同时，IPL与OPL的存储方式是针对原始的闪存存储器的，而不是现在被简单广泛地应用在SSD上，因此，它们具有相当大的局限性。

9.4.5    HV-Recovery

文献[LuMZ10]提出了一种适合于闪存数据库的日志恢复方法，即HV-Recovery。虽然HV-Recovery使用了日志记录数据的更新，但是，HV-Recovery在事务恢复时，充分利用了闪存设备异地更新产生的逻辑页的历史版本，所以，HV-Recovery其实是一种日志事务恢复方法和影子页事务恢复方法相结合的恢复方法。HV-Recovery通过日志记录逻辑页的历史版本的地址，在事务恢复时检查逻辑页的历史版本是否可用，如果历史版本中的数据没有被破坏，在事务恢复时，就将逻辑页地址映射到历史版本中，不用写入新的数据，从而显著地提高了事务恢复操作的效率。

日志一般都是一些小的写操作，为了节省闪存空间，减少日志记录产出的大量闪存写操作以及闪存写操作引发的代价高昂的闪存擦除操作，HV-Recovery提出了基于磁盘与闪存的混合存储系统，如图[HV-recovery]所示。HV-Recovery将数据存放在闪存上，将日志记录存放在磁盘中，通过这样的设计，节约了日志记录所占用的闪存空间，减少了大量写日志操作，从整体上提高了数据库系统的性能。

图[HV-recovery] 混合存储架构图

HV-Recovery之所以能够在事务恢复时利用逻辑页的历史版本，是因为它使用了一种全新的日志记录方法，即version_list。version_list是一个用以保存日志记录版本列表，其结构如表[version-list]所示。version_list中的日志记录包含了事务ID、逻辑页号、逻辑页的历史版本(PreAddress)，以及逻辑页的旧值(PreValue)。

Table[version-list] structure of version_list

表[version-list] version_list结构图

Tid	元素	PreAddress	PreValue
T1	X	P(X’)	X’
T2	A	P(A’)	A’
T4	D	NULL	NULL
T4	B	P(B’)	B’
T4	B	DELETE	NULL
T2	Y	P(Y’)	Y’
T1	X	P(X’’)	X’’
T1	commit	NULL	NULL
……	……	……	……

HV-Recovery遵循日志先写原则，如果事务改变了数据库元素，则日志记录必须在数据库元素的新值写到外部存储器前写出；如果事务提交，则事务提交日志记录操作必须在事务改变的所有数据库元素已写到外部存储之后再执行。在HV-Recovery中，事务更新与事务恢复时，对version_list的操作如下：

• 事务更新需要在version_list中写入更新日志。任何事务对数据库的更改操作都会产生一条日志记录，日志记录包含了事务ID、逻辑页号、逻辑页的历史版本以及逻辑页的旧值。事务修改一个逻辑页就添加一条日志记录，如果事务一次修改多个逻辑页，就添加多条日志记录，如表[version-list]中的第2条记录和第7条记录；如果事务插入一条新记录，则在日志中添加一条日志记录，这条日志的PreAddres和PreValue为空，如表[version-list]中的第3条记录；如果事务删除一条记录，则在日志中添加两条日志记录，第一条日志记录逻辑页的历史版本和旧值，第二条记录用一个DELETE标识表示删除操作，如表[version-list]中的第4条记录和第5条记录；如果事务多次修改一个逻辑页，则需要多次添加日志记录，如表中的第1条记录和第7条记录。
• 事务提交需要在version_list中写入事务提交日志。每当有事务提交时，HV-Recovery就在日志记录文件，也就是version_list中对该事务添加一条新的提交记录，如表中的第8条记录。
• 事务恢复的过程与传统的基于日志的恢复方法不同，HV-Recovery能够利用闪存中天然存在的历史版本，高效地执行事务恢复操作。由于HV-Recovery对日志记录和数据更新的提交顺序满足日志先写原则，所以，只需要对日志记录中体现为尚未提交的事务进行恢复。事务恢复时，先从外部存储中读入日志记录，然后根据这些日志记录，读出需要恢复的各数据项的历史版本的地址，从中取出数据，判断是否与日志记录中存在的旧值相同，若相同，将已写入新更新数据内容的地址标识为无效，将原地址标识为有效，并在地址映射表中将逻辑页的物理地址映射到原地址，从而完成恢复；若不同，则只有重新写入，在闪存中新分配一页，写入日志记录中的旧值，以此完成逻辑页的恢复。

HV-Recovery通过使用一种全新的日志记录方法，充分利用了闪存设备异地更新产生的逻辑页的历史版本，显著地提高了数据库恢复操作的性能。但是，HV-Recovery没有考虑事务的并发性，同时，在事务更新与事务提交时，需要写入大量的日志记录，虽然HV-Recovery通过将日志记录存储在磁盘中，减少写日志的代价，但是，HV-Recovery采用了基于磁盘和闪存的混合存储系统，增加了数据库系统的复杂性。

9.5  本章小节

本章内容首先介绍了事务的概念、事务的特性，并分析了传统的事务恢复机制在闪存数据库中的表现，说明了针对闪存数据库设计新的事务恢复方法的必要性；然后，重点介绍了几种典型的闪存数据库事务恢复方法，针对闪存数据库设计的事务恢复方法大都借鉴了影子页的思想（如Transactional FTL、TxFlash和Flag Commit），在闪存的物理页的带外区存储事务提交标识，通过事务提交标识跟踪事务的状态，以此减少写日志操作的数量，提高事务恢复的效率；接下来，又介绍了一种基于日志记录的事务恢复方法，该方法适用于日志结构的文件系统（ Log-Structure File System）；最后，介绍了一种日志恢复技术与影子页恢复技术相结合的事务恢复方法。在介绍不同的事务恢复方法的同时，还分析了各个事务恢复方法的优缺点和应用场景。

9.6    习题

1. 什么是事务？
2. 事务有哪些特性，ACID各指的是什么？
3. 为什么基于日志的事务恢复方法不适合闪存数据库？
4. 考虑一个事务T3，它需要一次修改P1，P4，P7，P2，其中P1的物理页地址为（1，0），为它分配的影子页地址为（0，0）；P4的物理页地址为（1，2），为它分配的影子页地址为（0，2）；P7的物理页地址为（1，3），为它分配的影子页地址为（0，3）；P2的物理页地址为（1，1），为它分配的影子页地址为(0，1)。请画出AFC算法执行事务T3的快照（参考图图[CFC-example]）。
5. 下图是一个BPCC算法的例子，请指出逻辑页A、B、C和D的最新已提交版本。

图[BPCC-algorithm-example] BPCC算法的一个实例

    6. 文中介绍的几种事务恢复方法，有哪些方法在事务提交时不需要写入事务提交日志？