在前一篇文章consul配置與實戰(zhàn)中，介紹了consul的一些內幕及consul配置相關，并對項目中的一些實際配置進行展示。這篇文章重點介紹consul中所涉及到的一致性算法raft。
1. 背景
分布式系統(tǒng)的一致性是相當重要的，即為CAP理論中的C(Consistency)。一致性又可以分為強一致性和最終一致性。這篇文章重點討論強一致性算法raft。
Lamport發(fā)表Paxos一致性算法從90年提出到現(xiàn)在已經(jīng)有二十幾年了，直到2006年Google的三篇論文初現(xiàn)“云”的端倪，其中的Chubby Lock服務使用Paxos作為Chubby Cell中的一致性算法，Paxos的人氣從此一路狂飆。而Paxos流程太過于繁雜實現(xiàn)起來也比較復雜，雖然現(xiàn)在很廣泛使用的Zookeeper也是基于Paxos算法來實現(xiàn)，但是Zookeeper使用的ZAB（Zookeeper Atomic Broadcast）協(xié)議對Paxos進行了很多的改進與優(yōu)化，復雜性是制約他發(fā)展的一個重要原因。Raft的設計初衷就是易于理解性。
Raft是斯坦福的Diego Ongaro、John Ousterhout兩個人以易懂（Understandability）為目標設計的一致性算法，在2013年發(fā)布了論文：《In Search of an Understandable Consensus Algorithm》
從2013年發(fā)布到現(xiàn)在不過只有兩年，到現(xiàn)在已經(jīng)有了十多種語言的Raft算法實現(xiàn)框架，較為出名的有etcd。
2. Raft詳解
強調的是易懂（Understandability），Raft和Paxos一樣只要保證n/2+1節(jié)點正常就能夠提供服務；眾所周知但問題較為復雜時可以把問題分解為幾個小問題來處理，Raft也使用了分而治之的思想把算法流程分為三個子問題：選舉（Leader election）、日志復制（Log replication）、安全性（Safety）三個子問題。
2.1 raft基本概念
-
states
一個raft集群擁有多個server，通常會有5臺，這樣可以允許系統(tǒng)中兩臺server宕機。在任何情況下，所有的server只有如下三種狀態(tài)之一：- Leader，負責Client交互和log復制，同一時刻系統(tǒng)中最多存在1個
- Follower，被動響應請求RPC，從不主動發(fā)起請求RPC
- Candidate，由Follower向Leader轉換的中間狀態(tài)
在正常的操作流程中，集群中有且只有一個server，其他所有的server都是follower。follower是被動的，他們只是被動地相應Candidate和leader的請求。。leader處理所有的客戶端請求，follower自己不處理而是轉發(fā)給leader。第三種狀態(tài)是Candidate，用來選舉一個新的leader。
角色轉換 -
Terms
Raft將時間劃分成任意的長度周期。Terms可以理解為邏輯周期，用連續(xù)的整數(shù)表示。在分布式環(huán)境中，時間同步很重要，同時是一個難題。在Raft中使用了一個可以理解為周期（任期）的概念，用Term作為一個周期，每個Term都是一個連續(xù)遞增的編號，每一輪選舉都是一個Term周期，在一個Term中只能產生一個Leader。
每個term伴隨著一次election，一個或多個Candidate試圖成為leader，如上圖的狀態(tài)轉換。如果某個Candidate贏得了這次election，它將升級為剩余server的leader。在某些election的情形中，會產生耗票（Split Votes）的結果 ，即投票結果無效，隨后一次新的term開始。raft確保在某個term至多有一個leader。
terms
如上圖所示，時間被劃分成多個terms，每個term隨著一次election。election完成后，一個leader節(jié)點管理整個集群，直至這個term結束。有些election失敗了，未能產生一個leader。
2.2 Leader election
所有節(jié)點都是以follower啟動。一個最小的 Raft 集群需要三個參與者，這樣才可能投出多數(shù)票。初始狀態(tài) 都是 Follower，然后發(fā)起選舉這時有三種可能情形發(fā)生。如果每方都投給了自己，結果沒有任何一方獲得多數(shù)票。之后每個參與方隨機休息一陣（Election Timeout）重新發(fā)起投票直到一方獲得多數(shù)票。這里的關鍵就是隨機 timeout，最先從timeout中恢復發(fā)起投票的一方向還在 timeout 中的另外兩方請求投票，這時它們就只能投給對方了，很快達成一致。
Raft的選舉由定時器來觸發(fā)，每個節(jié)點的選舉定時器時間都是不一樣的，開始時狀態(tài)都為Follower某個節(jié)點定時器觸發(fā)選舉后Term遞增，狀態(tài)由Follower轉為Candidate，向其他節(jié)點發(fā)起RequestVote RPC請求，這時候有三種可能的情況發(fā)生：
1.該RequestVote請求接收到n/2+1（過半數(shù)）個節(jié)點的投票，從Candidate轉為Leader，向其他節(jié)點發(fā)送heartBeat以保持Leader的正常運轉。
2.在此期間如果收到其他節(jié)點發(fā)送過來的AppendEntries RPC請求，如該節(jié)點的Term大則當前節(jié)點轉為Follower，否則保持Candidate拒絕該請求。
3.Election timeout發(fā)生則Term遞增，重新發(fā)起選舉。
在一個Term期間每個節(jié)點只能投票一次，所以當有多個Candidate存在時就會出現(xiàn)每個Candidate發(fā)起的選舉都存在接收到的投票數(shù)都不過半的問題，這時每個Candidate都將Term遞增、重啟定時器并重新發(fā)起選舉，由于每個節(jié)點中定時器的時間都是隨機的，所以就不會多次存在有多個Candidate同時發(fā)起投票的問題。
引用一張網(wǎng)上的圖片，比較形象，如下圖。
2.3 Log replication
日志復制主要是用于保證節(jié)點的一致性，這階段所做的操作也是為了保證一致性與高可用性；當Leader選舉出來后便開始負責客戶端的請求，所有事務（更新操作）請求都必須先經(jīng)過Leader處理，這些事務請求或說成命令也就是這里說的日志，我們都知道要保證節(jié)點的一致性就要保證每個節(jié)點都按順序執(zhí)行相同的操作序列，日志復制（Log Replication）就是為了保證執(zhí)行相同的操作序列所做的工作；在Raft中當接收到客戶端的日志（事務請求）后先把該日志追加到本地的Log中，然后通過heartbeat把該Entry同步給其他Follower，F(xiàn)ollower接收到日志后記錄日志然后向Leader發(fā)送ACK，當Leader收到大多數(shù)（n/2+1）Follower的ACK信息后將該日志設置為已提交并追加到本地磁盤中，通知客戶端并在下個heartbeat中Leader將通知所有的Follower將該日志存儲在自己的本地磁盤中。
上圖中，當leader選出來之后，follower的logs場景很可能出現(xiàn)在上圖中。follower有可能丟失entries、有未提交的entries、有額外的entries等等場景。Raft中，leader通過強制followers復制自己的logs來處理不一致。這意味著，在follower中l(wèi)ogs沖突的entries將會被leader logs中的覆寫。
2.4 Safety
安全性是用于保證每個節(jié)點都執(zhí)行相同序列的安全機制，如當某個Follower在當前Leader commit Log時變得不可用了，稍后可能該Follower又會倍選舉為Leader，這時新Leader可能會用新的Log覆蓋先前已committed的Log，這就是導致節(jié)點執(zhí)行不同序列；Safety就是用于保證選舉出來的Leader一定包含先前 commited Log的機制；
- Election Safety
每個Term只能選舉出一個Leader，假設某個Term同時選舉產生兩個LeaderA和LeaderB，根據(jù)選舉過程定義，A和B必須同時獲得超過半數(shù)節(jié)點的投票，至少存在節(jié)點N同時給予A和B投票，因此矛盾。 - Leader Completeness
這里所說的完整性是指Leader日志的完整性，當Log在Term1被Commit后，那么以后Term2、Term3…等的Leader必須包含該Log；Raft在選舉階段就使用Term的判斷用于保證完整性：當請求投票的該Candidate的Term較大或Term相同Index更大則投票，否則拒絕該請求； - Leader Append-Only
Leader從不“重寫”或者“刪除”本地Log，僅僅“追加”本地Log。Raft算法中Leader權威至高無上，當Follower和Leader產生分歧的時候，永遠是Leader去覆蓋修正Follower。 - Log Matching
如果兩個節(jié)點上的日志項擁有相同的Index和Term，那么這兩個節(jié)點[0, Index]范圍內的Log完全一致。 - State Machine Safety
一旦某個server將某個日志項應用于本地狀態(tài)機，以后所有server對于該偏移都將應用相同日志項。
3. 總結
本文主要講解了Raft算法的基本概念，以及算法中涉及到的leader選舉，日志同步，安全性。Raft是以易理解性作為其設計的一個目標，對于一個學習的新手來說，確實比Paxos易于理解很多。雖然 Raft 的論文比 Paxos 簡單版論文容易讀，論文依然有很多地方需要深刻體會與理解，筆者也還是搞了好幾天。
