从 Paxos 到 Raft，分布式一致性算法解析

一、CAP 理论和 BASE 理论

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

1. CAP 理论

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

（1）一致性（Consistency）

每次读操作都能保证返回的是最新数据；在分布式系统中，如果能针对一个数据项的更新执行成功后，所有的请求都可以读到其最新的值，这样的系统就被认为具有严格的一致性。

（2）可用性（Availablity）

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

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

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

CAP 指出，一个分布式系统只能满足三项中的两项而不可能满足全部三项。举例来看：如下图所示，假设有五个节点：n1~n5 ，因网络分区故障被分成两组：

[n1、n2]和[n3~n5]，那么当 n1 处理客户端请求时（为了支持"容忍网络分区"，即支持 P）：

1. 如果要保证 C(一致性)，那么它需要把消息复制到所有节点，但是网络分区导致无法成功复制到 n3~n5，所以它只能返回"处理失败"的结果给客户端。（这时系统就处于不可用状态，即丧失了 A） 

2. 如果要保证可用性 A，那么 n1 就只能把消息复制到 n2，而不用复制到 n3~n5(或者无视复制失败/超时)，但 n3 同时也可能在处理客户端请求，n3 也为了保证 A 而做了同样的处理。那么 [n1、n2]和[n3~n5]的状态就不一致了，于是就丧失了 C(一致性)。

3. 如果不容忍网络分区，则 P（分区容忍性）不能满足。

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

2. BASE 理论

BASE 理论是 eBay 的架构师 Dan Pritchett 提出的，它的思想是：“即使无法做到强一致性，但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性” 。

BASE 理论有三项指标：

• 基本可用（Basically Available）：是指分布式系统在出现不可预知故障的时候，允许损失部分可用性：比如响应时间、功能降级等；

• 软状态（ Soft State）：也称为弱状态，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点之间进行数据同步的过程存在延时；

• 最终一致性（ Eventual Consistency）：强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达成一致的状态。

BASE 理论面向的是大型高可用、可扩展的分布式系统。BASE 通过牺牲强一致性来获得可用性，并允许数据短时间内的不一致，但是最终达到一致状态。

接下来，我们一起学习经典的分布式算法。

二、经典分布式算法

1. PAXOS 算法

Paxos 算法是 Leslie Lamport 在 1990 年提出的，经典且完备的分布式一致性算法。Leslie 大佬也在这个算法中展示了他不同常人的智商。

该算法的目标是：在不同的节点间，对一个 key 的取值达成共识（同一个值）。

（1）角色

协议将系统中的节点分为三种角色：Proposer（提案者）、Acceptor（决议者）、Leaner（学习者），他们的具体职责为：

• 提案者：对 key 的值提出自己的值；

• 决议者：对提案者的提议进行投票，选定一个提案，形成最终决策；

• 学习者：学习决议者达成共识的决策。

（2）约束条件推导

本小节将通过推导来引出 Paxos 算法的约束条件，故事灵感来自于分布式理论：深入浅出 Paxos 算法【1】，在原文基础上优化了可读性。

https://my.oschina.net/u/150175/blog/2992187

在介绍 paxos 算法协议前，我们先来看一个故事，故事名叫《小明姓什么》。在孤儿院长大的小明马上就要步入社会了，但是孤儿院的老师还没有找到小明的姓氏，因此决定开会解决这个问题。

在会议上，由提案者 P 提出姓氏，然后决议者 A 来决定选择哪一个。

场景 1: Pa 向 A1 提出“赵”， Pb 向 A2，A3 提出“钱”。现在有超过半数的决策者接受了“钱”，所以最终的决策结果就是“钱”。

这里引出了一个基础的约束条件：

P0. 当集群中，超过半数的 Acceptor 接受了一个议案，那我们就可以说这个议案被选定了（Chosen）

P0 是完备的条件，但是不实用。

场景 2 ：Pa 向 A1 提出“赵”， Pb 向 A2 提出“钱”, Pc 向 A3 提出“孙”，这样就出现了三个决议者各执一票，无法形成多数派决议的局面。

因此，必须允许一个决策者能够接受多个议案，后接受的议案可以覆盖之前的议案。这样，Pc 可以向所有决策者提起议案“孙”，形成一个多数派决议。

但是，现在 Pa Pb 提案者也可以利用重新提案的能力，来重新提出自己的提案，导致形成的共识重新被推翻。会议乱成了一锅粥。因此还需要新的约束条件来保证会议正常进行。

我们提炼一下问题：在不同版本的提案中，选择一个固定的值作为全局决议。

Paxos 算法就是为解决这种不一致问题而提出的，算法目标有两个：

• T1：一次选举必须要选定一个议案（不能出现所有议案都被拒绝的情况）；

• T2：一次选举必须只选定一个议案（不能出现两个议案有不同的值，却都被选定的情况）。

首先介绍一个概念 “编号”：编号在算法中是唯一自增的键值，假设第一个提出的议案版本是 n1， 接下来提出的第二个议案版本 n2 = n1+1 。有了编号之后，一条提案也变成了（Num， Value）二元组。

为了达成上述目标，算法提出了一组约束条件：

P1：一个 Acceptor 必须接受它收到的第一个议案。

P2：如果一个值为 v 的议案被选定了，那么被选定的更大编号的议案，它的值必须也是 v。

a：如果一个值为 v 的议案被选定了，那么 Acceptor 接受的更大编号的议案，它的值必须也是 v。

b：如果一个值为 v 的议案被选定了，那么 Proposer 提出的更大编号的议案，它的值必须也是 v。

P2 和 P2a、P2b 理解起来比较费劲。P2 这个约束是为了解决上述场景 2 中，形成决议后又被推翻覆盖的问题。有了约束 2 之后，当形成了决议“孙”，则后续提出的议案的值必须为“孙”。

那么，如何才能满足 P2 呢，P2a 约束是在场景 2 的问题决策域提出的。为了能够满足 P2a，自然可以在问题的产生域也提出约束， 既 P2b。如果算法能够满足 P2b，也就是将解决“产生一致性问题”的时机提前。所以，P2b 是 P2a 的充分条件，只要能满足 P2b，那 P2a 就自动满足。

那么，作为提案者，如何提前知道一个目前的决议（多数派）议案呢？接下来，我们就提出了新的约束 P2c：

P2c: 在所有 Acceptor 中，任意选取半数以上的集合，称这个集合为 S。Proposal 新的提案 Pnew （Nnew , Vnew ）必须符合下面两个条件之一：  1）如果 S 中所有 Acceptor 都没有接受过议案，那么 Pnew 的编号保证唯一性和递增，Pnew 的值可以是任意值。  2）如果 S 中有 Acceptor 曾经接受过议案，找出编号最大的议案 PN (N,V) 。那么 Pnew 的编号必须大于 N，Pnew 的值必须等于 V。

在 P2c 中，引入了多数派集合 S。根据集合 S 中是否有被接受的议案，来推断全局节点是否已经形成决议。根据约束 P0，如果一个议案（Nchosen, Vchosen）是被选中的，那么它必然是被多于半数节点选中的。那么，在任意一个多数派集合 S 中，一定会存在至少一个节点 A，它的数据中已经决议的议案是（Nchosen, Vchosen）。

反之，如果多数派集合中没有被决议的议案，表示此时系统中还没有一个被选定的决议。

看这个例子，假设目前选定了（3， Va）状态；下次发起提案时，proposer 选定 A3、4、5 作为集合 S 进行查询；提出了编号为 4 的提案，在 P2c 约束条件下，提案必定为（4，Va）。

因此，满足 P2c 的算法也满足 P2b 算法。

但是也可能存在这种情况，当 proposer 发查询请求时，还没有一个被确认的提案，所以发出了(4, Vb)提案，这样还是会破坏 P2b 约束。

因此，当一个议案在提出时（即使已经在发送的半路上了），它必须能够知道当前已经提出的议案的最大编号。这听起来很魔幻，毕竟跑在网线上的请求很难被召回。因此，我们提出了新的约束条件；

P3：议案（n，v）在提出前，必须将自己的编号通知给半数以上的 Acceptor。收到通知的 Acceptor 将 n 跟自己之前收到的通知进行比较，如果 n 更大，就将 n 确认为最大编号。当半数以上 Acceptor 确认 n 是最大编号时，议案（n，v）才能正式提交。

P4：Acceptor 收到一个新的编号 n，在确认 n 比自己之前收到的编号大时，必须承诺不再接受比 n 小的议案。

有了 P3 的约束，则能够保证两个不同编号的议案，不可能同时被认为是最大编号；同时再加上 P4 约束，保证了一个决议者不会对自己接受的议案版本进行回退。

至此，Paxos 算法的约束条件就介绍完了。

（3）协议流程

在 Paxos 中，一个决策过程（Round、Phase）分为两个阶段：

phase1（准备阶段）：

1. Proposer 向超过半数（n/2+1）Acceptor 发起 prepare 消息(发送编号)；

2. 如果 Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。否则拒绝返回。

phase2（决议阶段或投票阶段）：

1. 如果超过半数 Acceptor 回复 promise，Proposer 向 Acceptor 发送 accept 消息。注意此时的 V：V 就是收到的响应中编号最大的提案的，如果响应中不包含任何提案，那么 V 就由 Proposer 自己决定；

2. Acceptor 检查 accept 消息是否符合规则，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案。

在实际发展中，Paxos 算法也演变出一系列变种：

• PBFT（实用拜占庭容错）算法：是一种共识算法，较高效地解决了拜占庭将军问题；

• Multi-Paxos 算法：优化了 prepare 阶段的效率，同时允许多个 Leader 并发提议；以及 FastPaxos、EPaxos 等，这些演变是针对某些问题进行的优化，内核思想还是依托于 Paxos。

2. Raft 算法

Paxos 协议从被提出，一直是分布式一致性算法的标准协议，但是它不易理解，对于工程师来说实现起来很复杂，以至于算法提出近 30 年都没有一个完全版的实现方案。业界很多实现都是 Paxos-like。

Raft 算法是斯坦福大学 2017 年提出，论文名称《In Search of an Understandable Consensus Algorithm》，望文生义，该算法的目的是易于理解。Raft 这一名字来源于"Reliable, Replicated, Redundant, And Fault-Tolerant"（“可靠、可复制、可冗余、可容错”）的首字母缩写。

Raft 使用了分治思想把算法流程分为三个子问题：选举（Leader election）、日志复制（Log replication）、安全性（Safety）三个子问题。

• Leader 选举：当前 leader 跪了或集群初始化的情况下，新 leader 被选举出来。

• 日志复制：leader 必须能够从客户端接收请求，然后将它们复制给其他机器，强制它们与自己的数据一致。

• 安全性：如何保证上述选举和日志复制的安全，使系统满足最终一致性。

（1）概念介绍

在 Raft 中，节点被分为 Leader Follower Cabdidate 三种角色：

• Leader：处理与客户端的交互和与 follower 的日志复制等，一般只有一个 Leader；

• Follower：被动学习 Leader 的日志同步，同时也会在 leader 超时后转变为 Candidate 参与竞选；

• Candidate：在竞选期间参与竞选；

• 
  

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

随机超时时间：Follower 节点每次收到 Leader 的心跳请求后，会设置一个随机的，区间位于[150ms, 300ms)的超时时间。如果超过超时时间，还没有收到 Leader 的下一条请求，则认为 Leader 过期/故障了。

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

（2）协议流程

a. 选举流程

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

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

• 增加本地节点的 Current Term 值；

• 将状态切换为 Candidate；

• 该节点投自己一票；

• 批量向其他节点发送拉票请求（RequestVote RPC）。

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

• 在一个任期 Term 中只能投一张票；

• 候选人的 Term 值大于 Current Term，且候选人已执行的 Log 序号不低于本地 Log（Log 及已执行的概念见《日志复制》小节），则拉票请求是合法的；

• 只选择首先到达的合法拉票请求；

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

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

b. 日志复制

在了解日志同步前，需要了解“复制状态机”这个概念。

复制状态机（Replicated state machines）是指：不同节点从相同的初始状态出发，执行相同顺序的输入指令集后，会得到相同的结束状态。

If two identical, deterministic processes begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.

分布式一致性算法的实现是基于复制状态机的。

在 Raft 算法中，节点初始化后具有相同初始状态。为了提供相同的输入指令集这个条件，raft 将一个客户端请求（command）封装到一个 log entry 中。Leader 负责将这些 log entries 复制到所有的 Follower 节点，然后节点按照相同的顺序应用 commands，达到最终的一致状态。

当 Leader 收到客户端的写请求，到将执行结果返回给客户端的这个过程，从 Leader 视角来看经历了以下步骤：

• 本地追加日志信息；

• 并行发出 AppendEntries RPC 请求；

• 等待大多数 Follower 的回应。收到查过半数节点的成功提交回应，代表该日志被复制到了大多数节点中(committed)；

• 在状态机上执行 entry command。既将该日志应用到状态机，真正影响到节点状态(applied)；

• 回应 Client 执行结果；

• 确认 Follower 也执行了这条 command；如果 Follower 崩溃、运行缓慢或者网络丢包，Leader 将无限期地重试 AppendEntries RPC，直到所有 Followers 应用了所有日志条目。

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

在前面的流程中，leader 只需要日志被复制到大多数节点即可向客户端返回，而一旦向客户端返回成功消息，那么系统就必须保证 log 在任何异常的情况下都不会发生回滚。

这里推荐两个 Raft 算法动画演示，通过动画能够对 Raft 算法的选举和日志复制过程有直观清晰的认知。

• raft step by step 入门演示： http://thesecretlivesofdata.com/raft/

• raft 官方演示： https://raft.github.io/

在动画演示中，可以通过调整时间流速和时间轴来观察节点间通信。

也可以通过单击节点或者请求包来查看节点的具体状态和请求包的数据。

3. 安全性及约束

（1）选举安全性

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

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

• 一个节点某一任期内最多只能投一票；而节点 B 的 term 必须比 A 的新，A 才能给 B 投票。

• 只有获得多数投票的节点才会成为 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 完备性 

被选举人必须比自己知道的更多（比较 term 、log index）。

如果一个 log entry 在某个任期被提交（committed），那么这条日志一定会出现在所有更高 term 的 leader 的日志里面 。选举人必须比自己知道的更多（比较 term，log index）如果日志中含有不同的任期，则选最新的任期的节点；如果最新任期一致，则选最长的日志的那个节点。

选举安全性中包含了 Leader 完备性

（5）状态机安全性

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

三、总语

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

“这个世界上只有一种一致性算法，那就是 Paxos”

Paxos 算法的贡献和地位无可替代。理解了 Paxos 算法，再去理解其他算法，则会势如破竹。

Raft 算法以其易于理解和实现的特性，推动分布式一致性算法进入了广泛应用阶段，不再是工程师心中的那颗拿得起，放不下的朱砂痣。🐶

分布式一致性算法的前沿理论也在飞速发展着，值得我们继续学习和关注。

头图：Unsplash

作者：董友康

原文：https://mp.weixin.qq.com/s/JfJ8R8qrT-g6G7MDN9Tk6g

原文：从 Paxos 到 Raft，分布式一致性算法解析

来源：云加社区 - 微信公众号 [ID：QcloudCommunity]

转载：著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。