諸葛 VS 龐統,拿下 Paxos 共識演算法
前言
分散式確實是一個有趣的話題,只要你留心觀察,分散式在生活中無處不在。
悟空哥最開始學習分散式是從一篇非常用心寫的技術徵文開始的,而且這篇文章獲得了徵文第一名,在此感謝掘金社區提供的平台。想學習的同學可以點這個文章鏈接:《這三年被分散式坑慘了,曝光十大坑》
前兩講主要是講解分散式理論,涉及到了分散式的四大理論。
拜占庭將軍問題:《用三國殺講分散式演算法,舒適了吧?》
BASE、CAP、ACID:《用太極拳講分散式理論,舒服!》
從這篇開始,將會講解分散式的八大協議/演算法。本篇主要講解 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, 東]
的作戰計劃,那麼最終關羽、張飛、趙雲的作戰計劃是怎麼樣的?歡迎評論區留言。
我是悟空,努力變強,變身超級賽亞人!手寫了一套 Spring Cloud 進階教程和 PMP 刷題小程式。歡迎關注公眾號:
悟空聊架構