概念說明

• leader: 如果candidate收大多數(shù)(n/2+1)節(jié)點的投票纽窟，就會轉(zhuǎn)換成leader鸣剪，leader定期發(fā)送心跳rpc寓辱，維護自身leader地位
• candidate: 如果一個follower長時間沒有收到請求压状，會轉(zhuǎn)變成candidate魂贬，candidate準備發(fā)起投票競選leader
• follower: 節(jié)點的初始狀態(tài)，或者收到rpc轉(zhuǎn)換為該狀態(tài)籽前；響應(yīng)來自其他節(jié)點的請求亭珍，并轉(zhuǎn)發(fā)client端的請求到leader
• term: 周期，集群的邏輯時間枝哄，遞增肄梨，每個周期都開始于一輪投票
• 集群節(jié)點數(shù)應(yīng)該為奇數(shù)，便于收集半數(shù)以上選票
• RPC, 有三種RPC:
  • RequestVote, candidate 發(fā)起的投票RPC
  • AppendEntries, leader發(fā)送的日志同步RPC挠锥， 日志項為空時為心跳RPC
  • InstallSnapshot峭范，發(fā)送日志快照，（leader已經(jīng)刪除快照點之前的日志）使follower保持同步

image

• 復(fù)制狀態(tài)機
  用于在多個節(jié)點系統(tǒng)上管理來自客戶端命令的日志瘪贱，按照日志的順序嚴格執(zhí)行日志中的命令，保證有相同的輸入辆毡，就有相同的輸出菜秦。
  一致性算法只需要保證每個節(jié)點上日志相同，復(fù)制狀態(tài)機就能保證每個節(jié)點最終存儲的狀態(tài)是一致的舶掖。

raft主要分成三個部分：

• 領(lǐng)導(dǎo)人選舉
• 日志復(fù)制
• 安全性
• 日志壓縮

• 客戶端交互

  
  
  image

領(lǐng)導(dǎo)人選舉

在系統(tǒng)初始化時球昨，所有的節(jié)點都會被初始化為follower，leader會被選舉出來眨攘。follower會周期性的接收到來自leader的心跳rpc主慰，以維持follower的狀態(tài)。若在選舉超時時間內(nèi)沒有收到rpc鲫售，follower就會選舉超時共螺，該超時時間在一個范圍內(nèi)隨機（如150-300ms）。超時后情竹，follower就自增自己的currentTerm,成為candidate藐不，并給自己投票，然后向其他服務(wù)器發(fā)送投票請求rpc秦效，follower處理投票請求rpc時遵循先到先得的與原則雏蛮。candidate會一直處于這個狀態(tài)直到下列某一情況發(fā)生：

1. 贏得大多數(shù)選票，成為leader
2. 其他服務(wù)器成為leader
3. 沒有任何一個服務(wù)器成為leader
   如果集群中同時出現(xiàn)兩個candidate阱州，其中一個競選成功挑秉，成為leader，發(fā)送心跳rpc苔货，另外一個競選失敗的candidate在收到心跳rpc的term至少跟自己的term一樣大時會轉(zhuǎn)變?yōu)閒ollower犀概。

日志復(fù)制

以一個請求來說明日志的復(fù)制流程：
leader

1. 客戶端發(fā)送set a = 1的請求到leader節(jié)點
2. leader節(jié)點在本地添加一條日志立哑，本地有兩條索引記錄日志的提交和應(yīng)用情況，committedIndex 日志的提交索引, appliedIndex 日志應(yīng)用到狀態(tài)機的索引阱冶。這一步日志還沒有提交刁憋，兩條索引還是指向上一條日志。
3. leader向集群其他節(jié)點廣播該日志 AppendEntires消息
   follower
4. follower收到AppendEntires消息木蹬，在本地添加AppendEntires對應(yīng)的日志至耻，該日志還沒有提交。
5. follower節(jié)點向leader節(jié)點應(yīng)答AppendEntires消息镊叁。
   leader
6. 當(dāng)leader節(jié)點收到集群半數(shù)以上節(jié)點AppendEntires的應(yīng)答響應(yīng)時尘颓，就認為set a = 1 命令成功復(fù)制，可以進行提交晦譬，于是修改本地committedIndex指向最新存儲的set a = 1的日志疤苹，而 appliedIndex保持不變
7. 提交之后，通知應(yīng)用層該命令可以提交敛腌，此時會修改appliedIndex為最新的committedIndex
8. leader節(jié)點在下一次給follower的AppendEntires請求中會帶上最新的committedIndex索引卧土，follower收到請求后會根據(jù)請求中的committedIndex修改本地的committedIndex

leader需要根據(jù)集群節(jié)點對AppendEntires的響應(yīng)來判斷一條日志是否被復(fù)制到半數(shù)以上節(jié)點。當(dāng)leader收到半數(shù)以上的響應(yīng)像樊，就認為該日志已經(jīng)復(fù)制成功尤莺。此時leader宕機時，后續(xù)新當(dāng)選的領(lǐng)導(dǎo)人肯定是在已成功接收最新日志的節(jié)點中產(chǎn)生生棍，還是能保證該日志被提交颤霎。

日志數(shù)據(jù)不一致問題：
Raft通過將將leader日志復(fù)制到follower節(jié)點，并覆蓋follower節(jié)點中與leader不一致的日志涂滴。leader節(jié)點為每個節(jié)點存儲了兩個記錄：

• nextIndex是下一次給該節(jié)點同步日志時的日志索引友酱，初始化的時候為leader日志的last log index+1
• matchIndex已知復(fù)制到該節(jié)點最大的日志索引, 初始化為0

AppendEntries RPC 中包括：

• prevLogIndex: 對應(yīng)節(jié)點nextIndex的的前一條日志的索引
• prevLogTerm：對應(yīng)節(jié)點nextIndex的的前一條日志的周期號
• entries[]: 需要復(fù)制到節(jié)點的日志條目
  因為leader給follower節(jié)點發(fā)送新的日志時，需要發(fā)送上一條日志的索引和周期與節(jié)點存儲的日志和索引做比較柔纵，節(jié)點在日志校驗不一致時會拒絕該條日志的復(fù)制請求缔杉。leader收到拒絕響應(yīng)后，會nextIndex--搁料，繼續(xù)發(fā)送AppendEntries壮吩，直到收到同意，leader就知道節(jié)點上與自己日志一致的位置加缘，就可以設(shè)置matchIndex鸭叙。找到日志一致的位置后，就可以將后續(xù)不一致的日志刪除拣宏，并將leader的日志復(fù)制上去沈贝。

狀態(tài)的持久化存儲和server的重啟：

• server在收到log entries時，需要在響應(yīng)leader之前進行l(wèi)og的持久化存儲
• server上的commit id可以臨時存儲勋乾，因為即使所以節(jié)點都重啟宋下，新leader當(dāng)選嗡善，就會確認最新的commit id，并同步到 其他節(jié)點
• 狀態(tài)機学歧，既可以是臨時存儲也可以做持久存儲罩引。
  • 一個臨時存儲的狀態(tài)機必須在重啟后應(yīng)用所有的log entries來恢復(fù)狀態(tài)
  • 持久存儲的狀態(tài)機在重啟后已經(jīng)應(yīng)用的大多數(shù)entries，但為了避免重啟后重復(fù)應(yīng)用log枝笨，狀態(tài)機需要持久化最新的log entries應(yīng)用索引

領(lǐng)導(dǎo)權(quán)轉(zhuǎn)移：
Raft允許server將自己的領(lǐng)導(dǎo)權(quán)轉(zhuǎn)移其他的server袁铐，有兩種場景：

1. 當(dāng)前l(fā)eader需要重啟維護，當(dāng)leader 選擇先變成follower再下線横浑，這段時間集群會出現(xiàn)選舉超時剔桨，集群不可用，通過
   領(lǐng)導(dǎo)權(quán)的轉(zhuǎn)移可以避免在這種情況徙融。
2. 當(dāng)其他一些Server更適合作為leader 時洒缀，如leader的負載較高，如廣域網(wǎng)部署欺冀，主要數(shù)據(jù)中心的延時較低树绩，server 更適合作為leader。raft可以定時觀察集群內(nèi)是否有更適合的server最為leader隐轩，然后將領(lǐng)導(dǎo)權(quán)交給它葱峡。

為了選舉能夠成功，當(dāng)前l(fā)eader需要將自己的log entries發(fā)送給目標Server龙助，保證目標server上持有所有提交的log entries，但后發(fā)起leader競選蛛芥，不需要等待選舉超時提鸟。

• 當(dāng)前l(fā)eader停止接收客戶端請求
• 當(dāng)前l(fā)eader更新目標server的日志，使之跟自己的log entries匹配
• 當(dāng)前l(fā)eader給目標Server發(fā)送TimeoutNow request仅淑，以觸發(fā)目標server發(fā)起leader競選称勋。目標server大概率會在其他 server之前發(fā)起競選。集群其他server接收到該server帶有新的term的message涯竟，當(dāng)前l(fā)eader會轉(zhuǎn)變?yōu)閒ollower赡鲜。

當(dāng)目標server失敗時，當(dāng)前l(fā)eader就會中斷領(lǐng)導(dǎo)權(quán)轉(zhuǎn)移過程庐船，恢復(fù)客戶端請求處理银酬。

集群成員變化

image

image

現(xiàn)在還有兩個問題：

• 新成員加入時，原先集群三臺機器中一臺宕機妇菱，這時就會影響新日志記錄的commit
• 若新添加的server速度較快承粤，在新添加的server數(shù)目少于舊server時，新配置的日志可以通過舊server來提交恶耽，當(dāng)新servre的數(shù)目等于舊server時密任，新配置的日志的提交就需要新server的參與，如果此時新server的日志遠落后于舊server時偷俭，這個集群的日志提交就需要等待新server的日志趕上舊的server浪讳。

為了解決新成員加入時，成員需要追趕leader日志的問題涌萤，raft 引入了 non-voting server淹遵，等到日志同步完成時再開始加入集群。首先會引入round的概念负溪，每個round開始時透揣，leader將non-voting server少于leader的日志同步到non-voting server，round中新接收的日志會在下一個round同步川抡。 若沒有新日志發(fā)送到leader時辐真，一個round開始會馬上結(jié)束，進入下一個round崖堤，當(dāng)進行round的次數(shù)超過閾值時侍咱，leader就將新的server加入到集群

當(dāng)前l(fā)eader的移除
當(dāng)要下線集群的leader時，首先客戶端會發(fā)送一條C new的配置請求密幔，C new會以日志的形式復(fù)制到集群大多數(shù)節(jié)點 楔脯， 只有當(dāng)該日志提交之后，leader才可以轉(zhuǎn)變?yōu)閒ollower再進一步下線胯甩，只有當(dāng)C new復(fù)制到大多數(shù)節(jié)點昧廷，集群才有可能從C new的成員中選舉出leader。leader才可以轉(zhuǎn)變?yōu)閒ollower偎箫，此時C new的成員會選舉超時木柬，從而選舉產(chǎn)生 leader。舊 leader的不可用到新leader的產(chǎn)生的這段時間系統(tǒng)是處于不可用的狀態(tài)淹办。
下線成員對系統(tǒng)的擾動
當(dāng)下線非leader節(jié)點時弄诲，該節(jié)點就收不到新的配置C new，也就不知道自己是否下線，此時leader上新的配置生效之后齐遵，就 不再給將要下線的節(jié)點發(fā)送heartbeat寂玲。該節(jié)點就會超時并發(fā)起選舉，選舉會擾亂當(dāng)前系統(tǒng)leader的工作梗摇，由于周期高于當(dāng)前l(fā)eader拓哟，leader就會轉(zhuǎn)變?yōu)閒ollower, 發(fā)起選舉的節(jié)點不在系統(tǒng)內(nèi)不會當(dāng)前選，系統(tǒng)內(nèi)會重新選舉出一個leader伶授。所以 raft提出了一個已解決方案：
為leader競選階段引入一個新的階段断序，pre-vote，candidate發(fā)起投票之前會詢問其他節(jié)點自己的日志是否足夠新的來競選leader糜烹。但pre-vote的引入并不能解決上述問題违诗。

image

安全性

前面描述的選舉和日志復(fù)制機制還不能完全保證每個狀態(tài)機都能根據(jù)相同的日志按照相同的順序執(zhí)行命令吼拥。例如一個follower因為網(wǎng)絡(luò)問題錯過了多次的日志復(fù)制，然后網(wǎng)絡(luò)恢復(fù)线衫，集群leader宕機凿可，follower當(dāng)選為leader，該follower缺少上一個leader 提交的日志，就會導(dǎo)致這些日志被新的leader覆蓋枯跑。

• 選舉限制
  為了避免日志覆蓋惨驶，raft引入了選舉限制，即raft要求只有當(dāng)選為leader的節(jié)點的日志需要包含所有的commits entries. 選舉的RequestVote包含candiddate的日志信息敛助，如果日志跟投票節(jié)點一樣新粗卜，candiddate將收到選票。一樣新判斷條件是通過比較日志的index和term纳击。term越大越新续扔，index越大越新。
  
  image
• 提交未提交日志
  一個新的leader當(dāng)選后還有未提交的日志焕数，leader是無法根據(jù)日志已經(jīng)復(fù)制到大多數(shù)機器上時就認為該日志是已經(jīng)提交的纱昧，上圖是一個例子。
  term 2時s1當(dāng)選為leader堡赔，并在復(fù)制了index=2處的日志到s2上识脆，然后宕機，接著s5當(dāng)選leader,接收了一條不同的日志加匈，然后宕機存璃，s1繼續(xù)當(dāng)選，并將之前的日志復(fù)制到s3上雕拼，此時該日志已經(jīng)復(fù)制到絕大多數(shù)機器上了纵东，日志未提交，如果此時s1再次宕機啥寇，s5當(dāng)選（s3,4,5的選票）偎球，日志3將會覆蓋日志2. 但如果s1在宕機之前還復(fù)制了當(dāng)前term的日志4大多 數(shù)機器上，那么日志2就不會被覆蓋辑甜。
  因此當(dāng)前周期的leader需要提一個當(dāng)前 term的日志衰絮，才能確保提交old term 的日志。也就是說磷醋，在當(dāng)前 term的日志美歐提交之前猫牡，old term的日志是有可能被覆蓋。上面的例子中邓线，在有當(dāng)前 term日志提交情況下淌友，由于選舉限制，s5是不可能當(dāng)選為leader的骇陈。
  補充說明：
  情況b中震庭，s5能成為新leader的前提是日志2還沒有被s1復(fù)制到大多數(shù)節(jié)點上（日志2不可能是已提交），否則s5就會因為選舉限制而不會當(dāng)選leader你雌。因此日志2被s1復(fù)制到大多數(shù)節(jié)點情況必須是在s1重新當(dāng)選leader后的本term進行的器联。此時為了確保該日志提交，需要在本term提交一個新日志或者dummy日志。

日志壓縮

隨著raft處理客戶端請求的增長拨拓，日志記錄也會越來越長肴颊，占用的存儲空間也會越來越多，也會花費越來越多的時間進行日志重放千元。但在一個實際的系統(tǒng)當(dāng)中苫昌，存儲空間不可能沒有限制，因此采取一種機制來丟棄部分日志記錄勢在必行幸海。
快照是最簡單的進行日志壓縮的方式祟身。每個節(jié)點獨立的生成快照，通過將整個狀態(tài)機的狀態(tài)都寫入快照然后存儲到穩(wěn)定的存儲介質(zhì)上方式物独，可以允許快照點之前的所有日志可以被刪除袜硫。Raft還會在快照中保存一部分元數(shù)據(jù)，也就是快照可以替換的所有日志記錄的最一條（最后一條狀態(tài)機執(zhí)行的日志記錄）挡篓，這條日志是用來做AppendEntries時的日志一致性檢查的婉陷。同時為了保證集群成員變化，快照中還會保存應(yīng)用最后一條日志時的配置文件官研。

• 并行快照
  快照是非常耗時的秽澳，為了避免影響集群服務(wù)客戶端請求，快照需要并行的進行戏羽。copy-on-write技術(shù)可以保證新的日志更新不會影響的快照的進行担神。有兩種方法可以保證快照的正確進行。
  • 狀態(tài)機可以采用不可變的數(shù)據(jù)結(jié)構(gòu)始花，快照操作可以在舊的狀態(tài)的上操作妄讯，因為狀態(tài)機不會修改舊的數(shù)據(jù)結(jié)構(gòu)。
  • 另外酷宵，操作系統(tǒng)的copy-on-write技術(shù)可以用來支持快照操作亥贸。例如的Linux操作系統(tǒng)fork系統(tǒng)調(diào)用可以拷貝當(dāng)前進程的整個地址空間。fork之后子進程只是引用了原進程的所有數(shù)據(jù)結(jié)構(gòu)浇垦，并沒有發(fā)生實際的數(shù)據(jù)復(fù)制直到子進程或者父進程修改了本地數(shù)據(jù)結(jié)構(gòu)炕置，該數(shù)據(jù)結(jié)構(gòu)才會被復(fù)制。通過這種機制男韧，避免了巨大的內(nèi)存復(fù)制開銷朴摊，同時是的父進程能服務(wù)客戶端請求
• 快照進行時機
  Raft需要決定何時執(zhí)行快照操縱，執(zhí)行的頻率太高會浪費磁盤的io和其他資源煌抒，頻率太低有可能會造成日志記錄積累太多仍劈。
  一個可選方案是為日志記錄大小設(shè)定閾值厕倍，日志記錄大小超過閾值時便會觸發(fā)快照操作寡壮，但這樣帶來問題就是當(dāng)狀態(tài)機的狀態(tài)較少時，需要積累較多的日志才會觸發(fā)一次快照操作。
  更好的方法是比較快照的大小與日志記錄的大小况既，當(dāng)快照大小將比日志記錄大小小很多倍時这溅，此時執(zhí)行快照就是一個非常值得的操作。但是棒仍，計算當(dāng)前日志記錄執(zhí)行快照后生成的快照大小是非常耗費資源和同時計算本身也是非常困難的悲靴。
  一個折中的方案，使用前一個快照的大小與當(dāng)前日志記錄的大小做比較，即當(dāng)前日志記錄的大小超過前一個快照的大小成一配置的擴展因子，擴展因子用來權(quán)衡磁盤io與日志空間占用九府。
  未來的可選優(yōu)化途徑涡驮，由于快照始終會造成cpu和磁盤io的突增，會導(dǎo)致用戶請求的延時處理经伙。可以根據(jù)計劃的方式來執(zhí)行快照，避免同一時間大部分機器都在執(zhí)行快照胳徽，通過計劃，只允許一定數(shù)量的機器在某一時間執(zhí)行快照操作爽彤。
  一個可行的計劃方式：Raft算法只要求集群中超過能正常工作养盗，集群就能正常工作，所以當(dāng)一個leader想要執(zhí)行快照操作時适篙，可以主動下線往核，在其不對外提供服務(wù)時執(zhí)行快照操作。
• 實現(xiàn)中的corner case
  • 保存和加載快照
    • 實現(xiàn)狀態(tài)機到磁盤的文件的流接口匙瘪，好處是避免在內(nèi)存中保存大量數(shù)據(jù)
    • 壓縮流以及使用和檢驗
    • 使用臨時文件铆铆，避免狀態(tài)機加載不完整的快照文件。
  • 傳輸快照
    • 快照傳輸?shù)男什恢匾?/li>
  • 丟棄日志記錄和消除不安全日志的訪問
    • 日志記錄獲取時的數(shù)組越界問題
  • 快照中使用copy-on-write技術(shù)
    • 采用fork雖然復(fù)雜但收益明顯
  • 何時執(zhí)行快照
    • 開發(fā)時丹喻，每次commit時執(zhí)行快照