分布式-协议

分布式-协议

转载声明

本文大量内容系转载自以下文章，有删改，并参考其他文档资料加入了一些内容：

• 图解：什么是Raft算法？
  作者： 无敌码农

• 分布式一致性算法 Paxos是什么梗？
  作者： 无敌码农

• Raft Vs Zab
  作者： 黄靠谱

1 概述

本文主要讨论分布式协议，包括Paxos、Raft、Zab等。

2 Paxos

2.1 概述

像 2PC 和 3PC 都需要引入一个协调者的角色，当协调者 down 掉之后，整个事务都无法提交，参与者的资源都出于锁定的状态，对于系统的影响是灾难性的，而且出现网络分区的情况，很有可能会出现数据不一致的情况。有没有不需要协调者角色，每个参与者来协调事务呢，在网络分区的情况下，又能最大程度保证一致性的解决方案呢。此时 Paxos 出现了。

Paxos 算法是 Lamport 于 1990 年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，Lamport在八年后重新发表，即便如此Paxos算法还是没有得到重视。2006 年 Google 的三篇论文石破天惊，其中的 chubby 锁服务使用Paxos 作为 chubbycell 中的一致性，后来才得到关注。

Google 的粗粒度锁服务 Chubby 的设计开发者 Burrows 曾经说过：“所有一致性协议本质上要么是 Paxos 要么是其变体”。其实也不为过，像非常有名的 Raft 算法、Zab 算法等都是基于 Paxos 的简化和改进。

2.2 解决了什么问题

Paxos 协议是一个解决分布式系统中，多个节点之间就某个值（提案）达成一致（决议）的通信协议。它能够处理在少数节点离线的情况下，剩余的多数节点仍然能够达成一致。即每个节点，既是参与者，也是协调（决策）者。

• 两种角色（两者可以是同一台机器）
  • Proposer：提议提案的服务器
  • Acceptor：批准提案的服务器

例如一个cache集群有3个节点，每个节点都可以写入。

集群内各个节点需要做数据同步，如果没有一致性算法做保证，3个节点内数据就可能混乱，例如：

• 节点1收到请求后，同步给节点2、3，节点2立即收到了，但因为网络原因，节点3没有立即同步。
• 在节点3同步之前，节点2也发起了同步请求，因为2、3间的网络状况好，节点3立即同步了。
• 所以，节点1、2的同步顺序是 x=1,x=2，而节点3的同步顺序是 x=2,x=1，造成了节点间数据不一致。

Paxos 就是用来解决这个问题，保证各节点数据的绝对一致，不会混乱。

1.3 Zab协议

Zab协议是在Paxos协议基础上进行改进和实践。

参考Zab

1.4 Paxos协议详解

1.4.1 角色

Paxos把每次对数据的更改称为一个提案，就像一个委员会，其中一人发起一个提案，委员会成员对这个提案投票，票数过半的通过，其中有3个角色：

• Proposer，提出提案
• Acceptor，对提案进行投票
• Learner，获取投票结果，不能投票和提出提案

1.4.2 概述

一次Paxos算法的执行实例中，只批准一个value，过程分为2个阶段：

1. Prepare 准备阶段
   Proposer 想发起提案，问各个 Acceptor ：我是否可以发起？
2. Accept 接受阶段
   如果多数 Acceptor 都同意，那么 Proposer 就真正发出自己的提案，请求大家接受。如果多数 Acceptor 都同意了，提案生效。

1.4.3 流程

Acceptor 如何判断是否同意提案呢？下面是整个流程。

首先需要知道，Acceptor 持有3个变量：

1. minProposal，自己目前持有的最小提案编号
2. acceptedProposal，已经接受的提案编号
3. acceptedValue，已经接受的提案内容

然后看流程图：

对照上面那个示例，使用Paxos算法后，流程可能就是这样的：

1. 节点1收到 x=1 的请求，节点1成为Proposer，拿到提案编号1，发起提案，得到了其他节点的同意，然后发送 accept(1,1)请求，请求大家接受。

2. 节点1顺利同意，但由于网络问题，节点2、3暂时没有收到，由于此提案没有得到超过半数的同意，所以现在没有生效。

3. 这时节点2提出x=2的提案，顺利得到大家的同意，因为节点1已经接受了(1,1)，会将其返回给节点2。

4. 节点2收到大家的同意确认，但发现节点1的返回信息中含有已经接受的提案accept(1,1)，就将其提案内容作为自己的提案，发送accept(2,1).注意这里已经改为1了，而不是2。

5. 大家收到后，记录提案内容，返回确认信息，节点2的提案生效了。

6. 在此之后节点2、3才收accept(1,1)请求，由于这个请求的提案编号1小于自己已经接受的提案编号2，所以不会同意，直接拒绝。

7. 最终，3个节点都是x=1，保持一致。

1.5 Paxos 的三种典型情况

为了方便理解，下面以5个节点为例。

1.5.1 提案已经生效，后来的提案只能学习已生效的

1. 节点1发起提案，编号为1，得到了3个节点的同意，提案生效。
2. 紧接着，节点2发起提案，编号为2，发给了节点3、4、5。
3. 节点3发现编号2大于自己的编号1，那么同意，并返回了自己已经接受的提案(1,x)。
4. 节点5从所有返回值中找到提案编号最大的值x，作为自己的提案内容，发出 accept(2,x)请求。
5. 节点3、4、5收到后，发现编号大于自己的，接受了提案。

结果是所有节点的数据一致为x。

1.5.2 提案未生效，但已经被某节点接受，后来的提案只能学习已经接受的

节点1发起提案，因为网络问题，节点3最先接受，节点1、2没有接受。

然后节点5发起提案，发给节点3、4、5。

节点3一看编号比自己的大，表示同意，同时返回自己已经接受的(1,x)。

节点5收到回复后，从所有返回值中找到编号最大的值x，作为自己的提案内容，发起接受请求accept(2,x)。

节点3、4、5接到后，记录提案，提案生效。

同时，节点1、2也收到了节点1的accept请求，记录提案。

结果是所有节点的数据一致为x。

1.5.3 先发起的提案失效，后来的提案生效

节点1发起提案，节点1、2、3同意，但因为网络问题，节点1最先接受。

在节点2、3还未接受时，节点5发起提案，发给了3、4、5。

节点3、4、5一看编号比自己的大，同意。

此时，节点3收到了节点1的accept请求，因为此时节点3自己记录的编号是2，大于节点1的编号，所以，节点3决绝了节点1的accept请求。

节点5收到大家的确认后，从返回值中没有找到已接受的提案，所以使用自己的提案内容y作为提案内容，发起accept(2,y)请求。

节点3、4、5接受，提案y生效。

节点1的提案没有得到多数同意，所以失效，节点1、2需要接受已经生效的提案。

1.6 Paxos小结

以上是Paxos最基本的思路，如果有兴趣，可以好好看看这两篇文章：

• https://segmentfault.com/a/1190000018844326

• https://zh.wikipedia.org/zh-cn/Paxos算法

2 Raft

2.1 概述

Paxos 是论证了一致性协议的可行性，但是论证的过程据说晦涩难懂，缺少必要的实现细节，而且工程实现难度比较高，广为人知实现只有 zk 的实现 zab 协议。然后斯坦福大学RamCloud项目中提出了易实现，易理解的分布式一致性复制协议 Raft。Java，C++，Go 等都有其对应的实现。

所有一致性算法都会涉及到状态机，而状态机保证系统从一个一致的状态开始，以相同的顺序执行一些列指令最终会达到另一个一致的状态。

以上是状态机的示意图。所有的节点以相同的顺序、相同命令处理日志，那么最终x、y、z的值在多个节点中都是一致的。

2.2 重要术语

2.2.1 前置术语

• 所有节点上持久化的变量（在响应RPC请求之前变更且持久化的变量）
  • currentTerm
    服务器的任期，初始为0，递增
  • votedFor
    当前获得选票的候选人的 Id
  • log[]
    日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的Term任期号
• 所有节点上非持久化的变量
  • commitIndex
    最大的已经被commit的日志的index
  • lastApplied
    最大的已经被应用到状态机的index
• Leader节点上非持久化的变量（选举后重新初始化）
  • nextIndex[]
    每个节点下一次应该接收的日志的index（初始化为Leader节点最后一个日志的Index + 1）
  • matchIndex[]
    每个节点已经复制的日志的最大的索引（初始化为0，之后递增）
• RequestVote
  用于Candidate获取选票，candidate 在选举过程中发起，收到 quorum (多数派）响应后，成为 leader。
  • 发送参数如下：
    • term Candidate的任期
    • candidateId Candidate的ID
    • lastLogIndex Candidate最后一条日志的索引
    • lastLogTerm Candidate最后一条日志的term
  • 响应参数如下：
    • term 当前任期，用于Candidate根据条件判断后决定是否更新自己的term
    • voteGranted true表示给Candidate投票，false表示投的别人
• AppendEntries
  附加日志，leader用来发送日志和心跳的机制
  • term
    Leader节点的任期
  • leaderId
    Leader节点的ID
  • prevLogIndex
    此次追加请求的上一个日志的索引，用于保证收到的日志是连续的
  • prevLogTerm
    此次追加请求的上一个日志的任期，用于保证收到的日志是连续的
  • entries[]
    此次追加的日志（空则为心跳请求）
  • leaderCommit
    Leader上已经Commit的Index
• AppendEntries的返回值
  • term
    当前任期号，用于Leader节点更新自己的任期。具体来说，如果这个返回值比Leader自身的任期大，那么Leader需要更新自己的任期。
  • success
    如果Follower节点匹配prevLogIndex和prevLogTerm，返回true。如果没找到，返回false，需要Leader重发更早的prevLogIndex和prevLogTerm，具体可以看5.2.8 log复制的本质中的原则二的例子。
• election timeout
  选举超时，如果 follower 在一段时间内没有收到任何消息(追加日志或者心跳)，就是选举超时。

2.2.2 角色

• Leader（主节点）：接受 client 更新请求，写入本地日志文件，然后同步到其他副本中
  • 一旦选举完成：发送心跳给所有节点；在空闲的周期内不断发送心跳保持Leader身份
  • 如果收到客户端的写请求，将日志追加到本地log，在日志被应用到状态机后响应给客户端
  • 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex，那么：发送从 nextIndex 开始的所有日志条目：
    • 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
    • 如果因为日志不一致而失败，减少 nextIndex 重试
    • 如果存在一个满足N > commitIndex的 N，并且大多数的matchIndex[i] ≥ N成立，并且log[N].term == currentTerm成立，那么令commitIndex等于这个N
• Follower（从节点）
  • 响应来自Leader的更新请求然后写入本地日志文件，并在Leader收到过半节点成功响应广播Commit请求之后，进行日志Commit
  • 响应来自Candidate的RPC请求
  • 对客户端提供读请求
  • 如果在选举超时周期内没有收到AppendEntries的请求或者给Candidate投票，转换为Candidate角色
• Candidate（候选节点）
  • 如果 follower 在一段时间内未收到 leader 心跳，则判断 leader 可能故障，发起选主提议。节点状态从 Follower 变为 Candidate 状态，开始选举，直到选主结束。
  • 转换为candidate角色，开始选举：
    • 递增currentTerm
    • 给自己投票
    • 重置选举时间
  • 发送RequestVote给其他所有节点
  • 如果收到了大多数节点的选票都是投本节点，转换为Leader节点
  • 如果收到Leader节点的AppendEntries请求，转换为Follower节点
  • 如果选举超时，重新开始新一轮的选举

2.2.3 状态转换

1. Follower (starts up)
   所有节点初始状态都是Follower角色
2. Follower -> Candidate (timest out, starts election)
   Follower在超时时间内没有收到Leader的请求则转换为Candidate进行选举
3. Candidate -> Candidate (timest out, new election)
   Candidate在选举过程中等待其他节点发送的投票超时，开启新一轮选举投票
4. Candidate -> Leader (receives votes from majority of servers)
   Candidate收到大多数节点的选票则转换为Leader；
5. Candidate -> Follower (discovers current leader or new term)
   Candidate发现Leader（收到Leader节点的AppendEntries请求）或者收到更高term任期的请求，转换为Follower
6. Leader -> Follower (discovers server with higher term)
   Leader在收到更高term任期的请求后转换为Follower

2.2.4 任期

• termId
  Raft把时间切割为一个个任意长度的任期，每个任期都产生一个新的 termId，采用连续的整数。
• 每一个term的开始都是Leader选举，一个任期内只有一个 leader，在成功选举Leader之后，Leader会在整个term内管理整个集群。
• 如果Leader选举失败，该term就会因为没有Leader而结束，开始下一轮选举
• termId 相当于 paxos 的 proposalId。

2.3 特性

• Leader 不会修改自身日志，只会做追加操作，日志只能由Leader转向Follower。
  例如：

  1. 即将要down掉的Leader节点A已经提交日志1，未提交日志 2，3。
  2. Leader节点A 挂掉之后，节点 B 启动并当选Leader，最新日志只有 1，然后提交了日志 4。
  3. 但随后节点 A 又恢复了，此时Leader节点 B 的编号 4 日志会同步给节点A从而追加到节点 A 的编号 1 日志的后面，而编号 2，3 的日志就丢失了。

• 不依赖各个节点物理时序保证一致性，而是通过逻辑递增的term-id和log-id保证。

• 所有节点

  • 如果commitIndex > lastApplied，应用log[lastApplied]到状态机，增加lastApplied
  • 如果RPC请求或者响应包含的任期T > currentTerm，将currentTerm设置为T并转换为Follower

2.4 选主

2.4.1 选主契机

• 启动时或接收Leader心跳超时
  服务器启动时初始状态都是follower，如果在超时时间内没有收到leader发送的心跳包，则将其当前term加一然后进入candidate状态等待一段随机的时间后发起一次Leader选举

• Candidate收到大多数节点的选票则转换为Leader；发现Leader或者收到更高任期的请求则转换为Follower

• Leader在收到更高任期的请求后转换为Follower

2.4.2 选主过程

图解选主过程可参考图解：什么是Raft算法

2.4.2.1 选举与任期

如图所示，Raft将时间分为多个 term（任期），term 以连续的整数来标识，每个 term 表示一个选举的开始。

例如Follower 节点 1。在 term1 和 term2 连接处的时间，联系不到Leader，将currentTerm编号加1，变成2，进入了到term2任期，在term2的蓝色部分选举完成，绿色部分正常工作。

当然一个任期不一定能选出Leader，那么会将currentTerm继续加1，然后继续进行选举，例如上图中的t3。

2.4.2.2 选举触发时机

Raft 使用心跳（heartbeat）触发Leader选举。

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

2.4.2.3 选举规则

选举的原则是，每一轮选举每个选民一张选票最开始选自己，投票的请求先到且选民发现候选人节点的日志id大于等于自己的，就会投票，否者不会投票。获得半数以上的票的节点成为主节点（注意这并不是说选出来的事务id一定是最大的）。

如果没有事务id（如刚启动时），就遵循投票请求先来先投。然后Leader将最新的日志复制到各个节点，再对外提供服务。

当然除了这些选举限制，还会有其他的情况。如commit限制等保证，Leader选举成功一定包含所有的commit和log

如果一次投票未选出合适的，则会发生超时，本次term无leader选出，节点会将currentTerm继续加1，等待随机时间后重新投票选举出新的leader。

2.4.2.4 选举流程

1. 初始时所有节点都是Follower
   
2. 在超时时间（为了避免长时间选举竞争，所以这个超时时间是随机的）内没有收到leader的日志(包括心跳)，Follower将状态切换为candidate，自增currentTerm，设置选举超时时间。比如现在Node a最先发现Leader心跳超时，将自己转换为Candidate。
   
3. 向所有节点广播选举请求
   它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC。如下就是Node a给其他节点发了投票RPC。
   
4. 其他Candidate在该Term内还未发送过投票就收到了其他Node发来的投票，则会给发送请求的Candidate进行投票响应,并且重置本节点的选举超时时间设置。
   
5. Candidate广播投票后等待响应，可能会有以下三种情况：
   • 如果收到多数派回应投自己，则成为leader。如下Node a成为了Leader。
     
   • 如果收到leader的心跳，且leader的term >= currentTerm，则自己切换为follower状态，
     否则，保持Candidate身份
   • 如果在超时时间内没有达成多数派，也没有收到leader心跳，则很可能选票被瓜分，则会自增currentTerm，在随机的超时时间后进行新一轮的选举
6. 选举出Leader后，Leader通过定期向所有Followers发送心跳信息维持其统治。Raft保证选举出的Leader上一定具有最新的已提交的日志。
7. 若Follower一段时间未收到Leader的心跳则认为Leader可能已经挂了，再次发起Leader选举过程。

2.4.2.5 选举中的follower流程

1. 如果term < currentTerm，说明有更新的term，返回给candidate。
2. 如果还没有投票，或者candidateId的日志(lastLogTerm,lastLogIndex)和本地日志一样或更新，则投票给它。

注意：一个term周期内，每个节点最多只能投一张票，按照先到先得原则

2.4.2.6 避免选举分裂的保证措施1-随机超时（都投自己时）

多个follower 同时转化成了candidate，投票可能会分裂导致没有一个candidate能获得大多数投票。当此情况出现后，每个candidate将会在随机的time out后开始新的选举并将自己的term加1。那么必须采取其他措施否则这种投票僵持的结果可能会一直持续下去，因为大家都一起投票且都投自己。

比如5个节点ABCDE，leader A 挂掉后，还剩4个节点，raft协议约定，每个服务器在一个term只能投一张票，假设B，D分别有最新的日志，且同时发起选举投票，则可能出现B和D分别得到2张票的情况，如果这样都得不到大多数确认，无法选出leader。

为了避免这种情况发生，raft采用随机的选举超时时间去确保分裂投票很少并能很快解决。随机超时时间从一个固定的区间产生T,2T。

这样一来，由于每个服务器的超时时间不同，则leader挂掉后，超时时间最短且拥有最多日志的follower最先开始选主，并成为leader。一旦candidate成为leader，就会向其他服务器发送心跳包阻止新一轮的选举开始。

2.4.2.7 避免选举分裂的保证措施2（网络分区导致集群分裂时）

我们再来考虑另外一种极端的情况，假设集群因为某些原因（如网络切断）导致集群被切割为两块，有Leader节点的一块继续运行、没有Leader节点的一块则进入选举状态，并选出自己新的Leader节点，如图：

此时c、d、e三个节点组成集群选举产生了新的Leader节点e，并且选举任期更新为2，比节点b更高，同时两个Client分别向这两块集群发起了SET请求。

由于网络分区，所以节点b不能复制到大多数节点，所以一直处于Uncommit状态，而节点c因为能够复制到大多数节点所以可以正常commit。

当集群分裂问题恢复后，原先的Leader节点B收到更高任期Leader请求就会主动下台变为Follower，而A和B两个节点将回滚它们未提交的条目，并匹配新leader节点c的日志，从而实现日志在整个集群中的一致性（实际上是少数节点的集群学习多数节点的集群的leader，进而完成一致性过程）。

2.5 log数据

2.5.1 log格式

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和用于状态机执行的命令。

如果一个日志条目被复制到大多数Follower服务器上，就被认为可以提交（commit）了。

• firstLogIndex/lastLogIndex
  为节点中开始和结束的索引位置（包含提交，未提交，写入状态机）
• applyIndex
  已写入状态机中的索引
• commitIndex
  已提交的索引

2.5.2 log写入和复制过程

Leader选出后，就开始接收客户端的写请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC 复制日志条目（心跳也是用的这种机制，只不过内容为空）。

当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

1. leader收到一个客户端发来的如x=1的请求后，会写入本地日志，然后将x=1的日志广播给所有follower。某些Followers可能没有成功的复制日志，Leader会无限的重试 AppendEntries RPC直到所有的Followers最终存储了所有的日志条目。具体发送的内容是:(term,leaderId,prevLogIndex,prevLogTerm,leaderCommitIndex)
2. follower如果收到请求，会将日志写入本地 log ，然后返回成功给Leader。
3. 当 leader 收到半数以上的节点回应时，会将此日志的状态变为commit，然后广播消息让 follwer commit日志。
4. 节点在 commit 日志后，会更新状态机中的 logindex ，并返回执行结果给客户端，此时集群就现在系统的状态达成了一致。

拆分的看leader流程：

1. 接收到client请求，本地持久化日志
2. 将日志发往各个节点
3. 如果达成多数派，再commit，返回给client。

备注：

• 如果传递给follower的lastLogIndex>=nextIndex,则从nextIndex继续传递，如果返回成功，则更新follower对应的nextIndex和matchIndex；如果失败，则表示follower还差更多的日志，则递减nextIndex，重试
• 如果存在N>commitIndex，且多数派matchIndex[i]>=N, 且log[N].term == currentTerm,
  设置commitIndex=N。

拆分的看Follower处理流程：

1. 比较term号和自身的currentTerm，如果term<currentTerm，则返回false
2. 如果(prevLogIndex,prevLogTerm)不存在，说明还差日志，返回false
3. 如果(prevLogIndex,prevLogTerm)与已有的日志冲突，则以leader为准，删除自身的日志
4. 将leader传过来的日志追加到末尾
5. 如果leaderCommitIndex>commitIndex,说明是新的提交位点，回放日志，设置commitIndex =
   min(leaderCommitIndex, index of last new entry)

备注：默认情况下，如果日志不匹配，会按logIndex逐条往前推进，直到找到match的位置，有一个简单的思路是，每次往前推进一个term，这样可以减少了网络交互，尽快早点match的位置，代价是可能传递了一些多余的日志。

2.5.3 log复制的本质

日志复制的本质是让 Follower 和 Leader 的已提交的日志顺序和内容都完全一样，用于保证一致性，具体的原则：

• 内容相同原则：两个日志在不同的 raft 节点中，如果有两个相同的 term 和 logIndex，则保证两个日志的内容完全一样（存储着相同命令）。
• 顺序性相同原则：两段日志在不同的 raft 节点中，如果他们的起始和终止 term，logIndex 都相同，那么两段日志中日志内容完全一样。
• Leader Append-Only原则：leader永远不会覆盖或删除自己的日志

如何保证

• 第一个原则只需要在创建 logIndex 的时候使用新的 logIndex，保证 logIndex 的唯一性,而且创建之后不去更改，那么在 leader 复制到 follower 之后，logIndex，term 和日志内容都没变。

• 第二个原则，在 Leader 复制给 Follower 时，要传递当前最新日志 currenTermId 和currentLogIndex，以及上一条日志 preCurrentTermId 和 preCurrentLogIndex。

  follwer接收日志时，会在相同任期号和索引位置找前一条日志，如果存在且匹配，则接收日志；否则拒绝，leader会减少日志索引位置并进行重试，直到某个位置与follower达成一致。然后follower删除索引后的所有日志，并追加leader发送的日志，一旦日志追加成功，则follower和leader的所有日志就保持一致。只有在多数派的follower都响应接受到日志后，表示事务可以提交，才能返回客户端提交成功。

  如下图，在 d 节点，term7，logIndex12。在给节点节点 a 同步时，发送(term7，logIndex11)，(term7，logIndex12),a 节点没有找到(term7，logIndex11)的日志，会让Leader，d 节点重新发送。d 节点会重新发（term6，logIndex10）(term7，logIndex11)，还是没有(term6，logIndex10)的日志,依然会拒绝同步。接着发(term6，logIndex9)(term6，logIndex10)。现在a节点有了(term6，logIndex9)。那么 leader节点就会将(term6，logIndex9) ~ (term7，logIndex11)日志内容给节点 a，节点 a 将会和节点d有一样的日志。
  
  上图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目，也有可能包含一些Leader没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

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

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

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

• 怎么找最近一致的点：
  leader节点为每一个follower节点维护了一个nextIndex.当一个节点选举成为leader后，leader 为所有follower 维护的nextIndex都是leader节点日志最新index值的后一个值(即 last index + 1)
  
  如果follower节点与leader日志不一致，AppendEntries一致性检查将在下一次AppendEntries RPC时失败。

  在follower拒绝后，leader将nextIndex减1，然后再重试AppendEntries RPC。

  最终nextIndex会到达一个两者日志匹配的点。找到后，删除Follower的冲突日志条目，然后追加从leader中过来的日志的AppendEntries将会成功。一旦成功，follower与leader两者日志一致，在接下来的其他term也将仍然按此逻辑进行。

3 Zab

Zookeeper的核心是原子广播，这个机制保证了各个Server之间的同步。实现这个机制的协议叫做Zab协议。

Paxos 虽然解决了分布式系统中，多个节点就某个值达成一致性的通信协议。但是还是引入了其他的问题。由于其每个节点，都可以提议提案，也可以批准提案。当有三个及以上的 proposer 在发送 prepare 请求后，很难有一个 proposer 收到半数以上的回复而不断地执行第一阶段的协议，在这种竞争下，会导致选举速度变慢。

所以 zookeeper 在 paxos 的基础上，提出了 ZAB 协议，本质上是，只有一台机器能提议提案（Proposer），而这台机器的名称称之为 Leader 角色。其他参与者扮演 Acceptor 角色。为了保证 Leader 的健壮性，引入了 Leader 选举机制。

ZAB协议还解决了这些问题

• 在半数以下节点宕机，依然能对台提供服务
• 客户端所有的写请求，交由 Leader 来处理。写入成功后，需要同步给所有的 follower 和 observer
• leader 宕机，或者集群重启。需要确保已经被 Leader 提交的事务最终都能被服务器提交，并且确保集群能快速回复到故障前的状态

可参考ZooKeeper的工作原理

4 协议对比

4.1 Raft对比Multi-Paxos

4.2 Raft对比Zab

4.2.1 请求的处理方式不同

• 建立连接对象不同

  • Zk集群中的client和任意一个Node建立TCP的长连接，完成所有的交互动作；
  • 而Raft第一次随机的获取到一个节点，然后找到Leader，后续直接和Leader交互

• sync

  • Zk中的读请求，直接由客户端连接的那个Node处理，不需要和leader汇报，也就是Consul中的stale模式。这种模式可能导致读取到的数据是过时的，但是可以保证一定是半数节点之前确认过的数据

    为了避免Follower的数据过时，Zk有sync()方法，可以保证读取到最新的数据。可以调用sync()之后，再查询，确保所有的数据一致后再返回结果。

• 角色不同

  • Zk引入了 Observer的角色来提升性能，既可以大幅提升读取的性能（将请求转发给Leader），也可以不影响写的速度和选举的速度，同时一定程度上增加了容错的能力。可参考这里
  • Raft没有这种起负载作用的角色

• 日志和状态机
  Zab和Raft都是同时存在 log[]（还有快照技术）和状态机（内存树）的存储结构。Zab中的日志和Raft中的日志模型很像，都是超过半数节点完成复制之后，该命令才会被commit，再结合半数节点选举confirm之后的节点才有可能成为新leader，这两点保证了集群的一致性。

  • 日志是以log和快照的形式持久化到磁盘，保存的是数据写的完整过程，为重启加载历史数据提供了便利，避免了服务器宕机造成的数据丢失。
  • 状态机（内存树）把数据加载到内存中，避免了查询操作时磁盘读取，读取的是数据的最终值，从而提升读取的性能

4.2.2 选主投票的区别

• 信息流向不同

  • Zk集群之间投票消息是单向、网状的，类似于广播。
    比如A广播 A投票给自己，然后B接收到A的这个消息之后，会PK A的数据，如果B更适合当leader（数据更新或者myid更大），B会归档A的这个投票，但是不会更新自己的数据，也不会广播任何消息，除非发现A的数据比B当前存储的数据更适合当leader，就更新自己的数据，且广播自己的最新的投票消息（A）。
  • 而Raft集群之间的所有消息都是双向的，发起一个RPC，会有个回复结果。
    比如A向B发起投票，B要么反馈投票成功，要么反馈投票不成功。

• 一个任期内可投票次数不同

  • ZK集群中，一个节点在一个epoch下是可以发起多次投票的。当节点发现有比之前更新的数据更适合的leader时，就会广播自己的最新投票消息，结合recvset这个Set的票箱结构，来更新某个结点最新的投票结果。
  • 而Raft的follower在一个term里只能投票一次。如果没选出来，就增加term再次投票。

• 成为leader的必要条件不同

  • ZK集群中，因为引入了myid的概念，系统倾向让数据最新和myid最大的节点当leader，所以即使有半数节点都投票给同一个Node当leader，这个Node也不一定能成为leader，需要等待200ms，看是不是有更适合的leader产生，当然如果可能因为网络原因 数据最新 myid最大的节点也不一定能当选为leader。
  • 但是在Raft系统中，只要某个candidate发现自己投票过半了，就一定能成为leader

• 选举成功的term数不同

  • ZK集群中，每一轮的选举一定会选出一个leader
    因为每个节点允许多次投票，而且会广播自己的最新投票结果。
  • 而Raft系统可能涉及选票瓜分，需要重新发起一轮选举才能选出leader，是通过选举超时时间的随机来降低选票瓜分的概率。
  • 所以ZK的选举理论上一般需要花费更多的时间，但是只需要一轮。Raft每一轮选举的时间是大致固定的，但是不一定一轮就能选出leader。

• ZK集群中，成为公认的leader条件更苛刻，raft模式下，只要新leader发一个命令为空的Log出来，大家就会认同这个节点为leader，但是在ZK集群中，追随leader的2种条件都很苛刻
  要么recvset中半数节点的选举following投票给A，才会认可A为自己的leader
  要么outofelection中半数节点都认可A为leader，自己才会认可A为自己的leader

4.2.3 事务操作的区别

• 事务操作分解不同

  • Raft系统中的事务消息是通过双向的RPC来完成的
  • 而Zab中，则是单向的，一来一回两个消息来完成的。
  • 明显Zab的性能更加，不需要浪费leader一个线程去等待follower完成业务操作。
    Zab中leader发送一个Proposal消息给follower，发送完成。当follower完成proposal过程时，再发送一个消息ACK到leader，发送完成。leader统计ACK数量过半时，触发广播commit给所有follower。

• 操作流程当中，Zab的即时性做的更好。

  • Raft的集群模式下：
    Leader创建日志，广播日志，半数节点复制成功后，自己commit日志，运用到状态机中，反馈客户端，并且在下一个心跳包中，通知小弟们commit
  • Zab的集群模式下：
    leader创建Proposal，广播之后，半数节点复制成功后，广播commit。同时自己也commit，commit完之后再运用到内存树，反馈客户端

更多好文

Raft

关于Raft的更多讨论可参考:

• Raft算法概述
• Raft 一致性算法
• Raft各流程详述