一、CAP 理论和 BASE 理论

理论是指导业界实现的纲领，也是提炼了多年研究的精华，在分布式一致性领域，最主要的指导理论是 CAP 和 BASE 两个。

1. CAP 理论

CAP理论是 Eric Brewer 教授在2000年提出 的，是描述分布式一致性的三个维度，分别是指：

（1）一致性（Consistency）

CAP 理论中的一致性是指强一致性（ Strong Consistency ），又叫线性一致性（ Linearizable Consistency ），每次读操作都能保证返回的是最新数据；在分布式系统中，如果能针对一个数据项的更新执行成功后，所有的请求都可以读到其最新的值，这样的系统就被认为具有严格的一致性。强调的是数据正确。

（2）可用性（Availablity）

任何一个没有发生故障的节点，会在合理的时间内返回一个正常的结果，也就是对于每一个请求总能够在有限时间内返回结果。强调的是不出错。

（3）分区容忍性（Partition-torlerance）

当节点间出现网络分区，照样可以提供满足一致性和可用性的服务，除非整个网络环境都发生了故障，强调的是不挂掉。那么，什么是网络分区呢？分区是系统中可能发生的故障之一，可能有节点暂时无法提供服务：发生了像 长时间 GC、CPU 死循环、链接池耗尽或者是网络通信故障等问题。

CAP 指出，一个分布式系统只能满足三项中的两项而不可能满足全部三项。举例来看：如下图所示，假设有五个节点：n1~n5 ，因网络分区故障被分成两组：[n1、n2]和[n3~n5]，那么当n1处理客户端请求时（为了支持"容忍网络分区"，即支持 P）：

1. 首先我们可以明确知道，在分布式系统中，系统间的网络不能 100% 保证健康，一定会有故障的时候，而服务有必须对外保证服务。因此 P（分区容错性） 不可避免。
2. 如果要保证C(一致性)，那么它需要把消息复制到所有节点，但是网络分区导致无法成功复制到n3~n5，所以它只能返回"处理失败"的结果给客户端。（这时系统就处于不可用状态，即丧失了A），只能满足 CP
3. 如果要保证可用性 A，那么 n1 就只能把消息复制到 n2，而不用复制到 n3~n5(或者无视复制失败/超时)，但 n3 同时也可能在处理客户端请求，n3 也为了保证A而做了同样的处理。那么 [n1、n2]和[n3~n5]的状态就不一致了，于是就丧失了C(一致性)，只能满足 AP。

既然 CAP 理论无法全部满足，为了指导工业实现，就需要降低标准，因此出现了 BASE 理论。

2. BASE理论

前面有提到，CAP 中的C（一致性）指的是强一致性，强一致性是程度最高一致性要求，也是最难实现的，而BASE理论则提到了另外的处理。BASE 理论是 eBay 的架构师 Dan Pritchett 提出的，它的思想是：“即使无法做到强一致性，但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性” 。

BASE 理论有三项指标：

• 基本可用（Basically Available）：是指分布式系统在出现不可预知故障的时候，允许损失部分可用性：比如响应时间、功能降级等；
• 软状态（ Soft State）：也称为弱状态，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点之间进行数据同步的过程存在延时；
• 最终一致性（ Eventual Consistency）：强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达成一致的状态。

**BASE 理论面向的是大型高可用、可扩展的分布式系统。BASE 通过牺牲强一致性来获得可用性，并允许数据短时间内的不一致，但是最终达到一致状态。**为了达到一致性，需要更深入一点，尝试设计出一种算法，能够让分布式系统内部可以暂时容忍存在不同的状态，但最终能够保证大多数节点的状态能够达成一致；同时，能够让分布式系统在外部看来，始终表现出整体一致的结果。这也就是后续讨论的共识算法内容。

二、拜占庭将军问题

拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了达到防御目的，每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。

这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成 。

在分布式系统领域, 拜占庭将军问题中的角色与计算机世界的对应关系如下:

• 将军：对应计算机节点;
• 忠诚的将军：对应运行良好的计算机节点；
• 叛变的将军：被非法控制的计算机节点；
• 信使被杀：通信故障使得消息丢失；
• 叛徒或间谍：通信被攻击, 攻击者篡改或伪造信息。

拜占庭将军问题的核心在于在缺少可信任的中央节点和可信任的通道的情况下，分布在不同地方的各个节点应如何达成共识。我们可以将这个问题延伸到分布式计算领域中。

在分布式计算领域中，试图在异步系统和不可靠的通道上达到一致性状态是不可能的，因此在对一致性的研究过程中，都往往假设信道是可靠的，而事实上，大多数系统都是部署在同一个局域网中，因此消息被篡改的情况非常罕见；另一方面，由于机器硬件和网络原因导致的消息不完整问题，也仅仅只需要一套简单的校验算法即可避免。

那么当我们假设拜占庭问题不存在（所有消息都是完整的，没有被篡改），那么这种情况下需要什么算法来保证一致性呢？拜占庭将军问题的提出者 Lamport 提出了一种非拜占庭将军问题的一致性解决方案——Paxos 算法

三、Paxos 算法

与拜占庭将军问题一样，Lamport 同样使用故事的方式来提出 Paxos 问题

希腊岛屿 Paxos 上的议员在议会大厅中表决通过法律，并通过服务员传递纸条的方式交流信息，每个议员会将通过的法律记录在自己的账目上。问题在于执法者和服务员都不可靠，他们随时会因为各种事情离开议会大厅，并随时可能有新的议员进入议会大厅进行法律表决，使用何种方式能够使得这个表决过程正常进行，且通过的法律不发生矛盾。

不难看出故事中内容和现实世界也有着对应关系：

• 议会大厅：分布式系统；
• 议员：节点或进程；
• 服务员传递纸条：节点间的消息传递的过程；
• 法律：需要保证一致性的值；
• 议员和服务员的进出：节点/网络的失效和加入；
• 议员的账目：节点中的持久化存储设备。

上面表决过程的正常进行可以表述为进展需求：当大部分议员在议会大厅呆了足够长时间，且期间没有议员进入或者退出，那么提出的法案应该被通过并被记录在每个议员的账目上。

Paxos 算法需要解决的问题就是如何在上述分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

1.Paxos 算法的工作流程

Paxos 算法将分布式系统中的节点分为三种角色：提案者、决策者和记录者，他们的具体职责和定义为：

• 提案者：称为 Proposer，提出对某个值进行设置操作的节点，设置值这个行为就是提案（Proposal）。值一旦设置成功，就是不会丢失也不可变的。需要注意的是，Paxos 是典型的基于操作转移模型而非状态转移模型来设计的算法，所以这里的“设置值”不要类比成程序中变量的赋值操作，而应该类比成日志记录操作。
• 决策者：称为 Acceptor，是应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，就意味着这个提案被批准（Accept）。提案被批准，就意味着该值不能再被更改，也不会丢失，且最终所有节点都会接受它。
• 记录者：被称为 Learner，不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案。比如，少数派节点从网络分区中恢复时，将会进入这种状态。

在使用 Paxos 算法的分布式系统里，所有的节点都是平等的，它们都可以承担以上某一种或者多种角色。

在分布式的环境下，不同参与者之间通过收发消息来进行通信。为了确保有明确的多数派，主要会受到下面两个因素的共同影响：

• 系统内部各个节点间的通讯是不可靠的。每个参与者可能会因为出错而导致停止、重启等情况，它们发出、收到的信息可能延迟送达、也可能会丢失，但不去考虑消息有传递错误的情况。
• 系统外部各个用户访问是可并发的。如果系统只会有一个用户，或者每次只对系统进行串行访问，那单纯地应用 Quorum 机制，少数节点服从多数节点，就已经足以保证值被正确地读写了。

第一点“系统内部各个节点间的通讯是不可靠的”，是网络通讯中客观存在的现象，也是所有共识算法都要重点解决的问题。所以我们重点看下第二点“系统外部各个用户访问是可并发的”，即“分布式环境下并发操作的共享数据”问题。

我们继续看 Paxos 算法是怎么解决并发操作带来的竞争的。

2.执行过程

首先我们规定一个提议包含两个字段：[n, v]，其中 n 为序号（具有唯一性），v 为提议值。

Paxos 算法主要包括两个阶段，与2PC（二阶段提交协议）类似。

• 准备（Prepare）阶段
• 批准（Accept）阶段

Prepare 阶段

1. Prepare 就相当于抢占锁的过程，如果某个提案节点准备发起提案，必须先向所有的决策节点广播一个许可申请（称为 Prepare 请求）。提案节点的 Prepare 请求中会附带一个全局唯一的数字 n 作为提案 ID，提议内容为[n1,v1]
2. 由于之前还未接受过 Prepare 请求，那么它会返回一个[no previous]的Prepare响应，并且设置当前接受的提议为[n1,v1]，同时保证以后不会再接收序号小于 n1 的提议。
3. 如果 Acceptor 再次收到一个 Prepare 请求，提议内容为[n2,v2]，此时会有两种情况。
   1. 如果 n2 < n1，此时 Acceptor 就会直接抛弃该请求
   2. 如果 n2 >= n1，此时 Acceptor 就会发送一个[n1,v1]的 Prepare 响应，设置当前接受到的提议为[n2,v2]，同时保证与上一步逻辑相同，保证以后不会再接受序号小于 n2 的提议。

Accept阶段

1. 当一个 Proposer 接收到超过一半的 Acceptor 的 Prepare 响应时，此时它就会发送一个针对[n,v]提案的 Accept 请求给 Acceptor。
2. 如果一个 Acceptor 收到一个编号为n的提案的 Accept 请求，此时有两种情况。
   1. 如果该 Acceptor 没有对编号大于 n 的 Prepare 请求做出过响应，它就会接受该提案，并发送 Learn 提议给 Learner
   2. 如果该 Acceptor 接受过编号大于 n 的 Prepare 请求，那么它就会拒绝、不回应或回复 error。（如果一个 Proposer 没有收到过半的回应，那他就会重新进入第一阶段，递增提案号后重新提出 Prepare请求）

在上述过程中，每一个 Proposer 都有可能会产生多个提案。但只要每个 Proposer 都遵循如上述算法运行，就一定能保证算法执行的正确性。

当每一个 Acceptor 收到 Accept 请求时，都会在遵循上述运行条件的情况下，接收并持久化当前提案 ID 和提案附带的值。当 Proposer 收到了多数派 Acceptor 的应答后，协商结束，共识决议形成，将形成的决议发送给所有Learner 进行记录。整个过程的时序图如下所示：

3.活锁问题

在 Paxos 算法实际运作的时候还存在这样一种极端的情况——当有两个 Proposer 依次提出了一系列编号递增的提案，此时就会导致陷入死循环，无法完成第二阶段，也就是无法选定一个提案，如以下场景。

1. Proposer P1 发出编号为 n1 的 Prepare 请求，收到过半响应，完成了阶段一的流程。
2. 同时，Proposer P2 发出编号为 n2 的 Prepare 请求（n2 > n1），也收到了过半的响应，完成了阶段一的流程，并且 Acceptor 承诺不再接受编号小于 n2 的提案。
3. P1 进入第二阶段时，由于 Acceptor 不接受小于 n2 的提案，所以 P1 重新回到第一阶段，递增提案号为 n3 后重新发出 Prepare 请求
4. 紧接着，P2 进入第二阶段，由于 Acceptor 不接受小于 n3 的提案，此时它也重新回到第一阶段，递增提案号后重新发出 Prepare 请求
5. 于是 P1、P2 陷入了死循环，谁都无法完成阶段二，这也就导致了没有 value 能被选定。 为了保证 Paxos 算法的可持续性，以避免陷入上述提到的死循环，就必须选择一个主 Proposer，并规定只有主 Proposer 才能够提出提案。这样一来，只要主 Proposer 和过半的 Acceptor 能够正常进行网络通信，那么肯定会有一个提案被批准（第二阶段的 accept），则可以解决死循环导致的活锁问题。

Basic Paxos 的价值在于开拓了分布式共识算法的发展思路，但因为它有如下缺陷，一般不会直接用于实践：Basic Paxos 只能对单个值形成决议，并且决议的形成至少需要两次网络请求和应答（准备和批准阶段各一次），高并发情况下将产生较大的网络开销，极端情况下甚至可能形成活锁。所以在实际应用中我们会选择更好理解的几个算法，比如 Raft、ZAB 等。

四、Raft 算法

从上面可以看出，Paxos算法相对来说较为复杂且难以理解，因此在后来又出现了一种用于替代Paxos 的算法——Raft

Raft 算法是一种简单易懂的共识算法，Raft 使用了分治思想把算法流程分为三个子问题：选举（Leader election）、日志复制（Log replication）、安全性（Safety）三个子问题，当这三个问题同时被解决时，就等价于达成共识。

• Leader 选举：当前 leader 宕机了或集群初始化的情况下，新 leader 被选举出来。
• 日志复制：leader 必须能够从客户端接收请求，然后将它们复制给其他机器，强制它们与自己的数据一致。
• 安全性：如何保证上述选举和日志复制的安全，使系统满足最终一致性。

在 Raft 中节点被分为 Leader Follower Cabdidate 三种角色，角色之间可以相互转换：

• Leader（主节点）
• Follower（从节点）
• Candidate（竞选节点）

具体的转换如下图：

Term：是有连续单调递增的编号，每个 term 开始于选举阶段，一般由选举阶段和领导阶段组成。

随机超时时间：Follower 节点每次收到 Leader 的心跳请求后，会设置一个随机的，区间位于[150ms, 300ms)的超时时间。如果超过超时时间，如果在倒计时结束前没有收到 Leader 的心跳包，此时 Follower 就会变为 Candidate，开始进入竞选状态。

心跳续命：Leader 在当选期间，会以一定时间间隔向其他节点发送心跳请求，以维护自己的 Leader 地位。

执行流程

1、Leader 选举

当某个 follower 节点在超时时间内未收到 Leader 的请求，它则认为当前 Leader 宕机或者当前无Leader，将发起选举， 既从一个 Follower 变成 Candidate。

这个转变过程中会发生四件事：

• 增加本地节点的 Current Term 值；
• 将状态切换为 Candidate；
• 该节点投自己一票；
• 批量向其他节点发送拉票请求（RequestVote RPC）。

在这个过程中，其他 Follower 节点收到拉票请求后，需要判断请求的合法性，然后为第一个到达的合法拉票请求进行投票。投票过程对于 Follower 的约束有三点：

• 在一个任期 Term 中只能投一张票；
• 候选人的 Term 值大于 Current Term，且候选人已执行的 Log 序号不低于本地 Log，则拉票请求是合法的；
• 只选择首先到达的合法拉票请求；

如果一个 Candidate 收到了超过半数的投票，则该节点晋升为 Leader，会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举；开始进行日志同步、处理客户端请求等。

如果一次选举中，Candidate 在选举超时时间内没有收到超过半数的投票，也没有收到其他Leader的请求，则认为当前 Term 选举失败，进入下一个选举周期。

2、日志复制

在了解日志同步前，需要了解“复制状态机”这个概念。共识算法的实现一般是基于复制状态机（Replicated state machines），何为复制状态机：

简单来说：相同的初识状态 + 相同的输入 = 相同的结束状态。就是说不同节点要以相同且确定性的函数来处理输入，而不要引入一下不确定的值，比如本地时间等。如何保证所有节点 ，使用replicated log 是一个很不错的注意，log 具有持久化、保序的特点，是大多数分布式系统的基石。

因此，可以这么说，在 raft 中，leader 将客户端请求（command）封装到一个个 log entry，将这些log entries 复制（replicate）到所有 follower 节点，然后大家按相同顺序应用（apply）log entry 中的 command，则状态肯定是一致的。

下图形象展示了这种基于日志的复制状态机：

请求完整流程

当系统（leader）收到一个来自客户端的写请求，到返回给客户端，整个过程从leader的视角来看会经历以下步骤：

• 本地追加日志信息；
• 并行发出 AppendEntries RPC请求；
• 等待大多数 Follower 的回应。收到查过半数节点的成功提交回应，代表该日志被复制到了大多数节点中(committed)；
• 在状态机上执行 entry command。既将该日志应用到状态机，真正影响到节点状态(applied)；
• 回应 Client 执行结果；
• 确认Follower也执行了这条 command；如果 Follower 崩溃、运行缓慢或者网络丢包，Leader 将无限期地重试 AppendEntries RPC，直到所有 Followers 应用了所有日志条目。

可以看到日志的提交过程有点类似两阶段提交(2PC)，不过与 2PC 的区别在于，leader 只需要大多数（majority）节点的回复即可，这样只要超过一半节点处于工作状态则系统就是可用的。

那么日志在每个节点上是什么样子的呢：

不难看到，logs 由顺序编号的 log entry 组成 ，每个 log entry 除了包含 command，还包含产生该log entry 时的 leader term。从上图可以看到，五个节点的日志并不完全一致，raft 算法为了保证高可用，并不是强一致性，而是最终一致性，leader 会不断尝试给 follower 发 log entries，直到所有节点的 log entries 都相同。

在上面的流程中，leader 只需要日志被复制到大多数节点即可向客户端返回，一旦向客户端返回成功消息，那么系统就必须保证 log（其实是log所包含的 command）在任何异常的情况下都不会发生回滚。这里有两个词：commit（committed），apply(applied)，前者是指日志被复制到了大多数节点后日志的状态；而后者则是节点将日志应用到状态机，真正影响到节点状态。

3、安全性

在上面提到只要日志被复制到多数节点，就能保证不会被回滚，即使在各种异常情况下，这跟leader election 提到的选举约束有关。在这一部分，主要讨论 raft 协议在各种各样的异常情况下如何工作的。

衡量一个分布式算法，有许多属性，如

• 协定性（Safety）：所有的坏事都不会发生（Something "bad" will never happen）。
• 终止性（Liveness）：所有的好事都终将发生，但不知道是啥时候（Something "good" will must happen, but we don't know when）。

在任何系统模型下，都需要满足 safety 属性，即在任何情况下，系统都不能出现不可逆的错误，也不能向客户端返回错误的内容。比如，raft 保证被复制到大多数节点的日志不会被回滚，那么就是safety 属性。而 raft 最终会让所有节点状态一致，这属于 liveness 属性。

raft 协议会保证以下属性：

（1）选举安全性

即任一任期内最多一个 leader 被选出。在一个集群中任何时刻只能有一个 leader。系统中同时有多余一个leader，被称之为脑裂（brain split），这是非常严重的问题，会导致数据的覆盖丢失。

在 raft 中，通过两点保证了这个属性：

• 一个节点某一任期内最多只能投一票；
• 只有获得多数投票的节点才会成为 leader。

因此，某一任期内一定只有一个leader。

（2）日志 append only

首先，leader 在某一 term 的任一位置只会创建一个 log entry，且 log entry 是 append-only。

其次，一致性检查。leader 在 AppendEntries 请求中会包含最新 log entry 的前一个 log 的 term 和index，如果 follower 在对应的 term index 找不到日志，那么就会告知 leader 日志不一致， 然后开始同步自己的日志。同步时，找到日志分叉点，然后将 leader 后续的日志复制到本地。

（3）日志匹配特性

如果两个节点上的某个 log entry 的 log index 相同且 term 相同，那么在该 index 之前的所有 log entry 应该都是相同的。

Raft 的日志机制提供两个保证，统称为 Log Matching Property：

• 不同机器的日志中如果有两个 entry 有相同的偏移和 term 号，那么它们存储相同的指令。
• 如果不同机器上的日志中有两个相同偏移和 term 号的日志，那么日志中这个 entry 之前的所有entry 保持一致。

（4）Leader 完整性

如果一个 log entry 在某个任期被提交（committed），那么这条日志一定会出现在所有更高term的leader 的日志里面。这个跟 leader election、log replication 都有关。

• 一个日志被复制到多数节点才算 committed
• 一个节点得到多数节点的投票才能成为 leader，而节点A给节点B投票的其中一个前提是，B的日志不能比A的日志旧

（5）状态机安全性

状态机安全性由日志的一致来保证。在算法中，一个日志被复制到多数节点才算 committed， 如果一个log entry在某个任期被提交（committed），那么这条日志一定会出现在所有更高 term 的 leader 的日志里面。

五、总结

分布式算法已经经历了近40年的发展，涌现出各种各样的算法。正如 Chubby 的作者所说：

There is only one consensus protocol, and that's “Paxos” — all other approaches are just broken versions of Paxos. 世界上只有一种共识协议，就是 Paxos，其他所有共识算法都是 Paxos 的退化版本。

虽然“世界上只有 Paxos 一种分布式共识算法”的说法有些夸张，但是如果没有 Paxos，那后续的 Raft、ZAB 等算法，ZooKeeper、etcd 这些分布式协调框架，Hadoop、Consul 这些在此基础上的各类分布式应用，都很可能出现得更曲折一点。

Paxos 不直接应用于工业界，但它的变体算法，比如 Multi Paxos、Raft 算法，以及今天我们没有提到的 ZAB 等算法，都是分布式领域中的基石。