Raft和Paxos在分散式存儲系統中的應用差異
本文的目的：
最新在看Group Replication(簡稱GR)的代碼，從Codeship的Galera到MariaDB Galera Cluster/Percona XtrDB Cluster的多主集群技術，再到如今的GR; 分散式存儲系統，尤其是分散式的RDBMS必然是未來的趨勢。其中最本質和最難的一個問題就是一致性問題，一致性問題已經是如今分散式系統必須要面臨的問題。從原子廣播到Viewstamped Replication/Paxos/Raft… 查閱了很多分散式一致性的理論paper和工程技術，把覺得不錯的資料翻譯總結一下。
基本概念：
log: 代表對存儲系統的一次操作記錄，比如一條redolog日誌或者binlog
message: 分散式系統中各個Server交互的單元
term: 一個任期的編號，就如美國總統的柯林頓、小布希等不同任職區間
index: 在一個term內的序號，通常是連續遞增的
slot: log序列中每一個log entry的全局位點
其實一致性演算法的核心思想非常簡單，可以這麼簡單(接地氣)地理解:
1. 一群人(集群中的Server)對某個問題吵得不可開交，相持沒有一個統一結論；
2. 過了很久... 大家都累了，意識到需要一位德高望重的領袖(Leader)，聽取Leader的意見；
3. 於是不同陣營推舉一位局部可以服眾的侯選人(Leader Candidate)；
4. 給候選人5分鐘拉票時間(timeout)，然後讓其他人投票(Election)，我們姑且認為選舉是公平公正的；
5. 最後選舉出Leader了，雖然還是有些人不服，反正少數服從多數(多數派)；
6. 以後的事情，都由Leader來提建議，大多數人同意後就張榜公布，一旦公布的結論就不能更改了(不能幹打臉的事情)；大家也就沒什麼異議了(少數人不服也只有忍~);
7. Leader當久了，難免有點權錢交易啊，這個時候可能被反腐了(Leader不可用); 可生活還得繼續不是，需要重新選舉一位Leader，這就重複前面的歷史了...; 當然也有些Leader不是因為權錢交易掛的，有被和諧的，有被揭竿而起的... 反正就是下課了，總進不了世界盃領導壓力大換個洋教頭也行啊！
8. 哪能啊，上一屆領導的爛賬，腫么辦？一個叫Raft的青年說：「先把屁股擦乾淨，否則老子不接這個爛攤子，我要有隊伍的絕對控制權！」 於是Raft正式上任前，就帶一幫人把舊賬本理清楚了，也公示了，然後走馬上任開啟了屬於自己的時代！
9. 當官都是肥差，像年輕的Raft青年這樣NB哄哄，有的時候也沒人鳥他...於是還是有些迫不及待的老油條，先佔住Leader的坑，至於前任的爛帳本，上任後的三把火來燒唄！沒錯，這老司機就是Paxos...
10. 貌似這Paxos兄弟江湖口碑一般啊？唉，自古套路留人心，這些老司機有很多法寶，分分鐘教你做人。所以，外面很多門(學)派(術)都在研究Paxos。
1. 背景
一致性是提供容錯服務的關鍵部分，例如分散式強一致存儲系統，非阻塞的原子廣播、Paxos和Raft是三種常見的一致性演算法。Paxos被學術界廣泛地研究，Raft則在工程師層面非常受歡迎。
儘管學術界對Paxos情有獨鍾，但Raft卻非常流行。工程師可以通過閱讀幾篇論文就可以理解Raft演算法，然後實現Raft演算法去解決一些實際的工程問題。演算法實現的過程中要考慮通訊交互的次數，消息的數量和資源的佔用率等等，綜合權衡這些因素的同時還要保證有較好的系統性能。同時，演算法的實現還要考慮演算法理論和工程實踐之間經常會遇到的一些問題。
為了克服這些障礙，Diego Ongaro和John Ousterhout發表了一種叫做Raft的新一致性演算法，其設計的初衷是更易於理解、以及比Paxos更好的工程化實現等。儘管Raft演算法給複雜的分散式系統帶來了耳目一新的感覺，但其中大部分思想和Paxos演算法的本質是相同的。例如，都會選擇一個唯一的Leader來負責參與者能否就某個問題達成一致。
在這邊文章中，我們將簡要地介紹Paxos和Raft之間的異同。首先我們會討論什麼是一致性演算法；然後我們會介紹如何實例化一個一致性演算法來構建一個數據複製方案；最後我們介紹Leader是如何選舉的，以及一致性演算法的安全性和活性。
請記住，本文的目的不是深入討論Paxos和Raft演算法(Paxos演算法的某些部分至今未理解透)，而僅僅是對兩者的一個概要介紹。如果需要深入了解這兩個演算法的細節，請閱讀參考論文1/2/3/4.
2. 分散式一致性
2.1 分散式系統的特徵
安全性和活性是分散式系統具有的兩個基本特性，因為安全性和活性是系統正確性的充分必要條件。安全性表示推導過程是正確的，即便有意外情況存在，這種意外也絕對不會發生，最終都會得到一個正確的結果。活性表示最終會得到一個結果，不會因為某種相持而讓系統無法繼續推演至得到結果(在有限的時間內得到一個結果)。從定義上可以這麼理解：
安全性
只有被提議的值才可能被選定(不會選定一個未被提議的值)
只會選定唯一的一個值
在一個值真正被選定之前，不會被其它Server學習到
活性
最終一定有某些被提議的值被選定
一個被選定的值，最終一定會被其它Server學習到
2.2 決議的達成
在一致性演算法中，目標是在多個Server之間就某個問題達成一致，活性體現為最終多個Server一定會就某個問題達成一致，不會一直僵持無果；安全性體現為不會有兩個Server包含不同決議。
不幸的是，一個Server可能比其它Server執行得慢、可能Crash、可能停止處理一致性演算法邏輯。消息可能延遲，亂序或者丟失。所有的這些因素導致實現一個一致性演算法是非常複雜的，也很難保證在穩定的時間內得出正確的決議。雖然我們不能確切地知道一個分散式系統在哪個時刻達到」穩定」狀態，但我們知道最終它一定會達到一個「穩定」狀態。
一次決議達成包含兩次通訊:
leader–(1)–>servers–(2)–>leader:
Leader發送一個想要達成一致性的提案給所有參與者，每一個收到這個提案的參與者回復一個ACK給Leader,表示他們已經接受這個提案。在Leader接收到多數派的ACK後，大家對這個提案就達成一致了。
值得注意的是，我們在上面的分析中忽略了兩條消息：第一條是從發起者到Leader之間(發送希望達成一致的意向)，第二條是Leader發送給所有的參與者，通知針對某個提案已經達成一致。第二條消息可以通過下面兩種方式避免：
一個Server可以把已經Accept的消息發送給其他所有Server
Leader可以在下一次發送其他提案時附帶已經達成一致的消息編號
2.3 日誌複製
為了實現複製，一般會啟動多個一致性演算法的實例，每一個實例對應複製日誌中的一個log entry，複製日誌通常被持久化到磁碟上。Leader可以並行多個一致性演算法的實例來針對不同的log entry達成一致，通過這種方式可以提升性能。但是，並行的程度取決於硬體，網路和應用程序本身。
每一個Leader只對自己所在的任期負責，當Leader發生改變的時候，其對應的任期編號也隨之遞增:
2.4 Leader選舉
無論Paxos演算法還是Raft演算法，最終都會產生一個Leader，所有其他正常的Server信任Leader來協調一致性的達成，一個任期內只有一個Leader.如果當前任期的Leader不可用，會觸發選舉一個新的Leader，新Leader的任期編號將大於當前任期編號(Term).
在Raft中，一個Server(Leader候選)發送一個「選舉請求」給其他Server，期望在正式成為Leader之前得到多數派Server的響應。如果沒有收到多數派Server的響應或者被告知已經有其他Server成為Leader，當前Server會在timeout後開啟一次新的選舉流程。在一個term內，任何Server只能為一個Leader候選投票。
Paxos沒有明確定義Leader是如何產生的。為了簡單起見，一般都使用基於等級的優先順序，比如依據Server的ID(一個整數)。因此，在所有正常的伺服器中，總是擁有最高等級或者最低等級的伺服器變成Leader. 儘管這是一種簡單直觀的方案，也需要在兩個任期之間劃分間隔：
新任期 = 舊任期 + N(集群中的伺服器數目)
Raft對選舉流程加了一些限制：只有最新的Server才能被選舉為Leader。基本上，這種機制保證了Leader擁有所有在上一個任期內達成一致的日誌，Leader不需要從全局達成一致的日誌中去學習那些它自身沒有的日誌。因此當一個Server成為Leader後，它可以立即對外服務，比如向其他Server發起一致性提案。
和Raft不同，Paxos允許任何Server被選舉為Leader. 因此在Paxos中當一個Server成為Leader後，它需要首先向其它Server學習舊任期內已經達成一致的日誌，然後才能對外提供服務。可以很明顯地看出，這種靈活性帶來了額外的複雜度。
如上圖所示，在Raft中只有Server1和Server2可以被選舉為Leader. 在Paxos中，所有Server都可以被選舉為Leader.
2.5 安全性
源於分散式系統的非同步特性，某個Server可能不時地故障並隨時觸發新一輪的選舉。這意味著整個集群中的Server可能在某個時刻臨時處於不同的任期(Term)內，但是他們最終都進入到相同的任期。
任何時候，如果一個Server收到一個來至舊任期內的消息，這意味著發送者要麼是Leader，要麼是舊任期內試圖成為Leader的一個Server.這種情況下，接收端Server必須拒絕這個消息並通知發送端Server.
如果一個Server接收到一個任期編號大於其當前任期，這意味著已經有一個新Leader產生，接收端必須開始接收新Leader的「提案」.
值得注意的是，兩種演算法都需要嚴格地避免覆蓋舊Leader已經達成一致的決議，因為這是明顯不安全的。這是Raft和Paxos的核心差異之一，這一點上我們可以看到Raft演算法的相對簡單和直接。
正如前面提到過的一樣，Raft在Leader選舉的時候做出了一些限制，只有擁有最新一致決議的Server才能被選舉為Leader:
Raft對比不同Server中最後一條log記錄的Index和Term來決定是否擁有最新的決議。如果兩條log的Term不相同，則Term較大者勝出。如果兩條log的Term相同，則Index較大者勝出。
Leader只需要保證已經複製的log最終都會被收集到，它通過加入下面的限制來實現這一點：對於一個特定的slot， 當其尚未對index為」n-1」的提案達成一致之前，不會接受index為」n」的提案。
Leader會在當前log中包含上一個log的Term編號，接收端Server只會接收和上一個log匹配的log請求(同一個Term內Index編號連續)。否則，它會要求Leader發送自己尚不存在的log，以此類推「n-2」和「n-3」等等。
在Paxos中，任何一個Server都可能成為Leader，因此避免一個已經達成的決議被覆蓋的任務相對複雜一些。新Leader首先必須找出其它Server都已經處理了哪些決議，然後再開始對外提供服務。
在Paxos演算法中，當一個新Leader被選舉出來後，有一個「準備」階段必須執行。「準備」消息包含新的任期編號Term和slot編號「n」，「n」代表前面已經達成一致的決議序號。其他Server回復大於slot編號「n」的信息，這些信息被用於限制新Leader可以對這些slot提議的值。
2.6 活性
只要集群中Server多數派存活，就可以保證集群可以正常服務(選舉和一致性達成流程都可以正常進行)[9].正如前面提到的活性定義，因為Raft和Paxos實際都會有一個Leader來對某一個提案負責，不會出現僵持無果的問題。
3. 結論
通過上面的分析我們了解了Raft和Paxos之間的異同，關鍵的不同之處在於Leader的選舉和安全性的保證。Raft只允許擁有最新數據的Server變成Leader，而Paxos沒有這個限制。這是Paxos的靈活性，當然這個靈活性也帶來了額外的複雜度。
值得注意的是無論在Raft還是在Paxos中，Leade都很容易成為系統的瓶頸，因為所有的請求都會經過Leader。在有Leader的集群中，消息處理的時間複雜度為O(N)，而在無Leader的集群中，消息處理的時間複雜度為O(1).
已經有一些基於Paxos的協議支持多個Leader，比如：Mencius；另外還有一些基於Paxos的有序無衝突並行協議，例如：Egalitarian Paxos 和Generalized Paxos. 希望能夠看到基於Raft協議的這種優化！
參考資料：
01 – Paxos made simple
02 – In Search of an Understandable Consensus Algorithm
03 – Desconstructing Paxos
04 – Yet Another Visit to Paxos
05 – Consensus in the presence of partial synchrony
06 – Failure Detection and Consensus in the Crash-Recovery Model
07 – Tuning paxos for high-throughput with batching and pipelining
08 – Introduction to Reliable and Secure Distributed Programming
09 – Lower Bounds for Asynchronous Consensus
10 – Mencius: Building Efficient Replicated State Machines for WANs
11 – There Is More Consensus in Egalitarian Parliaments
12 – Generalized Consensus and Paxos
TAG:中國存儲 |