distributed consensus - paxos

來自專欄 Time is an illusion6 人贊了文章

分散式系統中的節點通信存在兩種模型：共享內存（Shared memory）和消息傳遞（Messages passing）。

基於消息傳遞通信模型的分散式系統，不可避免的會發生以下錯誤：進程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重複，在基礎 Paxos 場景中，先不考慮可能出現消息篡改即拜占庭錯誤的情況。Paxos 演算法解決的問題是在一個可能發生上述異常的分散式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議的一致性。

拜占庭將軍問題

拜占庭將軍問題是 Leslie Lamport 在The Byzantine Generals Problem論文中提出的分散式領域的容錯問題，它是分散式領域中最複雜、最嚴格的容錯模型。

拜占庭將軍問題描述了一個如下場景：

一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題，將各支軍隊的行動策略限定為進攻或撤離兩種。因為部分軍隊進攻部分軍隊撤離可能會造成災難性後果，因此各位將軍必須通過投票來達成一致策略，即所有軍隊一起進攻或所有軍隊一起撤離。因為各位將軍分處城市不同方向，他們只能通過信使互相聯繫。在投票過程中每位將軍都將自己投票給進攻還是撤退的信息通過信使分別通知其他所有將軍，這樣一來每位將軍根據自己的投票和其他所有將軍送來的信息就可以知道共同的投票結果而決定行動策略。

https://zh.wikipedia.org/wiki/拜占庭將軍問題

系統的問題在於，將軍中可能出現叛徒，他們不僅可能向較為糟糕的策略投票，還可能選擇性地發送投票信息。假設有9位將軍投票，其中1名叛徒。8名忠誠的將軍中出現了4人投進攻，4人投撤離的情況。這時候叛徒可能故意給4名投進攻的將領送信表示投票進攻，而給4名投撤離的將領送信表示投撤離。這樣一來在4名投進攻的將領看來，投票結果是5人投進攻，從而發起進攻；而在4名投撤離的將軍看來則是5人投撤離。這樣各支軍隊的一致協同就遭到了破壞。

由於將軍之間需要通過信使通訊，叛變將軍可能通過偽造信件來以其他將軍的身份發送假投票。而即使在保證所有將軍忠誠的情況下，也不能排除信使被敵人截殺，甚至被敵人間諜替換等情況。因此很難通過保證人員可靠性及通訊可靠性來解決問題。

上述的故事映射到計算機系統里，將軍便成了計算機，而信差就是通信系統。拜占庭將軍問題描述的就是某些成員計算機或網路鏈路出現錯誤、甚至被蓄意破壞者控制的情況。

Paxos/Raft

Paxos 和 Raft 是目前分散式系統領域中兩種非常著名的解決一致性問題的共識演算法，兩者都能解決分散式系統中的一致性問題，但是前者的實現與證明非常難以理解，後者的實現比較簡潔並且遵循人的直覺，它的出現就是為了解決 Paxos 難以理解並和難以實現的問題。

There is only one consensus protocol, and that』s Paxos」 – all other approaches are just broken versions of Paxos.

世界上只有一種一致性協議，就是Paxos，其它一致性演算法都是Paxos演算法的不完整版本。

無論是 Paxos 還是 Raft 其實都只能解決非拜占庭將軍容錯的一致性問題，不能夠應對分散式網路中出現的極端情況，但是這在傳統的分散式系統都不是什麼問題，無論是分散式資料庫還是消息隊列集群，它們內部的節點並不會故意的發送錯誤信息，在類似系統中，最常見的問題就是節點失去響應或者失效，所以它們在這種前提下是有效可行的，也是充分的。

POW(區塊鏈中的工作量證明演算法)

Proof-of-work system?

en.wikipedia.org

POW（Proof-of-Work）是一個用於阻止拒絕服務攻擊和類似垃圾郵件等服務錯誤問題的協議，它在 1993 年被 Cynthia Dwork 和 Moni Naor 提出，它能夠幫助分散式系統達到拜占庭容錯。

Paxos - The Consensus Algorithm

paxos其實是個很容易理解的演算法，建議直接讀原文：https://lamport.azurewebsites.net/pubs/paxos-simple.pdf

1. paxos中的角色

假設分散式系統一組節點想要對某個Value(共享值)達成一致，Paxos把節點分為三種角色：proposers，acceptors，和 learners（每個節點可以身兼多種角色）

• Proposer: 可以提出新的Value(共享值)。
• Proposal: Proposer提出新的Value，稱作一個提案。
• Acceptor: 對Proposal進行投票表決。
• Learner：無投票權，從Learner那裡得知哪個Proposal被選中。

2. paxos的特點

在非拜占庭錯誤的條件下，paxos可以實現如下幾點：

• 一個或多個節點可以提出Proposal
• 系統必須針對所有提案中的某個Proposal達成一致 (超過半數的Acceptor同意該提案)
• 最多只能對一個確定的Proposal達成一致
• 只要超半數的節點存活並且可互相通信，整個系統就能達成一致狀態，即選擇一個確定的Proposal

3. paxos的實現過程

Paxos達成共識分成兩個階段：Prepare階段和Accept階段。

Prepare階段

• (a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
• (b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

Accept階段

• (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an acceptrequest to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
• (b) If an acceptor receives an accept request for a proposal numberedn, it accepts the proposal unless it has already responded to a preparerequest having a number greater than n.

4. paxos實現過程圖解

假設現在有五個節點的分散式系統，此時 A 節點打算提議 X 值，E 節點打算提議 Y 值，其他節點沒有提議。

假設現在 A 節點廣播它的提議（也會發送給自己），由於網路延遲的原因，只有 A，B，C 節點收到了。注意即使 A，E 節點的提議同時到達某個節點，它也必然有個先後處理的順序，這裡的「同時」不是真正意義上的「同時」。

A，B，C接收提議之後，由於這是第一個它們接收到的提議，acceptedProposal 和 acceptedValue 都為空。

由於 A 節點已經收到超半數的節點響應，且返回的 acceptedValue 都為空，也就是說它可以用 X 作為提議的值來發生 Accept 請求，A，B，C接收到請求之後，將 acceptedValue 更新為 X。

A，B，C 會發生 minProposal 給 A，A 檢查發現沒有大於 1 的 minProposal 出現，此時 X 已經被選中。等等，我們是不是忘了D，E節點？它們的 acceptedValue 並不是 X，系統還處於不一致狀態。至此，Paxos 過程還沒有結束，我們繼續看。

此時 E 節點選擇 Proposal ID 為 2 發送 Prepare 請求，結果就和上面不一樣了，因為 C 節點已經接受了 A 節點的提議，它不會三心二意，所以就告訴 E 節點它的選擇，E 節點也很紳士，既然 C 選擇了 A 的提議，那我也選它吧。於是，E 發起 Accept 請求，使用 X 作為提議值，至此，整個分散式系統達成了一致，大家都選擇了 X。

參考鏈接：