1.raft協(xié)議
raft協(xié)議是一個共識算法，主要包括leader election，log replication，safety三個關鍵部分，另外還包括membership changes和snapshot。
1.1 復制狀態(tài)機
復制狀態(tài)機是分布式系統(tǒng)中解決fault tolerance問題的常用手段。raft通過log replication來保證集群的多個server，會有同樣的數(shù)據(jù)輸入到各自的狀態(tài)機。如圖1所示。
關鍵術語：
Apply：將entry輸入到狀態(tài)機
committed：entry可以被安全的Apply到狀態(tài)機，一般情況下entry被同步到集群的大多數(shù)節(jié)點上時，就可以認為是committed（有特殊情況）。
每個server都有一個log，log中包含一系列的entry（entry中有相應的命令，即客戶端請求），狀態(tài)機按照log中的順序執(zhí)行這些命令。
如果每個server輸入狀態(tài)機的數(shù)據(jù)相同，狀態(tài)機產(chǎn)生的結果也是相同的。因此共識算法的目的就是保證多個server的log一致。
leader上的consensus module接收到客戶端的命令，將這些命令作為entry添加到log中，并且和其他follower上的consensus module通信，將log entry同步到其他follower，以確保多個server之間日志文件的最終一致。
當達到一定條件，即該條entry committed時，leader會將命令輸入狀態(tài)機，并將輸出返回給客戶端，同時通過心跳通知其他follower可以Apply該entry。
共識算法有以下特點：
1.safety，在所有非拜占庭條件下（包括網(wǎng)絡延遲，分區(qū)，丟包，duplication，reordering等），不會返回錯誤的結果
2.大部分節(jié)點正常話，系統(tǒng)就可以正常工作
3.不依靠物理時鐘來確保日志的一致，錯誤的物理時鐘和消息延遲最多會造成可用性問題
4.集群中的大多數(shù)節(jié)點在一輪rpc調(diào)用中正常響應的話，一個客戶端的請求就會被正常返回，不會受部分慢節(jié)點的影響
1.2 基本概念
任何時刻，一個server處于以下三個狀態(tài)之一：leader，follower，candidate。
一般情況下，有1個leader，其他節(jié)點都是follower，follower是被動的，不會發(fā)送請求，只會響應leader和candidate的請求。
leader處理所有客戶端的請求（如果客戶端請求了follower，follower將請求重定向到leader）。
candidate狀態(tài)用于選舉一個新的leader，狀態(tài)轉(zhuǎn)換如下圖
raft將物理時間分隔為一個個的任意長度的term，term是連續(xù)的。
每個term從election開始，一個或者多個candidate嘗試競選為leader，如果一個candidate贏得了選舉，就會成為term的余下時間內(nèi)的leader。
一些情況下，會產(chǎn)生split vote，term會以沒有l(wèi)eader的狀態(tài)結束，開始新一輪的term以及選舉
raft確保一個term中最多只會有一個leader。
term是邏輯時鐘，每個server存儲一個current term number，current term number隨著時間單調(diào)遞增，當節(jié)點之間通信時，會交換current term number，
如果一個server發(fā)現(xiàn)自己的current term number小于其他節(jié)點的，該server會將自己的term更新為更大的term，
如果一個candidate或者leader發(fā)現(xiàn)有節(jié)點的term大于自己的term，就會轉(zhuǎn)變?yōu)閒ollower（有特殊情況），
如果一個節(jié)點接收到一個有著過期term number的請求，則會拒絕這個請求。
1.3. RPC
raft的server之間使用RPC通信，主要為兩種類型的RPC，
RequestVote RPC：用于candidate選舉
AppendEntries RPC：用于leader發(fā)送log entry給follower，或者心跳
另外還有一種InstallSnapshot RPC，用于傳輸snapshot
2. leader election
raft協(xié)議首先需要選舉一個唯一的leader，leader接受客戶端的命令，將這些命令復制到其他follower，通知follower什么時候可以將這些日志輸入到狀態(tài)機。data flow是單向的，從leader到follower。
raft使用心跳機制觸發(fā)leader election，當一個server start up，起始狀態(tài)是follower，只要收到leader和candidate的正確RPC請求，server就會保持follower的狀態(tài)。
如果follower在一定時間內(nèi)（election timeout）沒有收到心跳，follower會認為當前沒有l(wèi)eader，并開始競選。
開始競選時，follower增加自己的current term并將狀態(tài)轉(zhuǎn)換為candidate，然后會選舉自己并發(fā)送RequestVote RPC請求給集群中的其他server。
一個candidate會保持自己的狀態(tài)直到下面三種情況之一發(fā)生：
1.贏得選舉
一個candidate在接收到集群中大多數(shù)節(jié)點對當前term的投票之后，贏得選舉。每個server在一個term中，最多只會給一個candidate投票，first-come-first-served，
2.其他節(jié)點成為leader
如果candidate收到其他節(jié)點的RPC請求，而且請求中的term大于等于candidate的current term，candidate會認為已經(jīng)選出leader，并返回到follower狀態(tài)。
如果RPC請求中的term小于candidate的current term，candidate會拒絕該RPC請求。
3.一定時間內(nèi)（election timeout）沒有選舉出leader
每個candidate都會time out，并且增加自己的term，開始新一輪的選舉
election timeout是在一個固定范圍內(nèi)（例如150ms-300ms內(nèi)）隨機的
上述機制保證在一個term中，只有一個candidate會成為leader，當一個candidate成為leader，它會發(fā)送心跳信息給所有其他的節(jié)點。
3. log replication
當一個leader被選舉出來之后，client發(fā)送請求給leader，leader將將請求作為一個新的entry添加到log中，然后并行的發(fā)送AppendEntries RPC請求（攜帶該entry）給follower。
leader判斷當前是否可以安全地將entry apply到狀態(tài)機中，此時該entry被叫做committed。然后leader將請求Apply到狀態(tài)機，并返回執(zhí)行結果。
log entry中會保存接受到entry時的term，以及一個用于標記log entry位置的index。
raft保證committed entries是持久化的，并最終會被所有的狀態(tài)機執(zhí)行。
當一個entry被leader replicate到集群中的大多數(shù)節(jié)點上時，該entry就是committed。
如果某條entry是committed的，該entry之前的entry也都是committed的，包括之前的leader創(chuàng)建的entry。
leader會記錄committed的日志的最高index，并將該index包含在之后的AppendEntries RPC中（包括 heartbeats），
follower知道某個entry是committed，就會將該entry apply到狀態(tài)機中。
AppendEntries Consistency Check:
當發(fā)送一個AppendEntries RPC，leader將新entries之前最近的log entry的index和term包含在RPC請求中。如果follower發(fā)現(xiàn)自己的log中沒有該index和term的entry，就會拒絕新的entries。
類似于一個歸納的過程，最初的空的log滿足Log Matching Property，當有新的log entry時，consistency check同樣保證了新的log entry滿足Log Matching Property。
這樣，當AppendEntries請求返回成功的響應時，leader就知道follower的log在new entries之前的部分和自己的log一樣。
一個新的leader被選舉出來之后，follower的log可能和新的leader不一樣，follower可能有l(wèi)eader沒有的entry，也可能有老的leader沒有commit的entry。
為了讓follower的log和leader的完全一致，leader需要找到follower的log和自己的log分叉的地方，刪除follower在分叉點之后的log entry，然后leader向follower發(fā)送自己在分叉點之后的log entry。
上述操作通過AppendEntries RPC來實現(xiàn)，leader會記錄每個follower的nextIndex，即leader應該發(fā)送給這個follower的下一個log entry的index。
如果follower的log和leader的不一樣，AppendEntries RPC會失敗，leader減小nextIndex并重試。
如果需要，這個協(xié)議也可以優(yōu)化，如果AppendEntries RPC失敗，follower可以返回沖突的term，以及該term的第一個index。這樣原來一個不同的entry就需要一個AppendEntries請求，現(xiàn)在一個term需要一個AppendEntries請求。
這樣多個節(jié)點之間的日志就會收斂一致。同時，leader從不會覆蓋或者刪除自己的log entry，符合Leader Append-Only Property。
4.safety
election safety：一個term中最多只有一個leader
leader append-only：leader不會覆蓋或者刪除log中的entry，只會append新的entry到log中
log matching：如果2個log包含一個相同term和相同index的entry，那2個日志中在該index之前的entry都是相同的。
leader completeness：如果一個entry在某個term中committed，那么這個entry會出現(xiàn)在所有具有更高term的leader的log中
state machine safety：如果一個server apply了一個index為n的entry，其他server不會apply一個不同的entry，且這個entry的index也為n
上述部分并不能完全保證每個狀態(tài)機以相同的順序執(zhí)行相同的命令。
例如，一個follower可能在當前l(fā)eader commit一些log entry的時候不可用，然后該follower被選舉為新的leader后，就可能覆蓋之前committed的日志，從而造成不同的狀態(tài)機執(zhí)行了不同的命令。
下面討論leader election的限制，這些限制能保證任何term的leader都會包含之前term中committed的log entry。
4.1 選舉限制
RequestVote RPC請求包含candidate的log，如果voter的log比candidate的log更加up-to-date，voter會拒絕這次投票。
up-to-date：兩個log，如果term不同，term更大的更新，如果term相同，日志更長的更新
4.2 commit之前term的log entry
一個leader不能立即判斷出一個之前term的entry是否應該committed，即使該entry被存儲到了大多數(shù)節(jié)點上。
（a）S1是leader，寫入一條命令，index是2
（b）S1 crash，S5選舉為leader，寫入一條命令，index是3
（c）S5 crash，S1選舉為leader，寫入一條命令，index是4，并將index為2的log entry同步到S3，commit和apply index為2的log entry
（d）S1 crash，S5選舉為leader，會覆蓋掉index2，造成多個server的狀態(tài)機apply不一樣的log entry
因此，raft不會因為之前term的log entry被存儲到了大多數(shù)節(jié)點上，就將該entry commit（raft never commits log entries from pervious terms by counting replicas），只有當前term的log entry被存儲到大多數(shù)節(jié)點上時，才會判斷該entry為commit
（only log entries from the leader's current term are committed by counting replicas）。這樣，由于Log Matching Property，所有之前的entries都會間接地被commit掉。
5. Membership change
raft使用two-phase的方案來處理configuration change，集群首先會切換到一個名叫joint consensus的中間狀態(tài)，一旦joint consensus被committed了，集群就會使用新的configuration。
joint consensus將老的和新的configuration結合在一起：
log entries會被同步到兩個configuration的server中
兩個configuration的server都可以被選舉為leader
agreement（election或者entry commitment）分別需要兩個configuration的大多數(shù)節(jié)點同意
集群configuration也是以log entry的方式存儲和同步到其他server上。
當leader接收到configuration從C-old變?yōu)镃-new的請求之后，將C-old,new的entry存儲到log中，并同步到其他server上。
follower接收到entry后，無論該entry是否已經(jīng)committed，都會使用entry包含的configuration替換當前的configuration。
如果leader crash，新的leader的configuration只可能是C-old或者C-old,new。
C-old,new被committed之后，leader創(chuàng)建一條C-new的entry，并同步到其他server上。
follower接收到該entry之后，無論該entry是否已經(jīng)committed，都會使用C-new替換之前的configuration。
當C-new被committed之后，C-old中的節(jié)點就可以被shut down。
上述方案需要解決三個問題：
1.新加入的server需要很長時間才能追上leader，在這段時間內(nèi)無法committed，為此raft引入了non-voting 成員
2.老的leader可能不在新的configuration中。為此，leader在C-new committed之后，leader需要變成follower
3.removed servers可能會影響集群。這些節(jié)點不會接收到心跳，然后time out，然后開始新一輪的選舉。這會造成當前的leader變成follower，然后重新選舉leader。上述過程會不斷重復。
為此，server需要忽略RequestVote RPC，如果當前的leader沒有time out。
6.Log compaction
snapshotting是log compacting的最簡單的辦法，狀態(tài)機將當前系統(tǒng)狀態(tài)被寫進snapshot，之前的log entry會被刪除。
每個server會獨立的take snapshot，snapshot會包含log中已經(jīng)committed的log entry。
snapshot中會包含少量的元數(shù)據(jù)，
last included index：狀態(tài)機apply的最后一個log entry，也就是snapshot替換掉的最后一個log entry 的index。
last included term：上述entry的term
元數(shù)據(jù)用于snapshot之后的第一個log entry的AppendEntries consistency check，由于該entry需要之前的log的index和term。
元數(shù)據(jù)也包含最近的configuration。
對于一個剛加進集群的server，leader使用InstallSnapshot RPC發(fā)送snapshot給follower。
7. Client interaction
raft需要把所有的請求發(fā)送給leader，當一個client start，client連接集群中的任意一個節(jié)點，如果該節(jié)點不是leader，則會拒絕client的請求，并返回leader的信息（AppendEntries請求包含了leader的網(wǎng)絡地址）。
如果leader crash，client請求會timeout，然后隨機選擇一個節(jié)點繼續(xù)重試。
raft協(xié)議需要實現(xiàn)線性語義（linearizable semantics），每個操作會且只會執(zhí)行一次（exactly once），但是僅靠之前提到的幾點，raft協(xié)議的可能會讓一個命令執(zhí)行多次。
7.1
例如，leader在commit一個log entry，但是還沒有來得及返回給client之后，就crash掉，client會在新的leader上重復發(fā)送相同的請求，造成該請求執(zhí)行兩次。
解決方法是client給每個命令一個序列號，狀態(tài)機記錄每個client最近執(zhí)行的序列號。如果狀態(tài)機收到一個命令，該命令的序列號是之前執(zhí)行過的，就立即返回而不再執(zhí)行該命令。
7.2
只讀操作可能會讀到過期的數(shù)據(jù)。因為client訪問一個leader時，集群中選舉出了其他leader，該leader馬上就會變成follower。linear semantics不能返回過期數(shù)據(jù)。
raft的解決方案分兩步，
首先，一個leader必須確認哪些entry是committed，Leader Completeness Property保證一個leader擁有所有committed的entry，但是在term的開始階段，leader并不知道哪些是已經(jīng)committed的。因此，leader需要在term的開始，先commit一個no-op entry。
然后，leader必須檢查當前是否有其他leader被選舉出來，將要取代自己的leader位置。raft在返回read-only請求的響應之前，需要和集群中的大多數(shù)節(jié)點發(fā)送心跳。
