本篇文章总结了三种常用的一致性算法：Raft、ZAB、Paxos

Raft算法

参考文档：

https://zhmin.github.io/2019/09/15/zookeeper-zab/

https://zhuanlan.zhihu.com/p/66441389

选举

一些概念

在介绍选举前先介绍几个概念

• leader 接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。

• Follower leader的跟随者，接收并持久化leader同步的日志

• Candidate Leader选举中的临时角色

• term 任期，比如新的选举任期，即整个集群初始化时，或者新的Leader选举就会开始一个新的选举任期。

• 大多数：假设一个集群由N个节点组成，那么大多数就是至少N/2+1。例如：3个节点的集群，大多数就是至少2；5个节点的集群，大多数就是至少3





如何选举

Leader选举需要某个节点发起投票，在确定哪个节点向其他节点发起投票之前，每个节点会分配一个随机的选举超时时间（election timeout）。在这个时间内，节点必须等待，不能成为Candidate状态。现在假设节点a等待168ms , 节点b等待210ms , 节点c等待200ms 。由于a的等待时间最短，所以它会最先成为Candidate，并向另外两个节点发起投票请求，希望它们能选举自己为Leader：

• a将其当前term+1然后转换为Candidate,它首先会给自己投票，并给集群中的其他节点发送RequestVote RPC

• a收到了大多数的投票，就会从Candidate变为Leader，接下来分布式系统所有的概念都会先经过节点a

• 如果a没有赢得多数的投票，则选举失败，等待选举时间超时后发起下一次选举





• 如果某个时刻，Follower不再收到Leader的消息，它就会变成Candidate。然后请求其他节点给他投票（类似拉票一样）。其他节点就会回复它投票结果，如果它能得到大多数节点的投票，它就能成为新的Leader。

日志复制

一些概念

• uncommitted 未提交，一条日志提交给Leader后，还没被其他节点接收，状态会初始化uncommitted

• committed 一旦大多数节点成功写入了这条日志，那么Leader节点的这条日志状态就会更新为commited状态

复制过程

1. client写入日志，发起请求

2. 请求首先进入Leader，Leader写入该日志，并将该日志的状态设置为uncommitted

3. Leader会将此日志通过心跳消息复制给其他的follower

4. 如果大多数节点成功写入这条日志，那么Leader节点的这条日志就会更新为commited

网络分区

一些概念

• CAP定义

• Consistency 每次读取的数据都应该是最近写入的数据或者返回一个错误，等同于所有节点访问同一份最新的数据副本

• Availability 每次请求都应该得到一个响应，而不是返回一个错误或者丢失后响应，不过这个响应不需要保证数据是最近写入的

• Partition tolerance 即使因为网络原因，部分服务器节点之间消息丢失或者延迟了，系统依然应该是可以操作的，以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况



• 网络分区 网络分区指由于网络设备的failure，造成网络分裂为多个独立的组

Raft处理

• 假设我们的集群由5个节点组成，且节点B是Leader节点

• 我们假设发生了网络分区：节点A和B在一个网络分区，节点C、D和E在另一个网络分区，且节点B和节点C分别是两个网络分区中的Leader节点

• 我们假设还有一个客户端，并且往节点B上发送了一个SET 3，由于网络分区的原因，这个值不能被另一个网络分区中的Leader即节点C拿到，它最多只能被两个节点（节点B和C）感知到，所以它的状态是uncomitted（红色）

• 另一个客户端准备执行SET 8的操作，由于可以被同一个分区下总计三个节点（节点C、D和E）感知到，3个节点已经符合大多数节点的条件。所以，这个值的状态就是committed

• 接下来，我们假设网络恢复正常，节点B能感知到C节点这个Leader的存在，它就会从Leader状态退回到Follower状态，并且节点A和B会回滚之前没有提交的日志（SET 3产生的uncommitted日志）。同时，节点A和B会从新的Leader节点即C节点获取最新的日志（SET 8产生的日志），从而将它们的值更新为8。如此以来，整个集群的5个节点数据完全一致了





超时处理

选举超时

为了防止3个节点（假设集群由3个节点组成）同时发起投票，会给每个节点分配一个随机的选举超时时间（Election Timeout），即从Follower状态成为Candidate状态需要等待的时间。在这个时间内，节点必须等待，不能成为Candidate状态。如下图所示，节点C优先成为Candidate，而节点A和B还在等待中：





心跳超时

如下图所示，节点A和C投票给了B，所以节点B是leader节点。节点B会固定间隔时间向两个Follower节点A和C发送心跳消息，这个固定间隔时间被称为heartbeat timeout。Follower节点收到每一条日志信息都需要向Leader节点响应这条日志复制的结果

重新选举

如果Leader节点出现故障，就会触发重新选举。如下图所示，Leader节点B故障（灰色），这时候节点A和C就会等待一个随机时间（选举超时），谁等待的时候更短，谁就先成为Candidate，然后向其他节点发送投票请求，如果节点A能得得到节点C的投票，加上自己的投票，就有大多数选票。那么节点A将成为新的Leader节点，并且Term即任期的值加1更新到2：





需要说明的是，每个选举期只会选出一个Leader。假设同一时间有两个节点成为Candidate（它们随机等待选举超时时间刚好一样），如下图所示，并且假设节点A收到了节点B的投票，而节点C收到了节点D的投票：



这种情况下，就会触发一次新的选举，节点A和节点B又等待一个随机的选举超时时间，直到一方胜出：





我们假设节点A能得到大多数投票，那么接下来节点A就会成为新的Leader节点，并且任期term加1：





ZAB算法

参考文档：

https://zhmin.github.io/2019/09/15/zookeeper-zab/

选举

一些概念

• leader 主节点，与上面相同

• follower 从节点，与上面相同

• observer 可以认为是主的clone copy，不参与投票

• quorum 集群中超过半数的节点集合

• zxid Zxid 是一个 64 位的数字，其中低 32 位是一个简单的单调递增的计数器，针对客户端每一个事务请求，计数器加 1；而高 32 位则代表 Leader 周期 epoch 的编号，每个当选产生一个新的 Leader 服务器，就会从这个 Leader 服务器上取出其本地日志中最大事务的ZXID，并从中读取 epoch 值，然后加 1，以此作为新的 epoch，并将低 32 位从 0 开始计数。



ZAB 中的节点有三种状态

• following：当前节点是跟随者，服从 leader 节点的命令

• leading：当前节点是 leader，负责协调事务

• election/looking：节点处于选举状态

如何选举

成为 leader 的条件

1. 选epoch最大的

2. epoch相等，选 zxid 最大的

3. epoch和zxid都相等，选择server id最大的（就是我们配置zoo.cfg中的myid）



选举过程（fast paxos）

节点在选举开始都默认投票给自己，当接收其他节点的选票时，会根据上面的条件更改自己的选票并重新发送选票给其他节点，当有一个节点的得票超过半数，该节点会设置自己的状态为 leading，其他节点会设置自己的状态为 following。

• 每个进入looking状态的节点，最开始投票给自己，然后把投票消息发给其它机器。内容为<第几轮投票，被投节点的zxid，被投节点的编号>。

• 其他looking状态的节点收到后，首先判断票是否有效，是否有效的方法为看票的投票轮数和本地记载的投票轮数是否相等。

• 如果比本地投票轮数的小，丢弃

• 如果比本地投票轮数的大，证明自己投票过期了，清空本地投票信息，更新投票轮数和结果为收到的内容。通知其他所有节点新的投票方案。

• 如果和本地投票轮数相等，按照投票的优先级比较收到的选票和自己投出去的选票

• 如果收到的优先级大，更新自己的投票为对方发过来投票方案，把投票发出去。

• 如果收到的优先级小，则忽略该投票。

• 如果收到的优先级相等，则更新对应节点的投票。

• 每收集到一个投票后，查看已经收到的投票结果记录列表，看是否有节点能够达到一半以上的投票数。如果有达到，则终止投票，宣布选举结束，更新自身状态。然后进行发现和同步阶段。

• 否则继续收集投票。



选举过程（basic paxos）

• 每个looking节点先发出请求，询问其他节点的投票。

• 其他节点返回自己的投票 < zk的id，zxid >。第一次都投自己。

• 收到结果后，如果收到的投票比自己投票的zxid大，更新自己的投票。

•  当收到所有节点返回后，统计投票，有一个节点的选举达到一半以上，则选举成功。否则继续开始下一轮询问，直到选择出leader结束。

消息复制

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

• 将数据都复制到 Follwer 中

• 等待 Follwer 回应 Ack，最低超过半数即成功

• 当超过半数成功回应，则执行 commit ，同时提交自己



一些细节

1. Leader 在收到客户端请求之后，会将这个请求封装成一个事务，并给这个事务分配一个全局递增的唯一 ID，称为事务ID（ZXID），ZAB 兮协议需要保证事务的顺序，因此必须将每一个事务按照 ZXID 进行先后排序然后处理。

2. 在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，解除同步阻塞。

3. zookeeper集群中为保证任何所有进程能够有序的顺序执行，只能是 Leader 服务器接受写请求，即使是 Follower 服务器接受到客户端的请求，也会转发到 Leader 服务器进行处理。

4. 实际上，这是一种简化版本的 2PC，不能解决单点问题。



灾难场景

Leader 崩溃

崩溃即：Leader 失去与过半 Follwer 的联系

ZAB保证：能够确保提交已经被 Leader 提交的事务，同时丢弃已经被跳过的事务。

• ZAB 协议确保那些已经在 Leader 提交的事务最终会被所有服务器提交。

• ZAB 协议确保丢弃那些只在 Leader 提出/复制，但没有提交的事务。



针对这个要求，如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群总所有机器编号（即 ZXID 最大）的事务，那么就能够保证这个新选举出来的 Leader 一定具有所有已经提交的提案。而且这么做有一个好处是：可以省去 Leader 服务器检查事务的提交和丢弃工作的这一步操作。



数据同步

当成为 follower 节点后，需要向 leader 节点同步数据，因为 follower 节点的数据可能落后于leader。当同步过程完成后，集群就可以对外提供读写服务了。

• 当 Follower 连接上 Leader 之后，Leader 服务器会根据自己服务器上最后被提交的 ZXID 和 Follower 上的 ZXID 进行比对，比对结果要么回滚，要么和 Leader 同步

• 当所有的 Follwer 服务器都成功同步之后，Leader 会将这些服务器加入到可用服务器列表中

• 这里只有当准Leader将多数节点数据同步到一致状态之后，才会发送NewLeader给多数节点，多数节点才更新其本地的currentEpoch





ZAB中Leader会根据Follower数据情况使用多种同步策略：



• SNAP：如果Follower数据太老，Leader将发送快照SNAP指令给Follower同步数据

• DIFF：Leader发送从Follower.lastZxid到Leader.lastZxid之间的提案DIFF数据给Follower同步数据

• TRUNC：当Follower.lastZxid比Leader.lastZxid大时，Leader发送从Leader.lastZxid到Follower.lastZxid的TRUNC指令让Follower丢弃该段数据SNAP和DIFF用于保证集群中Follower节点上已经Committed的数据的一致性，TRUNC用于抛弃已经被处理但是还没有Committed的数据。Follower接收SNAP/DIFF/TRUNC指令同步数据与ZXID，同步成功之后向Leader发送ACK-LD，Leader才会将其加入到可用Follower列表。



Paxos算法

参考文档：

https://zhuanlan.zhihu.com/p/31780743

https://www.cnblogs.com/linbingdong/p/6253479.html

背景

Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。



Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛Paxos作为比喻，描述了Paxos小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在2001年，Lamport觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版本《Paxos Made Simple》。



自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。



然而，Paxos的最大特点就是难，不仅难以理解，更难以实现。

Basic Paxos

一些概念

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。

• Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。

• Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。

在具体的实现中，一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。





算法过程

Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：



1. 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。

2. 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。

3. 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。





Paxos算法流程中的每条消息描述如下：



• Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。

• Promise: Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。



两个承诺：



1. 不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。



2. 不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求。



一个应答：



不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。



• Propose: Proposer 收到多数Acceptors的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案。如果所有应答的提案Value均为空值，则可以自己随意决定提案Value。然后携带当前Proposal ID，向所有Acceptors发送Propose请求。

• Accept: Acceptor收到Propose请求后，在不违背自己之前作出的承诺下，接受并持久化当前Proposal ID和提案Value。

• Learn: Proposer收到多数Acceptors的Accept后，决议形成，将形成的决议发送给所有Learners。



问题

Paxos算法可能形成活锁而永远不会结束，如下图实例所示：



Paxos算法形成活锁



回顾两个承诺之一，Acceptor不再应答Proposal ID小于等于当前请求的Prepare请求。意味着需要应答Proposal ID大于当前请求的Prepare请求。

两个Proposers交替Prepare成功，而Accept失败，形成活锁（Livelock）。



Multi-Paxos算法



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



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



1. 针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。

2. 在所有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提交的所有实例，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个Instance ID标识，Instance ID由Leader本地递增生成即可。



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



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