1.raft的原理動畫：http://thesecretlivesofdata.com/raft/
raft三種狀態(tài)：跟隨者，候選人赋除，領(lǐng)導者
客戶-》領(lǐng)導者-〉分發(fā)給跟隨者阱缓，跟隨者成為不了候選人或者候選人失敗后退居到跟隨者狀態(tài)。這樣領(lǐng)導分發(fā)的時候就不存在候選人狀態(tài)
2.實際的解釋：
013 一致性算法 - Raft
Raft 狀態(tài)
一個 Raft 集群包含若干個服務器節(jié)點贤重；通常是 5 個茬祷，這允許整個系統(tǒng)容忍 2 個節(jié)點的失效，每個節(jié)點處于以下三種狀態(tài)之一：
-
follower（跟隨者）：所有結(jié)點都以follower的狀態(tài)開始并蝗。如果沒收到leader消息則會變成candidate狀態(tài)祭犯。 -
candidate（候選人）：會向其他結(jié)點“拉選票”，如果得到大部分的票則成為leader滚停。這個過程就叫做Leader選舉(Leader Election)沃粗。 -
leader（領(lǐng)導者）：所有對系統(tǒng)的修改都會先經(jīng)過leader。
Raft 一致性算法
Raft通過選出一個leader來簡化日志副本的管理键畴，例如最盅，日志項(log entry)只允許從leader流向follower。
基于leader的方法起惕，Raft算法可以分解成三個子問題：
Leader election (領(lǐng)導選舉)：原來的leader掛掉后涡贱，必須選出一個新的leader
Log replication (日志復制)：leader從客戶端接收日志，并復制到整個集群中
Safety (安全性)：如果有任意的server將日志項回放到狀態(tài)機中了惹想，那么其他的server只會回放相同的日志項
Leader election (領(lǐng)導選舉)
Raft 使用一種心跳機制來觸發(fā)領(lǐng)導人選舉问词。當服務器程序啟動時，他們都是 follower(跟隨者) 身份嘀粱。如果一個跟隨者在一段時間里沒有接收到任何消息激挪，也就是選舉超時，然后他就會認為系統(tǒng)中沒有可用的領(lǐng)導者然后開始進行選舉以選出新的領(lǐng)導者锋叨。要開始一次選舉過程垄分，follower 會給當前term加1并且轉(zhuǎn)換成candidate狀態(tài)。
然后他會并行的向集群中的其他服務器節(jié)點發(fā)送請求投票的 RPCs 來給自己投票娃磺。候選人的狀態(tài)維持直到發(fā)生以下任何一個條件發(fā)生的時候薄湿，
-
他自己贏得了這次的選舉
- 如果這個節(jié)點贏得了半數(shù)以上的vote就會成為leader，每個節(jié)點會按照first-come-first-served的原則進行投票偷卧，并且一個term中只能投給一個節(jié)點嘿般， 這樣就保證了一個term最多有一個節(jié)點贏得半數(shù)以上的vote。
- 當一個節(jié)點贏得選舉涯冠， 他會成為leader炉奴， 并且給所有節(jié)點發(fā)送這個信息， 這樣所有節(jié)點都會回退成follower蛇更。
-
其他的服務器成為領(lǐng)導者
如果在等待選舉期間瞻赶，candidate接收到其他server要成為leader的RPC，分兩種情況處理：
- 如果leader的term大于或等于自身的term派任，那么改
candidate會轉(zhuǎn)成follower狀態(tài) - 如果leader的term小于自身的term砸逊，那么會拒絕該
leader，并繼續(xù)保持candidate狀態(tài)
- 如果leader的term大于或等于自身的term派任，那么改
-
一段時間之后沒有任何一個獲勝的人
有可能掌逛，很多follower同時變成candidate师逸，導致沒有candidate能獲得大多數(shù)的選舉，從而導致無法選出主豆混。當這個情況發(fā)生時篓像，每個candidate會超時动知，然后重新發(fā)增加term，發(fā)起新一輪選舉RPC员辩。需要注意的是盒粮，如果沒有特別處理，可能出導致無限地重復選主的情況奠滑。
Raft采用隨機定時器的方法來避免上述情況丹皱，每個candidate選擇一個時間間隔內(nèi)的隨機值，例如150-300ms宋税，采用這種機制摊崭，一般只有一個server會進入candidate狀態(tài)，然后獲得大多數(shù)server的選舉杰赛，最后成為主呢簸。每個candidate在收到leader的心跳信息后會重啟定時器，從而避免在leader正常工作時淆攻，會發(fā)生選舉的情況阔墩。
Log replication (日志復制)
當選出 leader 后，它會開始接受客戶端請求瓶珊，每個請求會帶有一個指令啸箫，可以被回放到狀態(tài)機中。leader 把指令追加成一個log entry伞芹，然后通過AppendEntries RPC并行的發(fā)送給其他的server忘苛，當改entry被多數(shù)派server復制后，leader 會把該entry回放到狀態(tài)機中唱较，然后把結(jié)果返回給客戶端扎唾。
當 follower 宕機或者運行較慢時，leader 會無限地重發(fā)AppendEntries給這些follower南缓，直到所有的follower都復制了該log entry胸遇。
raft的log replication保證以下性質(zhì)(Log Matching Property)：
如果兩個log entry有相同的index和term，那么它們存儲相同的指令
如果兩個log entry在兩份不同的日志中汉形，并且有相同的index和term纸镊，那么它們之前的log entry是完全相同的
其中特性一通過以下保證：
- leader在一個特定的term和index下，只會創(chuàng)建一個log entry
- log entry不會改變它們在日志中的位置
特性二通過以下保證：
- AppendEntries會做log entry的一致性檢查概疆，當發(fā)送一個AppendEntriesRPC時逗威，leader會帶上需要復制的log entry前一個log entry的(index, iterm)
如果follower沒有發(fā)現(xiàn)與它一樣的log entry，那么它會拒絕接受新的log entry 這樣就能保證特性二得以滿足岔冀。
安全性
選舉限制
在一些一致性算法中凯旭，即使一臺server沒有包含所有之前已提交的log entry，也能被選為主，這些算法需要把leader上缺失的日志從其他的server拷貝到leader上罐呼，這種方法會導致額外的復雜度鞠柄。相對而言，raft使用一種更簡單的方法弄贿，即它保證所有已提交的log entry都會在當前選舉的leader上春锋，因此矫膨，在raft算法中差凹，日志只會從leader流向follower。
為了實現(xiàn)上述目標侧馅，raft在選舉中會保證危尿，一個candidate只有得到大多數(shù)的server的選票之后，才能被選為主馁痴。得到大多數(shù)的選票表明谊娇，選舉它的server中至少有一個server是擁有所有已經(jīng)提交的log entry的，而leader的日志至少和follower的一樣新罗晕，這樣就保證了leader肯定有所有已提交的log entry济欢。
提交之前任期內(nèi)的日志條目
領(lǐng)導人知道一條當前任期內(nèi)的日志記錄是可以被提交的，只要它被存儲到了大多數(shù)的服務器上小渊。如果一個領(lǐng)導人在提交日志條目之前崩潰了法褥，未來后續(xù)的領(lǐng)導人會繼續(xù)嘗試復制這條日志記錄。然而酬屉，一個領(lǐng)導人不能斷定一個之前任期里的日志條目被保存到大多數(shù)服務器上的時候就一定已經(jīng)提交了半等。下圖展示了一種情況，一條已經(jīng)被存儲到大多數(shù)節(jié)點上的老日志條目呐萨，也依然有可能會被未來的領(lǐng)導人覆蓋掉杀饵。
如上圖的例子，圖（c）就發(fā)生了一個log entry雖然已經(jīng)復制到大多數(shù)的服務器谬擦，但是仍然有可能被覆蓋掉的可能切距，如圖（d），整個發(fā)生的時序如下：
圖a中惨远，S1被選為主谜悟，然后復制到log index為2的log entry到S2上
圖b中，S1掛掉锨络，然后S5獲得了S3赌躺，S4和自身的選舉，成為leader羡儿，然后礼患，其從客戶端收到了一個新的log entry(3)
圖c中，S5掛掉，S1重新正常工作缅叠，又被選為主悄泥，繼續(xù)復制log entry(2)，在log entry(2)被提交前肤粱，S1又掛掉
圖d中弹囚，S5又重新被選為領(lǐng)導者，然后领曼，會把term 3的log entry覆蓋到其他log index為2的log entry
為了上圖描述的情況鸥鹉，Raft 永遠不會通過計算副本數(shù)目的方式去提交一個之前任期內(nèi)的日志條目。只有領(lǐng)導人當前任期里的日志條目通過計算副本數(shù)目可以被提交庶骄；一旦當前任期的日志條目以這種方式被提交毁渗，那么由于日志匹配特性，之前的日志條目也都會被間接的提交单刁。例如灸异，圖e中，如果S1在掛掉前把log entry(4)復制到了大多數(shù)的server后羔飞，就能保證之前的log entry（2）被提交了肺樟，之后S5也就不可能被選為領(lǐng)導者了。
安全性論證
以反證法來證明逻淌，假設任期 T 的領(lǐng)導人（領(lǐng)導人 T）在任期內(nèi)提交了一條日志條目么伯，但是這條日志條目沒有被存儲到未來某個任期的領(lǐng)導人的日志中。設大于 T 的最小任期 U 的領(lǐng)導人 U 沒有這條日志條目恍风。
如果 S1 （任期 T 的領(lǐng)導者）提交了一條新的日志在它的任期里蹦狂，然后 S5 在之后的任期 U 里被選舉為領(lǐng)導人，然后至少會有一個機器朋贬，如 S3凯楔，既擁有來自 S1 的日志，也給 S5 投票了锦募。
在領(lǐng)導人 U 選舉的時候一定沒有那條被提交的日志條目（領(lǐng)導人從不會刪除或者覆蓋任何條目）摆屯。
領(lǐng)導人 T 復制這條日志條目給集群中的大多數(shù)節(jié)點，同時糠亩，領(lǐng)導人U 從集群中的大多數(shù)節(jié)點贏得了選票虐骑。因此，至少有一個節(jié)點（投票者赎线、選民）同時接受了來自領(lǐng)導人T 的日志條目廷没，并且給領(lǐng)導人U 投票了，這個投票者是產(chǎn)生這個矛盾的關(guān)鍵垂寥。
這個投票者必須在給領(lǐng)導人 U 投票之前先接受了從領(lǐng)導人 T 發(fā)來的已經(jīng)被提交的日志條目颠黎；否則他就會拒絕來自領(lǐng)導人 T 的附加日志請求（因為此時他的任期號會比 T 大）另锋。
投票者在給領(lǐng)導人 U 投票時依然保有這條日志條目，因為任何中間的領(lǐng)導人都包含該日志條目（根據(jù)上述的假設）狭归，領(lǐng)導人從不會刪除條目夭坪，并且跟隨者只有和領(lǐng)導人沖突的時候才會刪除條目。
-
投票者把自己選票投給領(lǐng)導人 U 時过椎，領(lǐng)導人 U 的日志必須和投票者自己一樣新室梅。這就導致了兩者矛盾之一。
首先疚宇，如果投票者和領(lǐng)導人 U 的最后一條日志的任期號相同亡鼠，那么領(lǐng)導人 U 的日志至少和投票者一樣長，所以領(lǐng)導人 U 的日志一定包含所有投票者的日志灰嫉。這是另一處矛盾拆宛，因為投票者包含了那條已經(jīng)被提交的日志條目嗓奢，但是在上述的假設里讼撒，領(lǐng)導人 U 是不包含的。
除此之外股耽，領(lǐng)導人 U 的最后一條日志的任期號就必須比投票人大了根盒。此外，他也比 T 大物蝙，因為投票人的最后一條日志的任期號至少和 T 一樣大（他包含了來自任期 T 的已提交的日志）炎滞。創(chuàng)建了領(lǐng)導人 U 最后一條日志的之前領(lǐng)導人一定已經(jīng)包含了那條被提交的日志（根據(jù)上述假設，領(lǐng)導人 U 是第一個不包含該日志條目的領(lǐng)導人）诬乞。所以册赛，根據(jù)日志匹配特性，領(lǐng)導人 U 一定也包含那條被提交當然日志震嫉，這里產(chǎn)生矛盾森瘪。
因此，假設不成立票堵，所有比 T 大的領(lǐng)導人一定包含了所有來自 T 的已經(jīng)被提交的日志扼睬。日志匹配原則保證了未來的領(lǐng)導人也同時會包含被間接提交的條目
跟隨者和候選人崩潰
跟隨者或者候選人崩潰，會按如下處理：
- 領(lǐng)導者會不斷給它發(fā)送選舉和追加日志的RPC悴势，直到成功
- 跟隨者會忽略它已經(jīng)處理過的追加日志的RPC
時間和可用性
領(lǐng)導人選舉是 Raft 中對時間要求最為關(guān)鍵的方面窗宇。Raft 可以選舉并維持一個穩(wěn)定的領(lǐng)導人,只要系統(tǒng)滿足下面的時間要求：
廣播時間（broadcastTime） << 選舉超時時間（electionTimeout） << 平均故障間隔時間（MTBF）
廣播時間指的是從一個服務器并行的發(fā)送 RPCs 給集群中的其他服務器并接收響應的平均時間滓玖；
選舉超時時間就是選舉的超時時間限制
平均故障間隔時間就是對于一臺服務器而言踪区，兩次故障之間的平均時間。
選舉超時時間要大于廣播時間的原因是褒傅，防止跟隨者因為還沒收到領(lǐng)導者的心跳捧存，而重新選主粪躬。
選舉超時時間要小于MTBF的原因是官硝，防止選舉時，能正常工作的server沒有達到大多數(shù)短蜕。
對于廣播時間氢架，一般在[0.5ms,20ms]之間，而平均故障間隔時間一般非常大朋魔，至少是按照月為單位岖研。因此，一般選舉超時時間一般選擇范圍為[10ms,500ms]警检。因此孙援，當領(lǐng)導者掛掉后，能在較短時間內(nèi)重新選主扇雕。
