WF曲速未來：區(qū)塊鏈核心算法之Paxos 算法區(qū)塊鏈
WF曲速未來：Paxos算法解決的問題是在一個可能發(fā)生消息可能會延遲、丟失、重復的分布式系統(tǒng)中如何就某個值達成一致，保證不論發(fā)生以上任何異常，都不會破壞決議的一致性。
WF曲速未來先帶你會看一下libpaxos3的代碼：
第一步獲取和編譯LibPaxos3所需的基本步驟：
運行示例
什么是Paxos算法
Paxos算法解決的問題是在一個可能發(fā)生消息可能會延遲、丟失、重復的分布式系統(tǒng)中如何就某個值達成一致，保證不論發(fā)生以上任何異常，都不會破壞決議的一致性。
一個典型的場景是，在一個分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點的初始狀態(tài)一致，每個節(jié)點都執(zhí)行相同的操作序列，那么他們最后能得到一個一致的狀態(tài)。為保證每個節(jié)點執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個“一致性算法”以保證每個節(jié)點看到的指令一致。
一個通用的一致性算法可以應(yīng)用在許多場景中，是分布式計算中的重要問題。 節(jié)點通信存在兩種模型：共享內(nèi)存和消息傳遞。Paxos算法就是一種基于消息傳遞模型的一致性算法。
Paxos算法的目的
Paxos算法的目的是為了解決分布式環(huán)境下一致性的問題。多個節(jié)點并發(fā)操縱數(shù)據(jù)，如何保證在讀寫過程中數(shù)據(jù)的一致性，并且解決方案要能適應(yīng)分布式環(huán)境下的不可靠性（系統(tǒng)如何就一個值達到統(tǒng)一）
Paxos算法中，可分為4種角色
Proposer：提議發(fā)起者
處理客戶端請求，將客戶端的請求發(fā)送到集群中，以便決定這個值是否可以被批準。
Acceptor：提議批準者
負責處理接收到的提議，他們的回復就是一次投票。會存儲一些狀態(tài)來決定是否接收一個值
Client：產(chǎn)生議題者
Proposer就像Client的使者，由Proposer使者拿著Client的議題去向Acceptor提議，讓Acceptor來決策。
Learner：最終決策學習者
最終學習的目標是Acceptor們最終接受了什么議題？
Paxos算法的原理
例如：公司商定年會舉辦的地點，每個人都可以提出建議。在現(xiàn)實環(huán)境中我們可以在一個會議室共同討論或在微信群中討論（基于內(nèi)存共享方式）；但在基于消息傳遞的分布式環(huán)境中每個人只能通過手機短信與其它人通過。如何在這種會延遲、丟失的環(huán)境中確定一個年會舉辦地點；
Paxos算法是這樣解決這個問題：
1.每個人都可以提出建議、同意建議、接受建議
2、少數(shù)服從多數(shù)。只要建議被多數(shù)人同意即可確定該建議。
于是確定以下討論方式：
1）只有被提出來的建議才能被大家同意。
2）最終只能確定一個建議
3）如果某個人認為大家同意了某 個建議，那么這個建議必須真的是被大家同意的
算法推論：
情況一：如果只有一個人提出建議怎么辦？
如果只有一個建議被提出來那么大家必須同這個建議，因為如果不同意這個建議就無法確定一個年會舉辦地點。
所以得出這樣的結(jié)論：
P1：每一個人必須同意他收到的第一個建議
基于這樣的結(jié)論會出現(xiàn)以下問題：
張三給王五發(fā)短信說：我建議去上海舉辦年會！
王五給李四發(fā)短信說：我建議去廣州舉辦年會！
李四給張三發(fā)短信說：我建議去北京舉辦年會！
根據(jù)P1：每個人必須同意他收到的第一個建議，那么張三、李四、王五最終獲得的信息是不一致的。
所以再次規(guī)定：一個提議必須被大多數(shù)人同意才能生效。
那么說明一個人可以同時同意多個建議，如果一個人可以同時同意多個建議最終可能出現(xiàn)拜占庭將軍問題導致最終結(jié)果不一致。（例如：張三同意到北京舉辦也同意到廣州舉辦，那么李四將獲得2票一票自己的，一票張三的。他會認為自己獲得多數(shù)人支持所以就確定最終是到北京舉辦，同理王五也會同時獲得2票，也認為大家最終決定到廣州舉辦）
所以要避免出現(xiàn)這種問題，某個人只要同意的多個提議中的內(nèi)容相同（公司舉辦的地址）就不會出現(xiàn)這種問題。
最終協(xié)商結(jié)果是有2票是到同一個地方，這樣就可以確認最終舉辦地！
那么就會引出 這樣的一個結(jié)論：
P2：一旦同意某個建議，那么之后同意的建議中提議公司舉辦年會的地址必須一致。
問題出來了：如何確定什么是“之前”，什么 是“之后”
所以必須為提議分配一個編號，在提議之間建立一個全序關(guān)系。
情況二：
當張三、李四、王五三個人確定最終到鄭州舉辦年會后。趙六、孫七2人由于手機沒電，沒收到通知，當他們2人開機后趙六給孫七發(fā)短信提議到海南舉辦，這個提議是孫七開機后第一次收到的提議，根據(jù)P1原則，他必須同意他接收到的第一個提議，所以孫七同意到海南舉行年會。但這樣就會導致孫七與張三、李四、王五他們確定的舉辦地點不一致。
為了避免出現(xiàn)以上問題。對P2進行具體說明：
P2a：一旦一個提議被大家同意，那么之后的人再次同意的提議中的公司舉辦年會的地址必須一致。
也就是說，孫七在開機后同意的第一個提議必須是“到鄭州舉辦”才不會出現(xiàn)信息不一致的現(xiàn)象。但孫七開機后必須得接受第一個提議（P1原則），并且無法干涉提議中的內(nèi)容（公司舉辦年會的地址）。所以最好的辦法通過某種方式讓趙六的提議中的內(nèi)容與張三、李四同意的地址相同（到鄭州舉行）。這樣孫七同意的第一個提議就是“到鄭州舉辦”
我們再次對P2a進行修改：
P2b：一旦一個提議被大家同意，那么之后的人再次提議，提議中的公司舉辦年會的地址必須跟之前其它人解決的地址一致。
如何讓剛開機的趙六提議的內(nèi)容必須與張三、李四、王五討論出來的一致（到鄭州舉行）？
我們繼續(xù)對P2b進行強化修改：
P2c：如果有一個編號為N的提議具有V(提議的內(nèi)容)，那么存在一個多數(shù)派，要么他們中所有人都沒有同意編號小于N的任何提議，要么他們已經(jīng)同意的所有編號小于N的提案中編號最大的那個提案具有V。
要滿足P2c的要求，提議人在提議之前，首先要和多數(shù)人通信并獲得他們進行的最后一次同意的提議。之后根據(jù)反饋的信息決定這次提議的內(nèi)容，形成提議開始投票！
所以整個投票決議分兩個階段：
準備階段
1、提議人選擇一個編號N，并將準備信息發(fā)送給多數(shù)人。
2、如果收信人收到準備消息后，如果提議的編號大于它已經(jīng)回復的所有準備信息。那么收信人將自己上次接受的提議內(nèi)容回復給提議人，并承諾不再回復小于N的提議。
同意階段
1）當一個提議人收到多數(shù)人反饋的信息后，就進入同意階段。它要向反饋給它信息的人再次發(fā)送一個請同意該提議的請求。包含編號N和根據(jù)P2C決定的提議內(nèi)容（如果回復中沒有反饋他們已經(jīng)接受過的提議內(nèi)容，則可以自由決定提議內(nèi)容）
2）在不違背向其它人承諾的前提下，收到該提議請求后立即同意該請求。
舉例說明一下：
假設(shè)：只有User1、User2、User3 三個人決定1 1等于幾！
.準備階段
1.User1提案編號為1 并發(fā)送給User2和User3。
因User2和User3根據(jù)P2c它們并沒有接受過小于編號為1的提案。所以它們可以接受該提議，并反饋給User1不再接受小于編號1的提案。這時User1收到多數(shù)人的回復，將進入第2階段。（如果收到的回復并不能形成多數(shù)人，那么將再次進入階段1）
2.User2提案編號為2 ；并發(fā)送給User1和User3。
因User1第一次收到提案，并且根據(jù)P2C它并沒有同意過小于編號為2的提議，所以它可以接受該提議。User3由于接受過User1編號為1的提案，但User2的提案編號2>1所以User3也可以同意User2的提議，并反饋不再接受小于2的提議。User2也收到多數(shù)人的回復，將進行第2階段。
3.User3提案編號為3；并發(fā)送給user1和user2 。
因user1收到user3編號為3的提案>user2編號為2的提案，所以接受user3的提案。
因user2收到User3編號為3的提案>user1 編號為1的提案，所以接受user3的提案。
至些user3也收到多數(shù)人回復，將進行第2階段。
階段2：
1.user1發(fā)送編號為1的提議，提議內(nèi)容為：1 1=1；并發(fā)送給user2和User3。
由于user2已經(jīng)聲明不再接受小于3的提案，所以拒絕user1的提案。
由于User3已經(jīng)聲明不再接受小于2的提案，所以同樣拒絕User1的提案。
User1提議被多數(shù)人拒絕，再次進入階段1.
2.user2發(fā)送編號為2的提議，提議內(nèi)容為：1 1=2；并發(fā)送給User1和User3
由于User1已經(jīng)聲明不再接受小于3的提案，所以拒絕user2的提議。
由于User3已經(jīng)聲明不再接受小于2的提案，該提案編號=2所以user3同意User2的提議。
但User2并沒有獲得多數(shù)人的同意，所以同樣進行階段1.
3.User3發(fā)送編號為3的提議，提議內(nèi)容為：1 1=3；并發(fā)送給User1和User2;
由于user1聲明不再接受小于3的提案，所以同意User3的提議。
由于 user2聲明不再接受小于3的提案，所以同意User3的提議。
至此最終User3可以獲得多數(shù)人的同意。
Paxos算法圖解：
在實現(xiàn)環(huán)境中會通過一次提議，選擇一個Leader。后續(xù)所有的提議都只能由Leader提出。
原來paxos算法里的角色都是這樣的不靠譜，不過沒關(guān)系，結(jié)果靠譜就可以了。該算法就是為了追求結(jié)果的一致性。
1.TMT觀察網(wǎng)遵循行業(yè)規(guī)范，任何轉(zhuǎn)載的稿件都會明確標注作者和來源；
2.TMT觀察網(wǎng)的原創(chuàng)文章，請轉(zhuǎn)載時務(wù)必注明文章作者和"來源：TMT觀察網(wǎng)"，不尊重原創(chuàng)的行為TMT觀察網(wǎng)或?qū)⒆肪控熑危?br>
3.作者投稿可能會經(jīng)TMT觀察網(wǎng)編輯修改或補充。
