jinfeng_wang

微信重磅開源生產(chǎn)級(jí)Paxos類庫PhxPaxos！本文將用科普的口吻向大家介紹PhxPaxos背后的實(shí)現(xiàn)原理以及一些有趣的細(xì)節(jié)。

本文由微信后臺(tái)團(tuán)隊(duì)授權(quán)轉(zhuǎn)載，ID：gh_93b1115dc96f

開源地址：https://github.com/tencent-wechat/phxpaxos

前言

本文通俗易懂，無需任何分布式以及Paxos算法基礎(chǔ)。

三個(gè)關(guān)鍵字：“生產(chǎn)級(jí)、Paxos、實(shí)現(xiàn)”，涵蓋了本文的重點(diǎn)。生產(chǎn)級(jí)，就是能用于生產(chǎn)線的、而非實(shí)驗(yàn)產(chǎn)品。生產(chǎn)級(jí)別擁有超高的穩(wěn)定性、不錯(cuò)的性能、能真正服務(wù)于用戶。Paxos，就不用說了。而實(shí)現(xiàn)，是本文重點(diǎn)中的重點(diǎn)。本文將避開Paxos算法理論與證明，直接進(jìn)入實(shí)現(xiàn)細(xì)節(jié)，告訴大家一個(gè)生產(chǎn)級(jí)別的Paxos庫背后的樣子。

為何要寫這篇文章？Paxos算法理論與證明不是更重要么？我?guī)啄昵霸?jīng)也讀過Paxos論文，雖然大致理解了算法的過程，但是在腦海中卻無一個(gè)場(chǎng)景去構(gòu)建這個(gè)算法，而后也就慢慢印象淡化，以至于最近重讀Paxos論文的時(shí)候，感覺像是第一次讀論文的樣子。

在真正去實(shí)現(xiàn)了Paxos之后，我才明白了這個(gè)問題。人們?nèi)ダ斫庖粋€(gè)理論或事務(wù)的時(shí)候，都會(huì)往這個(gè)理論或事物上套一個(gè)場(chǎng)景，然后在腦海里模擬而試圖去理解。比如經(jīng)典的Dijkstra算法，事實(shí)它并不只用于最短尋路，然而在學(xué)習(xí)這個(gè)算法的時(shí)候，最短尋路給我們提供了一個(gè)很好的場(chǎng)景，可以讓我們更快去理解它。

第一次讀Paxos論文，我不知道它的應(yīng)用場(chǎng)景，不知道它是用來干什么的，也不知道它怎么實(shí)現(xiàn)，然而這些往往就是一個(gè)基礎(chǔ)，大神可能可以自己創(chuàng)造場(chǎng)景，然而更多的人都需要知道這個(gè)場(chǎng)景，當(dāng)你知道后，理解算法將變得更為容易。

本文將告訴你Paxos是什么，用來做什么，怎么使用它，如何工程化，如何做到生產(chǎn)級(jí)別，以及在工程上會(huì)遇到的問題與解決辦法。文中將盡量講課方式的口吻，盡量避免專業(yè)術(shù)語，力求能闡述得更為通俗、簡(jiǎn)單易懂。 

Paxos簡(jiǎn)介

一致性協(xié)議

Paxos是一個(gè)一致性協(xié)議。什么叫一致性？一致性有很多種，從強(qiáng)到弱分了很多等級(jí)，如線性一致性、因果一致性、最終一致性，等等。什么是一致？這里舉個(gè)例子，三臺(tái)機(jī)器，每臺(tái)機(jī)器的磁盤存儲(chǔ)為128字節(jié)，如果三臺(tái)機(jī)器這128字節(jié)數(shù)據(jù)都完全相同，那么可以說這三臺(tái)機(jī)器是磁盤數(shù)據(jù)是一致的，更為抽象地說，就是多個(gè)副本確定同一個(gè)值，大家記錄下來同一個(gè)值，那么就達(dá)到了一致性。

Paxos能達(dá)到什么樣的一致性級(jí)別？這是一個(gè)較為復(fù)雜的問題。因?yàn)橐恢滦酝蝗Q于客觀存在的事實(shí)，如3臺(tái)機(jī)器雖然擁有相同的數(shù)據(jù)，但是數(shù)據(jù)的寫入是一個(gè)過程，有時(shí)間的先后，而更多的一致性取決于觀察者，觀察者看到的并未是最終的數(shù)據(jù)。這里就先不展開講，先暫且認(rèn)為Paxos保證了寫入的最終一致性。

為何說是一個(gè)協(xié)議而不是一個(gè)算法，可以這么理解，算法是設(shè)計(jì)出來服務(wù)于這個(gè)協(xié)議的，如同法律是協(xié)議，那么算法就是各種機(jī)構(gòu)的執(zhí)行者，使得法律的約束能得到保證。

Paxos的協(xié)議其實(shí)很簡(jiǎn)單，就三條規(guī)定。我認(rèn)為這三條規(guī)定也是Paxos最精髓的內(nèi)容，各個(gè)執(zhí)行者奮力去保護(hù)這個(gè)協(xié)議，使得這個(gè)協(xié)議的約束生效，自然就得到了一致性。 

分布式環(huán)境

為何要設(shè)計(jì)出這么一套協(xié)議，其他協(xié)議不行么？如最容易想到的，一個(gè)值A(chǔ)，往3臺(tái)機(jī)器都寫一次，這樣一套簡(jiǎn)單的協(xié)議，能不能達(dá)到一致性的效果？這里就涉及到另外一個(gè)概念，Paxos一致性協(xié)議是在特定的環(huán)境下才需要的，這個(gè)特定的環(huán)境稱為異步通信環(huán)境。而恰恰，幾乎所有的分布式環(huán)境都是異步通信環(huán)境，在計(jì)算機(jī)領(lǐng)域面對(duì)的問題，非常需要Paxos來解決。

異步通信環(huán)境指的是消息在網(wǎng)絡(luò)傳輸過程中，可能發(fā)生丟失、延遲、亂序現(xiàn)象。在這種環(huán)境下，上面提到的三寫協(xié)議就變得很雞肋了。消息亂序是一個(gè)非常惡劣的問題，這個(gè)問題導(dǎo)致大部分協(xié)議在分布式環(huán)境下都無法保證一致性，而導(dǎo)致這個(gè)問題的根本原因是網(wǎng)絡(luò)包無法控制超時(shí)，一個(gè)網(wǎng)絡(luò)包可以在網(wǎng)絡(luò)的各種設(shè)備交換機(jī)等停留數(shù)天，甚至數(shù)周之久，而在這段時(shí)間內(nèi)任意發(fā)出的一個(gè)包，都會(huì)跟之前發(fā)出的包產(chǎn)生亂序現(xiàn)象。無法控制超時(shí)的原因更多是因?yàn)闀r(shí)鐘的關(guān)系，各種設(shè)備以及交換機(jī)時(shí)鐘都有可能錯(cuò)亂，無法判斷一個(gè)包的真正到達(dá)時(shí)間。

異步通信環(huán)境并非只有Paxos能解決一致性問題，經(jīng)典的兩階段提交也能達(dá)到同樣的效果，但是分布式環(huán)境里面，除了消息網(wǎng)絡(luò)傳輸?shù)膼毫迎h(huán)境，還有另外一個(gè)讓人痛心疾首的，就是機(jī)器的當(dāng)機(jī)，甚至永久失聯(lián)。在這種情況下，兩階段提交將無法完成一個(gè)一致性的寫入，而Paxos，只要多數(shù)派機(jī)器存活就能完成寫入，并保證一致性。

至此，總結(jié)一下Paxos就是一個(gè)在異步通信環(huán)境，并容忍在只有多數(shù)派機(jī)器存活的情況下，仍然能完成一個(gè)一致性寫入的協(xié)議。 

提議者

前面講了這么多都是協(xié)議協(xié)議，在分布式環(huán)境當(dāng)中，協(xié)議作用就是每臺(tái)機(jī)器都要扮演一個(gè)角色，這個(gè)角色嚴(yán)格遵守這個(gè)協(xié)議去處理消息。在Paxos論文里面這個(gè)角色稱之為Acceptor，這個(gè)很好理解。大家其實(shí)更關(guān)心另外一個(gè)問題，到底誰去發(fā)起寫入請(qǐng)求，論文里面介紹發(fā)起寫入請(qǐng)求的角色為提議者，稱為Proposer。Proposer也是嚴(yán)格遵守paxos協(xié)議，通過與各個(gè)Acceptor的協(xié)同工作，去完成一個(gè)值的寫入。在Paxos里面，Proposer和Acceptor是最重要的兩個(gè)角色。

Paxos為誰服務(wù)

確定一個(gè)值

既然說到寫入數(shù)據(jù)，到底怎么去寫？寫一次還是寫多次，還是其他？這也是我一開始苦惱的問題，相信很多人都會(huì)很苦惱。

這里先要明確一個(gè)問題，Paxos到底在為誰服務(wù)？更確定地說，到底在為什么數(shù)據(jù)服務(wù)？還是引上面的例子，Paxos就是為這128字節(jié)的數(shù)據(jù)服務(wù)，Paxos并不關(guān)心外面有多少個(gè)提議者，寫入了多少數(shù)據(jù)，寫入的數(shù)據(jù)是不是一樣的，Paxos只會(huì)跟你說，我確定了一個(gè)值，當(dāng)這個(gè)值被確定之后，也就是這128字節(jié)被確定了之后，無論外面寫入什么，這個(gè)值都不會(huì)改變?cè)俑淖兞耍胰_(tái)機(jī)確定的值肯定是一樣的。

說到這估計(jì)肯定會(huì)有人懵了，說實(shí)話我當(dāng)時(shí)也懵了。我要實(shí)現(xiàn)一個(gè)存儲(chǔ)服務(wù)啊，我要寫入各種各樣的數(shù)據(jù)啊，你給我確定這么一個(gè)值，能有啥用？但先拋開這些疑問，大家先要明確這么一個(gè)概念，Paxos就是用來確定一個(gè)值用的，而且大家這里就先知道這么個(gè)事情就可以了，具體Paxos協(xié)議是怎樣的，怎么通過協(xié)議里面三條規(guī)定來獲得這樣的效果的，怎么證明的等等理論上的東西，都推薦去大家去看看論文，但是先看完本文再看，會(huì)得到另外的效果。

如下圖，有三臺(tái)機(jī)器（后面為了簡(jiǎn)化問題，不做特別說明都是以三臺(tái)機(jī)器作為講解例子），每臺(tái)機(jī)器上運(yùn)行這Acceptor來遵守paxos協(xié)議，每臺(tái)機(jī)器的Acceptor為自己的一份Data數(shù)據(jù)服務(wù)，可以有任意多個(gè)Proposer。當(dāng)Paxos協(xié)議宣稱一個(gè)值被確定（Chosen）后，那么Data數(shù)據(jù)就會(huì)被確定，并且永遠(yuǎn)不會(huì)被改變。

Proposer只需要與多數(shù)派的Acceptor交互，即可完成一個(gè)值的確定，但一旦這個(gè)值被確定下來后，無論P(yáng)roposer再發(fā)起任何值的寫入，Data數(shù)據(jù)都不會(huì)再被修改。Chosen value即是被確定的值，永遠(yuǎn)不會(huì)被修改。 

確定多個(gè)值

對(duì)我們來說，確定一個(gè)值，并且當(dāng)一個(gè)值確定后是永遠(yuǎn)不能被修改的，很明顯這個(gè)應(yīng)用價(jià)值是很低的。雖然我都甚至還不知道確定一個(gè)值能用來干嘛，但如果我們能有辦法能確定很多個(gè)值，那肯定會(huì)比一個(gè)值有用得多。我們先來看下怎么去確定多個(gè)值。

上文提到一個(gè)三個(gè)Acceptor和Proposer各自遵守paxos協(xié)議，協(xié)同工作最終完成一個(gè)值的確定。這里先定義一個(gè)概念，Proposer，各個(gè)Acceptor，所服務(wù)的Data共同構(gòu)成了一個(gè)大的集合，這個(gè)集合所運(yùn)行的paxos算法最終目標(biāo)是確定一個(gè)值，我們這里稱這個(gè)集合為一個(gè)Paxos實(shí)例。

一個(gè)實(shí)例可以確定一個(gè)值，那么多個(gè)實(shí)例自然可以確定多個(gè)值，很簡(jiǎn)單的模型就可以構(gòu)建出來，只要我們同時(shí)運(yùn)行著多個(gè)實(shí)例，那么我們就能完成確定多個(gè)值的目標(biāo)。

這里強(qiáng)調(diào)一點(diǎn)，每個(gè)實(shí)例必須是完全獨(dú)立，互不干涉的。意思就是說Acceptor不能去修改其他實(shí)例的Data數(shù)據(jù)，Proposer同樣也不能跨越實(shí)例去與其他實(shí)例的Acceptor交互。

如下圖，三臺(tái)機(jī)器每臺(tái)機(jī)器運(yùn)行兩個(gè)實(shí)例，每個(gè)實(shí)例獨(dú)立運(yùn)作，最終會(huì)產(chǎn)生兩個(gè)確定的值。這里兩個(gè)實(shí)際可以擴(kuò)展成任意多個(gè)。 

至此，實(shí)例成為了我現(xiàn)在介紹Paxos的一個(gè)基本單元，一個(gè)實(shí)例確定一個(gè)值，多個(gè)實(shí)例確定多個(gè)值，但各個(gè)實(shí)例獨(dú)立，互不干涉。

然而比較遺憾的一點(diǎn)，確定多個(gè)值，仍然對(duì)我們沒有太大的幫助，因?yàn)槔锩孀羁珊薜囊稽c(diǎn)是，當(dāng)一個(gè)值被確定后，就永遠(yuǎn)無法被修改了，這是我們不能接受的。大部分的存儲(chǔ)服務(wù)可能都需要有一個(gè)修改的功能。 

有序確定多個(gè)值

我們需要轉(zhuǎn)換一下切入點(diǎn)，也許我們需要Paxos確定的值，并不一定是我們真正看到的數(shù)據(jù)。我們觀察大部分存儲(chǔ)系統(tǒng)，如LevelDB，都是以AppendLog的形式，確定一個(gè)操作系列，而后需要恢復(fù)存儲(chǔ)的時(shí)候都可以通過這個(gè)操作系列來恢復(fù)，而這個(gè)操作系列，正是確定之后就永遠(yuǎn)不會(huì)被修改的。到這已經(jīng)很豁然開朗了，只要我們通過Paxos完成一個(gè)多機(jī)一致的有序的操作系列，那么通過這個(gè)操作系列的演進(jìn)，可實(shí)現(xiàn)的東西就很有想象空間了，存儲(chǔ)服務(wù)必然不是問題。

如何利用Paxos有序的確定多個(gè)值？上文我們知道可以通過運(yùn)行多個(gè)實(shí)例來完成確定多個(gè)值，但為了達(dá)到順序的效果，需要加強(qiáng)一下約束。

首先給實(shí)例一個(gè)編號(hào)，定義為i，i從0開始，只增不減，由本機(jī)器生成，不依賴網(wǎng)絡(luò)。其次，我們保證一臺(tái)機(jī)器任一時(shí)刻只能有一個(gè)實(shí)例在工作，這時(shí)候Proposer往該機(jī)器的寫請(qǐng)求都會(huì)被當(dāng)前工作的實(shí)例受理。最后，當(dāng)編號(hào)為i的實(shí)例獲知已經(jīng)確定好一個(gè)值之后，這個(gè)實(shí)例將會(huì)被銷毀，進(jìn)而產(chǎn)生一個(gè)編號(hào)為i+1的實(shí)例。

基于這三個(gè)約束，每臺(tái)機(jī)器的多個(gè)實(shí)例都是一個(gè)連續(xù)遞增編號(hào)的有序系列，而基于Paxos的保證，同一個(gè)編號(hào)的實(shí)例，確定的值都是一致的，那么三臺(tái)機(jī)都獲得了一個(gè)有序的多個(gè)值。

下面結(jié)合一個(gè)圖來詳細(xì)說明一下這個(gè)運(yùn)作過程，以及存在什么異常情況以及異常情況下的處理方式。

圖中A，B，C代表三個(gè)機(jī)器，紅色代表已經(jīng)被銷毀的實(shí)例，根據(jù)上文約束，最大的實(shí)例就是當(dāng)前正在工作的實(shí)例。A機(jī)器當(dāng)前工作的實(shí)例編號(hào)是6，B機(jī)是5，而C機(jī)是3。為何會(huì)出現(xiàn)這種工作實(shí)例不一樣的情況？首先解釋一下C機(jī)的情況，由于Paxos只要求多數(shù)派存活即可完成一個(gè)值的確定，所以假設(shè)C出現(xiàn)當(dāng)機(jī)或者消息丟失延遲等，都會(huì)使得自己不知道3-5編號(hào)的實(shí)例已經(jīng)被確定好值了。而B機(jī)比A機(jī)落后一個(gè)實(shí)例，是因?yàn)锽機(jī)剛剛參與完成實(shí)例5的值的確定，但是他并不知道這個(gè)值被確定了。上面的情況與其說是異常情況，也可以說是正常的情況，因?yàn)樵诜植际江h(huán)境，發(fā)生這種事情是很正常的。

下面分析一下基于圖示狀態(tài)的對(duì)于C機(jī)的寫入是如何工作的。C機(jī)實(shí)例3處理一個(gè)新的寫入，根據(jù)Paxos協(xié)議的保證，由于實(shí)例3已經(jīng)確定好一個(gè)值了，所以無論寫入什么值，都不會(huì)改變?cè)瓉淼闹担赃@時(shí)候C機(jī)實(shí)例3發(fā)起一輪Paxos算法的時(shí)候就可以獲知實(shí)例3真正確定的值，從而跳到實(shí)例4。但在工程實(shí)現(xiàn)上這個(gè)事情可以更為簡(jiǎn)化，上文提到，各個(gè)實(shí)例是獨(dú)立，互不干涉的，也就是A機(jī)的實(shí)例6，B機(jī)的實(shí)例5都不會(huì)去理會(huì)C機(jī)實(shí)例3發(fā)出的消息，那么C機(jī)實(shí)例3這個(gè)寫入是無法得到多數(shù)派響應(yīng)的，自然無法寫入成功。

再分析一下A機(jī)的寫入，同樣實(shí)例6無法獲得多數(shù)派的響應(yīng)，同樣無法寫入成功。同樣假如B機(jī)實(shí)例5有寫入，也是寫入失敗的結(jié)果，那如何使得能繼續(xù)寫入，實(shí)例編號(hào)能繼續(xù)增長(zhǎng)呢？這里引出下一個(gè)章節(jié)。 

實(shí)例的對(duì)齊（Learn）

上文說到每個(gè)實(shí)例里面都有一個(gè)Acceptor的角色，這里再增加一個(gè)角色稱為L(zhǎng)earner，顧名思義就是找別人學(xué)習(xí)，她回去詢問別的機(jī)器的相同編號(hào)的實(shí)例，如果這個(gè)實(shí)例已經(jīng)被銷毀了，那說明值已經(jīng)確定好了，直接把這個(gè)值拉回來寫到當(dāng)前實(shí)例里面，然后編號(hào)增長(zhǎng)跳到下一個(gè)實(shí)例再繼續(xù)詢問，如此反復(fù)，直到當(dāng)前實(shí)例編號(hào)增長(zhǎng)到與其他機(jī)器一致。

由于約束里面保證僅當(dāng)一個(gè)實(shí)例獲知到一個(gè)確定的值之后，才能編號(hào)增長(zhǎng)開始新的實(shí)例，那么換句話說，只要編號(hào)比當(dāng)前工作實(shí)例小的實(shí)例（已銷毀的），他的值都是已經(jīng)確定好的。所以這些值并不需要再通過Paxos來確定了，而是直接由Learner直接學(xué)習(xí)得到即可。

如上圖所示，B機(jī)的實(shí)例5是直接由Learner從A機(jī)學(xué)到的，而C機(jī)的實(shí)例3-5都是從B機(jī)學(xué)到的，這樣大家就全部走到了實(shí)例6，這時(shí)候?qū)嵗?接受的寫請(qǐng)求就能繼續(xù)工作下去。 

Paxos如何應(yīng)用

狀態(tài)機(jī)

一個(gè)有序的確定的值，也就是日志，可以通過定義日志的語義進(jìn)行重放的操作，那么這個(gè)日志是怎么跟Paxos結(jié)合起來的呢？我們利用Paxos確定有序的多個(gè)值這個(gè)特點(diǎn)，再加上這里引入的一個(gè)狀態(tài)機(jī)的概念，結(jié)合起來實(shí)現(xiàn)一個(gè)真正有工程意義的系統(tǒng)。

狀態(tài)機(jī)這個(gè)名詞大家都不陌生，一個(gè)狀態(tài)機(jī)必然涉及到一個(gè)狀態(tài)轉(zhuǎn)移，而Paxos的每個(gè)實(shí)例，就是狀態(tài)轉(zhuǎn)移的輸入，由于每臺(tái)機(jī)器的實(shí)例編號(hào)都是連續(xù)有序增長(zhǎng)的，而每個(gè)實(shí)例確定的值是一樣的，那么可以保證的是，各臺(tái)機(jī)器的狀態(tài)機(jī)輸入是完全一致的。根據(jù)狀態(tài)機(jī)的理論，只要初始狀態(tài)一致，輸入一致，那么引出的最終狀態(tài)也是一致的。而這個(gè)狀態(tài)，是有無限的想象空間，你可以用來實(shí)現(xiàn)非常多的東西。

如下圖這個(gè)例子是一個(gè)狀態(tài)機(jī)結(jié)合Paxos實(shí)現(xiàn)了一個(gè)具有多機(jī)一致的KV系統(tǒng)。 

實(shí)例0-3的值都已經(jīng)被確定，通過這4個(gè)值最終引出(b, ‘jeremy’)這個(gè)狀態(tài)，而各臺(tái)機(jī)器實(shí)例系列都是一致的，所以大家的狀態(tài)都一樣，雖然引出狀態(tài)的時(shí)間有先后，但確定的實(shí)例系列確定的值引出確定的狀態(tài)。

下圖例子告訴大家Proposer，Acceptor，Learner，State machine是如何協(xié)同工作的。

一個(gè)請(qǐng)求發(fā)給Proposer，Proposer與相同實(shí)例編號(hào)為x的Acceptor協(xié)同工作，共同完成一值的確定，之后將這個(gè)值作為狀態(tài)機(jī)的輸入，產(chǎn)生狀態(tài)轉(zhuǎn)移，最終返回狀態(tài)轉(zhuǎn)移結(jié)果給發(fā)起請(qǐng)求者。

Paxos工程化

多角色盡量在一起

上文提到一個(gè)實(shí)例，需要有Proposer和Acceptor兩個(gè)角色協(xié)同工作，另外還要加以Learner進(jìn)行輔助，到了應(yīng)用方面又加入了State machine，這里面勢(shì)必會(huì)有很多狀態(tài)需要共享。如一個(gè)Proposer必須于Acceptor處于相同的實(shí)例才能工作，那么Proposer也就必須知道當(dāng)前工作的實(shí)例是什么，又如State machine必須知道實(shí)例的Chosen value是啥，而Chosen value是存儲(chǔ)于Acceptor管理的Data數(shù)據(jù)中的。在概念上，這些角色可以通過任意的通信方式進(jìn)行狀態(tài)共享，但真正去實(shí)現(xiàn)，我們都會(huì)盡量基于簡(jiǎn)單、高性能出發(fā)，一般都會(huì)將這些角色同時(shí)融合在一個(gè)機(jī)器、一個(gè)進(jìn)程里面。

下圖例子是一個(gè)工程上比較常規(guī)的實(shí)現(xiàn)方式。 

這里提出一個(gè)新的概念，這里三臺(tái)機(jī)器，每臺(tái)機(jī)器運(yùn)行著相同的實(shí)例i，實(shí)例里整合了Acceptor，Proposer，Learner，State machine四個(gè)角色，三臺(tái)機(jī)器的相同編號(hào)實(shí)例共同構(gòu)成了一個(gè)Paxos group的概念，一個(gè)請(qǐng)求只需要灌進(jìn)Paxos group里面就可以了，根據(jù)Paxos的特點(diǎn)，Paxos group可以將這個(gè)請(qǐng)求可以隨意寫往任意一個(gè)Proposer，由Proposer來進(jìn)行提交。Paxos group是一個(gè)虛設(shè)的概念，只是為了方便解釋，事實(shí)上是請(qǐng)求隨意丟到三臺(tái)機(jī)任意一個(gè)Proposer就可以了。

那么具體這四個(gè)角色是如何工作的呢。首先，由于Acceptor和Proposer在同一個(gè)進(jìn)程里面，那么保證它們處于同一個(gè)實(shí)例是很簡(jiǎn)單的事情。其次，當(dāng)一個(gè)值被確認(rèn)之后，也可以很方便傳送給State machine去進(jìn)行狀態(tài)的轉(zhuǎn)移。最后當(dāng)出現(xiàn)異常狀態(tài)，實(shí)例落后或者收不到其他機(jī)器的回應(yīng)，剩下的事情就交給Learner去解決，就這樣一整合，事情就變得簡(jiǎn)單了。 

嚴(yán)格的落盤

Paxos協(xié)議的運(yùn)作工程需要做出很多保證，即保證了在相同的條件下一定會(huì)做出相同的處理，如何能完成這些保證？眾所周知，在計(jì)算機(jī)里面，一個(gè)線程、進(jìn)程，甚至機(jī)器都可能隨時(shí)掛掉，而當(dāng)他再次啟動(dòng)的時(shí)候，磁盤是他恢復(fù)記憶的方法，在Paxos協(xié)議運(yùn)作里面也一樣，磁盤是她記錄下這些保證條目的介質(zhì)。

而一般的磁盤寫入是有緩沖區(qū)的，當(dāng)機(jī)器當(dāng)機(jī)，這些緩沖區(qū)仍然未刷到磁盤，那么就會(huì)丟失部分?jǐn)?shù)據(jù)，導(dǎo)致保證失效，所以在Paxos做出這些保證的時(shí)候，落盤一定要非常嚴(yán)格，嚴(yán)格的意思是當(dāng)操作系統(tǒng)告訴我寫盤成功，那么無論任何情況都不會(huì)丟失。這個(gè)我們一般使用fsync來解決問題，也就是每次進(jìn)行寫盤都要附加一個(gè)fsync進(jìn)行保證。

Fsync是一個(gè)非常重的操作，也因?yàn)檫@個(gè)，Paxos最大的瓶頸也是在寫盤上，在工程上，我們需要盡量通過各種手段，去減少Paxos算法所需要的寫盤次數(shù)。

萬一磁盤fsync之后，仍然丟失或者數(shù)據(jù)錯(cuò)亂怎么辦？這個(gè)稱之為拜占庭問題，工程上需要一系列的措施檢測(cè)出這些拜占庭錯(cuò)誤，然后選擇性的進(jìn)行數(shù)據(jù)回滾或者直接丟棄。 

一個(gè)Leader

由于看這篇文章的讀者未必知道Paxos理論上是如何去確定一個(gè)值的，這里簡(jiǎn)單說明一下，Paxos一個(gè)實(shí)例，支持任意多個(gè)Proposer同時(shí)進(jìn)行寫入，但是最終確定出來一個(gè)相同的值，里面是運(yùn)用了一些類似鎖的方法來解決沖突的，而越多的Proposer進(jìn)行同時(shí)寫入，沖突的劇烈程度會(huì)更高，雖然完全不妨礙最終會(huì)確定一個(gè)值，但是性能上是比較差的。所以這里需要引入一個(gè)Leader的概念。

Leader就是領(lǐng)導(dǎo)者的意思，顧名思義我們希望有一個(gè)Proposer的領(lǐng)導(dǎo)者，優(yōu)先由他來進(jìn)行寫入，那么當(dāng)在只有一個(gè)Proposer在進(jìn)行寫入的情況下，沖突的概率是極小的，這樣性能會(huì)得到一個(gè)飛躍。這里再次重申一下，Leader的引入，不是為了解決一致性問題，而是為了解決性能問題。

由于Leader解決的是性能問題而非一致性問題，即使Leader出錯(cuò)也不會(huì)妨礙正確性，所以我們只需要保證大部分情況下只有一個(gè)Proposer在工作就行了，而不用去保證絕對(duì)的不允許出現(xiàn)兩個(gè)Proposer或以上同時(shí)工作，那么這個(gè)通過一些簡(jiǎn)單的心跳以及租約就可以做到，實(shí)現(xiàn)也是非常簡(jiǎn)單，這里就不展開解釋。 

狀態(tài)機(jī)記錄最大實(shí)例編號(hào)

狀態(tài)機(jī)可以是任何東西，可以是kv，可以是mysql的binlog，在Paxos實(shí)例運(yùn)行時(shí)，我們可以保證時(shí)刻與狀態(tài)機(jī)同步。這里同步的意思是指狀態(tài)機(jī)輸入到的實(shí)例的最大編號(hào)和Paxos運(yùn)行當(dāng)中認(rèn)為已經(jīng)確認(rèn)好值的實(shí)例最大編號(hào)是一樣的，因?yàn)楫?dāng)一個(gè)實(shí)例已經(jīng)完成值的確認(rèn)之后，我們必須確保已經(jīng)輸入到狀態(tài)機(jī)并且進(jìn)行了狀態(tài)轉(zhuǎn)移，之后我們才能開啟新的實(shí)例。但，當(dāng)機(jī)器重啟或者進(jìn)程重啟之后，狀態(tài)機(jī)的數(shù)據(jù)可能會(huì)由于自身實(shí)現(xiàn)問題，或者磁盤數(shù)據(jù)丟失而導(dǎo)致回滾，這個(gè)我們沒辦法像上文提到的fsync一樣進(jìn)行這么強(qiáng)的約束，所以提出了一種方法，狀態(tài)機(jī)必須嚴(yán)格記得自己輸入過的最大實(shí)例編號(hào)。

這個(gè)記錄有什么用？在每次啟動(dòng)的時(shí)候，狀態(tài)機(jī)告訴Paxos最大的實(shí)例編號(hào)x，而Paxos發(fā)現(xiàn)自己最大的已確定值的實(shí)例編號(hào)是y，而x < y. 那這時(shí)候怎么辦，只要有(x, y]的Chosen value，我們重新把這些value一個(gè)一個(gè)輸入到狀態(tài)機(jī)，那么狀態(tài)機(jī)的狀態(tài)就會(huì)更新到y(tǒng)了，這個(gè)稱為啟動(dòng)重放。

這樣對(duì)狀態(tài)機(jī)的要求將盡量簡(jiǎn)單，只需要嚴(yán)格的記錄好這么一個(gè)編號(hào)就可以了。當(dāng)然不記錄，每次從0開始也可以，但這樣Paxos需要從0開始重放，是一個(gè)蠢方法。

異步消息處理模型

上文說到分布式環(huán)境是一個(gè)異步通信環(huán)境，而Paxos解決了基于這種環(huán)境下的一致性問題，那么一個(gè)顯而易見的特點(diǎn)就是，我們不知道也不確定消息何時(shí)到達(dá)，是否有序到達(dá)，是否到達(dá)，我們只需要去遵守Paxos協(xié)議，嚴(yán)格的處理每一條到達(dá)的消息即可，這跟RPC模型比較不一樣，Paxos的特點(diǎn)是有去無回。

這里先定義一個(gè)名詞叫Paxos消息，這里指的是Paxos為了去確定一個(gè)值，算法運(yùn)行過程中需要的通信產(chǎn)生的消息。下圖通過一個(gè)異步消息處理模型去構(gòu)建一個(gè)響應(yīng)Paxos消息系統(tǒng)，從而完成Paxos系統(tǒng)的搭建。

這里分為四個(gè)部分：

1. Request，即外部請(qǐng)求，這個(gè)請(qǐng)求直接輸入到Proposer里面，由Proposer嘗試完成一個(gè)值的確定。
2. Network i/o，網(wǎng)絡(luò)i/o處理，負(fù)責(zé)paxos內(nèi)部產(chǎn)生的消息的發(fā)送與接收，并且只處理Paxos消息，采用私有端口，純異步，各臺(tái)機(jī)器之前的network i/o模塊互相通信。
3. Acceptor，Proposer，Learner。用于響應(yīng)并處理Paxos消息。
4. State machine，狀態(tài)機(jī)，實(shí)例確定的值(Chosen value)的應(yīng)用者。

工作流程如下：

1. 收到Request，由Proposer處理，如需要發(fā)送Paxos消息，則通過network i/o發(fā)送。
2. Net work i/o收到Paxos消息，根據(jù)消息類型選擇Acceptor，Proposer，或Leaner處理，如處理后需要發(fā)送Paxos消息，則通過network i/o發(fā)送。
3. Proposer通過paxos消息獲知Chosen value，則輸入value到State machine完成狀態(tài)轉(zhuǎn)移，最終通知Request轉(zhuǎn)移結(jié)果，完成一個(gè)請(qǐng)求的處理。
4. 當(dāng)Paxos完成一個(gè)值的確認(rèn)之后，所有當(dāng)前實(shí)例相關(guān)角色狀態(tài)進(jìn)行清空并初始化進(jìn)行下一個(gè)編號(hào)的實(shí)例。

生產(chǎn)級(jí)Paxos庫

RTT與寫盤次數(shù)的優(yōu)化

雖然經(jīng)過在工程化上做的諸多要求，可以實(shí)現(xiàn)出一個(gè)基于Paxos搭建的，可掛載任意狀態(tài)機(jī)，并且能穩(wěn)定運(yùn)行的系統(tǒng)，但性能遠(yuǎn)遠(yuǎn)不夠。在性能方面需要進(jìn)行優(yōu)化，方能上崗。由于上文并未對(duì)Paxos理論做介紹，這里大概說明一下樸素的Paxos算法，確定一個(gè)值，在無沖突的情況下，需要兩個(gè)RTT，以及每臺(tái)機(jī)器的三次寫盤。這個(gè)性能想象一下在我們?cè)诰€服務(wù)是非常慘烈的。為了達(dá)到生產(chǎn)級(jí)，最終我們將這個(gè)優(yōu)化成了一個(gè)RTT以及每臺(tái)機(jī)器的一次寫盤。(2,3)優(yōu)化到(1,1)，使得我們能真正在線上站穩(wěn)腳跟。但由于本文的重點(diǎn)仍然不在理論，這里具體優(yōu)化手段就暫不多做解釋。

同時(shí)運(yùn)行多個(gè)Paxos group

由于實(shí)例運(yùn)行的方式是確保i實(shí)例的銷毀才能運(yùn)行i+1實(shí)例，那么這個(gè)請(qǐng)求的執(zhí)行明顯是一個(gè)串行的過程，這樣對(duì)cpu的利用是比較低的，我們得想辦法將cpu利用率提升上來。

一個(gè)Paxos group可以完成一個(gè)狀態(tài)機(jī)的輸入，但如果一臺(tái)機(jī)器同時(shí)有多個(gè)狀態(tài)機(jī)呢？比如可以同時(shí)利用Paxos實(shí)現(xiàn)兩種業(yè)務(wù)，每個(gè)業(yè)務(wù)對(duì)應(yīng)一個(gè)狀態(tài)機(jī)，互不關(guān)聯(lián)。那么一個(gè)Paxos group分配一個(gè)端口，我們即可在一臺(tái)機(jī)器上運(yùn)行多個(gè)Paxos group，各自端口不同，互相獨(dú)立。那么cpu利用率將能大幅提升。

比如想實(shí)現(xiàn)一個(gè)分布式的kv，那么對(duì)于一臺(tái)機(jī)器服務(wù)的key段，我們可以再在里面分割成多個(gè)key段，那每個(gè)小key段就是一個(gè)獨(dú)立的狀態(tài)機(jī)，每個(gè)狀態(tài)機(jī)搭配一個(gè)獨(dú)立Paxos group即可完成同時(shí)運(yùn)行。

但一臺(tái)機(jī)器搞幾十個(gè)，幾百個(gè)端口也是比較齷齪的手法，所以我們?cè)谏a(chǎn)級(jí)的Paxos庫上，實(shí)現(xiàn)了基于一個(gè)network i/o搭配多組Paxos group的結(jié)構(gòu)。

如上圖，每個(gè)group里面都有完整的Paxos邏輯，只需要給Paxos消息增加一個(gè)group的標(biāo)識(shí)，通過network i/o的處理，將不同group的消息輸送到對(duì)應(yīng)的group里面處理。這樣我們一臺(tái)機(jī)器只需要一個(gè)私有端口，即可完成多個(gè)狀態(tài)機(jī)的并行處理。

至此可以獲得一個(gè)多個(gè)Paxos group的系統(tǒng)，完整結(jié)構(gòu)如下：

更快對(duì)齊數(shù)據(jù)

上文說到當(dāng)各臺(tái)機(jī)器的當(dāng)前運(yùn)行實(shí)例編號(hào)不一致的時(shí)候，就需要Learner介入工作來對(duì)齊數(shù)據(jù)了。Learner通過其他機(jī)器拉取到當(dāng)前實(shí)例的Chosen value，從而跳轉(zhuǎn)到下一編號(hào)的實(shí)例，如此反復(fù)最終將自己的實(shí)例編號(hào)更新到與其他機(jī)器一致。那么這里學(xué)習(xí)一個(gè)實(shí)例的網(wǎng)絡(luò)延時(shí)代價(jià)是一個(gè)RTT。可能這個(gè)延遲看起來還不錯(cuò)，但是當(dāng)新的數(shù)據(jù)仍然通過一個(gè)RTT的代價(jià)不斷寫入的時(shí)候，而落后的機(jī)器仍然以一個(gè)RTT來進(jìn)行學(xué)習(xí)，這樣會(huì)出現(xiàn)很難追上的情況。

這里需要改進(jìn)，我們可以提前獲取差距，批量打包進(jìn)行學(xué)習(xí)，比如A機(jī)器Learner記錄當(dāng)前實(shí)例編號(hào)是x，B機(jī)器是y，而x < y，那么B機(jī)器通過通信獲取這個(gè)差距，將(x,y]的Chosen value一起打包發(fā)送給A機(jī)器，A機(jī)器進(jìn)行批量的學(xué)習(xí)。這是一個(gè)很不錯(cuò)的方法。

但仍然不夠快，當(dāng)落后的數(shù)據(jù)極大，B機(jī)器發(fā)送數(shù)據(jù)需要的網(wǎng)絡(luò)耗時(shí)也將變大，那么發(fā)送數(shù)據(jù)的過程中，A機(jī)器處于一種空閑狀態(tài)，由于Paxos另外一個(gè)瓶頸在于寫盤，如果不能利用這段時(shí)間來進(jìn)行寫盤，那性能仍然堪憂。我們參考流式傳輸，采用類似的方法實(shí)現(xiàn)Learner的邊發(fā)邊學(xué)，B機(jī)器源源不斷的往A機(jī)器輸送數(shù)據(jù)，而A機(jī)器只需要收到一個(gè)實(shí)例最小單元的包體，即可立即解開進(jìn)行學(xué)習(xí)并完成寫盤。

具體的實(shí)現(xiàn)大概是先進(jìn)行一對(duì)一的協(xié)商，建立一個(gè)Session通道，在Session通道里直接采用直塞的方式無腦發(fā)送數(shù)據(jù)。當(dāng)然也不是完全的無腦，Session通過心跳機(jī)制進(jìn)行維護(hù)，一旦Session斷開即停止發(fā)送。 

刪除Paxos數(shù)據(jù)

Paxos數(shù)據(jù)，即通過Paxos確認(rèn)下來的有序的多個(gè)值，后面我們稱這個(gè)為Paxos log，這些log作為狀態(tài)機(jī)的輸入，是源源不斷的。狀態(tài)機(jī)的狀態(tài)是有限的，但輸入是無限的，但磁盤的空間又是有限的，所以輸入必然不能長(zhǎng)期保留，我們必須找到方法來把它刪除。

上文說到要求狀態(tài)機(jī)記錄下來輸入過的最大實(shí)例編號(hào)，這里定義為Imax，那么每次啟動(dòng)的時(shí)候是從這個(gè)編號(hào)后開始重放Paxos log，也就是說小于等于這個(gè)編號(hào)Imax數(shù)據(jù)是沒用的了，它不會(huì)再次使用，可以直接刪除掉。但這個(gè)想法不夠周全，因?yàn)镻axos是允許少于多數(shù)派的機(jī)器掛掉的，這個(gè)掛掉可能是機(jī)器永遠(yuǎn)離線。而這種情況我們一般是用一臺(tái)新的機(jī)器代替。這臺(tái)新的機(jī)器要干什么？他要從0開始重放Paxos log，而這些Paxos log從哪里來？肯定是Learner找別的機(jī)器拷貝過來的。那別的機(jī)器刪了怎么辦？涼拌。

但也并不是沒辦法了，我可以把這臺(tái)機(jī)狀態(tài)機(jī)相關(guān)的數(shù)據(jù)全部拷貝到新機(jī)，然后就可以從Imax來啟動(dòng)了，那么自然就不需要[0,Imax]的Paxos log了。但是狀態(tài)機(jī)的數(shù)據(jù)是無時(shí)無刻不在寫入的，一個(gè)正在寫入的數(shù)據(jù)去拷貝出來，出現(xiàn)什么情況都是不可預(yù)期的，所以這個(gè)方法并不能簡(jiǎn)單的實(shí)現(xiàn)，什么？停機(jī)拷數(shù)據(jù)？別逗了。但這個(gè)思路給了我們一個(gè)啟示。

我們需要的是一個(gè)狀態(tài)機(jī)的鏡像數(shù)據(jù)，這個(gè)數(shù)據(jù)在我們需要去拷貝的時(shí)候是可以隨時(shí)停止寫入的，那么只要有了這個(gè)鏡像數(shù)據(jù)，就可以刪除Paxos log了。 

Checkpoint

這個(gè)狀態(tài)機(jī)的鏡像數(shù)據(jù)就稱為Checkpoint。如何去生成Checkpoint，一個(gè)狀態(tài)機(jī)能在不停寫的情況下生成一個(gè)鏡像數(shù)據(jù)么？答案是不確定的，看你要實(shí)現(xiàn)的狀態(tài)機(jī)是什么，有的或許可以并很容易，有的可以但很難，有得可能根本無法實(shí)現(xiàn)。那這個(gè)問題又拋回給Paxos庫了，我要想辦法去給他生成一個(gè)鏡像數(shù)據(jù)，并且由我控制。

一個(gè)狀態(tài)機(jī)能構(gòu)建出一份狀態(tài)數(shù)據(jù)，那么搞一個(gè)鏡像狀態(tài)機(jī)就可以同樣構(gòu)建出一份鏡像狀態(tài)數(shù)據(jù)了。

如上圖，用兩個(gè)狀態(tài)轉(zhuǎn)移完全一致的狀態(tài)機(jī)，分別管理不同的狀態(tài)數(shù)據(jù)，通過灌入相同的Paxos log，最終出來的狀態(tài)數(shù)據(jù)是完全一致的。

在真正生產(chǎn)級(jí)的Paxos庫里面，這個(gè)特性太為重要了。我們實(shí)際實(shí)現(xiàn)通過一個(gè)異步線程來構(gòu)建這個(gè)鏡像數(shù)據(jù)，而當(dāng)發(fā)現(xiàn)其他機(jī)器需要獲取這份數(shù)據(jù)的時(shí)候，可以很輕易地停止線程的工作，使得這份數(shù)據(jù)不再寫入。最后發(fā)送給別的機(jī)器使用。

在目前的實(shí)現(xiàn)版本，我們真正做到了刪Paxos log，新機(jī)啟動(dòng)獲取Checkpoint，數(shù)據(jù)對(duì)齊的完全自動(dòng)化。也就是說，首先程序會(huì)根據(jù)磁盤使用情況自動(dòng)刪除Paxos log，其次，程序自動(dòng)的通過鏡像狀態(tài)機(jī)生成Checkpoint，最后，當(dāng)一個(gè)新機(jī)器啟動(dòng)的時(shí)候，可以自動(dòng)的獲取到Checkpoint，然后通過Learner自動(dòng)的對(duì)齊剩下的數(shù)據(jù)，從而自動(dòng)的完成無人工介入的機(jī)器更換。

正確性保證

分布式算法是很難在工程上去驗(yàn)證他的正確性的，我們只能在工程上利用各種手段去接近正確，這里包括了運(yùn)行前的測(cè)試，運(yùn)行中的對(duì)賬，拜占庭問題的細(xì)化解決。

模擬異步通信環(huán)境

我們對(duì)算法內(nèi)核的構(gòu)建過程中，使用了內(nèi)存隊(duì)列來模擬網(wǎng)絡(luò)通信，使用一個(gè)進(jìn)程來模擬一個(gè)機(jī)器。進(jìn)程通過內(nèi)存隊(duì)列來通信。我們對(duì)內(nèi)存隊(duì)列加以修改，使其支持出隊(duì)的延遲，丟失，以及亂序，使得整個(gè)通信過程能按我們配置的方式來運(yùn)行。我們通過配置不同的丟失率，延遲時(shí)間，以及亂序程度，驗(yàn)證不同參數(shù)構(gòu)造的環(huán)境下，Paxos的工作效果以及一致性是否得到保證。而我們通過鉤子將進(jìn)程頻繁殺掉重啟，以及寫盤方面的控制，模擬機(jī)器當(dāng)機(jī)重啟。

運(yùn)行時(shí)對(duì)賬

采用crc32算法，對(duì)有序的多個(gè)值進(jìn)行累加校驗(yàn)，得到一個(gè)當(dāng)前數(shù)據(jù)版本的校驗(yàn)值，通過不斷的在運(yùn)行過程中比對(duì)每個(gè)當(dāng)前編號(hào)實(shí)例對(duì)應(yīng)的累加數(shù)據(jù)校驗(yàn)值，一旦發(fā)現(xiàn)機(jī)器間校驗(yàn)值不相同，則進(jìn)行core的處理，防止錯(cuò)誤繼續(xù)擴(kuò)散。

防止拜占庭問題

對(duì)于所有磁盤寫入的數(shù)據(jù)，都需要進(jìn)行二次校驗(yàn)，防止磁盤數(shù)據(jù)被串改。在發(fā)現(xiàn)數(shù)據(jù)被串改后，能及時(shí)的回滾到上一個(gè)校驗(yàn)成功的數(shù)據(jù)，并產(chǎn)生報(bào)警。

小結(jié)

這里還有更多有意思的優(yōu)化和更為細(xì)節(jié)的問題，由于篇幅問題，就先不做探討了。相信大家也發(fā)現(xiàn)了，本文通篇都在說確定一個(gè)值，確定一個(gè)值，但就沒說到底怎么去確定一個(gè)值。如果你覺得本文對(duì)你有啟發(fā)，那就去找下論文研究一下Paxos到底是怎么確定一個(gè)值的吧。

老司機(jī)簡(jiǎn)介

lynncui，微信后臺(tái)高級(jí)工程師，負(fù)責(zé)朋友圈架構(gòu)設(shè)計(jì)，參與微信后臺(tái)全球化部署的架構(gòu)設(shè)計(jì)以及高性能高可用后臺(tái)核心模塊的開發(fā)。目前正致力于關(guān)系型數(shù)據(jù)庫的可用性以及數(shù)據(jù)一致性提升。PhxPaxos作者之一。