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

為什么需要 Paxos

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

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

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

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

Paxos 協議主要有兩種用法：

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

以一個分布式的 KV 數據庫為例，假設數據庫對外提供 2 種操作 Put 和 Get，具體架構如下：

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

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

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

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

大白話理解 Paxos 算法

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

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

• Proposer：提議者
• Acceptor：決策者
• Learner：最終決策學習者

實現的時候往往采用一組固定數目的 Server，每個 Server 同時擔任上述三個角色。

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

Prepare 階段

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

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

Proposer 發起的 Proposal 至少要收到大多數以上的 Acceptor 的 Prepare 應答后，才能進入接下來的 Accept 階段，否則需要重新進行 Prepare 階段向大多數 Acceptor 發起 Prepare 請求。

Accept 階段

Proposer 收到大多數的 Acceptor 的 Prepare 應答后，看 Acceptor 是否已經有被接受的 Proposal。

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

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

Learn 階段

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

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

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

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

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

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

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

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

***種情況：溝通的隊長們全部都還沒有決定到底去哪里旅游，此刻驢友 A 會把自己想去的旅游地發給隊長們（比如馬爾代夫）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這樣，就難以達到半數以上都同意與某個驢友溝通的狀態，為了減小這個時間，Paxos 還有 Fast Paxos 的改進等等。

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

這里的例子說的是 basic paxos，basic paxos 協議較復雜，且相對效率較低，所以現在所有和 paxos 有關的協議的系統，一般都是基于 multi-paxos 來實現的。

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

Paxos 在數據庫高可用上的使用

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

強同步復制

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

這就有個問題，一旦主從之間網絡出現抖動，甚至從庫宕機，則主庫就無法再繼續提供服務，這種模式實現了數據的強一致，但是犧牲了服務的可用性。

異步復制

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

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

半同步復制

這種模式是一個折中，主要指至少有一個從庫節點收到日志返回給主庫 ok 之后，這時就可以返回給客戶端提交成功，當網絡環境不好的時候可能退化為異步復制。

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

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

• 數據不丟失
• 服務持續可用性
• 自動選主
• 自動容錯

使用 Paxos 協議的日志同步就可以實現以上的三個需求，當然 Paxos 協議需要依賴一個基本假設。

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

所以我們可以使用 Paxos 進行 redolog 或者 binlog 的復制，從而保證高可用強一致的集群。

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

[[216691]]

蒲聰，平臺事業部 DBA，2013 年 6 月加入去哪兒網，目前負責支付平臺事業部的 MySQL 數據庫和 HBase 整體的運維工作，從無到有建立去哪兒網 HBase 運維體系，在 MySQL 和 Hbase 數據庫上有豐富的架構、調優和故障處理等經驗。目前專注于分布式數據庫領域的研究和實踐工作。