溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

如何掌握分布式Paxos

發(fā)布時(shí)間:2021-10-20 13:50:10 來源:億速云 閱讀:109 作者:iii 欄目:web開發(fā)

這篇文章主要講解了“如何掌握分布式Paxos”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“如何掌握分布式Paxos”吧!

Paxos 算法

Paxos 是分布式算法中的老大哥,可以說 Paxos 是分布式共識(shí)的代名詞。最常用的分布式共識(shí)算法都是基于它改進(jìn)。比如 Raft  算法(后面也會(huì)介紹)。所以學(xué)習(xí)分布式算法必須先學(xué)習(xí) Paxos 算法。

Paxos 算法主要包含兩個(gè)部分:

Basic Paxos 算法:多個(gè)節(jié)點(diǎn)之間如何就某個(gè)值達(dá)成共識(shí)。(這個(gè)值我們稱作提案 Value)

Multi-Paxos 算法:執(zhí)行多個(gè) Basic Paxos 實(shí)例,就一系列值達(dá)成共識(shí)。

Basic Paxos 算法是 Multi-Paxos 思想的核心,Multi 的意思就是多次,也就是說多執(zhí)行幾次 Basic Paxos 算法。所以  Basic Paxos 算法是重中之重。

三國中的 Paxos

三國中劉備集團(tuán),有兩大軍師:諸葛亮和龐統(tǒng),都是非常厲害的人物,當(dāng)他們有不同作戰(zhàn)計(jì)劃給多名武將時(shí),如何達(dá)成一致?

角色

Paxos 中有三種角色:提議者、接受者、學(xué)習(xí)者。

讓我們用更通俗的方式來講解 Paxos 算法。讓我們穿越回東漢末年,劉備集團(tuán)的帳營中一同學(xué)習(xí) Paxos 算法是怎么攻打曹操的。

劉備的帳營中人物介紹:

  • 主公一名:劉備,作為請求方或客戶端。

  • 軍師兩名:諸葛亮、龐統(tǒng),作為提議者。

  • 武將三名:關(guān)羽、張飛、趙云,作為接受者。

  • 文臣兩名:法正、馬良,作為學(xué)習(xí)者。

如何掌握分布式Paxos

劉備集團(tuán)

提議者(Proposer)

  • 提議一個(gè)值,用于投票表決。

  • 接入和協(xié)調(diào),收到客戶端的請求后,可以發(fā)起二階段提交,進(jìn)行共識(shí)協(xié)商。

  • 映射到上面的故事中,軍師就是用來部署作戰(zhàn)計(jì)劃的。

接受者(Acceptor)

  • 對每個(gè)提議的值進(jìn)行投票,并存儲(chǔ)接受的值。

  • 投票協(xié)商和存儲(chǔ)數(shù)據(jù),對提議的值進(jìn)行投票,并接受達(dá)成共識(shí)的值,存儲(chǔ)保存。

  • 映射到上面的故事中,武將就是用來接受軍師的作戰(zhàn)計(jì)劃。

其實(shí),集群中所有的節(jié)點(diǎn)都在扮演接受者的角色,參與共識(shí)協(xié)商,并接受和存儲(chǔ)數(shù)據(jù)。

學(xué)習(xí)者(Learner)

  • 被告知投票的結(jié)果,接受達(dá)成共識(shí)的值,存儲(chǔ)數(shù)據(jù),

  • 不參與投票的過程,即不參與共識(shí)協(xié)商。

  • 映射到上面的故事中,就是兩名文臣作為記錄作戰(zhàn)方案的備胎。

接受者 or 提議者

為什么說節(jié)點(diǎn)可以扮演接受者,也可以扮演提議者呢?

上篇我在講解 BASE 協(xié)議的時(shí)候,講到二階段提交協(xié)議。其中有一個(gè)協(xié)調(diào)者的身份,協(xié)調(diào)者既可以是接受者,也可以是提議者。

  • 作為接受者,接收客戶端的消息。比如諸葛亮需要接收劉備的作戰(zhàn)要求。

  • 作為提議者,發(fā)起二階段提交。然后這個(gè)節(jié)點(diǎn)和另外其他節(jié)點(diǎn)作為接受者進(jìn)行共識(shí)協(xié)商。比如諸葛亮要匯總最終的作戰(zhàn)計(jì)劃給劉備。

如下圖所示,節(jié)點(diǎn) 1 作為提議者和接受者,節(jié)點(diǎn) 2 和節(jié)點(diǎn) 3 作為接受者。

如何掌握分布式Paxos

節(jié)點(diǎn)既是提議者也是接受者

諸葛亮 VS 龐統(tǒng)

三國中有劉備集團(tuán)(占據(jù)西蜀)、曹操集團(tuán)(占據(jù)北邊)、孫權(quán)集團(tuán)(占據(jù)江南)。

諸葛亮和龐統(tǒng)作為提議者,向三個(gè)接受者進(jìn)作戰(zhàn)計(jì)劃的提案。提案中有兩個(gè)屬性:

提案編號(hào),每次軍師進(jìn)行提案,都會(huì)有個(gè)編號(hào),這里用 n 表示。

提議值,也就是作戰(zhàn)計(jì)劃,這里用 v 表示。所以提案就是 [n, v]。

諸葛亮的作戰(zhàn)計(jì)劃是從北邊進(jìn)攻曹操,龐統(tǒng)的作戰(zhàn)計(jì)劃是從南邊進(jìn)攻曹操,而關(guān)羽、張飛、趙云先后收到了他們的作戰(zhàn)計(jì)劃,該聽誰的呢?這里就是一個(gè)共識(shí)的問題。而  Paxos 算法達(dá)成共識(shí)分兩個(gè)階段。準(zhǔn)備(Prepare)階段和接受(Accept)階段。

準(zhǔn)備階段

諸葛亮和龐統(tǒng)作為提議者,分別向所有的接受者(關(guān)羽、張飛、趙云)發(fā)送包含作戰(zhàn)計(jì)劃編號(hào)(提案編號(hào))的準(zhǔn)備請求,但不包含作戰(zhàn)計(jì)劃(提案值)。

發(fā)送準(zhǔn)備請求

  • 提議者諸葛亮先發(fā)送編號(hào)為 1 的作戰(zhàn)計(jì)劃的準(zhǔn)備請求,龐統(tǒng)發(fā)送編號(hào)為 2 的作戰(zhàn)計(jì)劃的準(zhǔn)備請求。

  • 接受者關(guān)羽(節(jié)點(diǎn) X)在8 點(diǎn)收到來自諸葛亮發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請求,在10 點(diǎn) 收到來自龐統(tǒng)發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請求。

  • 接受者張飛(節(jié)點(diǎn) Y)在9 點(diǎn)收到來自諸葛亮發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請求,在 11 點(diǎn) 收到來自龐統(tǒng)發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請求。

  • 接受者趙云(節(jié)點(diǎn) Z)在 12 點(diǎn) 收到來自龐統(tǒng)發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請求,在13 點(diǎn)收到來自諸葛亮發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請求。

如何掌握分布式Paxos

準(zhǔn)備階段-發(fā)送準(zhǔn)備請求

注意:準(zhǔn)備階段不需要攜帶具體的作戰(zhàn)計(jì)劃,所以作戰(zhàn)計(jì)劃可以為空,但是提議編號(hào)必須有。

收到準(zhǔn)備請求(第一次)

按照接受請求的時(shí)間順序,關(guān)羽和張飛收到諸葛亮的請求[1,空],趙云收到龐統(tǒng)的請求[2,空]。

如何掌握分布式Paxos

準(zhǔn)備階段-收到準(zhǔn)備的請求(第一次)

因?yàn)殛P(guān)羽、張飛之前沒有收到提案,所以返回一個(gè)尚無提案的響應(yīng)。也就是告訴諸葛亮,不會(huì)再響應(yīng)編號(hào)小于等于 1 的準(zhǔn)備請求了,也不會(huì)通過編號(hào)小于 1  的提案。響應(yīng)的時(shí)間點(diǎn)是 14 點(diǎn)和 15 點(diǎn)。

而趙云之前也沒有收到提案,所以返回一個(gè)尚無提案的響應(yīng)。也就是告訴龐統(tǒng),不會(huì)再響應(yīng)編號(hào)小于等于 2 的準(zhǔn)備請求了,也不會(huì)通過編號(hào)小于 2  的提案。響應(yīng)的時(shí)間點(diǎn)是 16 點(diǎn)。

收到準(zhǔn)備請求(第二次)

如何掌握分布式Paxos

準(zhǔn)備階段-收到準(zhǔn)備的請求(第二次)

而對于龐統(tǒng)的準(zhǔn)備請求,關(guān)羽、張飛收到編號(hào)為 2 的準(zhǔn)備請求,而 編號(hào) 2 大于之前接受到的編號(hào) 1  ,而且關(guān)羽和張飛沒有通過任何提案,所以還是會(huì)返回給龐統(tǒng)一個(gè)尚無提案 的響應(yīng)。也就是告訴龐統(tǒng)不會(huì)再響應(yīng)編號(hào)小于等于 2 的準(zhǔn)備請求了,也不會(huì)通過編號(hào)小于 2  的提案。響應(yīng)的時(shí)間點(diǎn)是 14 點(diǎn)和 15 點(diǎn)。

而趙云最后收到諸葛亮編號(hào)為 1 的準(zhǔn)備請求后,因編號(hào) 1小于之前響應(yīng)的準(zhǔn)備請求的提案編號(hào) 2,所以直接丟棄該準(zhǔn)備請求,不做響應(yīng),如上圖的 ?  圖示。

接受階段

發(fā)送接受請求

諸葛亮和龐統(tǒng)收到準(zhǔn)備響應(yīng)后,會(huì)分別發(fā)送接受請求,如下圖所示:

如何掌握分布式Paxos

接受階段-發(fā)送接受請求

諸葛亮收到大多數(shù)接受者(關(guān)羽和張飛)的準(zhǔn)備響應(yīng)后,根據(jù)響應(yīng)中提案編號(hào)最大的提案的值,設(shè)置接受請求中的值。因?yàn)殛P(guān)羽和張飛返回的準(zhǔn)備響應(yīng)都是尚無提案,所以還是發(fā)送提案編號(hào)為  1,提案值為北的接受請求,北代表從北邊進(jìn)攻曹操。發(fā)送的時(shí)間點(diǎn)是 15 點(diǎn)過 1 分、16 點(diǎn)。

為什么是 15 點(diǎn)過 1 分? 因?yàn)橹灰獫M足大多數(shù)接受者的準(zhǔn)備請求后,就可以發(fā)送接受請求了。關(guān)羽和張飛響應(yīng)的時(shí)間點(diǎn)是 14 點(diǎn)和 15 點(diǎn),所以 15  點(diǎn)以后就可以發(fā)送了。

而龐統(tǒng)收到大多數(shù)接受者(關(guān)羽、張飛和趙云)的準(zhǔn)備響應(yīng)后,根據(jù)響應(yīng)中提案編號(hào)最大的提案的值,,設(shè)置接受請求中的值。因?yàn)殛P(guān)羽、張飛和趙云返回的準(zhǔn)備響應(yīng)都是尚無提案,所以還是發(fā)送提案編號(hào)為  2,提案值為南的接受請求,南代表從南邊進(jìn)攻曹操。發(fā)送的時(shí)間點(diǎn)是 18 點(diǎn)、19 點(diǎn)、20 點(diǎn)。

收到接受請求

當(dāng)關(guān)羽、張飛、趙云收到諸葛亮和龐統(tǒng)的接受請求后,會(huì)進(jìn)行如下處理,如下圖所示:

如何掌握分布式Paxos

接受階段-收到接受請求

關(guān)羽、張飛、趙云收到諸葛亮發(fā)送的提案 [1,北]時(shí)候,因?yàn)樘岚妇幪?hào) 1小于他們承諾的能通過的提案的最小提案編號(hào) 2,所以諸葛亮的提案被拒絕了。

而當(dāng)他們收到龐統(tǒng)的發(fā)送的提案 [2,南] 的時(shí)候,因?yàn)榫幪?hào) 2 不小于之前承諾的編號(hào) 2,所以通過龐統(tǒng)的提案 [2,南]  ,所以關(guān)羽、張飛、趙云他們的作戰(zhàn)計(jì)劃是從南邊進(jìn)攻曹操。達(dá)成了共識(shí)。

學(xué)習(xí)者登場

當(dāng)接受者通過了一個(gè)提案時(shí),就通知所有的學(xué)習(xí)者。當(dāng)學(xué)習(xí)者發(fā)現(xiàn)大多數(shù)的接受者都通過了某個(gè)提案,那么學(xué)習(xí)者也會(huì)通過該提案,接受該提案的值。

也就是說關(guān)羽、張飛、趙云達(dá)成了共識(shí)后,學(xué)習(xí)者法正和馬良也同樣通過從南邊進(jìn)攻的作戰(zhàn)計(jì)劃。

感謝各位的閱讀,以上就是“如何掌握分布式Paxos”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對如何掌握分布式Paxos這一問題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!

向AI問一下細(xì)節(jié)

免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI