作者： 京东物流 郭益如

导读

在分布式体系中， 什么是拜占庭将军问题？发生的场景和处理计划是什么？什么是 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 节点状况图：

拜占庭将军问题和 Raft 共识算法讲解

图1 Raft 节点状况图

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

2.1.4 任期 Term

Raft 把时刻分割成恣意长度的任期 Term，用接连的整数符号。

拜占庭将军问题和 Raft 共识算法讲解

图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。

拜占庭将军问题和 Raft 共识算法讲解

图3 主从节点进行 Entry 仿制

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

2.3.1 日志同步流程

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

拜占庭将军问题和 Raft 共识算法讲解

图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 或许会导致数据丢掉：

拜占庭将军问题和 Raft 共识算法讲解

图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 的共同算法。经过将共同问题拆分成主节点推举和主从日志同步，以及安全流程，来提高分布式体系的数据共同性、可靠性和容错性；首要推举主节点，然后主节点担任接收外部恳求、数据仿制、提交，确保体系中数据都是共同的。