Paxos分布式系統共識算法?我愿稱其為點歌算法…( 二 )


于是,聽眾1再次打進熱線,先單獨向話務員2發起了選歌提議 。

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

文章插圖
在收到聽眾1的點歌請求后 , 話務員2看到聽眾1在請求中攜帶的之前報價是1塊 , 滿足大于等于自己記錄的最大報價這一條件 , 于是果斷接受聽眾1的點歌請求 。
在接受點歌請求后,話務員2要記錄的東西又要增加了,她不但要記住已接受的請求的報價金額,還要記住已接受請求的點播歌曲 。然后給聽眾1一個回復,表示我已經接受了你的點歌請求 。
Paxos分布式系統共識算法?我愿稱其為點歌算法…

文章插圖
當然了,在聽眾1努力點歌的時候,其他聽眾也不會閑著對不對?
聽眾2雖然打進電話晚了點,但是直接發動鈔能力,把自己的報價提升到了兩塊,來和話務員們進行通話 。
Paxos分布式系統共識算法?我愿稱其為點歌算法…

文章插圖
由于兩塊錢的報價高于本地記錄的最高報價,所以話務員1和話務員2都會認可這個報價,所以她們會先把本地的最高報價值更新為兩塊 。
但是接下來,由于本地記錄的信息有所不同,所以她們將會給出不同的答復 。
Paxos分布式系統共識算法?我愿稱其為點歌算法…

文章插圖
如果這時候,再來一個聽眾3打進電話 , 并且嘗試以兩塊或以下的價格進行報價給前兩個話務員的話,那么他的報價不會得到話務員的認可 。
這是因為我們前面說過了,話務員們都遵循拜金主義這一潛規則 , 所以她們不會接受比已記錄的最高報價還要低的報價 。
Paxos分布式系統共識算法?我愿稱其為點歌算法…

文章插圖
在拒絕了聽眾3之后 , 我們再回到前面的兩位聽眾這邊 。
接下來 , 我們根據聽眾1和2誰先打進電話 , 把時間線劃分為兩個平行宇宙 。
平行宇宙1在平行宇宙1這條時間線里 , 我們假設聽眾1先打進電話 。
這時,仍然只有話務員2接受了聽眾1的點歌請求,于是聽眾1繼續向其他話務員撥打電話,告訴她們自己要聽的歌 。
Paxos分布式系統共識算法?我愿稱其為點歌算法…

文章插圖
在話務員3這里,她記錄的最高報價還是聽眾1之前的1塊,所以沒有意外,話務員3會接受聽眾1的點歌請求,并更新本地的記錄信息 。
但是話務員1這就不一樣了,她所認可的報價已經漲到了2,所以舊的1塊錢報價已經不能在她這里點歌了,因此話務員1會拒絕聽眾1的點歌請求 。
Paxos分布式系統共識算法?我愿稱其為點歌算法…

文章插圖
盡管請求沒有得到話務員1的接受,但是前面我們說了,話務員之間要遵循少數服從多數的原則,聽眾1的點歌請求已經被半數以上話務員接受 , 那么聽眾1確認自己點的這首《東風破》已被選定 。
平行宇宙2讓我們回到平行宇宙的分叉點 , 先回顧一下前情 , 這時聽眾2已經向話務員1和話務員2發出過報價,并從話務員2那里得知她已經以1塊錢的報價接受了《東風破》這首歌的提案 。
那么在這條時間線中,我們讓聽眾2先打給1、2號話務員 。
聽眾2這時心里會想,我們杰迷們都是有素質的人,盡管我之前想聽的是《簡單愛》 , 但聽一下《東風破》貌似也挺不錯,那么我干脆支持聽眾1的選擇吧 。
于是,報價已被認可的他再次拿起電話打給兩位話務員,發起點歌請求 。
Paxos分布式系統共識算法?我愿稱其為點歌算法…

文章插圖
話務員1和話務員2再次比較聽眾2這次攜帶的之前報價,均大于等于本地記錄的最高報價 , 所以接受他的點歌請求 。在更新本地記錄的信息后,回復信息給聽眾2 。
Paxos分布式系統共識算法?我愿稱其為點歌算法…

文章插圖
于是,聽眾2的點歌請求也獲得了半數以上話務員的承認,那么聽眾2確認自己點的歌被選定 。
看到這里 , 是不是似乎感覺世界線產生了收束,難道之后的每一種結果都是《東風破》將被選定?
其實,Paxos算法中最精彩的部分在于它更像是一場博弈 , 棋局中的每一步,都可能影響最終的結果 。
平行宇宙β讓我們把分叉點上的時間,再往前多回溯一點 , 回到下面這個時間點的狀態,這時話務員2剛接受了聽眾1的點歌請求,而聽眾2還沒有開始打熱線電話 。

推薦閱讀