轉(zhuǎn) # raft--分布式一致性協(xié)議
0. 寫在前面的話
一直從事分布式對象存儲工作而线，在分布式對象存儲的運營倔韭，開發(fā)等工作中虱歪，數(shù)據(jù)一致性是至關(guān)重要的绒障。因此想寫一篇關(guān)于分布式一致性的文章。一來挚赊，可以和大家分享。二來鳞陨，可以提高自己的文字提煉能力也可以當(dāng)作備忘盛嘿。
本篇文章并不是raft的一篇科普文洛巢，不著重介紹raft的具體過程，這些具體過程raft論文中都詳細闡述次兆，在此不再贅述稿茉，而是著重于raft中選舉以及日志復(fù)制過程如何保證數(shù)據(jù)的一致性的闡述。
#如果對raft不了解的同學(xué)芥炭，建議搜索raft論文譯文+原文對照看
#分享的都是個人體會和思考的過程可能不是很嚴(yán)謹
#不求全漓库，可能有些細節(jié)會被省略，但求能夠把raft最主要的東西說清楚
1. 什么是分布式一致性協(xié)議
#分布式：多個節(jié)點互為副本蚤认，副本之間可以是平等關(guān)系也可以是主從關(guān)系
#一致性：保證各個節(jié)點上的數(shù)據(jù)米苹，只要是提交的數(shù)據(jù)一定是保證一致的
2. 為什么需要分布式一致性協(xié)議
在分布式對象存儲系統(tǒng)中糕伐，數(shù)據(jù)的安全性是通過多份冗余副本的保證的砰琢，這就要求系統(tǒng)能夠保證多份副本上的數(shù)據(jù)一致，比如對于對象存儲系統(tǒng)的master管理著整個集群的副本關(guān)系良瞧，block狀態(tài)等元數(shù)據(jù)信息陪汽。為了防止master單點，一般會采取一主多從的方式褥蚯，而在存儲系統(tǒng)中由于故障導(dǎo)致的數(shù)據(jù)遷移挚冤，空間回收等場景都會導(dǎo)致元數(shù)據(jù)發(fā)生改變，這些元數(shù)據(jù)的改變?nèi)绾瓮降狡渌麄錂C上對提升整個分布式的數(shù)據(jù)安全性有著至關(guān)重要的作用赞庶。
3. raft是如何做到保證數(shù)據(jù)一致性
raft作為一種比較好理解的分布式一致性算法（相對于paxos來說啦训挡，其實要理解還是有點難度的！）歧强，是通過選舉機制澜薄，日志復(fù)制來保證系統(tǒng)數(shù)據(jù)的一致性
筆者認為，raft協(xié)議理解的難度并不在于raft定義的那些操作摊册，而是在于raft定義的操作和raft系統(tǒng)遵守的原則之間的關(guān)系肤京，以及為什么系統(tǒng)遵循這些原則就能保證數(shù)據(jù)的一致性呢？所以剛開始了解raft協(xié)議時給人的感覺就是比較散亂而不清晰茅特。
因此下面將會著重試著從raft操作是如何保證系統(tǒng)始終遵守這些原則之間忘分，以及這些原則為什么能保證數(shù)據(jù)的一致性來闡述
#raft基本概念：
提交的日志索引（commitIdx）：已經(jīng)同步至大部分節(jié)點的log的下標(biāo)，表明數(shù)據(jù)是安全狀態(tài)白修，是不會再被修改的日志數(shù)據(jù)妒峦。
任期（term）：相當(dāng)于系統(tǒng)的邏輯時鐘，每一個任期中只能有一個leader兵睛，可以理解為系統(tǒng)每進入一輪選舉時任期+1舟山〕窈可以把任期想象成一個朝代，一朝天子一朝臣累盗，leader就是這朝的皇帝寒矿，從節(jié)點就是這朝的臣子。term是理解raft的一個關(guān)鍵點若债。
日志索引（logIdx）：raft日志索引是一個的下標(biāo)連續(xù)&單調(diào)遞增的符相，例如（1，2蠢琳，3啊终，4，5傲须，..,n,n+1）蓝牲。
狀態(tài)機執(zhí)行日志索引（applyIdx）：發(fā)送給狀態(tài)機（是個抽象的概念可以是對象存儲系統(tǒng)，也可以是其他的系統(tǒng)）執(zhí)行的日志下標(biāo)泰讽。
#raft基本操作
#選舉：
功能描述：
請求其他節(jié)點為自己競選leader投票例衍，超過半數(shù)節(jié)點投票給自己就會轉(zhuǎn)化成leader節(jié)點
發(fā)起方：
角色：候選者
操作名稱：RequestVote
操作參數(shù)：
#當(dāng)前最新的日志條目索引（當(dāng)前日志的term+logIdx）【規(guī)則b會用到】
#當(dāng)前的term號 【規(guī)則a會用到】
#自身的ID，用于告訴選民我是誰
響應(yīng)方：
角色：所有
響應(yīng)規(guī)則：
a.請求方term大于自身的term已卸。（小于的話佛玄，就好比生在新中國的我們來了個古代人來參選主席，你說你會答應(yīng)嗎累澡？）
b.請求方的日志條目包含自身的日志條目梦抢。（通過筆記兩方的日志條目索引來判斷，后面會介紹為什么這種判斷可以保證）愧哟。對方知道的東西還不如你多奥吩，說要當(dāng)你領(lǐng)導(dǎo)你干嗎？）
c.在同一個任期內(nèi)只能投一次票蕊梧，多個競選者按照先來先得的投票原則霞赫。
在上面a，b望几，c條件都滿足的情況下绩脆，會投出神圣的一票給對方，否則不投橄抹。
#日志同步：
發(fā)起方：
功能描述：
#leader把客戶端寫到leader的日志的條目復(fù)制給從節(jié)點
· #在leader上任時會進行一次主從數(shù)據(jù)的同步（可以理解為當(dāng)權(quán)者掌權(quán)后清除異己靴迫，主把從上和自己不同的記錄都給刪掉，直到保持一致Ｂナ摹）
#充當(dāng)心跳報文玉锌，維持leader的存在，抑制從節(jié)點進入競選疟羹。（leader刷存在感的方式）
發(fā)起方：
角色：leader
操作名稱：appendEntrtries
操作參數(shù)：
#當(dāng)前任期：term
#entries[]：日志數(shù)據(jù)數(shù)組主守，記錄將要復(fù)制給從節(jié)點的日志條目
prevLogIndex / prevLogTerm：entries[0]日志的前一個日志對應(yīng)的logIdx / prevLogIndex對應(yīng)日志條目的任期號（很多raft介紹文章是：最新日志之前的日志的索引值禀倔，但是本人參考raft原文以及邏輯推理覺的并不是最新日志之前）
#leaderId
#CommitIdx：leader上已經(jīng)提交的日志索引
內(nèi)部維護的數(shù)據(jù)結(jié)構(gòu)：
#nextIndex[]:維護每一個從節(jié)點下一次需要復(fù)制的日志條目索引數(shù)組
響應(yīng)方：
角色：非leader角色
響應(yīng)規(guī)則：
a.進行term檢查，如果term小于自身参淫，拒絕更新日志救湖，直接返回False。（上一屆領(lǐng)導(dǎo)的命令肯定不能聽）
b.進行一致性檢測：如果在prevLogIndex處的日志的任期號與prevLogTerm不匹配時,返回 false
c.如果一條已經(jīng)存在的日志與新的沖突（index 相同但是任期號 term 不同）涎才，則刪除已經(jīng)存在的日志和它之后所有的日志鞋既。
d.添加任何在已有的日志中不存在的條目
e.更新commitidx，如果主的commitidx>自身的commitidx耍铜，則 自身的commitidx = 主的commitidx邑闺。（本人認為在實際raft系統(tǒng)中由于滿足領(lǐng)導(dǎo)人完全原則所以不會存在從的commitidx>主的commitidx情況）
#raft遵循的原則
#領(lǐng)導(dǎo)人只增加原則：領(lǐng)導(dǎo)人永遠不會覆蓋或者刪除自己的日志，它只會增加條目
領(lǐng)導(dǎo)人完全原則：再一個任期提交的日志一定棕兼，出現(xiàn)在任期更大的領(lǐng)導(dǎo)人日志中陡舅。
#選舉安全原則：一個任期內(nèi)最多只能有一個leader
#日志匹配原則：如果兩個日志在相同的索引位置上的日志條目的任期號相同，那么我們就認為這個日志從頭到這個索引位置之間的條目完全相同
#狀態(tài)機安全原則：如果一個服務(wù)器已經(jīng)將給定索引位置的日志條目應(yīng)用到狀態(tài)機中伴挚，則所有其他服務(wù)器不會在該索引位置應(yīng)用不同的條目
#raft和遵循原則的之間的因果關(guān)系
#領(lǐng)導(dǎo)人只增加原則：
raft系統(tǒng)中日志的修改來自兩方面靶衍，1.appendEntrtries，根據(jù)appendEntrtries的響應(yīng)描述可知章鲤，日志可以append摊灭，刪除修改咆贬。2败徊，客戶端日志寫入，是append操作
在raft的appendEntrtries操作定義中響應(yīng)方是非leader掏缎，所以leader只能介紹客戶段的append日志操作-->原則得證
#選舉安全原則：
在選舉操作響應(yīng)規(guī)則c中規(guī)定在同一個任期內(nèi)只能投一次票
證明：同一個任期內(nèi)只能投一次票：則這個任期中的投票次數(shù)和節(jié)點個數(shù)相等的（2N+1）,其中大多數(shù)票投個A皱蹦，成為leader，B就不能得到大多數(shù)的投票眷蜈。
#領(lǐng)導(dǎo)人完全原則:
在選舉的操作中沪哺，響應(yīng)規(guī)則b，要求候選者的日志條目包含自身的日志條目酌儒，才可以投票給該候選者辜妓。
一個候選者得到大多數(shù)的節(jié)點的投票才能成為leader -->leader的日志能夠包含大多數(shù)節(jié)點（Node_Majority_set)的日志條目，并且當(dāng)前l(fā)eader的任期一定大于Node_Majority_set日志中的term忌怎。
證明：
反證法：假設(shè)存在一條日志已經(jīng)提交了但是在Node_Majority_set_1中不存在節(jié)點包含這條記錄
由于已經(jīng)提交的日志是已經(jīng)存在于大多數(shù)節(jié)點(Node_Majority_set_2)中的日志籍滴，Node_Majority_set_1&Node_Majority_set_2 != NULL，因此必定存在節(jié)點包含這條記錄榴啸，所以得出矛盾孽惰，結(jié)論正確
因此已經(jīng)提交的日志條目一定包含在Node_Majority_set_1的節(jié)點中（不一定全包含，可能是部分節(jié)點）鸥印，而前面的論證leader的日志能夠包含大多數(shù)節(jié)點的日志條目（節(jié)點已提交的日志條目是所有日志條目的子集）勋功，所以新leader的日志一定包含所有已經(jīng)提交的日志條目坦报。
#日志匹配原則：
命題：如果兩個日志在相同的索引位置上的日志條目的任期號相同-->該日志索引處前面的索引上對應(yīng)的日志條目完全相同
根據(jù)appendEntrtries響應(yīng)規(guī)則中b的描述：在在prevLogIndex處的日志的任期號與prevLogTerm不匹配時,返回 false
歸納證明：初始化時所有的節(jié)點的在LogIdx=0處的任期號自然相同。
當(dāng)LogIdx=N處的任期號相同時狂鞋，appendEntrtries leader同步復(fù)制 LogIdx = N+1的日志時片择，會比對LogIdx=N的進行任期相同的比較，如果相同會寫入 LogIdx = N+1的日志條目骚揍，由于所有的從節(jié)點復(fù)制來自同一個主節(jié)點所以任期相同
因此歸納證明可得結(jié)論
#狀態(tài)機安全原則：
首先發(fā)送給狀態(tài)機的日志必須是已經(jīng)提交的日志构回，如果一個日志log1已經(jīng)提交，那么在該日志的索引位置處不會存在另一條log2已經(jīng)提交但是和該日志條目不一樣的日志
假設(shè)存在log2已經(jīng)被提交疏咐，說明在log2處的索引的日志在大多數(shù)節(jié)點保持一致纤掸，同理log1在log1索引處的日志條目在大多多數(shù)節(jié)點保持一致。
(log1_idx == log2_idx) 所以必然得到 log2 == log1
#這些原則為什么能保證數(shù)據(jù)的一致性
# 領(lǐng)導(dǎo)人只增加原則+選舉安全原則：保證raft系統(tǒng)中最多只有一個leader浑塞，并且日志復(fù)制只從leader單向流動到從節(jié)點（個人任務(wù)系統(tǒng)命名為raft中文漂流借跪，是不是就是因為日志復(fù)制是單向的流動的呢）。
# 領(lǐng)導(dǎo)人完全原則:能夠保證新的leader中包含所有已經(jīng)提交的日志酌壕，已經(jīng)提交的日志是不會再修改的掏愁，從而保證新的leader產(chǎn)生也不會對已經(jīng)提交的日志產(chǎn)生修改操作。
#根據(jù)日志匹配原則可以保證如果兩個日志在相同的索引位置上的日志條目的任期號相同-->該日志索引處前面的索引上對應(yīng)的日志條目完全相同：
在appendEntrtries操作的響應(yīng)規(guī)則c規(guī)定如果一條已經(jīng)存在的日志與新的沖突（index 相同但是任期號 term 不同）卵牍，則刪除已經(jīng)存在的日志和它之后所有的日志果港。然后復(fù)制eader的同步的日志條目，和leader保持一致糊昙。
如果不沖突：根據(jù)日志匹配原則可以判斷前面的日志一定也是和leader保持一致的辛掠，把新的日志條目添加后，和leader保持一致释牺。
綜上所述:這些原則能夠保證系統(tǒng)中最多只存在一個leader萝衩，而且leader包含之前任期的所有已提交的日志條目，日志條目只從leader流向從節(jié)點没咙，在主從日志同步階段能夠保證日志的一致猩谊。
