Aurora架构

aurora是一个shared storage的架构，的整体结构如下

所有的写入都通过一个Primary 进行，Primary生成redo log后发送到下面的storage层，storage层将日志回放为数据，primary和replica都共享存储层的数据。

像其他很多数据库一样，aurora将数据进行了切分，每个分片称之为一个segment，有6个副本。

6副本中，4写，3读，跨越3个AZ，每个AZ放两个副本。原因是aurora认为可能一个AZ的机房可能出问题（网络，停电等），而同时随着数据的增多，同一时刻某个分片的数据出问题的概率也不小。为了在这种情况下保证不丢数据，至少要剩下3个副本可读以保证可以重建和恢复。如上图所示，当AZ3整体不可用的时候，AZ1中的一个副本也出现了问题，这个时候由于还剩下3个副本，我们能保证至少有一个副本有最新的数据，可以在AZ1中重建新副本，保证数据安全和实例可用。因此aurora支持“AZ + 1”的容错能力。

写链路与崩溃恢复

整体流程

在storage层面的写入流程如论文中的图所示

1. 从primary发送redo log到storage的INCOMMING QUEUE（内存中）
2. 将接收到的redo log写进UPDATE QUEUE，并且回复计算层（UPDATE QUEUE是持久化的）
3. 将受到的redo log进行排序（redo log是异步发送的，可能存在空洞，后面会讨论）
4. 通过gossip协议从其他副本获取缺少的log
5. 将redo log回放为数据block
6. 周期性的进行备份（日志和数据）
7. GC，淘汰老数据
8. 周期性的进行数据校验

名词

下面介绍相关的一些名词，后文将会用到：

Log Sequence Number（LSN): 全局单调递增的序列号，与正常innodb的redo log的lsn类似，在aurora中由primary instance生成。全局单调递增的LSN是aurora能不使用共识算法的关键点。

Protection group： 上面已经提到日志和数据被分片为一个一个的segment，每个segment有6个副本，被称为一个Protection group。

Storage volume: 许多的Protection group组织在一起被称为一个storage volume，storage volume与实例对应。

Segment Complete LSN（SCL）: segment中连续log的上界，在这个lsn以及之前的属于本segment的log都已经收到了。SCL在存储层由每个segment维护。

Protection Group Complete LSN (PGCL): 在整个protection group的6副本中，这个位点表示在这个位点以及之前的log都已经在至少4个副本中持久化。PGCL在计算层维护。

Volume Complete LSN (VCL) ：在整个实例层面，横跨多个protection group，在它之前的所有log都已经完成持久化。

Volume Durable LSN (VDL): 在VCL之下最近的mini transaction的最后一个log的lsn，表示最后一个完整mtr。

如上图中，共有两个Protection Gruop(PG1与PG2)，分别有6个副本（A1-F1, A2-F2）。奇数lsn的log的log属于PG1，偶数lsn的log属于PG2。其中PG1的SCL是103，因为105没有写入4个副本。PG2的SCL是104，因为106没有写入4个人副本。如果整个系统只有这两个PG，则VCL是104。

异步写与乱序发送

aurora的redo log都由primary生成并发送到storage。redo log在primary内存中的log buffer中被按lsn顺序写入，并且需要被持久化。由于需要通过网络进行发送到stoage，并且要写入4个副本，aurora采用了异步与乱序的方式向storage层发送redo log。

1. master并不强求上一个redo log record写成功，才发下一个redo log record，即可以乱序
2. 如果某个redo log record暂时没有收集到4个response，就重试重发，因为假设整个存储层是永久有效的，所以，针对这个redo log record的write也是最终能保证收集至少4个response。
3. 当某个redo log record收集了4个response，master可以不再给剩下的2个Storage node发write请求，因为系统允许至多两个Storage node失败
4. 当之前的所有的redo log record都收集了至少4个response，当前这个redo log record也收集了至少4个response（即必要和前提条件），master才认为当前这个redo log record写成功（success of quorum write），即还必须有之前的redo log record连续写成功的约束。

假设有如下几个lsn的log

1, 5, 7, 9

上面日志项分别来自不同的事务，这几个log record可以分别异步的发送，后续的log record无需等待前面的log获得回复。与逐个发送的方式相比，流量会更大，与常用的batch攒批优化相比，延时会更低。如果其中一个log record（例如5）是一个事务的commit log，则当primary的VCL推进超过5之后，才能回复客户端事务完成提交。在论文中提到工作线程写完commit log到master的buffer中后并不会阻塞一直等待到可以提交为止，而是将事务和客户端相关信息放进一个commit queue中，等到VCL被推进到足够远后，将会唤醒专门的通知线程去回复客户端（和业界常见优化MySQL复制的思路类似）。

空洞处理

由于primary写redo log到storage层的时候是直接向各个segment副本写，并且收到4个response就认为写成功，那么显然部分segment的log可能存在空洞。如果LSN是严格按1连续递增则很容易判断空洞，但是事实上LSN只能保证递增但并不连续（实际上在innodb中是是log record在redo log中的偏移量的字节数）因此，Aurora维护了两个链表：每一个log record中有两个指针，分别指向在redo log中的前一条日志，和修改同一个block的前一条日志。

如上图所示：有4条日志，其lsn分别为1, 9, 14, 20

这四个log是连续的，因此表示整个redo log的链表为

1<-9<-14<-20

lsn 1与lsn 14修改block1

1<-14

lsn 9 与 lsn20修改block2

9<-20

因此，segment能很容易的识别出空洞，空洞的日志通过gossip协议从其他节点获取。

崩溃恢复

传统数据库一般使用ARIES来做恢复，依赖WAL来恢复已提交的事务。数据库系统周期性地进行checkpoint，本质上也是为了缩短恢复时间，恢复时通过应用checkpoint之后的日志来恢复到宕机前的一致的状态，以mysql来讲，其实是需要通过应用redo恢复出buffer pool中未来得及刷脏的脏页，并且通过执行undo回滚相应的事务。因此刷脏、checkpoint、恢复、写这些息息相关，刷脏太频繁会影响写性能，太慢会影响恢复时间，而Aurora的设计解耦了前台写入与redo的处理，就不需要这些权衡。

同样地，在恢复时，redo apply依然与计算节点是解耦的，数据库可以非常快地启动，同时日志应用在存储节点上后台执行，不需要在recovery时同步处理，甚至可以是在处理读请求时再对相应的page进行log apply。

本质上，aurora通过再数据库中维护一致性位点来达到读写的一致性的，而不是通过多个storage node构建分布式一致性。因此Aurora也需要构建宕机前的运行时状态，需要与每个PG建立联系，重建每个PG的read quorum，然后通过本地segment的SCL重新计算出PGCL、VCL。如下图所示，实例crash之前尾部的log是存在空洞的，也就是部分log还未达成write quorum，在恢复时计算出VCL后，VCL后面再加一部分的log就会被truncate，即便在恢复过程中它们互相又补齐了也不再有效，新的redo的LSN将从truncate位置开始继续分配。

如果aurora无法重建write quorum，会使用read quorum来重建故障的segment，这样就会导致PG的状态可能有变化，因此增加了epoch的方式来区分PG的版本，每个读/写请求会携带epoch信息，storage node会拒绝过期的epoch请求，这样也就避免了旧的连接在存储节点经历了crash recovery之后还继续访问该节点(可能已经读不到之前可以读到数据)。

整个恢复过程不需要回放redo，之前未提交需要回滚的事务依然是通过undo进行操作，不过也是可以等数据库提供服务以后与用户请求并行处理。

读链路

避免quorum read

进行一次读操作的时候，不管是primary还是replica，如果page不在buffer pool中，都需要从storage层去读取。根据aurora的quorum协议，一次读取需要至少读3个副本，但是如果每次都读3个副本会造成大量的开销，并且延时实际上是这3个副本中最大的那个。因为Computing node可以知道每个Storage node的完成情况，比如：是哪4台Storage node，保证完成VCL，它可以选择有此完备（complete）数据的其中的一台去读即可，而且可以做到基本选择最快的那台Storage node去读。

避免stale read

在master上进行读取的时候，需要处理stale read的情况。例如我们有一个page，上面记录最近修改它的lsn是107。由于buffer pool满了我们将这个page淘汰掉，由于aurora没有刷脏的流程，所以这个page将被丢弃掉。随后，我们又需要读取这个page，但是由于aurora的redo log是异步发送的，存储层可能还没有收到lsn为107的log，对应的page在存储层无法找到，直接读取这个page将读到一个老版本的page。因此aurora有一个约束：只有page中记录修改这个page的lsn < VDL的page才能够被淘汰。原文中的描述为“greater”，应该是笔误。

副本读

复制通道

aurora支持添加读副本，replical与primary共享同一份数据，因此添加副本的开销很小。replica与primary一样有自己的buffer pool，如果需要读取本地buffer pool中没有的page则需要从存储层进行读取。同时primary还会向replica发送redo log过来，收到redo log后replica只apply那些对应page在自己的buffer pool的log，对于没有在buffer pool中的page的log，可以直接丢弃掉。因为当需要这些log的时候直接从存储层读取就行了。

innodb将B+ tree的变更封城一个个mini transaction对应SMO操作，mini transaction必须被原子的执行，而不能执行一半。因此primary传输给replica的redo log是以mini transaction为单位，不允许只传输一半、执行一半。在replica上也必须整个mini transaction执行。

ReadView

数据库在进行读的时候需要一个快照去读某个时刻的数据，当从relical进行读的时候同样也需要。与通常数据库通过水位和活跃事务列表来构建快照类似，aurora通过VDL（replica中的VDL）和活跃事务列表来构建replical上的Read View。论文中称复制通道将会发送VDL和活跃事务列表给replica，尽管redo log中包含足够的信息去构建活跃事务列表，但是出于效率考虑选择直接发送活跃事务列表。

MVCC

由于replica的VDL很可能是落后primary的，因此当在replical进行读取的时候实际上要看到的是过去某个时间点的一个一致性视图（论文中没提，但是按理在master上之前就开启的一些事务的快照也应该是同样的道理），那么实际上需要读到的是历史上的版本，读某个page的时候page可能在buffer pool中，也可能在storage层。如果在buffer pool中，那可以通过page和对应undo log来找到对这个ReadView可见的数据。但是replica的VDL可能落后于primary，例如下面这样的情况

replica想要去stoage读取page2，但是由于replical的VDL太老，storage层的page2对于这个ReadView实际上是未来的数据，它想要读取的是过去某个时间点的page2。因此aurora的存储层实际上实现了page的MVCC，在逻辑上来讲存在多个版本的page2，replical在读取的时候带着自己ReadView的VDL，去读取对应版本的page。对于多版本page的GC，aurora维护了一个PGMPL（Protection Group Minimum Read Point），它代表整个实例级别所有活跃事务可能访问的最小lsn，page的lsn小于这个PGMPL就可以进行回收。

成员变更

为了处理成员变更，aurora引入了两个概念：quorum sets 和 epoch。quorum sets表示一组副本，每次副本中有成员发生变更就增加epoch。读取请求必须带有epoch，副本集只接受匹配的epoch的读取请求，如果是更老的epoch的请求，被拒绝后需要更新成员信息。

如上图所示，假设一个quorum set是由A,B,C,D,E,F 6个副本组成，epoch = 1。此时F出现了故障，系统用G来替代它。成员变更的步骤分为两步：

第一步：将写入集合变为 (ABCDEF) AND (ABCDEG)，也就是说任何一次写入都必须在ABCDEF 和 ABCDEG中都写入 4/6。读取集合变更为(ABCDEF) OR (ABCDEG)，也就是说在ABCDEF和ABCDEG两个集合中任意一个中读取到3个副本的值，这样可以确保读和写一定会有overlap，一定能读到最新的写入。成员变更本身同样也是一次写入，也要在涉及的集合达到多数派。完成变更后epoch修改为epoch2。

第二步：如果过了一定时间，F依然处于down的状态。则我们可以通过再一次变更将集合变更为ABCDEG，写其中4/6，读其中3/6。epoch也被变更为epoch3。反之，如果F恢复了，我们可以将集合再变成ABCDEF。

考虑一种更复杂的情况，我们正在将F替换为G的过程中，也就是上图epoch为2的时候，E又出现了故障。那么写入集合将变更为 ((ABCDEF) AND (ABCDEG)) AND ((ABCDFH) AND (ABCDGH)) （也就是将故障的两个与其他4个进行组合），读集合则是前面4个子集中的一个。

一些疑问与思考

aurora的两篇论文中介绍了aurora的整体架构，但是系统的很多细节并没有介绍。读完后有一些疑问，这里列出一些

segment是依照什么规则划分的？

作为aurora的核心，存储层只介绍了大概，没有说明是怎么实现的。例如，segment是依照什么规则划分的？从文章中来看有可能是按照某种规则hash，每个segment负责一部分的page和对应的redo log？

segment的元数据和路由信息怎么管理？

是否存在一个第三方的类似kv存储的系统负责管理？如果存在的话是不是多个aurora实例共用的？如果共用的怎么做多租户资源隔离？如果不在的话用什么方式管理元数据和路由信息？最基本的问题是client怎么知道某个page在哪个Protection Group，Protection Group的副本集是哪些segment。

segment是否会分裂？

文章中提到segment大小为10G，10G是指的哪些数据的大小，redo log + page吗？如果数据量增加segment是不是会分裂，过程是怎样的

undo log怎么管理

文章中提到只有redo会发送到storage层，undo应该是在本地。那么undo log具体怎么管理，replica的undo log看起来应该是直接从传过来的redo log中回放出来的。文章中缺少更多关于undo的细节。

storage中的page的多版本具体怎么实现的

常见的方式可能有两种，一种是简单的把各个版本的page都回放出来，然后在用链表串在一起，也可能是用一个base的page加一个链表串上各个版本的delta记录，可以在读的时候merge成其他版本。

主从之间是否可以failover？

主备之间是否可以切换，如果切换的话怎么处理undo log？因为replica的undo log可能是滞后与primary的。

······