关于raft:拜占庭将军问题和-Raft-共识算法讲解

作者：京东物流 郭益如

导读

在分布式系统中，什么是拜占庭将军问题？产生的场景和解决方案是什么？什么是 Raft 共识算法？Raft 算法是如何解决拜占庭将军问题的？其外围原理和算法逻辑是什么？除了 Raft，还有哪些共识算法？共识问题作为分布式系统的一大难点和痛点，本文次要介绍了其产生的背景、起因，以及通用的 Raft 算法解决方案。

01 拜占庭将军问题

【分布式对等网络中的通信容错问题。

在分布式计算中，不同的计算机通过通信替换信息达成共识依照一套合作策略口头。有时候，零碎中的成员计算机可能出错而发送谬误的信息，用于传递信息的通信网络也可能导致信息损坏，使得网络中不同的成员对于整体合作的策略得出不同论断，从而毁坏零碎一致性，这就是拜占庭将军问题。

拜占庭将军问题被认为是容错性问题中最难的问题类型之一。】

9 位将军兵分 9 路去打仗，他们各自有势力观测敌情并做出口头判断 —— 防御或撤退，他们必须口头统一，即所有军队一起防御或者一起撤退，否则局部防御局部撤退会造成灾难性结果。

前提：

1. 将军之间只能通过信使互相联系，每位将军将本人的判断发送给其余将军，并接管其余将军发送的判断；
2. 收到信息的将军综合所有的判断，当超过半数都抉择防御时，就决定防御，当超过半数都抉择撤退时就决定撤退；

问题是，将军两头可能呈现叛徒，他可能会抉择相同的后果进行通信（投票），也可能选择性的发送信息，叛徒要达成的指标是：

1. 选择性的发送信息，坑骗某些将军采取防御的口头；
2. 促成一个谬误的决定，比方将军们不心愿防御时防御；
3. 蛊惑某些将军，使得他们无奈做出决定；

如果叛徒达成了其中之一，任何的攻打后果都是注定要失败的，只有齐全达成统一的致力能力获得胜利。

比方，可能 9 位将军中有 8 位虔诚的将军和一名叛徒，8 位将军中 4 位抉择防御，4 位抉择撤退，叛徒别离给抉择防御的将军发送防御的信息，给抉择撤退的将军发送撤退信息。这样一来，在 4 位抉择防御的将军看，共 5 位将军抉择防御，从而发动防御；而在 4 位抉择撤退的将军看，共 5 位将军抉择撤退，从而发动撤退，这样各个将军的一致性就受到了毁坏。

并且，叛徒将军可能会伪造其余将军的身份发送函件；

拜占庭将军问题形容的是，在存在信息失落的不牢靠信道上试图通过消息传递的形式达到一致性是不可能的，在零碎中除了存在的音讯提早或不可送达故障外，还可能包含音讯篡改、节点解决异样等潜在性异样。

1.1 拜占庭容错

在晚期的解决方案中，一种是 “拜占庭容错”，它遵循“多数遵从少数”的共识机制，即便呈现了谬误或伪造的信息，只有有问题的将军数量不到 1/3，仍能够达到“拜占庭容错”，使整个零碎便能够失常运作。

为什么是 1/ 3 呢？

其原理是这样的，假如将军总数是 N，其中耿直的将军数量是 S，叛变的将军数量是 T，那么 N=S+T；

为了保障即便叛变的将军都不去投票也能产生最终的后果，那么 S 必须要超过半数，这种状况下，S 都做出雷同的抉择，仍然能够达成共识，即 S>T；

如果叛徒给一半反对防御的将军发送防御信息，给一半反对撤退的将军发送撤退信息，这种状况要保障也能产生最终的投票后果，则 X > S/2 + E；

综合以上关系，能够失去：

N = S + T

X < S

X > S/2 + T

求解以上不等式，能够失去：

(N-T)/2 > T，即 N > 3T

所以要保障耿直的将军至多占所有将军总数的 2/3，才有可能达成共识。

1.2 拜占庭算法

拜占庭算法是一种共识算法，确定共识的准则，各个节点通过这个共识准则既能够保障一致性，又能保障根本的分区容错性。

共识是可容错零碎中的一个根本问题：即便面对故障，服务器如何在共享状态上达成统一？

02 Raft 算法

了解，首先 MCube 会根据模板缓存状态判断是否须要网络获取最新模板，当获取到模板后进行模板加载，加载阶段会将产物转换为视图树的构造，转换实现后将通过表达式引擎解析表达式并获得正确的值，通过事件解析引擎解析用户自定义事件并实现事件的绑定，实现解析赋值以及事件绑定后进行视图的渲染，最终将指标页面展现到屏幕。

【Raft 算法解决的是简化版的拜占庭将军问题，即在不思考数据失落、篡改的状况下的拜占庭将军问题。】

假如当初有 3 位将军 A、B、C，将军中没有叛徒，信使的信息牢靠，但有可能被暗杀，此时将军们如何达成防御的一致性决定？

计划： Raft 的计划是，在所有的将军中选出一个大将军，用来做出所有的决定。大将军派信使给其余将军，如果过一段时间没有回复（可能被暗杀）就再派一个信使，直到收到回复。

如果大将军的信使，派出去一个被干掉一个，其余将军们总也收不到大将军的信息，他们如何达成一致性决定？

计划： 每位将军都有一个随机工夫的计时器，工夫一到，他就把本人当成大将军的候选人，派信使将选举后果给将军 B、C。如果将军 B、C 还没有把选举大将军后果投给其他人（包含本人）时，他们就会把选举票投给 A。A 将军的信使返回 A 时，A 将军就晓得本人收到了足够的票数，成为了新的大将军。

Raft 算法是一种简略易懂的共识算法，它通过首先选举一个 Leader 主节点，而后让 Leader 齐全负责数据同步，依附状态机和主从同步的形式，在各个节点之间实现数据的一致性。

通过这种主节点进行数据同步的形式，Raft 将一致性问题拆分成了三个绝对独立的子问题：

1. 主节点选取 Leader Election： 启动集群时，或者现有主节点失败时，会启动新的投票，取得大多数选票（N/2+1）的节点会成为新的主节点；

2. 复制日志 Log Replication： 主节点从客户端接管日志信息，再把信息复制到其余从节点上，使得日志信息都能保持数据统一；

3. 安全性： Raft 定义了一系列标准来保证数据安全性。

2.1 Raft 节点

Raft 算法为节点定义了三种角色：Leader（主节点）、Follower（从节点）、Candidate（参加投票竞争的节点），节点的角色是能够转换的，在任意的工夫，每个服务器肯定处于三种状态中的一个。

每个节点上都有一个倒计时器（Election Timeout），随机值在 150ms ~ 300ms 之间，当节点收到选举申请，或收到 Leader 的 Heartbeat 时，就会重置倒计时。

2.1.1 主节点 Leader

通常状况下，零碎中只有一个主节点，用来发动心跳，解决所有的客户端申请，创立日志和同步日志。

2.1.2 从节点 Follower

除主节点外，其余的节点都是从节点，用于接管主节点的心跳和日志数据，保障其数据状态与主节点统一，以及在 Leader 选举时，投票给 Candidate。

如果有客户端跟 Follower 分割，那么 Follower 会把申请重定向给 Leader。

2.1.3 候选人 Candidate

候选人 Candidate 是在 Leader 选举过程中的长期角色，由 Follower 转换而来，用于发动投票参加竞选。

Raft 节点状态图：

[]()

图 1 Raft 节点状态图

启动时，或 Follower 接管不到 Leader 信息时，它就会变成 Candidate 并发动一次选举。取得集群中大多数选票的 Candidate 就成为新的 Leader。

2.1.4 任期 Term

Raft 把工夫宰割成任意长度的任期 Term，用间断的整数标记。

[]()

图 2 各任期 Term 下的状态演变

每一个任期都会开始一次新的选举，一个或多个 Candidate 会尝试成为 Leader。如果一个 Candidate 博得了选举，它就会在该任期内负责 Leader，直到任期完结或者服务器宕机。在某些状况下，没有选出 Leader（如选票瓜分等），则会开启下一个任期并立即开始新的选举。

任期在 Raft 算法中充当逻辑时钟的作用，每一个节点都会存储以后的 Term 号，这一编号在整个集群期间内枯燥增长，服务器之间通信的时候也会替换以后的 Term 号：

• 如果一个节点发现其 Term 号比其余服务器小，那么它会更新本人的 Term 号到较大的值；
• 如果一个 Candidate 或者 Leader 发现其 Term 号过期了，那么它会立刻复原成 Follower 状态；
• 如果一个节点接管到的申请中 Term 号过期了，那么它会间接回绝此次申请。

Raft 算法中服务器节点之间通信应用近程过程调用（RPCs），并且根本的一致性算法只须要两种类型的 RPCs。申请投票（RequestVote）RPCs 由候选人在选举期间发动，而后附加条目（AppendEntries）RPCs 由领导者发动，用来复制日志和提供一种心跳机制。如果未及时收到响应，则请求者有责任重试 RPC。

2.1.5 事件 Entry

每一个事件是一个 Entry，只有 Leader 能够创立 Entry，构造为 <term, index, cmd> 其中 cmd 是能够利用到状态机的操作。

2.1.6 日志 Log

日志是 Raft 的外围概念，是一个由 Entry 形成的数组。只有 Leader 才能够扭转其余节点的 Log。Leader 先把 Entry 增加到本人的 Log 数组中，发动共识申请，取得批准后，才会将 Entry 提交给状态机。Follower 只能从 Leader 中获取新日志和以后的 CommitIndex，而后把对应的 Entry 利用到本人的状态机中。

2.2 选取主节点 Leader Election

2.2.1 选举机制

• raft 通过心跳机制来触发 Leader 的选举；

<!—->

• Leader 会向所有的 Follower 周期性发送心跳来保障本人的 Leader 位置。

<!—->

• 如果服务器可能收到来自 Leader 或者 Candidate 的无效信息，那么它会始终放弃为 Follower 状态，并且刷新本人的 electionElapsed，从新计时。

<!—->

• 如果一个 Follower 在一个周期内没有收到任何信息，也就是选举超时，它就会认为此时没有可用的 Leader，开始进行一次选举以选出一个新的 Leader。
• 当服务器启动时，所有的节点都是 Follower。

2.2.2 选举过程

Follower 自增的 term 号并且转换状态为 Candidate。而后他会向所有节点发动 RequestVoteRPC 申请，Candidate 的状态会继续到以下状况产生：

• 取得大多数选票（N/2 +1），博得选举，成为 Leader
• 其余节点博得选举
• 一轮选举完结，无人胜出

在 Candidate 期待选票的时候，它可能收到其余节点申明其是 Leader 的心跳：

• 该 Leader 的 term 号大于等于本人的 term 号，阐明对方曾经成为 Leader，则本人回退为 Follower。
• 该 Leader 的 term 号小于本人的 term 号，那么会回绝该申请并让该节点更新 term。

为了避免出现“脑裂”，即同一时刻呈现多个 Candidate，导致没有 Candidate 取得大多数选票的情况，Raft 减少了随机选举超时工夫的办法。每一个 Candidate 在发动选举后，都会随机化一个超时工夫（150-300 毫秒），使得各个服务器分散开来，在大多数状况下只有一个服务器会率先超时，博得选举。

相干代码实现：

【plain】func (rf *Raft) RequestVote(request *RequestVoteRequest, response *RequestVoteResponse) {rf.mu.Lock()
  defer rf.mu.Unlock()
  defer rf.persist()
  defer DPrintf("{Node %v}'s state is {state %v,term %v,commitIndex %v,lastApplied %v,firstLog %v,lastLog %v} before processing requestVoteRequest %v and reply requestVoteResponse %v", rf.me, rf.state, rf.currentTerm, rf.commitIndex, rf.lastApplied, rf.getFirstLog(), rf.getLastLog(), request, response)




  if request.Term < rf.currentTerm || (request.Term == rf.currentTerm && rf.votedFor != -1 && rf.votedFor != request.CandidateId) {
    response.Term, response.VoteGranted = rf.currentTerm, false
    return
  }
  if request.Term > rf.currentTerm {rf.ChangeState(StateFollower)
    rf.currentTerm, rf.votedFor = request.Term, -1
  }
  if !rf.isLogUpToDate(request.LastLogTerm, request.LastLogIndex) {
    response.Term, response.VoteGranted = rf.currentTerm, false
    return
  }
  rf.votedFor = request.CandidateId
  rf.electionTimer.Reset(RandomizedElectionTimeout())
  response.Term, response.VoteGranted = rf.currentTerm, true
}


func (rf *Raft) StartElection() {request := rf.genRequestVoteRequest()
  DPrintf("{Node %v} starts election with RequestVoteRequest %v", rf.me, request)
  // use Closure
  grantedVotes := 1
  rf.votedFor = rf.me
  rf.persist()
  for peer := range rf.peers {
    if peer == rf.me {continue}
    go func(peer int) {response := new(RequestVoteResponse)
      if rf.sendRequestVote(peer, request, response) {rf.mu.Lock()
        defer rf.mu.Unlock()
        DPrintf("{Node %v} receives RequestVoteResponse %v from {Node %v} after sending RequestVoteRequest %v in term %v", rf.me, response, peer, request, rf.currentTerm)
        if rf.currentTerm == request.Term && rf.state == StateCandidate {
          if response.VoteGranted {
            grantedVotes += 1
            if grantedVotes > len(rf.peers)/2 {DPrintf("{Node %v} receives majority votes in term %v", rf.me, rf.currentTerm)
              rf.ChangeState(StateLeader)
              rf.BroadcastHeartbeat(true)
            }
          } else if response.Term > rf.currentTerm {DPrintf("{Node %v} finds a new leader {Node %v} with term %v and steps down in term %v", rf.me, peer, response.Term, rf.currentTerm)
            rf.ChangeState(StateFollower)
            rf.currentTerm, rf.votedFor = response.Term, -1
            rf.persist()}
        }
      }
    }(peer)
  }
}

2.3 日志同步 Log Replication

Raft 通过 Leader 向集群中所有 Follower 进行日志同步来保障整个集群数据的最终一致性。

只有 Leader 有权限承受客户端的申请并且同步数据给集群中其余节点。每一个客户端的申请都蕴含一条须要被复制状态机 RSM（Replicated State Mechine）执行的命令，Leader 收到客户端申请后，会生成一个 Entry，蕴含，再将这个 entry 增加到本人的日志开端后，向所有的节点播送该 Entry，要求其余服务器复制这条 Entry。

[]()

图 3 主从节点进行 Entry 复制

如图所示，Logs 日志是一个顺序存储的 Entry 数组，方框内是任期 Term 号。

2.3.1 日志同步流程

例如，在 Term3 中，Leader 最初一个 Entry 的 Index 为 7，x 值为 5，收到申请 set x= 4 时：

[]()

图 4 日志同步流程

1. Leader 收到客户端申请 x←4 时，Leader 会生成一条新的 Entry<8, 3, set x=4>，并将该 Entry 增加到本人的 Log 数组最初
2. Leader 通过 AppendEntries RPC 播送该 Entry；
3. 如果 Follower 承受该 Entry，则会将 Entry 增加到其日志前面，同时返回给 Leader 批准。
4. 如果 Leader 收到了少数的胜利响应，Leader 认为这个 Entry 是 committed，利用到本人的状态机 RSM 中，并且向客户端返回执行后果。之后，该 commited 信息会随着之后的 AppendEntryRPC 传达到其余节点。
5. committed 示意被 Leader 创立的 Entry 曾经复制到了大多数的服务器上，Leader 会跟踪它记录的最大索引值 Index，并在之后的 AppendEntries RPC（包含心跳）中，蕴含该索引值，以此确保其余服务器同步这个 Entry 曾经提交，Follower 接管到该信息后，也会按程序同步更新到本地的状态机中。

Raft 通过这种日志机制来保障不同服务器上日志的一致性和安全性：

• 在两个日志里，有两个 entry 领有雷同的 index 和 term，那么它们肯定有雷同的 cmd；
• 在两个日志里，有两个 entry 领有雷同的 index 和 term，那么它们后面的 entry 也肯定雷同。

2.3.2 Leader Crash

个别状况下，Leader 和 Follower 的日志保持一致，AppendEntries 的一致性查看通常不会失败。而后，Leader Crash 可能会导致数据失落：

[]()

图 5 Leader Crash 时的数据情况

当最下面的 Leader 掌权后，Follower 日志可能有 a~f 几种状况：

1. 日志失落（a，b）；

2. Follower 含有未提交数据（c、d）；

3. 日志失落 + Follower 含有未提交数据（e、f）；

场景 f 可能呈现的状况为：

如果一台服务器在 Term2 时是 Leader，并且向它的日志中增加了一些数据条目，而后在数据提交前宕机了；接着该 Leader 很快重启后，又称为了任期 3 的 Leader，接着又向它的日志中增加了一些数据，而后在 Term2，Term3 数据条目提交前，又宕机了，之后始终处于宕机状态，直到有新的 Leader 产生。

当遇到这种一致性查看失败的状况时，Leader 通过强制 Follower 复制本人的日志来解决日志的不统一。这就意味着，在 Follower 上的抵触日志会被领导者的日志 笼罩。

Leader 找到 Follower 与它日志统一的中央（Index=3），而后删除 Follower 在该地位之后的日志，接着把这之后的日志发送给 Follower：

Leader 给每一个 Follower 保护了一个 nextIndex，它示意 Leader 将要发送给该追随者的下一条日志条目标索引。当一个 Leader 开始掌权时，它会将 nextIndex 初始化为它的最新的日志条目索引数 +1。如果一个 Follower 的日志和 Leader 的不统一，AppendEntries 一致性查看会在下一次 AppendEntries RPC 时返回失败。在失败之后，Leader 会将 nextIndex 递加而后重试 AppendEntries RPC。最终 nextIndex 会达到一个 Leader 和 Follower 日志统一的中央。这时，AppendEntries 会返回胜利，Follower 中抵触的日志条目都被移除了，并且增加所短少的上了 Leader 的日志条目。一旦 AppendEntries 返回胜利，Follower 和 Leader 的日志就统一了，这样的状态会放弃到该任期完结。

相干实现代码：

【plain】func (rf *Raft) replicateOneRound(peer int) {rf.mu.RLock()
  if rf.state != StateLeader {rf.mu.RUnlock()
    return
  }
  prevLogIndex := rf.nextIndex[peer] - 1
  if prevLogIndex < rf.getFirstLog().Index {
    // only snapshot can catch up
    request := rf.genInstallSnapshotRequest()
    rf.mu.RUnlock()
    response := new(InstallSnapshotResponse)
    if rf.sendInstallSnapshot(peer, request, response) {rf.mu.Lock()
      rf.handleInstallSnapshotResponse(peer, request, response)
      rf.mu.Unlock()}
  } else {
    // just entries can catch up
    request := rf.genAppendEntriesRequest(prevLogIndex)
    rf.mu.RUnlock()
    response := new(AppendEntriesResponse)
    if rf.sendAppendEntries(peer, request, response) {rf.mu.Lock()
      rf.handleAppendEntriesResponse(peer, request, response)
      rf.mu.Unlock()}
  }
}


func (rf *Raft) AppendEntries(request *AppendEntriesRequest, response *AppendEntriesResponse) {rf.mu.Lock()
  defer rf.mu.Unlock()
  defer rf.persist()
  defer DPrintf("{Node %v}'s state is {state %v,term %v,commitIndex %v,lastApplied %v,firstLog %v,lastLog %v} before processing AppendEntriesRequest %v and reply AppendEntriesResponse %v", rf.me, rf.state, rf.currentTerm, rf.commitIndex, rf.lastApplied, rf.getFirstLog(), rf.getLastLog(), request, response)


  if request.Term < rf.currentTerm {
    response.Term, response.Success = rf.currentTerm, false
    return
  }


  if request.Term > rf.currentTerm {rf.currentTerm, rf.votedFor = request.Term, -1}


  rf.ChangeState(StateFollower)
  rf.electionTimer.Reset(RandomizedElectionTimeout())


  if request.PrevLogIndex < rf.getFirstLog().Index {
    response.Term, response.Success = 0, false
    DPrintf("{Node %v} receives unexpected AppendEntriesRequest %v from {Node %v} because prevLogIndex %v < firstLogIndex %v", rf.me, request, request.LeaderId, request.PrevLogIndex, rf.getFirstLog().Index)
    return
  }


  if !rf.matchLog(request.PrevLogTerm, request.PrevLogIndex) {
    response.Term, response.Success = rf.currentTerm, false
    lastIndex := rf.getLastLog().Index
    if lastIndex < request.PrevLogIndex {response.ConflictTerm, response.ConflictIndex = -1, lastIndex+1} else {firstIndex := rf.getFirstLog().Index
      response.ConflictTerm = rf.logs[request.PrevLogIndex-firstIndex].Term
      index := request.PrevLogIndex - 1
      for index >= firstIndex && rf.logs[index-firstIndex].Term == response.ConflictTerm {index--}
      response.ConflictIndex = index
    }
    return
  }


  firstIndex := rf.getFirstLog().Index
  for index, entry := range request.Entries {if entry.Index-firstIndex >= len(rf.logs) || rf.logs[entry.Index-firstIndex].Term != entry.Term {rf.logs = shrinkEntriesArray(append(rf.logs[:entry.Index-firstIndex], request.Entries[index:]...))
      break
    }
  }


  rf.advanceCommitIndexForFollower(request.LeaderCommit)


  response.Term, response.Success = rf.currentTerm,True
}

2.3.3 安全性

Leader 须要保障其存储全副曾经提交的日志条目，保障日志条目只能从 Leader 流向 Follower，且 Leader 永远不会笼罩曾经存在的日志条目。

每个 Candidate 发送 RequestVoteRPC 时，都会带上最初一个 Entry 的信息。所有节点收到投票信息时，会对该 Entry 进行比拟，如果发现自己的更新，则回绝投票给该 Candidate。

03 其余一致性算法

了解，首先 MCube 会根据模板缓存状态判断是否须要网络获取最新模板，当获取到模板后进行模板加载，加载阶段会将产物转换为视图树的构造，转换实现后将通过表达式引擎解析表达式并获得正确的值，通过事件解析引擎解析用户自定义事件并实现事件的绑定，实现解析赋值以及事件绑定后进行视图的渲染，最终将指标页面展现到屏幕。

3.1 Paxos 算法

晚期的共识算法，由拜占庭将军问题的提出者 Leslie Lamport 所创造。谷歌的分布式锁服务 Chubby 就是以 Paxos 算法为根底。

3.2 ZAB 算法

Zookeeper 所应用的一致性算法，在流程上和 Raft 算法比拟靠近。

3.3 PBFT 算法

区块链技术所应用的共识算法之一，实用于公有链的共识。

04 总结

了解，首先 MCube 会根据模板缓存状态判断是否须要网络获取最新模板，当获取到模板后进行模板加载，加载阶段会将产物转换为视图树的构造，转换实现后将通过表达式引擎解析表达式并获得正确的值，通过事件解析引擎解析用户自定义事件并实现事件的绑定，实现解析赋值以及事件绑定后进行视图的渲染，最终将指标页面展现到屏幕。

Raft 算法是很宽泛的强一致性、去中心化和高可用的分布式协定，是一种 leader-based 的共识算法。通过将共识问题拆分成主节点选举和主从日志同步，以及平安流程，来进步分布式系统的数据一致性、可靠性和容错性；首先选举主节点，而后主节点负责接管内部申请、数据复制、提交，保证系统中数据都是统一的。