分布式一致性

引言

本文从分布式一致性问题出发，介绍了各种一致性算法，希望通过该文能让大家对分布式系统有一定的认识。更多关于分布式系统的文章均收录于<分布式系列文章>中。

分布式系统

分布式系统是一个硬件或软件组件分布在不同的网络计算机上,彼此之间仅仅通过消息传递进行通信和协调的系统。

由来

在过去的很长一段时间里，集中式的计算机系统架构一直占据主流市场，因为集中式系统一般都是依赖下层卓越的大型主机，它们的处理能力非常优秀，而且稳定性良好。但是随着互联网的普及，集中式系统越来越难以满足大型网络系统发展的需要，一来大型主机的价格也非常昂贵，而且存在单点问题。此时依赖于小型机的分布式系统应运而生，它们凭借可量化的可靠性，以及水平扩展能力，逐渐在大型互联网系统中崭露头角。

目标

分布式系统的设计目标，一般包括如下几个方面：

• 可用性:可用性是分布式系统的核心需求,其用于衡量一个分布式系统持续对外提供服务的能力。
• 可扩展性:增加机器后不会改变或极少改变系统行为,并且能获得近似线性的性能提升。
• 容错性:系统发生错误时,具有对错误进行规避以及从错误中恢复的能力。
• 性能:对外服务的响应延时和吞吐率要能满足用户的需求。

面临的问题

分布式系统虽然目标很美好，但是在实际的实现过程中，还是会面临许多问题，它们主要集中在如下几个方面：

• 通信异常：分布式系统需要在各个节点之间进行网络通信,因此每次网络通信都会伴随着网络不可用的风险，此外每一次的通信都有可能产生较大的消息延时，甚至消息丢失。
• 网络分区：网络分区和通信异常虽然都是因为网络传输出现问题，但是在分布式系统的层面却分化出两类问题。而网络分区特指那些系统分化出大小两个网络组，每个组内都能正常通讯通信，但是组间通讯被阻隔，我们将这种现象称为"脑裂"。
• 三态：分布式系统的每一次请求，可能存在三种结果，成功，失败和超时，当发生超时现象时，请求者无法判断当前请求是否成功处理。
• 节点故障：节点故障是一个非常常见的问题，指分布式系统的服务器节点可能出现宕机，僵死，器件损坏等问题。

经典理论

CAP

CAP理论告诉我们,一个分布式系统不可能同时满足一致性(C:Consistency)、可用性(A: Availability)和分区容错性(P:Partition tolerance)这三个基本需求,最多只能同时满足其中的两项。

一致性
在分布式环境中,一致性是指数据在多个副本之间是否能够保持一致的特性。如果对第一个节点的数据进行了更新操作并且更新成功后,却没有使得第二个节点上的数据得到相应的更新,于是在对第二个节点的数据进行读取操作时,获取的依然是老数据(或称为脏数据),这就是典型的分布式数据不一致情况。在分布式系统中,如果能够做到针对一个数据项的更新操作执行成功后,所有的用户都可以读取到其最新的值,那么这样的系统就被认为具有强一致性(或严格的一致性)。

可用性
可用性是指系统提供的服务必须一直处于可用的状态,对于用户的每一个操作请求总是能够在有限的时间内返回结果。

分区容错性
分布式系统在遇到任何网络分区故障的时候,仍然需要能够保证对外提供满足一致性和可用性的服务,除非是整个网络环境都发生了故障。

从 CAP 定理中我们可以看出,一个分布式系统不可能同时满足一致性、可用性和分区容错性这三个需求。另一方面,需要明确的一点是,对于一个分布式系统而言,分区容错性可以说是一个最基本的要求。因为既然是一个分布式系统,那么分布式系统中的组件必然需要被部署到不同的节点,因此必然出现子网络。而对于分布式系统而言,网络问题又是一个必定会出现的异常情况,因此分区容错性也就成为了一个分布式系统必然需要面对和解决的问题。因此系统架构设计师往往需要把精力花在如何根据业务特点在C(一致性)和A(可用性)之间寻求平衡。

BASE

BASE 是 Basically Available(基本可用)、Soft state(软状态)和 Eventually consistent(最终一致性)三个短语的简写。BASE是对CAP中一致性和可用性权衡的结果,其来源于对大规模互联网系统分布式实践的总结,是基于CAP定理逐步演化而来的,其核心思想是即使无法做到强一致性(Strong consistency),但每个应用都可以根据自身的业务特点,采用适当的方式来使系统达到最终一致性(Eventual consistency)。

基本可用
基本可用是指分布式系统在出现不可预知故障的时候,允许损失部分可用性，但这绝不等价于系统不可用。比如一个请求本来需要0.5秒返回结果，但是因为系统故障，最终花了2秒。

软状态
允许系统中的数据存在中间状态,并认为该中间状态的存在不会影响系统的整体可用性,即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

最终一致性
最终一致性强调的是系统中所有的数据副本,在经过一段时间的同步后,最终能够达到一个一致的状态。因此,最终一致性的本质是需要系统保证最终数据能够达到一致,而不需要实时保证系统数据的强一致性。

最终一致性是一种特殊的弱一致性，系统能够保证在没有其他新的更新操作的情况下,数据最终一定能够达到一致的状态,因此所有客户端对系统的数据访问都能够获取到最新的值。同时,在没有发生故障的前提下,数据达到一致状态的时间延迟,取决于网络延迟、系统负载和数据复制方案设计等因素。

一致性模型

严格一致性

严格一致性也称强一致性,原子一致性或者是可线性化(Linearizability),是要求最高的一致性模型。严格一致性的要求具体如下。

• 任何一次读都能读到某个数据的最近一次写的数据。
• 系统中的所有进程,看到的操作顺序,都与全局时钟下的顺序一致。

对于严格一致性的存储器，要求写操作在任一时刻对所有的进程都是可见的，同时还要维护一个绝对全局时间顺序 。一旦存储器中的值发生改变，那么不管读写之间的事件间隔有多小，不管是哪个进程执行了读操作，以后读出的都是新更改的值。同样，如果执行了读操作，那么不管后面的写操作有多迅速，该读操作仍应读出原来的值。

但是在分布式计算机系统中为每个操作都分配一个准确的全局时间戳是不可能实现的 。 因此，严格一致性，只是存在于理论中的一致性模型。但是，以通常的编程角度来看这个问题，每个语句的执行时刻并不重要，而读和写的顺序至关重要，我们可以通过锁来进行读写的同步，先拿到锁的操作就会被认定是先执行，反之则是后执行的。这实际上是对严格一致性的一种弱化。

顺序一致性

因为全局时钟导致严格一致性很难实现，因此顺序一致性放弃了全局时钟的约束，改为分布式逻辑时钟实现。顺序一致性是指所有的进程都以相同的顺序看到所有的修改。读操作未必能够及时得到此前其他进程对同一数据的写更新，但是每个进程读到的该数据不同值的顺序却是一致的。

图中a满足顺序一致性，但是不满足强一致性。原因在于，从全局时钟的观点来看，P2进程对变量 X 的读操作在P1进程对变量 X 的写操作之后，然而读出来的却是旧的数据。但是这个图却是满足顺序一致性的，因为两个进程P1，P2的顺序一致性并没有冲突。从这两个进程的角度来看，顺序应该是这样的: Write(y，2)→ Read(x,O)→ Write(x,4)→ Read(y,2)，每个进程内部的读写顺序都是合理的，但是显然这个顺序与全局时钟下看到的顺序并不一样。

图中b满足强一致性，因为每个读操作都读到了该变量最新写的结果，同时两个进程看到的操作顺序与全局时钟的顺序一样，都是 Write(y,2)→ Read (x,4)→ Write(x,4)→ Read(y,2)。

图中c 不满足顺序一致性，当然也就不满足强一致性。因为从进程P1的角度来看，它对变量Y的读操作返回了结果0。也就是说，P1进程的对变量Y的读操作在P2进程对变量Y的写操作之前，这意味着它认为的顺序是这样的: Write(x,4)→ Read(y,O)→ Write(y,2)→ Read(x,O)，显然这个顺序是不能满足的，因为最后一个对变量x的读操作读出来的也是旧的数据。 因此这个顺序是有冲突的，不满足顺序一致性。

因果一致性

因果一致性是指,如果进程A在更新完某个数据项后通知了进程B,那么进程B之后对该数据项的访问都应该能够获取到进程A更新后的最新值,并且如果进程B要对该数据项进行更新操作的话,务必基于进程A更新后的最新值,即不能发生丢失更新情况。与此同时,与进程A无因果关系的进程C的数据访问则没有这样的限制。

读己之所写

读己之所写是指,进程A更新一个数据项之后,它自己总是能够访问到更新过的最新值,而不会看到旧值。也就是说对于单个数据获取者来说,其读取到的数据,一定不会比自己上次写入的值旧。因此,读己之所写也可以看作是一种特殊的因果一致性。

会话一致性

会话一致性将对系统数据的访问过程框定在了一个会话当中系统能保证在同一个有效的会话中实现“读己之所写”的一致性,也就是说,执行更新操作之后,客户端能够在同一个会话中始终读取到该数据项的最新值。

单调一致性

单调读一致性是指如果一个进程从系统中读取出一个数据项的某个值后,那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。

以上就是最终一致性的五类常见的变种,在实际系统实践中,可以将其中的若干个变种互相结合起来,以构建一个具有最终一致性特性的分布式系统。

复制状态机

复制状态机的思想是一个分布式的复制状态机系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在一组状态变量中。状态机的状态能够并且只能通过外部命令来改变。

上文提到的“一组状态变量”通常是基于操作日志来实现的。每一个复制单元存储一个包含一系列指令的日志，并且严格按照顺序逐条执行日志上的指令。因为每个状态机都是确定的，所以每个外部命令都将产生相同的操作序列 (日志)。又因为每一个日志都是按照相同的顺序包含相同的指令，所以每一个服务器都将执行相同的指令序列，并且最终到达相同的状态。

综上所述，在复制状态机模型下，一致性算法的主要工作就变成了如何保证操作日志的一致性。

服务器上的一致性模块负责接收外部命令，然后追加到自己的操作日志中。它与其他服务器上的一致性模块进行通信以保证每一个服务器上的操作日志最终都以相同的顺序包含相同的指令。一旦指令被正确复制，那么每一个服务器的状态机都将按照操作日志的顺序来处理它们，然后将输出结果返回给客户端。

复制状态机之所以能够工作是基于下面这样的假设:如果一些状态机具有相同的初始状态，并且它们接收到的命令也相同，处理这些命令的顺序也相同，那么它们处理完这些命令后的状态也应该相同。因为所有的复制节点都具有相同的状态，它们都能独立地从自己的本地日志中读取信息作为输人命令，所以即使其中一些服务器发生故障，也不会影响整个集群的可用性。不论服务器集群包含多少个节点，从外部看起来都只像是单个高可用的状态机一样。

复制状态机在分布式系统中常被用于解决各种容错相关的问题，例如，GFS、HDFS、Chubby、ZooKeeper和etcd等分布式系统都是基于复制状态机模型实现的。

FLP不可能性

No completely asynchronous consensus protocol can tolerate even a single unannounced process death.

在异步通信场景下，任何一致性协议都不能保证：只有一个进程失败，其他非失败进程能达成一致。这里的“unannounced process death” 指的是一个进程发生了故障，但其他节点并不知道，继续认为这个进程还没有处理完成或发生消息延迟了。

举个例子来说，甲、乙、丙三个人各自分开进行投票(投票结果是0或1)。他们彼此可以通过电话进行沟通，但有人会睡着。 例如:甲投票0，乙投票 1，这时候甲和乙打平，丙的选票就很关键。然而丙睡着了，在他醒来之前甲和乙都将无法达成最终的结果。即使重新投票，也有可能陷入无尽的循环之中。

根据FLP定理，实际的一致性协议(Paxos、 Raft等)在理论上都是有缺陷的，最大的问题是理论上存在不可终止性!至于 Paxos 和 Raft协议在工程的实现上都做了哪些调整(例如，Paxos 和 Raft都通过随机的方式显著降低了发生算法无法终止的概率)，从而规避了理论上存在的问题，下文将会有详细的解释。

一致性算法

前文已经提到了，分布式系统都可以通过复制状态机模型来实现，而复制状态机模型又需要一致性协议来保证各个节点的日志写入顺序，所以接下来我们着重介绍一下各种一致性协议。

2PC

2PC是 Two-Phase Commit的缩写,即二阶段提交,是计算机网络尤其是在数据库领域内,为了使基于分布式系统架构下的所有节点在进行事务处理过程中能够保持原子性和一致性而设计的一种算法。通常,二阶段提交协议也被认为是一种一致性协议,用来保证分布式系统数据的一致性。目前,绝大部分的关系型数据库都是采用二阶段提交协议来完成分布式事务处理的,利用该协议能够非常方便地完成所有分布式事务参与者的协调,统一决定事务的提交或回滚,从而能够有效地保证分布式数据一致性,因此二阶段提交协议被广泛地应用在许多分布式系统中。

阶段1: 提交事务请求

• 事务询问：协调者向所有的参与者发送事务内容,询问是否可以执行事务提交操作,并开始等待各参与者的响应。
• 执行事务：各参与者节点执行事务操作,并将Undo和Redo信息记入事务日志中。
• 各参与者向协调者反馈事务询问的响应：如果参与者成功执行了事务操作,那么就反馈给协调者Yes响应,表示事务可以执行。如果参与者没有成功执行事务,那么就反馈给协调者No响应,表示事务不可以执行。

阶段2：执行事务提交

在这个阶段，协调者会根据参与者反馈来决定是否进行事务的提交。假如协调者从所有的参与者获得的反馈都是Yes响应,那么就会执行事务提交。

假如任何一个参与者向协调者反馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务。

2PC的就是将处理过程分为2个阶段，第一个阶段是投票，如果大家都觉得没问题，那么就接着往下进行，否则取消。2PC的关键是阶段1的Undo和Redo写入日志，如果之后的Commit过程失败了，可以根据事务log找到未完成的事务，然后找协调者确认该事务的最终提案，如果最终提案是Commit那么就执行Redo日志做完之前没做完的工作，如果最终提案是Rollback那么就需要执行Undo日志，撤销之前写入的内容，当处理完所有的事务日志之后，再对外提供服务，这样整个系统就达到了最终一致性。

但是，如果在协调者刚准备Commit时，发送了一个Commit请求给其中一个节点，这时候协调者和收到Commit的节点都挂了，其他节点就无法知道应当怎么做了,这时候他们会一直阻塞直到协调者恢复。而即便选取出新的协调者之后，这个新协调者也无法作出判断，因为可能存在潜在的节点已经Commit了相关内容，所以它要等所有节点都恢复之后，才能得出Commit或者Rollback的结论，而这整个过程中所有客户端都将阻塞。

3PC

3PC是 3-Phase Commit的缩写，它将原来的Commit拆分成了PreCommit和Commit两个阶段。

阶段1:CanCommit

• 事务询问：协调者向所有的参与者发送一个包含事务内容的canCommit 请求,询问是否可以执行事务提交操作,并开始等待各参与者的响应。
• 各参与者向协调者反馈事务询问的响应：参与者在接收到来自协调者的 canCommit请求后,正常情况下,如果其自身认为可以顺利执行事务,那么会反馈Yes响应,并进入预备状态,否则反馈No响应。

阶段2: PreCommit

在这个阶段，协调者会根据参与者反馈来决定是否进行事务的预提交。假如协调者从所有的参与者获得的反馈都是Yes响应,那么就会执行预提交。

• 事务预提交：参与者接收到preCommit请求后,会执行事务操作,并将Undo 和 Redo 信息记录到事务日志中。
• 各参与者向协调者反馈事务执行的响应。如果参与者成功执行了事务操作,那么就会反馈给协调者 Ack 响应,同时等待最终的指令:提交 (commit)或中止 (abort)。

假如任何一个参与者向协调者反馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务。

• 发送中断请求：协调者向所有参与者节点发出abort请求。
• 中断事务：无论是收到来自协调者的abort请求,或者是在等待协调者请求过程中出现超时,参与者都会中断事务。

阶段3：DoCommit
如果二阶段的参与者都返回了ACK，那么协调者就会给所有参与者发送DoCommit请求。

• 事务提交：参与者接收到doCommit请求后,会正式执行事务提交操作,并在完成提交之后释放在整个事务执行期间占用的事务资源。
• 反馈事务提交结果：参与者在完成事务提交之后,向协调者发送 Ack消息。
• 完成事务：协调者接收到所有参与者反馈的 Ack消息后,完成事务。

如果二阶段任意参与者返回了No或者等待超时之后，那么就会执行中断事务。

• 发送中断请求：协调者向所有的参与者节点发送abort 请求。
• 事务回滚:参与者接收到abort请求后,会利用其在阶段二中记录的Undo信息来执行事务回滚操作,并在完成回滚之后释放在整个事务执行期间占用的资源。
• 反馈事务回滚结果:参与者在完成事务回滚之后,向协调者发送Ack消息。
• 中断事务: 协调者接收到所有参与者反馈的 Ack消息后,中断事务。

看过很多人的文章，他们认为引出3PC能解决前面提到的的2PC的一致性问题，但我却看不出它是怎么解决的。如果协调者在PreCommit阶段有一个节点反馈了No，这时候协调者作出Abort的决定，并将Abort请求发送给其中一个节点A，A做完回滚操作后和协调者一起挂了，这时候新选出的协调者也没法明确之前的协调者最终作出了什么决定。新协调者只能根据当前参与者的PreCommit反馈，如果大家都返回ACK，那么协调者大胆假设之前的协调者也做出了Commit的决定，通过这样的方式3PC确实减少了2PC中的阻塞问题。3PC相对于2PC有了一个PreCommit状态作为参考，从而增大了猜对的可能性，因为正常来说，如果进入了PreCommit阶段那么所有节点都对CanCommit的决议作出了ACK的回应，那么它们对PreCommit作出ACK的回应的几率也会很大。

既然我们已经知道了3PC方案的一致性问题，那么接下来就让我们看一看去中心化的一致性算法是如何来做的吧。

Paxos

拜占庭帝国有许多支军队,不同军队的将军之间必须制订一个统一的行动计划,从而做出进攻或者撤退的决定,同时,各个将军在地理上都是被分隔开来的,只能依靠军队的通讯员来进行通讯。然而,在所有的通讯员中可能会存在叛徒,这些叛徒可以任意篡改消息,从而达到欺骗将军的目的。

这就是著名的“拜占廷将军问题”。从理论上来说,在分布式计算领域,试图在异步系统和不可靠的通道上来达到一致性状态是不可能的,因此在对一致性的研究过程中,都往往假设信道是可靠的,即消息不会被篡改，对于这类问题只需一套简单的校验算法即可避免。因此,在实际工程实践中,可以假设不存在拜占庭问题（或者说拜占庭错误）,也即假设所有消息都是完整的,没有被篡改的。那么,在这种情况下需要什么样的算法来保证一致性呢?

在古希腊有一个叫做Paxos的小岛,岛上采用议会的形式来通过法令,议会中的议员通过信使进行消息的传递。值得注意的是,议员和信使都是兼职的,他们随时有可能会离开议会厅,并且信使可能会重复的传递消息,也可能一去不复返。因此,议会协议要保证在这种情况下法令仍然能够正确的产生,并且不会出现冲突。

这就是论文The Part-Time Parliament中提到的兼职议会,而Paxos算法名称的由来也是取自论文中提到的 Paxos 小岛。

问题描述

假设有一组可以提出提案的进程集合,那么对于一个一致性算法来说需要保证以下几点:

• 在这些被提出的提案中,只有一个会被选定。
• 如果没有提案被提出,那么就不会有被选定的提案。
• 当一个提案被选定后,进程应该可以获取被选定的提案信息。

安全性需求如下:

• 只有被提出的提案才能被选定 (Chosen) 。
• 只能有一个值被选定。
• 如果某个进程认为某个提案被选定了,那么这个提案必须是真的被选定的那个。

在一致性算法中有三种角色，Proposer，Acceptor，Learner。在具体实现中，一个进程可能充当不止一种角色。由前面提到分布式系统面临的问题，我们知道：

• 每个参与者以任意的速度执行,可能会因为出错而停止,也可能会重启。同时,即使一个提案被选定后,所有的参与者也都有可能失败或重启。
• 消息在传输过程中可能会出现不可预知的延迟,也可能会重复或丢失,但是消息不会被损坏,即消息内容不会被纂改(拜占庭式的问题)。

提案的选定

要选定一个唯一提案的最简单方式莫过于只允许一个 Acceptor存在,这样的话,Proposer只能发送提案给该 Acceptor, Acceptor会选择它接收到的第一个提案作为被选定的提案。这种解决方式尽管实现起来非常简单,但是却很难让人满意,因为一旦这个Acceptor出现问题,那么整个系统就无法工作了。

因此,应该寻找一种更好的解决方式,在存在多个 Acceptor的情况下,如何进行提案的选取:Proposer向一个Acceptor集合发送提案,集合中的每个 Acceptor都可能会批准(Accept)该提案,当有足够多的Acceptor批准这个提案的时候,我们就可以认为该提案被通过。那么怎么来定义足够多呢？我们假定足够多的Acceptor是所有Acceptor集合的一个子集，并且让这个子集大到可能包含Acceptor集合的大多数成员，这样一来任意两个包含大多数Acceptor的集合必然会有至少一个公共成员。另外我们规定每个Acceptor最多只能批准一个提案，这样，在一轮提议中，就只会有一个提案被选定。

推导过程
如果我们规定拿到大多数Acceptor的投票后就算提案被选中，并且我们希望每轮只有一个提案被选中，最简单的一个约定就是：
P1：一个Acceptor必须批准它收到的第一个提案

但是只有这一层保证会有一个问题，多个提案被不同的Acceptor批准，但是每个人提案都没有获得大多数的选票。

因为我们希望每轮的提案都能选出一个结果，而不是轮空，那么我们就需要加入一些别的约束。首先，我们要放开一个Acceptor只能批准一个提案的约束，然后我们引入一个全局唯一编号的机制，生成这个全局唯一编号的方法不是我们关注的重点。有了这个编号之后，我们的提案就变成【编号，Value】这样的一对组合了。

根据上面的内容，现在我们的Acceptor可以允许多个提案了，但是我们必须要保证，所有被接受的提案最终会具有相同的Value。那么我们就简单地约定编号越小优先级越高，那么在一轮选举中，编号最小的提案如果被选中了，那么其对应的Value，将成为最终选举结果。该约定可以定义如下：
`
P2:如果编号为M0，Value值为V0,的提案(即[M0,V0])被选定了,那么如果这一轮选举中最终选定的提案编号Mn比M0更高的的话,那么该提案Mn其Value值必须也是V0。
`
在P2的基础上，我们知道一个提案如果要被选定，就必须被至少一个Acceptor批准，因此我们的P2可以转化为如下形式：
`
P2a:如果编号为M0，Value值为V0,的提案(即[M0,V0])被选定了,那么如果这一轮选举中被Acceptor批准的提案编号Mn比M0更高的的话,那么该提案Mn其Value值必须也是V0。
`
因为通信是异步的，一个提案可能会在某个Acceptor没收到任何其他提案时就被选中，如下图：

如图所示,在 Acceptor1没有收到任何提案的情况下,其他4个 Acceptor 已经批准了来自Proposer2的提案【M0,V0】,而此时,Proposer1产生了一个具有其他 Value 值的编号更高的提案【M1,V1】,并发送给了 Acceptor1。根据P1,就需要 Acceptor1批准该提案,但是这与P2a矛盾,因此如果要同时满足P1和P2a,需要对P2a进行如下强化:
`
P2b:如果一个提案[M0,V0],被选定后,那么之后任何Proposer产生的编号更高的提案,其 Value 值都为V0。
`
我们假设编号为M0，value为V0的提案已经被选定了,这就意味着肯定存在一个由半数以上的 Acceptor组成的集合C,C中的每个Acceptor都批准了该提案。

因为任何包含半数以上 Acceptor的集合S都至少包含C中的一个成员,因此我们可以认为如果保证如下约定,那么编号为Mn,的提案的 Value也为 V0。

P2c:对于任意的Mn和Vn,如果提案[Mn,Vn]被提出,那么肯定存在一个由半数以上的Acceptor组成的集合S,满足以下两个条件中的任意一个。
- S中不存在任何批准过编号小于Mn的提案的 Acceptor。
- 选取S中所有Acceptor批准的编号小于M的提案,其中编号最大的那个提案其 Value值是V。

Proposer生成提案

Proposer选择一个新的提案编号Mn,然后向某个Acceptor集合的成员发送请求,要求该集合中的 Acceptor 做出如下回应。

• 向Proposer承诺,保证不再批准任何编号小于Mn的提案。
• 如果 Acceptor已经批准过任何提案,那么其就向Proposer反馈当前该Acceptor已经批准的编号小于Mn,但为最大编号的那个提案的值。

我们将该请求称为编号为Mn的提案的Prepare请求。如果Proposer收到了来自半数以上的 Acceptor的响应结果,那么它就可以产生编号为Mn,Value值为Vn的提案,这里的Vn是所有响应中编号最大的提案的 Value值。当然还存在另一种情况,就是半数以上的 Acceptor都没有批准过任何提案,即响应中不包含任何的提案,那么此时Vn值就可以由Proposer 任意决定。

换个通俗一点的说法，如果只有一个Proposer发出提案【M0，V0】，那么所有Acceptor都会接受它的提案，那么最终被选定的提案就是【M0，V0】，但是如果有两个并发的提案【M0，V0】，【M1，V1】，如果M0先被AcceptorA批准了，AcceptorA会记录下V0，之后它收到了M1的提案，它会告诉M1提案的Proposer自己已经接受了【M0，V0】,最后M1的Proposer会将自己的提案改成【M1，V0】。因为任意两个半数以上的Acceptor集合必然有至少一个公共Acceptor，所以在每一轮投票中，M1提案的Proposer必然会感知到M0提案的存在。

从上图中，我们就能看到【M1，V1】最终是如何变成【M1，V0】的。图中P代表Prepare请求，A代表Accept请求，M0=3.1，M1=4.5，V0=X，V1=Y，首先M0的prepare请求先到达了s1，s2，s3，这时候已经达到了半数以上的人接受，所以它将X的值发送给了s1，s2，s3，这时候我们称【M0，V0】已经被批准，而这时候M1提案被提出，M1想要通过必然会有和之前的提案M0有一个公共Acceptor，就是图中的s3。因为s3已经批准了【M0=3.1，V0=X】，他就将V0=X的信息发送给了M1的Proposer，该Proposer为了让系统的一致性得到保证，就将最初要提议的V1=Y改成了V1=X。最后的结果，就如大家看到的一样，整个系统达到一致的状态，即X成为本轮提案的最终选中Value。

Acceptor批准提案

根据上面的内容,一个Acceptor可能会收到来自Proposer的两种请求,分别是Prepare请求和Accept请求,对这两类请求做出响应的条件分别如下：

• Prepare请求:Acceptor可以在任何时候响应一个Prepare请求，但是如果接受了一个Mn的prepare请求，那么它再也不会接受小于Mn的Prepare请求。
• Accept请求:Acceptor可以在任何时候响应 Accept请求，但是只有在尚未响应任意大于Mn的prepare请求的情况下，它才可以接受Mn的提案。

前面的例子已经介绍了【M0，V0】先被接受然后【M1，V1】最终变成【M1，V0】的过程。接下来会介绍一下因为【M1，V1】先被接受【M0，V0】被拒的过程。

和上图一样，P代表Prepare请求，A代表Accept请求，M0=3.1，M1=4.5，V0=X，V1=Y。这里s3在收到M0的Accept请求之前先收到了M1的prepare请求，所以他最终会拒绝V0=3.1，而是接受了V1=Y，最终【M1=4.5，V1=Y】得到了大多数Acceptor的批准成为了最终提案。图中虽然已经s1，s2接受了【M0=3.1，V0=X】的提案，但是该提案并没有得到大多数Acceptor的认可，也就是说这轮选举只有【M1=4.5，V1=Y】一个提案胜出，最终s1，s2会在接收到M1的Accept请求后将Value改成V1=Y，整个系统达到最终一致性。

Learner获取提案

在一个提案被半数以上Acceptor批准以后，就需要将提案的内容分发给所有Learner，如果让Acceptor和每个Learner进行通信，那么通信次数就是两者个数的乘积就很大，如果在Learner中选举一位Master，Acceptor只和Learner Master通讯，有可能存在单点问题，所以一般都是让Acceptor和一部分Learner通讯，然后这些Learner再将消息传播开来。

并发分析

看到这，我觉得大家可能还会有一些疑问，觉得如果超过两个并发的提案是不是可能造成一致性无法达成。下面我们以同一时刻的3个提案【M0，V0】，【M1，V1】，【M2，V2】作为例子，这里我们不考虑prepare请求被拒绝的情况，因为如果prepare未达半数时不会发送Accept请求，所以该情况不会对一致性产生影响。

上图中，M0=3.1，M1=4.5，M2=5.1，V0，V1，V2分别为X，Y，Z，我们先假设M0=3.1的prepare请求先被多数节点接受，这时候M1=4.5的也被多数节点接受，因为它们存在公共Acceptor s3，所以M0与M1的冲突会根据M0=3.1的Accept请求与M1=4.5的prepare请求的到达顺序决定，如果M0的Accept请求先于M1的prepare到达，那么M1的值最终会改成V0=X，否则M1的值会依旧保持自己的值V1=Y。

然后让我们再来看M2，他会和M0的支持者以及M1的支持者都有至少一个公共Acceptor，我们就拿图中s2和s3为例。

• 如果M0的Accept请求A3.1X先于M2的Prepare请求P5.1到达S2，并且M1的Accept请求A4.5？先于M2的Prepare请求P5.1到达s3：M2的Proposer会取最大编号M1的值？(取决于A3.1是否先于P4.5到达s3)作为自己的Value。
• 如果M0的Accept请求A3.1X后于M2的Prepare请求P5.1到达S2，并且M1的Accept请求A4.5？先于M2的Prepare请求P5.1到达s3：M2的Proposer会取最大编号M1的值？(取决于A3.1是否先于P4.5到达s3)作为自己的Value。
• 如果M0的Accept请求A3.1X先于M2的Prepare请求P5.1到达S2，并且M1的Accept请求A4.5？后于M2的Prepare请求P5.1到达s3：M2的Proposer会取最大编号M0的值X作为自己的Value。
• 如果M0的Accept请求A3.1X后于M2的Prepare请求P5.1到达S2，并且M1的Accept请求A4.5？后于M2的Prepare请求P5.1到达s3：M2的Proposer会使用自己的原始Value=Z。

从上面的例子我们看出，即便存在大量的并发，也会通过如果 Acceptor已经批准过任何提案,那么其就向Proposer反馈当前该Acceptor已经批准的编号小于Mn,但为最大编号的那个提案的值。这条准则来化解，因为任意两个多数派都会有一个公共Acceptor，他们就是通过这个关键的Acceptor来交换信息，最终让结果趋于一致。

活锁问题

看到这大家可能还有一个问题，如果有两个并发提案，但是它们的Accept请求总是慢了一步，让另一个提案的Prepare先到了，就会陷入不断发送Prepare请求的循环中无法解脱，这就是前面提到的的FLP问题。下图就是Paxos发生FLP问题时的例子：

从图中我们可以看到P3.1的Accept请求慢于P3.5的prepare请求，导致自己的提案被驳回，于是它又重新发起新的一轮提案P4.1，而P4.1又恰好先于P3.5的Accept请求，所以A3.5被驳回，又发起了P5.5提案。他们会无休止地循环下去，直到某一方的Accept请求先传输给多数Acceptor。

Multi-Paxos

原始的Paxos算法（Basic Paxos）只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos 就效率很低。因此Basic Paxos几乎只是用来做理论研究，并不直接应用在实际工程中。

实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos正是为解决此问题而提出。Multi-Paxos基于Basic Paxos做了改进：

• 在所有Proposers中选举一个Leader，由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

Multi-Paxos首先需要选举Leader，Leader的确定也是一次决议的形成，所以可执行一次Basic Paxos来选举出一个Leader。选出Leader之后只能由Leader提交Proposal，在Leader宕机之后服务临时不可用，需要重新选举Leader继续服务。在系统中仅有一个Leader进行Proposal提交的情况下，Prepare阶段可以跳过。

Multi-Paxos通过改变Prepare阶段的作用范围，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。

Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性，这样的场景即退化为Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的变形。

Raft

Paxos算法向来以难以理解，难以实现而闻名。而接下来要说的Raft算法则以容易理解，容易实现作为设计目标来解决一致性问题。尽可能地将问题分解成为若干个可解决的、更容易理解的小问题，这是众所周知的简化问题的方法论。Raft算法把问题分解成了领袖选举(leader election)、日志复制(log replication)、安全性(safety)和成员关系变化(membership changes)这几个子问题。

• 领袖选举:在一个领袖节点发生故障之后必须重新给出一个新的领袖节点。
• 日志复制:领袖节点从客户端接收操作请求,然后将操作日志复制到集群中的其他服务器上,并且强制要求其他服务器的日志必须和自己的保持一致。
• 安全性:Raft关键的安全特性是下文提到的状态机安全原则(StateMachine Safety)。如果一个服务器已经将给定索引位置的日志条目应用到状态机中,则所有其他服务器不会在该索引位置应用不同的条目。下文将会证明Raft是如何保证这条原则的。
• 成员关系变化:配置发生变化的时候,集群能够继续工作。

Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

• Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
• Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
• Candidate：Leader选举过程中的临时角色。

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。当请求发送给leader后，leader保证该请求修改的内容已经在大多数节点修改完成后，再回复请求方。

众所周知，分布式环境下的“时间同步”是一个大难题，但是有时为了识别“过期信息”，时间信息又是必不可少的。于是，任期在Raft中起着逻辑时钟的作用，同时也可用于在Raft节点中检测过期信息，比如过期的领导人。Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

每个Raft节点各自都在本地维护一个当前任期值，触发这个数字变化(增加) 主要有两个场景:开始选举和与其他节点交换信息。当节点之间进行通信时，会相互交换当前的任期号。如果一个节点(包括领导人)的当前任期号比其他节点的任期号小，则将自己本地的任期号自觉地更新为较大的任期号。 如果一个候选人或者领导人意识到它的任期号过时了(比别人的小)，那么它会立刻切换回群众状态;如果一个节点收到的请求所携带的任期号是过时的，那么该节点就会拒绝响应本次请求。

选举Leader

Raft集群三类角色的有限状态机如上图所示，其中有一个“times out”(超时)条件，这是触发有限状态自动机发生状态迁移的一个重要条件。在 Raft的选举中，有两个概念非常重要:心跳和选举定时器。每个Raft节点都有一个选举定时器，所有的Raft节点最开始以Follower角色运行时都会启动这个选举定时器。

Leader在任期内必须定期向集群内的其他节点广播心跳包，昭告自己的存在。Follower每次收到心跳包后就会主动将自己的选举定时器清零重置(reset)。 因此如果Follower选举定时器超时，则意味着在Raft规定的一个选举超时时间周期内，Leader的心跳包并没有发给 Follower (或者已经发送了但在网络传输过程中发生了延迟或被丢弃了)，于是Follower就假定Leader已经不存在或者发生了故障，于是会发起一次新的选举。

如果决定要参加选举，会按照如下步骤操作：

1. 将自己本地维护的当前任期号(current term id)加1。
2. 将自己的状态切换到候选人(Candidate)，并为自己投票。也就是说每个候选人的第一张选票来自于他自己。
3. 向其所在集群中的其他节点发送RequestVote RPC(RPC消息会携带“current term id”值)，要求它们投票给自己。

接下来我们看一下可能发生的情况：

1. 收到大多数Follower的投票，赢得选举。在一个任期内一个节点最多只为一个候选人投票，它会投给最早来拉选票的人。如果某个候选人赢得了选举，它就会开始发送心跳包。
2. 拉票过程中收到其他Leader的心跳包。如果心跳包中的任期号比自己本地地大，就承认其合法性，并放弃选举。如果不合法则拒绝该心跳包，并告诉他当前最新的任期号，这能让该领导人意识到自己已经过时了。
3. 多个候选人均未得到超过半数的选票，他们会重新发起下一轮选举。但是这就会出现前面提到的FLP问题，为了避免这种问题，Raft采用了一种随机延时重试的方式。例如每个节点等待100-300ms后再开始下一轮拉票。通过这种方式，FLP问题发生的可能性会快速收敛并接近为0。

日志同步

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

某些Followers可能没有成功的复制日志，Leader会无限的重试 AppendEntries RPC直到所有的Followers最终存储了所有的日志条目。

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。

Raft日志同步保证如下两点：

• 如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
• 如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。

第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。

第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时，Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志，它就会拒绝新的日志条目。

一般情况下，Leader和Followers的日志保持一致，因此 AppendEntries 一致性检查通常不会失败。然而，Leader崩溃可能会导致日志不一致：旧的Leader可能没有完全复制完日志中的所有条目。

上图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目，也有可能包含一些Leader没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

Leader通过强制Followers复制它的日志来处理日志的不一致，Followers上的不一致的日志会被Leader的日志覆盖。

Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。

Leader会从后往前试，每次AppendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。

安全性

Raft增加了如下两条限制以保证安全性：

• 拥有最新的已提交的log entry的Follower才有资格成为Leader。RequestVote RPC中携带last term和log index，term和log index越大的才会成为Leader。
• Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交（log index 小于 commit index的日志被间接提交）。

之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况：

在阶段a，term为2，S1是Leader，且S1写入日志（term, index）为(2, 2)，并且日志被同步写入了S2。

在阶段b，S1离线，触发一次新的选主，此时S5被选为新的Leader，此时系统term为3，且写入了日志（term, index）为（3， 2）。

S5尚未将日志推送到Followers就离线了，进而触发了一次新的选主，而之前离线的S1经过重新上线后被选中变成Leader，此时系统term为4，此时S1会将自己的日志同步到Followers，按照上图就是将日志（2， 2）同步到了S3，而此时由于该日志已经被同步到了多数节点（S1, S2, S3），因此，此时日志（2，2）可以被提交了。

在阶段d，S1又下线了，触发一次选主，而S5有可能被选为新的Leader（这是因为S5可以满足作为主的一切条件：1. term = 5 > 4，2. 最新的日志为（3，2），比大多数节点（如S2/S3/S4的日志都新），然后S5会将自己的日志更新到Followers，于是S2、S3中已经被提交的日志（2，2）被截断了。

增加上述限制后，即使日志（2，2）已经被大多数节点（S1、S2、S3）确认了，但是它不能被提交，因为它是来自之前term（2）的日志，直到S1在当前term（4）产生的日志（4， 4）被大多数Followers确认，S1方可提交日志（4，4）这条日志，当然，根据Raft定义，（4，4）之前的所有日志也会被提交。此时即使S1再下线，重新选主时S5不可能成为Leader，因为它没有包含大多数节点已经拥有的日志（4，4）。

日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot。

Snapshot中包含以下内容：

• 日志元数据。最后一条已提交的 log entry的 log index和term。这两个值在snapshot之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。
• 系统当前状态。

当Leader要发给某个日志落后太多的Follower的log entry被丢弃，Leader会将snapshot发给Follower。或者当新加进一台机器时，也会发送snapshot给它。发送snapshot使用InstalledSnapshot RPC。

做snapshot既不要做的太频繁，否则消耗磁盘带宽，也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次snapshot。

做一次snapshot可能耗时过长，会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步。

成员变更

成员变更是在集群运行过程中副本发生变化，如增加/减少副本数、节点替换等。

成员变更也是一个分布式一致性问题，既所有服务器对新成员达成一致。但是成员变更又有其特殊性，因为在成员变更的一致性达成的过程中，参与投票的进程会发生变化。

如果将成员变更当成一般的一致性问题，直接向Leader发送成员变更请求，Leader复制成员变更日志，达成多数派之后提交，各服务器提交成员变更日志后从旧成员配置（Cold）切换到新成员配置（Cnew）。

因为各个服务器提交成员变更日志的时刻可能不同，造成各个服务器从旧成员配置（Cold）切换到新成员配置（Cnew）的时刻不同。

成员变更不能影响服务的可用性，但是成员变更过程的某一时刻，可能出现在Cold和Cnew中同时存在两个不相交的多数派，进而可能选出两个Leader，形成不同的决议，破坏安全性。

为了解决这一问题，Raft提出了两阶段的成员变更方法。集群先从旧成员配置Cold切换到一个过渡成员配置，称为共同一致（joint consensus），共同一致是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew，一旦共同一致Cold U Cnew被提交，系统再切换到新成员配置Cnew。

Raft两阶段成员变更过程如下：

• Leader收到成员变更请求从Cold切成Cnew。
• Leader在本地生成一个新的log entry，其内容是Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该log entry复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认。
• Follower收到Cold∪Cnew的log entry后更新本地日志，并且此时就以该配置作为自己的成员配置。
• 如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，Leader就提交这条log entry。
• 接下来Leader生成一条新的log entry，其内容是新成员配置Cnew，同样将该log entry写入本地日志，同时复制到Follower上。
• Follower收到新成员配置Cnew后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在Cnew这个成员配置中会自动退出。
• Leader收到Cnew的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功。

异常分析：

• 如果Leader的Cold U Cnew尚未推送到Follower，Leader就挂了，此后选出的新Leader并不包含这条日志，此时新Leader依然使用Cold作为自己的成员配置。
• 如果Leader的Cold U Cnew推送到大部分的Follower后就挂了，此后选出的新Leader可能是Cold也可能是Cnew中的某个Follower。
• 如果Leader在推送Cnew配置的过程中挂了，那么同样，新选出来的Leader可能是Cold也可能是Cnew中的某一个，此后客户端继续执行一次改变配置的命令即可。
• 如果大多数的Follower确认了Cnew这个消息后，那么接下来即使Leader挂了，新选出来的Leader肯定位于Cnew中。

两阶段成员变更比较通用且容易理解，但是实现比较复杂，同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性，因此我们期望增强成员变更的限制，以简化操作流程。

两阶段成员变更，之所以分为两个阶段，是因为对Cold与Cnew的关系没有做任何假设，为了避免Cold和Cnew各自形成不相交的多数派选出两个Leader，才引入了两阶段方案。

如果增强成员变更的限制，假设Cold与Cnew任意的多数派交集不为空，这两个成员配置就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。

那么如何限制Cold与Cnew，使之任意的多数派交集不为空呢？方法就是每次成员变更只允许增加或删除一个成员。

可从数学上严格证明，只要每次只允许增加或删除一个成员，Cold与Cnew不可能形成两个不相交的多数派。

一阶段成员变更：

• 成员变更限制每次只能增加或删除一个成员（如果要变更多个成员，连续变更多次）。
• 成员变更由Leader发起，Cnew得到多数派确认后，返回客户端成员变更成功。
• 一次成员变更成功前不允许开始下一次成员变更，因此新任Leader在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。
• Leader只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步。

可用性与时序

领导人选取是Raft算法中对时序要求最多的地方。只有当系统环境满足以下时序要求时，Raft算法才能选举并且保持一个稳定的领导人存在:

broadcastTime << electionTimeout << MTBF

在以上不等式中，broadcastTime指的是一个节点向集群中其他节点发送RPC，并且收到它们响应的平均时间，electionTimeout就是在上文中多次出现的选举超时时间，MTBF指的是单个节点发生故障的平均时间间隔。为了使领导人能够持续发送心跳包来阻止下面的Follower发起选举，broadcastTime应该比electionTimeout小一 个数量级。根据已经给出的随机化选举超时时间方法，这个不等式也显著降低了候选人平分选票的概率。为了使得系统稳定运行，electionTimeout也应该比MTBF小几个数量级。当领导人出现故障且在新的领导人选举出来之前，系统对外将会不可用，这个时长大约为electionTimeout。

文章说明

更多有价值的文章均收录于贝贝猫的文章目录

版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

创作声明： 本文基于下列所有参考内容进行创作，其中可能涉及复制、修改或者转换，图片均来自网络，如有侵权请联系我，我会第一时间进行删除。

参考内容

[1]《云原生分布式存储基石 etcd深入解析》
[2]《从Paxos到ZooKeeper 分布式一致性原理与实践》
[3] 漫话分布式系统共识协议: 2PC/3PC篇
[4] Paxos算法详解
[5] Raft算法详解