在前一篇文章consul配置與實戰(zhàn)中木柬，介紹了consul的一些內(nèi)幕及consul配置相關(guān)，并對項目中的一些實際配置進行展示淹办。這篇文章重點介紹consul中所涉及到的一致性算法raft眉枕。
1. 背景
分布式系統(tǒng)的一致性是相當重要的，即為CAP理論中的C(Consistency)怜森。一致性又可以分為強一致性和最終一致性齐遵。這篇文章重點討論強一致性算法raft。
Lamport發(fā)表Paxos一致性算法從90年提出到現(xiàn)在已經(jīng)有二十幾年了塔插，直到2006年Google的三篇論文初現(xiàn)“云”的端倪梗摇，其中的Chubby Lock服務(wù)使用Paxos作為Chubby Cell中的一致性算法，Paxos的人氣從此一路狂飆想许。而Paxos流程太過于繁雜實現(xiàn)起來也比較復雜伶授，雖然現(xiàn)在很廣泛使用的Zookeeper也是基于Paxos算法來實現(xiàn)，但是Zookeeper使用的ZAB（Zookeeper Atomic Broadcast）協(xié)議對Paxos進行了很多的改進與優(yōu)化流纹，復雜性是制約他發(fā)展的一個重要原因糜烹。Raft的設(shè)計初衷就是易于理解性。
Raft是斯坦福的Diego Ongaro漱凝、John Ousterhout兩個人以易懂（Understandability）為目標設(shè)計的一致性算法疮蹦，在2013年發(fā)布了論文：《In Search of an Understandable Consensus Algorithm》
從2013年發(fā)布到現(xiàn)在不過只有兩年，到現(xiàn)在已經(jīng)有了十多種語言的Raft算法實現(xiàn)框架茸炒，較為出名的有etcd愕乎。
2. Raft詳解
強調(diào)的是易懂（Understandability）阵苇，Raft和Paxos一樣只要保證n/2+1節(jié)點正常就能夠提供服務(wù)；眾所周知但問題較為復雜時可以把問題分解為幾個小問題來處理感论，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铺浇，被動響應(yīng)請求RPC，從不主動發(fā)起請求RPC
- Candidate垛膝，由Follower向Leader轉(zhuǎn)換的中間狀態(tài)
在正常的操作流程中鳍侣，集群中有且只有一個server，其他所有的server都是follower吼拥。follower是被動的倚聚，他們只是被動地相應(yīng)Candidate和leader的請求。凿可。leader處理所有的客戶端請求惑折，follower自己不處理而是轉(zhuǎn)發(fā)給leader。第三種狀態(tài)是Candidate枯跑，用來選舉一個新的leader惨驶。
角色轉(zhuǎn)換 -
Terms
Raft將時間劃分成任意的長度周期。Terms可以理解為邏輯周期敛助，用連續(xù)的整數(shù)表示粗卜。在分布式環(huán)境中，時間同步很重要纳击，同時是一個難題续扔。在Raft中使用了一個可以理解為周期（任期）的概念，用Term作為一個周期焕数，每個Term都是一個連續(xù)遞增的編號纱昧，每一輪選舉都是一個Term周期，在一個Term中只能產(chǎn)生一個Leader堡赔。
每個term伴隨著一次election识脆，一個或多個Candidate試圖成為leader，如上圖的狀態(tài)轉(zhuǎn)換。如果某個Candidate贏得了這次election灼捂，它將升級為剩余server的leader离例。在某些election的情形中，會產(chǎn)生耗票（Split Votes）的結(jié)果 纵东，即投票結(jié)果無效粘招，隨后一次新的term開始啥寇。raft確保在某個term至多有一個leader偎球。
terms
如上圖所示，時間被劃分成多個terms辑甜，每個term隨著一次election衰絮。election完成后，一個leader節(jié)點管理整個集群磷醋，直至這個term結(jié)束猫牡。有些election失敗了，未能產(chǎn)生一個leader邓线。
2.2 Leader election
所有節(jié)點都是以follower啟動淌友。一個最小的 Raft 集群需要三個參與者，這樣才可能投出多數(shù)票骇陈。初始狀態(tài) 都是 Follower震庭，然后發(fā)起選舉這時有三種可能情形發(fā)生。如果每方都投給了自己你雌，結(jié)果沒有任何一方獲得多數(shù)票器联。之后每個參與方隨機休息一陣（Election Timeout）重新發(fā)起投票直到一方獲得多數(shù)票。這里的關(guān)鍵就是隨機 timeout婿崭，最先從timeout中恢復發(fā)起投票的一方向還在 timeout 中的另外兩方請求投票拨拓，這時它們就只能投給對方了，很快達成一致氓栈。
Raft的選舉由定時器來觸發(fā)渣磷，每個節(jié)點的選舉定時器時間都是不一樣的，開始時狀態(tài)都為Follower某個節(jié)點定時器觸發(fā)選舉后Term遞增授瘦，狀態(tài)由Follower轉(zhuǎn)為Candidate幸海，向其他節(jié)點發(fā)起RequestVote RPC請求，這時候有三種可能的情況發(fā)生：
1.該RequestVote請求接收到n/2+1（過半數(shù)）個節(jié)點的投票奥务，從Candidate轉(zhuǎn)為Leader物独，向其他節(jié)點發(fā)送heartBeat以保持Leader的正常運轉(zhuǎn)。
2.在此期間如果收到其他節(jié)點發(fā)送過來的AppendEntries RPC請求氯葬，如該節(jié)點的Term大則當前節(jié)點轉(zhuǎn)為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選舉出來后便開始負責客戶端的請求浇垦，所有事務(wù)（更新操作）請求都必須先經(jīng)過Leader處理炕置，這些事務(wù)請求或說成命令也就是這里說的日志，我們都知道要保證節(jié)點的一致性就要保證每個節(jié)點都按順序執(zhí)行相同的操作序列男韧，日志復制（Log Replication）就是為了保證執(zhí)行相同的操作序列所做的工作朴摊；在Raft中當接收到客戶端的日志（事務(wù)請求）后先把該日志追加到本地的Log中，然后通過heartbeat把該Entry同步給其他Follower此虑，F(xiàn)ollower接收到日志后記錄日志然后向Leader發(fā)送ACK甚纲，當Leader收到大多數(shù)（n/2+1）Follower的ACK信息后將該日志設(shè)置為已提交并追加到本地磁盤中，通知客戶端并在下個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积锅，假設(shè)某個Term同時選舉產(chǎn)生兩個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權(quán)威至高無上谅猾，當Follower和Leader產(chǎn)生分歧的時候，永遠是Leader去覆蓋修正Follower鳍悠。 - Log Matching
如果兩個節(jié)點上的日志項擁有相同的Index和Term税娜，那么這兩個節(jié)點[0, Index]范圍內(nèi)的Log完全一致。 - State Machine Safety
一旦某個server將某個日志項應(yīng)用于本地狀態(tài)機藏研，以后所有server對于該偏移都將應(yīng)用相同日志項敬矩。
3. 總結(jié)
本文主要講解了Raft算法的基本概念，以及算法中涉及到的leader選舉蠢挡，日志同步弧岳，安全性。Raft是以易理解性作為其設(shè)計的一個目標业踏，對于一個學習的新手來說禽炬，確實比Paxos易于理解很多。雖然 Raft 的論文比 Paxos 簡單版論文容易讀勤家，論文依然有很多地方需要深刻體會與理解腹尖，筆者也還是搞了好幾天。
