2020SIGMOD-Rethinking Logging, C

2021-05-08  本文已影响0人  Caucher

标题：重新思考高性能存储引擎中的日志、检查点、恢复。

ABSTRACT

背景

按近几十年的行业标准，ARIES是数据库日志和恢复系统的标准，其能提供一些重要支持，如：

现代轻量级建立在SSD闪存上的存储引擎，性能接近于内存，但是还因为速度原因不支持ARIES，内存里写日志也不可能。

解决方案

本文提出了一个新的日志和恢复解决方案，能够支持：

1 INTRODUCTION

2 BACKGROUND

2.1 ARIES

ARIES是日志和恢复的标准。ARIES一个基础就是“物理和逻辑结合的日志记录”。按照页面级别进行日志记录（每条日志附带一个page id），但是也支持页面内的修改。

这个基础带来两点好处：

  1. 允许模糊检查点；
  2. 有能力用日志记录和恢复所有以页为基础的数据结构：索引可以直接恢复，无需逐步执行恢复。

2.2 In-memory Database Systems

内存数据库中，value-logging的方案和本文设计相似。
value log不包含page id，只包含：

  1. 逻辑tuple id
  2. 单调递增的事务id
  3. 修改过的tuple内容。

value-logging使得指向同一页的不同log之间没有依赖了，在“物理与逻辑结合的日志”中，这是一个额外的同步过程。
之前提到，中心化的日志记录过程是一个瓶颈。value-logging的方案是分布式logging，每个transaction被分配到一个log buffer，多核就有多个log buffer，每个log buffer都有自己的log file，互相之间不需要同步。持久性基于一个群体提交协议和一个epoch的概念。恢复时，会找到所有log files里最大的epoch，然后各个log file并行恢复即可。
缺点在于：

  1. 不支持索引恢复；
  2. 要求数据集常驻内存；
  3. 缺少递增的checkpoint。

2.3 Checkpoints

目前缺少一个高性能的脏页驱逐方案。

2.4 Scalable Logging

从集中式log到分布式log可以提升scalability，但至少有两点问题：

  1. 不同的log之间有因果依赖，commit一个log，要把其依赖的log先flush；
  2. 没有统一递增的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手上，因此在不同日志中。日志分成三阶段：

  1. 第一阶段在NVM里，log被批量组织成chunk，有一个环形链表，分成三个区域，current chunk负责接收写进来的日志(append)，写满了进full chunk，full chunk会被WAL writer线程写入SSD，写完了的chunk进入到free chunks，free chunks会被挑选称为current chunk。
  2. 第二阶段在SSD里，由WAL writer线程写入；

  3. 第三阶段在HDD里，对所有logging worker的日志进行归档。归档意味着数据已经持久化，这些日志甚至可以删除了。


    image.png

    性能分析：NVM写入特别快，因此事务提交特别迅速，就跟写内存一样。不需要group commit。SSD带宽足够应对当今最快的事务系统。

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补充了三个信息：

执行时，每当一个事务访问一个页，会看这个页的GSN是否小于GSN_{flushed}，是的话，就可以正常执行，因为之前的修改已经刷到了磁盘。
否则的话，查看L_{last}是否是当前事务提交的日志文件，是的话也可以继续执行，因为最近一次修改是当前事务。
这二者都不满足的话，就标记needsRemoteFlush为True，执行群组提交。
RFA和群组提交是正交的，可以单独用也可以组合用。

3.3 Challenges of Checkpointing

现代内存数据库做checkpoint基本接近copy全量数据集然后持久化，空间占用大，对前台影响也大，速度很慢，恢复时间也慢。
本文采用的方案是基于页的checkpoint。基于页的方案有一个重要的trade-off，就是checkpoint的频率问题：

除了这个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值增加，所以每次都算一下这个GSN_{min}，然后在看下当前活跃的事务，最小的GSN是多少，和GSN_{min}取较小值，这个值就是一个精确checkpoint，这个checkpoint以前的日志就可以archive去了。
下图是个例子：
image.png
性能分析：连续检查点在过快和过慢的时间频率上做了折中，按照日志量，均匀的进行脏页刷写，使得性能更加平稳。然而shards数量仍然是个参数，shards较大checkpoint increment频率更高，性能更加平稳，但是I/O代价也会更高，仍需谨慎选择。

3.5 Page Provisioning

除了checkpoint以外，写脏页还有可能发生在页面替换时，被驱逐的页正好是脏页，则要进行写回。本节我们讲本文的，也是LeanStore的buffer pool策略。核心架构如下图：


image.png

buffer pool分成三个区：

为了保证吞吐量，我们不让执行事务的worker线程做其它事情，这主要是由空闲区来保证的，当Worker需要空闲页面槽位时，直接从空闲区去取即可，无需考虑任何替换驱逐策略。
buffer pool的管理仍然需要一个page provider线程来执行，它们主要做三件事：

  1. 从热区unswizzle到冷区FIFO队列队尾；
  2. 驱逐冷区队首到空闲区；
  3. 对于被驱逐的脏页，则要首先写回磁盘，才能进入空闲区。

一般的脏页写回线程(比如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分别是如下信息：

  1. 插入：无需undo log，信息都在命令语句里；
  2. 删除：记录原数据，但是不常见；
  3. 修改：记录原数据和新数据的修改属性即可。

性能分析：由于正在执行的事务的日志通常都在NVM里，而且同一事务都在一个日志文件里，所以执行会非常快。
方案对比：steal策略可以执行大事务（超过内存大小），而且对于checkpoint, page provider都不必考虑事务是否写入的问题；普通策略则不必写undo log，空间更节省（不过作者实验分析只有20%左右大小的undo log）。

3.7 Recovery

恢复通常和buffer pool size的比例挂钩，如果buffer pool size很大，那么恢复的时间也不可小觑。和ARIES类似，有三个阶段，日志分析，redo和undo。如下图展示前两个阶段，整个过程可以并行完成。


image.png

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

  1. a表示由于continuous Checkpoint技术，本文算法的日志总量是稳定的。而SiloR就不是了。
  2. c曲线表示SoliR会在checkpoint突发写入全部数据，而本文算法较均衡。
  3. d曲线表示SoliR数据集大小一旦超过内存，无法继续支持服务；而相反，e表示本文系统的page provider进程启动，开始置换页；f表示前台服务没有受到可见影响。

  4. 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
上一篇下一篇

猜你喜欢

热点阅读