本文的目的：

最新在看Group Replication(簡稱GR)的代碼，從Codeship的Galera到MariaDB Galera Cluster/Percona XtrDB Cluster的多主集群技術(shù)，再到如今的GR; 分布式存儲系統(tǒng)，尤其是分布式的RDBMS必然是未來的趨勢。其中最本質(zhì)和最難的一個問題就是一致性問題，一致性問題已經(jīng)是如今分布式系統(tǒng)必須要面臨的問題。從原子廣播到Viewstamped Replication/Paxos/Raft… 查閱了很多分布式一致性的理論paper和工程技術(shù)，把覺得不錯的資料翻譯總結(jié)一下。

[[232150]]

基本概念：

log: 代表對存儲系統(tǒng)的一次操作記錄，比如一條redolog日志或者binlog

message: 分布式系統(tǒng)中各個Server交互的單元

term: 一個任期的編號，就如美國總統(tǒng)的克林頓、小布什等不同任職區(qū)間

index: 在一個term內(nèi)的序號，通常是連續(xù)遞增的

slot: log序列中每一個log entry的全局位點(diǎn)

其實一致性算法的核心思想非常簡單，可以這么簡單(接地氣)地理解:

1. 一群人(集群中的Server)對某個問題吵得不可開交，相持沒有一個統(tǒng)一結(jié)論；

2. 過了很久... 大家都累了，意識到需要一位德高望重的領(lǐng)袖(Leader)，聽取Leader的意見；

3. 于是不同陣營推舉一位局部可以服眾的侯選人(Leader Candidate)；

4. 給候選人5分鐘拉票時間(timeout)，然后讓其他人投票(Election)，我們姑且認(rèn)為選舉是公平公正的；

5. 最后選舉出Leader了，雖然還是有些人不服，反正少數(shù)服從多數(shù)(多數(shù)派)；

6. 以后的事情，都由Leader來提建議，大多數(shù)人同意后就張榜公布，一旦公布的結(jié)論就不能更改了(不能干打臉的事情)；大家也就沒什么異議了(少數(shù)人不服也只有忍~);

7. Leader當(dāng)久了，難免有點(diǎn)權(quán)錢交易啊，這個時候可能被反腐了(Leader不可用); 可生活還得繼續(xù)不是，需要重新選舉一位Leader，這就重復(fù)前面的歷史了...; 當(dāng)然也有些Leader不是因為權(quán)錢交易掛的，有被和諧的，有被揭竿而起的... 反正就是下課了，總進(jìn)不了世界杯領(lǐng)導(dǎo)壓力大換個洋教頭也行?。?/p>

8. 哪能啊，上一屆領(lǐng)導(dǎo)的爛賬，腫么辦？一個叫Raft的青年說：“先把屁股擦干凈，否則老子不接這個爛攤子，我要有隊伍的絕對控制權(quán)！” 于是Raft正式上任前，就帶一幫人把舊賬本理清楚了，也公示了，然后走馬上任開啟了屬于自己的時代！

9. 當(dāng)官都是肥差，像年輕的Raft青年這樣NB哄哄，有的時候也沒人鳥他...于是還是有些迫不及待的老油條，先占住Leader的坑，至于前任的爛帳本，上任后的三把火來燒唄！沒錯，這老司機(jī)就是Paxos...

10. 貌似這Paxos兄弟江湖口碑一般?。堪?，自古套路留人心，這些老司機(jī)有很多法寶，分分鐘教你做人。所以，外面很多門(學(xué))派(術(shù))都在研究Paxos。

1. 背景

一致性是提供容錯服務(wù)的關(guān)鍵部分，例如分布式強(qiáng)一致存儲系統(tǒng)，非阻塞的原子廣播、Paxos和Raft是三種常見的一致性算法。Paxos被學(xué)術(shù)界廣泛地研究，Raft則在工程師層面非常受歡迎。

盡管學(xué)術(shù)界對Paxos情有獨(dú)鐘，但Raft卻非常流行。工程師可以通過閱讀幾篇論文就可以理解Raft算法，然后實現(xiàn)Raft算法去解決一些實際的工程問題。算法實現(xiàn)的過程中要考慮通訊交互的次數(shù)，消息的數(shù)量和資源的占用率等等，綜合權(quán)衡這些因素的同時還要保證有較好的系統(tǒng)性能。同時，算法的實現(xiàn)還要考慮算法理論和工程實踐之間經(jīng)常會遇到的一些問題。

為了克服這些障礙，Diego Ongaro和John Ousterhout發(fā)表了一種叫做Raft的新一致性算法，其設(shè)計的初衷是更易于理解、以及比Paxos更好的工程化實現(xiàn)等。盡管Raft算法給復(fù)雜的分布式系統(tǒng)帶來了耳目一新的感覺，但其中大部分思想和Paxos算法的本質(zhì)是相同的。例如，都會選擇一個唯一的Leader來負(fù)責(zé)參與者能否就某個問題達(dá)成一致。

在這邊文章中，我們將簡要地介紹Paxos和Raft之間的異同。首先我們會討論什么是一致性算法；然后我們會介紹如何實例化一個一致性算法來構(gòu)建一個數(shù)據(jù)復(fù)制方案；最后我們介紹Leader是如何選舉的，以及一致性算法的安全性和活性。

請記住，本文的目的不是深入討論P(yáng)axos和Raft算法(Paxos算法的某些部分至今未理解透)，而僅僅是對兩者的一個概要介紹。如果需要深入了解這兩個算法的細(xì)節(jié)，請閱讀參考論文1/2/3/4.

2. 分布式一致性

2.1 分布式系統(tǒng)的特征

安全性和活性是分布式系統(tǒng)具有的兩個基本特性，因為安全性和活性是系統(tǒng)正確性的充分必要條件。安全性表示推導(dǎo)過程是正確的，即便有意外情況存在，這種意外也絕對不會發(fā)生，最終都會得到一個正確的結(jié)果?；钚员硎咀罱K會得到一個結(jié)果，不會因為某種相持而讓系統(tǒng)無法繼續(xù)推演至得到結(jié)果(在有限的時間內(nèi)得到一個結(jié)果)。從定義上可以這么理解：

安全性

• 只有被提議的值才可能被選定(不會選定一個未被提議的值)
• 只會選定唯一的一個值
• 在一個值真正被選定之前，不會被其它Server學(xué)習(xí)到

活性

• 最終一定有某些被提議的值被選定
• 一個被選定的值，最終一定會被其它Server學(xué)習(xí)到

2.2 決議的達(dá)成

 在一致性算法中，目標(biāo)是在多個Server之間就某個問題達(dá)成一致，活性體現(xiàn)為最終多個Server一定會就某個問題達(dá)成一致，不會一直僵持無果；安全性體現(xiàn)為不會有兩個Server包含不同決議。

不幸的是，一個Server可能比其它Server執(zhí)行得慢、可能Crash、可能停止處理一致性算法邏輯。消息可能延遲，亂序或者丟失。所有的這些因素導(dǎo)致實現(xiàn)一個一致性算法是非常復(fù)雜的，也很難保證在穩(wěn)定的時間內(nèi)得出正確的決議。雖然我們不能確切地知道一個分布式系統(tǒng)在哪個時刻達(dá)到”穩(wěn)定”狀態(tài)，但我們知道最終它一定會達(dá)到一個“穩(wěn)定”狀態(tài)。

一次決議達(dá)成包含兩次通訊:

leader –(1)–> servers –(2)–> leader: 

 Leader發(fā)送一個想要達(dá)成一致性的提案給所有參與者，每一個收到這個提案的參與者回復(fù)一個ACK給Leader,表示他們已經(jīng)接受這個提案。在Leader接收到多數(shù)派的ACK后，大家對這個提案就達(dá)成一致了。

值得注意的是，我們在上面的分析中忽略了兩條消息：第一條是從發(fā)起者到Leader之間(發(fā)送希望達(dá)成一致的意向)，第二條是Leader發(fā)送給所有的參與者，通知針對某個提案已經(jīng)達(dá)成一致。第二條消息可以通過下面兩種方式避免：

一個Server可以把已經(jīng)Accept的消息發(fā)送給其他所有Server

Leader可以在下一次發(fā)送其他提案時附帶已經(jīng)達(dá)成一致的消息編號

2.3 日志復(fù)制

為了實現(xiàn)復(fù)制，一般會啟動多個一致性算法的實例，每一個實例對應(yīng)復(fù)制日志中的一個log entry，復(fù)制日志通常被持久化到磁盤上。Leader可以并行多個一致性算法的實例來針對不同的log entry達(dá)成一致，通過這種方式可以提升性能。但是，并行的程度取決于硬件，網(wǎng)絡(luò)和應(yīng)用程序本身。

每一個Leader只對自己所在的任期負(fù)責(zé)，當(dāng)Leader發(fā)生改變的時候，其對應(yīng)的任期編號也隨之遞增:

2.4 Leader選舉

無論P(yáng)axos算法還是Raft算法，最終都會產(chǎn)生一個Leader，所有其他正常的Server信任Leader來協(xié)調(diào)一致性的達(dá)成，一個任期內(nèi)只有一個Leader.如果當(dāng)前任期的Leader不可用，會觸發(fā)選舉一個新的Leader，新Leader的任期編號將大于當(dāng)前任期編號(Term).

在Raft中，一個Server(Leader候選)發(fā)送一個“選舉請求”給其他Server，期望在正式成為Leader之前得到多數(shù)派Server的響應(yīng)。如果沒有收到多數(shù)派Server的響應(yīng)或者被告知已經(jīng)有其他Server成為Leader，當(dāng)前Server會在timeout后開啟一次新的選舉流程。在一個term內(nèi)，任何Server只能為一個Leader候選投票。

Paxos沒有明確定義Leader是如何產(chǎn)生的。為了簡單起見，一般都使用基于等級的優(yōu)先級，比如依據(jù)Server的ID(一個整數(shù))。因此，在所有正常的服務(wù)器中，總是擁有最高等級或者最低等級的服務(wù)器變成Leader. 盡管這是一種簡單直觀的方案，也需要在兩個任期之間劃分間隔：

新任期 = 舊任期 + N(集群中的服務(wù)器數(shù)目)

Raft對選舉流程加了一些限制：只有最新的Server才能被選舉為Leader?；旧希@種機(jī)制保證了Leader擁有所有在上一個任期內(nèi)達(dá)成一致的日志，Leader不需要從全局達(dá)成一致的日志中去學(xué)習(xí)那些它自身沒有的日志。因此當(dāng)一個Server成為Leader后，它可以立即對外服務(wù)，比如向其他Server發(fā)起一致性提案。

和Raft不同，Paxos允許任何Server被選舉為Leader. 因此在Paxos中當(dāng)一個Server成為Leader后，它需要首先向其它Server學(xué)習(xí)舊任期內(nèi)已經(jīng)達(dá)成一致的日志，然后才能對外提供服務(wù)?？梢院苊黠@地看出，這種靈活性帶來了額外的復(fù)雜度。

如上圖所示，在Raft中只有Server1和Server2可以被選舉為Leader. 在Paxos中，所有Server都可以被選舉為Leader.

2.5 安全性

源于分布式系統(tǒng)的異步特性，某個Server可能不時地故障并隨時觸發(fā)新一輪的選舉。這意味著整個集群中的Server可能在某個時刻臨時處于不同的任期(Term)內(nèi)，但是他們最終都進(jìn)入到相同的任期。

任何時候，如果一個Server收到一個來至舊任期內(nèi)的消息，這意味著發(fā)送者要么是Leader，要么是舊任期內(nèi)試圖成為Leader的一個Server.這種情況下，接收端Server必須拒絕這個消息并通知發(fā)送端Server.

 如果一個Server接收到一個任期編號大于其當(dāng)前任期，這意味著已經(jīng)有一個新Leader產(chǎn)生，接收端必須開始接收新Leader的“提案”.

值得注意的是，兩種算法都需要嚴(yán)格地避免覆蓋舊Leader已經(jīng)達(dá)成一致的決議，因為這是明顯不安全的。這是Raft和Paxos的核心差異之一，這一點(diǎn)上我們可以看到Raft算法的相對簡單和直接。

正如前面提到過的一樣，Raft在Leader選舉的時候做出了一些限制，只有擁有最新一致決議的Server才能被選舉為Leader:

Raft對比不同Server中最后一條log記錄的Index和Term來決定是否擁有最新的決議。如果兩條log的Term不相同，則Term較大者勝出。如果兩條log的Term相同，則Index較大者勝出。

Leader只需要保證已經(jīng)復(fù)制的log最終都會被收集到，它通過加入下面的限制來實現(xiàn)這一點(diǎn)：對于一個特定的slot， 當(dāng)其尚未對index為”n-1”的提案達(dá)成一致之前，不會接受index為”n”的提案。

Leader會在當(dāng)前l(fā)og中包含上一個log的Term編號，接收端Server只會接收和上一個log匹配的log請求(同一個Term內(nèi)Index編號連續(xù))。否則，它會要求Leader發(fā)送自己尚不存在的log，以此類推“n-2”和“n-3”等等。

在Paxos中，任何一個Server都可能成為Leader，因此避免一個已經(jīng)達(dá)成的決議被覆蓋的任務(wù)相對復(fù)雜一些。新Leader首先必須找出其它Server都已經(jīng)處理了哪些決議，然后再開始對外提供服務(wù)。

在Paxos算法中，當(dāng)一個新Leader被選舉出來后，有一個“準(zhǔn)備”階段必須執(zhí)行。“準(zhǔn)備”消息包含新的任期編號Term和slot編號“n”，“n”代表前面已經(jīng)達(dá)成一致的決議序號。其他Server回復(fù)大于slot編號“n”的信息，這些信息被用于限制新Leader可以對這些slot提議的值。

2.6 活性

只要集群中Server多數(shù)派存活，就可以保證集群可以正常服務(wù)(選舉和一致性達(dá)成流程都可以正常進(jìn)行)[9].正如前面提到的活性定義，因為Raft和Paxos實際都會有一個Leader來對某一個提案負(fù)責(zé)，不會出現(xiàn)僵持無果的問題。

3. 結(jié)論

通過上面的分析我們了解了Raft和Paxos之間的異同，關(guān)鍵的不同之處在于Leader的選舉和安全性的保證。Raft只允許擁有最新數(shù)據(jù)的Server變成Leader，而Paxos沒有這個限制。這是Paxos的靈活性，當(dāng)然這個靈活性也帶來了額外的復(fù)雜度。

值得注意的是無論在Raft還是在Paxos中，Leade都很容易成為系統(tǒng)的瓶頸，因為所有的請求都會經(jīng)過Leader。在有Leader的集群中，消息處理的時間復(fù)雜度為O(N)，而在無Leader的集群中，消息處理的時間復(fù)雜度為O(1).

已經(jīng)有一些基于Paxos的協(xié)議支持多個Leader，比如：Mencius；另外還有一些基于Paxos的有序無沖突并行協(xié)議，例如：Egalitarian Paxos 和Generalized Paxos. 希望能夠看到基于Raft協(xié)議的這種優(yōu)化！

參考資料：

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