WF曲速未來(lái)先帶你會(huì)看一下libpaxos3的代碼：

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

運(yùn)行示例

什么是Paxos算法

Paxos算法解決的問(wèn)題是在一個(gè)可能發(fā)生消息可能會(huì)延遲、丟失、重復(fù)的分布式系統(tǒng)中如何就某個(gè)值達(dá)成一致，保證不論發(fā)生以上任何異常，都不會(huì)破壞決議的一致性。

一個(gè)典型的場(chǎng)景是，在一個(gè)分布式數(shù)據(jù)庫(kù)系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個(gè)節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個(gè)一致的狀態(tài)。為保證每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個(gè)“一致性算法”以保證每個(gè)節(jié)點(diǎn)看到的指令一致。

一個(gè)通用的一致性算法可以應(yīng)用在許多場(chǎng)景中，是分布式計(jì)算中的重要問(wèn)題。 節(jié)點(diǎn)通信存在兩種模型：共享內(nèi)存和消息傳遞。Paxos算法就是一種基于消息傳遞模型的一致性算法。

Paxos算法的目的

Paxos算法的目的是為了解決分布式環(huán)境下一致性的問(wèn)題。多個(gè)節(jié)點(diǎn)并發(fā)操縱數(shù)據(jù)，如何保證在讀寫過(guò)程中數(shù)據(jù)的一致性，并且解決方案要能適應(yīng)分布式環(huán)境下的不可靠性（系統(tǒng)如何就一個(gè)值達(dá)到統(tǒng)一）

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

Proposer：提議發(fā)起者

處理客戶端請(qǐng)求，將客戶端的請(qǐng)求發(fā)送到集群中，以便決定這個(gè)值是否可以被批準(zhǔn)。

Acceptor：提議批準(zhǔn)者

負(fù)責(zé)處理接收到的提議，他們的回復(fù)就是一次投票。會(huì)存儲(chǔ)一些狀態(tài)來(lái)決定是否接收一個(gè)值

Client：產(chǎn)生議題者

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

Learner：最終決策學(xué)習(xí)者

最終學(xué)習(xí)的目標(biāo)是Acceptor們最終接受了什么議題？

Paxos算法的原理

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

Paxos算法是這樣解決這個(gè)問(wèn)題：

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

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

于是確定以下討論方式：

1）只有被提出來(lái)的建議才能被大家同意。

2）最終只能確定一個(gè)建議

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

算法推論：

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

如果只有一個(gè)建議被提出來(lái)那么大家必須同這個(gè)建議，因?yàn)槿绻煌膺@個(gè)建議就無(wú)法確定一個(gè)年會(huì)舉辦地點(diǎn)。

所以得出這樣的結(jié)論：

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

基于這樣的結(jié)論會(huì)出現(xiàn)以下問(wèn)題：

張三給王五發(fā)短信說(shuō)：我建議去上海舉辦年會(huì)！

王五給李四發(fā)短信說(shuō)：我建議去廣州舉辦年會(huì)！

李四給張三發(fā)短信說(shuō)：我建議去北京舉辦年會(huì)！

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

所以再次規(guī)定：一個(gè)提議必須被大多數(shù)人同意才能生效。

那么說(shuō)明一個(gè)人可以同時(shí)同意多個(gè)建議，如果一個(gè)人可以同時(shí)同意多個(gè)建議最終可能出現(xiàn)拜占庭將軍問(wèn)題導(dǎo)致最終結(jié)果不一致。（例如：張三同意到北京舉辦也同意到廣州舉辦，那么李四將獲得2票一票自己的，一票張三的。他會(huì)認(rèn)為自己獲得多數(shù)人支持所以就確定最終是到北京舉辦，同理王五也會(huì)同時(shí)獲得2票，也認(rèn)為大家最終決定到廣州舉辦）

所以要避免出現(xiàn)這種問(wèn)題，某個(gè)人只要同意的多個(gè)提議中的內(nèi)容相同（公司舉辦的地址）就不會(huì)出現(xiàn)這種問(wèn)題。

最終協(xié)商結(jié)果是有2票是到同一個(gè)地方，這樣就可以確認(rèn)最終舉辦地！

那么就會(huì)引出 這樣的一個(gè)結(jié)論：

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

問(wèn)題出來(lái)了：如何確定什么是“之前”，什么 是“之后”

所以必須為提議分配一個(gè)編號(hào)，在提議之間建立一個(gè)全序關(guān)系。

情況二：

當(dāng)張三、李四、王五三個(gè)人確定最終到鄭州舉辦年會(huì)后。趙六、孫七2人由于手機(jī)沒(méi)電，沒(méi)收到通知，當(dāng)他們2人開(kāi)機(jī)后趙六給孫七發(fā)短信提議到海南舉辦，這個(gè)提議是孫七開(kāi)機(jī)后第一次收到的提議，根據(jù)P1原則，他必須同意他接收到的第一個(gè)提議，所以孫七同意到海南舉行年會(huì)。但這樣就會(huì)導(dǎo)致孫七與張三、李四、王五他們確定的舉辦地點(diǎn)不一致。

為了避免出現(xiàn)以上問(wèn)題。對(duì)P2進(jìn)行具體說(shuō)明：

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

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

我們?cè)俅螌?duì)P2a進(jìn)行修改：

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

如何讓剛開(kāi)機(jī)的趙六提議的內(nèi)容必須與張三、李四、王五討論出來(lái)的一致（到鄭州舉行）？

我們繼續(xù)對(duì)P2b進(jìn)行強(qiáng)化修改：

P2c：如果有一個(gè)編號(hào)為N的提議具有V(提議的內(nèi)容)，那么存在一個(gè)多數(shù)派，要么他們中所有人都沒(méi)有同意編號(hào)小于N的任何提議，要么他們已經(jīng)同意的所有編號(hào)小于N的提案中編號(hào)最大的那個(gè)提案具有V。

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

所以整個(gè)投票決議分兩個(gè)階段：

準(zhǔn)備階段

1、提議人選擇一個(gè)編號(hào)N，并將準(zhǔn)備信息發(fā)送給多數(shù)人。

2、如果收信人收到準(zhǔn)備消息后，如果提議的編號(hào)大于它已經(jīng)回復(fù)的所有準(zhǔn)備信息。那么收信人將自己上次接受的提議內(nèi)容回復(fù)給提議人，并承諾不再回復(fù)小于N的提議。

同意階段

1）當(dāng)一個(gè)提議人收到多數(shù)人反饋的信息后，就進(jìn)入同意階段。它要向反饋給它信息的人再次發(fā)送一個(gè)請(qǐng)同意該提議的請(qǐng)求。包含編號(hào)N和根據(jù)P2C決定的提議內(nèi)容（如果回復(fù)中沒(méi)有反饋他們已經(jīng)接受過(guò)的提議內(nèi)容，則可以自由決定提議內(nèi)容）

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

舉例說(shuō)明一下：

假設(shè)：只有User1、User2、User3 三個(gè)人決定1 1等于幾！

.準(zhǔn)備階段

1.User1提案編號(hào)為1 并發(fā)送給User2和User3。

因User2和User3根據(jù)P2c它們并沒(méi)有接受過(guò)小于編號(hào)為1的提案。所以它們可以接受該提議，并反饋給User1不再接受小于編號(hào)1的提案。這時(shí)User1收到多數(shù)人的回復(fù)，將進(jìn)入第2階段。（如果收到的回復(fù)并不能形成多數(shù)人，那么將再次進(jìn)入階段1）

2.User2提案編號(hào)為2 ；并發(fā)送給User1和User3。

因User1第一次收到提案，并且根據(jù)P2C它并沒(méi)有同意過(guò)小于編號(hào)為2的提議，所以它可以接受該提議。User3由于接受過(guò)User1編號(hào)為1的提案，但User2的提案編號(hào)2>1所以User3也可以同意User2的提議，并反饋不再接受小于2的提議。User2也收到多數(shù)人的回復(fù)，將進(jìn)行第2階段。

3.User3提案編號(hào)為3；并發(fā)送給user1和user2 。

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

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

至些user3也收到多數(shù)人回復(fù)，將進(jìn)行第2階段。

階段2：

1.user1發(fā)送編號(hào)為1的提議，提議內(nèi)容為：1 1=1；并發(fā)送給user2和User3。

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

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

User1提議被多數(shù)人拒絕，再次進(jìn)入階段1.

2.user2發(fā)送編號(hào)為2的提議，提議內(nèi)容為：1 1=2；并發(fā)送給User1和User3

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

由于User3已經(jīng)聲明不再接受小于2的提案，該提案編號(hào)=2所以u(píng)ser3同意User2的提議。

但User2并沒(méi)有獲得多數(shù)人的同意，所以同樣進(jìn)行階段1.

3.User3發(fā)送編號(hào)為3的提議，提議內(nèi)容為：1 1=3；并發(fā)送給User1和User2;

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

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

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

Paxos算法圖解：

在實(shí)現(xiàn)環(huán)境中會(huì)通過(guò)一次提議，選擇一個(gè)Leader。后續(xù)所有的提議都只能由Leader提出。

原來(lái)paxos算法里的角色都是這樣的不靠譜，不過(guò)沒(méi)關(guān)系，結(jié)果靠譜就可以了。該算法就是為了追求結(jié)果的一致性。