這是1個有關Paxos算法非常形象的講授與示范。Paxos是能夠基于1大堆完全不可靠的網絡條件下卻能可靠肯定地實現共鳴1致性的算法。也就是說：它允許1組不1定可靠的處理器（服務器）在某些條件得到滿足情況下就可以達成肯定的安全的共鳴，如果條件不能滿足也確保這組處理器（服務器）保持1致。

甚么是共鳴？

　　具體來講是這樣：散布式系統中由于網絡之間通訊可能會中斷，雖然幾率很低，但是沒有100%完善的網絡因此，依托網絡通訊的計算機之間要達成共鳴就比較困難，假定有X, Y和Z3臺計算機謀劃在周1攻擊人類世界，它們的攻擊計劃是只要所有計算機可用于戰役時就1起進行攻擊，不落下任何1臺機器，但是當他們決定具體甚么時間開始攻擊時，在這個關鍵問題上常常會出錯。

　　1個基本問題是，每臺機器都有自己的攻擊時間建議，計算機X可以建議在08:00時間，由于這個時間正是周1凌晨，而人們剛剛過完狂歡的周末休息天，但是計算機Z認為13:00比較好，理由固然也有1大堆，讓這3臺計算機基于某個時刻達成共鳴是非常困難的，因此，也給人類反擊留下了機會。

　　另外1個情況是，這3臺計算機是位于世界不同的位置，之間通訊也許通過電纜或其他不太可靠的網絡裝備通訊，如果X建議在08:00，它必須確認它的這個建議能夠到達活著的Y和Z，以避免1個人戰役。

問題是：我們不能準確地知道某個計算機的延遲的緣由：是由于性能慢了還是已是完全死機不能用？

　　那末，X怎樣知道其他兩個計算機是可用的呢？也就是說，當X和其他兩個計算機通訊發現得到響應要過很長時間，它不能肯定這兩臺計算機到底還能不能繼續活下去，或許這次通訊有延遲了，下1次它們又活過來了沒有延遲了，或許下次延遲更長了1點，或許下次延遲略微短了1點，這些隨機幾率問題使得X不能肯定Y和Z究竟是出了甚么問題造成延遲的，是由于處理了某個特別耗費CPU的任務還是由于死鎖等緣由？固然，有些天真的設計者會說，只要我們將性能監控到位，如果延遲超過1定時間，我們人工參與告知X確切情況就能夠，那末這類人工參與的散布式系統不是1個天然自洽的自動化系統了，不在我們討論范圍以內，而且這樣的系統會讓人疲于奔命。

　　由于X不能肯定Y或Z是不是可用，所以X僅僅只能和Y與Z中1臺基于攻擊時間達成共鳴，就沒法完全3臺機器全部投入戰役的計劃。注意的是，X Y Z3臺中任何1臺都可能會出現延遲，這就造成了3臺機器之間任何通訊都是沒法確認可靠的，比如X發出消息給Z，Z確認后回執給X，但是這段時間X突然死機了，那末Z要等待X多長時間才能知道它收到確認呢？還是再次等待X回復確認的確認，這樣無窮循環下去也不能解決它們之間通訊可能出現隨機不可靠的問題。

　　所有關鍵問題在于：由于這3臺機器之間通訊是沒法保證100%可靠，它們就不能就任何事情達成共鳴。

　　下面以散布式拍賣案例說明這類情況和Paxos的基本原理？

　　在傳統拍賣場景中，價高者先得，這些拍賣者都是在同1個房間，彼此能夠直接看得到對方的報價，如果我們假定散布式拍賣是將這些拍賣者分離到不同的地方，這樣我們可以用拍賣者之間的聯系摹擬散布式計算機之間的通訊。

　　假定拍賣者各自在自己家里拍賣，通過郵局信件發出自己的拍賣信息，拍賣者之間除非等到郵局投遞人告知他們彼此之間的報價，否則是沒法知道對方報價的。如果郵局信件投遞這個環節出了問題，投遞速度慢了乃至沒法投遞了，那末全部拍賣程序就沒法繼續進行下去。

Paxos解決共鳴思路

　　Paxos是1個解決共鳴問題consensus problem的算法，現實中Paxos的實現和成為1些世界級軟件的心臟，如Cassandra, Google的 Spanner數據庫, 散布式鎖服務Chubby. 1個被Paxos管理的系統實際上談論的是值 狀態和跟蹤等問題，其目標是建造更高可用性和強1致性的散布式系統。

　　Paxos完成1次寫操作需要兩次來回，分別是prepare/promise, 和 propose/accept：

　　第1次由提交者Leader向所有其他服務器發出prepare消息要求準備，所有服務器中大多數如果回復諾言許諾就表示準備好了，可以接受寫入；第2次提交者向所有服務器發出正式建議propose，所有服務器中大多數如果回復已接收就表示成功了。

　　為了詳細描寫這個兩段進程，首先讓我們定義1下我們將使用的1些名詞術語：

• 1個進程是系統中計算機的1個. 人們使用有關復制或節點等詞語表達，都差不多。
• 1個客戶端是屬于系統中1個成員的計算機，但是詢問系統值是甚么或要求系統獲得1個新的值。

　　Paxos構建散布式數據庫的小片斷: 它僅僅實現進程將1個新的東西精確地寫入系統中，進程是由Paxos的1個實例管治，可以失敗或不知道任何東西、或大多數進程都知道1個一樣的值，這就是共鳴，Paxos其實不真的告知我們如何用它來構建數據庫或類似的東西，它只是負責獨立節點之間通訊的進程， 這些進程服務器會基于1個新值履行決定，Paxos會存儲1個值數據，只是1次性的，1旦你第1次設置以后就不能再改變它。

Paxo讀操作

　　其實Paxos精華是在寫操作，將讀操作放在寫操作前面講授，是側重Paxos以大多數服務器達成共鳴為重要標志，通過讀取判斷是不是達成共鳴這1狀態。

　　為了從Paxos系統中讀取1個值數據，客戶端會要求讀取所有進程中存儲確當前值，然后從大多數進程服務器中取得這個值，如果數量湊不夠大多數或沒有足夠的客戶端響應，讀取操作失敗，下面圖示你會看到1個客戶端詢問其他節點他們的值是多少，這些節點返回值給客戶端，當客戶端取得了大多數節點的響應，返回的值都是一樣的，它就算成功地讀操作了，并順便保存讀結果。

　　與單節點系統(只有1臺服務器)相比這有些奇怪，這兩個系統中，客戶端都需要視察系統已決定狀態，但是在非散布式系統中像MySQL或1個memcached服務器中, 客戶端只需直接向標準的狀態存儲的服務器地址獲得狀態便可，在簡單的Paxos中, 客戶端也是一樣的方式視察狀態，但是由于并沒有標準的狀態存儲的服務器地址，它需要詢問所有的成員，以便能夠肯定唯一1個會報告值數據，實際上是大多數節點都持有的值數據，如果客戶端詢問1個節點，有可能這個節點進程已過期，得到了毛病的值數據，進程失效過期的緣由有很多：由于不可靠的網絡致使本應投遞到它們的消息丟失了；或他們或許當機然后使用了1個過期狀態恢復；或算法還在運行計算中，進程并沒有正好得到消息等等。在現實中使用Paxos實現時，其實不需要每一個節點都進行1次讀取，會有更好的讀取方式，但是他們都是拓展的原始 Paxos 算法。

Paxos寫操作

　　當1個客戶端要求寫入系統1個新值時，讓我們看看Paxos讓我們集群的進程都做了甚么？下面的進程都是只有1個值的寫入，終究我們能用這個進程作為原始數據，允許值數據在彼此之間1個個設置，但是基本的Paxos算法管治了1個新值數據的寫操作流程， 然后做重復的事情。

　　首先Paxos管理的系統中1個客戶端要求寫入1個新值，客戶端這里如圖所示是紅圈，其它進程是藍圈， Paxos能保證客戶端發送它們的寫要求到Paxos集群中任何成員, 這里演示中客戶端隨機挑選進程中任意1個，這類方式是重要且奇妙的，意味著沒有任何單點風險，意味著我們的Paxos管治系統能繼續保持在線可用，不管任何1個節點當機或其他不可用緣由無響應。如果我們設計1個特定節點作為“推薦人proposer”或 "the master" 等, 如果這個主節點死機，那末全部系統就崩潰了。

　　當寫要求被接受后，Paxos進程會接受這個寫新值到系統中要求“建議”， “建議”是Paxos中1個正式概念: 向1個Paxos管治的系統建議可能會成功或失敗，需要步驟來確保共鳴能夠達成維系，這個建議以準備消息從那些與客戶端連接的進程節點們被發往全部系統。

序列號

　　這個準備消息保存在被建議的值數據中，它們也稱為序列號sequence number，序列號是由建議進程產生的，它定義了接受進程應當準備接受帶有序列號的建議，這個序列號是關鍵: 它用于表明新舊建議之間的區分，如果兩個進程試圖取得需要設置1個值，Paxos認為最后1個進程應當有優先權，這樣讓進程分辨哪一個是最后1個，這樣它就可以設置最新的值。

　　這些接受的進程能夠進行在系統中關鍵的檢查：這個在到來的準備消息中序列號是我見過的最高級別嗎？如果是，那就很cool, 我能準備好接受將要到來的值數據，那就不要管之前聽到的任何其他值數據了，你能看到這個進程在右側演示中：客戶端每隔1段向1個進程建議1個新值，這個進程發送準備消息給其他進程，然后那些進程注意到這是1個成功的更高的超過舊的新序列號，然后就放手那些舊建議。

　　這里有1個順序的設計(先發送準備消息)，這是為避免單點風險，如果沒有這個順序，Paxos中成員就沒法分辨哪一個建議是他們可以有信心腸準備接受的。

　　我們不能想象有另外不同的共鳴算法，不是依照以下步驟：首先發送第1個消息詢問其他進程，以確保將設置的新值是最新的值，雖然方式可以再簡單些，但是可能就不能滿足共鳴算法安全的需求了，如果兩個進程正好同時建議不同的值，以下所示：

　　大自然常常會這樣欺騙我們，每一個包都能另外1半的進程相信它們接受的或許是正確或許是毛病的值，系統將進入1個僵局，存在兩個相同數量的組卻有不同的值，那末就沒法肯定大多數這個概念了，這個僵局能夠被第1個Paxos消息避免，由于Paxos的序列號，那些有問題的建議將有被其他更低的序列號，這樣序列號更高的建議就會絕不含糊地被大多數進程接收，它們也首先取得了更高的序列號，然后如果接遭到更低的序列號就會謝絕，Paxos 就是這樣通過用序列號控制全部系統的時間節奏。

　　注意：保證沒有兩個建議使用相同的序列號是很重要的，這是確保他們的順序，這樣每一個序列號只有1個建議，這樣才能比較兩個建議，實現Paxos時，全局唯1有序的序列號實際是精確系統時間和集群中節點數量的拷貝，隨著時間不斷增加，歷來不會重復。

Paxos第1階段：準備Perpare/諾言Promises

　　Paxos的第1階段是prepare/promise，準備階段就是將建議值發送到各個目標節點。

　　當建議被發到目標節點后，進程會會檢查建議中的序列號，是不是是它們見到過的最高級，如果是最高級，它們會發出1個promise不再接受比這個新序列號更舊的建議了，這個諾言promise作為消息從許下諾言的進程發到提交建議新值的進程服務器，這個諾言消息給提交建議的進程后，提交建議的進程需要自己統計1下有多少其他進程已發回它們的諾言promise了，如果判斷數量上是不是到達大多數？如果大多數進程已同意接受這個建議或更高級序列號的建議，這個提交建議的進程就可以知道它取得了發言權(由于有大多數支持)，這樣就開始講話，算法中的下1步處理將可能進行；如果回復諾言的節點數量沒有到達大多數，也就是共鳴沒有達成，這樣這個節點提交的建議將退出，客戶端要求的寫操作失敗。

　　為了決定1個建議是不是已有足夠的回復諾言promises, 提交建議者只是統計1下它接遭到的promise消息數量，然后和全部系統中節點服務器數量比較1下，“足夠”意味著大多數(N/2 + 1)個進程服務器在某段時間內都回復了諾言promises。如果超過1半的進程服務器沒有返回諾言，這意味著這個建議沒有被大多數通過，那末在前面描寫的讀算法中就不能滿足大多數的要求，也就不能達成共鳴，這個建議就退出。其他包括網絡分區毛病也可能會禁止大多數達成共鳴，

第2階段：Paoxs接納Acceptance