raft算法浅析
raft算法可分解成六部分：
選舉leader：包括檢測崩潰和選舉新的leader
復制log
leader發生變化時的安全性、可用性和一致性
中立舊leader
客戶端交互
修改配置：增加或刪除server
raft算法定義了term（任期）的概念。一個term可分為兩個階段：選舉和復制日志。選舉階段用于選出一個leader，且僅有一個leader；leader選舉出來以后，就可以開始復制日志了。當然，選舉階段可能出現分裂投票的情況，即多個candidate都持有不足半數的投票，沒有一個candidate的票數過半，大家互不相讓，導致選舉超時，這時直接進入下一輪term，重新開始選舉。
term默認值為0，然后單調遞增。term的主要作用是用于識別出過時信息。比如網絡分區時，某一分區的server的term滯后，分區恢復后就能根據term值識別出過期的server，過期的server也可以根據收到的較大的term更新自己的term。
raft算法中，在一個term中，一個server只能是以下三種狀態之一：
leader：負責與客戶端交互，復制日志
follower：只能接收leader的rpc并作出響應
candidate：選舉期間server的狀態
狀態轉換圖如下：
server啟動時，處于follower狀態；由于收不到leader的心跳包，超時轉入candidate狀態。
candidate狀態下，可能會因為收到多數server的投票轉入leader狀態；或者因為收到了新leader的心跳包而轉入follower狀態，也可能因為發現了更大的term而轉入follower狀態；或者是因為上述幾種情況均未發生而一直等待至超時，導致進入下一輪term，重新轉入candidate狀態。
leader狀態下，如果發現了更大的term，就會退位，轉入follower狀態。
上述提到了“發現了更大的term”這種情況，這種情況主要是在系統出現網絡分區一段時間后恢復正常時可能出現。
一、選舉過程（系統啟動時的選舉可以和leader崩潰時的選舉統一起來）
各follower將term加1，進入新一輪term；然后所有的follower隨機等待一段時間（一般取T~2T，T一般取150ms）后轉入candidate狀態，發起投票（即發送RequestVote RPC），同時開始計時一個election timeout時間；
如果在election timeout超時之前沒收到新leader的心跳包或者沒收到多數投票，則回到步驟1；
否則，根據情況轉入follower狀態或者leader狀態，開始復制log；如果是follower狀態，則監聽leader的心跳包，如果心跳包超時，則回到步驟1。
步驟1中要求隨機等待一段時間再發起投票是為了防止上文提到的多個candidate同時發起投票導致出現分裂投票的情況。
二、復制log
log結構：log entry由index、term和command組成。
leader收到客戶端的命令后，封裝成一個log entry，append到本地log中，然后向所有的follower發送AppendEntries RPC。當收到多數follower的響應時，leader認為該log entry已提交，然后可以在本地狀態機上執行該命令，并返回結果給客戶端，同時通知各個follower該log entry已提交，follower收到該通知后就可以將命令送入狀態機執行。
從上述描述可以總結出一點，log entry已提交就是指該log entry在大多數server上都有了備份，且大多數server知曉這一點。
對于那些還沒向leader發送響應的follower，leader會不斷向它們發送AppendEntries RPC，直到它們成功響應。
log一致性特性：
如果兩個server上的log entry有相同的index和term，則
該index中存的命令一定相同；
小于該index的所有log entry 一定相同。
如果某一個log entry已被提交，則該log entry之前的所有log entry（index更小的log entry）均已被提交。
下面解釋一下為什么raft算法中的log具有這兩個特性。
第一，leader每次復制日志時，會進行AppendEntries RPC調用，該調用包含了這樣幾個參數：
prevLogIndex：leader的本地log中最新的log entry之前的log entry（因為leader是將客戶端命令封裝成log entry并append到本地log之后才開始復制日志的，所以才會說“之前”）的index
prevLogTerm：leader的本地log中最新的log entry之前的log entry的term
entries[]：將要復制到follower的log entries，可以不止一條
當leader接收了客戶端發起的一個新的命令，并將命令封裝成log entry寫入了本地log后，他需要將該log entry復制到所有的follower上，這時follower不僅僅是簡單地將log entry寫入到本地log即可，還需要在寫入之前檢查所有已有的log entry是否與leader中的一致。follower將prevLogIndex和prevLogTerm這兩個參數與自己本地最新的log entry的index和term進行對比，如果相同，可以認為自己的本地log與leader是一致的，然后就可以將新的log entry append到本地log中；如果對比發現不相同，則拒絕append，并返回false。
上述提到的這種檢查其實是一種遞歸檢查。這一次檢查發現prevLogIndex和prevLogTerm與本地最新的log entry的index和term是匹配的，說明上一次檢查時相應的prevLogIndex和prevLogTerm也是匹配的，一直遞歸到log為空，append第一條log entry時，prevLogIndex和prevLogTerm都為0，也是匹配的。所以每次檢查時如果prevLogIndex和prevLogTerm與本地最新的log entry匹配，則之前的所有的log entry也是一致的。
那么follower在檢查完之后，如果本地最新的log entry是一致的，則本次將log entry append到本地log中之后，整個log與leader上的log仍然是一致的。
此時已經證明了第一條特性。在說明過程中提到的AppendEntries RPC的參數以及follower的一致性檢查是不完整的，只是摘取了與第一條特性相關的點。
第二條特性不知道怎么解釋，可以簡單理解為log entry是按順序提交的嗎？暫且當結論記住吧(￣ェ￣;)
三、leader發生變化
leader發生變化時必須保證安全性，即：
如果當前term的leader判斷一條log entry已提交，當leader發生變化時，新的leader的log中必須有該log entry。
raft保證安全性的做法是candidate在發起RequestVote RPC時攜帶其最后一條log entry的index和term，收到rpc的server要進行如下判斷：
如果結果為true，則拒絕給該candidate投票。
等價于：
如果選民的term比candidate的還大，直接拒絕投票；
如果選民的term跟candidate的一樣大，就再看log的長度，如果選民的log更長，直接拒絕投票；如果選民的log不比candidate更長，則投票；
如果選民的term比candidate的小，則直接投票。
這種方法能夠保證在如下情況下的安全性：
term2的leader s1將log entry(index=4, term=2)復制到s3上后完成該log entry的提交，然后s1崩潰，s4和s5不可能當選為leader。
但是無法保證在如下情況下的安全性：
term4的leader s1將log entry(index=4, term=2)復制到s3上后完成該log entry的提交，然后s1崩潰。根據判決條件，s5是可能當選為leader的。s5一旦當選，將會把自己的log復制到其他server上，這樣log entry(index=4, term=2)將被覆蓋，即出現了已提交的log entry在leader改變后消失的情況。
針對這種情況，raft對commit規則作出了改進。
leader上的一條老term的log entry需滿足如下兩個條件才能被認為已提交：
必須在大多數server有備份
至少要有一條當前term的log entry在大多數server上有備份
根據官方視頻的示例，貌似對于當前term中創建的log entry，只要在大多數server上備份了就算是已提交了。
在下圖的情形中，根據commit的新定義，log entry(index=4, term=2)就不是已提交狀態，leader s1也就不會將該命令傳入狀態機。那么，即使s5當選為新term的leader之后，覆蓋掉s1、s2和s3上的log entry(index=4, term=2)也無所謂了。
如果滿足了commit的新定義，如下圖所示，則log entry(index=4, term=2)就是已提交的，于是也就可以放心地將該log entry傳入狀態機執行了。s5不可能當選為leader，leader只可能在s1、s2和s3中產生，所以log entry(index=4, term=2)不會被新的leader覆蓋掉。
總的來說，新的commit規則和選舉規則保證了舊leader上已提交的log entry不會被新的leader覆蓋掉。
很自然地，下面就要介紹新leader如何使所有follower上的log與新leader一致。
新leader出現后，與leader上的log相比，follower上的log中未提交的部分可能出現log entry缺失，也可能有多余的log entry。
“缺失”很好理解，就是指follower的log比leader的短。
“多余”包括兩種情況：
follower的log比leader長的部分
follower的log中與leader中不同的部分
下圖的示例中：
先看第一種情況，（c）、（d）和（f）中index>10的entry都是多余的entry。
再看第二種情況，（e）中index=6,7的entry都是多余的entry；（f）中4<=index<=10的entry都是多余的entry。
leader為每個follower維護一個nextIndex變量。為某個follower維護的nextIndex表示leader要發送給該follower的下一個entry的index。nextIndex初始化為leader的最后一個entry的index加1。
leader根據nextIndex設置好AppendEntries RPC的參數prevLogIndex和prevLogTerm，然后發送給follower。如果follower的響應為false，則將nextIndex減一，然后重復上述操作。
當follower收到leader的AppendEntries RPC后，會進行一致性檢查。如果一致性檢查通過，則將AppendEntries RPC中的entries復制到自己的log中；否則返回false。
四、中立舊leader
當出現網絡分區時，可能會有新的leader出現，當分區恢復時，如何處理兩個leader呢？
raft使用term識別舊的leader。
對于任何一個RPC，如果發送方的term小于接收方的term，則接收方拒絕該RPC，發送方收到拒絕后轉為follower，并更新自己的term。
如果發送方的term大于接收方的term，則接收方轉為follower，并更新自己的term，正常處理RPC請求。
五、客戶端協議
如果客戶端不知道哪個server是leader，則將命令發送到任何一個server上。接收到該命令的server如果不是server，則返回leader信息，讓客戶端重定向到leader。
leader收到客戶端的命令后，必須等待命令被提交，然后將命令注入狀態機執行，最后才將執行結果返回給客戶端。
如果客戶端的請求超時無響應，則客戶端會重發該命令到其他server上，最終重定向到新的leader。
如果leader執行了客戶端的命令后，還沒來得及將結果返回給客戶端就崩潰了，那么客戶端會因為超時而重發該命令，這樣可能導致同一個命令執行了兩次。如何避免這種情況呢？
如果leader接收了客戶端的命令后，提交了該entry，還未將命令注入狀態機執行就崩潰了，也可能導致該命令被新的leader提交，最終也還是會執行兩次。
raft的做法是在客戶端發送命令時攜帶一個唯一的id，leader收到該命令后首先檢查本地log中是否已有該id，若有，則直接返回對應命令的結果；否則正常操作。
六、修改配置：增加或刪除server
當配置發生變化時，由于網絡問題，不能保證新配置在所有的server上同時生效。比如某集群由3臺集群擴展成5臺機器，新配置可能只在2臺新機器和1臺舊機器上生效，有2臺舊機器仍然在使用舊配置。2臺舊機器認為目前集群中只有3臺機器，因此它們倆就構成了大多數，也就可以選舉出一個leader。同時，3臺使用新配置的機器認為目前集群中有5臺機器，它們仨就構成了大多數，也可以選舉出一個leader。此時集群中就出現了2個leader。
raft規避這種情況的方法是采用聯合共識（joint consensus）。在從舊配置過渡到新配置的過程中，增加一個新舊配置同時生效的階段。具體做法如下圖所示：
當leader收到客戶端更改配置的命令時，將新舊配置封裝到一個log entry（記為Cold+new）中，存入本地log；同時立刻讓新配置生效，此時leader中同時存在舊配置和新配置，兩者都有效。然后將Cold+new廣播給其它server。
follower，也就是其它server，收到Cold+new后，一旦決定將該entry寫入本地log，則使新配置立即生效，不用等到leader通知已提交后才生效。
leader如果確認Cold+new已被提交，則集群進入joint consensus階段。在此階段，不管是選舉還是提交命令，必須得到舊配置有效的機器中的大多數的確認，同時也必須得到新配置有效的機器中的大多數的確認。
當leader確認Cold+new已被提交后，就可以開始將新配置廣播到其它server上了。一旦新配置提交成功，則集群就可以使用新配置了。
本文圖片截自油管官方視頻中的PPT《Raft: A Consensus Algorithm for Replicated Logs》。
歡迎關注博主個人微信公眾號~~~
總結
- 上一篇： 图书分类系统-总述
- 下一篇： freemarker截取字符串subSt