深度分析Raft的主要特點

Quorum與Paxos，Raft等一致性協議有什麼區別，這個問題的答案本身很簡單：一致性協議大多使用了Quorum機制，但僅僅有Quorum(R+W>N)機制是保證不了一致性的。本文計劃延伸這個問題，以Raft為例回答一個完善的一致性協議擁有包括Quorum在內的那些機制，試著說明這些機制的完備以及其中每一項的不可或缺。

要回答這個問題首先需要說明Raft是做什麼的，Paxos、Raft被稱為一致性協議，顧名思義它們要解決的是多節點的一致性問題，需要注意的是這裡所說的一致性並不是要求所有節點在任何時刻狀態完全一致。而是要保證：

即使發生網路分割槽或機器節點異常，整個叢集依然能夠像單機一樣提供一致的服務，即在每次操作時都可以看到其之前的所有成功操作按順序完成。

這裡有兩點需要說明：

1. 強調在網路分割槽或節點異常時，是因為如果不考慮這種異常狀況，一致性是非常容易保證的，單節點即可。而一致性協議所要做的就是在容忍異常的情況下保證一致。

2. 這裡的一致是對叢集外部使用者而言的，將整個叢集看做一個整體。

將每一個對Raft叢集的操作稱為一個提案，希望Raft叢集對外遮蔽內部的網路或節點異常，依次對每一個提案作出相應，提交成功的提案可以在後續操作中持續可見。這裡的提案需要是冪等的，即重複執行不會導致叢集狀態不同。

接下來我們就看Raft是如何實現這種一致性保證的。Raft將一致性問題拆分為三個子問題，各個擊破，從而使得其實現簡單易懂。本文將首先簡單介紹其三個子問題的內容以及達成方式；之後證明三個子問題是實現一致性的充分條件；最後嘗試說明這三個子問題的保證缺一不可。

1. Leader Election

組成一個Raft叢集至少需要三臺機器，而Raft限制每一時刻最多隻能有一個節點可以發起提案，這個限制極大的簡化了一致性的實現，這個可以發起提案的節點稱為Leader。因此所要解決的第一個問題便是：

如何保證任何時候最多隻有一個Leader節點
以及當Leader節點異常時如何儘快的選擇出新的Leader節點。 

如上圖所示：

• 所有的節點以Follower的角色啟動；

• Leader週期性給其他節點傳送心跳；

• 在超時時間內沒有收到心跳包的Follower變成Candidate，將自己的Term加一，並廣播Vote請求，發起新一輪選舉；

• 選舉結束：

• 收到大多數節點的投票，變成Leader，並向其他節點傳送自己Term的AppendEntry。在一個Term裡，同一個Server只會給出一次投票，先到先得；

• 收到相同或更大Term的AppendEntry，承認對方為Leader，變成Follower；

• 超時，重新開始新的選舉，透過隨機的超時時間來減少這種情況得發生。

2. Log Replication

從上面對Raft狀態轉換的討論中可以看到，任何非Leader的節點都有可能在未來成為Leader，為了能保證後續Leader節點變化後依然能夠使得整個叢集對外保持一致，需要透過Log Replication機制來解決如下兩個問題：

• Follower以與Leader節點相同的順序依次執行每個成功提案;

• 每個成功提交的提案必須有足夠多的成功副本，來保證後續的訪問一致

上圖描述了一個Raft提案的執行過程：

• Leader收到Client的請求，寫入本地Log，之後並行地向所有Follower透過AppendEntry請求傳送該Log Entry；

• Follower對收到的Entry進行驗證，包括驗證其之前的一條Log Entry項是不是和Leader相同，驗證成功後寫入本地Log並返回Leader成功；

• Leader收到超過半數的Follower答覆成功後，將當前Log Commit（如寫入狀態機），之後返回客戶端成功；

• 後續的AppendEntry及HeartBeat都會攜帶主的Commit位置，Follower會提交該位置之前的所有Log Entry。

Follower在接受AppendEntry時會檢查其前一條的Log是否與Leader相同，利用數學歸納法可以很簡單的證明Leader和Follower上的Log一致。另外，由於只需要過半數的節點成功即可返回，也就在保證一致性的前提下竟可能的提高了叢集的可用性。

W > N/2 & R > N/2 => W + R > N

這裡需要注意，Leader Commit過的提案會向使用者返回成功，因此Raft叢集需要保證這些提案永遠存在。

3. Safety

透過上述的兩個子問題已經解決了大部分的難題，除了下面兩個細節：

1. Leader Crash後，新的節點成為Leader，為了不讓資料丟失，我們希望新Leader包含所有已經Commit的Entry。為了避免資料從Follower到Leader的反向流動帶來的複雜性，Raft限制新Leader一定是當前Log最新的節點，即其擁有最多最大term的Log Entry。

2. 通常對Log的Commit方式都是Leader統計成功AppendEntry的節點是否過半數。在節點頻發Crash的場景下只有舊Leader Commit的Log Entry可能會被後續的Leader用不同的Log Entry覆蓋，從而導致資料丟失。造成這種錯誤的根本原因是Leader在Commit後突然Crash，擁有這條Entry的節點此時可能並不能佔到大多數。這種情況在論文中有詳細的介紹。Raft很巧妙的限制Leader只能對自己本Term的提案採用統計大多數的方式Commit，而舊Term的提案則利用“Commit的Log之前的所有Log都順序Commit”的機制來提交。

透過上述的三個子問題的解決，我們得到了一個完善的一致性演算法，論文中給出了詳細嚴謹的證明，其首先假設Commit過的提案會在後續丟失，之後推匯出矛盾進而反證成功，這裡不再贅述。該證明的關鍵點在於：Leader Election中要求新Leader獲得超過半數的節點投票，Log Replication中每個Commit都有超過半數的節點同意，因此這兩個大多數中至少存在一個公共節點，這個節點既同意了某個提案的Commit又投票給了新的Leader。

上面討論了三個子問題對一致性的充分性，接下來要討論的是在Raft的框架下，任何一個子問題的缺失都會導致嚴重的不一致後果：

• Leader Election缺失，假設某一時刻有兩個節點作為Leader同時接受使用者請求，發起提案。整個叢集便無法確定這兩個提案的前後關係，從而導致衝突。Dynamo雖然使用了Quorum的寫入策略卻依然需要透過vector clock甚至交給使用者來處理衝突。

• Log Replication缺失，假設提案的提交不能保證R + W > N，也就是讀寫兩次提交涉及的節點之間可能沒有交集。顯而易見的會導致成功提交的請求在後續訪問中不可見

• Safety缺失，假設新Leader不能保證擁有最長的Log，其可能並沒有最新的Commit資料，從而導致之前成功的提交不可見；

透過上面的討論，可以看出一個完整的一致性協議做了包括Quorum在內的諸多努力。Raft劃分了三個子問題來使得整個一致性演算法的實現簡單易懂，我們也基於Raft實現了自己的一致性庫Floyd來滿足諸如Zeppelin元資訊叢集及Pika跨機房功能中對一致性的需求。

來源：區塊鏈大師 微訊號 DACMaster