最近大家都在討論P(yáng)axos算法。看了很多網(wǎng)上的文章，總覺(jué)得有點(diǎn)晦澀。經(jīng)過(guò)一段時(shí)間的研究，對(duì)Paxos有了一些了解。這里想總結(jié)一下，希望拋磚引玉。

1.你為什么需要帕克斯

Paxos要解決的問(wèn)題是分布式系統(tǒng)中的一致性問(wèn)題。那么“分布式系統(tǒng)中的一致性問(wèn)題”到底是什么呢？在分布式系統(tǒng)中，為了保證數(shù)據(jù)的高可用性，我們通常會(huì)保留多個(gè)數(shù)據(jù)副本，這些副本將被放置在不同的物理機(jī)器上。為了保持副本一致，所有副本的更新順序應(yīng)該一致。因?yàn)閿?shù)據(jù)的增加、刪除、修改、查詢操作一般涉及多個(gè)客戶端的并發(fā)操作，哪個(gè)客戶端先做，哪個(gè)客戶端后做，更新順序要有保證。如果不是分布式的，可以加鎖，誰(shuí)申請(qǐng)加鎖誰(shuí)先操作，但是有一個(gè)單點(diǎn)問(wèn)題。Paxos協(xié)議主要有兩個(gè)用途:一個(gè)是實(shí)現(xiàn)全局鎖服務(wù)或者命名和配置服務(wù)，比如Google Chubby和Apache ZooKeeper。另一種用法是用它把用戶數(shù)據(jù)復(fù)制到多個(gè)數(shù)據(jù)中心，比如Google Megastore和Google扳手。

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

在這樣的架構(gòu)下，多個(gè)服務(wù)器可以組成一個(gè)集群，以避免單點(diǎn)問(wèn)題。我們需要解決的是三個(gè)服務(wù)器必須同步，也就是說(shuō)如果請(qǐng)求put ("a "，1)發(fā)送到集群并成功，那么整個(gè)集群中的任何一個(gè)服務(wù)器都必須包含(" a "，1)。另外，假設(shè)多個(gè)客戶端并發(fā)訪問(wèn)集群，來(lái)自不同客戶端的請(qǐng)求可能會(huì)落在不同的服務(wù)器機(jī)器上，比如put ("b "，2)和put ("c "，3)，我們需要保證哪些客戶端請(qǐng)求先做，哪些客戶端請(qǐng)求后做，并保證更新順序，這是Paxos算法需要解決的問(wèn)題。

2.Paxos算法

先簡(jiǎn)單描述一下Paxos算法，對(duì)算法本身有一個(gè)直觀的認(rèn)識(shí)，然后結(jié)合下面的例子進(jìn)一步了解。

Paxos算法中有三個(gè)主要角色:

提議者:提議者

接受者:決策者

學(xué)習(xí)者:最終的決策學(xué)習(xí)者

實(shí)施時(shí)往往采用一套固定數(shù)量的服務(wù)器，每臺(tái)服務(wù)器同時(shí)扮演上述三個(gè)角色。

Paxos算法分為以下三個(gè)階段:

1.準(zhǔn)備階段

(1)發(fā)起人向多數(shù)承兌人發(fā)起1)提議人(紀(jì)元號(hào)，值)的準(zhǔn)備請(qǐng)求。

(2)2)接受者收到準(zhǔn)備請(qǐng)求，如果epochNo小于之前收到的，則直接拒絕；如果電子方案號(hào)大于收到的電子方案號(hào)，則將電子方案號(hào)最大的方案返回給提案人。

(3)由3)提議者發(fā)起的提議在進(jìn)入下一個(gè)接受階段之前，必須至少收到來(lái)自多于大多數(shù)接受者的準(zhǔn)備響應(yīng)；否則，有必要在準(zhǔn)備階段再次向大多數(shù)接受者發(fā)出準(zhǔn)備請(qǐng)求。

2.接受階段:

(1)演示者收到大多數(shù)接受者的“準(zhǔn)備”響應(yīng)后，查看接受者是否接受了1)提議者。如果沒(méi)有已接受的建議，則提出建議并啟動(dòng)接受請(qǐng)求；如果已經(jīng)有一個(gè)接受建議，從其中選擇具有最大電子技術(shù)號(hào)的建議，并啟動(dòng)對(duì)此建議的接受請(qǐng)求。

(2)接受方收到請(qǐng)求后，如果建議書的電子技術(shù)號(hào)大于其上次響應(yīng)準(zhǔn)備請(qǐng)求的電子技術(shù)號(hào)，則接受方接受該請(qǐng)求；否則，請(qǐng)求將被拒絕。

3.學(xué)習(xí)階段:

接受者接受的所有建議都應(yīng)不斷通知學(xué)習(xí)者，或者學(xué)習(xí)者應(yīng)主動(dòng)詢問(wèn)。一旦學(xué)習(xí)者確認(rèn)建議書被大多數(shù)接受者接受，這意味著建議書的價(jià)值被選擇，學(xué)習(xí)者可以了解建議書的價(jià)值，同時(shí)，他自己的服務(wù)器將不再接受建議書的請(qǐng)求。

我喜歡通過(guò)例子來(lái)理解理論，理論來(lái)源于生活。我會(huì)用生活中的例子來(lái)描述算法。

假設(shè)一群驢友決定端午節(jié)去旅游。全國(guó)有10個(gè)驢友。為了達(dá)成協(xié)議，這10個(gè)人又找了5個(gè)隊(duì)長(zhǎng)。5個(gè)隊(duì)長(zhǎng)互不交流，只給10個(gè)驢友發(fā)短信。

第一階段(申請(qǐng)階段)，驢友給五個(gè)隊(duì)長(zhǎng)發(fā)短信申請(qǐng)和他們溝通。隊(duì)長(zhǎng)任何時(shí)候只能和一個(gè)驢友交流。每條信息都有時(shí)間。組長(zhǎng)采取的原則是同意用最新的消息發(fā)送時(shí)間和驢友溝通。如果有更新的消息，就用更新的消息和驢友溝通。至少大部分隊(duì)長(zhǎng)同意溝通，讓驢友進(jìn)入實(shí)質(zhì)性溝通的第二階段。

第二階段(交流階段)，獲得交流權(quán)的驢友A收到隊(duì)長(zhǎng)發(fā)給他的旅游目的地，可能有幾種情況。

第一種情況:所有通信隊(duì)長(zhǎng)都還沒(méi)決定去哪里旅行。這時(shí)，驢友a(bǔ)會(huì)把他想去的目的地發(fā)給船長(zhǎng)(比如馬爾代夫)。因此，大多數(shù)船長(zhǎng)可能會(huì)同意。整個(gè)過(guò)程完成后，他將前往馬爾代夫，其他驢友遲早會(huì)知道。另外，意味著失敗?？赡苁顷?duì)長(zhǎng)沒(méi)回復(fù)(打電話給女朋友)，也可能是其他驢友搶了交流權(quán)(上面說(shuō)隊(duì)長(zhǎng)只和最新的短信交流)。如果失敗，A需要重啟第一階段申請(qǐng)，并向組長(zhǎng)發(fā)送短信申請(qǐng)通信權(quán)限。

第二種情況:至少有一個(gè)船長(zhǎng)決定了目的地。這時(shí)A會(huì)收到不同隊(duì)長(zhǎng)決定的多個(gè)目的地，這些目的地是不同隊(duì)長(zhǎng)和不同驢友在不同時(shí)間決定的。a將首先檢查一些旅游目的地是否得到了大多數(shù)(超過(guò)一半)團(tuán)隊(duì)領(lǐng)導(dǎo)的同意。如果有(假設(shè)三個(gè)領(lǐng)隊(duì)決定去三亞，一個(gè)去拉薩，可能因?yàn)槟撤N原因沒(méi)有照顧)，證明整個(gè)決定過(guò)程已經(jīng)達(dá)成一致。a收拾東西去三亞，結(jié)束！

如果沒(méi)有一個(gè)達(dá)到一半(比如兩個(gè)去三亞，一個(gè)去拉薩，一個(gè)去昆明，一個(gè)沒(méi)管)，A這個(gè)時(shí)候可能想去馬爾代夫，但是并沒(méi)有按照自己的意愿亂來(lái)(這是Paxos的關(guān)鍵，后者認(rèn)可前者，否則整個(gè)過(guò)程沒(méi)完沒(méi)了)， a會(huì)根據(jù)所有接待隊(duì)長(zhǎng)的旅游目的地找到最新的決定地點(diǎn)(比如去昆明是隊(duì)長(zhǎng)一分鐘前決定的，這時(shí)候去昆明的決定更新了，這樣下一個(gè)搶到交流權(quán)的驢友很可能會(huì)去昆明，越來(lái)越多的隊(duì)長(zhǎng)決定去昆明。

一旦大部分(超過(guò)一半)隊(duì)長(zhǎng)同意在某個(gè)時(shí)刻去某個(gè)地方，比如昆明，后續(xù)得到交流權(quán)的驢友B會(huì)發(fā)現(xiàn)大部分隊(duì)長(zhǎng)都決定去昆明了，它會(huì)服從，最后所有的驢友都達(dá)成了去昆明的協(xié)議。

Paxos的基本思路大致就是上面這個(gè)過(guò)程。Paxos用的是少數(shù)服從多數(shù)的思想。只要n (n為奇數(shù)，至少大于等于3)個(gè)節(jié)點(diǎn)中有[N/2]+1(其中N/2向下舍入)個(gè)或更多個(gè)節(jié)點(diǎn)與某個(gè)決策一致，那么系統(tǒng)就被認(rèn)為是一致的。在這種情況下，客戶端不需要與所有的服務(wù)器通信，而是選擇其中的大部分。不需要所有服務(wù)器都處于工作狀態(tài)，有些服務(wù)器是掛起的。只有半數(shù)以上存活下來(lái)，整個(gè)過(guò)程才能繼續(xù)，容錯(cuò)性相當(dāng)好。

帕克斯里的接受者相當(dāng)于上面的船長(zhǎng)，提議者相當(dāng)于上面的驢友，而epochNo。相當(dāng)于示例中申請(qǐng)短信的發(fā)送時(shí)間。Paxos最費(fèi)時(shí)間的地方是，需要他們一半以上的人同意溝通，才能進(jìn)入第二步。試想一下，剛開(kāi)始的時(shí)候，所有的驢友都給隊(duì)長(zhǎng)發(fā)瘋狂短信，每個(gè)隊(duì)長(zhǎng)都收到不同驢友的最新短信，很難達(dá)到一半以上同意和一個(gè)驢友交流的狀態(tài)。為了減少這個(gè)時(shí)間，這里不詳述Paxos和Fast Paxos的改進(jìn)。另外，paxos不是指一個(gè)協(xié)議，而是一類協(xié)議的總稱。比較常見(jiàn)的paxos協(xié)議有基本paxos和多paxos。這里的例子是基本的paxos?；镜膒axos協(xié)議比較復(fù)雜，效率相對(duì)較低，所以現(xiàn)在所有的paxos相關(guān)協(xié)議的系統(tǒng)，一般都是基于多paxos的。如果你感興趣，你可以參考https://zhuanlan.zhihu.com/p/25664121的文章

3.Paxos在數(shù)據(jù)庫(kù)高可用性中的應(yīng)用

作為dba，為了實(shí)現(xiàn)高可用性，最常用的高可用性模式是主從模式，以mysql為例，主要有幾種方式

(1)強(qiáng)同步復(fù)制，binlog同步到從庫(kù)后，從庫(kù)可以返回到主庫(kù)，然后提交給客戶端成功。這有一個(gè)問(wèn)題。一旦主庫(kù)和從庫(kù)之間的網(wǎng)絡(luò)緊張，甚至從庫(kù)關(guān)閉，主庫(kù)就不能再提供服務(wù)。這種模式實(shí)現(xiàn)了強(qiáng)大的數(shù)據(jù)一致性，但犧牲了服務(wù)的可用性。

(2)異步復(fù)制:主庫(kù)本地寫成功后，立即返回客戶端說(shuō)成功，不用等待從庫(kù)回復(fù)。這樣，一旦主庫(kù)關(guān)閉，少量日志可能無(wú)法與從庫(kù)同步，從而導(dǎo)致部分?jǐn)?shù)據(jù)丟失。這種模式有很好的可用性，但代價(jià)是數(shù)據(jù)的一致性。

(3)半同步復(fù)制，這是一種折衷，主要是指從庫(kù)節(jié)點(diǎn)收到的至少一個(gè)日志返回到主庫(kù)ok后，可以返回到客戶端成功提交，在網(wǎng)絡(luò)環(huán)境不好的時(shí)候可能退化為異步復(fù)制。

另外，主從模式還有一個(gè)不可避免的問(wèn)題，就是選擇主。對(duì)于主從模式，很多高可用的方案，比如MMM、MHA、中間層等等，都誕生了很久，但顯然理論和思路都不是最先進(jìn)的。

綜上所述，主從模式下處理數(shù)據(jù)庫(kù)高可用性存在很多缺陷。為了改進(jìn)這種數(shù)據(jù)同步模式，我們可以對(duì)數(shù)據(jù)庫(kù)的高可用性提出幾個(gè)要求:

(1)數(shù)據(jù)沒(méi)有丟失

(2)服務(wù)的持續(xù)可用性

(3)自動(dòng)選擇主控形狀

(4)自動(dòng)容錯(cuò)

以上三個(gè)需求可以通過(guò)使用paxos協(xié)議的日志同步來(lái)實(shí)現(xiàn)。當(dāng)然，paxos協(xié)議需要依賴一個(gè)基本假設(shè)，即主備之間的大部分機(jī)器(N/2+1)是活的，它們之間的網(wǎng)絡(luò)通信是正常的。如果不滿足此條件，服務(wù)將無(wú)法啟動(dòng)，數(shù)據(jù)也無(wú)法寫入或讀取。

因此，我們可以使用paxos復(fù)制重做日志或binlog，以確保集群具有高可用性和強(qiáng)一致性。不需要擔(dān)心主從切換，只需要有一個(gè)vip，后端映射后面數(shù)據(jù)庫(kù)的多個(gè)點(diǎn)。paxos將自動(dòng)確保多個(gè)點(diǎn)的一致寫入。業(yè)內(nèi)阿里巴巴云用paxos或者raft做一個(gè)企業(yè)三節(jié)點(diǎn)mysql集群。