[[375586]]

 前言

分布式確實是一個有趣的話題，只要你留心觀察，分布式在生活中無處不在。

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

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

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

本文主要內(nèi)容

Paxos 算法

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

Paxos 算法主要包含兩個部分：

Basic Paxos 算法：多個節(jié)點之間如何就某個值達成共識。(這個值我們稱作提案 Value)

Multi-Paxos 算法：執(zhí)行多個 Basic Paxos 實例，就一系列值達成共識。

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

三國中的 Paxos

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

角色

Paxos 中有三種角色：提議者、接受者、學習者。

讓我們用更通俗的方式來講解 Paxos 算法。讓我們穿越回東漢末年，劉備集團的帳營中一同學習 Paxos 算法是怎么攻打曹操的。

劉備的帳營中人物介紹：

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

劉備集團

提議者(Proposer)

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

接受者(Acceptor)

• 對每個提議的值進行投票，并存儲接受的值。
• 投票協(xié)商和存儲數(shù)據(jù)，對提議的值進行投票，并接受達成共識的值，存儲保存。
• 映射到上面的故事中，武將就是用來接受軍師的作戰(zhàn)計劃。

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

學習者(Learner)

• 被告知投票的結(jié)果，接受達成共識的值，存儲數(shù)據(jù)，
• 不參與投票的過程，即不參與共識協(xié)商。
• 映射到上面的故事中，就是兩名文臣作為記錄作戰(zhàn)方案的備胎。

接受者 or 提議者

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

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

• 作為接受者，接收客戶端的消息。比如諸葛亮需要接收劉備的作戰(zhàn)要求。
• 作為提議者，發(fā)起二階段提交。然后這個節(jié)點和另外其他節(jié)點作為接受者進行共識協(xié)商。比如諸葛亮要匯總最終的作戰(zhàn)計劃給劉備。

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

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

諸葛亮 VS 龐統(tǒng)

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

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

提案編號，每次軍師進行提案，都會有個編號，這里用 n 表示。

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

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

準備階段

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

發(fā)送準備請求

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

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

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

收到準備請求(第一次)

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

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

因為關(guān)羽、張飛之前沒有收到提案，所以返回一個尚無提案的響應。也就是告訴諸葛亮，不會再響應編號小于等于 1 的準備請求了，也不會通過編號小于 1 的提案。響應的時間點是 14 點和 15 點。

而趙云之前也沒有收到提案，所以返回一個尚無提案的響應。也就是告訴龐統(tǒng)，不會再響應編號小于等于 2 的準備請求了，也不會通過編號小于 2 的提案。響應的時間點是 16 點。

收到準備請求(第二次)

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

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

而趙云最后收到諸葛亮編號為 1 的準備請求后，因編號 1小于之前響應的準備請求的提案編號 2，所以直接丟棄該準備請求，不做響應，如上圖的 ? 圖示。

接受階段

發(fā)送接受請求

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

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

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

為什么是 15 點過 1 分? 因為只要滿足大多數(shù)接受者的準備請求后，就可以發(fā)送接受請求了。關(guān)羽和張飛響應的時間點是 14 點和 15 點，所以 15 點以后就可以發(fā)送了。

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

收到接受請求

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

接受階段-收到接受請求

關(guān)羽、張飛、趙云收到諸葛亮發(fā)送的提案 [1，北]時候，因為提案編號 1小于他們承諾的能通過的提案的最小提案編號 2，所以諸葛亮的提案被拒絕了。

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

學習者登場

當接受者通過了一個提案時，就通知所有的學習者。當學習者發(fā)現(xiàn)大多數(shù)的接受者都通過了某個提案，那么學習者也會通過該提案，接受該提案的值。

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

總結(jié)

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

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

提案編號代表優(yōu)先級，保證了三個承諾：

• 如果準備請求的提案編號，小于等于接受者已經(jīng)響應的準備請求的提案編號，那么接受者將承諾不響應這個準備請求。
• 如果接受請求中的提案的提案編號，小于接受者已經(jīng)響應的準備請求的提案，那么接受者將承諾不通過這個提案。
• 如果接受者之前有通過提案，那么接受者將承諾，會在準備請求的響應中，包含已經(jīng)通過的最大編號的提案信息。

加分題

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

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