raft--分布式一緻性協定

0. 寫在前面的話

　　一直從事分布式對象存儲工作，在分布式對象存儲的營運，開發等工作中，資料一緻性是至關重要的。是以想寫一篇關于分布式一緻性的文章。一來，可以和大家分享。二來，可以提高自己的文字提煉能力也可以當作備忘。

　　本篇文章并不是raft的一篇科普文，不着重介紹raft的具體過程，這些具體過程raft論文中都詳細闡述，在此不再贅述，而是着重于raft中選舉以及日志複制過程如何保證資料的一緻性的闡述。

　　　　#如果對raft不了解的同學，建議搜尋raft論文譯文+原文對照看

　　　　#分享的都是個人體會和思考的過程可能不是很嚴謹　　　　  

　　　　#不求全，可能有些細節會被省略，但求能夠把raft最主要的東西說清楚

1. 什麼是分布式一緻性協定

　　#分布式：多個節點互為副本，副本之間可以是平等關系也可以是主從關系

　　#一緻性：保證各個節點上的資料，隻要是送出的資料一定是保證一緻的

2. 為什麼需要分布式一緻性協定

　　在分布式對象存儲系統中，資料的安全性是通過多份備援副本的保證的，這就要求系統能夠保證多份副本上的資料一緻，比如對于對象存儲系統的master管理着整個叢集的副本關系，block狀态等中繼資料資訊。為了防止master單點，一般會采取一主多從的方式，而在存儲系統中由于故障導緻的資料遷移，空間回收等場景都會導緻中繼資料發生改變，這些中繼資料的改變如何同步到其他備機上對提升整個分布式的資料安全性有着至關重要的作用。

3. raft是如何做到保證資料一緻性

　　raft作為一種比較好了解的分布式一緻性算法（相對于paxos來說啦，其實要了解還是有點難度的！），是通過選舉機制，日志複制來保證系統資料的一緻性

　　筆者認為，raft協定了解的難度并不在于raft定義的那些操作，而是在于raft定義的操作和raft系統遵守的原則之間的關系，以及為什麼系統遵循這些原則就能保證資料的一緻性呢？是以剛開始了解raft協定時給人的感覺就是比較散亂而不清晰。

　　是以下面将會着重試着從raft操作是如何保證系統始終遵守這些原則之間，以及這些原則為什麼能保證資料的一緻性來闡述

　　#raft基本概念：

　　　　送出的日志索引（commitIdx）：已經同步至大部分節點的log的下标，表明資料是安全狀态，是不會再被修改的日志資料。

　　　　任期（term）：相當于系統的邏輯時鐘，每一個任期中隻能有一個leader，可以了解為系統每進入一輪選舉時任期+1。可以把任期想象成一個朝代，一朝天子一朝臣，leader就是這朝的皇帝，從節點就是這朝的臣子。term是了解raft的一個關鍵點。

　　　　日志索引（logIdx）：raft日志索引是一個的下标連續&單調遞增的，例如（1，2，3，4，5，..,n,n+1）。

　　　　狀态機執行日志索引（applyIdx）：發送給狀态機（是個抽象的概念可以是對象存儲系統，也可以是其他的系統）執行的日志下标。

　　#raft基本操作

　　　　#選舉：

　　　　　　功能描述：

　　　　　　　　請求其他節點為自己競選leader投票，超過半數節點投票給自己就會轉化成leader節點

　　　　　　發起方：

　　　　　　　　角色：候選者

　　　　　　　　操作名稱：RequestVote

　　　　　　　　操作參數：

　　　　　　　　　　#目前最新的日志條目索引（目前日志的term+logIdx）【規則b會用到】

　　　　　　　　　　#目前的term号 【規則a會用到】

　　　　　　　　　　#自身的ID，用于告訴選民我是誰

　　　　　　響應方：

　　　　　　　　角色：所有

　　　　　　　　響應規則：

　　　　　　　　　　a.請求方term大于自身的term。（小于的話，就好比生在新中國的我們來了個古代人來參選主席，你說你會答應嗎？）

　　　　　　　　　　b.請求方的日志條目包含自身的日志條目。（通過筆記兩方的日志條目索引來判斷，後面會介紹為什麼這種判斷可以保證）。對方知道的東西還不如你多，說要當你上司你幹嗎？）

　　　　　　　　　　c.在同一個任期内隻能投一次票，多個競選者按照先來先得的投票原則。

　　　　　　　　　　在上面a，b，c條件都滿足的情況下，會投出神聖的一票給對方，否則不投。

　　　　#日志同步：

　　　　　　發起方：

　　　　　　　　功能描述：

　　　　　　　　　　#leader把用戶端寫到leader的日志的條目複制給從節點

　　·　　　　　　　  #在leader上任時會進行一次主從資料的同步（可以了解為當權者掌權後清除異己，主把從上和自己不同的記錄都給删掉，直到保持一緻！）

　　　　　　　　　　#充當心跳封包，維持leader的存在，抑制從節點進入競選。（leader刷存在感的方式）

　　　　　　　　發起方：

　　　　　　　　　　角色：leader

　　　　　　　　　　操作名稱：appendEntrtries

　　　　　　　　　　操作參數：

　　　　　　　　　　　　#目前任期：term

　　　　　　　　　　　　#entries[]：日志資料數組，記錄将要複制給從節點的日志條目

　　　　　　　　　　　　#prevLogIndex / prevLogTerm：entries[0]日志的前一個日志對應的logIdx / prevLogIndex對應日志條目的任期号（很多raft介紹文章是：最新日志之前的日志的索引值，但是本人參考raft原文以及邏輯推理覺的并不是最新日志之前）

　　　　　　　　　　　　#leaderId

　　　　　　　　　　　　#CommitIdx：leader上已經送出的日志索引

　　　　　　　　　　内部維護的資料結構：　

　　　　　　　　　　　　#nextIndex[]:維護每一個從節點下一次需要複制的日志條目索引數組

　　　　　　響應方：

　　　　　　　　角色：非leader角色

　　　　　　　　響應規則：

　　　　　　　　　　a.進行term檢查，如果term小于自身，拒絕更新日志，直接傳回False。（上一屆上司的指令肯定不能聽）

　　　　　　　　　　b.進行一緻性檢測：如果在

prevLogIndex

處的日志的任期号與

prevLogTerm

不比對時,傳回 false

　　　　　　　　　　c.如果一條已經存在的日志與新的沖突（index 相同但是任期号 term 不同），則删除已經存在的日志和它之後所有的日志。

　　　　　　　　　　d.添加任何在已有的日志中不存在的條目

　　　　　　　　　　e.更新commitidx，如果主的commitidx>自身的commitidx，則 自身的commitidx = 主的commitidx。（本人認為在實際raft系統中由于滿足上司人完全原則是以不會存在從的commitidx>主的commitidx情況）

　　#raft遵循的原則

　　　　#上司人隻增加原則：上司人永遠不會覆寫或者删除自己的日志，它隻會增加條目

　　　　#上司人完全原則：再一個任期送出的日志一定，出現在任期更大的上司人日志中。

　　　　#選舉安全原則：一個任期内最多隻能有一個leader

　　　　#日志比對原則：如果兩個日志在相同的索引位置上的日志條目的任期号相同，那麼我們就認為這個日志從頭到這個索引位置之間的條目完全相同

　　　　#狀态機安全原則：如果一個伺服器已經将給定索引位置的日志條目應用到狀态機中，則所有其他伺服器不會在該索引位置應用不同的條目

　　#raft和遵循原則的之間的因果關系

　　　  #上司人隻增加原則：

　　　　　　raft系統中日志的修改來自兩方面，1.appendEntrtries，根據appendEntrtries的響應描述可知，日志可以append，删除修改。2，用戶端日志寫入，是append操作

　　　　　　在raft的appendEntrtries操作定義中響應方是非leader，是以leader隻能介紹客戶段的append日志操作-->原則得證

　　　#選舉安全原則：

　　　　　在選舉操作響應規則c中規定在同一個任期内隻能投一次票

　　　　　　證明：同一個任期内隻能投一次票：則這個任期中的投票次數和節點個數相等的（2N+1）,其中大多數票投個A，成為leader，B就不能得到大多數的投票。

　　　 #上司人完全原則:

　　　　　　在選舉的操作中，響應規則b，要求候選者的日志條目包含自身的日志條目，才可以投票給該候選者。

　　　　　　一個候選者得到大多數的節點的投票才能成為leader -->leader的日志能夠包含大多數節點（Node_Majority_set)的日志條目，并且目前leader的任期一定大于Node_Majority_set日志中的term。

　　　　　　證明：　　

　　　　　　反證法：假設存在一條日志已經送出了但是在Node_Majority_set_1中不存在節點包含這條記錄

　　　　　　　　由于已經送出的日志是已經存在于大多數節點(Node_Majority_set_2)中的日志，Node_Majority_set_1&Node_Majority_set_2 != NULL，是以必定存在節點包含這條記錄，是以得出沖突，結論正确

　　　　　　是以已經送出的日志條目一定包含在Node_Majority_set_1的節點中（不一定全包含，可能是部分節點），而前面的論證leader的日志能夠包含大多數節點的日志條目（節點已送出的日志條目是所有日志條目的子集），是以新leader的日志一定包含所有已經送出的日志條目。

　　　#日志比對原則：

　　　　　　命題：如果兩個日志在相同的索引位置上的日志條目的任期号相同-->該日志索引處前面的索引上對應的日志條目完全相同

　　　　　　根據appendEntrtries響應規則中b的描述：在在

prevLogIndex

處的日志的任期号與

prevLogTerm

不比對時,傳回 false

　　　　　　歸納證明：初始化時所有的節點的在LogIdx=0處的任期号自然相同。

　　　　　　當LogIdx=N處的任期号相同時，appendEntrtries leader同步複制 LogIdx = N+1的日志時，會比對LogIdx=N的進行任期相同的比較，如果相同會寫入 LogIdx = N+1的日志條目，由于所有的從節點複制來自同一個主節點是以任期相同

　　　　　　是以歸納證明可得結論

　　　　#狀态機安全原則：

　　　　　　首先發送給狀态機的日志必須是已經送出的日志，如果一個日志log1已經送出，那麼在該日志的索引位置處不會存在另一條log2已經送出但是和該日志條目不一樣的日志

　　　　　　假設存在log2已經被送出，說明在log2處的索引的日志在大多數節點保持一緻，同理log1在log1索引處的日志條目在大多多數節點保持一緻。

　　　　　　(log1_idx == log2_idx) 是以必然得到 log2 == log1

　　#這些原則為什麼能保證資料的一緻性

　　　　# 上司人隻增加原則+選舉安全原則：保證raft系統中最多隻有一個leader，并且日志複制隻從leader單向流動到從節點（個人任務系統命名為raft中文漂流，是不是就是因為日志複制是單向的流動的呢）。

　　　　# 上司人完全原則:能夠保證新的leader中包含所有已經送出的日志，已經送出的日志是不會再修改的，進而保證新的leader産生也不會對已經送出的日志産生修改操作。

　　　　#根據日志比對原則可以保證如果兩個日志在相同的索引位置上的日志條目的任期号相同-->該日志索引處前面的索引上對應的日志條目完全相同：

　　　　　在appendEntrtries操作的響應規則c規定如果一條已經存在的日志與新的沖突（index 相同但是任期号 term 不同），則删除已經存在的日志和它之後所有的日志。然後複制eader的同步的日志條目，和leader保持一緻。

　　　　　如果不沖突：根據日志比對原則可以判斷前面的日志一定也是和leader保持一緻的，把新的日志條目添加後，和leader保持一緻。

　　綜上所述:這些原則能夠保證系統中最多隻存在一個leader，而且leader包含之前任期的所有已送出的日志條目，日志條目隻從leader流向從節點，在主從日志同步階段能夠保證日志的一緻。