[[375586]]

 前言

分布式確實(shí)是一個(gè)有趣的話題，只要你留心觀察，分布式在生活中無(wú)處不在。

悟空哥最開始學(xué)習(xí)分布式是從一篇非常用心寫的技術(shù)征文開始的，而且這篇文章獲得了征文第一名，在此感謝掘金社區(qū)提供的平臺(tái)。

從這篇開始，將會(huì)講解分布式的八大協(xié)議/算法。本篇主要講解 Paxos 共識(shí)算法。

本文主要內(nèi)容如下：

本文主要內(nèi)容

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 算法是重中之重。

三國(guó)中的 Paxos

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

角色

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

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

劉備的帳營(yíng)中人物介紹：

• 主公一名：劉備，作為請(qǐng)求方或客戶端。
• 軍師兩名：諸葛亮、龐統(tǒng)，作為提議者。
• 武將三名：關(guān)羽、張飛、趙云，作為接受者。
• 文臣兩名：法正、馬良，作為學(xué)習(xí)者。

劉備集團(tuán)

提議者(Proposer)

• 提議一個(gè)值，用于投票表決。
• 接入和協(xié)調(diào)，收到客戶端的請(qǐng)求后，可以發(fā)起二階段提交，進(jìn)行共識(shí)協(xié)商。
• 映射到上面的故事中，軍師就是用來部署作戰(zhàn)計(jì)劃的。

接受者(Acceptor)

• 對(duì)每個(gè)提議的值進(jìn)行投票，并存儲(chǔ)接受的值。
• 投票協(xié)商和存儲(chǔ)數(shù)據(jù)，對(duì)提議的值進(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 作為接受者。

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

諸葛亮 VS 龐統(tǒng)

三國(guó)中有劉備集團(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ì)劃，該聽誰(shuí)的呢?這里就是一個(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)備請(qǐng)求，但不包含作戰(zhàn)計(jì)劃(提案值)。

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

• 提議者諸葛亮先發(fā)送編號(hào)為 1 的作戰(zhàn)計(jì)劃的準(zhǔn)備請(qǐng)求，龐統(tǒng)發(fā)送編號(hào)為 2 的作戰(zhàn)計(jì)劃的準(zhǔn)備請(qǐng)求。
• 接受者關(guān)羽(節(jié)點(diǎn) X)在8 點(diǎn)收到來自諸葛亮發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請(qǐng)求，在10 點(diǎn) 收到來自龐統(tǒng)發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請(qǐng)求。
• 接受者張飛(節(jié)點(diǎn) Y)在9 點(diǎn)收到來自諸葛亮發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請(qǐng)求，在 11 點(diǎn) 收到來自龐統(tǒng)發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請(qǐng)求。
• 接受者趙云(節(jié)點(diǎn) Z)在 12 點(diǎn) 收到來自龐統(tǒng)發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請(qǐng)求，在13 點(diǎn)收到來自諸葛亮發(fā)送的作戰(zhàn)計(jì)劃準(zhǔn)備請(qǐng)求。

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

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

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

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

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

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

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

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

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

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

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

接受階段

發(fā)送接受請(qǐng)求

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

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

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

為什么是 15 點(diǎn)過 1 分? 因?yàn)橹灰獫M足大多數(shù)接受者的準(zhǔn)備請(qǐng)求后，就可以發(fā)送接受請(qǐng)求了。關(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è)置接受請(qǐng)求中的值。因?yàn)殛P(guān)羽、張飛和趙云返回的準(zhǔn)備響應(yīng)都是尚無(wú)提案，所以還是發(fā)送提案編號(hào)為 2，提案值為南的接受請(qǐng)求，南代表從南邊進(jìn)攻曹操。發(fā)送的時(shí)間點(diǎn)是 18 點(diǎn)、19 點(diǎn)、20 點(diǎn)。

收到接受請(qǐng)求

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

接受階段-收到接受請(qǐng)求

關(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í)者登場(chǎng)

當(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ì)劃。

總結(jié)

Basic Paxos 也是通過二階段提交協(xié)議達(dá)成共識(shí)。準(zhǔn)備階段、接受階段。不知道二階段提交協(xié)議的，可以看我前面的文章。《用太極拳講分布式理論，舒服!》

Basic Paxos 不僅僅實(shí)現(xiàn)了共識(shí)，還實(shí)現(xiàn)了容錯(cuò)。有少于一半的節(jié)點(diǎn)出現(xiàn)故障時(shí)，集群也能正常工作。文中也多次強(qiáng)調(diào)了大多數(shù)節(jié)點(diǎn)都同意的原則，而這個(gè)原則賦予了 Basic Paxos 容錯(cuò)的能力。

提案編號(hào)代表優(yōu)先級(jí)，保證了三個(gè)承諾：

• 如果準(zhǔn)備請(qǐng)求的提案編號(hào)，小于等于接受者已經(jīng)響應(yīng)的準(zhǔn)備請(qǐng)求的提案編號(hào)，那么接受者將承諾不響應(yīng)這個(gè)準(zhǔn)備請(qǐng)求。
• 如果接受請(qǐng)求中的提案的提案編號(hào)，小于接受者已經(jīng)響應(yīng)的準(zhǔn)備請(qǐng)求的提案，那么接受者將承諾不通過這個(gè)提案。
• 如果接受者之前有通過提案，那么接受者將承諾，會(huì)在準(zhǔn)備請(qǐng)求的響應(yīng)中，包含已經(jīng)通過的最大編號(hào)的提案信息。

加分題

如果關(guān)羽和張飛已經(jīng)通過了提案 [2，南]，而趙云還未通過任何提案，當(dāng)?shù)谌妿熀?jiǎn)雍提出一個(gè)提案，編號(hào)為 8，作戰(zhàn)計(jì)劃為從東邊進(jìn)攻曹操，也就是 [8, 東]的作戰(zhàn)計(jì)劃，那么最終關(guān)羽、張飛、趙云的作戰(zhàn)計(jì)劃是怎么樣的?

本文轉(zhuǎn)載自微信公眾號(hào)「悟空聊架構(gòu)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系悟空聊架構(gòu)公眾號(hào)。