Raft簡單實作小結

版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。 https://blog.csdn.net/feilengcui008/article/details/64135653

上一周花了大部分時間重新拾起了之前落下的MIT6.824 2016的分布式課程，實作和調試了下Raft協定，雖然Raft協定相對其他容錯分布式一緻性協定如Paxos/Multi-Paxos/VR/Zab等來說更容易了解，但是在實作和調試過程中也遇到不少細節問題。雖然論文中有僞代碼似的協定描述，但是要把每一小部分邏輯組合起來放到正确的位置還是需要不少思考和踩坑的，這篇文章對此做一個小結。

Raft實作

這裡實作的主要是Raft基本的Leader Election和Log Replication部分，沒有考慮Snapshot和Membership Reconfiguration的部分，因為前兩者是後兩者的實作基礎，也是Raft協定的核心。MIT6.824 2016使用的是Go語言實作，一大好處是并發和異步處理非常直覺簡潔，不用自己去管理異步線程。

• 宏觀
  • 合理規劃同步和異步執行的代碼塊，比如Heartbeat routine/向多個節點異步發送請求的routine
  • 注意加鎖解鎖，每個節點的heartbeat routine/請求傳回/接收請求都可能改變Raft結構的狀态資料，尤其注意不要帶鎖發請求，很容易和另一個同時帶鎖發請求的節點死鎖
  • 理清以下幾塊的大體邏輯
    • 公共部分的邏輯
      • 發現小的term丢棄
      • 發現大的term，跟新自身term，轉換為Follower，重置votedFor
      • 修改term/votedFor/log之後需要持久化
    • Leader/Follower/Candidate的Heartbeat routine邏輯
    • Leader Election
      • 發送RequestVote并處理傳回，成為leader後的邏輯(nop log replication)
      • 接收到RequestVote的邏輯，如何投票(Leader Election Restriction)
    • Log Replication
      • 發送AppendEntries并處理傳回(consistency check and repair)，達成一緻後的邏輯(更新commitIndex/nextIndex/matchIndex， apply log)
      • 接收到AppendEntries的邏輯(consistency check and repair, 更新commitIndex，apply log)
• 細節
  • • timeout的随機性
    • timeout的範圍，必須遠大于rpc請求的平均時間，不然可能很久都選不出主，通常rpc請求在ms級别，是以可設定150~300ms
    • 選主請求發送結束後，由于有可能在選主請求(RequestVote)的傳回或者别的節點的選主請求中發現較大的term，而被重置為Follower，這時即使投票數超過半數也應該放棄成為Leader，因為目前選主請求的term已經過時，成為Leader可能導緻在新的term中出現兩個Leader.(注意這點是由于發送請求是異步的，同步請求發現較大的term後可直接修改狀态傳回)
    • 每次發現較大的term時，自身重置為Follower，更新term的同時，需要重置votedFor，以便在新的term中可以參與投票
    • 每次選主成功後，發送一條nop的日志複制請求，讓Leader送出所有之前應該送出的日志，進而讓Leader的狀态機為最新，這樣為讀請求提供linearializability，不會傳回stale data
  • • Leader更新commitIndex時，需要嚴格按照論文上的限制條件(使用matchIndex)，不能送出以前term的日志
    • 對于同一term同一log index的日志複制，如果失敗，應該無限重試，直到成功或者自身不再是Leader，因為我們需要保證在同一term同一log index下有唯一的一條日志cmd，如果不無限重試，有可能會導緻以下的問題
      • 五個節點(0, 1, 2, 3, 4), node 0為leader，複制一條Term n, LogIndex m, Cmd cmd1的日志
      • node 1收到cmd1的日志請求，node 2, 3, 4未收到
      • 如果node 0不無限重試而傳回，此時另一個cmd2的日志複制請求到達，leader 0使用同一個Term和LogIndex發送請求
      • node 2, 3, 4收到cmd2的請求，node 1未收到
      • node 1通過election成為新的leader(RequestVote的檢查會通過，因為具有相同的Term和LogIndex)
      • node 1發送nop送出之前的日志，cmd1被applied(consistency check會通過，因為PrevLogTerm和PrevLogIndex相同)
      • cmd2則被node 2, 3, 4 applied
      • cmd1和cmd2發生了不一緻
• 測試和其他一些問題
  • 測試過程中發現MIT6.824測試有兩處小問題
    • 一個是TestReElection中隔離leader1，重連leader1後需要睡眠至少一個心跳周期，讓leader1接收到leader1的心跳而轉換為follower
    • 另一個是cfg.one中送出一個日志後需要檢查所有參與節點applied日志後的結果，是以需要leader和所有follower盡早applied日志，但是follower總是滞後于leader至少一個心跳周期或者一次AppendEntries請求的，是以這個檢查會失敗
  • Start異步執行的問題?
    • 由于測試代碼直接阻塞調用Start，需要擷取Start傳回的Term/Index等，當日志複制請求失敗時，Start會無限重試，進而阻塞測試代碼，而無法重新加入節點，到時整個測試阻塞。
    • 如果在單獨的goroutine中執行Start的邏輯，log index的擷取是序列化的(Raft需要保證前面所有的日志送出後才能送出本條日志)，是以本質上後面的請求需要等待前面的請求完成并持久化日志然後再拿下一個log index，是以還是序列化的。而且，并發之後給commitIndex和apply log的邏輯引入了更多的複雜度。
  • 一些優化點在保證基本協定正确性的前提下如何實作?
    • 鎖的優化
    • pipeline
    • batch
  • 用戶端互動，保證exactly once語義

總結

• 一個工程級别的分布式一緻性協定實作并不容易，要注意的細節很多，不僅要保證正确地實作協定，還要考慮優化點，在優化整個系統的性能時保證系統的正确性。
• 分布式系統尤其是像分布式一緻性協定這樣的複雜系統需要大量的測試來保證系統的正确性，算法本身簡潔的描述忽略了非常多實際工程中會遇到的各種fault，在工程實作之後很難保證其正确性，有些case需要經曆多次狀态轉換才能發現失敗原因。
• 大緻實作了Raft之後，再回過頭去看Paxos/Multi-Paxos，會更明白Raft為了簡單做的trade-off
  • 保證協定safety性質的前提下，通過增加以下三個條件來簡化Leader恢複或者說View Change過程中的狀态恢複，保證日志從Leader上單向流動到Follower(而這個過程又可以合并到AppendEntries日志複制的邏輯中，即consistency check)，這個過程往往是關鍵和最複雜的步驟。
    • 選主的時候滿足發請求的節點和被請求的節點日志至少一樣新，保證選主成功後Leader上的日志最新
    • 日志必須順序送出(對資料庫事務日志來說可能并不友好)
    • 新選出的Leader不能直接送出以前Term的日志，需要寫入一條目前Term的日志後才能送出之前Term的日志
• 最後放上簡單的代碼供參考:-), Raft