浅析Aurora Quorum
Aurora在SIGMOD18'的论文《Amazon Aurora: On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes》中描述了Aurora关于共识方案的选择和Quorum方案的详细内容，本文这里做一些简单的分析。
Aurora架构背景
在描述Aurora的Quorum方案前，先介绍下Aurora的系统架构。
Aurora是share-storage、一写多读的架构，构建在MySQL(InnoDB)代码库上，当然后来增加了multi-master多写能力。
数据库被解耦成两层：DB层跟单机MySQL差不多，负责了查询处理、事务、锁、BufferPool、undo管理几大块功能；存储层是一个可扩展的针对MySQL定制的存储服务，负责redo logging、页面持久化、垃圾回收、备份恢复等。
存储层为了扩展性和快速恢复，将数据分为若干10GB的单元，叫segment。Segment里面包含若干page，同时也存储了跟这些page关联的redo records (redo log)，page和redo log二者是一体的，因为record可以apply到page上。这些segment分散到多个存储节点上，为了支持AZ+1的高可用，每个Segment存到3AZ共6副本，这6个副本合称为一个PG（Protection Group），Aurora使用改进的读3写4的Quorum协议实现多副本一致性。
MySQL事务执行过程中，会产生wal，即innodb redo record，只有这些wal完成存储层持久化，才能响应客户端提交成功。DB层一个事务产生若干条redo record，这些record可能会被分发到各自对应的segment。Segment收到之后，完成本地持久化，回应DB层，DB层维护bookkeeping来追踪各个副本持久化的位点推进，后台异步检查连续性（需要维护segment粒度和page粒度的LSN链/子序列），链中遗漏的靠gossip找其他副本补，视情况将redo record到segment的page上。
Aurora Quorum
Focus到quorum上，Aurora Quorum实际上不是简单的quorum系统。
我们可以对比一下Dynamo的quorum方案。Dynamo是Amazon开发的分布式KV存储，也是一个影响很大的系统。Dynamo使用的也是NWR Quorum协议，要求W+R>N。写操作只要N个副本中W个返回成功即可，如果出现数据变更历史分叉，要读操作负责做数据版本的仲裁。举个数据版本仲裁的例子：某客户购物车里面一开始是空，从浏览器页面点击加入商品1，购物车从 '{}' 变为 '{商品1}' ，然后从另一页面点击加入商品2，购物车从 '{}' 变为 '{商品2}'。下单时，购物车业务逻辑合并两个数据版本，认为购物车是 '{商品1、商品2}'，注意到这里是靠用户业务层逻辑解决弱一致异常。
Aurora Quorum引入了epoch。Segment上有epoch值（实际上epoch是Aurora实例粒度的，假设只有一个PG），读写请求上也带上epoch值，Segment会拒绝掉stale epoch的读写请求。在writer recovery（正常重启或异常失效）时，新的writer会先明确当前已经确认的那些写入，再使用新的epoch提供读写服务。
读者可能已经发现了，Aurora Quorum实际上跟Paxos（广义Paxos协议族）本质上是一样的。尤其是注意到，Aurora single-writer是唯一的record seq发生器，Aurora SIGMOD17' 里面提到的 'the log is the database' 也可以理解成是复制状态机的一种变相表述。如果再读读后面Aurora Quorum成员变更的方案，就会发现该方案跟Raft的joint-consensus方案在关键思路上也是一致的。
Multi-Paxos和Aurora Quorum也有方案细节和实现上的多处差异，几个典型差异如下：
- 差异一：标准Multi-Paxos的quorum system是简单多数派(Q=N/2+1)，Aurora Quorum配置的是NWR=643。不过这个差异实际上并不大，根本上讲，只要保证两轮epoch的数据确认状态能够正确传递即可， 这篇文章 做过一些分析。
- 差异二：Multi-Paxos里面要求新的proposer使用新的proposal id来明确已有日志确认状态的，Aurora Quorum是先用旧的epoch来完成这步，然后再递增全局epoch（epoch记录在整个Aurora实例的metadata上，等于是维护在中心化的一个节点上）。这里正确性实际上是不明确的，可能Aurora在这里额外做了限制，比如靠外部来保证只允许一个实例做recovery？
- 差异三：Multi-Paxos数据提交链路比Aurora Quorum多一跳。这个差异要从几个方面看。本质上讲这个差异并不大，等于是bookkeeping中couting replica的工作从leader上上提到了Aurora计算节点上，这跟共识的数据库背景有关。但是实现效果上可能差异比较大，一是网络多一跳（这个也看各段连接的网络质量），二是leader失效导致的短时间不可用（一般是几秒到几十秒）。
总结下来，三句话：
- Aurora Quorum通过 '引入epoch' 和 '单点record generator'，将简单的quorum system改成了和Multi-Paxos本质相同的共识系统。
- Aurora Quorum的成员变更与Raft协议的joint-consensus思路一致。
- 从CAP角度看，Aurora Quorum 和 Spanner Multi-Paxos是强一致的CP系统，Dynamo Quorum是弱一致的AP系统。
周边的几个问题。
有说法说Aurora Consensus从存储层剥离，这是不严谨的。
要么系统就设计成弱一致的，让用户业务去承担弱一致的麻烦。如果设计成强一致的，那么应该是无法逃脱FLP定理的魔掌，'引入epoch'这一点就绕不开。再去审视上述观点就可以知道，实际上Aurora Consensus是跨了存储组件和DB组件，存储组件不只是简单地负责存储。
Aurora与2PC
有人认为Aurora是个单写系统，本来就不需要2PC实现分布式事务。这个观点有失偏颇，Aurora避开2PC并不是trivial的。即使Aurora只有单点接受客户端写入，单点生成redo log records，但一个事务的多条records的持久化可能是分散在不同存储节点上的，因为一个事务可能涉及多个PG，使用2PC来保证事务的多个操作的原子性也未尝不可。
相比之下，Socrate（微软SQL Server的存储计算分离版本）是将WAL写到LandingZone，LandingZone是一个可靠的持久化存储组件，在整个架构中，实际上可以视为单一可靠硬盘，这种架构下绕开2PC就是很自然的。
Aurora Multi-Master 与 Spanner的分布式事务
Aurora的Multi-Master实现目前没有公开，只有AWS re-invent ppt上有少量信息透漏。
对比两个多写方案，Spanner是先将数据分区，DML操作请求是直接发送到对应的分区，提交时走2PC完成原子提交。冲突的多个写请求实际上是被路由到分区所在leader节点来完成协调的，例如写写冲突用行锁来解决，这几本上完全限定在执行期间的事务并发控制逻辑里面。
Aurora Multi-Master的方案似乎是多个master各自完成读写，官方PPT里面说没有全局序，所以segment里面应该是有多个redo record日志流，与多个master一一对应，segment的状态机等于基线数据加一组有偏序关系的redo record日志流。各个master生成自己的redo record发送到存储层去触发冲突检测。这个过程有点类似于EPaxos的多点写，两个冲突的redo record写到同一组副本，某些副本会检测到冲突，至少一个写请求会失败或者解决冲突后重试。这种冲突检测方式要比Spanner复杂很多，毕竟Spanner分层非常清晰。另外，Aurora修改数据估计还是read-modify-write的模式，这跟EPaxos的kv盲写还不太一样（EPaxos会在副本本地解决冲突然后建立完序关系再写log，之后再通知到请求端），Aurora Multi-Master似乎不需要像EPaxos一样对read/write quorum set做非常大的调整。