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

导语 | 后台服务架构经过了集中式、SOA、微服务和服务网格四个阶段，目前互联网界大都使用微服务和服务网格。服务从集中式、中心化向分布式、去中心化不断演进，服务也变得更灵活，能够自动扩缩容、快速版本迭代等。但是分布式架构也将集中式下一些问题放大，比如通信故障、请求三态（成功、失败、超时）、节点故障等，这些问题会导致一系例数据不一致的问题，也是计算机领域的老大难问题。本文将与大家一起学习分布式一致性算法，因作者水平有限，若文中有不正处，还请多多指导。文章作者：董友康，腾讯PCG研发工程师。

一、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）：

如果要保证C(一致性)，那么它需要把消息复制到所有节点，但是网络分区导致无法成功复制到n3~n5，所以它只能返回"处理失败"的结果给客户端。（这时系统就处于不可用状态，即丧失了A）
如果要保证可用性A，那么n1就只能把消息复制到n2，而不用复制到n3~n5(或者无视复制失败/超时)，但n3同时也可能在处理客户端请求，n3也为了保证A而做了同样的处理。那么 [n1、n2]和[n3~n5]的状态就不一致了，于是就丧失了C(一致性)。
如果不容忍网络分区，则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（准备阶段）：

Proposer向超过半数（n/2 1）Acceptor发起prepare消息(发送编号)；
如果Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer，同时该Acceptor 承诺不再接受任何编号小于 N 的提案。否则拒绝返回。

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

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