Raft 算法濃縮總結(jié)
Raft 論文給出了下面的表格，用于總結(jié) Raft 算法精華 。
| 特性 | 解釋 |
|---|---|
| 選舉安全特性 | 對于一個給定的任期號，最多只會有一個領(lǐng)導(dǎo)人被選舉出來 |
| 領(lǐng)導(dǎo)人只附加原則 | 領(lǐng)導(dǎo)人絕對不會刪除或者覆蓋自己的日志，只會增加 |
| 日志匹配原則 | 如果兩個日志在相同的索引位置的日志條目的任期號相同，那么我們就認(rèn)為這個日志從頭到這個索引位置之間全部完全相同 |
| 領(lǐng)導(dǎo)人完全特性 | 如果某個日志條目在某個任期號中已經(jīng)被提交，那么這個條目必然出現(xiàn)在更大任期號的所有領(lǐng)導(dǎo)人中 |
| 狀態(tài)機(jī)安全特性 | 如果一個領(lǐng)導(dǎo)人已經(jīng)在給定的索引值位置的日志條目應(yīng)用到狀態(tài)機(jī)中，那么其他任何的服務(wù)器在這個索引位置不會提交一個不同的日志 |
實際上，這些精華都是一條條限制推出來的。讓我們一起看看是怎么推出來的。
選舉安全特性
描述： 對于一個給定的任期號，最多只會有一個領(lǐng)導(dǎo)人被選舉出來
如何實現(xiàn)？
Raft 規(guī)定：每個節(jié)點最多只會對一個任期號投出一張選票，按照先來先服務(wù)的原則（隨機(jī)時間的重要性），同時，當(dāng)一個候選人從整個集群的大多數(shù)節(jié)點獲得了針對同一個任期號的選票，那么他就贏得了這次選舉并成為領(lǐng)導(dǎo)人。
領(lǐng)導(dǎo)人只附加原則
描述：領(lǐng)導(dǎo)人絕對不會刪除或者覆蓋自己的日志，只會增加。
這個不需要保證別的規(guī)則保證，服務(wù)器自己搞定。
日志匹配原則
描述：如果兩個日志在相同的索引位置的日志條目的任期號相同，那么我們就認(rèn)為這個日志從頭到這個索引位置之間全部完全相同。
如何實現(xiàn)？
Raft 維護(hù)著以下特性：
- 如果在不同的日志中的兩個條目擁有相同的索引和任期號，那么他們存儲了相同的指令。
- 如果在不同的日志中的兩個條目擁有相同的索引和任期號，那么他們之前的所有日志條目也全部相同。
第一個特性來自這樣的一個事實，領(lǐng)導(dǎo)人最多在一個任期里在指定的一個日志索引位置創(chuàng)建一條日志條目，同時日志條目在日志中的位置也從來不會改變。
第二個特性由附加日志 RPC 的一個簡單的一致性檢查所保證。在發(fā)送附加日志 RPC 的時候，領(lǐng)導(dǎo)人會把新的日志條目緊接著之前的條目的索引位置和任期號包含在里面。如果跟隨者在它的日志中找不到包含相同索引位置和任期號的條目，那么他就會拒絕接收新的日志條目。
領(lǐng)導(dǎo)人完全特性
解釋：如果某個日志條目在某個任期號中已經(jīng)被提交，那么這個條目必然出現(xiàn)在更大任期號的所有領(lǐng)導(dǎo)人中。
規(guī)則保證：
當(dāng)一個 leader 提交了某條日志，然后崩潰了，候選者如果想當(dāng)選 leader，必須滿足以下條件：
- 首先比較任期號，誰都任期號大，誰就新。
- 如果任期號相同，那誰的日志長，誰就新。
- 獲取過半投票者的選票。
同時，需要滿足：leader 只能在自己當(dāng)前任期的日志滿足多數(shù)規(guī)則時，才能提交。
所以，當(dāng)之前的 leader 成功提交最后一條日志，后面的候選者，必須包含過半已提交的最后一條日志的投票者的選票，才能成為 leader。
狀態(tài)機(jī)安全特性
描述： 如果一個領(lǐng)導(dǎo)人已經(jīng)在給定的索引值位置的日志條目應(yīng)用到狀態(tài)機(jī)中，那么其他任何的服務(wù)器在這個索引位置不會提交一個不同的日志。
解釋：
通過領(lǐng)導(dǎo)人完全特性，我們就能證明狀態(tài)機(jī)安全特性，即如果已經(jīng)服務(wù)器已經(jīng)在某個給定的索引值應(yīng)用了日志條目到自己的狀態(tài)機(jī)里，那么其他的服務(wù)器不會應(yīng)用一個不一樣的日志到同一個索引值上。
在一個服務(wù)器應(yīng)用一條日志條目到他自己的狀態(tài)機(jī)中時，他的日志必須和領(lǐng)導(dǎo)人的日志，在該條目和之前的條目上相同，并且已經(jīng)被提交。
現(xiàn)在我們來考慮在任何一個服務(wù)器應(yīng)用一個指定索引位置的日志的最小任期；日志完全特性保證擁有更高任期號的領(lǐng)導(dǎo)人會存儲相同的日志條目，所以之后的任期里應(yīng)用某個索引位置的日志條目也會是相同的值。因此，狀態(tài)機(jī)安全特性是成立的。
參考
[英文 paper pdf 地址]ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf
[Raft paper 中文翻譯 —— 尋找一種易于理解的一致性算法（擴(kuò)展版）]github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
[Raft 作者講解視頻]youtube.com/watch?v=YbZ3zDzDnrw&feature=youtu.be
[Raft 作者講解視頻對應(yīng)的 PPT] 2.cs.uh.edu/~paris/6360/PowerPoint/Raft.ppt
[一個簡單的講解 Raft 協(xié)議的動畫]thesecretlivesofdata.com/raft/
