标题：重新思考高性能存储引擎中的日志、检查点、恢复。
ABSTRACT
背景
按近几十年的行业标准，ARIES是数据库日志和恢复系统的标准，其能提供一些重要支持，如：
- 任意负载；
- 模糊检查点；
- 透明索引恢复。
现代轻量级建立在SSD闪存上的存储引擎，性能接近于内存，但是还因为速度原因不支持ARIES，内存里写日志也不可能。
解决方案
本文提出了一个新的日志和恢复解决方案，能够支持：
- 递增地、模糊地检查点； => 保证有界的恢复时间
- 索引恢复；
- 外存负载；
- 低延迟事务提交。
在性能上： - 逐线程的日志提交和最小化的同步，使得在多核的扩展性上几乎是线性的。
- 对于内存负载，和内存相关方案性能接近（本文方案支持的功能更多）；
- 对于外存负载，对于支持ARIES的方案，性能提升2倍。
1 INTRODUCTION
- 基于磁盘的存储引擎：ARIES风格的WAL一直是设计标准，持久性和恢复也是关键特征，但是恢复的设计实现会影响DB的整体性能。据研究显示，Shore存储引擎50%的时间都花在了buffer管理和日志上。而且可扩展性差，难以利用多核，尤其是中心化的日志组件。
- 基于内存的存储引擎：一般不全部实现ARIES，只实现一个轻量级的日志；在内存中存储数据，不需要buffer管理；实现更加简单高效。但是恢复做的不好，一般对于数据量大于内存的就没法恢复了。
- 基于SSD的存储引擎：随机读写快，提供块级别访问，已经有大量优化专门针对SSD，例如pointer swizzling, scalable optimistic synchronization等，LeanStore就实现了这些优化，同时还提供透明的buffer管理。
- 基于NVM的存储引擎：介质太贵，但是写入快，一般只用于WAL。
- 本文方案：主要做日志和恢复，可以在高性能存储引擎中使用，基于一个NVM logging schema扩展而来，补充了：
- 一个连续检查点算法；
- 页预取策略；
- cross-log 提交协议。
并把这些都实现在了LeanStore上。具有如下优良性能： - CPU负载低；
- 可多核扩展；
- 平衡了I/O负载和恢复时间；
- 利用了现代硬件：NVM用于低延迟提交；SSD用于数据量大于内存时的恢复。
2 BACKGROUND
2.1 ARIES
ARIES是日志和恢复的标准。ARIES一个基础就是“物理和逻辑结合的日志记录”。按照页面级别进行日志记录（每条日志附带一个page id），但是也支持页面内的修改。
- 页面级别的日志记录允许以页面为级别并行恢复；
- 对页面内修改的日志记录允许即使是未提交的页面修改，也可以先写入磁盘页（就地更新），因为崩溃时根据WAL做undo就可以撤销修改；
这个基础带来两点好处：
- 允许模糊检查点；
- 有能力用日志记录和恢复所有以页为基础的数据结构：索引可以直接恢复，无需逐步执行恢复。
2.2 In-memory Database Systems
内存数据库中，value-logging的方案和本文设计相似。
value log不包含page id，只包含：
- 逻辑tuple id
- 单调递增的事务id
- 修改过的tuple内容。
value-logging使得指向同一页的不同log之间没有依赖了，在“物理与逻辑结合的日志”中，这是一个额外的同步过程。
之前提到，中心化的日志记录过程是一个瓶颈。value-logging的方案是分布式logging，每个transaction被分配到一个log buffer，多核就有多个log buffer，每个log buffer都有自己的log file，互相之间不需要同步。持久性基于一个群体提交协议和一个epoch的概念。恢复时，会找到所有log files里最大的epoch，然后各个log file并行恢复即可。
缺点在于：
- 不支持索引恢复；
- 要求数据集常驻内存；
- 缺少递增的checkpoint。
2.3 Checkpoints
目前缺少一个高性能的脏页驱逐方案。
2.4 Scalable Logging
从集中式log到分布式log可以提升scalability，但至少有两点问题：
- 不同的log之间有因果依赖，commit一个log，要把其依赖的log先flush；
- 没有统一递增的LSN。
对于因果依赖的问题，可以基于Lamport时间戳的思路解决，把事务和页都看作分布式系统的进程，日志记录看做是需要定序的事件（分配GSN）。
对于持久性问题，一个事务提交，首先在本log buffer进行提交，然后等待一个群组提交队列，让其它log buffer把GSN更小的log都提交，队列里的提交完之后，这个事务算提交完成。
这也是本文算法的基础之一。
3 LOW-LATENCY LOGGING AND ROBUST CHECKPOINTING WITH BOUNDED RECOVERY
3.1 Two-Stage Distributed Logging
多线程的logging worker，每个worker负责一部分事务日志。不同的事务可以对同一页进行操作，即同一页的不同事务，可能会在不同worker手上，因此在不同日志中。日志分成三阶段：
- 第一阶段在NVM里，log被批量组织成chunk，有一个环形链表，分成三个区域，current chunk负责接收写进来的日志(append)，写满了进full chunk，full chunk会被WAL writer线程写入SSD，写完了的chunk进入到free chunks，free chunks会被挑选称为current chunk。
- 第二阶段在SSD里，由WAL writer线程写入；
-
第三阶段在HDD里，对所有logging worker的日志进行归档。归档意味着数据已经持久化，这些日志甚至可以删除了。
image.png
性能分析：NVM写入特别快，因此事务提交特别迅速，就跟写内存一样。不需要group commit。SSD带宽足够应对当今最快的事务系统。
- 备选方案：把第一阶段直接放进内存里，持久性通过把log chunk刷入SSD来完成。基于RFA的群组提交，会使得速度也很快。
3.2 Low-Latency Commit Through RFA
上一节我们讲到的是刷log的一个物理过程，这节讲更上层的，决定哪些log要被刷，能否延迟被刷，针对的是单个事务的提交peak时延不会过长。
因为用到的是分布式logging技术，所以必须要用到GSN来追踪一些log依赖。而由于log之间这些依赖，分布式logging技术中的群组提交(group commit)会严重削弱scalability。还有一个乐观群组提交的方案，事务只刷自己的日志，然后放到队列里去，一个群组提交线程会在队里选一个最小的GSN，让以这个GSN为最后日志的事务可以进行提交。然而延迟仍然较高。
接下来介绍RFA。RFA的Observation是GSN的设计虽然充分，但是有些过度，有些没什么关系的log也会被GSN赋予前后关系，而事实上并没有数据依赖。换句话说，Lamport时间戳实际上是一个偏序关系，很多事件(log record)是无法比较先后关系的（并行的），而GSN做成了全序的，强行赋予了一些先后关系，RFA的设计就是要去除这些不必要的先后关系，减少群组提交的次数。
具体来说，RFA补充了三个信息：
- 对于每个页，记录
，指向最近修改该页的日志文件，注意到每个log worker写入一个日志文件，每个transation被分配给一个worker，因此一个日志文件同时只能被一个transaction提交。
- 当一个事务开始的时候，要确定
，使得在
- 每个事务都有一个
标记，初始化为False。
执行时，每当一个事务访问一个页，会看这个页的GSN是否小于，是的话，就可以正常执行，因为之前的修改已经刷到了磁盘。
否则的话，查看是否是当前事务提交的日志文件，是的话也可以继续执行，因为最近一次修改是当前事务。
这二者都不满足的话，就标记为True，执行群组提交。
RFA和群组提交是正交的，可以单独用也可以组合用。
3.3 Challenges of Checkpointing
现代内存数据库做checkpoint基本接近copy全量数据集然后持久化，空间占用大，对前台影响也大，速度很慢，恢复时间也慢。
本文采用的方案是基于页的checkpoint。基于页的方案有一个重要的trade-off，就是checkpoint的频率问题：
- checkpoint太快，I/O负载太高，写放大比例也高；
- checkpoint太慢，log size太大，空间上不好控制；脏页太多，内存紧张；
除了这个trade-off，checkpoint时脏页的选择也很tricky，比如对于一些hot page，不应该首先被flush；类似的规则应该还有很多。
近来的研究没有对页级别的checkpoint深入下去，主要的研究力都在record粒度上了。
一个好的例子还是PostgresSQL，写脏页由两个进程来完成，一个checkpointer，一个background writer。checkpointer定时或者log满的时候会被触发，将内存池的所有脏页刷下去(direct checkpoint)。
为了不至于peak memory usage太高，background writer会按配置信息定时刷一些脏页以均衡I/O。这个实际上没法自适应地检测负载，把问题推给DBA来解决了。
3.4 Continuous Checkpointing
checkpoint机制的目的是为了限制恢复时间，限制WAL大小，那么会很自然地联系到把checkpoint策略和WAL中写入日志的数量联系起来。
举个例子，假如我们想限制WAL<=20GB，那么在WAL超过20GB之后，我们会扫描一次buffer pool，把最老的那部分日志对应的脏页写回，checkpoint向前推进，工作结束。
问题在于，我们不想每次扫描偌大的一个buffer pool，就为了写回少量脏页和几MB日志。为了解决这个问题，作者提出了连续检查点的方案。
算法将buffer pool逻辑上分成S份，每次需要checkpoint了(称为checkpoint increment)，就以round rubin的方式选择一份，写回其中的所有脏页，然后尽可能前移checkpoint。什么时候触发checkpoint increment呢？WAL大小到达限制大小的1/S了，就执行一次。
算法如下图：
image.png
我们为buffer pool按S个shard建一张表，每个shard有一个entry表示1个GSN，每个GSN代表在该shard内部，<=GSN的log record已经全部被持久化。那么精确的checkpoint就是整张表中最小的entry值了。
每次checkpoint increment时，我们询问log producer：“现在GSN到多少了？”，因为线程触发启动有一定时延，所以会比触发increment的那条log record的GSN略大一些。然后这个GSN就作为表中本次刷脏页shard的GSN。shard选择是Round rubin的。
每一次incremen都可能导致整张表最小的entry值增加，所以每次都算一下这个
下图是个例子：
image.png
性能分析：连续检查点在过快和过慢的时间频率上做了折中，按照日志量，均匀的进行脏页刷写，使得性能更加平稳。然而shards数量仍然是个参数，shards较大checkpoint increment频率更高，性能更加平稳，但是I/O代价也会更高，仍需谨慎选择。
3.5 Page Provisioning
除了checkpoint以外，写脏页还有可能发生在页面替换时，被驱逐的页正好是脏页，则要进行写回。本节我们讲本文的，也是LeanStore的buffer pool策略。核心架构如下图：
image.png
buffer pool分成三个区：
- 热区：可以直接由指针来进行访问，swizzlzing，保存最近访问的页，通过worker thread访问磁盘页面/冷区页面，或者新写一个页面向热区调入页面；
- 冷区：由一个FIFO队列构成，由哈希表实现，需要由page id查表访问；
- 空闲区：空闲页面无内容，需要页面替换时，首先从空闲区挑选空闲页面作为替换对象。
为了保证吞吐量，我们不让执行事务的worker线程做其它事情，这主要是由空闲区来保证的，当Worker需要空闲页面槽位时，直接从空闲区去取即可，无需考虑任何替换驱逐策略。
buffer pool的管理仍然需要一个page provider线程来执行，它们主要做三件事：
- 从热区unswizzle到冷区FIFO队列队尾；
- 驱逐冷区队首到空闲区；
- 对于被驱逐的脏页，则要首先写回磁盘，才能进入空闲区。
一般的脏页写回线程(比如PostgresSQL)，只会关注第三点。
而LeanStore page provider工作就相当忙碌了，负责整个buffer pool的scala均衡，当发生偏斜时，worker thread就会把它唤醒，重新做均衡。
均衡会做很多轮，直到冷区和空闲区大小达到标准。每一轮，page provider会从热区unswizzle固定数量的页面到冷区队尾(1)，然后将冷区队首的页面出队，分成两部分，一部分是干净页面，进入干净缓存区，待缓冲区满，则转入空闲区（2）；另一部分是脏页，被标记为“写回”，被放入写回缓冲区。写回缓冲区的页面仍然可以访问、修改，也可以被swizzle回热区。待缓冲区满，统一写回磁盘。写回之后，这些页面里的干净页面会被放入空闲区，此时又被写成脏页的又被转回热区。
BTW，作者这里解释了为什么只用一个线程，而不是三个线程做三种事，主要是三件事密切相关，互相依赖，多线程反而可能导致不均衡。
3.6 Transaction Abort
这里讲到的是steal策略。一般来说，作为RDBMS中的写提交时，首先写WAL buffer，然后读取页面，内存里写成脏页，事务提交时将WAL buffer持久化，之后某个时刻再将数据写回。然而像LeanStore和前面几节讲到的连续检查点机制，写回脏页，根本没有考虑到事务是否已经提交，意味着很多没提交的事务的脏页也被写回了，这就称之为steal策略。
但是事务如果没提交，反而abort了怎么办呢？那就在写操作之前除了log再写一个undo log即可，abort时反向执行该事务的undo log，即可复原状态。
这就是本文算法采取的策略。
写，无非是插入、修改、删除，对于这三种情况，undo log分别是如下信息：
- 插入：无需undo log，信息都在命令语句里；
- 删除：记录原数据，但是不常见；
- 修改：记录原数据和新数据的修改属性即可。
性能分析：由于正在执行的事务的日志通常都在NVM里，而且同一事务都在一个日志文件里，所以执行会非常快。
方案对比：steal策略可以执行大事务（超过内存大小），而且对于checkpoint, page provider都不必考虑事务是否写入的问题；普通策略则不必写undo log，空间更节省（不过作者实验分析只有20%左右大小的undo log）。
3.7 Recovery
恢复通常和buffer pool size的比例挂钩，如果buffer pool size很大，那么恢复的时间也不可小觑。和ARIES类似，有三个阶段，日志分析，redo和undo。如下图展示前两个阶段，整个过程可以并行完成。
image.png
- 第一阶段：每个log partition读取在SSD和NVM中的日志文件，分成redo和undo两个区，每个区维护一个哈希表，key为page id，value为具体的log。
- 第二阶段：每个线程被分配一个page id的range，从前一阶段的Redo区取相应的log，按照page归档日志，最后逐页去执行，写成脏页。这个过程当然也包含那些abort的事务的redo log。（编者注：对于那些已经持久化过的log，应该要么记录了前后变化来判断是否已经持久化，要么直接有一个flag标识是否已经持久化）。
- 第三阶段：类似第二阶段，去反向执行undo log。
4 EVALUATION
系统没有完全实现事务隔离性，系统仅基于read uncommited来实验。
单机24核48线程，192GB内存，768GB NVM，基于LeanStore来实现。
实验的目的就是测试不同的logging和checkpointing技术在高性能存储引擎上的表现，为保证单一变量，所有实验对象都被单独在LeanStore上实现了一次（编者：瑞思拜）。
ARIES, Aether是集中式的日志系统，
SiloR是纯内存的。
4.1 Scalability
扩展性在24核前基本呈亚线性，在24核后就不太行了。但是SiloR扩展性一直很强。作者追踪其原因，发现是NVM多线程写导致的过饱和。
RFA总归还是难以避免远程flush的，因此比完全乐观的group commit稍差一些。
image.png
下面表格，比较了在不同个数的Warehouse下，远程flush率，可以看到，事务越独立，远程flush越少。
image.png
4.2 Log Volume and Checkpointing
- a表示由于continuous Checkpoint技术，本文算法的日志总量是稳定的。而SiloR就不是了。
- c曲线表示SoliR会在checkpoint突发写入全部数据，而本文算法较均衡。
- d曲线表示SoliR数据集大小一旦超过内存，无法继续支持服务；而相反，e表示本文系统的page provider进程启动，开始置换页；f表示前台服务没有受到可见影响。
-
h曲线表示在基于磁盘的日志系统里，本文的设计比吞吐量STOA好2倍。
image.png
4.3 Dissecting the Features
通过逐步加功能，看看吞吐量减少了多少，要执行的指令增加了多少（复杂度）。
image.png
4.4 RFA and Contention
在不同数据倾斜程度下的吞吐量和Remote flush比例。
image.png
4.5 Transaction Latencies
平均事务提交时延比较。
image.png
4.7 System Comparison
最后是和WiredTiger(MongoDB存储引擎)进行对比，是否有checkpoint/logging对WiredTiger影响还是比较大，但是对我们系统的设计影响就比较平滑。由于WiredTiger是单核，教科书式的ARIES实现，所以吞吐量较低。
image.png
网友评论