深入剖析一致性算法 Paxos
這是一個有關Paxos算法非常形象的講解與示範。Paxos是能夠基於一大堆完全不可靠的網絡條件下卻能可靠確定地實現共識一致性的算法。也就是說：它允許一組不一定可靠的處理器（伺服器）在某些條件得到滿足情況下就能達成確定的安全的共識，如果條件不能滿足也確保這組處理器（伺服器）保持一致。
什麼是共識？
具體來說是這樣：分布式系統中由於網絡之間通訊可能會中斷，雖然機率很低，但是沒有100%完美的網絡因此，依靠網絡通訊的計算機之間要達成共識就比較困難，假設有X, Y和Z三台計算機謀劃在周一攻擊人類世界，它們的攻擊計劃是只要所有計算機可用於戰鬥時就一起進行攻擊，不落下任何一台機器，但是當他們決定具體什麼時間開始攻擊時，在這個關鍵問題上往往會出錯。
一個基本問題是，每台機器都有自己的攻擊時間建議，計算機X可以建議在08:00時間，因為這個時間正是周一早晨，而人們剛剛過完狂歡的周末休息天，但是計算機Z認為13:00比較好，理由當然也有一大堆，讓這三台計算機基於某個時刻達成共識是非常困難的，因此，也給人類反擊留下了機會。
另外一個情況是，這三台計算機是位於世界不同的位置，之間通訊或許通過電纜或者其他不太可靠的網絡設備通訊，如果X建議在08:00，它必須確認它的這個建議能夠到達活著的Y和Z，以免一個人戰鬥。
問題是：我們不能準確地知道某個計算機的延遲的原因：是因為性能慢了還是已經是徹底死機不能用？
那麼，X怎麼知道其他兩個計算機是可用的呢？也就是說，當X和其他兩個計算機通訊發現得到響應要過很長時間，它不能確定這兩台計算機到底還能不能繼續活下去，也許這次通訊有延遲了，下一次它們又活過來了沒有延遲了，也許下次延遲更長了一點，也許下次延遲稍微短了一點，這些隨機機率問題使得X不能確定Y和Z到底是出了什麼問題造成延遲的，是因為處理了某個特別耗費CPU的任務還是因為死鎖等原因？當然，有些天真的設計者會說，只要我們將性能監控到位，如果延遲超過一定時間，我們人工介入告訴X確切情況就可以，那麼這種人工介入的分布式系統不是一個天然自洽的自動化系統了，不在我們討論範圍之內，而且這樣的系統會讓人疲於奔命。
因為X不能確定Y或Z是否可用，所以X僅僅只能和Y與Z中一台基於攻擊時間達成共識，就無法完全三台機器全部投入戰鬥的計劃。注意的是，X Y Z三台中任何一台都可能會出現延遲，這就造成了三台機器之間任何通訊都是無法確認可靠的，比如X發出消息給Z，Z確認後回執給X，但是這段時間X突然死機了，那麼Z要等待X多長時間才能知道它收到確認呢？還是再次等待X回復確認的確認，這樣無限循環下去也不能解決它們之間通訊可能出現隨機不可靠的問題。
所有關鍵問題在於：由於這三台機器之間通訊是無法保證100%可靠，它們就不能就任何事情達成共識。
下面以分布式拍賣案例說明這種情況以及Paxos的基本原理？
在傳統拍賣場景中，價高者先得，這些拍賣者都是在同一個房間，彼此能夠直接看得到對方的報價，如果我們假設分布式拍賣是將這些拍賣者分離到不同的地方，這樣我們可以用拍賣者之間的聯繫模擬分布式計算機之間的通訊。
假設拍賣者各自在自己家裡拍賣，通過郵局信件發出自己的拍賣信息，拍賣者之間除非等到郵局投遞人告訴他們彼此之間的報價，否則是無法知道對方報價的。如果郵局信件投遞這個環節出了問題，投遞速度慢了甚至無法投遞了，那麼整個拍賣程序就無法繼續進行下去。
Paxos解決共識思路
Paxos是一個解決 共識問題consensus problem 的算法，現實中Paxos的實現以及成為一些世界級軟體的心臟，如Cassandra, Google的 Spanner資料庫, 分布式鎖服務Chubby. 一個被Paxos管理的系統實際上談論的是值 狀態和跟蹤等問題，其目標是建造更高可用性和強一致性的分布式系統。
Paxos完成一次寫操作需要兩次來回，分別是prepare/promise, 和 propose/accept：
第一次由提交者Leader向所有其他伺服器發出prepare消息請求準備，所有伺服器中大多數如果回復諾言承諾就表示準備好了，可以接受寫入；第二次提交者向所有伺服器發出正式建議propose，所有伺服器中大多數如果回復已經接收就表示成功了。
為了詳細描述這個兩段過程，首先讓我們定義一下我們將使用的一些名詞術語：
- 一個流程是系統中計算機的一個. 人們使用有關複製或節點等詞語表達，都差不多。
- 一個客戶端是屬於系統中一個成員的計算機，但是詢問系統值是什麼或者要求系統獲取一個新的值。
Paxos構建分布式資料庫的小片段: 它僅僅實現流程將一個新的東西精確地寫入系統中，流程是由Paxos的一個實例管治，可以失敗或者不知道任何東西、或者大多數流程都知道一個同樣的值，這就是共識，Paxos並不真的告訴我們如何用它來構建資料庫或類似的東西，它只是負責獨立節點之間通訊的流程， 這些流程伺服器會基於一個新值執行決定，Paxos會存儲一個值數據，只是一次性的，一旦你第一次設置以後就不能再改變它。
Paxo讀操作
其實Paxos精華是在寫操作，將讀操作放在寫操作前面講解，是著重Paxos以大多數伺服器達成共識為重要標誌，通過讀取判斷是否達成共識這一狀態。
為了從Paxos系統中讀取一個值數據，客戶端會請求讀取所有流程中存儲的當前值，然後從大多數流程伺服器中獲得這個值，如果數量湊不夠大多數或者沒有足夠的客戶端響應，讀取操作失敗，下面圖示你會看到一個客戶端詢問其他節點他們的值是多少，這些節點返回值給客戶端，當客戶端獲得了大多數節點的響應，返回的值都是同樣的，它就算成功地讀操作了，並順便保存讀結果。
與單節點系統(只有一台伺服器)相比這有些奇怪，這兩個系統中，客戶端都需要觀察系統已決定狀態，但是在非分布式系統中像MySQL或一個memcached伺服器中, 客戶端只需直接向標準的狀態存儲的伺服器地址獲取狀態即可，在簡單的Paxos中, 客戶端也是同樣的方式觀察狀態，但是因為並沒有標準的狀態存儲的伺服器地址，它需要詢問所有的成員，以便能夠確定僅有一個會報告值數據，實際上是大多數節點都持有的值數據，如果客戶端詢問一個節點，有可能這個節點流程已經過期，得到了錯誤的值數據，流程失效過期的原因有很多：由於不可靠的網絡導致本應送達到它們的消息丟失了；或者他們也許當機然後使用了一個過期狀態恢復；或者算法還在運行計算中，流程並沒有正好得到消息等等。在現實中使用Paxos實現時，其實不需要每個節點都進行一次讀取，會有更好的讀取方式，但是他們都是拓展的原始 Paxos 算法。
Paxos寫操作
當一個客戶端要求寫入系統一個新值時，讓我們看看Paxos讓我們集群的流程都做了什麼？下面的過程都是只有一個值的寫入，最終我們能用這個流程作為原始數據，允許值數據在彼此之間一個個設置，但是基本的Paxos算法管治了一個新值數據的寫操作流程， 然後做重複的事情。
首先Paxos管理的系統中一個客戶端要求寫入一個新值，客戶端這裡如圖所示是紅圈，其它流程是藍圈， Paxos能保證客戶端發送它們的寫請求到Paxos集群中任何成員, 這裡演示中客戶端隨機挑選流程中任意一個，這種方式是重要且巧妙的，意味著沒有任何單點風險，意味著我們的Paxos管治系統能繼續保持在線可用，無論任何一個節點當機或其他不可用原因無響應。如果我們設計一個特定節點作為「推薦人proposer」或者 「the master」 等, 如果這個主節點死機，那麼整個系統就崩潰了。
當寫請求被接受後，Paxos流程會接受這個寫新值到系統中請求「建議」， 「建議」是Paxos中一個正式概念: 向一個Paxos管治的系統建議可能會成功或失敗，需要步驟來確保共識能夠達成維繫，這個建議以準備消息從那些與客戶端連接的流程節點們被發往整個系統。
序列號
這個準備消息保存在被建議的值數據中，它們也稱為序列號s equence number ，序列號是由建議流程產生的，它定義了接受流程應該準備接受帶有序列號的建議，這個序列號是關鍵: 它用於表明新舊建議之間的區別，如果兩個流程試圖獲得需要設置一個值，Paxos認為最後一個流程應該有優先權，這樣讓流程分辨哪個是最後一個，這樣它就能設置最新的值。
這些接受的流程能夠進行在系統中關鍵的檢查：這個在到來的準備消息中序列號是我見過的最高級別嗎？如果是，那就很cool, 我能準備好接受將要到來的值數據，那就不要管之前聽到的任何其他值數據了，你能看到這個過程在右邊演示中：客戶端每隔一段向一個流程建議一個新值，這個流程發送準備消息給其他流程，然後那些流程注意到這是一個成功的更高的超過舊的新序列號，然後就放手那些舊建議。
這裡有一個順序的設計(先發送準備消息)，這是為避免單點風險，如果沒有這個順序，Paxos中成員就無法分辨哪個建議是他們可以有信心地準備接受的。
我們不能想像有另外不同的共識算法，不是按照如下步驟：首先發送第一個消息詢問其他流程，以確保將設置的新值是最新的值，儘管方式可以再簡單些，但是可能就不能滿足共識算法安全的需求了，如果兩個流程正好同時建議不同的值，如下所示：
大自然經常會這樣欺騙我們，每個包都能另外一半的流程相信它們接受的也許是正確也許是錯誤的值，系統將進入一個僵局，存在兩個相同數量的組卻有不同的值，那麼就無法確定大多數這個概念了，這個僵局能夠被第一個Paxos消息避免，因為Paxos的序列號，那些有問題的建議將有被其他更低的序列號，這樣序列號更高的建議就會毫不含糊地被大多數流程接收，它們也首先獲得了更高的序列號，然後如果接受到更低的序列號就會拒絕，Paxos 就是這樣通過用序列號控制整個系統的時間節奏。
上圖演示了客戶端首先發一個準備消息給Paxos流程，Paxos流程會檢查下一步將到來的建議的序列號，以分辨是否準備接受這個新值，所有流程都是這樣消除歧義，共識由此達成。
注意：保證沒有兩個建議使用相同的序列號是很重要的，這是確保他們的順序，這樣每個序列號只有一個建議，這樣才能比較兩個建議，實現Paxos時，全局唯一有序的序列號實際是精確係統時間和集群中節點數量的拷貝，隨著時間不斷增加，從來不會重複。
Paxos第一階段：準備Perpare/諾言Promises
Paxos的第一階段是prepare/promise，準備階段就是將建議值發送到各個目標節點。
當建議被發到目標節點後，流程會會檢查建議中的序列號，是否是它們見到過的最高級，如果是最高級，它們會發出一個promise不再接受比這個新序列號更舊的建議了，這個諾言promise作為消息從許下諾言的流程發到提交建議新值的流程伺服器，這個諾言消息給提交建議的流程後，提交建議的流程需要自己統計一下有多少其他流程已經發回它們的諾言promise了，如果判斷數量上是否達到大多數？如果大多數流程已經同意接受這個建議或者更高級序列號的建議，這個提交建議的流程就能知道它獲得了發言權(因為有大多數支持)，這樣就開始講話，算法中的下一步處理將可能進行；如果回復諾言的節點數量沒有達到大多數，也就是共識沒有達成，這樣這個節點提交的建議將退出，客戶端要求的寫操作失敗。
為了決定一個建議是否已經有足夠的回覆諾言promises, 提交建議者只是統計一下它接受到的 promise 消息數量，然後和整個系統中節點伺服器數量比較一下，「足夠」意味著大多數(N/2 + 1)個流程伺服器在某段時間內都回復了諾言promises。如果超過一半的流程伺服器沒有返回諾言，這意味著這個建議沒有被大多數通過，那麼在前面描述的讀算法中就不能滿足大多數的要求，也就不能達成共識，這個建議就退出。其他包括網絡分區錯誤也可能會阻止大多數達成共識，
第二階段：Paoxs接納Acceptance
當完成prepare/promise階段，進入了 propose/accept階段。
一旦建議提交者已經從大多數其他流程伺服器獲得了諾言，它會要求許諾的流程伺服器接收它們之前承諾接受的新值數據，這是一個「確認commit」階段，如果沒有衝突建議 失敗或分區錯誤，那麼這個新建議將被所有其他節點接受，那麼Paxos過程就完成了。
你能看到右邊的演示，注意這個演示比上面promise在最後多了一個動作，也就是提交建議者將新值發給那些許諾言的流程伺服器，讓它們接受了這個新值。
接受的過程也許可能會發生失敗，在回復了諾言消息以後，在接受到Accept消息之前，如果有足夠多的伺服器正好在這個時間段失敗，那麼接受行為只能是少數伺服器，那麼Paxos進入了厄運狀態：一些流程伺服器接受了新值，而不是全部的，這種不一致已經在前面讀操作中描述：一個客戶端試圖從系統中大多數節點伺服器讀取它們同意接受的值，它發現一些節點伺服器報告有不同的值數據，這會引起讀失敗，但是Paxos還保持一致性，不允許在沒有達成共識情況下任何寫操作發生，這種壞的情況在實踐中經常通過重複接受階段來讓大多數節點最終接受。
總結
Paxos算法是保證在分布式系統中寫操作能夠順利進行，保證系統中大多數狀態是一致的，沒有機會看到不一致，因此，Paxos算法的特點是一致性>可用性。
vector clock向量時鐘是另外一種保證複製的算法，其特點是可用性>一致性，但是，一旦發生衝突，不像Paxos能自行解決，需要人工干預編寫代碼解決。
Paxos算法和Vector Clock都是由Leslie Lamport提出。