TMT观察网_独特视角观察TMT行业

WF曲速未來先帶你會看一下libpaxos3的代碼：

第一步獲取和編譯LibPaxos3所需的基本步驟：

運行示例

什么是Paxos算法

Paxos算法解決的問題是在一個可能發生消息可能會延遲、丟失、重復的分布式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議的一致性。

一個典型的場景是，在一個分布式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那么他們最后能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個“一致性算法”以保證每個節點看到的指令一致。

一個通用的一致性算法可以應用在許多場景中，是分布式計算中的重要問題。 節點通信存在兩種模型：共享內存和消息傳遞。Paxos算法就是一種基于消息傳遞模型的一致性算法。

Paxos算法的目的

Paxos算法的目的是為了解決分布式環境下一致性的問題。多個節點并發操縱數據，如何保證在讀寫過程中數據的一致性，并且解決方案要能適應分布式環境下的不可靠性（系統如何就一個值達到統一）

Paxos算法中，可分為4種角色

Proposer：提議發起者

處理客戶端請求，將客戶端的請求發送到集群中，以便決定這個值是否可以被批準。

Acceptor：提議批準者

負責處理接收到的提議，他們的回復就是一次投票。會存儲一些狀態來決定是否接收一個值

Client：產生議題者

Proposer就像Client的使者，由Proposer使者拿著Client的議題去向Acceptor提議，讓Acceptor來決策。

Learner：最終決策學習者

最終學習的目標是Acceptor們最終接受了什么議題？

Paxos算法的原理

例如：公司商定年會舉辦的地點，每個人都可以提出建議。在現實環境中我們可以在一個會議室共同討論或在微信群中討論（基于內存共享方式）；但在基于消息傳遞的分布式環境中每個人只能通過手機短信與其它人通過。如何在這種會延遲、丟失的環境中確定一個年會舉辦地點；

Paxos算法是這樣解決這個問題：

1.每個人都可以提出建議、同意建議、接受建議

2、少數服從多數。只要建議被多數人同意即可確定該建議。

于是確定以下討論方式：

1）只有被提出來的建議才能被大家同意。

2）最終只能確定一個建議

3）如果某個人認為大家同意了某 個建議，那么這個建議必須真的是被大家同意的

算法推論：

情況一：如果只有一個人提出建議怎么辦？

如果只有一個建議被提出來那么大家必須同這個建議，因為如果不同意這個建議就無法確定一個年會舉辦地點。

所以得出這樣的結論：

P1：每一個人必須同意他收到的第一個建議

基于這樣的結論會出現以下問題：

張三給王五發短信說：我建議去上海舉辦年會！

王五給李四發短信說：我建議去廣州舉辦年會！

李四給張三發短信說：我建議去北京舉辦年會！

根據P1：每個人必須同意他收到的第一個建議，那么張三、李四、王五最終獲得的信息是不一致的。

所以再次規定：一個提議必須被大多數人同意才能生效。

那么說明一個人可以同時同意多個建議，如果一個人可以同時同意多個建議最終可能出現拜占庭將軍問題導致最終結果不一致。（例如：張三同意到北京舉辦也同意到廣州舉辦，那么李四將獲得2票一票自己的，一票張三的。他會認為自己獲得多數人支持所以就確定最終是到北京舉辦，同理王五也會同時獲得2票，也認為大家最終決定到廣州舉辦）

所以要避免出現這種問題，某個人只要同意的多個提議中的內容相同（公司舉辦的地址）就不會出現這種問題。

最終協商結果是有2票是到同一個地方，這樣就可以確認最終舉辦地！

那么就會引出 這樣的一個結論：

P2：一旦同意某個建議，那么之后同意的建議中提議公司舉辦年會的地址必須一致。

問題出來了：如何確定什么是“之前”，什么 是“之后”

所以必須為提議分配一個編號，在提議之間建立一個全序關系。

情況二：

當張三、李四、王五三個人確定最終到鄭州舉辦年會后。趙六、孫七2人由于手機沒電，沒收到通知，當他們2人開機后趙六給孫七發短信提議到海南舉辦，這個提議是孫七開機后第一次收到的提議，根據P1原則，他必須同意他接收到的第一個提議，所以孫七同意到海南舉行年會。但這樣就會導致孫七與張三、李四、王五他們確定的舉辦地點不一致。

為了避免出現以上問題。對P2進行具體說明：

P2a：一旦一個提議被大家同意，那么之后的人再次同意的提議中的公司舉辦年會的地址必須一致。

也就是說，孫七在開機后同意的第一個提議必須是“到鄭州舉辦”才不會出現信息不一致的現象。但孫七開機后必須得接受第一個提議（P1原則），并且無法干涉提議中的內容（公司舉辦年會的地址）。所以最好的辦法通過某種方式讓趙六的提議中的內容與張三、李四同意的地址相同（到鄭州舉行）。這樣孫七同意的第一個提議就是“到鄭州舉辦”

我們再次對P2a進行修改：

P2b：一旦一個提議被大家同意，那么之后的人再次提議，提議中的公司舉辦年會的地址必須跟之前其它人解決的地址一致。    

如何讓剛開機的趙六提議的內容必須與張三、李四、王五討論出來的一致（到鄭州舉行）？

我們繼續對P2b進行強化修改：

P2c：如果有一個編號為N的提議具有V(提議的內容)，那么存在一個多數派，要么他們中所有人都沒有同意編號小于N的任何提議，要么他們已經同意的所有編號小于N的提案中編號最大的那個提案具有V。

要滿足P2c的要求，提議人在提議之前，首先要和多數人通信并獲得他們進行的最后一次同意的提議。之后根據反饋的信息決定這次提議的內容，形成提議開始投票！

所以整個投票決議分兩個階段：

準備階段

1、提議人選擇一個編號N，并將準備信息發送給多數人。

2、如果收信人收到準備消息后，如果提議的編號大于它已經回復的所有準備信息。那么收信人將自己上次接受的提議內容回復給提議人，并承諾不再回復小于N的提議。

同意階段

1）當一個提議人收到多數人反饋的信息后，就進入同意階段。它要向反饋給它信息的人再次發送一個請同意該提議的請求。包含編號N和根據P2C決定的提議內容（如果回復中沒有反饋他們已經接受過的提議內容，則可以自由決定提議內容）

2）在不違背向其它人承諾的前提下，收到該提議請求后立即同意該請求。

舉例說明一下：

假設：只有User1、User2、User3 三個人決定1 1等于幾！

.準備階段

1.User1提案編號為1 并發送給User2和User3。

因User2和User3根據P2c它們并沒有接受過小于編號為1的提案。所以它們可以接受該提議，并反饋給User1不再接受小于編號1的提案。這時User1收到多數人的回復，將進入第2階段。（如果收到的回復并不能形成多數人，那么將再次進入階段1）

2.User2提案編號為2 ；并發送給User1和User3。

因User1第一次收到提案，并且根據P2C它并沒有同意過小于編號為2的提議，所以它可以接受該提議。User3由于接受過User1編號為1的提案，但User2的提案編號2>1所以User3也可以同意User2的提議，并反饋不再接受小于2的提議。User2也收到多數人的回復，將進行第2階段。

3.User3提案編號為3；并發送給user1和user2 。

因user1收到user3編號為3的提案>user2編號為2的提案，所以接受user3的提案。

因user2收到User3編號為3的提案>user1 編號為1的提案，所以接受user3的提案。

至些user3也收到多數人回復，將進行第2階段。

階段2：

1.user1發送編號為1的提議，提議內容為：1 1=1；并發送給user2和User3。

由于user2已經聲明不再接受小于3的提案，所以拒絕user1的提案。

由于User3已經聲明不再接受小于2的提案，所以同樣拒絕User1的提案。

User1提議被多數人拒絕，再次進入階段1.

2.user2發送編號為2的提議，提議內容為：1 1=2；并發送給User1和User3

由于User1已經聲明不再接受小于3的提案，所以拒絕user2的提議。

由于User3已經聲明不再接受小于2的提案，該提案編號=2所以user3同意User2的提議。

但User2并沒有獲得多數人的同意，所以同樣進行階段1.

3.User3發送編號為3的提議，提議內容為：1 1=3；并發送給User1和User2;

由于user1聲明不再接受小于3的提案，所以同意User3的提議。

由于 user2聲明不再接受小于3的提案，所以同意User3的提議。

至此最終User3可以獲得多數人的同意。

Paxos算法圖解：

在實現環境中會通過一次提議，選擇一個Leader。后續所有的提議都只能由Leader提出。

原來paxos算法里的角色都是這樣的不靠譜，不過沒關系，結果靠譜就可以了。該算法就是為了追求結果的一致性。