跟着微信后台团队学习分布式一致性协议
目錄
什么是Paxos
一致性協(xié)議
分布式環(huán)境
提議者
Paxos是用來干什么的
確定一個值
確定多個值
有序的確定多個值
實例的對齊(Learn)
如何應(yīng)用Paxos
狀態(tài)機
工程化
我們需要多個角色盡量在一起
我們需要嚴(yán)格的落盤
我們需要一個Leader
我們需要狀態(tài)機記錄下來輸入過的最大實例編號
異步消息處理模型
生產(chǎn)級的Paxos庫
RTT與寫盤次數(shù)的優(yōu)化
同時運行多個paxos?group
更快的對齊數(shù)據(jù)
如何刪除Paxos數(shù)據(jù)
Checkpoint
微信自研生產(chǎn)級paxos類庫PhxPaxos實現(xiàn)原理介紹
前言
本文是一篇無需任何分布式以及paxos算法基礎(chǔ)的人可以看懂的(這句話是騙人的)。微信重磅開源生產(chǎn)級paxos類庫PhxPaxos，本文用科普的口吻向大家介紹PhxPaxos背后的實現(xiàn)原理以及一些有意思的細(xì)節(jié)。
開源地址：https://github.com/tencent-wechat/phxpaxos
原文地址：https://mp.weixin.qq.com/s__biz=MzI4NDMyNTU2Mw==&mid=2247483695&idx=1&sn=91ea422913fc62579e020e941d1d059e#rd
標(biāo)題主要有三個關(guān)鍵字，生產(chǎn)級，paxos，實現(xiàn)，涵蓋了本文的重點。什么叫生產(chǎn)級，直譯就是能用于生產(chǎn)線的，而非實驗產(chǎn)品。生產(chǎn)級別擁有超高的穩(wěn)定性，不錯的性能，能真正服務(wù)于用戶的。paxos就不用說了，而實現(xiàn)，是本文最大的重點，本文將避開paxos算法理論與證明，直入實現(xiàn)細(xì)節(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ù)是一致的，更為抽象的說，就是多個副本確定同一個值，大家記錄下來同一個值，那么就達(dá)到了一致性。
Paxos能達(dá)到什么樣的一致性級別？這是一個較為復(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í)行者奮力的去保護(hù)這個協(xié)議，使得這個協(xié)議的約束生效，自然就得到了一致性。?
?
分布式環(huán)境
為何要設(shè)計出這么一套協(xié)議，其他協(xié)議不行么。如最容易想到的，一個值A(chǔ)，往3臺機器都寫一次，這樣一套簡單的協(xié)議，能不能達(dá)到一致性的效果？這里就涉及到另外一個概念，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è)備以及交換機時鐘都有可能錯亂，無法判斷一個包的真正到達(dá)時間。
異步通信環(huán)境并非只有paxos能解決一致性問題，經(jīng)典的兩階段提交也能達(dá)到同樣的效果，但是分布式環(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是用來干什么的
確定一個值
既然說到寫入數(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ù)就會被確定，并且永遠(yuǎn)不會被改變。
Proposer只需要與多數(shù)派的Acceptor交互，即可完成一個值的確定，但一旦這個值被確定下來后，無論Proposer再發(fā)起任何值的寫入，Data數(shù)據(jù)都不會再被修改。Chosen?value即是被確定的值，永遠(yuǎn)不會被修改。
?
確定多個值
對我們來說，確定一個值，并且當(dāng)一個值確定后是永遠(yuǎn)不能被修改的，很明顯這個應(yīng)用價值是很低的。雖然我都甚至還不知道確定一個值能用來干嘛，但如果我們能有辦法能確定很多個值，那肯定會比一個值有用得多。我們先來看下怎么去確定多個值。
上文提到一個三個Acceptor和Proposer各自遵守paxos協(xié)議，協(xié)同工作最終完成一個值的確定。這里先定義一個概念，Proposer，各個Acceptor，所服務(wù)的Data共同構(gòu)成了一個大的集合，這個集合所運行的paxos算法最終目標(biāo)是確定一個值，我們這里稱這個集合為一個paxos?instance，即一個paxos實例。
一個實例可以確定一個值，那么多個實例自然可以確定多個值，很簡單的模型就可以構(gòu)建出來，只要我們同時運行著多個實例，那么我們就能完成確定多個值的目標(biāo)。
這里強調(diào)一點，每個實例必須是完全獨立，互不干涉的。意思就是說Acceptor不能去修改其他實例的Data數(shù)據(jù)，Proposer同樣也不能跨越實例去與其他實例的Acceptor交互。
如下圖，三臺機器每臺機器運行兩個實例，每個實例獨立運作，最終會產(chǎn)生兩個確定的值。這里兩個實際可以擴(kuò)展成任意多個。
至此，實例(Instance)以成為了我現(xiàn)在介紹paxos的一個基本單元，一個實例確定一個值，多個實例確定多個值，但各個實例獨立，互不干涉。
然而比較遺憾的一點，確定多個值，仍然對我們沒有太大的幫助，因為里面最可恨的一點是，當(dāng)一個值被確定后，就永遠(yuǎn)無法被修改了，這是我們不能接受的。大部分的存儲服務(wù)可能都需要有一個修改的功能。?
?
有序的確定多個值
我們需要轉(zhuǎn)換一下切入點，也許我們需要paxos確定的值，并不一定是我們真正看到的數(shù)據(jù)。我們觀察大部分存儲系統(tǒng)，如LevelDB，都是以AppendLog的形式，確定一個操作系列，而后需要恢復(fù)存儲的時候都可以通過這個操作系列來恢復(fù)，而這個操作系列，正是確定之后就永遠(yuǎn)不會被修改的。到這已經(jīng)很豁然開朗了，只要我們通過paxos完成一個多機一致的有序的操作系列，那么通過這個操作系列的演進(jìn)，可實現(xiàn)的東西就很有想象空間了，存儲服務(wù)必然不是問題。
如何利用paxos有序的確定多個值？上文我們知道可以通過運行多個實例來完成確定多個值，但為了達(dá)到順序的效果，需要加強一下約束。
首先給實例一個編號，定義為i，i從0開始，只增不減，由本機器生成，不依賴網(wǎng)絡(luò)。其次，我們保證一臺機器任一時刻只能有一個實例在工作，這時候Proposer往該機器的寫請求都會被當(dāng)前工作的實例受理。最后，當(dāng)編號為i的實例獲知已經(jīng)確定好一個值之后，這個實例將會被銷毀，進(jìn)而產(chǎn)生一個編號為i+1的實例。
基于這三個約束，每臺機器的多個實例都是一個連續(xù)遞增編號的有序系列，而基于paxos的保證，同一個編號的實例，確定的值都是一致的，那么三臺機都獲得了一個有序的多個值。
下面結(jié)合一個圖示來詳細(xì)說明一下這個運作過程以及存在什么異常情況以及異常情況下的處理方式。
圖中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ù)工作下去。?
?
如何應(yīng)用Paxos
狀態(tài)機
一個有序的確定的值，也就是日志，可以通過定義日志的語義進(jìn)行重放的操作，那么這個日志是怎么跟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ā)起請求者。
?
工程化
我們需要多個角色盡量在一起
上文提到一個實例，需要有Proposer和Acceptor兩個角色協(xié)同工作，另外還要加以Learner進(jìn)行輔助，到了應(yīng)用方面又加入了State?machine，這里面勢必會有很多狀態(tài)需要共享。如一個Proposer必須于Acceptor處于相同的實例才能工作，那么Proposer也就必須知道當(dāng)前工作的實例是什么，又如State?machine必須知道實例的chosen?value是啥，而chosen?value是存儲于Acceptor管理的Data數(shù)據(jù)中的。在概念上，這些角色可以通過任意的通信方式進(jìn)行狀態(tài)共享，但真正去實現(xiàn)，我們都會盡量基于簡單，高性能出發(fā)，一般我們都會將這些角色同時融合在一個機器，一個進(jìn)程里面。
下圖例子是一個工程上比較常規(guī)的實現(xiàn)方式。
這里提出一個新的概念，這里三臺機器，每臺機器運行著相同的實例i，實例里整合了Acceptor，Proposer，Learner，State?machine四個角色，三臺機器的相同編號實例共同構(gòu)成了一個paxos?group的概念，一個請求只需要灌進(jìn)paxos?group里面就可以了，跟根據(jù)paxos的特點，paxos?group可以將這個請求可以隨意寫往任意一個Proposer，由Proposer來進(jìn)行提交。Paxos?group是一個虛設(shè)的概念，只是為了方便解釋，事實上是請求隨意丟到三臺機任意一個Proposer就可以了。
那么具體這四個角色是如何工作的呢。首先，由于Acceptor和Proposer在同一個進(jìn)程里面，那么保證他們處于同一個實例是很簡單的事情，其次，當(dāng)一個值被確認(rèn)之后，也可以很方便的傳送給State?machine去進(jìn)行狀態(tài)的轉(zhuǎn)移，最后當(dāng)出現(xiàn)異常狀態(tài)，實例落后或者收不到其他機器的回應(yīng)，剩下的事情就交給Learner去解決，就這樣一整合，一下事情就變得簡單了。?
?
我們需要嚴(yán)格的落盤
Paxos協(xié)議的運作工程需要做出很多保證(Promise)，這個意思是我保證了在相同的條件下我一定會做出相同的處理，如何能完成這些保證？眾所周知，在計算機里面，一個線程，進(jìn)程，甚至機器都可能隨時掛掉，而當(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來解決問題，也就是每次進(jìn)行寫盤都要附加一個fsync進(jìn)行保證。
Fsync是一個非常重的操作，也因為這個，paxos最大的瓶頸也是在寫盤上，在工程上，我們需要盡量通過各種手段，去減少paxos算法所需要的寫盤次數(shù)。
萬一磁盤fsync之后，仍然丟失或者數(shù)據(jù)錯亂怎么辦？這個稱之為拜占庭問題，工程上需要一系列的措施檢測出這些拜占庭錯誤，然后選擇性的進(jìn)行數(shù)據(jù)回滾或者直接丟棄。?
?
我們需要一個Leader
由于看這篇文章的讀者未必知道paxos理論上是如何去確定一個值的，這里簡單說明一下，paxos一個實例，支持任意多個Proposer同時進(jìn)行寫入，但是最終確定出來一個相同的值，里面是運用了一些類似鎖的方法來解決沖突的，而越多的Proposer進(jìn)行同時寫入，沖突的劇烈程度會更高，雖然完全不妨礙最終會確定一個值，但是性能上是比較差的。所以這里需要引入一個Leader的概念。
Leader就是領(lǐng)導(dǎo)者的意思，顧名思義我們希望有一個Proposer的領(lǐng)導(dǎo)者，優(yōu)先由他來進(jìn)行寫入，那么當(dāng)在只有一個Proposer在進(jìn)行寫入的情況下，沖突的概率是極小的，這樣性能會得到一個飛躍。這里再次重申一下，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)機并且進(jìn)行了狀態(tài)轉(zhuǎn)移，之后我們才能開啟新的實例。但，當(dāng)機器重啟或者進(jìn)程重啟之后，狀態(tài)機的數(shù)據(jù)可能會由于自身實現(xiàn)問題，或者磁盤數(shù)據(jù)丟失而導(dǎo)致回滾，這個我們沒辦法像上文提到的fsync一樣進(jìn)行這么強的約束，所以提出了一種方法，狀態(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)境下的一致性問題，那么一個顯而易見的特點就是我們不知道也不確定消息何時到達(dá)，是否有序到達(dá)，是否到達(dá)，我們只需要去遵守paxos協(xié)議，嚴(yán)格的處理每一條到達(dá)的消息即可，這跟RPC模型比較不一樣，paxos的特點是有去無回。
這里先定義一個名詞叫paxos消息，這里指的是paxos為了去確定一個值，算法運行過程中需要的通信產(chǎn)生的消息。下圖通過一個異步消息處理模型去構(gòu)建一個響應(yīng)paxos消息系統(tǒng)，從而完成paxos系統(tǒng)的搭建。
這里分為四個部分：
1.Request，即外部請求，這個請求直接輸入到Proposer里面，由Proposer嘗試完成一個值的確定。
2.Network?i/o，網(wǎng)絡(luò)i/o處理，負(fù)責(zé)paxos內(nèi)部產(chǎn)生的消息的發(fā)送與接收，并且只處理paxos消息，采用私有端口，純異步，各臺機器之前的network?i/o模塊互相通信。
3.Acceptor，Proposer，Learner。用于響應(yīng)并處理paxos消息。
4.State?machine，狀態(tài)機，實例確定的值(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é)果，完成一個請求的處理。
4.當(dāng)paxos完成一個值的確認(rèn)之后，所有當(dāng)前實例相關(guān)角色狀態(tài)進(jìn)行清空并初始化進(jìn)行下一個編號的實例。
?
生產(chǎn)級的Paxos庫
RTT與寫盤次數(shù)的優(yōu)化
雖然經(jīng)過我們在工程化上做的諸多要求，我們可以實現(xiàn)出一個基于paxos搭建的，可掛載任意狀態(tài)機，并且能穩(wěn)定運行的系統(tǒng)，但性能遠(yuǎn)遠(yuǎn)不夠。在性能方面需要進(jìn)行優(yōu)化，方能上崗。由于上文并未對paxos理論做介紹，這里大概說明一下樸素的paxos算法，確定一個值，在無沖突的情況下，需要兩個RTT，以及每臺機器的三次寫盤。這個性能想象一下在我們在線服務(wù)是非常慘烈的。為了達(dá)到生產(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來進(jìn)行學(xué)習(xí)，這樣會出現(xiàn)很難追上的情況。
這里需要改進(jìn)，我們可以提前獲取差距，批量打包進(jìn)行學(xué)習(xí)，比如A機器Learner記錄當(dāng)前實例編號是x，B機器是y，而x?<?y，那么B機器通過通信獲取這個差距，將(x,y]的chosen?value一起打包發(fā)送給A機器，A機器進(jìn)行批量的學(xué)習(xí)。這是一個很不錯的方法。
但仍然不夠快，當(dāng)落后的數(shù)據(jù)極大，B機器發(fā)送數(shù)據(jù)需要的網(wǎng)絡(luò)耗時也將變大，那么發(fā)送數(shù)據(jù)的過程中，A機器處于一種空閑狀態(tài)，由于paxos另外一個瓶頸在于寫盤，如果不能利用這段時間來進(jìn)行寫盤，那性能仍然堪憂。我們參考流式傳輸，采用類似的方法實現(xiàn)Learner的邊發(fā)邊學(xué)，B機器源源不斷的往A機器輸送數(shù)據(jù)，而A機器只需要收到一個實例最小單元的包體，即可立即解開進(jìn)行學(xué)習(xí)并完成寫盤。
具體的實現(xiàn)大概是先進(jìn)行一對一的協(xié)商，建立一個Session通道，在Session通道里直接采用直塞的方式無腦發(fā)送數(shù)據(jù)。當(dāng)然也不是完全的無腦，Session通過心跳機制進(jìn)行維護(hù)，一旦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ù)派的機器掛掉的，這個掛掉可能是機器永遠(yuǎn)離線。而這種情況我們一般是用一臺新的機器代替。這臺新的機器要干什么？他要從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ù)，從而自動的完成無人工介入的機器更換。?
?
正確性保證
分布式算法是很難在工程上去驗證他的正確性的，我們只能在工程上利用各種手段去接近正確，這里包括了運行前的測試，運行中的對賬，拜占庭問題的細(xì)化解決。
?
模擬異步通信環(huán)境
我們對算法內(nèi)核的構(gòu)建過程中，使用了內(nèi)存隊列來模擬網(wǎng)絡(luò)通信，使用一個進(jìn)程來模擬一個機器。進(jìn)程通過內(nèi)存隊列來通信。我們對內(nèi)存隊列加以修改，使其支持出隊的延遲，丟失，以及亂序，使得整個通信過程能按我們配置的方式來運行。我們通過配置不同的丟失率，延遲時間，以及亂序程度，驗證不同參數(shù)構(gòu)造的環(huán)境下，paxos的工作效果以及一致性是否得到保證。而我們通過鉤子將進(jìn)程頻繁殺掉重啟，以及寫盤方面的控制，模擬機器當(dāng)機重啟。
?
運行時的對賬
采用crc32算法，對有序的多個值進(jìn)行累加校驗，得到一個當(dāng)前數(shù)據(jù)版本的校驗值，通過不斷的在運行過程中比對每個當(dāng)前編號實例對應(yīng)的累加數(shù)據(jù)校驗值，一旦發(fā)現(xiàn)機器間校驗值不相同，則進(jìn)行core的處理，防止錯誤繼續(xù)擴(kuò)散。
?
防止拜占庭問題帶來的錯誤
對于所有磁盤寫入的數(shù)據(jù)，都需要進(jìn)行二次校驗，防止磁盤數(shù)據(jù)被串改。在發(fā)現(xiàn)數(shù)據(jù)被串改后，能及時的回滾到上一個校驗成功的數(shù)據(jù)，并產(chǎn)生報警。
?
最后
由于篇幅問題，這里還有更多的有意思的優(yōu)化，以及更為細(xì)節(jié)的有趣的問題，就先不做探討了。相信大家也發(fā)現(xiàn)了，這篇文章通篇都在說確定一個值，確定一個值，但就沒說到底是怎么去確定一個值的。如果你覺得這篇文章有趣對你有啟發(fā)，那就去找下論文研究一下paxos到底是怎么確定一個值的吧。
總結(jié)
以上是生活随笔為你收集整理的跟着微信后台团队学习分布式一致性协议的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 达摩院十大科技趋势发布：2020 非同小
- 下一篇： Raft 论文翻译