最近兩年工作中對區塊鏈技術接觸較多，接下來可能要告一段落了。期間對 go-ethereum 進行過聯盟鏈改造，使用 Raft 共識算法把以太坊的 TPS 提升到了 1K+。這裡總結一下 Raft 算法，既是對自己經歷對一種記錄，也算是對他人對幫助。
Raft 算法是一個非常好理解（相比 Paxos 算法來說），也是一個非常受歡迎的共識算法，比如常用的服務發現、共享配置以及一致性保障的 etcd 和 Counsul 都使用了 Raft 算法來保證一致性。
0x01 什麼是分布式共識算法
在分布式計算領域中有一個非常有名的 CAP 定理：一個分布式系統最多只能同時滿足一致性（Consistency）、可用性（Availability）和分區容忍性（Partition tolerance）這三項中的兩項。
一致性是指節點數據的一致，即所有節點在同一時間的數據完全一致。如果細分的話，一致性又可以分為強一致、弱一致和最終一致。比如我們經常使用的多副本關係型資料庫滿足的是強一致性，又因為要同時滿足高可用，那麼就弱化了分區容忍性（可以使用簡單的網絡拓撲來減少分區出錯的可能）；公有的比特幣、以太坊網絡是屬於最終一致，因為它們必須優先滿足可用性和分區容忍性。
分布式網絡中所有節點要想達成一致，就需要一個算法來促成這個一致，這個算法就是共識算法。我們常聽說的 挖礦、PoS、DPoS、PBFT、Raft 都屬於解決一致性的算法。
0x02 理解 Raft
Raft 中，節點通過心跳消息來保持通信，一個節點只會處於以下三種狀態中的一種：
- Follower（跟從者）
- Candidate（候選人）
- Leader（領導者）
最開始時，所有的節點都是 follower，如果 follower 收不到 leader 的心跳消息，那麼 follower 會變為 candidate，並向其他節點發起投票，如果該 candidate 節點收到了半數以上的選票（包括投給自己的一票），那麼它就當選為新的 leader。這個過程被稱為leader 選舉 的過程。
接下來，leader 節點將帶領所有節點對分布式網絡中對數據更改達成一致，這個過程被稱為日誌同步 。
日誌同步的過程如下：
- Leader 收到客戶端到數據提交請求，leader 把請求作為一個條目（entry）加入到它到日誌中，這個時候它不會立刻更新數據；
- Leader 向所有的 followers 節點發送這個條目，這個發送的過程被稱為 Append Entries；
- Followers 節點收到 leader 的 Append Entries 請求後，向 leader 回復條目響應；
- Leader 節點收集了半數以上的條目響應後，向客戶端響應條目已確認，這時它才會更新自身節點的數據，同時向所有 fwllowers 節點發送條目確認的消息；
0x03 特殊情況
Leader 選舉過程中，如果沒有收到半數以上的選票，該怎麼辦？
Raft 中，有兩種超時機制：選舉超時和心跳超時。
每個 follower 會隨機生成一個選舉超時時間。任意節點當自身的選舉超時時間結束後還沒有收到 leader 的消息，那麼它就重置這輪選舉，變為 candidate 向其他節點發起新一輪投票。這樣，最終總會選舉出一個 leader 節點來。
正常運行過程中，如果 leader 節點掛掉，會出現什麼情況？
這種情況下，會用到心跳超時機制。當 followers 在心跳超時後仍舊沒有收到 leader 節點的心跳消息，那麼 followers 節點就會發起新一輪投票，直到選舉出新的 leader 來。
網絡分區的情況下會發生什麼？
網絡故障導致導致節點被分隔到多個不連通的區域，在被隔離的區域中又會觸發新的 leader 選舉，對於隔離區域中包含半數以上的節點，選舉就可能成功。當網絡恢復後，followers 接受最大任期（term）和最新日誌的 leader。這個思路蕾絲比特幣、以太坊網絡分叉後以最長區塊為準的解決方案，確保了最終一致性。
end：如果你覺得本文對你有幫助的話，記得關注點贊轉發，你的支持就是我更新動力。