10.13｜讲一下你知道的分布式共识算法

共识算法

paxos、raft准确来说是共识（consensus）算法，而不是一致性（consistency）算法。

共识指的是一个或多个进程提议了一个值应当是什么后，采用一种大家都认可的方法，使得系统中所有进程对这个值达成一致意见。

比如说选主（Leader election）问题中所有进程对Leader达成一致；互斥（Mutual exclusion）问题中对于哪个进程进入临界区达成一致；原子组播（Atomic broadcast）中进程对消息传递（delivery）顺序达成一致。对于这些问题有一些特定的算法，但是，分布式共识问题试图探讨这些问题的一个更一般的形式，如果能够解决分布式共识问题，则以上的问题都可以得以解决。

一致性指的是对于同一个数据的多个副本之间，保持其对外表现的数据一致性。

一些常见的误解：使用了 Raft或者 paxos 的系统都是线性一致的（Linearizability 即强一致），其实不然，共识算法只能提供基础，要实现线性一致还需要在算法之上做出更多的努力。

共识算法属性

它的三个属性。

正确性（Validity）：诚实节点最终达成共识的值必须是来自诚实节点提议的值。
一致性（Agreement）：所有的诚实节点都必须就相同的值达成共识。
终止性（Termination）：诚实的节点必须最终就某个值达成共识。

共识算法中需要有“诚实”节点，它的概念是节点不能产生失败模型所描述的“任意失败”，或是“拜占庭失败”。

Paxos协议

Paxos 其实是一类协议，Paxos 中包含 Basic Paxos、Multi-Paxos、Cheap Paxos 和其他的变种。Raft 就是 Multi-Paxos 的一个变种，Raft 通过简化 Multi-Paxos 的模型，实现了一种更容易让人理解和工程实现的共识算法，

Paxos是第一个被证明完备的共识算法，能够让分布式网络中的节点在出现错误时仍然保持一致，当然前提是没有恶意节点，也就是拜占庭将军问题。在传统的分布式系统领域是不需要担心这种问题的，因为不论是分布式数据库、消息队列、分布式存储，你的机器都不会故意发送错误信息，最常见的问题反而是节点失去响应，所以它们在这种前提下，Paxos是足够用的。

一些常见的误解：使用了 Raft [0] 或者 paxos 的系统都是线性一致的（Linearizability [1]，即强一致），其实不然，共识算法只能提供基础，要实现线性一致还需要在算法之上做出更多的努力。以 TiKV 为例，它的共识算法是 Raft，在 Raft 的保证下，TiKV 提供了满足线性一致性的服务。

Paxos的直观解释

有时间的话推荐直接看大佬的原文：https://blog.openacid.com/algo/paxos

paxos的工作, 就是把一堆运行的机器协同起来, 让多个机器成为一个整体系统. 在这个系统中, 每个机器都必须让系统中的状态达成一致, 例如三副本集群如果一个机器上上传了一张图片, 那么另外2台机器上也必须复制这张图片过来, 整个系统才处于一个一致的状态.

几乎所有的分布式存储都必须用某种冗余的方式在廉价硬件的基础上搭建高可靠的存储. 而冗余的基础就是多副本策略, 一份数据存多份. 多副本保证了可靠性, 而副本之间的一致, 就需要paxos这类分布式一致性算法来保证.

主从异步复制

主从异步复制是最简单的策略之一, 它很容易实现, 但存在一个问题: 客户端收到一个数据已经安全(OK)的信息, 跟数据真正安全(数据复制到全部的机器上)在时间上有一个空隙, 这段时间负责接收客户端请求的那个机器(master)如果被闪电击中或被陨石砸到或被打扫卫生的大姐踢断了电源, 那数据就可能会丢失. 因此它不是一个可靠的复制策略(使用主从异步复制要求你必须相信宇宙中不存在闪电陨石和扫地大姐).

主从同步复制

跟主从异步复制相比, 主从同步复制提供了完整的可靠性: 直到数据真的安全的复制到全部的机器上之后, master才告知客户端数据已经安全.

但主从同步复制有个致命的缺点就是整个系统中有任何一个机器宕机, 写入就进行不下去了. 相当于系统的可用性随着副本数量指数降低.

主从半同步复制

然鹅, 在同步和异步之间, 做一个折中, 看起来是一个不错的方案. 这就是半同步复制. 它要求master在应答客户端之前必须把数据复制到足够多的机器上, 但不需要是全部. 这样副本数够多可以提供比较高的可靠性; 1台机器宕机也不会让整个系统停止写入.

但是它还是不完美, 例如数据a复制到slave-1, 但没有到达slave-2; 数据b复制达到了slave-2但没有到达slave-1, 这时如果master挂掉了需要从某个slave恢复出数据, 任何一个slave都不能提供完整的数据. 所以在整个系统中, 数据存在某种不一致.

多数派

为了解决半同步复制中数据不一致的问题, 可以将这个复制策略再做一改进: 多数派读写: 每条数据必须写入到半数以上的机器上. 每次读取数据都必须检查半数以上的机器上是否有这条数据.

在这种策略下, 数据可靠性足够, 宕机容忍足够, 任一机器故障也能读到全部数据.

多数派引起的问题1

然鹅多数派读写的策略也有个但是, 就是对于一条数据的更新时, 会产生不一致的状态. 例如:

node-1, node-2都写入了a=x,
下一次更新时node-2, node-3写入了a=y.

这时, 一个要进行读取a的客户端如果联系到了node-1和node-2, 它将看到2条不同的数据.

为了不产生歧义, 多数派读写还必须给每笔写入增加一个全局递增的时间戳. 更大时间戳的记录如果被看见, 就应该忽略小时间戳的记录. 这样在读取过程中, 客户端就会看到a=x₁, a=y₂ 这2条数据, 通过比较时间戳1和2, 发现y是更新的数据, 所以忽略a=x₁. 这样保证多次更新一条数据不产生歧义.

多数派引起的问题2

是的, 但是又来了. 这种带时间戳的多数派读写依然有问题. 就是在客户端没有完成一次完整的多数派写的时候: 例如, 上面的例子中写入, a=x₁写入了node-1和node-2, a=y₂时只有node-3 写成功了, 然后客户端进程就挂掉了, 留下系统中的状态如下:

node-1: a=x₁
node-2: a=x₁
node-3: a=y₂

这时另一个读取的客户端来了,

如果它联系到node-1和node-2, 那它得到的结果是a=x₁.
如果它联系到node-2和node-3, 那它得到的结果是a=y₂.

整个系统对外部提供的信息仍然是不一致的.

==paxos可以认为是多数派读写的进一步升级, paxos中通过2次原本并不严谨的多数派读写, 实现了严谨的强一致consensus算法.==

算法描述

一句话总结

proposer将发起提案（value）给所有accpetor，超过半数accpetor获得批准后，proposer将提案写入accpetor内，最终所有accpetor获得一致性的确定性取值，且后续不允许再修改。

Proposer 可以理解为客户端.
Acceptor 可以理解为存储节点.
Quorum 在99%的场景里都是指多数派, 也就是半数以上的Acceptor.
Round 用来标识一次paxos算法实例, 每个round是2次多数派读写: 算法描述里分别用phase-1和phase-2标识. 同时为了简单和明确, 算法中也规定了每个Proposer都必须生成全局单调递增的round, 这样round既能用来区分先后也能用来区分不同的Proposer(客户端).

在存储端(Acceptor)也有几个概念:

last_rnd 是Acceptor记住的最后一次进行写前读取的Proposer(客户端)是谁, 以此来决定谁可以在后面真正把一个值写到存储中.
v 是最后被写入的值.
vrnd 跟v是一对, 它记录了在哪个Round中v被写入了.

首先是paxos的phase-1, 它相当于之前提到的写前读取过程. 它用来在存储节点(Acceptor)上记录一个标识: 我后面要写入; 并从Acceptor上读出是否有之前未完成的paxos运行. 如果有则尝试恢复它; 如果没有则继续做自己想做的事情.

Proposer X收到多数(quorum)个应答, 就认为是可以继续运行的.如果没有联系到多于半数的acceptor, 整个系统就hang住了, 这也是paxos声称的只能运行少于半数的节点失效.

这时Proposer面临2种情况:

所有应答中都没有任何非空的v, 这表示系统之前是干净的, 没有任何值已经被其他paxos客户端完成了写入(因为一个多数派读一定会看到一个多数派写的结果). 这时Proposer X继续将它要写的值在phase-2中真正写入到多于半数的Acceptor中.
如果收到了某个应答包含被写入的v和vrnd, 这时, Proposer X 必须假设有其他客户端(Proposer) 正在运行, 虽然X不知道对方是否已经成功结束, 但任何已经写入的值都不能被修改!, 所以X必须保持原有的值. 于是X将看到的最大vrnd对应的v作为X的phase-2将要写入的值.

这时实际上可以认为X执行了一次(不知是否已经中断的)其他客户端(Proposer)的修复.

在第2阶段phase-2, Proposer X将它选定的值写入到Acceptor中, 这个值可能是它自己要写入的值, 或者是它从某个Acceptor上读到的v(修复).

当然这时(在X收到phase-1应答, 到发送phase-2请求的这段时间), 可能已经有其他Proposer又完成了一个rnd更大的phase-1, 所以这时X不一定能成功运行完phase-2.

Acceptor通过比较phase-2请求中的rnd, 和自己本地记录的rnd, 来确定X是否还有权写入. 如果请求中的rnd和Acceptor本地记录的rnd一样, 那么这次写入就是被允许的, Acceptor将v写入本地, 并将phase-2请求中的rnd记录到本地的vrnd中.

算法描述2

Paxos算法流程

Paxos算法分为两个阶段。具体如下：

阶段一：

(a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。

(b) 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。
阶段二：

(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对**[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value**，如果响应中不包含任何提案，那么V就由Proposer自己决定。

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

https://blog.csdn.net/yzf279533105/article/details/109315877

活锁

在这里插入图片描述

为了保持活性，避免上述的问题，就必须选择一个主Proposer，并规定只能由主Proposer才能提出议案，只有主能提出议案，那么就算主被抛弃了，下次也会提出更高议案，而其他非主不能再次提出更高的议案，这样就不会陷入死循环中，从而避免了上述的问题。

Mutil-Paxos

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

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

针对每一个要确定的值，运行一次Paxos算法实例(Instance)，形成决议。每一个Paxos实例使用唯一的Instance ID标识。
在所有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的变形。

Raft算法

状态机

简单来说，就是具有相同的初始状态的对象，加上相同的中间操作，最后的状态也必定是一样的。

基本术语

Raft集群包含多个服务器，5个服务器是比较典型的，允许系统容忍两个故障。在任何给定时间，每个服务器都处于以下三种状态之一，领导者（Leader），追随者（Follower）或候选人（Candidate）。这几个状态见可以相互转换。

Leader：处理所有客户端交互，日志复制等，一般一次只有一个Leader

Follower：类似选民，完全被动

Candidate：候选人，类似Proposer，可以被选为一个新的领导人

Raft算法子问题

Raft实现了和Paxos相同的功能，它将一致性分解为多个子问题: Leader选举(Leader election)、日志同步(Log replication)、安全性(Safety)、日志压缩(Log compaction)、成员变更(Membership change)等

Leader选举

Raft 使用心跳(heartbeat)触发Leader选举。当服务器启动时，初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。

Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC (RPC细节参见八、Raft算法总结)。结果有以下三种情况:

赢得了多数的选票，成功选举为Leader；
收到了Leader的消息，表示有其它服务器已经抢先当选了Leader；
没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。

选举出Leader后，Leader通过定期向所有Followers发送心跳信息维持其统治。若Follower一段时间未收到Leader的心跳则认为Leader可能已经挂了，再次发起Leader选举过程。

Raft保证选举出的Leader上一定具有最新的已提交的日志。

日志同步

Leader选出后，就开始接收客户端的请求。

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

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

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

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

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

安全性

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

拥有最新的已提交的log entry的Follower才有资格成为Leader。

这个保证是在RequestVote RPC中做的，Candidate在发送RequestVote RPC时，要带上自己的最后一条日志的term和log index，其他节点收到消息时，如果发现自己的日志比请求中携带的更新，则拒绝投票。

日志比较的原则是，如果本地的最后一条log entry的term更大，则term大的更新，如果term一样大，则log index更大的更新。

Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交(log index 小于 commit index的日志被间接提交)。

日志压缩与成员变更

https://pdai.tech/md/algorithm/alg-domain-distribute-x-raft.html

Raft与Multi-Paxos的不同

总结

Raft算法具备强一致、高可靠、高可用等优点，具体体现在：

强一致性：虽然所有节点的数据

并非实时一致，但Raft算法保证Leader节点的数据最全，同时所有请求都由Leader处理，所以在客户端角度看是强一致性的。

高可靠性：Raft算法保证了Committed的日志不会被修改，State Matchine只应用Committed的日志，所以当客户端收到请求成功即代表数据不再改变。Committed日志在大多数节点上冗余存储，少于一半的磁盘故障数据不会丢失。

高可用性：从Raft算法原理可以看出，选举和日志同步都只需要大多数的节点正常互联即可，所以少量节点故障或网络异常不会影响系统的可用性。即使Leader故障，在选举超时到期后，集群自发选举新Leader，无需人工干预，不可用时间极小。但Leader故障时存在重复数据问题，需要业务去重或幂等性保证。

高性能：与必须将数据写到所有节点才能返回客户端成功的算法相比，Raft算法只需要大多数节点成功即可，少量节点处理缓慢不会延缓整体系统运行。

关于Raft的一些面试题

https://blog.csdn.net/yzf279533105/article/details/127167605

ZAB协议

基本和raft相同，只是在一些名词的叫法上有一些区别
比如ZAB 将某一个leader的周期称为epoch,而raft称为 term。

实现上的话 raft为了保证日志连续性，心跳方向是从leader到follower，ZAB则是相反的

原子广播与 ZAB

ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）

广播协议是一类将数据从一个节点同步到多个节点的协议。

以上的广播过程产生了一个问题，那就是这个协调节点是明显的单点，它的可靠性至关重要。要保障其可靠，首先要解决的问题是需要检查这个节点的健康状态。我们可以通过各种健康检查方式去发现其健康情况。

如果它失败了，会造成消息传播到一部分节点中，而另外一部分节点却没有这一份消息，这就违背了“一致性”。那么应该怎解决这个问题呢？

一个简单的算法就是使用“漫灌”机制，这种机制是一旦一个消息被广播到一个节点，该节点就有义务把该消息广播到其他未收到数据节点的义务。这就像水田灌溉一样，最终整个系统都收到了这份数据。

当然以上的模式有个明显的缺点，就是会产生N2的消息。其中 N 是目前系统剩下的未同步消息的节点，所以我们的一个优化目标就是要减少消息的总数量。

虽然广播可以可靠传递数据，但通过一致性的学习我们知道：需要保证各个节点接收到消息的顺序，才能实现较为严格的一致性。所以我们这里定义一个原子广播协议来满足。

原子性：所有参与节点都收到并传播该消息；或相反，都不传播该消息。
顺序性：所有参与节点传播消息的顺序都是一致的。

满足以上条件的协议我们称为原子广播协议，最为常见的原子广播协议就是ZAB：Zookeeper Atomic Broadcast（ZAB）。

ZAB 设计

ZooKeeper 文档中明确写明它的一致性是 Sequential consistency即顺序一致

ZooKeeper中针对同一个Follower A提交的写请求request1、request2，某些Follower虽然可能不能在请求提交成功后立即看到（也就是强一致性），但经过自身与Leader之间的同步后，这些Follower在看到这两个请求时，一定是先看到request1，然后再看到request2，两个请求之间不会乱序，即顺序一致性

其实，实现上ZooKeeper 的一致性更复杂一些，ZooKeeper 的读操作是 sequential consistency 的，ZooKeeper 的写操作是 linearizability 的，关于这个说法，ZooKeeper 的官方文档中没有写出来，但是在社区的邮件组有详细的讨论。ZooKeeper 的论文《Modular Composition of Coordination Services》中也有提到这个观点。

总结一下，可以这么理解 ZooKeeper：从整体（read 操作 +write 操作）上来说是 sequential consistency，写操作实现了 Linearizability。

ZAB 协议由于 Zookeeper 的广泛使用变得非常流行。它是一种原子广播协议，可以保证消息顺序的传递，且消息广播时的原子性保障了消息的一致性。

ZAB 协议中，节点的角色有两种。

领导节点。==领导是一个临时角色，它是有任期的==。这么做的目的是保证领导角色的活性。领导节点控制着算法执行的过程，广播消息并保证消息是按顺序传播的。读写操作都要经过它，从而保证操作的都是最新的数据。如果一个客户端连接的不是领导节点，它发送的消息也会转发到领导节点中。
跟随节点。主要作用是接受领导发送的消息，并检测领导的健康状态。

既然需要有领导节点产生，我们就需要领导选举算法。

这里我们要明确两个 ID：数据 ID 与节点 ID。

前者可以看作消息的时间戳，后者是节点的优先级。

==选举的原则是：==

在同一任职周期内，节点的数据 ID 越大，表示该节点的数据越新，数据 ID 最大的节点优先被投票。

所有节点的数据 ID 都相同，则节点 ID 最大的节点优先被投票。当一个节点的得票数超过节点半数，则该节点成为主节点。

一旦领导节点选举出来，它就需要做两件事。

声明任期。领导节点通知所有的跟随节点当前的最新任期；而后由跟随节点确认当前任期是最新的任期，从而同步所有节点的状态。通过该过程，老任期的消息就不会被跟随节点所接受了。
同步状态。这一步很关键，首先领导节点会通知所有跟随节点自己的领导身份，而后跟随节点不会再选举自己为领导了；然后领导节点会同步集群内的消息历史，保证最新的消息在所有节点中同步。因为新选举的领导节点很可能并没有最新被接受的数据，因此同步历史数据操作是很有必要的。

经过以上的初始化动作后，领导节点就可以正常接受消息，进行消息排序而后广播消息了。在广播消息的时候，需要 Quorum（集群中大多数的节点）的节点返回已经接受的消息才认为消息被正确广播了。同时为了保证顺序，需要前一个消息正常广播，后一个消息才能进行广播。

领导节点与跟随节点使用心跳算法检测彼此的健康情况。如果领导节点发现自己与 Quorum 节点们失去联系，比如网络分区，此时领导节点会主动下台，开始新一轮选举。同理，当跟随节点检测到领导节点延迟过大，也会触发新一轮选举。

ZAB 选举的优势是，如果领导节点一直健康，即使当前任期过期，选举后原领导节点还会承担领导角色，而不会触发领导节点切换，这保证了该算法的稳定。

另外，它的节点恢复比较高效，通过比较各个节点的消息 ID，找到最大的消息 ID，就可以从上面恢复最新的数据了。

最后，它的消息广播可以理解为没有投票过程的两阶段提交，只需要两轮消息就可以将消息广播出去。

ZAB 消息广播

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

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

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

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

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

ZAB 奔溃恢复

Leader 崩溃怎么办？还能保证数据一致吗？如果 Leader 先本地提交了，然后 commit 请求没有发送出去，怎么办？

实际上，当 Leader 崩溃，即进入我们开头所说的崩溃恢复模式（崩溃即：Leader 失去与过半 Follwer 的联系）。下面来详细讲述。

假设1：Leader 在复制数据给所有 Follwer 之后崩溃，怎么办？
假设2：Leader 在收到 Ack 并提交了自己，同时发送了部分 commit 出去之后崩溃怎么办？

针对这些问题，ZAB 定义了 2 个原则：

ZAB 协议确保那些已经在 Leader 提交的事务最终会被所有服务器提交。
ZAB 协议确保丢弃那些只在 Leader 提出/复制，但没有提交的事务。

所以，ZAB 设计了下面这样一个选举算法：能够确保提交已经被 Leader 提交的事务，同时丢弃已经被跳过的事务。

针对这个要求，如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群总所有机器编号（即 ZXID 最大）的事务，那么就能够保证这个新选举出来的 Leader 一定具有所有已经提交的提案。

而且这么做有一个好处是：可以省去 Leader 服务器检查事务的提交和丢弃工作的这一步操作。

这样，我们刚刚假设的两个问题便能够解决。假设 1 最终会丢弃调用没有提交的数据，假设 2 最终会同步所有服务器的数据。这个时候，就引出了一个问题，如何同步？

ZAB 数据同步

当崩溃恢复之后，需要在正式工作之前（接收客户端请求），Leader 服务器首先确认事务是否都已经被过半的 Follwer 提交了，即是否完成了数据同步。目的是为了保持数据一致。

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

实际上，Leader 服务器处理或丢弃事务都是依赖着 ZXID 的，那么这个 ZXID 如何生成呢？

答：在 ZAB 协议的事务编号 ZXID 设计中，ZXID 是一个 64 位的数字，其中低 32 位可以看作是一个简单的递增的计数器，针对客户端的每一个事务请求，Leader 都会产生一个新的事务 Proposal 并对该计数器进行 + 1 操作。

而高 32 位则代表了 Leader 服务器上取出本地日志中最大事务 Proposal 的 ZXID，并从该 ZXID 中解析出对应的 epoch 值，然后再对这个值加一。

高 32 位代表了每代 Leader 的唯一性，低 32 代表了每代 Leader 中事务的唯一性。同时，也能让 Follwer 通过高 32 位识别不同的 Leader。简化了数据恢复流程。

基于这样的策略：当 Follower 链接上 Leader 之后，Leader 服务器会根据自己服务器上最后被提交的 ZXID 和 Follower 上的 ZXID 进行比对，比对结果要么回滚，要么和 Leader 同步。

总结

ZAB 协议和我们之前看的 Raft 协议实际上是有相似之处的，比如都有一个 Leader，用来保证一致性（Paxos 并没有使用 Leader 机制保证一致性）。再有采取过半即成功的机制保证服务可用（实际上 Paxos 和 Raft 都是这么做的）。

ZAB 让整个 Zookeeper 集群在两个模式之间转换，消息广播和崩溃恢复，消息广播可以说是一个简化版本的 2PC，通过崩溃恢复解决了 2PC 的单点问题，通过队列解决了 2PC 的同步阻塞问题。

而支持崩溃恢复后数据准确性的就是数据同步了，数据同步基于事务的 ZXID 的唯一性来保证。通过 + 1 操作可以辨别事务的先后顺序。

paxos、 raft 、redis的raft 一致性算法总结

basic-paxos算法，也就是经典的paxos算法

1） 2PC(2 phase commit，也就是2阶段提交），分为 prepare（准备）阶段：proposer产生perposeID，发给各个accepter。accept(接受)阶段：proposer根据准备阶段的结果最终提出commit，accepter决定接受还是不接受。至少三次网络交互的延迟（1. 产生logID；2. prepare阶段；3. accept阶段），所以效率很低

2）没有leader概念，各个进程之间是完全平等的

3）一个进程可能既是proposer，又是accepter

multi-paxos算法

1）有leader概念，先根据basic-paxos算法选举一个proposer为leader，其他proposer不再发起提案，这样就进入了一个leader任期，只能由leader发起提案，后续不再需要产生proposeID，也不必执行prepare阶段，直接执行accept阶段，所以冲突的可能性很低，效率比较高。我们可以将leader选举过程中的prepare操作，视为该leader任期内所有日志的一次性prepare操作，实际上acceptor应答选举的prepare成功的消息之前要先将这次prepare请求所携带的proposalID持久化到本地

2）后续的日志仍然要经过所有accepter的大多数（超过1/2）同意，即仍然有accept阶段

3） confirm日志的优化，之前的basic-paxos读取日志时，仍要执行一轮Paxos过程，效率低下，所以multi-paxos算法引入了confirm日志的优化，对于有confirm日志的日志不再执行paxos过程。对于没有confirm日志的日志，才会重新执行一遍paxos过程，即重确认

4）日志可能不连续，所以新leader需要对空洞的日志都进行一轮paxos

raft算法

1）有leader概念，且日志条目（log entries）只从 leader 流向其他follower服务器。leader有任期（term）限制，当leader失联时，其各个follower使用随机计时器进行 leader 选举，经过其他follower节点的大多数同意可当选为leader。

2）分三中角色，Leader，Follower，Candidate 这三种角色相互独立，也就是服务器在同一时间内只可能扮演其中一种角色。Leader：用于对所有用户的请求进行处理以及日志的复制等等；Follower：不会主动发送消息，只响应来自Leader与Candidate的请求；Candidate：用于选举新的Leader

3）有任期（term）概念，用一个数字表示，每一个任期的开始都是一次选举，一个或多个Candidate会试图称为Leader，但同一任期内只有获得超过一半的票数才能称为Leader，该机制保证了在给定的一个任期最多只有一个Leader

4）日志中包含的内容（任期号，日志包含的命令，索引号），如果 2 个节点日志的相同的索引位置的日志条目的任期号相同，那么 Raft 就认为这个日志从头到这个索引之间的所有日志全部相同。所以当 leader 和 follower 日志冲突的时候，leader 将校验 follower 最后一条日志是否和 leader 匹配，如果不匹配，将递减查询，直到匹配，匹配后，follower删除冲突的日志。这样就实现了主从日志的一致性