概念說明

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

image

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

raft主要分成三個(gè)部分：

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

• 客戶端交互

  
  
  image

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

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

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

日志復(fù)制

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

1. 客戶端發(fā)送set a = 1的請(qǐng)求到leader節(jié)點(diǎn)
2. leader節(jié)點(diǎn)在本地添加一條日志，本地有兩條索引記錄日志的提交和應(yīng)用情況，committedIndex 日志的提交索引, appliedIndex 日志應(yīng)用到狀態(tài)機(jī)的索引。這一步日志還沒有提交，兩條索引還是指向上一條日志。
3. leader向集群其他節(jié)點(diǎn)廣播該日志 AppendEntires消息
   follower
4. follower收到AppendEntires消息，在本地添加AppendEntires對(duì)應(yīng)的日志，該日志還沒有提交。
5. follower節(jié)點(diǎn)向leader節(jié)點(diǎn)應(yīng)答AppendEntires消息。
   leader
6. 當(dāng)leader節(jié)點(diǎn)收到集群半數(shù)以上節(jié)點(diǎn)AppendEntires的應(yīng)答響應(yīng)時(shí)，就認(rèn)為set a = 1 命令成功復(fù)制，可以進(jìn)行提交，于是修改本地committedIndex指向最新存儲(chǔ)的set a = 1的日志，而 appliedIndex保持不變
7. 提交之后，通知應(yīng)用層該命令可以提交，此時(shí)會(huì)修改appliedIndex為最新的committedIndex
8. leader節(jié)點(diǎn)在下一次給follower的AppendEntires請(qǐng)求中會(huì)帶上最新的committedIndex索引，follower收到請(qǐng)求后會(huì)根據(jù)請(qǐng)求中的committedIndex修改本地的committedIndex

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

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

• nextIndex是下一次給該節(jié)點(diǎn)同步日志時(shí)的日志索引，初始化的時(shí)候?yàn)閘eader日志的last log index+1
• matchIndex已知復(fù)制到該節(jié)點(diǎn)最大的日志索引, 初始化為0

AppendEntries RPC 中包括：

• prevLogIndex: 對(duì)應(yīng)節(jié)點(diǎn)nextIndex的的前一條日志的索引
• prevLogTerm：對(duì)應(yīng)節(jié)點(diǎn)nextIndex的的前一條日志的周期號(hào)
• entries[]: 需要復(fù)制到節(jié)點(diǎn)的日志條目
  因?yàn)閘eader給follower節(jié)點(diǎn)發(fā)送新的日志時(shí)，需要發(fā)送上一條日志的索引和周期與節(jié)點(diǎn)存儲(chǔ)的日志和索引做比較，節(jié)點(diǎn)在日志校驗(yàn)不一致時(shí)會(huì)拒絕該條日志的復(fù)制請(qǐng)求。leader收到拒絕響應(yīng)后，會(huì)nextIndex--，繼續(xù)發(fā)送AppendEntries，直到收到同意，leader就知道節(jié)點(diǎn)上與自己日志一致的位置，就可以設(shè)置matchIndex。找到日志一致的位置后，就可以將后續(xù)不一致的日志刪除，并將leader的日志復(fù)制上去。

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

• server在收到log entries時(shí)，需要在響應(yīng)leader之前進(jìn)行l(wèi)og的持久化存儲(chǔ)
• server上的commit id可以臨時(shí)存儲(chǔ)，因?yàn)榧词顾怨?jié)點(diǎn)都重啟，新leader當(dāng)選，就會(huì)確認(rèn)最新的commit id，并同步到 其他節(jié)點(diǎn)
• 狀態(tài)機(jī)，既可以是臨時(shí)存儲(chǔ)也可以做持久存儲(chǔ)。
  • 一個(gè)臨時(shí)存儲(chǔ)的狀態(tài)機(jī)必須在重啟后應(yīng)用所有的log entries來恢復(fù)狀態(tài)
  • 持久存儲(chǔ)的狀態(tài)機(jī)在重啟后已經(jīng)應(yīng)用的大多數(shù)entries，但為了避免重啟后重復(fù)應(yīng)用log，狀態(tài)機(jī)需要持久化最新的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需要重啟維護(hù)，當(dāng)leader 選擇先變成follower再下線，這段時(shí)間集群會(huì)出現(xiàn)選舉超時(shí)，集群不可用，通過
   領(lǐng)導(dǎo)權(quán)的轉(zhuǎn)移可以避免在這種情況。
2. 當(dāng)其他一些Server更適合作為leader 時(shí)，如leader的負(fù)載較高，如廣域網(wǎng)部署，主要數(shù)據(jù)中心的延時(shí)較低，server 更適合作為leader。raft可以定時(shí)觀察集群內(nèi)是否有更適合的server最為leader，然后將領(lǐng)導(dǎo)權(quán)交給它。

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

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

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

集群成員變化

image

image

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

• 新成員加入時(shí)，原先集群三臺(tái)機(jī)器中一臺(tái)宕機(jī)，這時(shí)就會(huì)影響新日志記錄的commit
• 若新添加的server速度較快，在新添加的server數(shù)目少于舊server時(shí)，新配置的日志可以通過舊server來提交，當(dāng)新servre的數(shù)目等于舊server時(shí)，新配置的日志的提交就需要新server的參與，如果此時(shí)新server的日志遠(yuǎn)落后于舊server時(shí)，這個(gè)集群的日志提交就需要等待新server的日志趕上舊的server。

為了解決新成員加入時(shí)，成員需要追趕leader日志的問題，raft 引入了 non-voting server，等到日志同步完成時(shí)再開始加入集群。首先會(huì)引入round的概念，每個(gè)round開始時(shí)，leader將non-voting server少于leader的日志同步到non-voting server，round中新接收的日志會(huì)在下一個(gè)round同步。 若沒有新日志發(fā)送到leader時(shí)，一個(gè)round開始會(huì)馬上結(jié)束，進(jìn)入下一個(gè)round，當(dāng)進(jìn)行round的次數(shù)超過閾值時(shí)，leader就將新的server加入到集群

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

image

安全性

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

• 選舉限制
  為了避免日志覆蓋，raft引入了選舉限制，即raft要求只有當(dāng)選為leader的節(jié)點(diǎn)的日志需要包含所有的commits entries. 選舉的RequestVote包含candiddate的日志信息，如果日志跟投票節(jié)點(diǎn)一樣新，candiddate將收到選票。一樣新判斷條件是通過比較日志的index和term。term越大越新，index越大越新。
  
  image
• 提交未提交日志
  一個(gè)新的leader當(dāng)選后還有未提交的日志，leader是無法根據(jù)日志已經(jīng)復(fù)制到大多數(shù)機(jī)器上時(shí)就認(rèn)為該日志是已經(jīng)提交的，上圖是一個(gè)例子。
  term 2時(shí)s1當(dāng)選為leader，并在復(fù)制了index=2處的日志到s2上，然后宕機(jī)，接著s5當(dāng)選leader,接收了一條不同的日志，然后宕機(jī)，s1繼續(xù)當(dāng)選，并將之前的日志復(fù)制到s3上，此時(shí)該日志已經(jīng)復(fù)制到絕大多數(shù)機(jī)器上了，日志未提交，如果此時(shí)s1再次宕機(jī)，s5當(dāng)選（s3,4,5的選票），日志3將會(huì)覆蓋日志2. 但如果s1在宕機(jī)之前還復(fù)制了當(dāng)前term的日志4大多 數(shù)機(jī)器上，那么日志2就不會(huì)被覆蓋。
  因此當(dāng)前周期的leader需要提一個(gè)當(dāng)前 term的日志，才能確保提交old term 的日志。也就是說，在當(dāng)前 term的日志美歐提交之前，old term的日志是有可能被覆蓋。上面的例子中，在有當(dāng)前 term日志提交情況下，由于選舉限制，s5是不可能當(dāng)選為leader的。
  補(bǔ)充說明：
  情況b中，s5能成為新leader的前提是日志2還沒有被s1復(fù)制到大多數(shù)節(jié)點(diǎn)上（日志2不可能是已提交），否則s5就會(huì)因?yàn)檫x舉限制而不會(huì)當(dāng)選leader。因此日志2被s1復(fù)制到大多數(shù)節(jié)點(diǎn)情況必須是在s1重新當(dāng)選leader后的本term進(jìn)行的。此時(shí)為了確保該日志提交，需要在本term提交一個(gè)新日志或者dummy日志。

日志壓縮

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

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