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