在过去的几十年，关系数据库系统在商业应用中扮演着重要的角色。数据库系统作为基础软件为上层应用提供丰富的特性以支持多样化的工作负载。因此，数据库系统在很大程度上决定了上层软件设施的性能。关系数据库系统的设计可以追溯到上个世纪70年代初。在传统的数据库体系结构中，磁盘是主要的存储设备，磁盘I/O是主要的性能瓶颈。计算机一般配备单CPU与十分有限的内存资源。单线程的处理速度、系统运行所占内存资源以及I/O子系统成为影响存储管理系统性能的重要因素。设计高效的并发线程调度策略以隐藏磁盘I/O 延迟是取得高吞吐率的关键。

这种面向磁盘I/O 与单处理器优化的传统数据库引擎设计思想已经跟不上时代发展的潮流。我们认为目前数据库系统的主要矛盾是飞速发展的硬件（多核处理器，Non-Volatile Memory）与始于上世纪70年代单机数据库系统的设计思想。因此，修改单机数据库系统的设计思想（甚至重构数据库系统），借鉴分布式的思维是否有必要也成为在学术界与工业相当热点的一个问题。从最近的发展趋势看来，这是一个方向。这篇文章我们主要探讨利用distributed logging优化单机数据库系统（锁管理器引入的分布式思想也是相当有趣的一个话题，我们先按下不表，主要讨论日志子系统）。

一、WAL(Write-Ahead Logging)

预写式日志 （WAL）是数据库通常采用的一种事务日志实现方法。WAL 的核心思想是保证对数据文件（即存放表和索引等数据库对象的文件）的修改发生在日志记录的持久化之后。

换句话说，描述数据文件变化的日志记录到达永久存储器的时间必须先于数据文件的物理变化时间。如果遵循这个约束， 那么在事务提交时，DBMS不需要把该事务修改过的数据页强制冲刷到磁盘。如果系统崩溃，日志可以用来恢复数据库，即将日志记录所描述的所有尚未实施于数据页的改动全部重做。这称为向前滚动恢复或REDO。

日志模块保证了日志记录到达稳定存储介质的次序比该日志记录所描述的数据更新要早。为了实现这个保证，每个数据文件（无论是堆文件或者索引文件）的页头都保留对应该页面的最新日志记录的LSN（Log Sequence Number，实际上就是该日志记录在WAL文件中的偏移量）。同时，系统跟踪记录了日志缓冲区中已经冲刷到磁盘的日志的最新位置，flushedLSN。当缓冲区管理需要写出脏页时，它必须确保相应的日志记录已经冲刷到磁盘，也就是满足约束：       

图1给出了WAL的工作模式。对于已经刷出到磁盘的页面，它的pageLSN肯定满足pageLSN<= flushedLSN。对于还驻留在内存的数据页，它的pageLSN可以大于flushedLSN，也可以小于flushedLSN。WAL系统使用磁盘与缓冲区两层存储以及一个集中式的日志。事务将写操作聚合到缓存区，并且持久化到日志。该机制将磁盘的随机读写转换：

图1. WAL 工作模式

成顺序读写。这种写日志的方式是针对磁盘的优化，并且也已经被证明能够提供原子性与持久性的保障。日志文件包含对应每个更新操作的重做与撤销记录。如果堆文件的更新没有反映到磁盘，堆文件按照重做记录重放历史。撤销记录提供必要的回滚操作以移除中止事务与未提交事务的更新操作。恢复从最近的一个的检查点开始。检查点由系统定期创建并在日志中标记。恢复子系统顺序扫描重做日志文件直到结束，进行重放历史操作，将DBMS恢复到系统崩溃前状态；接着，利用撤销日志记录回滚未完成事务的操作。

为了有个具体的概念，我们首先探讨MySQL与PostgreSQL的WAL实现以及相应的问题。

在MySQL中， MTR（Mini-Transaction）将事务日志一开始存储在私有的局部缓冲区里面。如果MTR产生的日志不能用一个缓冲块装下，那么需要用链表将多个缓冲区块链接起来。Mtr将事务日志提交到公共的log buffer在mtr::Command::execute函数进行。这个函数的主要逻辑如下：

代码片段1

从代码片段1可以看到，mtr将日志记录提交到公共log buffer主要经历以下两个步骤：

1）计算redo record的长度。从这个过程开始，事务开始持有log buffer上的锁，log_sys->mutex。这个步骤主要由函数prepare_write完成。

2）将日志记录拷贝到公共缓冲区log_sys->buf。

拷贝需要区分两种情况，第一，mtr只存在于一个log buffer block上；第二，mtr的日志记录由多个log buffer block组成。如果mtr产生脏页，那么还可能需要将脏页挂在flush list上。在更新密集型的工作负载场景中，这个log_sys->mutex锁的竞争是非常严重的。PostgreSQL在9.4版本以前的WAL设计也类似MySQL，其保护日志缓冲区的临界区的代码长度大概有300-500行。后来社区的开发人员在其上做了一层抽象将临界区的代码量缩短到5行，同时将日志拷贝独立于临界区之外。

通过这两个优化，在不同的工作负载下，PostgreSQL的性能能够提升30%。优化前与优化的逻辑如图2所示。黄色部分代表事务的等待时间。从图2(b)可以看到，优化后，事务之间可以并行插入日志。这或许也可以作为MySQL的一个优化方向。
 

图2(a). 优化前的日志插入流程

图2(b). 优化后的日志插入流程

Pg9.4对预留空间的设计做了一层抽象。首先计算出日志子系统可用的空间，该过程需要去除页面的头部，以及segment 的头部大小。这个空间是全部可用来做日志记录存储的。通过这层抽象，这个函数将自旋锁（系统热点）持有时间最小化，临界区内只需要进行如下简单的计算即可。

临界区外面，系统进行实际的地址换算。该设计的另外一个问题是在日志刷盘的时候需要追踪哪些事务已经将日志拷贝完成，哪些没有。PostgreSQL9.4的做法是事务在插入日志的时候需要申请另外一种锁（这个锁设置为N=8，16等，因此这种锁不会成为性能瓶颈，也可视为分布式思想的一种体现）。因此，事务申请将日志刷盘的时候只需要简单检查这些锁空闲没有。

如图2所示，有4个事务(trx1、trx2、trx3、trx4)将日志提交到公共日志缓冲区。其中trx1已经拷贝完成，然后将锁释放。刷盘请求可以开始的前提是所有拷贝都已经完成，等价于正在进行拷贝日志的事务所持有的锁都已经释放。为了避免饥饿，PostgreSQL在这点的设计上利用优先级思想可以快速检测到锁的释放，非常巧妙，有兴趣的同学可以阅读源码。在这里不详细展开讨论。

图2. 并行日志插入

总结一下，PostgreSQL的日志插入流程如下：第一，获取指示拷贝是否完成的锁；第二，在公共缓冲区上预留相应空间；第三，将日志记录拷贝到预留空间，事务间可以并行执行；第四，释放步骤1的锁。

二、集中式设计带来的问题

纵观以上两个主流数据库系统的WAL设计，都存在热点问题，如图3所示。在多核环境下这容易成为系统的热点，限制系统的扩展性。虽然PostgreSQL在WAL的设计进行了大量的优化。但在大并发下还是存在相应的问题。

图3. 集中式WAL设计的问题

日志管理器上竞争激烈的本质原因是系统强制给不相关的更新事务规定顺序。实际上，系统大部分事务没有冲突，并行地执行。因此引入分布式思想，设计日志子系统可以缓解系统瓶颈。系统不再使用一个日志管理器，而是将负载分散到N个不同的日志管理器上，提高写日志的并行性（distributed logging），如图4所示。在DBMS中随处可见这种分布式设计思想，例如锁表的设计和数据缓冲区的设计。PostgreSQL中的锁表不是单纯地进行集中式管理，而是利用哈希的方法将锁表划分成不同的段。在这种设计方法下，不同段上的锁申请、释放不会相互阻塞，提高系统并发度（PostgreSQL的继承锁思想进一步优化了系统性能）。

类似地，PostgreSQL中将缓冲区中的哈希表划分成NUM_BUFFER_PARTITIONS部分。在distributed logging设计下，事务通过调度器在特定的日志缓冲区上进行日志追加操作。系统需要针对distributed logging重新设计建立检查点机制与恢复算法。调度器的功能可以是执行简单的映射操作，即利用（事务代理进程号 ProcID） MOD（日志管理器的个数 N）得到该事务对应的工作日志管理器。复杂一点可以在每个日志管理器上维护一个工作队列统计在该管理器上的负载信息，然后将新到来的请求分配到等待队列最短的日志管理器上，消除简单映射操作可能带来的倾斜。使用分布式日志必须解决以下三个问题：

• a) 日志序列号LSN（日志记录在磁盘上的地址），标准的系统单位时间，在分布式日志中不具有可比性。我们需要有其它的方法可以建立系统范围的时间。这种全局范围的时间戳是非常重要的，因为页面频繁地在不同的日志管理器之间迁移。当针对页面P的更新记录依次出现在日志管理器L1与L2，系统时间戳保证恢复程序首先处理L1上的日志记录。
   

图4. Distributed logging

• b) 集中式的日志设计方案中，日志持久化以串行的方式进行。系统也无需追踪事务的提交顺序。这个结论在分布式日志中不成立。系统需要保证事务的提交顺序按照一致性的方式进行。

• c) 分布式日志中，不同日志管理器会以不同的速率将日志文件刷新到磁盘。这可能导致“空洞”问题的发生，也就是系统崩溃的时候有些日志文件已经到磁盘，而有些日志文件已经丢失。日志文件从总体上看来是存在的“空洞”的。这将导致系统遇到不可恢复的情况，例如重做的时候删除一条根本就没有插入的元组。

后面的内容依次探讨这些问题的挑战以及相应解决方案。

在集中式日志管理器中，LSN是日志记录在磁盘上的地址，可以作为逻辑时间戳表示更新动作的先后次序。不同日志管理上的地址偏移不具有时间信息， 因此分布式日志系统不能够再使用原来的LSN。必须寻找其它机制来确定数据变更的先后顺序以便系统可以正确地运转，例如恢复阶段合并不同日志管理器上的日志记录以及WAL协议的保证等。一个可行的方法是维护系统范围时间戳SSN（SSN，System-wide Sequence Number）。每次插入一条日志记录前将SSN增加1。系统涉及到LSN的部分全部替换成SSN。恢复阶段根据SSN合并日志记录。

在高度并发的环境中一个串行点可能都会制约系统可扩展性。实际上，系统只要能够确定某个页面或者事务的更新序列即可，不同页面或者事务可以并行地执行，也就是日志记录只需满足偏序的条件即可。以后可以探讨利用Lamport时钟确立这种偏序关系，同时避免使用全局时钟。

在事务提交完成之前将锁释放会导致其它事务读到预提交事务的脏数据。这些事务称之为依赖事务，与预提交事务形成依赖关系。在集中式设计下读取预提交数据不会导致数据库产生不一致情况，因为依赖事务的提交日志记录不可能先于预提交事务到处达磁盘。这是由于在集中式日志缓冲区的设计下日志记录以追加的方式写入日志文件尾部，日志缓冲区页面顺序地刷新到磁盘。在distributed logging下，采用预提交技术的情况下追踪依赖就变得很有必要。这是一个开放性的难题。2014年清华大学与微软亚洲研究院发表过类似的研究，利用事务更新依赖图来减少主库与从库差距过大的问题（原因是主库多线程并发，从库单线程回放，事务更新依赖图可以识别不相关事务然后并行重放）。

对于没有采用预提交技术的系统，从本质上而言，上层锁机制能够保证冲突事务的更新日志记录按照事件的发生次序到达磁盘，无需追踪依赖。对于没有冲突的更新事务而且他们的更新对象不属于同一页面，根据现有的以数据页为恢复单位的模型，他们的日志记录到达磁盘次序对于系统恢复而言无关紧要。实际上，事务只要满足以上两个条件（没有冲突，并且更新对象不属于同一页面）提交时只是刷出其所在的日志管理器的缓冲区的数据可以保证恢复的正确性。

日志记录可以按照事务或者页面划分，也就是将同一事务产生的日志记录映射到某个日志缓冲区，或者将属于同一页面的日志记录映射到某个缓冲区。为了避免日志空洞问题（日志空洞问题是指后续的日志记录已经持久化，而先于该时间点的日志记录却已经丢失），上述两种方法都需要在事务提交的时候刷新多个日志缓冲区。

此外，日志文件以不同的速率写出到磁盘也会导致日志空洞问题。目前的研究尚没有找到有效的方法将日志记录归类到某个划分从而大幅度地减少划分之间的数据访问与数据页迁移。

从已有的技术实现来看，没有单节点的商用DBMS采用分布式日志。这主要是由于分布式日志带来大量的I/O操作，磁盘等块设备难以支撑。而现在Non-Volatile Memory下，例如3D XPoint，这种技术已经可以采用。当页面在不同的日志管理器迁移的时候，以下两个方法可以维护日志的完整性：其中一个方法是将脏页面写回；另外一个方法是将日志写回。因为页面在不同日志管理之间的迁移很频繁，上面列出的两种方法都会导致不可接受的I/O代价。

为了避免日志空洞且不用每次迁移都需要激发I/O操作，我们在外部可见事件发生的时候（例如事务提交或者写出脏页面）将所有日志缓冲区的内容写回磁盘。在创建检查点的时候，系统需要将各路日志进行同步，以便恢复算法选取合适的检查点进行恢复。

三、总结

硬件的发展、数据量以及业务需求是推动数据库系统技术发展的“三架马车”。关系数据库系统的设计源于上世纪70 年代。磁盘I/O 是那个时期系统性能的主要瓶颈，数据库系统主要面向磁盘I/O 与单处理器的优化。与此同时，硬件发展一直遵循摩尔定律。现在底层硬件设施已经发生了巨大改变。这使得数据库系统面临诸多新的挑战与机遇。如今Oracle也在针对Non-Volatile Memory重构DBMS。可以预见，在NVM下会涌现一大批的新理论，极大地丰富关系数据库理论基础，甚至是出现新的理论颠覆原有认知（CMU DBMS研究小组在NVM存储介质下下提出Write-Behind Logging）。

在这篇文章，我们探讨了利用distributed logging优化单机数据库系统，给出了相应的问题与解决方案。目前单机数据库系统性能很大程度上受制于WAL子系统。业界准备好distributed logging了么？我们拭目以待。