http://www.infoq.com/cn/articles/weinxin-open-source-paxos-phxpaxos
微信重磅開源生產(chǎn)級Paxos類庫PhxPaxos！本文將用科普的口吻向大家介紹PhxPaxos背后的實現(xiàn)原理以及一些有趣的細節(jié)。
本文由微信后臺團隊授權(quán)轉(zhuǎn)載，ID：gh_93b1115dc96f
開源地址：https://github.com/tencent-wechat/phxpaxos
前言
本文通俗易懂，無需任何分布式以及Paxos算法基礎(chǔ)。
三個關(guān)鍵字：“生產(chǎn)級、Paxos、實現(xiàn)”，涵蓋了本文的重點。生產(chǎn)級，就是能用于生產(chǎn)線的、而非實驗產(chǎn)品。生產(chǎn)級別擁有超高的穩(wěn)定性、不錯的性能、能真正服務(wù)于用戶。Paxos，就不用說了。而實現(xiàn)，是本文重點中的重點。本文將避開Paxos算法理論與證明，直接進入實現(xiàn)細節(jié)，告訴大家一個生產(chǎn)級別的Paxos庫背后的樣子。
為何要寫這篇文章？Paxos算法理論與證明不是更重要么？我?guī)啄昵霸?jīng)也讀過Paxos論文，雖然大致理解了算法的過程，但是在腦海中卻無一個場景去構(gòu)建這個算法，而后也就慢慢印象淡化，以至于最近重讀Paxos論文的時候，感覺像是第一次讀論文的樣子。
在真正去實現(xiàn)了Paxos之后，我才明白了這個問題。人們?nèi)ダ斫庖粋€理論或事務(wù)的時候，都會往這個理論或事物上套一個場景，然后在腦海里模擬而試圖去理解。比如經(jīng)典的Dijkstra算法，事實它并不只用于最短尋路，然而在學(xué)習(xí)這個算法的時候，最短尋路給我們提供了一個很好的場景，可以讓我們更快去理解它。
第一次讀Paxos論文，我不知道它的應(yīng)用場景，不知道它是用來干什么的，也不知道它怎么實現(xiàn)，然而這些往往就是一個基礎(chǔ)，大神可能可以自己創(chuàng)造場景，然而更多的人都需要知道這個場景，當(dāng)你知道后，理解算法將變得更為容易。
本文將告訴你Paxos是什么，用來做什么，怎么使用它，如何工程化，如何做到生產(chǎn)級別，以及在工程上會遇到的問題與解決辦法。文中將盡量講課方式的口吻，盡量避免專業(yè)術(shù)語，力求能闡述得更為通俗、簡單易懂。
Paxos簡介
一致性協(xié)議
Paxos是一個一致性協(xié)議。什么叫一致性？一致性有很多種，從強到弱分了很多等級，如線性一致性、因果一致性、最終一致性，等等。什么是一致？這里舉個例子，三臺機器，每臺機器的磁盤存儲為128字節(jié)，如果三臺機器這128字節(jié)數(shù)據(jù)都完全相同，那么可以說這三臺機器是磁盤數(shù)據(jù)是一致的，更為抽象地說，就是多個副本確定同一個值，大家記錄下來同一個值，那么就達到了一致性。
Paxos能達到什么樣的一致性級別？這是一個較為復(fù)雜的問題。因為一致性往往不取決于客觀存在的事實，如3臺機器雖然擁有相同的數(shù)據(jù)，但是數(shù)據(jù)的寫入是一個過程，有時間的先后，而更多的一致性取決于觀察者，觀察者看到的并未是最終的數(shù)據(jù)。這里就先不展開講，先暫且認(rèn)為Paxos保證了寫入的最終一致性。
為何說是一個協(xié)議而不是一個算法，可以這么理解，算法是設(shè)計出來服務(wù)于這個協(xié)議的，如同法律是協(xié)議，那么算法就是各種機構(gòu)的執(zhí)行者，使得法律的約束能得到保證。
Paxos的協(xié)議其實很簡單，就三條規(guī)定。我認(rèn)為這三條規(guī)定也是Paxos最精髓的內(nèi)容，各個執(zhí)行者奮力去保護這個協(xié)議，使得這個協(xié)議的約束生效，自然就得到了一致性。
分布式環(huán)境
為何要設(shè)計出這么一套協(xié)議，其他協(xié)議不行么？如最容易想到的，一個值A(chǔ)，往3臺機器都寫一次，這樣一套簡單的協(xié)議，能不能達到一致性的效果？這里就涉及到另外一個概念，Paxos一致性協(xié)議是在特定的環(huán)境下才需要的，這個特定的環(huán)境稱為異步通信環(huán)境。而恰恰，幾乎所有的分布式環(huán)境都是異步通信環(huán)境，在計算機領(lǐng)域面對的問題，非常需要Paxos來解決。
異步通信環(huán)境指的是消息在網(wǎng)絡(luò)傳輸過程中，可能發(fā)生丟失、延遲、亂序現(xiàn)象。在這種環(huán)境下，上面提到的三寫協(xié)議就變得很雞肋了。消息亂序是一個非常惡劣的問題，這個問題導(dǎo)致大部分協(xié)議在分布式環(huán)境下都無法保證一致性，而導(dǎo)致這個問題的根本原因是網(wǎng)絡(luò)包無法控制超時，一個網(wǎng)絡(luò)包可以在網(wǎng)絡(luò)的各種設(shè)備交換機等停留數(shù)天，甚至數(shù)周之久，而在這段時間內(nèi)任意發(fā)出的一個包，都會跟之前發(fā)出的包產(chǎn)生亂序現(xiàn)象。無法控制超時的原因更多是因為時鐘的關(guān)系，各種設(shè)備以及交換機時鐘都有可能錯亂，無法判斷一個包的真正到達時間。
異步通信環(huán)境并非只有Paxos能解決一致性問題，經(jīng)典的兩階段提交也能達到同樣的效果，但是分布式環(huán)境里面，除了消息網(wǎng)絡(luò)傳輸?shù)膼毫迎h(huán)境，還有另外一個讓人痛心疾首的，就是機器的當(dāng)機，甚至永久失聯(lián)。在這種情況下，兩階段提交將無法完成一個一致性的寫入，而Paxos，只要多數(shù)派機器存活就能完成寫入，并保證一致性。
至此，總結(jié)一下Paxos就是一個在異步通信環(huán)境，并容忍在只有多數(shù)派機器存活的情況下，仍然能完成一個一致性寫入的協(xié)議。
提議者
前面講了這么多都是協(xié)議協(xié)議，在分布式環(huán)境當(dāng)中，協(xié)議作用就是每臺機器都要扮演一個角色，這個角色嚴(yán)格遵守這個協(xié)議去處理消息。在Paxos論文里面這個角色稱之為Acceptor，這個很好理解。大家其實更關(guān)心另外一個問題，到底誰去發(fā)起寫入請求，論文里面介紹發(fā)起寫入請求的角色為提議者，稱為Proposer。Proposer也是嚴(yán)格遵守paxos協(xié)議，通過與各個Acceptor的協(xié)同工作，去完成一個值的寫入。在Paxos里面，Proposer和Acceptor是最重要的兩個角色。
Paxos為誰服務(wù)
確定一個值
既然說到寫入數(shù)據(jù)，到底怎么去寫？寫一次還是寫多次，還是其他？這也是我一開始苦惱的問題，相信很多人都會很苦惱。
這里先要明確一個問題，Paxos到底在為誰服務(wù)？更確定地說，到底在為什么數(shù)據(jù)服務(wù)？還是引上面的例子，Paxos就是為這128字節(jié)的數(shù)據(jù)服務(wù)，Paxos并不關(guān)心外面有多少個提議者，寫入了多少數(shù)據(jù)，寫入的數(shù)據(jù)是不是一樣的，Paxos只會跟你說，我確定了一個值，當(dāng)這個值被確定之后，也就是這128字節(jié)被確定了之后，無論外面寫入什么，這個值都不會改變再改變了，而且三臺機確定的值肯定是一樣的。
說到這估計肯定會有人懵了，說實話我當(dāng)時也懵了。我要實現(xiàn)一個存儲服務(wù)啊，我要寫入各種各樣的數(shù)據(jù)啊，你給我確定這么一個值，能有啥用？但先拋開這些疑問，大家先要明確這么一個概念，Paxos就是用來確定一個值用的，而且大家這里就先知道這么個事情就可以了，具體Paxos協(xié)議是怎樣的，怎么通過協(xié)議里面三條規(guī)定來獲得這樣的效果的，怎么證明的等等理論上的東西，都推薦去大家去看看論文，但是先看完本文再看，會得到另外的效果。
如下圖，有三臺機器（后面為了簡化問題，不做特別說明都是以三臺機器作為講解例子），每臺機器上運行這Acceptor來遵守paxos協(xié)議，每臺機器的Acceptor為自己的一份Data數(shù)據(jù)服務(wù)，可以有任意多個Proposer。當(dāng)Paxos協(xié)議宣稱一個值被確定（Chosen）后，那么Data數(shù)據(jù)就會被確定，并且永遠不會被改變。
Proposer只需要與多數(shù)派的Acceptor交互，即可完成一個值的確定，但一旦這個值被確定下來后，無論Proposer再發(fā)起任何值的寫入，Data數(shù)據(jù)都不會再被修改。Chosen value即是被確定的值，永遠不會被修改。
確定多個值
對我們來說，確定一個值，并且當(dāng)一個值確定后是永遠不能被修改的，很明顯這個應(yīng)用價值是很低的。雖然我都甚至還不知道確定一個值能用來干嘛，但如果我們能有辦法能確定很多個值，那肯定會比一個值有用得多。我們先來看下怎么去確定多個值。
上文提到一個三個Acceptor和Proposer各自遵守paxos協(xié)議，協(xié)同工作最終完成一個值的確定。這里先定義一個概念，Proposer，各個Acceptor，所服務(wù)的Data共同構(gòu)成了一個大的集合，這個集合所運行的paxos算法最終目標(biāo)是確定一個值，我們這里稱這個集合為一個Paxos實例。
一個實例可以確定一個值，那么多個實例自然可以確定多個值，很簡單的模型就可以構(gòu)建出來，只要我們同時運行著多個實例，那么我們就能完成確定多個值的目標(biāo)。
這里強調(diào)一點，每個實例必須是完全獨立，互不干涉的。意思就是說Acceptor不能去修改其他實例的Data數(shù)據(jù)，Proposer同樣也不能跨越實例去與其他實例的Acceptor交互。
如下圖，三臺機器每臺機器運行兩個實例，每個實例獨立運作，最終會產(chǎn)生兩個確定的值。這里兩個實際可以擴展成任意多個。
至此，實例成為了我現(xiàn)在介紹Paxos的一個基本單元，一個實例確定一個值，多個實例確定多個值，但各個實例獨立，互不干涉。
然而比較遺憾的一點，確定多個值，仍然對我們沒有太大的幫助，因為里面最可恨的一點是，當(dāng)一個值被確定后，就永遠無法被修改了，這是我們不能接受的。大部分的存儲服務(wù)可能都需要有一個修改的功能。
有序確定多個值
我們需要轉(zhuǎn)換一下切入點，也許我們需要Paxos確定的值，并不一定是我們真正看到的數(shù)據(jù)。我們觀察大部分存儲系統(tǒng)，如LevelDB，都是以AppendLog的形式，確定一個操作系列，而后需要恢復(fù)存儲的時候都可以通過這個操作系列來恢復(fù)，而這個操作系列，正是確定之后就永遠不會被修改的。到這已經(jīng)很豁然開朗了，只要我們通過Paxos完成一個多機一致的有序的操作系列，那么通過這個操作系列的演進，可實現(xiàn)的東西就很有想象空間了，存儲服務(wù)必然不是問題。
如何利用Paxos有序的確定多個值？上文我們知道可以通過運行多個實例來完成確定多個值，但為了達到順序的效果，需要加強一下約束。
首先給實例一個編號，定義為i，i從0開始，只增不減，由本機器生成，不依賴網(wǎng)絡(luò)。其次，我們保證一臺機器任一時刻只能有一個實例在工作，這時候Proposer往該機器的寫請求都會被當(dāng)前工作的實例受理。最后，當(dāng)編號為i的實例獲知已經(jīng)確定好一個值之后，這個實例將會被銷毀，進而產(chǎn)生一個編號為i+1的實例。
基于這三個約束，每臺機器的多個實例都是一個連續(xù)遞增編號的有序系列，而基于Paxos的保證，同一個編號的實例，確定的值都是一致的，那么三臺機都獲得了一個有序的多個值。
下面結(jié)合一個圖來詳細說明一下這個運作過程，以及存在什么異常情況以及異常情況下的處理方式。
圖中A，B，C代表三個機器，紅色代表已經(jīng)被銷毀的實例，根據(jù)上文約束，最大的實例就是當(dāng)前正在工作的實例。A機器當(dāng)前工作的實例編號是6，B機是5，而C機是3。為何會出現(xiàn)這種工作實例不一樣的情況？首先解釋一下C機的情況，由于Paxos只要求多數(shù)派存活即可完成一個值的確定，所以假設(shè)C出現(xiàn)當(dāng)機或者消息丟失延遲等，都會使得自己不知道3-5編號的實例已經(jīng)被確定好值了。而B機比A機落后一個實例，是因為B機剛剛參與完成實例5的值的確定，但是他并不知道這個值被確定了。上面的情況與其說是異常情況，也可以說是正常的情況，因為在分布式環(huán)境，發(fā)生這種事情是很正常的。
下面分析一下基于圖示狀態(tài)的對于C機的寫入是如何工作的。C機實例3處理一個新的寫入，根據(jù)Paxos協(xié)議的保證，由于實例3已經(jīng)確定好一個值了，所以無論寫入什么值，都不會改變原來的值，所以這時候C機實例3發(fā)起一輪Paxos算法的時候就可以獲知實例3真正確定的值，從而跳到實例4。但在工程實現(xiàn)上這個事情可以更為簡化，上文提到，各個實例是獨立，互不干涉的，也就是A機的實例6，B機的實例5都不會去理會C機實例3發(fā)出的消息，那么C機實例3這個寫入是無法得到多數(shù)派響應(yīng)的，自然無法寫入成功。
再分析一下A機的寫入，同樣實例6無法獲得多數(shù)派的響應(yīng)，同樣無法寫入成功。同樣假如B機實例5有寫入，也是寫入失敗的結(jié)果，那如何使得能繼續(xù)寫入，實例編號能繼續(xù)增長呢？這里引出下一個章節(jié)。
實例的對齊（Learn）
上文說到每個實例里面都有一個Acceptor的角色，這里再增加一個角色稱為Learner，顧名思義就是找別人學(xué)習(xí)，她回去詢問別的機器的相同編號的實例，如果這個實例已經(jīng)被銷毀了，那說明值已經(jīng)確定好了，直接把這個值拉回來寫到當(dāng)前實例里面，然后編號增長跳到下一個實例再繼續(xù)詢問，如此反復(fù)，直到當(dāng)前實例編號增長到與其他機器一致。
由于約束里面保證僅當(dāng)一個實例獲知到一個確定的值之后，才能編號增長開始新的實例，那么換句話說，只要編號比當(dāng)前工作實例小的實例（已銷毀的），他的值都是已經(jīng)確定好的。所以這些值并不需要再通過Paxos來確定了，而是直接由Learner直接學(xué)習(xí)得到即可。
如上圖所示，B機的實例5是直接由Learner從A機學(xué)到的，而C機的實例3-5都是從B機學(xué)到的，這樣大家就全部走到了實例6，這時候?qū)嵗?接受的寫請求就能繼續(xù)工作下去。
Paxos如何應(yīng)用
狀態(tài)機
一個有序的確定的值，也就是日志，可以通過定義日志的語義進行重放的操作，那么這個日志是怎么跟Paxos結(jié)合起來的呢？我們利用Paxos確定有序的多個值這個特點，再加上這里引入的一個狀態(tài)機的概念，結(jié)合起來實現(xiàn)一個真正有工程意義的系統(tǒng)。
狀態(tài)機這個名詞大家都不陌生，一個狀態(tài)機必然涉及到一個狀態(tài)轉(zhuǎn)移，而Paxos的每個實例，就是狀態(tài)轉(zhuǎn)移的輸入，由于每臺機器的實例編號都是連續(xù)有序增長的，而每個實例確定的值是一樣的，那么可以保證的是，各臺機器的狀態(tài)機輸入是完全一致的。根據(jù)狀態(tài)機的理論，只要初始狀態(tài)一致，輸入一致，那么引出的最終狀態(tài)也是一致的。而這個狀態(tài)，是有無限的想象空間，你可以用來實現(xiàn)非常多的東西。
如下圖這個例子是一個狀態(tài)機結(jié)合Paxos實現(xiàn)了一個具有多機一致的KV系統(tǒng)。
實例0-3的值都已經(jīng)被確定，通過這4個值最終引出(b, ‘jeremy’)這個狀態(tài)，而各臺機器實例系列都是一致的，所以大家的狀態(tài)都一樣，雖然引出狀態(tài)的時間有先后，但確定的實例系列確定的值引出確定的狀態(tài)。
下圖例子告訴大家Proposer，Acceptor，Learner，State machine是如何協(xié)同工作的。
一個請求發(fā)給Proposer，Proposer與相同實例編號為x的Acceptor協(xié)同工作，共同完成一值的確定，之后將這個值作為狀態(tài)機的輸入，產(chǎn)生狀態(tài)轉(zhuǎn)移，最終返回狀態(tài)轉(zhuǎn)移結(jié)果給發(fā)起請求者。
Paxos工程化
多角色盡量在一起
上文提到一個實例，需要有Proposer和Acceptor兩個角色協(xié)同工作，另外還要加以Learner進行輔助，到了應(yīng)用方面又加入了State machine，這里面勢必會有很多狀態(tài)需要共享。如一個Proposer必須于Acceptor處于相同的實例才能工作，那么Proposer也就必須知道當(dāng)前工作的實例是什么，又如State machine必須知道實例的Chosen value是啥，而Chosen value是存儲于Acceptor管理的Data數(shù)據(jù)中的。在概念上，這些角色可以通過任意的通信方式進行狀態(tài)共享，但真正去實現(xiàn)，我們都會盡量基于簡單、高性能出發(fā)，一般都會將這些角色同時融合在一個機器、一個進程里面。
下圖例子是一個工程上比較常規(guī)的實現(xiàn)方式。
這里提出一個新的概念，這里三臺機器，每臺機器運行著相同的實例i，實例里整合了Acceptor，Proposer，Learner，State machine四個角色，三臺機器的相同編號實例共同構(gòu)成了一個Paxos group的概念，一個請求只需要灌進Paxos group里面就可以了，根據(jù)Paxos的特點，Paxos group可以將這個請求可以隨意寫往任意一個Proposer，由Proposer來進行提交。Paxos group是一個虛設(shè)的概念，只是為了方便解釋，事實上是請求隨意丟到三臺機任意一個Proposer就可以了。
那么具體這四個角色是如何工作的呢。首先，由于Acceptor和Proposer在同一個進程里面，那么保證它們處于同一個實例是很簡單的事情。其次，當(dāng)一個值被確認(rèn)之后，也可以很方便傳送給State machine去進行狀態(tài)的轉(zhuǎn)移。最后當(dāng)出現(xiàn)異常狀態(tài)，實例落后或者收不到其他機器的回應(yīng)，剩下的事情就交給Learner去解決，就這樣一整合，事情就變得簡單了。
嚴(yán)格的落盤
Paxos協(xié)議的運作工程需要做出很多保證，即保證了在相同的條件下一定會做出相同的處理，如何能完成這些保證？眾所周知，在計算機里面，一個線程、進程，甚至機器都可能隨時掛掉，而當(dāng)他再次啟動的時候，磁盤是他恢復(fù)記憶的方法，在Paxos協(xié)議運作里面也一樣，磁盤是她記錄下這些保證條目的介質(zhì)。
而一般的磁盤寫入是有緩沖區(qū)的，當(dāng)機器當(dāng)機，這些緩沖區(qū)仍然未刷到磁盤，那么就會丟失部分?jǐn)?shù)據(jù)，導(dǎo)致保證失效，所以在Paxos做出這些保證的時候，落盤一定要非常嚴(yán)格，嚴(yán)格的意思是當(dāng)操作系統(tǒng)告訴我寫盤成功，那么無論任何情況都不會丟失。這個我們一般使用fsync來解決問題，也就是每次進行寫盤都要附加一個fsync進行保證。
Fsync是一個非常重的操作，也因為這個，Paxos最大的瓶頸也是在寫盤上，在工程上，我們需要盡量通過各種手段，去減少Paxos算法所需要的寫盤次數(shù)。
萬一磁盤fsync之后，仍然丟失或者數(shù)據(jù)錯亂怎么辦？這個稱之為拜占庭問題，工程上需要一系列的措施檢測出這些拜占庭錯誤，然后選擇性的進行數(shù)據(jù)回滾或者直接丟棄。
一個Leader
由于看這篇文章的讀者未必知道Paxos理論上是如何去確定一個值的，這里簡單說明一下，Paxos一個實例，支持任意多個Proposer同時進行寫入，但是最終確定出來一個相同的值，里面是運用了一些類似鎖的方法來解決沖突的，而越多的Proposer進行同時寫入，沖突的劇烈程度會更高，雖然完全不妨礙最終會確定一個值，但是性能上是比較差的。所以這里需要引入一個Leader的概念。
Leader就是領(lǐng)導(dǎo)者的意思，顧名思義我們希望有一個Proposer的領(lǐng)導(dǎo)者，優(yōu)先由他來進行寫入，那么當(dāng)在只有一個Proposer在進行寫入的情況下，沖突的概率是極小的，這樣性能會得到一個飛躍。這里再次重申一下，Leader的引入，不是為了解決一致性問題，而是為了解決性能問題。
由于Leader解決的是性能問題而非一致性問題，即使Leader出錯也不會妨礙正確性，所以我們只需要保證大部分情況下只有一個Proposer在工作就行了，而不用去保證絕對的不允許出現(xiàn)兩個Proposer或以上同時工作，那么這個通過一些簡單的心跳以及租約就可以做到，實現(xiàn)也是非常簡單，這里就不展開解釋。
狀態(tài)機記錄最大實例編號
狀態(tài)機可以是任何東西，可以是kv，可以是mysql的binlog，在Paxos實例運行時，我們可以保證時刻與狀態(tài)機同步。這里同步的意思是指狀態(tài)機輸入到的實例的最大編號和Paxos運行當(dāng)中認(rèn)為已經(jīng)確認(rèn)好值的實例最大編號是一樣的，因為當(dāng)一個實例已經(jīng)完成值的確認(rèn)之后，我們必須確保已經(jīng)輸入到狀態(tài)機并且進行了狀態(tài)轉(zhuǎn)移，之后我們才能開啟新的實例。但，當(dāng)機器重啟或者進程重啟之后，狀態(tài)機的數(shù)據(jù)可能會由于自身實現(xiàn)問題，或者磁盤數(shù)據(jù)丟失而導(dǎo)致回滾，這個我們沒辦法像上文提到的fsync一樣進行這么強的約束，所以提出了一種方法，狀態(tài)機必須嚴(yán)格記得自己輸入過的最大實例編號。
這個記錄有什么用？在每次啟動的時候，狀態(tài)機告訴Paxos最大的實例編號x，而Paxos發(fā)現(xiàn)自己最大的已確定值的實例編號是y，而x < y. 那這時候怎么辦，只要有(x, y]的Chosen value，我們重新把這些value一個一個輸入到狀態(tài)機，那么狀態(tài)機的狀態(tài)就會更新到y(tǒng)了，這個稱為啟動重放。
這樣對狀態(tài)機的要求將盡量簡單，只需要嚴(yán)格的記錄好這么一個編號就可以了。當(dāng)然不記錄，每次從0開始也可以，但這樣Paxos需要從0開始重放，是一個蠢方法。
異步消息處理模型
上文說到分布式環(huán)境是一個異步通信環(huán)境，而Paxos解決了基于這種環(huán)境下的一致性問題，那么一個顯而易見的特點就是，我們不知道也不確定消息何時到達，是否有序到達，是否到達，我們只需要去遵守Paxos協(xié)議，嚴(yán)格的處理每一條到達的消息即可，這跟RPC模型比較不一樣，Paxos的特點是有去無回。
這里先定義一個名詞叫Paxos消息，這里指的是Paxos為了去確定一個值，算法運行過程中需要的通信產(chǎn)生的消息。下圖通過一個異步消息處理模型去構(gòu)建一個響應(yīng)Paxos消息系統(tǒng)，從而完成Paxos系統(tǒng)的搭建。
這里分為四個部分：
- Request，即外部請求，這個請求直接輸入到Proposer里面，由Proposer嘗試完成一個值的確定。
- Network i/o，網(wǎng)絡(luò)i/o處理，負(fù)責(zé)paxos內(nèi)部產(chǎn)生的消息的發(fā)送與接收，并且只處理Paxos消息，采用私有端口，純異步，各臺機器之前的network i/o模塊互相通信。
- Acceptor，Proposer，Learner。用于響應(yīng)并處理Paxos消息。
- State machine，狀態(tài)機，實例確定的值(Chosen value)的應(yīng)用者。
工作流程如下：
- 收到Request，由Proposer處理，如需要發(fā)送Paxos消息，則通過network i/o發(fā)送。
- Net work i/o收到Paxos消息，根據(jù)消息類型選擇Acceptor，Proposer，或Leaner處理，如處理后需要發(fā)送Paxos消息，則通過network i/o發(fā)送。
- Proposer通過paxos消息獲知Chosen value，則輸入value到State machine完成狀態(tài)轉(zhuǎn)移，最終通知Request轉(zhuǎn)移結(jié)果，完成一個請求的處理。
- 當(dāng)Paxos完成一個值的確認(rèn)之后，所有當(dāng)前實例相關(guān)角色狀態(tài)進行清空并初始化進行下一個編號的實例。
生產(chǎn)級Paxos庫
RTT與寫盤次數(shù)的優(yōu)化
雖然經(jīng)過在工程化上做的諸多要求，可以實現(xiàn)出一個基于Paxos搭建的，可掛載任意狀態(tài)機，并且能穩(wěn)定運行的系統(tǒng)，但性能遠遠不夠。在性能方面需要進行優(yōu)化，方能上崗。由于上文并未對Paxos理論做介紹，這里大概說明一下樸素的Paxos算法，確定一個值，在無沖突的情況下，需要兩個RTT，以及每臺機器的三次寫盤。這個性能想象一下在我們在線服務(wù)是非常慘烈的。為了達到生產(chǎn)級，最終我們將這個優(yōu)化成了一個RTT以及每臺機器的一次寫盤。(2,3)優(yōu)化到(1,1)，使得我們能真正在線上站穩(wěn)腳跟。但由于本文的重點仍然不在理論，這里具體優(yōu)化手段就暫不多做解釋。
同時運行多個Paxos group
由于實例運行的方式是確保i實例的銷毀才能運行i+1實例，那么這個請求的執(zhí)行明顯是一個串行的過程，這樣對cpu的利用是比較低的，我們得想辦法將cpu利用率提升上來。
一個Paxos group可以完成一個狀態(tài)機的輸入，但如果一臺機器同時有多個狀態(tài)機呢？比如可以同時利用Paxos實現(xiàn)兩種業(yè)務(wù)，每個業(yè)務(wù)對應(yīng)一個狀態(tài)機，互不關(guān)聯(lián)。那么一個Paxos group分配一個端口，我們即可在一臺機器上運行多個Paxos group，各自端口不同，互相獨立。那么cpu利用率將能大幅提升。
比如想實現(xiàn)一個分布式的kv，那么對于一臺機器服務(wù)的key段，我們可以再在里面分割成多個key段，那每個小key段就是一個獨立的狀態(tài)機，每個狀態(tài)機搭配一個獨立Paxos group即可完成同時運行。
但一臺機器搞幾十個，幾百個端口也是比較齷齪的手法，所以我們在生產(chǎn)級的Paxos庫上，實現(xiàn)了基于一個network i/o搭配多組Paxos group的結(jié)構(gòu)。
如上圖，每個group里面都有完整的Paxos邏輯，只需要給Paxos消息增加一個group的標(biāo)識，通過network i/o的處理，將不同group的消息輸送到對應(yīng)的group里面處理。這樣我們一臺機器只需要一個私有端口，即可完成多個狀態(tài)機的并行處理。
至此可以獲得一個多個Paxos group的系統(tǒng)，完整結(jié)構(gòu)如下：
更快對齊數(shù)據(jù)
上文說到當(dāng)各臺機器的當(dāng)前運行實例編號不一致的時候，就需要Learner介入工作來對齊數(shù)據(jù)了。Learner通過其他機器拉取到當(dāng)前實例的Chosen value，從而跳轉(zhuǎn)到下一編號的實例，如此反復(fù)最終將自己的實例編號更新到與其他機器一致。那么這里學(xué)習(xí)一個實例的網(wǎng)絡(luò)延時代價是一個RTT。可能這個延遲看起來還不錯，但是當(dāng)新的數(shù)據(jù)仍然通過一個RTT的代價不斷寫入的時候，而落后的機器仍然以一個RTT來進行學(xué)習(xí)，這樣會出現(xiàn)很難追上的情況。
這里需要改進，我們可以提前獲取差距，批量打包進行學(xué)習(xí)，比如A機器Learner記錄當(dāng)前實例編號是x，B機器是y，而x < y，那么B機器通過通信獲取這個差距，將(x,y]的Chosen value一起打包發(fā)送給A機器，A機器進行批量的學(xué)習(xí)。這是一個很不錯的方法。
但仍然不夠快，當(dāng)落后的數(shù)據(jù)極大，B機器發(fā)送數(shù)據(jù)需要的網(wǎng)絡(luò)耗時也將變大，那么發(fā)送數(shù)據(jù)的過程中，A機器處于一種空閑狀態(tài)，由于Paxos另外一個瓶頸在于寫盤，如果不能利用這段時間來進行寫盤，那性能仍然堪憂。我們參考流式傳輸，采用類似的方法實現(xiàn)Learner的邊發(fā)邊學(xué)，B機器源源不斷的往A機器輸送數(shù)據(jù)，而A機器只需要收到一個實例最小單元的包體，即可立即解開進行學(xué)習(xí)并完成寫盤。
具體的實現(xiàn)大概是先進行一對一的協(xié)商，建立一個Session通道，在Session通道里直接采用直塞的方式無腦發(fā)送數(shù)據(jù)。當(dāng)然也不是完全的無腦，Session通過心跳機制進行維護，一旦Session斷開即停止發(fā)送。
刪除Paxos數(shù)據(jù)
Paxos數(shù)據(jù)，即通過Paxos確認(rèn)下來的有序的多個值，后面我們稱這個為Paxos log，這些log作為狀態(tài)機的輸入，是源源不斷的。狀態(tài)機的狀態(tài)是有限的，但輸入是無限的，但磁盤的空間又是有限的，所以輸入必然不能長期保留，我們必須找到方法來把它刪除。
上文說到要求狀態(tài)機記錄下來輸入過的最大實例編號，這里定義為Imax，那么每次啟動的時候是從這個編號后開始重放Paxos log，也就是說小于等于這個編號Imax數(shù)據(jù)是沒用的了，它不會再次使用，可以直接刪除掉。但這個想法不夠周全，因為Paxos是允許少于多數(shù)派的機器掛掉的，這個掛掉可能是機器永遠離線。而這種情況我們一般是用一臺新的機器代替。這臺新的機器要干什么？他要從0開始重放Paxos log，而這些Paxos log從哪里來？肯定是Learner找別的機器拷貝過來的。那別的機器刪了怎么辦？涼拌。
但也并不是沒辦法了，我可以把這臺機狀態(tài)機相關(guān)的數(shù)據(jù)全部拷貝到新機，然后就可以從Imax來啟動了，那么自然就不需要[0,Imax]的Paxos log了。但是狀態(tài)機的數(shù)據(jù)是無時無刻不在寫入的，一個正在寫入的數(shù)據(jù)去拷貝出來，出現(xiàn)什么情況都是不可預(yù)期的，所以這個方法并不能簡單的實現(xiàn)，什么？停機拷數(shù)據(jù)？別逗了。但這個思路給了我們一個啟示。
我們需要的是一個狀態(tài)機的鏡像數(shù)據(jù)，這個數(shù)據(jù)在我們需要去拷貝的時候是可以隨時停止寫入的，那么只要有了這個鏡像數(shù)據(jù)，就可以刪除Paxos log了。
Checkpoint
這個狀態(tài)機的鏡像數(shù)據(jù)就稱為Checkpoint。如何去生成Checkpoint，一個狀態(tài)機能在不停寫的情況下生成一個鏡像數(shù)據(jù)么？答案是不確定的，看你要實現(xiàn)的狀態(tài)機是什么，有的或許可以并很容易，有的可以但很難，有得可能根本無法實現(xiàn)。那這個問題又拋回給Paxos庫了，我要想辦法去給他生成一個鏡像數(shù)據(jù)，并且由我控制。
一個狀態(tài)機能構(gòu)建出一份狀態(tài)數(shù)據(jù)，那么搞一個鏡像狀態(tài)機就可以同樣構(gòu)建出一份鏡像狀態(tài)數(shù)據(jù)了。
如上圖，用兩個狀態(tài)轉(zhuǎn)移完全一致的狀態(tài)機，分別管理不同的狀態(tài)數(shù)據(jù)，通過灌入相同的Paxos log，最終出來的狀態(tài)數(shù)據(jù)是完全一致的。
在真正生產(chǎn)級的Paxos庫里面，這個特性太為重要了。我們實際實現(xiàn)通過一個異步線程來構(gòu)建這個鏡像數(shù)據(jù)，而當(dāng)發(fā)現(xiàn)其他機器需要獲取這份數(shù)據(jù)的時候，可以很輕易地停止線程的工作，使得這份數(shù)據(jù)不再寫入。最后發(fā)送給別的機器使用。
在目前的實現(xiàn)版本，我們真正做到了刪Paxos log，新機啟動獲取Checkpoint，數(shù)據(jù)對齊的完全自動化。也就是說，首先程序會根據(jù)磁盤使用情況自動刪除Paxos log，其次，程序自動的通過鏡像狀態(tài)機生成Checkpoint，最后，當(dāng)一個新機器啟動的時候，可以自動的獲取到Checkpoint，然后通過Learner自動的對齊剩下的數(shù)據(jù)，從而自動的完成無人工介入的機器更換。
正確性保證
分布式算法是很難在工程上去驗證他的正確性的，我們只能在工程上利用各種手段去接近正確，這里包括了運行前的測試，運行中的對賬，拜占庭問題的細化解決。
模擬異步通信環(huán)境
我們對算法內(nèi)核的構(gòu)建過程中，使用了內(nèi)存隊列來模擬網(wǎng)絡(luò)通信，使用一個進程來模擬一個機器。進程通過內(nèi)存隊列來通信。我們對內(nèi)存隊列加以修改，使其支持出隊的延遲，丟失，以及亂序，使得整個通信過程能按我們配置的方式來運行。我們通過配置不同的丟失率，延遲時間，以及亂序程度，驗證不同參數(shù)構(gòu)造的環(huán)境下，Paxos的工作效果以及一致性是否得到保證。而我們通過鉤子將進程頻繁殺掉重啟，以及寫盤方面的控制，模擬機器當(dāng)機重啟。
運行時對賬
采用crc32算法，對有序的多個值進行累加校驗，得到一個當(dāng)前數(shù)據(jù)版本的校驗值，通過不斷的在運行過程中比對每個當(dāng)前編號實例對應(yīng)的累加數(shù)據(jù)校驗值，一旦發(fā)現(xiàn)機器間校驗值不相同，則進行core的處理，防止錯誤繼續(xù)擴散。
防止拜占庭問題
對于所有磁盤寫入的數(shù)據(jù)，都需要進行二次校驗，防止磁盤數(shù)據(jù)被串改。在發(fā)現(xiàn)數(shù)據(jù)被串改后，能及時的回滾到上一個校驗成功的數(shù)據(jù)，并產(chǎn)生報警。
小結(jié)
這里還有更多有意思的優(yōu)化和更為細節(jié)的問題，由于篇幅問題，就先不做探討了。相信大家也發(fā)現(xiàn)了，本文通篇都在說確定一個值，確定一個值，但就沒說到底怎么去確定一個值。如果你覺得本文對你有啟發(fā)，那就去找下論文研究一下Paxos到底是怎么確定一個值的吧。
老司機簡介
lynncui，微信后臺高級工程師，負(fù)責(zé)朋友圈架構(gòu)設(shè)計，參與微信后臺全球化部署的架構(gòu)設(shè)計以及高性能高可用后臺核心模塊的開發(fā)。目前正致力于關(guān)系型數(shù)據(jù)庫的可用性以及數(shù)據(jù)一致性提升。PhxPaxos作者之一。