拜占庭將軍問題和Raft 共識算法講解- 京東雲開發者的個人空間- 科技資訊
作者： 京東物流郭益如
在分佈式系統中， 什麼是拜占庭將軍問題？產生的場景和解決方案是什麼？什麼是Raft 共識算法？ Raft 算法是如何解決拜占庭將軍問題的？其核心原理和算法邏輯是什麼？除了Raft，還有哪些共識算法？共識問題作為分佈式系統的一大難點和痛點，本文主要介紹了其產生的背景、原因，以及通用的Raft 算法解決方案。
【分佈式對等網絡中的通信容錯問題。
在分佈式計算中，不同的計算機通過通訊交換信息達成共識按照一套協作策略行動。有時候，系統中的成員計算機可能出錯而發送錯誤的信息，用於傳遞信息的通訊網絡也可能導致信息損壞，使得網絡中不同的成員關於全體協作的策略得出不同結論，從而破壞系統一致性，這就是拜占庭將軍問題。
拜占庭將軍問題被認為是容錯性問題中最難的問題類型之一。 】
9 位將軍兵分9 路去打仗，他們各自有權力觀測敵情並做出行動判斷—— 進攻或撤退，他們必須行動一致，即所有軍隊一起進攻或者一起撤退，否則部分進攻部分撤退會造成災難性後果。
前提：
-
將軍之間只能通過信使互相聯繫，每位將軍將自己的判斷發送給其他將軍，並接收其他將軍發送的判斷；
-
收到信息的將軍綜合所有的判斷，當超過半數都選擇進攻時，就決定進攻，當超過半數都選擇撤退時就決定撤退；
問題是，將軍中間可能出現叛徒，他可能會選擇相反的結果進行通信（投票），也可能選擇性的發送信息，叛徒要達成的目標是：
-
選擇性的發送信息，欺騙某些將軍採取進攻的行動；
-
促成一個錯誤的決定，比如將軍們不希望進攻時進攻；
-
迷惑某些將軍，使得他們無法做出決定；
如果叛徒達成了其中之一，任何的攻擊結果都是注定要失敗的，只有完全達成一致的努力才能獲得勝利。
比如，可能9 位將軍中有8 位忠誠的將軍和一名叛徒，8 位將軍中4 位選擇進攻，4 位選擇撤退，叛徒分別給選擇進攻的將軍發送進攻的信息，給選擇撤退的將軍發送撤退信息。這樣一來，在4 位選擇進攻的將軍看，共5 位將軍選擇進攻，從而發起進攻；而在4 位選擇撤退的將軍看，共5 位將軍選擇撤退，從而發起撤退，這樣各個將軍的一致性就遭到了破壞。
並且，叛徒將軍可能會偽造其他將軍的身份發送信件；
拜占庭將軍問題描述的是，在存在信息丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的，在系統中除了存在的消息延遲或不可送達故障外，還可能包括消息篡改、節點處理異常等潛在性異常。
在早期的解決方案中，一種是 “拜占庭容錯” ，它遵循“少數服從多數”的共識機制，即使出現了錯誤或偽造的信息，只要有問題的將軍數量不到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
求解以上不等式，可以得到：
(NT)/2 > T，即N > 3T
所以要保證正直的將軍至少佔所有將軍總數的2/3，才有可能達成共識。
拜占庭算法是一種共識算法，確定共識的原則，各個節點通過這個共識原則既可以保證一致性，又能保證基本的分區容錯性。
共識是可容錯系統中的一個基本問題： 即使面對故障，服務器如何在共享狀態上達成一致？
理解，首先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 定義了一系列規範來保證數據安全性。
Raft 算法為節點定義了三種角色： Leader（主節點） 、Follower（從節點） 、Candidate（參與投票競爭的節點） ，節點的角色是可以轉換的，在任意的時間，每個服務器一定處於三種狀態中的一個。
每個節點上都有一個倒計時器（Election Timeout），隨機值在150ms ~ 300ms 之間，當節點收到選舉請求，或收到Leader 的Heartbeat 時，就會重置倒計時。
通常情況下，系統中只有一個主節點，用來發起心跳，處理所有的客戶端請求，創建日誌和同步日誌。
除主節點外，其他的節點都是從節點，用於接收主節點的心跳和日誌數據，保證其數據狀態與主節點一致，以及在Leader 選舉時，投票給Candidate。
如果有客戶端跟Follower 聯繫，那麼Follower 會把請求重定向給Leader。
候選人Candidate是在Leader 選舉過程中的臨時角色，由Follower 轉換而來，用於發起投票參與競選。
Raft 節點狀態圖：
圖1 Raft 節點狀態圖
啟動時，或Follower 接收不到Leader 信息時，它就會變成Candidate 並發起一次選舉。獲得集群中大多數選票的Candidate 就成為新的Leader。
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。
每一個事件是一個Entry，只有Leader 可以創建Entry，結構為
日誌是Raft 的核心概念，是一個由Entry 構成的數組。只有Leader 才可以改變其他節點的Log。 Leader 先把Entry 添加到自己的Log 數組中，發起共識請求，獲得同意後，才會將Entry 提交給狀態機。 Follower 只能從Leader 中獲取新日誌和當前的CommitIndex，然後把對應的Entry 應用到自己的狀態機中。
- raft 通過心跳機制來觸發Leader 的選舉；
- Leader 會向所有的Follower 週期性發送心跳來保證自己的Leader 地位。
- 如果服務器能夠收到來自Leader 或者Candidate 的有效信息，那麼它會一直保持為Follower 狀態，並且刷新自己的electionElapsed，重新計時。
- 如果一個Follower 在一個週期內沒有收到任何信息，也就是選舉超時，它就會認為此時沒有可用的Leader，開始進行一次選舉以選出一個新的Leader。
- 當服務器啟動時，所有的節點都是Follower。
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)
}
}
Raft 通過Leader 向集群中所有Follower 進行日誌同步來保證整個集群數據的最終一致性。
只有Leader 有權限接受客戶端的請求並且同步數據給集群中其他節點。每一個客戶端的請求都包含一條需要被複製狀態機RSM（Replicated State Mechine）執行的命令，Leader 收到客戶端請求後，會生成一個Entry，包含，再將這個entry 添加到自己的日誌末尾後，向所有的節點廣播該Entry，要求其他服務器複製這條Entry。
圖3 主從節點進行Entry 複製
如圖所示，Logs 日誌是一個順序存儲的Entry 數組，方框內是任期Term 號。
例如，在Term3 中，Leader 最後一個Entry 的Index 為7，x 值為5，收到請求set x=4時：
圖4 日誌同步流程
-
Leader 收到客戶端請求x←4 時，Leader 會生成一條新的Entry<8, 3, set x=4>，並將該Entry 添加到自己的Log 數組最後
-
Leader 通過AppendEntries RPC 廣播該Entry；
-
如果Follower 接受該Entry，則會將Entry 添加到其日誌後面，同時返回給Leader 同意。
-
如果Leader 收到了多數的成功響應，Leader 認為這個Entry 是committed，應用到自己的狀態機RSM 中，並且向客戶端返回執行結果。之後，該commited 信息會隨著之後的AppendEntryRPC 傳達到其他節點。
-
committed 表示被Leader 創建的Entry 已經復製到了大多數的服務器上，Leader 會跟踪它記錄的最大索引值Index，並在之後的AppendEntries RPC（包括心跳）中，包含該索引值，以此確保其他服務器同步這個Entry 已經提交，Follower 接收到該信息後，也會按順序同步更新到本地的狀態機中。
Raft 通過這種日誌機制來保證不同服務器上日誌的一致性和安全性：
- 在兩個日誌裡，有兩個entry 擁有相同的index 和term，那麼它們一定有相同的cmd；
- 在兩個日誌裡，有兩個entry 擁有相同的index 和term，那麼它們前面的entry 也一定相同。
一般情況下，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
}
Leader 需要保證其存儲全部已經提交的日誌條目，保證日誌條目只能從Leader 流向Follower，且Leader 永遠不會覆蓋已經存在的日誌條目。
每個Candidate 發送RequestVoteRPC 時，都會帶上最後一個Entry 的信息。所有節點收到投票信息時，會對該Entry 進行比較，如果發現自己的更新，則拒絕投票給該Candidate。
理解，首先MCube 會依據模板緩存狀態判斷是否需要網絡獲取最新模板，當獲取到模板後進行模板加載，加載階段會將產物轉換為視圖樹的結構，轉換完成後將通過表達式引擎解析表達式並取得正確的值，通過事件解析引擎解析用戶自定義事件並完成事件的綁定，完成解析賦值以及事件綁定後進行視圖的渲染，最終將目標頁面展示到屏幕。
早期的共識算法，由拜占庭將軍問題的提出者Leslie Lamport 所發明。谷歌的分佈式鎖服務Chubby 就是以Paxos 算法為基礎。
Zookeeper 所使用的一致性算法，在流程上和Raft 算法比較接近。
區塊鏈技術所使用的共識算法之一，適用於私有鏈的共識。
理解，首先MCube 會依據模板緩存狀態判斷是否需要網絡獲取最新模板，當獲取到模板後進行模板加載，加載階段會將產物轉換為視圖樹的結構，轉換完成後將通過表達式引擎解析表達式並取得正確的值，通過事件解析引擎解析用戶自定義事件並完成事件的綁定，完成解析賦值以及事件綁定後進行視圖的渲染，最終將目標頁面展示到屏幕。
Raft 算法是很廣泛的強一致性、去中心化和高可用的分佈式協議，是一種leader-based 的共識算法。通過將共識問題拆分成主節點選舉和主從日誌同步，以及安全流程，來提高分佈式系統的數據一致性、可靠性和容錯性；首先選舉主節點，然後主節點負責接收外部請求、數據複製、提交，保證系統中數據都是一致的。
