前言
这篇文章是《漫谈分布式》系列文章的第五篇，主题为线性一致性和共识算法，以理清概念为主，不涉及具体的共识算法，如有兴趣参考文章 MIT 6.824 学习笔记（二） 介绍了 Raft 算法以及 The Part-Time Parliament 论文笔记 记录了 Paxos 论文的笔记。
一致性保证
大部分分布式数据库都至少提供最终一致性。但因为其表现和单线程读写变量并不一致，单线程并不存在读取到过期数据或读取失败等问题，最终一致性会增加应用层开发的难度。下面探讨分布式系统中所能提供的更强的一致性模型：线性一致性和因果一致性。一致性模型和我们之前讨论的事务隔离级别这两个概念存在一些重合，但这两个概念其实是互相独立的：事务隔离主要是防止并行执行事务带来的竞争问题，而一致性模型则是在网络延迟或故障时如何协调多个备份节点的状态。
线性一致性
线性一致性又称为原子一致性、强一致性。关于线性一致性的详细介绍，可以读 Linearizability: A Correctness Condition for Concurrent Objects。线性一致性为分布式系统提供了数据单一副本的假象。
下图以 A、B、C 发起读写操作为例，图中标识的是客户端从发起请求到收到回包的时延，网络延迟的原因，客户端收到回包的时延不一。因为不确定服务端什么时候成功处理完写操作，在读写操作的时间段存在重合的情况下，读操作返回的有可能是旧值也有可能是新值。
线性一致性保证所有的读写操作在一个单调递增的物理时间线上串行地向执行，提供单一对象读写的假象，不允许出现读回退的现象：
用户 A 已经成功读取到写入成功后的值 1，B 的读操作发生在 A 之后，线性一致性要求 B 也应该读取到写入成功后的值。在线性一致性系统中，一旦客户端的写操作成功执行了，所有客户端都能读取到最新的值，因此线性一致性也称为新鲜度保证（Recency Guarantee）。
线性一致性和可串行性的对比
-
可串行性
可串行性为事务的隔离性保证，特别是涉及多个对象读写的事务，可串行性保证了并行事务的执行和串行执行事务的结果一致。
-
线性一致性
线性一致性是指对单一对象读写的新鲜度保证（总能读取到最新值）。和事务不同的是，不涉及对多个操作的打包。
数据库可以同时提供可串行性和线性一致性的保证，这两者的结合被称为严格串行性（Strict Serializability）或强单一副本串行性（Strong One-Copy Serializability 简称 Strong-1SR）。基于 2PL 或串行执行事务所实现的可串行性通常也是线性一致性的。但 SSI 并不是线性一致性的，SSI 中读操作读取的是数据快照，并不是最新写入的值，因此不遵循线性一致性。
使用场景
线性一致性一般用于以下场景：
-
Leader 选举
-
分布式锁
-
实现唯一约束
-
时序依赖
下面是一个时序依赖的例子：
上图中，Web Server 先将图片上传到 CDN，上传完成后再发送指令给 Image Resizer。如果整个的操作流程不是线性一致性的，那么可能出现 Image Resizer 在接收到 resize 指令之后拉取不到图片或者拉取到的是老版本的图片。
实现线性一致性
实现线性一致性最简单的做法是只用一个数据副本，但单一数据副本无法做到容灾，容灾最常见的做法是对数据备份多份副本。
在之前漫谈分布式：数据复制 文章中讨论过复制的几种方式：
基于单 leader 的复制：不保证遵循线性一致性
如果只在主节点或者同步复制的备节点执行读操作，可能是线性一致的。但注意并不是所有主从复制的数据库都遵循线性一致，因为有些采用了快照隔离，或者由于并行 bug 导致，如 Call Me Maybe: MongoDB Stale Reads 所介绍的。
脑裂情况下可能会违背线性一致性，或者异步复制方式下发生故障切换时，存在丢失写的可能，也违反了线性一致。
多 leader 复制：不遵循线性一致性
多 leader 复制通常不是线性一致的，多个节点会同时处理写请求并且异步复制，当引发写冲突也意味着违背了线性一致性所提供的单一数据的假象。
无中心复制：不保证遵循线性一致性
无中心复制在网络延迟的情况下也可能违反线性一致：
即使满足 Quorum 条件，执行结果也可能不是线性一致。B 的读请求在 A 之后，但 A 返回的值却比 B 的新。如果读操作在返回结果给客户端前同步执行读修复（Read Repair），并且写操作前需要先读取 quorum 节点的最新状态，采用这种方法可以实现线性一致，不过会带来性能损失，
但这种方式只能实现线性读写，不支持线性 Compare-And-Set 操作。如果希望支持线性 Compare-And-Set 操作，需要共识算法来支持，参考论文 Wait-Free Synchronization。
共识算法
共识算法类似于单 leader 复制，另外包括了避免脑裂和过期副本的处理机制，因此可以实现线性一致性。
顺序保证
在介绍共识算法之前，先讨论顺序保证、全序广播这两个概念。
顺序与因果关系
事件顺序如此重要的原因是因为从事件发生的顺序可以得出事件的因果关系。如果一个系统中的事件顺序符合因果关系，那么称该系统遵循因果一致性。因果一致性比线性一致性稍弱，要求具有因果关系的操作在所有节点上的顺序必须一致，无因果关系的并发操作在不同节点的顺序可以不一致。
全序与偏序
全序关系（Total Order）允许任意两个元素可以比较，偏序关系（Partial Order）则存在无法比较的元素，因果关系就属于偏序，因为并发操作之间不存在因果关系无法比较。全序和偏序的区别在不同的一致性模型也有所展现：
-
线性一致性
在线性一致性系统中，事件是全序排序的。线性一致性的行为就如同只存在单一数据副本，并且所有操作是原子性的。因此任意两个操作的先后顺序都可以比较，只存在一条时间线，不存在并行的操作。
-
因果一致性
在因果一致性系统中，并行的操作无法互相比较，因此事件是偏序的。
因果一致性 vs 线性一致性
如果一个系统是线性一致性的，那同时也遵循因果一致性。实现线性一致性的系统会牺牲性能和可用性（CAP 定理），而通常我们只需要保证事件符合因果关系。除了线性一致性，还有其他更高效的做法来提供因果一致性，因果一致性也是生产环境中在网络异常的情况下还能保证可用性的最强的一致性级别。
维护因果关系
为了维护因果关系，需要知道每个操作发生的先后顺序，即 “happened-before” 关系。
在 漫谈分布式：数据复制 写冲突小节介绍了 Lamport 逻辑时钟、版本向量的方式来比较事件的先后顺序。这两种方式虽然维护了因果关系，但仍然无法满足某些业务场景，考虑用户昵称唯一的例子， Lamport 逻辑时钟只能在事后（收集到所有节点的操作后）根据操作的逻辑时钟大小来决定取昵称操作成功与否，无法在用户发起取昵称请求时就判断这次请求能否成功。
在单 leader 复制模式中，leader 每次递增日志的索引序号，通过日志索引序号，复制日志定义了所有操作的全序关系且该顺序符合因果关系。单 leader 复制模式虽然可以满足用户昵称唯一的业务要求，但也带来了一些挑战点：
- 仅单一 leader 处理请求，吞吐量变大时如何扩展？
- Leader 如果挂了，如何容灾处理？
全序广播
单 leader 复制模式已经提供了事件顺序保证，如果解决了容灾扩容的问题，那就能够实现线性一致性了。全序广播（Total Order Broadcast），也称为原子广播（Atomic Broadcast）作为节点间消息传递的协议，其提供两个保证：
- 可靠性传播：不会丢消息，即使有部分节点挂了的情况下。
- 全序传播：每个节点收到消息的顺序相同。
全序广播可以用来实现数据库备份：每条消息代表一个写操作，如果每个 replica 以同样的顺序处理该写操作，那么所有 replica 的状态是保持一致的，这也称为状态机复制（State Machine Replication）。
全序广播也可以用来实现可串行化事务：每条消息代表一个确定性事务，以存储过程的方式执行。如果每个节点以相同的顺序处理消息，那么数据库中所有分区和备份的状态保持一致。
全序广播一个最重要的特征是：消息在传递时顺序就已经确定了，弥补了逻辑时钟只能事后处理的缺陷。基于全序广播可以实现线性一致性，基于线性一致性可以实现全序广播，因此可以认为这两个概念是等价的。
共识算法
如何实现全序广播呢？首先先了解什么是共识算法。在分布式系统中，网络数据包可能会丢失、乱序、重复或出现不定长的延时，不同节点的时钟只能尽可能的近似，且每个节点可能会暂停（例如忙于垃圾回收）或崩溃。共识（Consensus），简单来说就是让分布式系统中的多个节点对某个观点达成一致，掩盖了分布式系统中网络延迟、节点时钟偏差等问题，提供了多节点一致的抽象。在一些场景下，各个节点达成一致很重要，比方说 leader 选举场景下，所有节点都需要知晓哪个节点为 leader，在网络异常情况下避免出现脑裂的问题；还有在事务原子提交的场景下，所有节点对事务的处理（提交还是回滚）需要保持一致。
二阶段提交 Two-Phase Commit (2PC)
原子性用以避免事务失败执行导致数据库处于中间状态，这对涉及多对象事务和需要维护二级索引的场景来说尤其重要。二阶段提交是保证原子性最广泛运用的算法，也是共识算法的一种，不过并不算一个高效的算法。
在单节点数据库上，原子性通常由 WAL 来保证，事务准备提交前先写入日志文件中。涉及多节点的事务，则可能出现在某些节点被提交而另外的节点被终止，导致各节点状态不一致。
二阶段提交算法提供了多节点事务原子性的保证，其基于以下假设：
- 所有节点都采用 WAL，写入后即使节点发生故障依然能保持日志完整。
- 所有节点不会永久性宕机可以恢复。
基本流程图如下：
从图中可以看出算法引入一个新角色：协调者（coordinator）或称事务管理者。
-
第一阶段：提交请求阶段，也称为投票阶段
- 协调者节点向所有参与者节点询问是否可以执行提交操作，等待各参与者节点的响应。
- 参与者节点执行询问发起为止的所有事务操作，将 Undo 和 Redo 信息写入 WAL 日志，并将执行结果恢回复给协调者（执行成功返回“同意”，执行失败返回“终止”）。
-
第二阶段：提交执行阶段，也称为完成阶段
- 当协调者节点从所有参与者节点获得的相应消息都为“同意”时，协调者将提交信息写入 WAL 日志，然后向所有参与者节点发出“提交”的请求。参与者节点将提交信息写入 WAL 日志，并提交事务，释放在整个事务期间内占用的资源，回复协调者节点“提交完成”的消息。如果有参与者节点回复超时，协调者将无限重试直到成功。
- 如果任一参与者节点在第一阶段返回的响应消息为“终止”，或者有参与者回复超时，协调者将回滚信息写入 WAL 日志，并向所有参与者节点发出“回滚”的请求，参与者节点使用 Undo 日志执行回滚，并释放在整个事务期间内占用的资源，回复协调者节点“回滚完成”消息。如果有参与者节点回复超时，协调者将无限重试直到成功。
2PC 性能比较差，每次都需要两次磁盘强制写和传输两条消息的网络时延。采用 2PC 实现分布式事务还存在以下问题：
- 协调者是整个系统的单点，无法容灾。
- 很多应用在部署上是无状态的，状态通常会保存在数据库中。当引入协调者作为应用的一部分，而协调者本身又是带状态的，这会改变整个应用的部署策略。
- 2PC 会放大错误，完成一个事务需要所有节点的响应。一旦某个节点无响应时，会导致整个系统一直无限重试。这与构建高可用高容灾系统的出发点相违背。
XA
XA 是由 X/Open 组织提出的分布式事务的规范，实现了 2PC 协议。MySQL 和 PostgreSQL 等数据库都采用了 XA 来实现分布式事务。
三阶段提交 Three-Phase Commit (3PC)
2PC 是阻塞性的协议，如果协调者挂了，需要一直等待直到协调者恢复。3PC 优化了 2PC 使之变成非阻塞的协议，但其假设了网络延迟和回包时延存在上限，在实际系统环境中并不能保证原子性。如果想实现非阻塞性的原子提交协议，需要一个完美的 failure detector。
容错共识算法
前面提到说，共识即让几个节点在某些事情上达成一致。共识问题可以归纳为：一个或多个节点发起提议，由共识算法来决策采纳其中一个提议。共识算法需要满足下面几个性质：
-
Uniform agreement
每个节点最终采纳的提议是一致的，不存在采纳不同提议的节点。
-
Integrity
每个节点只采纳提议一次，不会重复采纳。
-
Validity
被采纳的值必须是由某个节点提议的。
-
Termination
每个节点最终都会采纳提议。
Termination 属于 liveness property，其他三个性质属于 safety property。最著名的容灾共识算法有 Viewstamped Replication (VSR)、Paxos、Raft 和 Zab。
共识算法与全序广播
前面提到全序广播要求每个消息被传递一次，并且在所有节点上的顺序一致。如果每一轮消息传递都采用共识算法，即能保证每个节点每一轮收到的消息一致，回顾共识算法的四个性质：
-
Uniform agreement
每个节点最终采纳的提议是一致的，最终所有节点上消息的顺序保证是一致的。
-
Integrity
每个节点只采纳提议一次，不会重复采纳，保证了消息不会重复处理。
-
Validity
被采纳的值必须是由某个节点提议的，保证消息是真实有效的。
-
Termination
每个节点最终都会采纳提议，保证消息传递的可靠性。
可以推导出，全序广播等价于多轮共识算法，基于全序广播可以实现线性一致性，因此基于多轮共识算法可以实现线性一致性。
