淺談 Raft 分布式一致性協(xié)議｜圖解 Raft

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

前言

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

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

一、 單機KV數(shù)據(jù)讀寫服務

DB Engine這里可以簡單看成對數(shù)據(jù)的狀態(tài)進行存儲（比如B+樹型的組織形式），負責存儲KV的內(nèi)容 ，并假設這個KV服務將提供如下接口：

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

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

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

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

• 單進程，所有操作順序執(zhí)行，可以保證已經(jīng)存儲的數(shù)據(jù)是正確的

數(shù)據(jù)規(guī)模不斷增加，我們需要擴大這個KV服務的規(guī)模，將其構(gòu)建成一個分布式的系統(tǒng)

二、一致性與共識算法

2.1 從復制開始

既然一個節(jié)點會掛，那么我們就多準備一個節(jié)點！

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

2.2 如何復制

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

2.3 具體的寫流程

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

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

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

• 主副本確認Log已經(jīng)成功寫入到從副本機器上，當狀態(tài)機apply后，返回客戶端（關(guān)于寫入之后，請求返回客戶端的時機，是可以由應用控制的，可以是Log寫入從副本之后，就從主副本機器返回，也可以等Log完成落盤之后，再返回）

2.4 具體的讀流程

• 方案一：直接讀狀態(tài)機（這里指的是DB），要求上一步寫操作進入狀態(tài)機后再返回client（數(shù)據(jù)已落盤）
• 方案二：寫操作復制Log完成后直接返回，讀操作Block等待所有pending log進入狀態(tài)機

• 如果不遵循上述兩種方案：可能存在剛剛寫入的值讀不到的情況（在Log中）

2.5 什么是一致性

對于我們的KV服務，要像操作一臺機器一樣，對用戶來說在寫入成功后，就應該能讀到最近寫入的值，而不關(guān)心具體底層是如何分布式實現(xiàn)。

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

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

2.6 復制協(xié)議-當失效發(fā)生

上述用到的添加了一個從副本節(jié)點的方式，我們暫且將其稱為山寨版分布式一致性協(xié)議——復制協(xié)議（因為它依賴于主從副本間的復制操作）

那么當主副本失效時，以這個復制協(xié)議為基礎的KV服務的運行情況如何呢：

• 容錯能力：沒有容錯能力，因為主副本停了，KV服務就停了

• 高可用：或許有，取決于我們發(fā)現(xiàn)主副本宕機后多快將從副本切換為主副本（手動切換）

• 正確性：正確，因為操作只從一臺機器發(fā)起，可以控制所有操作返回前都已經(jīng)復制到另一臺機器了

衍生出的一些的問題：

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

2.7 共識算法

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

共識協(xié)議不等于一致性：

• 應用層面不同的一致性，都可以用共識算法來實現(xiàn)

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

• 簡單的復制協(xié)議也可以提供線性一致性（雖然不容錯）

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

• 因為弱一致性往往可以使用相對簡單的復制算法實現(xiàn)

三、一致性協(xié)議案例：Raft

3.1 Ratf概述

• 2014年發(fā)表

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

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

3.2 復制狀態(tài)機（RSM）

• RSM（replicated state machine）

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

• Commited Index（這里先有個概念，用于標識Log中哪些數(shù)據(jù)可以提交給狀態(tài)機）

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

3.3 Raft角色

• Leader是所有操作的發(fā)起者，會把Log同步給Follower，確定哪個Log已經(jīng)Commit了
• 接受Leader的請求，并且在發(fā)現(xiàn)Leader消失，則轉(zhuǎn)換為Candidate，向其他Follower申請投票，如果獲得票數(shù)過半，則晉升為Leader

3.4 Raft日志復制

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

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

這里有一個細節(jié)就是，雖然Raft協(xié)議使節(jié)點間的數(shù)據(jù)最終達成了一致，但是節(jié)點Log數(shù)據(jù)落盤時間是有先后的（因為Commited Index在各節(jié)點之間存在差異，所以Log與狀態(tài)機是有時差的）

3.5 Raft從節(jié)點失效

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

3.6 Raft Term

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

• 每個Leader服務于一個term：一旦發(fā)現(xiàn)更高的term，那么表示我已經(jīng)不是Leader了
• 每個term至多只有一個leader：選出新的Leader，會使得term增加
• 每個節(jié)點存儲當前的term
• 每個節(jié)點term從一開始，只增不減
• 所有的rpc的request response 都攜帶term
• 只commit本term內(nèi)的log

3.7 Raft主節(jié)點失效

• Leader定期發(fā)送AppendEntries RPCs 給其余所有的節(jié)點

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

• Candidate自增自己的term，同時使用RequestVote PRCs 向剩余節(jié)點請求投票

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

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

3.8 Raft Leader failure

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

關(guān)于為什么s3落后s2兩條Commited Index，有可能是s2一次同步了兩條Log給s3，而s3的狀態(tài)機還沒來得及同步數(shù)據(jù)，但是s3接收到在標識TQ的Log后，將其commit到自己的Log之中，就返回確認響應給了s2，s2將自己的Commited Index向后推進到Q的位置。

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

3.9 Raft 安全性 - 同 Term

• 對于Term內(nèi)的安全性

  • 目標：對于所有已經(jīng)commited的<term, index>位置上至多只有一條log

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

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

3.10 Raft 安全性 - 跨 Term

• 對于跨Term的安全性

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

• 可以證明這個property：

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

四、回到KV

4.1 重新打造KV服務

結(jié)合Raft算法，更新一下我們的KV

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

• 方案一：

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

• 方案二：

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

• 方案三：

  • 寫log被狀態(tài)機apply，返回給client
  • 讀操作直接讀狀態(tài)機
  • 優(yōu)化讀時延

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

• 服務無法水平擴展

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

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

4.2 回到共識算法

• Raft：關(guān)于log

  • 論文中就給出的方案，當過多的Log產(chǎn)生后，啟動snapshot，替換掉Log
  • 如果對于持久化的狀態(tài)機，如何快速的產(chǎn)生Snapshot（略）
  • 多組Raft的應用中，Log如何合流（略）

• 關(guān)于configuration change（節(jié)點規(guī)模變化）

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

4.3 共識算法的未來

• Raft Paxos相互移植

  • Raft有很多成熟的實現(xiàn)

  • 研究主要關(guān)注在Paxos上

  • 如何關(guān)聯(lián)兩種算法：

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

小結(jié)

本文根據(jù)字節(jié)青訓課程中一節(jié)針對《分布式數(shù)據(jù)一致性》的課程內(nèi)容的進行總結(jié)與整理，希望可以幫助大家加深對以Raft為代表的分布式一致性協(xié)議的理解。