近期大家都在討論 Paxos 算法，我看了很多網(wǎng)上的文章，總覺得有些晦澀難懂，經(jīng)過一段時間研究，對 Paxos 有了一些理解，在這里總結(jié)一下，希望能拋磚引玉。

為什么需要 Paxos

Paxos 要解決的問題，是分布式系統(tǒng)中的一致性問題。那么到底什么是“分布式系統(tǒng)中的一致性問題”呢？

在分布式系統(tǒng)中，為了保證數(shù)據(jù)的高可用，通常，我們會將數(shù)據(jù)保留多個副本(replica)，這些副本會放置在不同的物理的機(jī)器上。

副本要保持一致，那么，所有副本的更新序列就要保持一致。因為數(shù)據(jù)的增刪改查操作一般都存在多個客戶端并發(fā)操作，到底哪個客戶端先做，哪個客戶端后做，更新順序要保證。

如果不是分布式，那么可以通過加鎖的方法，誰先申請到鎖誰就先操作，但這就存在單點問題。

Paxos 協(xié)議主要有兩種用法：

• 用來實現(xiàn)全局的鎖服務(wù)或者命名和配置服務(wù)，例如 Google Chubby 以及 Apache ZooKeeper。
• 用它來將用戶數(shù)據(jù)復(fù)制到多個數(shù)據(jù)中心，例如 Google Megastore 以及 Google Spanner。

以一個分布式的 KV 數(shù)據(jù)庫為例，假設(shè)數(shù)據(jù)庫對外提供 2 種操作 Put 和 Get，具體架構(gòu)如下：

在這樣一個架構(gòu)下，可以通過多臺 Server 組成集群來避免單點問題。

我們需要解決的是 3 臺 Server 必須保持同步，也就是說，如果向集群發(fā)送請求 Put(“a”,1)并成功，那么整個集群任意一臺 Server 必須含有("a",1)。

另外假設(shè)此時多個 client 并發(fā)訪問集群，不同客戶端的請求可能會落入到不同的 Server 機(jī)器上。

比如并發(fā)有 Put("b”,2)和 Put(“c”,3)，我們需要保證哪個客戶端請求先做，哪個后做，保證更新順序，這就是 Paxos 算法需要解決的問題。

大白話理解 Paxos 算法

我們先來簡單描述一下 Paxos 算法，對算法本身有一個直觀的認(rèn)識，然后再結(jié)合后面的例子來進(jìn)一步理解。

在 Paxos 算法中，主要有 3 種角色：

• Proposer：提議者
• Acceptor：決策者
• Learner：最終決策學(xué)習(xí)者

實現(xiàn)的時候往往采用一組固定數(shù)目的 Server，每個 Server 同時擔(dān)任上述三個角色。

Paxos算法分為以下三個階段：

Prepare 階段

Proposer 向大多數(shù) Acceptor 發(fā)起 Proposal(epochNo,value)的 Prepare 請求。

Acceptor 收到 Prepare 請求，如果 epochNo 比之前接收到的小，直接拒絕；如果 epochNo 比之前已經(jīng)接收的大，就將已經(jīng)接收到的 epochNo ***的 Proposal 返回到 Proposer。

Proposer 發(fā)起的 Proposal 至少要收到大多數(shù)以上的 Acceptor 的 Prepare 應(yīng)答后，才能進(jìn)入接下來的 Accept 階段，否則需要重新進(jìn)行 Prepare 階段向大多數(shù) Acceptor 發(fā)起 Prepare 請求。

Accept 階段

Proposer 收到大多數(shù)的 Acceptor 的 Prepare 應(yīng)答后，看 Acceptor 是否已經(jīng)有被接受的 Proposal。

如果沒有已經(jīng)接受的 Proposal，就自己提出一個 Proposal，發(fā)起 Accept 請求；如果已經(jīng)有被接受的 Proposal，就從中選出 epochNo ***的 Proposal，發(fā)起對該 Proposal 的 Accept 請求。

Acceptor 收到請求后，如果該 Proposal 的 epochNo 比它***一次應(yīng)答 Prepare 請求的 epochNo 要大，那么就接受該請求；否則拒絕該請求。

Learn 階段

所有 Acceptor 接受的 Proposal 要不斷通知 Learner，或者 Learner 主動去查詢，一旦 Learner 確認(rèn) Proposal 被大多數(shù)的 Acceptor 接受。

那么表示這個 Proposal 的 Value 被 Chosen，Learner 就可以學(xué)習(xí)這個 Proposal 的 Value，同時自己的 Sever 上就不再受理 Proposor 的請求。

我喜歡通過例子來理解理論，理論源于生活，下面我以生活中的例子來進(jìn)行該算法的描述。

假設(shè)一群驢友決定春節(jié)去旅游，驢友遍布全國各地，一共 10 人，為了能達(dá)成一致，這 10 個人另外找 5 個作為隊長。5 個隊長之間相互不通信，只跟 10 個驢友發(fā)短信。

***階段（申請階段），驢友發(fā)短信給 5 個隊長，申請與隊長進(jìn)行溝通，隊長在任何時刻只能與一個驢友溝通。

發(fā)送的每條短信都帶有時間，隊長采用的原則是同意與短信發(fā)送時間***的驢友溝通。

如果出現(xiàn)更新的短信，則與短信更新的驢友溝通。至少大多數(shù)隊長同意溝通了，這個驢友才能進(jìn)入第二階段實質(zhì)性溝通。

第二階段（溝通階段），獲得溝通權(quán)的驢友 A 收到隊長們給他發(fā)的旅游地，可能有如下幾種情況：

***種情況：溝通的隊長們?nèi)慷歼€沒有決定到底去哪里旅游，此刻驢友 A 會把自己想去的旅游地發(fā)給隊長們（比如馬爾代夫）。

結(jié)果可能大多數(shù)隊長同意了，整個過程執(zhí)行完畢，就是去馬爾代夫旅游了，其他的驢友遲早會知道。

除此之外就表明失敗了，可能隊長沒有回復(fù)(跟女友打電話去了)，可能被其他驢友搶占溝通權(quán)了（上面說過隊長只跟***的短信的人進(jìn)行溝通）。

如果失敗了，A 需要重新開始***階段申請，重新給隊長們發(fā)短信申請溝通權(quán)。

第二種情況：至少有一個隊長已經(jīng)決定旅游地了，這個時候 A 會收到不同隊長決定的多個旅游地，這些旅游地是不同隊長跟不同驢友在不同時間做的決定。

A 會先看看有的旅游地是不是被大多數(shù)（半數(shù)以上）隊長同意了，如果有(這里假設(shè) 3 個隊長決定去三亞，一個去拉薩，另外可能某種原因沒搭理），那證明整個決定過程已經(jīng)達(dá)成一致了，A 收拾收拾去三亞吧，結(jié)束！

如果都沒有達(dá)到半數(shù)（比如 2 個去三亞，1 個去拉薩，1 個去昆明，1 個沒搭理），這時候 A 可能想去馬爾代夫，但也不按照自己意愿亂來了（這里是 Paxos 的關(guān)鍵所在，后者認(rèn)可前者，否則整個過程無止境了）。

A 會根據(jù)收到隊長的所有旅游地中找到***的那個決定地（比如去昆明是那個隊長在 1 分鐘前決定的，去拉薩的隊長是半小時前決定的，去三亞的隊長是 1 小時前決定的），于是 A 頂***的決定，去昆明。

這時候去昆明的決定又更新了，這樣下一個搶到溝通權(quán)的驢友也很大可能會頂去昆明，這樣決定去昆明的隊長會越來越多。

一旦某個時刻大多數(shù)（半數(shù)以上），隊長都同意了去某個地點，比如去昆明，后續(xù)獲得溝通權(quán)的驢友 B 會發(fā)現(xiàn)大多數(shù)隊長都決定去昆明了，它也會服從，最終所有的驢友都達(dá)成一致去昆明。

Paxos 的基本思想大致就是上面過程，Paxos 利用的是選舉，少數(shù)服從多數(shù)的思想。

只要 N 個(N 為奇數(shù)，至少大于等于 3)節(jié)點中，有[N/2]+1(這里N/2為向下取整)或以上個節(jié)點同意了某個決定，則認(rèn)為系統(tǒng)達(dá)到了一致。

這樣的話，客戶端不必與所有服務(wù)器通信，選擇與大部分通信即可；也無需服務(wù)器都全部處于工作狀態(tài)，有一些服務(wù)器掛掉，只有保證半數(shù)以上存活著，整個過程也能持續(xù)下去，容錯性相當(dāng)好。

Paxos 中的 Acceptor 相當(dāng)于上面的隊長，Proposer 相當(dāng)于上面的驢友，epochNo 號就相當(dāng)于例子中申請短信的發(fā)送時間。

Paxos 最消耗時間的地方就在于需要半數(shù)以上同意溝通了才能進(jìn)入第二步。

試想一下，一開始，所有驢友就給隊長狂發(fā)短信，每個隊長收到的***短信來自不同驢友。

這樣，就難以達(dá)到半數(shù)以上都同意與某個驢友溝通的狀態(tài)，為了減小這個時間，Paxos 還有 Fast Paxos 的改進(jìn)等等。

另外，Paxos 并不指代一個協(xié)議，而是一類協(xié)議的統(tǒng)稱，比較常見的 Paxos類協(xié)議有：basic paxos 和 multi-paxos。

這里的例子說的是 basic paxos，basic paxos 協(xié)議較復(fù)雜，且相對效率較低，所以現(xiàn)在所有和 paxos 有關(guān)的協(xié)議的系統(tǒng)，一般都是基于 multi-paxos 來實現(xiàn)的。

有興趣了解可以參考文章：https://zhuanlan.zhihu.com/p/25664121

Paxos 在數(shù)據(jù)庫高可用上的使用

作為 DBA，為了實現(xiàn)高可用，最常用的高可用方式是主從模式，以 MySQL 為例，主要有如下幾種：

強(qiáng)同步復(fù)制

binlog 同步到從庫之后，從庫返回給主庫 ok 之后才能返回給客戶端提交成功。

這就有個問題，一旦主從之間網(wǎng)絡(luò)出現(xiàn)抖動，甚至從庫宕機(jī)，則主庫就無法再繼續(xù)提供服務(wù)，這種模式實現(xiàn)了數(shù)據(jù)的強(qiáng)一致，但是犧牲了服務(wù)的可用性。

異步復(fù)制

主庫寫本地成功后，立刻返回給客戶端說成功，無需等待從庫應(yīng)答。

這樣一旦主庫宕機(jī)，可能會有少量的日志沒有同步到從庫造成部分?jǐn)?shù)據(jù)丟失，這種模式可用性很好，但是犧牲了數(shù)據(jù)的一致性。

半同步復(fù)制

這種模式是一個折中，主要指至少有一個從庫節(jié)點收到日志返回給主庫 ok 之后，這時就可以返回給客戶端提交成功，當(dāng)網(wǎng)絡(luò)環(huán)境不好的時候可能退化為異步復(fù)制。

另外主從模式還有一個無法繞過的問題，就是選主，為了主從模式的選主，長期以來也誕生了很多種高可用方案，如 MMM、MHA、中間層等等，但顯然理論和思路都不是***進(jìn)的。

總結(jié)一下，針對主從方式處理數(shù)據(jù)庫高可用有諸多缺陷，要想改進(jìn)這種數(shù)據(jù)同步方式，可以梳理數(shù)據(jù)庫高可用的幾點需求：

• 數(shù)據(jù)不丟失
• 服務(wù)持續(xù)可用性
• 自動選主
• 自動容錯

使用 Paxos 協(xié)議的日志同步就可以實現(xiàn)以上的三個需求，當(dāng)然 Paxos 協(xié)議需要依賴一個基本假設(shè)。

主備之間有多數(shù)派機(jī)器(N/2+1)是存活且它們之間的網(wǎng)絡(luò)通訊正常，如果不滿足這個條件，則無法啟動服務(wù)，數(shù)據(jù)也無法寫入和讀取。

所以我們可以使用 Paxos 進(jìn)行 redolog 或者 binlog 的復(fù)制，從而保證高可用強(qiáng)一致的集群。

主從的切換也不需要擔(dān)心，只需要有個 vip，后端映射后面數(shù)據(jù)庫的多點就行，Paxos 會自動保證多點的一致性寫入，業(yè)界阿里云使用 Paxos 或者 raft 來做的企業(yè)三節(jié)點的 MySQL 集群。 

[[216691]]

蒲聰，平臺事業(yè)部 DBA，2013 年 6 月加入去哪兒網(wǎng)，目前負(fù)責(zé)支付平臺事業(yè)部的 MySQL 數(shù)據(jù)庫和 HBase 整體的運(yùn)維工作，從無到有建立去哪兒網(wǎng) HBase 運(yùn)維體系，在 MySQL 和 Hbase 數(shù)據(jù)庫上有豐富的架構(gòu)、調(diào)優(yōu)和故障處理等經(jīng)驗。目前專注于分布式數(shù)據(jù)庫領(lǐng)域的研究和實踐工作。