[[375586]]

 前言

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

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

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

本文主要內容如下：

本文主要內容

Paxos 算法

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

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

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

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

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

三國中的 Paxos

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

角色

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

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

劉備的帳營中人物介紹：

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

劉備集團

提議者(Proposer)

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

接受者(Acceptor)

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

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

學習者(Learner)

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

接受者 or 提議者

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

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

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

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

節點既是提議者也是接受者

諸葛亮 VS 龐統

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

諸葛亮和龐統作為提議者，向三個接受者進作戰計劃的提案。提案中有兩個屬性：

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

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

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

準備階段

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

發送準備請求

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

準備階段-發送準備請求

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

收到準備請求(第一次)

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

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

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

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

收到準備請求(第二次)

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

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

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

接受階段

發送接受請求

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

接受階段-發送接受請求

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

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

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

收到接受請求

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

接受階段-收到接受請求

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

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

學習者登場

當接受者通過了一個提案時，就通知所有的學習者。當學習者發現大多數的接受者都通過了某個提案，那么學習者也會通過該提案，接受該提案的值。

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

總結

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

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

提案編號代表優先級，保證了三個承諾：

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

加分題

如果關羽和張飛已經通過了提案 [2，南]，而趙云還未通過任何提案，當第三名軍師簡雍提出一個提案，編號為 8，作戰計劃為從東邊進攻曹操，也就是 [8, 東]的作戰計劃，那么最終關羽、張飛、趙云的作戰計劃是怎么樣的?

本文轉載自微信公眾號「悟空聊架構」，可以通過以下二維碼關注。轉載本文請聯系悟空聊架構公眾號。