前言

上一篇文章解析了Raft協(xié)議的選舉機(jī)制节吮，客戶端通過和選舉出來的Leader通信來讀寫數(shù)據(jù)【傳送門】睦疫。選舉只是保證數(shù)據(jù)一致性的基礎(chǔ)，數(shù)據(jù)讀寫才是該協(xié)議要實(shí)現(xiàn)的功能而柑。這篇文章來分析下Raft協(xié)議通過哪些約束來保證數(shù)據(jù)在多個(gè)節(jié)點(diǎn)上一致性。

基礎(chǔ)原理

官方文檔上對Raft的描述中說荷逞，“Raft本質(zhì)上是管理日志復(fù)制的一致性算法”媒咳。這句話包含兩層意思，1）Raft規(guī)定數(shù)據(jù)在集群節(jié)點(diǎn)中的同步通過復(fù)制日志來實(shí)現(xiàn)种远；2）Raft協(xié)議的核心是通過一系列約束涩澡，保證日志復(fù)制的可靠性。

• 為什么采用日志復(fù)制
  所謂日志復(fù)制院促，就是所有數(shù)據(jù)操作指令以日志的方式發(fā)送到集群內(nèi)的所有節(jié)點(diǎn)上筏养，然后按照相同的順序被執(zhí)行，可以參考復(fù)制狀態(tài)機(jī)的圖來理解常拓。
  復(fù)制狀態(tài)機(jī)
  
  復(fù)制狀態(tài)機(jī)
  
  上圖就是復(fù)制狀態(tài)機(jī)的工作過程：
  第①步渐溶，客戶端把更新指令發(fā)給server（對應(yīng)Raft中的Leader節(jié)點(diǎn)）
  第②步，server把指令以log方式持久化（追加到日志隊(duì)尾）弄抬，然后發(fā)送到其他節(jié)點(diǎn)（Raft中的Follower）
  第③步茎辐，日志被發(fā)送到所有節(jié)點(diǎn)后（Raft中超過半數(shù)節(jié)點(diǎn)即可），server將數(shù)據(jù)應(yīng)用到狀態(tài)機(jī)（提交）
  第④步，回復(fù)客戶端數(shù)據(jù)修改成功
  因?yàn)長og日志隊(duì)列是有序的拖陆，只要保證所有節(jié)點(diǎn)的隊(duì)列數(shù)據(jù)一致弛槐，就可以按照先進(jìn)先出的順序執(zhí)行相同的日志（通常里面存的是指令），狀態(tài)機(jī)的最終狀態(tài)肯定是一致的依啰。
  優(yōu)點(diǎn)
  采用復(fù)制日志的方式來同步數(shù)據(jù)有什么好處呢乎串？
  1）對于leader節(jié)點(diǎn)來說，只需要記錄每個(gè)節(jié)點(diǎn)最后一條復(fù)制成功日志的index速警。這樣對于復(fù)制失敗的情況叹誉，可以從這個(gè)index不斷重試，而不需要全量數(shù)據(jù)覆蓋闷旧。
  2）可以防止ABA的問題长豁，比如上圖中的y先變成1后變成9，follower節(jié)點(diǎn)可以知道整個(gè)變化的過程忙灼，在某些需要中間狀態(tài)的場景不會導(dǎo)致錯(cuò)誤匠襟。
  通過復(fù)制日志來同步數(shù)據(jù)在很多系統(tǒng)中都有應(yīng)用，比如MySQL中通過復(fù)制Binlog來做主從數(shù)據(jù)同步该园，HDFS中文件冗余存儲也是采用同樣的原理酸舍。
• Raft要達(dá)成的目標(biāo)
  Raft通過對復(fù)制狀態(tài)機(jī)運(yùn)行過程添加一定的約束，從而保證了如下的一致性特性：
  1）安全性保證（絕對不會返回一個(gè)錯(cuò)誤的結(jié)果）：在非拜占庭錯(cuò)誤情況下爬范，包括網(wǎng)絡(luò)延遲父腕、分區(qū)、丟包青瀑、冗余和亂序等錯(cuò)誤都可以保證正確璧亮。
  2）可用性：集群中只要有大多數(shù)的機(jī)器可運(yùn)行并且能夠相互通信、以及和客戶端通信斥难，就可以保證可用枝嘶。因此，一個(gè)典型的包含 5 個(gè)節(jié)點(diǎn)的集群可以容忍兩個(gè)節(jié)點(diǎn)的失斞普铩（服務(wù)器被停止就認(rèn)為是失斎悍觥）。他們當(dāng)有穩(wěn)定的存儲的時(shí)候可以從狀態(tài)中恢復(fù)回來并重新加入集群镀裤。
  3）不依賴時(shí)序來保證一致性：物理時(shí)鐘錯(cuò)誤或者極端的消息延遲只有在最壞情況下才會導(dǎo)致可用性問題竞阐。
  4）通常情況下，一條指令可以盡可能快的在集群中大多數(shù)節(jié)點(diǎn)響應(yīng)一輪遠(yuǎn)程過程調(diào)用時(shí)完成暑劝。小部分比較慢的節(jié)點(diǎn)不會影響系統(tǒng)整體的性能骆莹。
  以上是完整的一致性協(xié)議通常的保證的特性，從中可以看出担猛，狀態(tài)機(jī)數(shù)據(jù)存儲部分不是Raft關(guān)心的范疇幕垦，Raft只保證把數(shù)據(jù)安全的送到集群中的所有節(jié)點(diǎn)丢氢。下面我們通過分解Raft協(xié)議，來看下它是怎么完成任務(wù)的先改。

日志復(fù)制規(guī)范

Raft對于復(fù)制狀態(tài)機(jī)中描述的流程疚察，在日志存儲和復(fù)制方面都做了定義

日志數(shù)據(jù)存儲

日志存儲屬性定義

• log屬性用來存儲日志貌嫡，必須保證在回復(fù)request之前，log已經(jīng)持久化到磁盤上猜嘱。
• 當(dāng)日志被復(fù)制到超過半數(shù)節(jié)點(diǎn)后衅枫，Leader節(jié)點(diǎn)就會變更c(diǎn)ommitIndex嫁艇。所有節(jié)點(diǎn)在收到最新的commitIndex后就會嘗試把之前未提交的日志應(yīng)用到狀態(tài)機(jī)朗伶，然后修改lastApplied。
• Leader節(jié)點(diǎn)額外存儲了所有節(jié)點(diǎn)的同步進(jìn)度步咪。matchIndex在收到Follower的Response后更新论皆，這樣對于一條日志來說，matchIndex中超過半數(shù)都確認(rèn)了猾漫，Leader就知道這條日志可以提交了点晴。

節(jié)點(diǎn)日志存儲格式
一個(gè)典型的log結(jié)構(gòu)如下：

log數(shù)據(jù)結(jié)構(gòu)

日志數(shù)據(jù)復(fù)制

上一節(jié)講過屠橄，Raft采用了強(qiáng)Leader得模式，所有的客戶端指令都先發(fā)給Leader來執(zhí)行闰挡，所以復(fù)制肯定有Leader來發(fā)起锐墙。

復(fù)制步驟

• 客戶端把指令發(fā)給Leader
• Leader將指令以存成一個(gè)新的log條目追加到隊(duì)尾
• Leader分發(fā)新的log條目給Follower，這一步是并發(fā)執(zhí)行的
• Follower處理日志條目长酗，返回結(jié)果給Leader

Raft對于復(fù)制過程做了一些約束：

• Leader不允許刪除或者修改日志條目溪北，只允許追加，更不會復(fù)制Follower上的數(shù)據(jù)更新自己的
• Leader強(qiáng)制要求Follower上的數(shù)據(jù)和自己相同夺脾，如果Follower在指定index上的數(shù)據(jù)和Leader不同之拨，則先刪除index上的log，從Leader重新同步咧叭。（數(shù)據(jù)產(chǎn)生不一致的情況都是因?yàn)長eader宕機(jī)引發(fā)重新選舉引起的）
• 當(dāng)超過半數(shù)的Follower收到index為N的log條目后蚀乔，Leader就會更新commitIndex，把日志應(yīng)用到狀態(tài)機(jī)佳簸。應(yīng)用到狀態(tài)機(jī)乙墙，表示這條數(shù)據(jù)生效了颖变。

復(fù)制RPC

日志復(fù)制RPC由Leader發(fā)給Follower腥刹，和心跳使用同一個(gè)RPC調(diào)用，只是其中的entries屬性包含日志條目汉买。LeaderCommit即Leader節(jié)點(diǎn)CommitIndex的當(dāng)前值衔峰。當(dāng)Leader的CommitIndex發(fā)生變化后，F(xiàn)ollower就會在下一次rpc請求中獲取到這個(gè)值蛙粘，就可以知道應(yīng)該把那些日志條目應(yīng)用到狀態(tài)機(jī)中垫卤。
復(fù)制RPC的Response

在集群運(yùn)行正常的時(shí)候舔痕，Leader不斷地發(fā)送日志復(fù)制包給Follower评抚，而Follower接收日志后發(fā)現(xiàn)自己prevLogIndex處的日志條目term值等于prevLogTerm，就會追加到本地日志隊(duì)列中伯复。
如果發(fā)生重新選舉并且選舉前不是所有節(jié)點(diǎn)的數(shù)據(jù)都是最新的慨代，新選上的Leader帶過來的prevLogIndex就會和Follower的最大LogIndex對不上，這個(gè)時(shí)候Follower會返回false啸如，Leader會用更小的prevLogIndex來嘗試侍匙，直到雙方匹配上為止。

一次正常的復(fù)制過程

下面用數(shù)據(jù)模擬一次正常的日志復(fù)制過程叮雳。
1）當(dāng)前集群的狀態(tài)

當(dāng)前集群狀態(tài)

當(dāng)前集群經(jīng)歷了兩個(gè)選舉周期想暗，當(dāng)前現(xiàn)在term為2。Leader已經(jīng)將最新的日志復(fù)制到Follower1债鸡，3成功江滨，超過了半數(shù)，所以commitIndex為5厌均。Follower2唬滑、4最后一條日志的response還未收到，所以Leader中對應(yīng)的matchIndex=4棺弊。此時(shí)Leader中狀態(tài)機(jī)中的值x=1,y=1晶密。
2）客戶端向Leader發(fā)送新的指令，y=2
3）Leader收到指令后模她，同步向Follower發(fā)送日志復(fù)制RPC

4）Follower收到日志后稻艰，將log持久化存儲，比較自己的commitIndex和leaderCommit侈净，將log應(yīng)用到狀態(tài)機(jī)后尊勿，更新CommitIndex和lastApplied僧凤。當(dāng)超過半數(shù)的Follower接收到日志后的可能狀態(tài)如下：

追加日志

此時(shí)，F(xiàn)ollower1和2收到了index 6的日志并保存元扔，并將自己的commitIndex更新成5躯保，然后將index5的日志應(yīng)用到狀態(tài)機(jī)，返回成功給Leader澎语。
5）Leader節(jié)點(diǎn)收到了超過半數(shù)response途事，則將index 6的log應(yīng)用到狀態(tài)機(jī)，更新commitIndex和lastApplied為6
6）Leader返回操作成功給客戶端
以上就是一次完整的日志復(fù)制過程擅羞，看起來邏輯比較簡單尸变。Leader接收到客戶端請求，將日志復(fù)制給Follower减俏，當(dāng)收到超過半數(shù)的Follower反饋召烂，則更新commitIndex，返回客戶端成功垄懂。剩下的Follower大部分情況下也會返回成功骑晶，或者極少數(shù)情況如果失敗的話，Leader會不斷重試草慧，直到成功或者確認(rèn)Follower已宕機(jī)，這兩種情況都不會對結(jié)果有影響匙头。

日志數(shù)據(jù)差異處理

Raft集群在大部分情況下漫谷，都會按照上面正常的邏輯來運(yùn)行，但是在極少數(shù)情況下蹂析，由于因?yàn)楦鞣N原因?qū)е翷eader重新選舉舔示，可能會出現(xiàn)各節(jié)點(diǎn)上的數(shù)據(jù)差異很大的情況，從下面幾個(gè)例子可以看下Raft如何處理电抚。
Follower上的數(shù)據(jù)落后很多

Follower數(shù)據(jù)差異大

Leader頻繁崩潰的數(shù)據(jù)

• 節(jié)點(diǎn)（a）晚唇，index 10的位置為空，所以它會返回false盗似，Leader收到后會將nextIndex-1重新發(fā)送請求哩陕，請求中的prevLogIndex=9，prevLogTerm=6赫舒，同時(shí)entries中攜帶index 10的log條目悍及。（a）收到后發(fā)現(xiàn)和自己index=9處的日志匹配成功，則追加并保存index=10的log接癌，然后返回true心赶。

這里有一點(diǎn)需要注意，（a）節(jié)點(diǎn)index=9處的log條目的term和Leader的index=9處term相同缺猛，則index<9的日志條目肯定相同缨叫，這個(gè)使有Raft的安全性保證的，Raft保證了如下兩個(gè)特性：
1） 如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號枯夜，那么他們存儲了相同的指令
2）如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號弯汰，那么他們之前的所有日志條目也全部相同
這兩個(gè)特性的證明，可以參考Raft協(xié)議原文

• 節(jié)點(diǎn)（b）湖雹，處理邏輯同節(jié)點(diǎn)(a)咏闪，Leader會從nextIndex=11開始嘗試，直到等于5的時(shí)候日志匹配
• 節(jié)點(diǎn)（c）, 收到Leader的prevLogIndex=10摔吏，prevLogTerm=6的RPC請求后鸽嫂，（c）發(fā)現(xiàn)index=11處的log條目是比leader多的纵装，按照Raft的要求會直接刪除index=11的日志條目
• 節(jié)點(diǎn)（d），處理邏輯同（c）据某，會刪除index=11和12處的日志
• 節(jié)點(diǎn)（e）橡娄，發(fā)現(xiàn)index=6和7處的日志跟Leader不同，會刪除這兩個(gè)index處的日志癣籽，然后重新用Leader上6-10的日志追加到（e）的末尾
• 節(jié)點(diǎn)（f) 挽唉，同節(jié)點(diǎn)（e）,會刪除index=4及之后的日志

差異處理總結(jié)
Raft通過兩個(gè)約定來保證Leader和Follower的數(shù)據(jù)最終會達(dá)成一致。

• Leader節(jié)點(diǎn)只會追加log數(shù)據(jù)筷狼，不會修改瓶籽、刪除已有數(shù)據(jù)
• 如果Follower在指定的index上的log條目和Leader任期號不一致，則會刪除Follower上的數(shù)據(jù)埂材，重新同步Leader的數(shù)據(jù)

上面的例子可能沒有覆蓋所有特殊情況塑顺，下面用問題的方式詳細(xì)解釋一下。

復(fù)制安全性問題

1. 在相同的Index上俏险，領(lǐng)導(dǎo)人的日志和Follower的日志不一樣严拒，怎么辦
   Raft強(qiáng)制Follower上的日志必須和Leader相同，不同則用Leader上的日志覆蓋Follower

2. 會不會出現(xiàn)Leader發(fā)送日志給Follower的時(shí)候竖独，F(xiàn)ollower同一個(gè)Index處的term號更大裤唠？
   可能出現(xiàn)，因?yàn)镕ollower原來是Leader预鬓，日志后還沒復(fù)制到超過半數(shù)節(jié)點(diǎn)就崩潰了（如下圖）巧骚。這種情況下，F(xiàn)ollower收到Leader的日志復(fù)制包后就會刪除自己的格二，不管term是大還是小

   
   
   term 2的時(shí)候S1是Leader，復(fù)制日志到S1和S2后崩潰了竣蹦。S5憑借S3和S4的選票成為新的Leader顶猜，收到客戶端新term 3的指令，還沒來得及復(fù)制就崩潰了痘括，S1重新當(dāng)選為Leader长窄，這時(shí)候S1會把term 2的日志復(fù)制到S3~S5，S5上term3的日志會被覆蓋纲菌。

3. 如果原來的Leader宕機(jī)挠日，新選出的Leader沒有最新的數(shù)據(jù)怎么辦
   首先定義下什么是最新的數(shù)據(jù)（up-to-date）。有兩個(gè)標(biāo)準(zhǔn)翰舌，1）對于同一個(gè)index上的日志嚣潜，term大的更新。2）對于term相同的椅贱，index大的更新懂算。Raft規(guī)定在新的Leader選舉時(shí)只冻，F(xiàn)ollower給候選人投同意票，必須是候選人的日志至少和自己一樣新计技，否則就會投反對票喜德。所以沒有最新的日志的Follower，不可能當(dāng)選Leader（如下圖的S4和S5不會當(dāng)選）

   
   
   S1是Leader垮媒，將index 2的日志復(fù)制到S2和S3上后還沒提交就崩潰了舍悯，觸發(fā)重新選舉。S4和S5不可能當(dāng)選新的Leader睡雇，以S5為例萌衬，它需要收到除自己之外的2張選票，S4可以投給它入桂，但是S2和S3不可能投給它奄薇，所以無法當(dāng)選。但是如果是問題2中的情況抗愁，S5是可以當(dāng)選的馁蒂，因?yàn)閠erm2的日志只復(fù)制到了S2，沒超過半數(shù)肯定沒有提交蜘腌，后期被新的leader覆蓋也是正常的

4. Leader將日志復(fù)制給超過半數(shù)Follower后沫屡，將數(shù)據(jù)應(yīng)用到狀態(tài)機(jī)，就返回客戶端成功撮珠，F(xiàn)ollower是什么時(shí)候把日志應(yīng)用到狀態(tài)機(jī)的沮脖？
   Leader節(jié)點(diǎn)在將日志應(yīng)用到狀態(tài)機(jī)之前，commitIndex必然已更新芯急。在后續(xù)leader發(fā)送心跳或者復(fù)制新的客戶端日志給Follower的時(shí)候勺届，F(xiàn)ollower發(fā)現(xiàn)自己的commitIndex比leader的小，就會將更新自己的commitIndex娶耍，并將日志應(yīng)用到狀態(tài)機(jī)免姿。

5. 如果領(lǐng)導(dǎo)人提交并反饋客戶端以后，F(xiàn)ollower還沒提交榕酒，Leader掛了胚膊，對數(shù)據(jù)有沒有影響？
   對最終的結(jié)果沒有影響想鹰。Leader提交了指定index上的日志紊婉，說明這條日志和它之前的日志已經(jīng)復(fù)制到超過半數(shù)的節(jié)點(diǎn)上。Leader掛掉后辑舷，新的Leader會繼續(xù)提交該日志喻犁。如問題3中的情況，S2或者S3當(dāng)選新的Leader后，會繼續(xù)復(fù)制term 2的日志至S4和S5株汉。

6. 如果日志被復(fù)制到超過半數(shù)節(jié)點(diǎn)筐乳，但是Leader還沒提交就崩潰了，重新選舉后數(shù)據(jù)會不會被提交乔妈？
   答案是不一定蝙云。初看上去，這個(gè)問題和問題5有點(diǎn)像路召〔伲可能的疑問就是，Raft又沒有一個(gè)專門的RPC請求叫提交請求股淡，都是通過后續(xù)的心跳和日志來通知Follower的身隐，那5和6的區(qū)別在哪里呢？這其實(shí)恰恰是Raft一致性協(xié)議的核心唯灵，就是Raft保證只要Leader把某個(gè)日志應(yīng)用到狀態(tài)機(jī)（即提交）贾铝，那最終所有節(jié)點(diǎn)都會把該日志應(yīng)用到狀態(tài)機(jī)。但是埠帕，日志只是被復(fù)制到超過半數(shù)節(jié)點(diǎn)垢揩，Leader還沒將其應(yīng)用到狀態(tài)機(jī)，Raft不保證該條日志后續(xù)一定會提交敛瓷。這個(gè)問題從客戶端的角度可能更好理解叁巨，在Leader將客戶端某條指令提交后，回復(fù)客戶端提交成功呐籽，那客戶端可以確認(rèn)一點(diǎn)锋勺，這條指令最終一定會在集群中生效；但是如果Leader收到指令后沒提交就崩潰了狡蝶，那客戶端就肯定不會收到肯定的答復(fù)庶橱，所以也就無法知道指令最終生效沒有，這個(gè)需要Raft協(xié)議的實(shí)現(xiàn)方來做處理贪惹，不屬于Raft協(xié)議的范疇悬包，這就是問題5和6的區(qū)別。下面通過Raft論文中舉的最復(fù)雜的一個(gè)例子來加深理解：

   
   
   日志提交

在上圖中馍乙，（a）中S1是Leader，term 2中復(fù)制新的日志到S2后崩潰了垫释，S5在term 3當(dāng)選丝格。（b）中S5收到新的日志放在index 2后也崩潰了，S1在term 4重新當(dāng)選棵譬。（c）中S1將term 2的日志復(fù)制到S3上显蝌，所以term 2的日志已經(jīng)超過半數(shù)，這時(shí)候S1會不會提交term 2的日志呢，答案是不會的曼尊，Raft禁止Leader提交不屬于自己周期的日志酬诀。所以在（c）的狀態(tài)下可能會出現(xiàn)兩種結(jié)果，一種是客戶端在term 4發(fā)送了新的指令骆撇，S1將該指令的日志復(fù)制到了超過半數(shù)節(jié)點(diǎn)瞒御，然后S1就可以將commitIndex改成4，在提交term 4的同時(shí)把term 2也提交了神郊，就是上圖中的（e）肴裙。另外一種就是term 4的日志沒被復(fù)制到超過半數(shù)的節(jié)點(diǎn)，S1又掛了涌乳，這個(gè)時(shí)候觸發(fā)選舉蜻懦，S5會重新當(dāng)選，因?yàn)樗膖erm 3的日志是最新的夕晓，S5會把term 3的日志復(fù)制到所有節(jié)點(diǎn)上宛乃，就是上圖中的（d）。

通過上圖相信已經(jīng)可以理解蒸辆，日志復(fù)制到超過半數(shù)節(jié)點(diǎn)征炼，不是日志肯定被提交的充分必要條件。如果在上圖中的（c)中S1把term 2的日志提交了吁朦，然后又掛了柒室，S5當(dāng)選后覆蓋S2和S3的數(shù)據(jù)就會造成數(shù)據(jù)不一致，因?yàn)橐呀?jīng)提交的日志條目是不能被修改的逗宜。所以雄右，日志被提交生效的充分必要條件是，日志已經(jīng)被復(fù)制到超過半數(shù)節(jié)點(diǎn)纺讲，并且日志是在當(dāng)前Leader的任期（term）內(nèi)從客戶端收到的擂仍。
現(xiàn)在再回顧下問題5，客戶端發(fā)指令給Leader熬甚，Leader提交成功并反饋逢渔，這里面其實(shí)隱含了一個(gè)肯定成立的條件就是客戶端請求和Leader反饋是在同一個(gè)任期內(nèi)。

總結(jié)

Raft通過對日志復(fù)制和選舉的限制相結(jié)合保證了安全性乡括，從而滿足了一致性協(xié)議的特性肃廓。下一篇將解析Raft協(xié)議關(guān)于集群擴(kuò)容縮容的規(guī)范。

鏈接：
分布式一致性協(xié)議-Raft詳解 (一)
分布式一致性協(xié)議-Raft詳解 (三)