分布式一致性几种算法介绍

在分布式系统CAP理论解析中提到，分布式一致性算法为了使基于分布式系统架构下的所有节点进行事务处理过程中能够保持原子性和一致性而设计的一种算法。本文介绍几种常用的一致性算法，包括2PC、3PC、共识算法Paxos、基于日志的复制算法Raft、Zookeeper的Zab协议等。

1、二阶段提交2PC

二阶段提交2PC是一致性协议算法，可以保证数据的强一致性，该算法能够解决很多临时性系统故障（包括进程、网络节点、通信等故障），被广泛地使用于关系型数据库系统中。

1.1 二阶段提交过程

2PC协议中系统分为协调者和参与者，整个过程分为两个阶段：

1） 阶段1：Prepare请求阶段

在请求阶段，协调者向事务的参与者发起执行操作的CanCommit请求，通知事务参与者准备提交或取消事务，并等待参与者的响应；
参与者接到请求后，执行请求中的事务操作，记录undo/redo日志信息，同时锁定当前记录
参与者反馈事务的执行结果，如果执行成功则返回YES，如果执行失败则返回NO
当所有的参与者返回操作结果后，系统进入提交阶段

2） 阶段2：Commit提交阶段

协调者会根据所有参与者返回的信息向参与者发送DoCommit或DoAbort指令
当且仅当所有的参与者返回YES时协调者向所有的参与者发送DoCommit消息提交事务，否则协调者将向所有的参与者发送DoAbort取消事务。此时发送“Yes”的参与者则会根据回滚日志对之前操作进行回滚
参与者在接收到协调者发来的消息后向协调者发送“HaveCommitted”消息
协调者接收到“HaveCommitted”消息，就意味着整个事务结束

1.2 如何应对超时

事务协调者等待参与者返回响应超时

此时协调者没有发送任何commit指令，可以安全的发起abort指令放弃commit，因此可以说协调者采取了非常保守的方案

参与者等待协调者发送commit/abort指令超时

如果B之前回复的是NO，此时无需等待协调者回复就可以之间abort操作，因为即使收到协调者响应也是abort操作
如果B之前回复的是YES，此时B就不能单方面的执行abort操作或commit操作，因为如果A接收到协调者发送的commit操作但是B超时没有收到，B进行abort后就会出现数据不一致；如果B执行commit但是A返回给协调者的是NO，也是存在问题的
出现这种问题，就需要更优化的一致性算法，也就是3PC

1.3 2PC缺点

2PC协议的优点是原理简单、实现方便，但也有以下缺点：

同步阻塞：在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，也就是说，各个参与者在等待其他参与者响应的过程中，将无法进行其他任何操作。
单点问题：协调者的角色在整个二阶段提交协议中起到了非常重要的作用。一旦协调者出现问题，那么整个二阶段提交流程将无法运转，更为严重的是，如果协调者是在阶段二中出现问题的话，那么其他参与者将会一直处于锁定事务资源的状态中，而无法继续完成事务操作。
数据不一致：在阶段二时，当协调者向所有的参与者发送Commit请求之后，发生了局部网络异常或者是协调者尚未发送完Commit请求之前自身发生了崩溃，导致最终只有部分参与者收到了Commit请求。于是，这部分收到了Commit请求的参与者就会进行事务的提交，而其他没有收到Commit请求的参与者则无法进行事务提交，于是整个分布式系统便出现了数据不一致现象。
二阶段无法解决的问题：协调者在发出DoCommit 消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

2、三阶段提交3PC

为了解决2PC过程中同步阻塞和数据不一致的问题，3PC协议在协调者和参与者中都引入超时机制，并且把两阶段提交协议的第一个阶段拆分成了两步：询问，然后再锁资源，最后真正提交，包括CanCommit、PreCommit和doCommit三个阶段。

2.1 3PC提交过程

1）CanCommit阶段

3PC的CanCommit阶段和2PC的准备阶段很像。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。

2）PreCommit阶段

协调者根据参与者的反应情况来决定是否可以继续事务的PreCommit操作。根据响应情况，有以下两种可能。

假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会进行事务的预执行：

发送预提交请求。协调者向参与者发送PreCommit请求，并进入Prepared阶段。
事务预提交。参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
响应反馈。如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。

假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就中断事务：

发送中断请求。协调者向所有参与者发送abort请求。
中断事务。参与者收到来自协调者的abort请求之后（或超时之后，仍未收到Cohort的请求），执行事务的中断。

3）DoCommit阶段

该阶段进行真正的事务提交，也可以分为以下两种情况:

执行提交

发送提交请求。协调者接收到参与者发送的ACK响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
事务提交。参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
响应反馈。事务提交完之后，向协调者发送ACK响应。
完成事务。协调者接收到所有参与者的ACK响应之后，完成事务。

中断事务

协调者没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。

2.2 3PC优缺点

3PC优点：

降低了二阶段的同步阻塞范围（在第二阶段，只要参与者收到preCommit请求，就会执行事务，此后，不管能不能收到协调者的doCommit请求,都会执行事务提交，不会出现阻塞问题）
解决单点问题：进入阶段三会出现两种情况：1：协调者出现问题；2：协调者与参与者之间出现网络故障；都导致参与者无法收到doCommit请求，但参与者在超时之后都会提交事务

3PC缺点：

数据不一致：参与者收到preCommit请求，此时如果出现网络分区，协调者与参与者之间无法进行正常网络通信，参与者在超时之后还是会进行事务提交，就会出现数据不一致。

3、共识算法Paxos

Paxos由莱斯利•兰伯特(Leslie Lamport)于1998年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛Paxos，描述了Paxos小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在2001年，莱斯利•兰伯特重新发表了朴实的算法描述版本《Paxos Made Simple》

Paxos算法解决的问题是在一个可能发生消息可能会延迟、丢失、重复的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

3.1 Paxos算法中的角色

Paxos算法中存在5种角色：client、acceptor、proposer、learner和leader，但在实际的实现中，一个服务可能同时扮演一个或者多个角色。

Client（客户端）：是指请求的发起端，Client发送请求给分布式系统，并等待回复。
Acceptor (决策者)：Acceptor可以接受提案并进行投票，投票结果是否通过以多数派为准。Acceptor可以看做是消息请求的存储器，一般来说Acceptors是由一定数量的服务组成的，当消息被发送给Acceptor，只有大部分Acceptor确认接收此消息，该消息才会被存储，否则该消息将被丢弃。
Proposer（提案发起者）：可以看做Client的代理人，Proposer将Client的消息请求发送给Acceptors，并等待Acceptors的确认。在发生消息冲突时，Proposer充当协调者尝试解决冲突。
Learner：Learners可以看做是所有被确认消息的执行器，一旦有Client的消息请求被Acceptors确认之后，Learners会做相应的处理（如：执行消息内容，发送回复给Client）。Learner可以有多个，不参与投票。
Leader：Paxos需要一个Leader来确保分布式系统可以按步骤进行下去。这里的Leader其实就是一个Proposer，Paxos协议会确保只有一个Proposer会被当做Leader。

3.2 Paxos算法过程

1）阶段1A：Prepare

在Prepare阶段，一个Proposer会创建一个Prepare消息，每个Prepare消息都有唯一的提案编号n。n并不是将要提案的内容，而只是一个唯一的编号，用来标志这个Prepare的消息。n必须比该Proposer之前用过的所有编号都大，一般来说我们可以以数字递增的方式来实现这个编号。接下来Proposer会把该编号发送给Acceptors，只有大多数Acceptors接收到Proposer发来的消息，该消息才算是发送成功。

2）阶段1B：Promise

当一个Acceptor收到从Proposer发过来的Prepare消息时候，会有两种情况：

如果一个Acceptor收到一个编号为N的Prepare请求，如果小于它已经响应过的请求，则拒绝，不回应或回复error。
若N大于该Acceptor已经响应过的所有Prepare请求的编号（maxN），那么它就会将它已经接受过（已经经过第二阶段accept的提案）的编号最大的提案（如果有的话，如果还没有的accept提案的话返回{pok，null，null}）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。

3）阶段2A：Accept

如果一个Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value（某个acceptor响应的它已经通过的{acceptN，acceptV}），如果响应中不包含任何提案，那么V就由Proposer自己决定

4）阶段2B：Accepted

如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。如果N小于Acceptor以及响应的prepare请求，则拒绝，不回应或回复error（当proposer没有收到过半的回应，那么他会重新进入第一阶段，递增提案号，重新提出prepare请求）

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

3.3 Paxos算法处理流程

3.3.1 正常处理流程

客户端发起request请求到Proposer，然后Proposer发出提案并携带提案的编号1，分别发给每一个Acceptor；每一个Acceptor根据编号是否满足大于1，将投票结果通过Propose阶段反馈给Proposer；Proposer收到Acceptor的结果判断是否达到了多数派，达到了多数派则向Acceptor发出Accept请求，并携带提案的具体内容V；Acceptor收到提案内容后向Proposer反馈Accepted表示收到，并将提案内容交给Learner进行备份。

#1：Prepare(N=1)
#2：if(1>0) Promise(1,(Va,Vb,Vc))
#3：Accept(N=1,V=1)
#4：Accepted(N=1,V=1)

3.3.2 Acceptor失败情况

虽然Accetor3出现异常，没有向Proposer反馈，但是Proposer此时收到的接受提案的反馈有2个Acceptor，仍然满足多数派的情况，此时仍然能够将提案内容继续写入的，所以后续的Accept的发送只需要发送给剩下的两个Acceptor即可。

#1：Prepare(N=1)
#2：if(1>0) Promise(1,(Va,Vb,null))
#3：Accept(N=1,V=1)
#4：Accepted(N=1,V=1)

3.3.3 Proposer失败情况

Proposer失败的话表示收到Acceptor的Propose请求之后无法继续发送Accept请求，这个时候集群会重新选出另一个新的能够工作的Proposer，再从prepare阶段开始处理，同时Prepare的提案版本号会增加一个，但是提案的内容还是之前的内容。

3.4 Multi-paxos

Basic Paxos首先流程上复杂,实现极其困难，其次效率低(达成一致性需要2轮RPC调用)，引入了Multi-Paxos进行优化改进。Multi-Paxos是针对basic Paxos流程进行拆分为选举和复制的过程，第一次发起投票流程在所有的Acceptor中确定一个Leader，第二次发起投票流程直接由Leader确认。

4、基于日志复制算法Raft

4.1 Raft中角色

Raft协议一共包含如下3类角色：

Leader（领袖）：领袖由群众投票选举得出，每次选举，只能选出一名领袖；Leader负责发送心跳、管理日志复制与提交
Candidate（候选人）：当没有领袖时，某些群众可以成为候选人，然后去竞争领袖的位置；主动发起并参与选举
Follower（群众）：被动响应其他节点发送过来的请求

Raft算法由leader节点来处理一致性问题。leader节点接收来自客户端的请求日志数据，然后同步到集群中其它节点进行复制，当日志已经同步到超过半数以上节点的时候，leader节点再通知集群中其它节点哪些日志已经被复制成功，可以提交到raft状态机中执行。

4.2 Raft状态变化

节点的状态切换状态机如图所示，图中标记了状态切换的6种路径，下面做一个简单介绍

start up：起始状态，节点刚启动的时候自动进入的是follower状态。
times out, starts election：follower在启动之后，将开启一个选举超时的定时器，当这个定时器到期时，将切换到candidate状态发起选举。
times out, new election：进入candidate 状态之后就开始进行选举，但是如果在下一次选举超时到来之前，都还没有选出一个新的leade，那么还会保持在candidate状态重新开始一次新的选举。
receives votes from majority of servers：当candidate状态的节点，收到了超过半数的节点选票，那么将切换状态成为新的leader。
discovers current leader or new term：candidate状态的节点，如果收到了来自leader的消息，或者更高任期号的消息，都表示已经有leader了，将切换回到follower状态。
discovers server with higher term：leader状态下如果收到来自更高任期号的消息，将切换到follower状态。这种情况大多数发生在有网络分区的状态下。

如果一个candidate在一次选举中赢得leader，那么这个节点将在这个任期中担任leader的角色。但并不是每个任期号都一定对应有一个leader的，比如上面的情况3中，可能在选举超时到来之前都没有产生一个新的leader，那么此时将递增任期号开始一次新的选举。

4.3 Leader选举

1）在进行选举过程中，有几个重要的概念

Leader Election（领导人选举）：简称选举，就是从候选人中选出领袖；
Term（任期）：它其实是个单独递增的连续数字，每一次任期就会重新发起一次领导人选举；
Election Timeout（选举超时）：就是一个超时时间，当群众超时未收到领袖的心跳时，会重新进行选举。

2）选举详细过程

如果follower在election timeout内没有收到来自leader的心跳，则会主动发起选举。步骤如下：

增加节点本地的current term ，切换到candidate状态
投自己一票
并行给其他节点发送RequestVote RPCs
等待其他节点的回复

在这个过程中，根据来自其他节点的消息，可能出现三种结果：

收到多数的投票（含自己的一票），则赢得选举，成为leader。每个节点在一个任期中只能给一个节点投票，而且遵守“先来后到”的原则。这样就保证了，每个任期最多只有一个节点会赢得选举成为leader。当一个candidate节点赢得选举成为leader后，它将发送心跳消息给其他节点来宣告它的权威性以阻止其它节点再发起新的选举。
被告知别人已成为leader。当candidate节点等待其他节点时，如果收到了来自其它节点的AppendEntries RPC请求，同时做个请求中带上的任期号不比candidate节点的小，那么说明集群中已经存在leader了，此时candidate节点将切换到follower状态；但是，如果该RPC请求的任期号比candidate节点的小，那么将拒绝该RPC请求继续保持在candidate状态。
一段时间内没有收到majority投票，则保持candidate状态，重新发出选举。当选举超时到来时，如果集群中还没有一个leader存在，那么candidate节点将继续递增任期号再次发起一次新的选举。这种情况理论上可以一直无限发生下去。

4.4 日志复制

选举leader以后，系统可以对外进行工作。客户端的请求发送到leader，leader来调度这些并发请求的顺序，并保证leader和follower状态的一致性。在Raft算法中，将这些请求以及执行顺序告知followers，leader和followers以相同的顺序来执行这些请求，保证状态一致。共识算法一般是通过复制状态机来实现的，复制状态机简单来说就是：相同的初识状态 + 相同的输入=相同的结束状态。如何保证所有节点按照相同的顺序执行相同的输入，replicated log可以实现，log具有持久化、有序的特点，是大多数分布式系统的基石。因此，在raft算法中，leader将客户端请求封装到一个个log entry，然后将这些log entries复制到所有follower节点，然后大家按相同顺序应用log entry中的command，来保证状态一致性。

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

leader以append方式写log entry
leader 并行发送AppendEntries RPC
leader等待majority回应
leader将log entry应用到state machine
leader回复消息到client
leader通知follower应用log

可以看到日志的提交过程有点类似两阶段提交(2PC)，不过与2PC的区别在于，leader只需要大多数（majority）节点的回复即可，这样只要超过一半节点处于工作状态则系统就是可用的。每个节点的日志并不完全一致，raft算法为了保证高可用，并不是强一致性，而是最终一致性，leader会不断尝试给follower发log entries，直到所有节点的log entries都相同。

5、Zookeeper原子广播协议Zab

Zab协议的全称是Zookeeper Atomic Broadcast（Zookeeper原子广播），是为分布式协调服务Zookeeper专门设计的一种支持崩溃恢复的原子广播协议，是Zookeeper保证数据一致性的核心算法。Zab借鉴了Paxos算法，但又不像Paxos那样，是一种通用的分布式一致性算法，它是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。

在Zookeeper中主要依赖Zab协议来实现数据一致性，基于该协议，zk实现了一种主备模型的系统架构来保证集群中各个副本之间数据的一致性。这里的主备系统架构模型，就是指只有一台客户端（Leader）负责处理外部的写事务请求，然后Leader客户端将数据同步到其他Follower节点。具体如下图所示：

上图显示了Zookeeper如何处理集群中的数据。所有客户端写入数据都是写入到主进程（称为 Leader）中，然后由Leader复制到备份进程（称为 Follower）中，从而保证数据一致性。从设计上看，和Raft类似。

5.1 基本角色和概念

5.1.1 Zab协议中的角色

Zookeeper内部有三个角色

leader：整个集群只能有一个，主要处理写请求，zookeeper中所有的写请求都需要由leader负责处理。当然也能提供读服务。
follower: 整个集群可以有多个，只能提供读服务。在leader发生异常之后通过ZAB的leader election 以及后续的Discovery完成leader的重新选举，将一个follower 标记为leader，对外提供读写服务。
observer: 不参与leader选举和投票，仅仅提供读服务和接受leader变更的通知。可以作为zookeeper同城双机房，中的从机房的角色。既能够提供读服务，又能够有效得减少两个机房之间的rpc通信，从而提升整体的集群性能

5.1.2 ZAB协议四个阶段

ZAB协议主要有四个阶段：

Leader election：主要是节点之间进行信息同步，选择出一个leader。leader选举过程，electionEpoch自增，在选举的时候lastProcessedZxid越大，越有可能成为leader
Discovery：leader获取最新的消息。leader收集follower的lastProcessedZxid，这个主要用来通过和leader的lastProcessedZxid对比来确认follower需要同步的数据范围。选举出一个新的peerEpoch，主要用于防止旧的leader来进行提交操作
Synchronization：leader将获取到的最新的数据同步到其他的从节点，并补全老数据，删除新数据。follower中的事务日志和leader保持一致的过程，就是依据follower和leader之间的lastProcessedZxid进行，follower多的话则删除掉多余部分，follower少的话则补充，一旦对应不上则follower删除掉对不上的zxid及其之后的部分然后再从leader同步该部分之后的数据
Broadcast：整个集群就可以对外提供读写服务，且zookeeper集群正常状态下处于该阶段。leader针对客户端的事务请求，然后提出一个议案，发给所有的follower，一旦过半的follower回复OK的话，leader就可以将该议案进行提交了，向所有follower发送提交该议案的请求，leader同时返回OK响应给客户端

5.1.3 Zab中zxid

zxid: 唯一标识一个trasaction, 全局唯一递增的64位整数。其中低32位可以看作是一个简单的递增的计数器，针对客户端的每一个事务请求，Leader都会产生一个新的事务Proposal并对该计数器进行+ 1操作；高32位则代表了Leader服务器上取出本地日志中最大事务Proposal的ZXID，并从该ZXID中解析出对应的epoch值，然后再对这个值加一。
zxid由 <epoch, count>组成

Epoch: 每个leader生命周期的一个标识。newEpoch = lastEpoch + 1
Count :表示每个Epoch期间发生的transaction id, 每个count 都是从0开始加一递增

zxid的比较；我们称zxid<e, c> 大于 zxid'<e’, c’>，当满足 (e > e’ ) || (e = e’ & c > c’).

5.2 Leader选举

Leader选举即通过投票完成leader选举，最后每个成员都会知道leader的epoch和leader id。整个Leader选举的流程如下所示：

投票的信息主要是类似vote (zxid,id)，其中id唯一标识一个peer、zxid为当前peer最新的版本号。图中有三条白色箭头分别代表三个节点的时间，每一个节点在某一个时间会有三条线。

T1 时刻开始了leader选举，三个节点都将各自的node信息先发送给自己，再发送给其他两个节点。比如T1时刻的node1的三条黄色线，表示分别向自己投票，将自己的投票信息发送给其他两个节点，投票信息的大小比较如下规则：node1(id,zxid) > node2(id’ , zxid’) ，当满足 zxid > zxid’ || (zxid==zxid’ && id > id’)
T2 时刻， 其他两个节点都已经完成了投票信息的比较：

比如node1会收到其他两个节点的投票信息，依次和自己的zxid进行比较，版本号高的成为leader；node1最高，不需要再发送消息投票（它开始已经投自己一票了）。
node2会收到来自node3和node1的投票，进行投票信息的比较，发现node1 > node2，node1 > node3，投票给node1，并准备好新的投票结果进行广播。
node3 类似，投票给node1。

T3 时刻，整个集群其实已经完成了选举，node1成为新leader, 不过还是准leader，后续需要进行一些更进一步的版本数据同步

5.3 消息广播

Zab协议的消息广播过程使用的是一个原子广播协议，类似一个二阶段提交过程。对于客户端发送的写请求，全部由Leader接收，Leader将请求封装成一个事务Proposal，将其发送给所有Follwer ，然后，根据所有Follwer的反馈，如果超过半数成功响应，则执行commit操作（先提交自己，再发送commit给所有Follwer）。

如果集群中的Learner节点收到客户端的事务请求，那么这些Learner会将请求转发给Leader 服务器。然后再执行如下的具体过程：

Leader接收到事务请求后，为事务赋予一个全局唯一的 64 位自增 id，即zxid，通过zxid 的大小比较即可实现事务的有序性管理，然后将事务封装为一个Proposal。
Leader根据Follower列表获取到所有Follower，然后再将Proposal通过这些Follower的队列将提案发送给各个Follower。
当Follower接收到提案后，会先将提案的zxid与本地记录的事务日志中的最大的zxid进行比较。若当前提案的zxid大于最大zxid，则将当前提案记录到本地事务日志中，并向Leader返回一个ACK。
当Leader接收到过半的ACKs后，Leader就会向所有Follower的队列发送COMMIT消息，向所有Observer的队列发送Proposal。
当Follower收到COMMIT消息后，就会将日志中的事务正式更新到本地。当Observer收到Proposal后，会直接将事务更新到本地。
无论是Follower还是Observer，在同步完成后都需要向Leader发送成功ACK。

6、总结

本文主要介绍了5中一致性算法，包括2PC、3PC、Paxos、Raft和Zab，2PC在传统的数据库中广泛使用，实现起来简单但是因为事务阻塞和数据一致性问题，已经不适用于分布式架构下的大规模架构的性能要求了。Paxos作为解决分布式一致性问题的通用算法，在Google的很多大型分布式系统如Chubby和Spanner中广泛使用，但是在实际工程中实现起来复杂，所以出现了很多优化算法，比如Raft和Zab。Zab是为分布式协调服务Zookeeper专门设计的一种支持崩溃恢复的原子广播协议，Raft则是一种更为通用的一致性算法，在ETCD、TiDB等数据库存储产品中广泛使用，相对Paxos来说实现上也更为简单些。