Write-Behind Logging

这篇论文主要探讨了在传统DBMS系统中，WAL log所扮演的角色和发挥的作用，在NVM设备出现后，DBMS和WAL log原有基于DRAM和磁盘设计的架构并不能完全发挥出NVM设备所提供的特性。WAL log作为DBMS的事务记录以及故障恢复的重要机制，其读写效率大大影响了DBMS系统的写入性能和故障恢复速度。因此作者在此篇论文中，着重讨论了如何基于NVM设备所带来的新特性，来设计一个具有更好性能和更快故障恢复速度的新的日志系统，也就是今天的主题WBL（write-behind logging）。

WBL设计的核心原则在于，记录DBMS中的数据改变了什么，而不是记录其是如何改变的。我们会在后续的讨论中去完整的阐述这句话代表的意义。WBL在DBMS将数据的更改全部持久化后，才将log写入到NVM设备中，并且通过原子写入log的模式，保证了事务修改数据的持久性和原子性。WBL还减少了每条事务需要记录的log的大小，因此也大大减少了对NVM设备的写入次数，提升了NVM设备的使用寿命。

WBL在该篇论文的数据统计中，针对传统的WAL模式，提升了DBMS系统事务吞吐大约1.3倍，其故障恢复速度提升了2个数量级，并在同样的NVM设备上，节省了大约1.5倍的空间。

并且作者还设计了针对多副本模式下的WBL log协议。

在介绍WBL之前，我们先回顾一下数据DBMS已有的一些机制。

恢复机制和NVM带来的新特性

恢复机制

DBMS为保证数据的一致性，需要有两个约束，分别是更新持久性和故障原子性：

  • 更新持久性：所有已提交事务的数据更改一定是持久化的
  • 故障原子性：中止的事务（事务冲突，失败等）或者在DBMS发生故障时未成功提交的事务，他们对数据的修改要保证对后续的事务不可见。

这两个约束保证了数据库的数据完整性，在出现系统故障，比如掉电、系统crash等情况下，数据库依然能完整的恢复到出现故障前的状态。

DBMS中常见的故障分为以下三类：

  • 事务中止：当前事务和另一个事务发生冲突时中止事务，或者应用程序自己执行了事务中止。
  • 系统故障：当DBMS/OS中的错误，或者计算机硬件故障发生的系统故障。
  • 存储设备故障：NVM/SSD/HDD等非易失性存储设备损坏造成数据丢失。

针对这三种故障情况，DBMS对那些未完成提交事务，必须保证数据恢复到之前的一个特定版本，且这些事务对数据的修改也必须撤销，并将这些事务的log也进行清除，以保证故障原子性。

现有的大多数DBMS都采用了steal和no-force策略来管理DRAM中的修改数据和存储设备上的持久化数据，steal策略允许DBMS随时刷新对未提交事务数据的修改，no-force策略则允许事务在提交时不将DRAM中的修改数据刷写到持久化存储设备中，但需要保证在向应用程序返回事务提交完成时，将对应事务的更改持久化在log中。

在DBMS因故障而发生重启Recovery时，需要通过log来保障其数据的原子性和一致性，Recovery算法通过在log中的记录来恢复故障时刻的数据库状态，针对已提交完成的事务，需要确保其在log中记录的数据更改操作全部生效，执行redo操作来完成数据修改的回放，针对未完成提交的事务，需要将这些事务带来的数据更改进行撤销，执行undo操作来完成数据更改的撤销。针对存储设备故障，DBMS通过在多个存储设备上存储数据，日志和数据库的归档（即checkpoint）来实现数据完整性。

NVM带来的新特性

传统的HDD盘具有高数据密度，价格低廉，持久化稳定的优点，但也无法摆脱机械盘寻道带来的开销，而且顺序访问和随机访问的性能差异巨大。

SSD相比HDD来说具备更加好的读写性能，其读写时延相比HDD来说低3个数量级。但针对DBMS系统来说，SSD也存在三个问题：

  1. 仅支持面向block的访问模式
  2. SSD的NAND只有固定的擦写次数，存在寿命问题
  3. SSD的成本过于高昂，每GB的价格是HDD的3-10倍

SSD/HDD的读写速度限制了使用它们来存储log的DBMS系统的性能，主要是因为DRAM和SSD/HDD存在巨大的随机与顺序访问延迟差异，以及两者的数据访问粒度也存在差异（即粗粒度的面向块的访问模式，细粒度的面向字节的访问模式）。

新生的NVM技术，如PCM，STT-MRAM以及RRAM，提供更快的读写访问速度，且提供细粒度的面向字节的访问模式。与使用SATA接口的SSD/HDD相比，NVM设备可以插入DIMM插槽，通过PCIE接口进行访问，为CPU提供了更高的带宽和更低的访问时延。且如下图所示，NVM设备的顺序访问和随机访问的差异相对SSD/HDD来说非常小。

但NVM设备也存在价格高昂，使用寿命有限的问题，如果DBMS将其直接作为数据存储来使用，将会大大增加系统的成本，因此需要去优化NVM的写入数据量，来增加NVM设备的使用寿命。另外一种比较经济的使用方案是将DBMS的log数据存储在NVM设备上，将数据存储于价格相对便宜的SSD/HDD上，但这种方案只利用到了NVM设备的低延迟顺序写的特性，并没利用起来NVM设备的随机写入和细粒度的面向字节访问的能力。鉴于此，针对DBMS系统，作者设计了一种专门为NVM设备上使用的log记录和恢复算法，并将其称之为WBL，并将其应用在CMU的自研数据库Peloton中。

如图所示，分别是基于WBL和WAL的DBMS的性能统计，由图可得，WBL在吞吐，故障恢复延迟，以及log存储空间占用方面，都远远处于优势，尤其是在DBMS出现故障恢复时，WBL具有非常快的恢复速度，为什么会有如此大的差异呢，随后我们将慢慢道来，首先会分别阐述一下WAL和WBL的工作方式，分别从Runtime Operation **，Commit Protocol** 和**Recovery Protocol **，以及两者在其中的差异，来阐述一下WBL的优势所在。

WAL

基于WAL设计的最著名的恢复方法是IBM在20实际90年代开发的ARIES协议。ARIES协议中提出了redo和undo操作，在DBMS正常工作状态中，需要记录redo和undo log，并将其保存在持久化设备上，在出现故障恢复时再去读区log并执行相应的redo和undo操作来保证数据完整性。

作者基于多版本协议控制（MVCC）协议来调度事务的DBMS进行了对WAL的探讨，MVCC现在DBMS系统中使用最广泛的并发控制方案。在MVCC中，DBMS将meta数据的版本和元组数据都记录下来，并通过meta数据决定元组数据对事务是否可见。每个元组的meta数据由以下数据组成：

  • TxnId：事务标识符，全局唯一，递增
  • BeginCTS & EndCTS： 元组可见的时间戳范围，事务提交时间在其中的才对该元组数据可见
  • PreV：之前版本数据的指针（如果有之前版本的话）

在事务开始时，会通过一个计数器分配给事务一个全局唯一的TxnId，并事务分配一个事务提交时间戳，只有事务提交时间戳在元组的BeginCTS & EndCTS范围内，这个元组的数据才对该事务可见。如果该元组上曾经发生过update操作，即元组还有更早的版本，则还需要PreV指针指向更早版本的元组。

Runtime Operation

WAL在Runtime Operation阶段执行顺序为：

  1. DBMS会先执行该事务中包含的操作
  2. 然后会将此次事务修改后的数据写入DRAM中
  3. 紧接着创建一条与更改相对应的log
  4. 最后将这条log写入至log文件的buffer中。

WAL log的数据结构如下图所示：

LSN：唯一的日志序列号

Log Record Type：当前log的操作类型（Insert，Update或者Delete）

Transaction Commit Timestamp：事务提交时间戳

Table Id：表ID

Insert Location：插入元组的位置，新写入数据的元组的位置

Delete Location：更新前元组的位置，即旧版本的位置。

After Image：修改后的镜像（即更新后的值）。

同时DBMS中还维护了两个用于恢复的元数据表：

  • DPT(Dirty page table)：脏页表，事务修改后尚未flush到持久话存储设备中的数据页，这些数据页都会有一条对应的最后一次修改它的log的LSN，DPT中的数据和log中的数据需要在Recovery中回放这些操作，恢复数据修改。
  • ATT(Active transaction table)：活动事务表，这里面会记录所有活动事务的最新日志记录到的LSN，用于追踪正在运行事务的状态。

DBMS还会周期的对数据进行Checkpoint操作，用于提升Recovery过程的效率，DBMS会将DPT中的数据和ATT中的数据作为检查点的一部分，然后会将已经事务提交完成的数据页进行flush，并且删除其在WAL log中的记录。

Commit Protocol

事务在commit阶段的过程：

  1. 首先会整理log文件的buffer
  2. 然后将其从buffer中的数据sync到持久化存储设备中
  3. 将事务标记为已提交状态
  4. 通知worker线程进行group commit
  5. 通知应用程序commit完成

在WAL log模式下，当一个事务开始时，DBMS会在ATT中创建一个entry，并且将其标记为active状态，后续针对这个事务对数据库的每个修改，DBMS都会创建对应的log记录，并且将其追加到log buffer中。然后更新所有在ATT中相关联事务的LSN。

在事务提交之前，DBMS会将事务相关联的所有log通过fsync命令flush到持久话存储当中，即所谓的同步日志记录(synchronous logging)。最后，DBMS从ATT中将该事务的状态标记为已提交。

使用WAL时，从DBMS到持久化存储的的写入顺序如下图所示：

  1. 事务对数据的修改首先应用于DRAM中的Table Heap和索引
  2. 在事务提交时，WAL要求DBMS必须将事务所有的修改flush到持久化存储设备中
  3. 最后会周期的进行CheckPoint操作，在此过程中会将log中的修改完全应用到数据库中，并清除对应的log

通常每个事务都会产生很对条log，并且每条log的大小都很小，针对这种情况，DBMS为了提高事务的吞吐和减少单次访问持久化设备的平均开销，采用了group-commit的模式来合并多条log记录一起flush到持久化存储设备中。

Recovery Protocol

如上图所示，传统的WAL的恢复算法分为3个阶段：

  • Analysis

    在Analysis阶段，DBMS从最近的Checkpoint开始处理log，并从log中筛选出在DBMS出现down时，正在活动的事务，以及这些事务对数据库的修改。

  • Redo

    在Redo阶段，DBMS首先加载一个新的ATT，并从Checkpoint之后的最早的那条log开始处理，将log中记录已提交事务对数据库的修改操作进行回放并保证其持久化存储。

  • Undo

    在Undo阶段，DBMS将log回放过程中未提交的事务的log内容跳过，不作处理，并且如果是Delete或者Update操作，还需要将tuple的数据回滚至以前的版本。

在MVCC协议中，简化了回放log算法，在redo阶段，DBMS会直接跳过那些重复的和未提交的log条目，即将Redo和Undo两部分合并在了一起。

虽然WAL对事务的高效处理支持的还算不错，但因为DRAM的易失性和持久化存储设备不支持快速随机写入，并不能完全将NVM设备的特性发挥出来。以及每个事务会有多条非常小的log，频繁的对NVM设备的写入对NVM的寿命损耗也比较大。

WBL

在总结了WAL的整个机制之后，现在来探讨一下论文中所设计的WBL机制。

WBL机制完美利用了NVM设备的高读写性能，按字节存储等优点，WBL的特点是在数据成功flush到持久化存储设备之后，才记录一条log。相比于WAL，WBL具备更好的写入性能和更快的故障恢复速度，主要原因有三：

  1. NVM设备的写入带宽相比SSD/HDD来说高出了数量级的差距
  2. 相比SDD/HDD来说，NVM设备的随机访问能力和顺序访问能力间的差距很小
  3. NVM设备提供了按字节存储的特性，这使得CPU可以直接访问NVM设备中的字节，从而不需要将数据组织成page或通过IO系统访问。

Runtime Operation

WBL相比WAL来说有很多方面的不同之处，最主要的是WBL不会在log中记录数据库元组的修改信息，因为在记录log的时候，事务已经完成了提交，且对数据库的更改都已经全部同步到了持久化存储设备中。当一个事务去修改数据库中的值时，DBMS会将其写入到一个dirty tuple table (DTT) 中去追踪这个事务的执行过程，每一条在DTT中的记录都包含了事务ID，类型等数据，类似于WAL中log中记录的数据。对于Insert和Delete操作，DTT中的记录会包含插入和删除的tuple的位置，针对Update操作，需要包含新值和旧值的位置，但DTT中的记录从来不会包含after-images的tuple。在事务提交时，会将DTT中的数据进行清空，DTT中的数据都在内存中，从来都不会写入到NVM或者其他持久化存储设备中。

在事务执行过程中，WBL中主要完成了：

  1. 执行事务操作
  2. 将对数据库的修改写入到内存中
  3. 将数据修改记录写入到DTT中，且一定不包含after-images的tuple

Commit Protocol

WBL放宽了数据写入到持久化存储设备中的顺序，即先将修改后的数据写入到持久化存储，再记录log的模式，会使得WBL的事务提交和故障恢复变得很复杂。DBMS在故障恢复过程中，必须要确定在故障的那一刻，哪些事务的数据是需要redo操作来进行回放的，而哪些数据又是需要undo操作来进行丢弃的。而在WBL的模式下，很可能会因为数据刷写到了持久化存储设备，但还未有对应的log来记录这一操作而导致数据的回放无法正确的辨识这些修改，故而在回放过程中可能需要扫描整个数据库来鉴别哪些数据是正确的，这对于DBMS的故障恢复来说是不可承受的。

在事务Commit阶段，为了解决如何通过log去记录从DRAM中将事务对数据库的修改flush到持久化存储设备的过程，作者设计了新的WBL的log entry结构，并且通过两个事务提交的时间戳来记录对数据修改的tuple的可见性，log entry结构如下图所示：

LSN：唯一的日志序列号

Log Record Type：当前log的操作类型（Insert，Update或者Delete）

Persisted Commit Timestamp(Cp)：最后一条事务提交的时间戳

Dirty Commit Timestamp(Cd)：DBMS分配给当次事务提交时，所产生的最大事务提交时间戳

在WBL中，也是采用group commit的模式来flush数据，在当前事务提交时，实际可能已经有很多个事务的数据已经flush到持久化存储设备中了，因此选取最后一个提交事务的提交时间戳作为Cp，表示在Cp这个时间戳以前的数据都是有效修改，都已经持久化在了存储设备中。同时，DBMS会分配出一个在此次事务提交完成之前的一个时间戳作为Cd，DBMS保证了当前所有flush到持久化存储设备中的数据所对应的事务的提交时间戳都小于Cd。即当前早于Cp的数据是已经确定可见了，故障恢复时不需要清理这些数据，处于(Cp,Cd)之间的数据是不可见的，故障恢复时需要将这些数据进行清理，且DBMS保证在此次事务提交完成之前，不可能产生比Cd还大的事务提交时间戳。只有事务提交时间戳早于Cp的事务才会通知应用程序为事务提交完成，而处于(Cp,Cd)之间的的事务提交，还需要等待下一轮的group commit来完成。

事务在commit阶段的过程：

  1. DBMS检查DTT中的条目，确定事务所关联的所有修改后的脏tuple
  2. 为本次group commit计算Cp和Cd
  3. 执行sync操作将DRAM中修改之后的脏数据块flush到持久化存储设备中
  4. 执行sync操作将包含Cp和Cd的log flush到NVM设备中
  5. 通知worker线程进行group commit
  6. 通知应用程序commit完成

在事务group commit过程中，可能会存在有些长事务，即可能在本次group commit完成时，还会有事务没有完成提交，这些未完成提交事务的时间戳会被记录在下一轮group commit的log中，私以为将这种事务的时间戳称之为Cl，则实际log中需要记录的事务提交窗口为(Cl,(Cp,Cd))，直到这个长事务提交完成后，才将Cl不记录在下一轮的group commit的log中。

在事务group commit过程中，可能会出现一个事务中修改的数据处于两个不同的Table中，即刷写到持久化存储设备中的tuple的位置实际上并不连续，这样一来如果使用NVM设备作为持久化存储设备，可以充分利用NVM设备的高性能随机访问能力。

对于那些未完成提交的事务，即中止的事务，会依据在DRAM中的DTT中记录的信息，完成这些事务对数据修改的撤销操作。

如上图所示，WBL的写入模式为先写入DRAM中的Table Heap，在其中完成对数据库数据的修改和索引信息，在事务提交时，DBMS会将内存中的所有此事务关联的数据全部flush到持久化存储设备中，最后在NVM设备中记录log。

Recovery Protocol

在WBL中，故障恢复过程只需要Undo操作。作者设计了commit timestamp gap的一种数据结构来控制在故障恢复阶段的数据处理，即在上文中所提到的(Cp,Cd)。在恢复过程中，针对事务提交时间戳位于(Cp,Cd)中的数据，都会视为事务未提交完成，即对这些数据进行清理，DBMS有专门的垃圾收集器线程去扫描处于(Cp,Cd)的tuple的数据修改，并将其撤销，当垃圾收集器完成对所有处于(Cp,Cd)的tuple数据的修改撤销，页会把这条log也做清除处理。

使用WBL机制时，不需要定期构建类似于WAL的Checkpoint机制来加快故障恢复速度，因为每个WBL log中已经包含了所有故障恢复所需要的数据，即commit timestamp gap (Cp,Cd)，和长时间未提交完成的事务提交时间戳Cl，即提交窗口(Cl,(Cp,Cd))，在故障恢复过程中，只需要对处于这个间隔的数据进行undo操作即可，并且在每次log最新纪录时，既可以删除以前较老的log，以保证log实际的大小永远都很小，这极大的加快了故障恢复的速度。

如图所示，实际WBL的故障恢复过程只包含一个Analysis阶段即可，不需要redo阶段，因为事务对数据库的修改都已经刷写到持久化存储设备中了。在完成对数据tuple的确定和撤销操作后，DBMS就立马开始接收并处理新请求了。

以上的讨论都是基于MVCC的模式，如果在一个单版本的DBMS中使用WBL，则数据库需要在修改元组时将旧版本的元组进行copy，当事务发生回滚或DBMS处于故障恢复时，需要将修改后的数据进行撤销，并且恢复原有旧版本数据的可见性。

多副本

在WAL和WBL中，针对事务中止，系统故障都通过log来实现其数据完整性的恢复，但针对存储设备故障，并不能通过WAL或WBL来解决这一问题，而是需要通过主从备份或多副本的模式来解决这种问题。即当主服务出现设备故障，造成数据丢失时，备份服务依然可以提供读服务来避免数据丢失。

在WAL中，可以通过同步log的方式来完成数据备份，副本节点只需要回放其log既能完成数据的备份工作。但在WBL中，在log记录里并不包含真实的数据（比如after-images ），因此需要在WBL中增加一些额外的步骤来保证数据的主备复制。作者在WBL采用在log中增加类似于WAL log中的操作日志的模式来记录事务对数据库数据的修改变更，并将其同步给备份数据库服务，从而完成数据主备工作。其中又分为两种不同的模式：

  • synchronous
  • asynchronous

如上图所示，如果是synchronous模式，WBL在主库执行完所有操作后，还需要等待备库也完成所有操作后才能向应用程序返回处理结果，即需要完成1-4步骤。如果是asynchronous模式，WBL在主库执行完所有操作后，就可以向应用程序返回处理结果，同时异步的将log同步到备份库，但不需要等待它返回执行结果。

synchronous和asynchronous模式对数据库发生failover 时有不同的影响。当主库出现异常down时，synchronous模式因为主备的数据是完全一致的，则备库可以直接接管服务。asynchronous模式有可能主备数据并非一致，所以会导致备库如果接管服务会使得最近的事务产生的修改不生效。

Benchmarks

作者分别将WBL和WAL模式在NVM、SSD和HDD上进行测试，并且在相同的情况下进行了测试。

通过使用YCSB对6类log模式做了测试，测试场景和具体表现如下：

  • Read-Heavy: 90% reads, 10% updates
  • Balanced: 50% reads, 50% updates
  • Write-Heavy: 10% reads, 90% updates

如图所见，WBL无论是在吞吐还是在访问时延方面，在相同的存储介质下，都普遍优于WAL。在同一日志协议下，NVM>SSD>HDD的吞吐和时延也是处于一个下降的过程中，即佐证了WBL在NVM设备上发挥的功效更为强大，其基于NVM的设计时有意义的。

同时我们也在回顾一下WBL和WAL的故障恢复速度的对比图，也可以得出WBL在同等条件下，具备超快恢复能力，相比WAL高出了数量级的差距。