淺談 Raft 分散式一致性協議｜圖解 Raft

前言

本篇文章將模擬一個KV數據讀寫服務，從提供單一節點讀寫服務，到結合分散式一致性協議（Raft）後，逐步擴展為一個分散式的，滿足一致性讀寫需求的讀寫服務的過程。

其中將配合引入Raft協議的種種概念：選主、一致性、共識、安全等，通篇閱讀之後，將幫助你深刻理解什麼是分散式一致性協議。

一、 單機KV數據讀寫服務

DB Engine這裡可以簡單看成對數據的狀態進行存儲（比如B+樹型的組織形式），負責存儲KV的內容 ，並假設這個KV服務將提供如下介面：

  • Get(key) —> value
  • Put([key, value])

思考此時KV服務的可靠性：

  • 容錯：單個數據存儲節點，不具備容錯能力。
  • 高可用：服務部署在單節點上，節點宕機將無法提供服務。

思考此時KV服務的正確性：

  • 單進程，所有操作順序執行，可以保證已經存儲的數據是正確的

數據規模不斷增加，我們需要擴大這個KV服務的規模，將其構建成一個分散式的系統

二、一致性與共識演算法

2.1 從複製開始

既然一個節點會掛，那麼我們就多準備一個節點！

我們這裡只考慮主副本負責接收數據，而從副本只負責同步接收主副本數據的模式，如果主從都開放數據接收能力，將要考慮更多高可用和數據一致性的問題。

2.2 如何複製

  • 主副本定期拷貝全量數據到從副本（代價太高）
  • 主副本拷貝操作日誌到從副本：如果你了解MySQL的主從同步，你就會想起它也是通過從副本監聽主副本當中的bin log操作日誌變化，進行集群數據同步的，因此這種方式也是更主流的選擇。

2.3 具體的寫流程

  • 主副本把所有的操作打包成Log

    • 所有的Log寫入都是持久化的，保存在磁碟上

  • 應用包裝成狀態機（也就是DB Engine部分），只接收Log作為Input

  • 主副本確認Log已經成功寫入到從副本機器上，當狀態機apply後，返回客戶端（關於寫入之後，請求返回客戶端的時機，是可以由應用控制的，可以是Log寫入從副本之後，就從主副本機器返回，也可以等Log完成落盤之後，再返回）

2.4 具體的讀流程

  • 方案一：直接讀狀態機（這裡指的是DB），要求上一步寫操作進入狀態機後再返回client（數據已落盤）
  • 方案二：寫操作複製Log完成後直接返回，讀操作Block等待所有pending log進入狀態機
  • 如果不遵循上述兩種方案：可能存在剛剛寫入的值讀不到的情況（在Log中）

2.5 什麼是一致性

對於我們的KV服務，要像操作一台機器一樣，對用戶來說在寫入成功後，就應該能讀到最近寫入的值，而不關心具體底層是如何分散式實現。

一致性是一種模型（或語義），約定一個分散式系統如何向外界提供服務，KV服務中常見的一致性模型有以下兩種：

  • 最終一致性：讀取可能暫時讀不到但是總會讀到
  • 線性一致性：最嚴格，線性時間執行（寫完KV確保就能讀到），是最理想中的狀態

2.6 複製協議-當失效發生

上述用到的添加了一個從副本節點的方式，我們暫且將其稱為山寨版分散式一致性協議——複製協議（因為它依賴於主從副本間的複製操作）

那麼當主副本失效時，以這個複製協議為基礎的KV服務的運行情況如何呢：

  • 容錯能力：沒有容錯能力，因為主副本停了，KV服務就停了
  • 高可用：或許有，取決於我們發現主副本宕機後多快將從副本切換為主副本（手動切換）
  • 正確性：正確，因為操作只從一台機器發起，可以控制所有操作返回前都已經複製到另一台機器了

衍生出的一些的問題：

  • 如何保證主副本是真的失效了，切換的過程中如果主副本又開始接收client請求，則會出現Log覆蓋寫的情況
  • 如果增加到3個乃至更多的節點，每次PUT數據的請求都等待其他節點操作落盤性能較差
  • 能否允許少數節點掛了的情況下，仍然可以保持服務能工作（具備容錯能力）

2.7 共識演算法

什麼是共識：一個值一旦確定，所有人都認同

共識協議不等於一致性：

  • 應用層面不同的一致性，都可以用共識演算法來實現

    • 比如可以故意返回舊的值（共識演算法只是一個彼此的約定，只要數據存儲與獲取符合需求，達成共識即可）

  • 簡單的複製協議也可以提供線性一致性（雖然不容錯）

一般討論共識協議時提到的一致性，都指線性一致性

  • 因為弱一致性往往可以使用相對簡單的複製演算法實現

三、一致性協議案例：Raft

3.1 Ratf概述

  • 2014年發表

  • 易於理解作為演算法設計的目標

    • 使用了RSM、Log、RPC的概念
    • 直接使用RPC對演算法進行了描述
    • Strong Leader-based（所有操作都是Leader發起的）
    • 使用了隨機的方法減少約束（比如選主時Follower誰先發現Leader失聯就發起選主）

3.2 複製狀態機（RSM）

  • RSM（replicated state machine）

    • Raft中所有的共識機制（consensus）都是直接使用Log作為載體：簡單說就是client將Log提供給Raft（也就是上圖的Consensus Module），Raft確定這個Log已經Commit之後（寫入Log文件），將Log提供給用戶的狀態機
    • 注意此時狀態機是一個記憶體中的存儲概念，當然後續每個節點數據還涉及到落盤持久化，這是具體應用層面的問題了，這裡討論的更多是Raft協議的原理概念，使用狀態機對此進行抽象

  • Commited Index（這裡先有個概念，用於標識Log中哪些數據可以提交給狀態機）

    • 一旦Raft更新Commited Index，意味著這個Index前所有的Log都可以提交給狀態機了
    • Commited Index是不持久化的，狀態機也是volatile的（斷電清空），重啟後從第一條Log開始恢復狀態機，Raft協議工作過程中每個節點的Commited Index可能是不一致的，但是Ratf可以保證最終所有節點都是一致的

3.3 Raft角色

  • Leader是所有操作的發起者，會把Log同步給Follower，確定哪個Log已經Commit了
  • 接受Leader的請求，並且在發現Leader消失，則轉換為Candidate，向其他Follower申請投票，如果獲得票數過半，則晉陞為Leader

3.4 Raft日誌複製

接下來講解一下Raft協議中Log是如何在節點間同步的：

  1. 第一張圖s2是當前Leader，紫色的小箭頭指向每個節點已經確認commit的Log位置
  2. 第二張圖s2又append了一條新的Log，用K標識
  3. 第三張圖表示，s2將自己收到的K以及自己的Commited Index發送給所有Follower節點。Follower都同步Leader的Log以及Commited Index，並且Follower的狀態機檢測到自己的Commited Index又向前推進了，說明有新的Log值達成了共識，就會把Commited Index沒讀取的Log值應用給狀態機
  4. 第四張圖，當Follower完成步驟三的操作之後，會告訴Leader自己已經拿到這個Log值了，Leader在收到多數派的確認消息後，就可以確定這個K已經永遠的持久化，也就是已經Commit了，因此將Commited Index向後推一位

這裡有一個細節就是，雖然Raft協議使節點間的數據最終達成了一致，但是節點Log數據落盤時間是有先後的（因為Commited Index在各節點之間存在差異，所以Log與狀態機是有時差的）

3.5 Raft從節點失效

  1. 圖一假設s3失效了很久，Log有很多數據沒有同步
  2. 圖二表示此時的Leader是s2，將自己Log中的K和自己的Commited Index複製給s1
  3. 圖三中s2的K完成了commit（流程參考Raft日誌複製），因為s1、s2共兩個節點已經形成了多數派（此時已經有容錯能力了）
  4. 圖四中，s3嘗試重新同步數據，在Raft協議中，s3會向s2逆向迭代的去獲取Log數據（K、QK、TQK、XTQK），直到與s3當前Log相對齊則完成數據同步（當然Raft具體實現中應用對此過程進行了優化）

3.6 Raft Term

Term（周期的概念），在Raft中相當於一個邏輯的時鐘，下面介紹：

  • 每個Leader服務於一個term：一旦發現更高的term，那麼表示我已經不是Leader了
  • 每個term至多只有一個leader：選出新的Leader，會使得term增加
  • 每個節點存儲當前的term
  • 每個節點term從一開始，只增不減
  • 所有的rpc的request response 都攜帶term
  • 只commit本term內的log

3.7 Raft主節點失效

  • Leader定期發送AppendEntries RPCs 給其餘所有的節點

  • 如果Follower 有一段時間沒有收到Leader的AppendEntries，則轉換身份為Candidate

  • Candidate自增自己的term，同時使用RequestVote PRCs 向剩餘節點請求投票

    • raft在檢查是否可以投票時，會檢查log是否outdated，至少不比本身舊才會投票給對應的Candidate

  • 如果多數派投給它，則成為該term的leader

3.8 Raft Leader failure

接下來模擬一下主節點失效後的流程，並且注意此時圖一當中，s1的Log內容比較特殊，為XW，這個場景是可以實現的，比如一開始有s1、s2、s3，其中s1是Leader，首先將X同步給了s2和s3，並且接受到了新的W，但是突然s1節點卡死了，s2和s3重新開始選舉Leader為s2，最終s2和s3的Log變成了XTQ（這只是一種情況，一切皆有可能），然後s1又恢復了。

關於為什麼s3落後s2兩條Commited Index，有可能是s2一次同步了兩條Log給s3，而s3的狀態機還沒來得及同步數據，但是s3接收到在標識TQ的Log後，將其commit到自己的Log之中，就返回確認響應給了s2，s2將自己的Commited Index向後推進到Q的位置。

  • 從圖二開始，s3發現s2掛了，沒有Leader，則將自己的term+1變為3，並且向s1請求Vote
  • 圖三中，s1發現RequestVote是來自term等於3的，大於自己的term，因此將自己的term也更新為3，同時答應給s3投票，達成多數派條件，s3成為新的Leader
  • 圖四，s3開始同步自己的Log給s1，但是發現s1中的Log起初為XW，而s3中為XTQY，因此還是會按照從後往前迭代的方式將數據同步給s1（Y、QY、TQY、XTQY），最後s1雖然與同步狀態發生了衝突，但是由於Raft是Strong Leader-based的，會完全按照Leader的內容覆蓋自己的Log

3.9 Raft 安全性 – 同 Term

  • 對於Term內的安全性

    • 目標：對於所有已經commited的<term, index>位置上至多只有一條log

  • 由於Raft的多數派選舉，我們可以保證在一個term中只有一個leader

    • 我們可以證明一條更嚴格的聲明：在任何<term, index>位置上，至多只有一條log

3.10 Raft 安全性 – 跨 Term

  • 對於跨Term的安全性

    • 目標：如果一個log被標記commited，那這個log一定會在未來所有的leader中出現

  • 可以證明這個property：

    • Raft選舉時會檢查Log是否outdated，只有最新的才能當選Leader
    • 選舉需要多數派投票，而commited log也已經在多數派當中（必有overlap）
    • 新Leader一定持有commited log，且Leader永遠不會overwrite log

四、回到KV

4.1 重新打造KV服務

結合Raft演算法，更新一下我們的KV

回顧一下一致性讀寫的定義：

  • 方案一：

    • 寫log被commit了，返回客戶端成功
    • 讀操作也寫入一條log（因為讀的數據可能還沒從Log寫入狀態機，無法讀取狀態機數據），狀態機apply log後返回client
    • 增加Log量

  • 方案二：

    • 寫log被commit了，返回客戶端成功
    • 讀操作先等待所有commited log apply，再讀取狀態機
    • 優化寫時延

  • 方案三：

    • 寫log被狀態機apply，返回給client
    • 讀操作直接讀狀態機
    • 優化讀時延

多個副本只有單個副本可以提供服務（一個Leader萬一忙不過來怎麼辦）

  • 服務無法水平擴展

  • 增加更多Raft組（不多展開）

    • 如果操作跨Raft組（對key進行分組，每一個Raft負責讀寫一個range的key）

4.2 回到共識演算法

  • Raft：關於log

    • 論文中就給出的方案，當過多的Log產生後，啟動snapshot，替換掉Log
    • 如果對於持久化的狀態機，如何快速的產生Snapshot（略）
    • 多組Raft的應用中，Log如何合流（略）

  • 關於configuration change（節點規模變化）

    • 論文中就給出的joint-consensus以及單一節點變更兩種方案（很複雜，略）

4.3 共識演算法的未來

  • Raft Paxos相互移植

    • Raft有很多成熟的實現

    • 研究主要關注在Paxos上

    • 如何關聯兩種演算法：

      • On the Parallels between Paxos and Raft, and how to Port Optimizations[1]
      • Paxos vs Raft: Have we reached consensus on distributed consensus?[2]

小結

本文根據位元組青訓課程中一節針對《分散式數據一致性》的課程內容的進行總結與整理，希望可以幫助大家加深對以Raft為代表的分散式一致性協議的理解。

Tags:

VirMach 便宜 VPS

QNews

QNews