一、Paxos是什么？

Paxos，它是一個基于消息傳遞的一致性算法，Leslie Lamport在1990年提出，近幾年被廣泛應用于分布式計算中，Google的Chubby，Apache的Zookeeper都是基于它的理論來實現的，Paxos還被認為是到目前為止唯一的分布式一致性算法，其它的算法都是Paxos的改進或簡化。有個問題要提一下，Paxos有一個前提：沒有拜占庭將軍問題。就是說Paxos只有在一個可信的計算環境中才能成立，這個環境是不會被入侵所破壞的。

那么拜占庭將軍問題（Byzantine Generals Problem）是什么呢？

1982年，Leslie Lamport發表了名為《The Byzantine Generals Problem》 的論文，描述了拜占庭將軍投票問題，借以映射分布式系統中計算機通信容錯問題。

一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題，將各支軍隊的 行動策略限定為進攻或撤離兩種 。因為部分軍隊進攻部分軍隊撤離可能會造成災難性后果，因此各位將軍 必須通過投票來達成一致策略 ，即所有軍隊一起進攻或所有軍隊一起撤離。因為各位將軍分處城市不同方向，他們只能通過 信使 互相聯系。在投票過程中每位將軍都將自己投票給進攻還是撤退的信息通過信使分別通知其他所有將軍，這樣一來每位將軍根據自己的投票和其他所有將軍送來的信息就可以知道共同的投票結果而決定行動策略。

投票系統的問題在于， 軍隊中可能存在叛徒和敵軍的間諜 ，左右將軍們的決定又擾亂整體軍隊的秩序。這時候在已知有成員可能不可靠的情況下，其他忠誠的將軍如何在不受叛徒和間諜影響的情況下意見達成一致，這就是拜占庭將軍問題。

拜占庭將軍問題是對分布式系統的模型化，將軍是計算機，信使則是通信系統，由于硬件錯誤或者惡意攻擊等，計算機和網絡可能會出現拜占庭將軍問題。

二、Paxos描述了這樣一個場景：

1、有一個叫做Paxos的小島(Island)上面住了一批居民，島上面所有的事情由一些特殊的人決定，他們叫做 議員 (Senator)。
2、議員的 總數 (SenatorCount)是 確定 的，不能更改。
3、島上每次環境事務的變更都需要通過一個提議(Proposal)， 每個提議都有一個編號 (PID)，這個編號是 一直增長 的，不能倒退。
4、每個提議都需要 超過半數 ((SenatorCount)/2+1)的議員同意才能生效。
5、每個議員只會同意大于當前編號的提議，包括已生效的和未生效的。
6、如果議員收到小于等于當前編號的提議，他會拒絕，并告知對方：你的提議已經有人提過了。這里的當前編號是每個議員在自己記事本上面記錄的編號，他不斷更新這個編號。整個議會不能保證所有議員記事本上的編號總是相同的。
現在議會有一個目標：保證所有的議員對于提議都能達成一致的看法。

三、Paxos運作過程

1、現在議會開始運作，所有議員一開始記事本上面記錄的編號都是0。
2、有一個議員發了一個提議：將電費設定為1元/度。
（1）他首先看了一下記事本，當前提議編號是0，那么我的這個提議的編號就是1，于是他給所有議員發消息：1號提議，設定電費1元/度。

（2）其他議員收到消息以后查了一下記事本，當前提議編號是0，這個提議可接受，于是他記錄下這個提議并回復：我接受你的1號提議，同時他在記事本上記錄：當前提議編號為1。

（3）發起提議的議員收到了超過半數的回復，立即給所有人發通知：1號提議生效！收到的議員會修改他的記事本，將1好提議由記錄改成正式的法令，當有人問他電費為多少時，他會查看法令并告訴對方：1元/度。
3、讓我們來看看 沖突的解決 ：

（1）假設總共有三個議員S1-S3，S1和S2同時發起了一個提議:1號提議，設定電費。

（2）S1想設為1元/度, S2想設為2元/度。

（3）結果S3先收到了S1的提議，于是他做了和前面同樣的操作。

（4）緊接著他又收到了S2的提議，結果他一查記事本，咦，這個提議的編號小于等于我的當前編號1，于是他拒絕了這個提議：對不起，這個提議先前提過了。

（5）于是S2的提議被拒絕，S1正式發布了提議: 1號提議生效。

（6）S2向S1或者S3打聽并更新了1號法令的內容，然后他可以選擇繼續發起2號提議。

四、ZK里面Paxos是如何運作的呢？

1、現在讓我們來對號入座，看看在ZK Server里面Paxos是如何得以貫徹實施的。

小島(Island)——ZK Server Cluster

議員(Senator)——ZK Server

提議(Proposal)——ZNode Change(Create/Delete/SetData…)

提議編號(PID)——Zxid(ZooKeeper Transaction Id)

正式法令——所有ZNode及其數據

2、貌似關鍵的概念都能一一對應上，但是等一下，Paxos島上的議員應該是人人平等的吧，而ZK Server好像有一個 Leader 的概念。沒錯，其實Leader的概念也應該屬于Paxos范疇的。

如果議員人人平等，在某種情況下會由于提議的沖突而產生一個“活鎖”（所謂活鎖我的理解是大家都沒有死，都在動，但是一直解決不了沖突問題）。Paxos的作者Lamport在他的文章” The Part-Time Parliament “中闡述了這個問題并給出了解決方案——在所有議員中設立一個總統，只有總統有權發出提議，如果議員有自己的提議，必須發給總統并由總統來提出。好，我們又多了一個角色： 總統 。

總統——ZK Server Leader

3、總統怎么選舉呢？

完成的協議包含了一個選舉唯一的發起表決的議員的過程，這個議員稱為president（總統）。在多數形式的政府中，選舉一個總統是困難的，因為大多數政府都要求在任何時刻只能有唯一的一個總統。比如在美國，如果一些人認為Bush已經被選為總統，而另一些人認為Dukakis才是總統就會造成混亂，因為其中某個總統可能會簽署某個法令而另一個總統不贊成該法令。在Paxon圣會，擁有多個總統只是會阻礙可進展性，并不會引起不一致的情況。為了滿足可進展性，選舉唯一總統的方法只需要滿足presidential selection requirement：

“如果沒有人進出會議室，那么在T分鐘之后，會議室中的牧師可以認為自己是總統。”

如果總統的選舉條件被滿足，那么完整的協議將保證，如果多數派議員在會議室中且T+99分鐘內沒有人進入或離開會議室，在這樣一個周期結束時，會議室中的每個議員的律簿上都會增加一條法令。

Paxon公民按照議員名字的字典序來選擇成為總統的議員。presidential selection requirement會被滿足，如果議員沒T-11分鐘發送一次包含他名字的消息給其他的議員，如果他T分鐘內沒有收到更高級別的名字的消息，那么他認為自己是總統。

通過要求基礎協議中的議員快速的執行步驟（2）-（6），并且增加一個選舉總統用于發起表決的方法，要求總統在合適的時機發起表決來得到完整的協議。更多的協議細節還不清楚，以上只是簡單的描述了選舉總統的辦法和總統發起表決的時機。

但顯然這不是Paxons公民所使用的辦法。我給出的規則要求在一個法令被選出后總統需要繼續發起表決，以讓剛進入會議室的議員能知道被選中的法令。顯然還有更好的辦法讓剛進入會議室的議員學習被選中的法令。另外，在挑選總統時，每個議員可以發送lastTried[p]給其他議員，以便于總統在第一次發起表決時能選擇一個足夠大的表決編號。

Paxons的公民意識到，任何涉及到進展性的條件都需要測量時間的推移。在擁有精準計時器的前提下，上面描述的總統選舉和表決的發起都可以通過超時的方式被描述為準確的算法。更詳細的分析表明，這種算法可以在時間有精準性邊界的情況下工作。Paxons上熟練的工匠可以造出滿足精度要求的沙漏。

4、選舉好總統之后，來看看ZK Sever是怎么實施的。

情況一：

屁民甲(Client)到某個議員(ZK Server)那里詢問(Get)某條法令的情況(ZNode的數據)，議員毫不猶豫的拿出他的記事本(local storage)，查閱法令并告訴他結果，同時聲明：我的數據不一定是最新的。你想要最新的數據？沒問題，等著，等我找總統Sync一下再告訴你。

情況二：

屁民乙(Client)到某個議員(ZK Server)那里要求政府歸還欠他的一萬元錢，議員讓他在辦公室等著，自己將問題反映給了總統，總統詢問所有議員的意見，多數議員表示欠屁民的錢一定要還，于是總統發表聲明，從國庫中拿出一萬元還債，國庫總資產由100萬變成99萬。屁民乙拿到錢回去了(Client函數返回)。

情況三：

總統突然掛了，議員接二連三的發現聯系不上總統，于是各自發表聲明，推選新的總統，總統大選期間政府停業，拒絕屁民的請求。

參考文章：

1. https://blog.csdn.net/cxhzqhzq/article/details/6568040

2. https://www.cnblogs.com/hzmark/p/The_Part-Time_Parliament.html

唯有熱愛方能抵御歲月漫長。

總結

以上是生活随笔為你收集整理的Paxos算法的一个简单小故事的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。