Transaction And Recover Overview

之前的B+Tree和BoltDB Internals文章，对数据库的存储层有了大概的了解。而 事务 是建立在存储之上的更高组件，是database必不可少的一部分，事务需要满足ACID特性，BoltDB中已经谈过。

数据库系统中，事务 需要协调多个组件，共同才能实现ACID。下面会依次总览这些组件。

page cache

数据库将磁盘上的数据，加载到内存中成逻辑模型，如BoltDB中的node，它提供一层缓存供其它层使用。一般称page buffer pool。这个缓冲池也是有内存大小的，所以需要page in和evict操作。

当数据库其它层，请求page时，会先通过page buffer pool查询，如果没有缓存，则从磁盘加载到内存，再提供出去。其它层对缓冲区的page更改是发生在内存中的，更改后的page会被标记成dirty page，直到这个page最终写入磁盘。

缓存回收

由于操作系统内存是有限的，page buffer pool的容量也是有限的，当容量不够时候，只能evict旧的page，如果旧page时dirty page，则需要先刷盘后才能换出。如果旧page，在被其它事务锁定或访问，则不能换出。

dirty page如果每次evict时都刷盘，肯定性能会很差，所以必然会batch操作，即后台进程单独记录evict的dirty page并在一个时机刷盘。

但为了实现durability，如果数据库crash，则dirty page还未刷盘，就产生了数据丢失。

为了满足durability，数据库一般都实现了WAL和checkpoint。需要刷的dirty page会先写入WAL，而checkpoint会记录当前WAL执行到的位置，当这个dirty page真实写入磁盘后，才会丢弃WAL里的只，并从page buffer pool中evict它。

锁定页

由于B+Tree的写放大特性，越靠近树的顶端，修改和读取的时越会被命中。因此，对这种page，可以锁定在page buffer pool中，不用和普通leaf page一样需要evict。

evict算法

有比较常见的FIFO和LRU。但对于B+Tree来说，每个page它们的权重并不是一样的，不能单纯的采用FIFO和LRU来evict，还需要考虑并发操作时，维护FIFO和LRU的代价。

clock-sweep和LFU可以作为参考，这里不做介绍。

recover

数据库系统构建在，硬件 和 操作系统 之上。必须要考虑这些软硬件的 稳定性 和 可靠性 等问题。所有durability是必须要考虑的问题。

因此，许多数据库系统，都会采用 WAL(write-ahead log)，预写日志，实现当数据库crash发生后，事务的恢复。WAL是一种 仅追加的预写日志，保存着数据操作历史，可以通过replay日志的方式，恢复还未刷盘的数据，它是数据刷盘前唯一的磁盘副本。

操作日志 和 数据日志

一些数据库使用 shadow paging技术(一种copy-on-write的技术，参考BoltDB的事务)，来确保事务 durability 和 atomicity。它的本质，修改的内容会被放入一个新的、未发布的shadow paging中，可以通过翻转meta指针，来让shadow paging可见，从而达到替换旧页的方式。

进一步思考，数据的任何状态变化，都可以通过日志方式记录下来，包含redo(重做)和undo(撤销) 这两个操作，对应数据变化前后。

日志类型 分为 物理日志(被操作的整个页，都会记录下来，包含操作前后)，逻辑日志(对应页的的具体操作，插入或删除某一条，以及相应的撤销操作)。物理日志用于redo操作，以缩短恢复时间。逻辑日志用于undo操作，以提升并发。

steal 和 force 策略

为了确定何时将内存中的更改 刷新到磁盘上，数据库定义了 steal/no-steal 和 force/no-force 策略。

这些策略 应用于 page cache。

• steal：事务提交前，允许 事务修改过的page，刷磁盘
• no-steal：不允许，将未提交的 事务内容，刷磁盘

steal解释成：将dirty page偷窃出来，并刷写到磁盘上，并加载另一个page到该位置

• force：事务提交前，强制 事务修改过的page，刷磁盘
• no-force：事务提交前，事务修改过的page，未刷磁盘，事务仍可以提交

force解释成：强制 dirty page，在事务提交前，必须将其刷写到磁盘上

数据库如果，采用steal或force策略不同的策略，其影响的是recover的redo 和 undo操作。下面会介绍一种算法。

ARIES

ARIES是1992提出的，一种 steal/no-force 策略。它的特点：

• 使用物理 redo log，来提高 数据库recover恢复的性能，因为物理日志能更快速的应用更改
• 使用逻辑 undo log，来提高 正常操作时期的 并发，因为逻辑撤销操作，可以独立的应用到page
• 使用WAL，来实现 在恢复时的，replay历史，从而完整的重建数据库crash前的状态，这么理解WAL在redo和undo之前阶段

并发控制

数据库系统 避免不了 并发操作，针对 不同事务的并发操作，数据库有不同的技术来控制，如下：

• OCC：乐观并发控制。允许多个事务并发读写操作，互相互不阻塞，而是记录操作历史，在事务commit阶段，检查冲突。如果冲突，则终止其中一个事务。
• MVCC：多版本并发控制。允许一条记录，可以存在多个时间戳的版本。通过这种方式，保证了事务读取到的是过去某个时刻的数据。
• PCC：悲观并发控制。不允许事务并发操作。

B树的变体

通常在应对，并发处理、写操作优化、节点间链接查询等等场景时，基础的B树无法满足需求，进而演变出了B树的各种变体

COW

有些数据库没有 构建复杂的锁机制，而是使用了 copy-on-write 技术，来保证并发操作情况下，数据的完整性。

COW树的核心：每当page即将被修改时候，会先copy它，在它的基础上修改，而不是直接修改原来的page。这样就创建出 一个与旧tree平行的新tree，他们之间共用了 未修改的 page。如下

COW树的优缺点：

• pros: reader和writer互不阻塞，因为reader读取的是旧page，writer操作的是copied新page。只有当写事务完成后，修改page才对外可见
• cons: 它需要更多的空间，去存储旧版本数据

Lazy B-Trees

惰性B树，降低更新B树的成本，它使用 轻量的，并发友好的 内存结构 来缓存延迟 传播更新。

简单来说就是，存在一个 更新缓冲区，减少对相同page写操作次数。如下 针对单个page的缓冲区，当然也存在针对 多个page组 的缓冲区，本质就是batch来减少写操作。

它的优点：B-Tree的page更新 和 结构调整(spill/rebalance)，通过缓冲区，可以实现由 后台进程执行。而读写进程 不必等待它们完成。提高了写操作性能。

FD-Trees

上面的Lazy B-Trees体现了数据库中重要思想：batch。它将许多次的随机写操作，替代成单次大的写操作。本质就是为了减轻B-Tree的负担：维护B-Tree需要大量的随机写入操作。

如果我们避免了随机写入操作，那这数据结构是什么样的呢？

FD-Trees就是为了解决大量小的随机写操作 设计出的，尽管它是解决flash disks上的随机性性能，但是仍然可以应用于SSD。参考Tree Indexing on Solid State Drives

总体来说，针对它的任何更新操作，都不需要定位到目标node，而是 只通过追加操作。

具体来说，FD-Trees由 一个小的、可变的head tree 和 多个不可变的有序段 构成。当随机I/O产生的时候，先去更新head tree，一旦它填满，它的内容会转移到 不可变的有序段 中，如果当前有序段 大小超过阈值，则将其内容和下一层 合并，从上到下逐层 传递数据。

FD树两个核心技术是：分段级联 + 对数级有序段

分段级联 fractional cascading 技术，有助于降低在级联排序数组中定位数据项的成本。本质就是，在相邻层数组之间建立bridge，来构建层之间的捷径。

构造它的方式：在低层数组中，每隔N-1个数据项，就将一个数据项拉到高层数组中。

如下图

对数级有序段

它是一组不可变的 排序数组，它的大小以系数K递增，并且它的创建 是通过merge上一层与当前层 而来的。

构造方式：

1. head tree填满时候，将它的叶子节点都写入第一层，即最高层的有序段
2. head tree再次填满，将它的内容与第一层有序段 merge，用来替换第一层有序段
3. 当较高层的 有序段达到阈值时，会创建低层的 有序段，同理如果已经存在低层 有序段，则进行merge操作

注意点：FD-Trees 不存在原地update pages，并且可能 一个key会存在 多个层的有序段中，所以当一个key被删除时，会通过插入一个Filter Entry来表明该key逻辑上已经被删除。并且该entry最终会merge到最低层，便可以丢弃。

具体参考paper中的3.2 Overview of FD-Tree章节。

Bw-Trees

B树已知存在的问题。参考理解amplification

• 写放大 write amplification
• 空间放大 space amplification
• 并发问题与latch锁 处理复杂度

为了同时解决上面三个问题，出现了一种无锁树，Buzzword Tree。参考CMU的OpenBw-Tree

本质通过 lock-free index来提供更高的并发吞吐。具体做法：仅通过append-only方式 更新树的node，并将更新的数据 与 原base数据 组织成链表，通过CAS来append链，从而达到无锁。

如下图中，逻辑上的一个node，它包含了Base，Base后面链接着更新部分。

总结

由于B-Tree存在一些缺点：写放大(Structure Modification Operation, SMO 引起) 和 空间放大(一个node不会完全填充满，为了将来写入保留空间)。

因此，针对这些缺点，演进出了一些变体

• 使用缓冲层 减少 写放大：Lazy B-Trees，将内存缓冲区 附加到 单个node或node组 上，减少了更新所需的I/O操作
• 使用不可变性 减少 空间放大：FD-Trees，将数据存储在不可变的有序段中。Bw-Trees，利用append-only base node也实现了不可变性