1. 首頁 > 生活百科 > >

Paxos分布式系統共識算法？我愿稱其為點歌算法…

生活百科

原創：微信公眾號 碼農參上，歡迎分享 ， 轉載請保留出處 。
哈嘍大家好??，我是Hydra 。
【Paxos分布式系統共識算法？我愿稱其為點歌算法…】分布式系統共識算法Paxos相信大家都不陌生，它被稱為最難理解的算法不是沒有道理的，首先，它的發表之路就充滿了坎坷 。
1990年，萊斯利·蘭伯特大佬寫了一篇論文，舉了一個城邦選舉的例子來介紹Paxos算法，然而大佬的幽默感并未得到審稿人的認可，論文未發表成功…
1998年，蘭伯特重新發表論文《The Part-Time Parliament》描述算法，然而眾多學者并不買賬，直呼看不懂…
2001年 ， 蘭伯特對算法的描述進行簡化 ， 再次發表 《Paxos Made Simple》，這次Paxos成為了世界公認最優秀的分布式系統共識算法…
Paxos分布式系統共識算法？我愿稱其為點歌算法…

文章插圖
其實說白了，Paxos算法要解決的問題是一個分布式系統如何就某個值決議達成一致 。比如說，一組進程現在正在提議某個數據的值 ， 需要通過消息傳遞的方式使這個值達成一致，也就是最終僅能有一個值被選定 。
但畢竟是大佬寫出來的東西，且不說邏輯推理部分 ， 就算單拎出來論文中對兩個核心階段的描述來說，我等凡人理解起來也還是有些困難 。
不信？那就讓英語六級的我先來簡單地翻譯一下 。
Paxos分布式系統共識算法？我愿稱其為點歌算法…

文章插圖
階段1a、提案者選擇一個提案號n，發送一個提案號為n的prepare請求給大多數接受者 。
b、如果一個接受者收到的編號為n的prepare請求，并且編號比它已經響應過的任何prepare請求的編號都大，那它就回應這個請求，承諾不再接受任何編號小于n的提案，并回復它已經接受的編號最大的提案（如果存在的話） 。
階段2a、如果提案者收到大多數接受者關于它編號為n的prepare請求的回應，它就給這些接受者發送一個編號為n，值為v的accept請求，v是收到的回應中編號最大的提案值 。如果之前不存在任何一個提案的回復時 ， 那么v可以是任意值，也就是可以由自己指定 。
b、接受者收到編號為n的accept請求時，只要它還沒有響應編號比n更高的prepare請求，那么它將接受該提案 。
Paxos分布式系統共識算法？我愿稱其為點歌算法…

文章插圖
是不是還看不懂？那就對了，下面我們通過一個簡單的例子來描述這個過程 。
記得小時候 ， 有不少廣播電臺可以通過電話點歌，打電話給話務員告訴她你要點的歌，接下來就會播放 。當然了，這個過程不是免費的，肯定有不少小伙伴在月末父母交話費的時候，慘遭過社會的毒打 。
既然是電臺熱線，那么肯定不只有一個話務員了，我們假定這個電臺同時存在3個話務員，并且她們之間是相互沒有交流的，那么當短時間內打進來很多電話時，要怎么決定放哪首歌呢？
Paxos分布式系統共識算法？我愿稱其為點歌算法…

文章插圖
首先 ， 話務員之間遵從少數服從多數 ， 那么為了獲得更多話務員的支持，你可以不斷給更多的話務員打電話 。
其次，前面我們說過，這個過程是收費的，假定存在一條潛規則，電臺會更偏向于接受出價高的人的點歌請求，那么也就好辦了，你可以使了勁地加錢 。
在這種環境下，聽眾想要點歌成功的話 ， 就得靠上面兩個辦法 。
這時，第一個聽眾打進來電話了，在第一個階段聽眾只能進行報價，還不能提出自己想要聽什么歌，這個報價就可以理解為算法中的編號n 。
Paxos分布式系統共識算法？我愿稱其為點歌算法…

文章插圖
因為聽眾1是第一個打進熱線電話的，在他之前還不存在任何報價，所以這里話務員們會無條件地先接受第一個聽眾的報價并記錄下來，然后返回給聽眾1一個回復信息 。
在回復的信息中，話務員不但需要告訴聽眾他的報價目前最高，已經被認可了，還要說明之前沒有接受過其他任何聽眾的點歌請求 。
Paxos分布式系統共識算法？我愿稱其為點歌算法…

文章插圖
這時候聽眾1一看，自己已經獲得了超過半數以上的話務員的認可了，那么進入階段2，告訴話務員自己想要聽什么歌曲 。當然，在這個過程中，還得順帶著告訴話務員自己在上一階段中的報價是多少 。

推薦閱讀