1、raft協(xié)議是什么？

分布式系統(tǒng)之于單機系統(tǒng)，優(yōu)勢之一就是有更好的容錯性。

• 比如，一臺機器上的磁盤損壞，數(shù)據(jù)丟失，可以從另一臺機器上的磁盤恢復(fù)（分布式系統(tǒng)會對數(shù)據(jù)做備份）
• 比如，集群中某些機器宕機，整個集群還可以對外提供服務(wù)

這是如何做到的？比較容易的一個想法就是備份（backup）。一個系統(tǒng)的工作模是：接受客戶端的command，系統(tǒng)進行處理，將處理的結(jié)果返回給客戶端。由此可見，系統(tǒng)里的數(shù)據(jù)可能會因為command而變化。

實現(xiàn)備份的做法之一就是復(fù)制狀態(tài)機（Repilcated State Machine，RSM），它有一個很重要的性質(zhì)——確定性（deterministic）：

• 如果兩個相同的、確定性的狀態(tài)從同一狀態(tài)開始，并且以相同的順序獲得相同的輸入，那么這兩個狀態(tài)機將會生成相同的輸出，并且結(jié)束在相同的狀態(tài)

也就是說，如果我們能按順序?qū)ommand作用于狀態(tài)機，它就可以產(chǎn)生相同的狀態(tài)和相同的輸出

那么一個狀態(tài)機如何實現(xiàn)呢？如下圖所示（來自raft協(xié)議）：

image

上圖中，每個RSM都有一個replicated log，存儲的是來自客戶端的commands。每個RSM中replicate log中commads的順序都是相同的，狀態(tài)機按順序處理replicate log中的command,并將處理的結(jié)果返回給客戶端。由于狀態(tài)機具有確定性，因此每個狀態(tài)機的輸出和狀態(tài)都是相同的。

上圖中有一個模塊——Consensus Module剛剛沒有提及。這個模塊用于保證每個server上Log的一致性！

• 如果不做任何保障，直接將commad暴力寫入，一旦服務(wù)器宕機或者出現(xiàn)什么其他故障，就會導(dǎo)致這個Log丟失，并且無法恢復(fù)。而出現(xiàn)故障的可能性是很高的，這就導(dǎo)致系統(tǒng)不可用
• raft就是Consensus Module的一個實現(xiàn)

因此，raft是一致性協(xié)議，是用來保障servers上副本一致性的一種算法。

2、raft協(xié)議原理

下面將看論文時我認為的重要點進行記錄。

raft協(xié)議遵循的性質(zhì)

• Election Safty

  • 每一個任期內(nèi)只能有一個領(lǐng)導(dǎo)人

• Leader Append-Only

  • leader只能追加日志條目，不能重寫或者刪除日志條目

• Log Maching

  • 如果兩個日志條目的index和term都相同，則兩個如果日志中，兩個條目及它們之前的日志條目也完全相同

• Leader Completeness

  • 如果一條日志被commited過，那么大于該日志條目任期的日志都應(yīng)該包含這個點

• State Machine Safety

  • 如果一個server將某個特定index的日志條目交由狀態(tài)機處理了，那么對于其他server，交由狀態(tài)及處理的log中相同index的日志條目應(yīng)該相同

2.1 如何保證Election Safty

raft中，只要candidate獲得多數(shù)投票，就可以成為領(lǐng)導(dǎo)人。follower在投票的時候遵循兩個條件：

• 先到先得
• cadidate的term大于follower的term，或者兩個term相等，但cadidate的index大于follower的index

對于選舉結(jié)果：

• 如果票被瓜分，產(chǎn)生兩個leader，這次選舉失效，進行下一輪的選舉
• 只有一個leader的情況是被允許的

這里重要的一點是：如何保證在有限的時間內(nèi)確定出一個候選人，而不會總是出現(xiàn)票被瓜分的情況？raft使用了一個比較優(yōu)雅的實現(xiàn)方式，隨機選舉超時(randomize election timeouts)。這就使得每個server的timeout不一樣，發(fā)起新一輪選舉的時候，有些server還不是voter;或者一些符合條件的candidate還沒有參加下一輪。這種做法使得單個leader會很快被選舉出來。

2.2 如何保證Log Matching

Leader在進行AppendEntry RPCs的時候，這個消息中會攜帶preLogIndex和preLogTerm這兩個信息，follower收到消息的時候，首先判斷它最新日志條目的index和term是否和rpc中的一樣，如果一樣，才會append.

這就保證了新加日志和其前一條日志一定是一樣的。從第一條日志起就開始遵循這個原理，很自然地可以作出這樣的推斷。

2.3 如何保證Leader Completeness

這個在raft協(xié)議中是有完整證明的，這個證明比較簡短，用反正法，我在看的時候加了一些標注。

假設(shè)leaderU是第一個沒有包含leaderT中commitT點（T<U）

• 基于這個假設(shè)，一個事實是，開始選舉的時候，U中就不包含T中的commit點
• 由于leaderT有commitT點，說明在任期T內(nèi)，有大部分的follower都有commitT的點。這就說明，一定存在一個voter，它包含了commitT點，并且它投票給了leaderU
• 如果leaderU和這個voter有相同的term，那么leaderU的日志長度一定大于等于這個voter（否則會因為index小而被拒絕投票），那么leaderU肯定包含了voter的所有信息（這個是由Log Matching的屬性決定的，它們包含有相同的term，因此相同index的日志條目肯定相同),leaderU中肯定包含commit點，這與假設(shè)矛盾
• 如果leaderU和這個voter的term不同，那么leaderU的日志index一定大于等于voter的index。也就是說，為leaderU添加最后一條entry的那個leader因該已經(jīng)包含提交的日志（這是因為leaderU的leader的term>leaderU的term>voter的term，而leaderU是的一個不符合條件的任期，所以leaderU的leader應(yīng)該是符合條件的，肯定就包含了voter的commit點），即包含commit點，根據(jù)Log Maching的原則，leaderU里面一定包含了這一點，這與假設(shè)矛盾
• 因此，leader completeness是可以保證的

2.4 raft協(xié)議中有一個約定，不能提交之前任期內(nèi)log entry作為commit點。這是為什么？

這個問題主要是raft協(xié)議中commiting entries from previous term部分看的時候有點困惑，開始誤解成了這個約定是用來保證之前任期內(nèi)已經(jīng)被復(fù)制到大多數(shù)server卻沒有被提交的日志在新的仍期內(nèi)不會被覆蓋。

實際上，論文中的figrure8的過程是一個正確的過程。

image

在（c）中,index=2并沒有被提交，在(d)中被復(fù)制了是一個正確的做法。論文想闡述的是：如果在(c)中，leader提交了這個之前任期內(nèi)的entry，在(d)中依然會被覆蓋，也就是說被commit的entry覆蓋了，這是一個錯誤！因此約定“can not commit entries from previous term”

2.5 cluster membership changes

如果集群的配置發(fā)生了變化，例如，新加入幾臺server，掛掉幾臺server。這是會影響選舉的。

• 例如，如果新增了服務(wù)器，卻沒有更新原來server的配置，會導(dǎo)致leader election只有老機器在參與
• 又比如，如果直接將新的配置更新到leader這個方法是有問題的。如果leader沒有及時通知到所有的服務(wù)器，那么存在部分server是老配置，部分server是新配置，從而可能會產(chǎn)生兩個leader,如下圖的情況：

image

raft的解決方法就是two phase approch，引入一個過度配置，稱為共同一致狀態(tài)。具體的做法和圖示：

• leader收到更新配置請求的時候，產(chǎn)生一個（old,new）entry，并append進日志
• 通過rpc讓follower追加這條日志
• 如果順利，將這條日志commit
• 產(chǎn)生new entry, append到日志
• 通過rpc讓follower追加
• 如果順利commit，從而完成新配置的生成

image

　考慮上述過程：

• 1,2兩個階段，如果過程中出現(xiàn)問題，大多數(shù)情況old成為新的leader
  • 因為此時，擁有（old，new）entry的server并不是大多數(shù)
  • 如果說，已經(jīng)復(fù)制給大多數(shù)server，只是未提交，那么（old，new）是有可能被選為leader，不過這沒有什么太大的影響，因為新的leader在被選之后，會發(fā)送一條no-op的rpc，這個時候（old，new）就會被提交。重要的是，此時也僅有可能一個leader被選出，old不肯那個被選舉為leader.
• 3,4,5階段，大多數(shù)情況（old，new）成為leader，例外與上條類似
• 5階段就是new成為leader

2.6 log過長或日志回放時間過長怎么辦？

此時就需要做log compaction

raft采用的方法是寫時復(fù)制的snapshot(寫是復(fù)制在linux中可以通過fork來完成)

寫時復(fù)制主要是處于性能考慮的，如果state machine數(shù)據(jù)太多，snapshot將會耗費大量的時間，也許會導(dǎo)致系統(tǒng)可用性大大降低