17張圖輕松搞定分布式一致性協議

兩階段提交

Two-phase Commit（2PC）：保證一個事務跨越多個節點時保持 ACID 特性；

兩類節點：協調者（Coordinator）和參與者（Participants），協調者只有一個，參與者可以有多個。

過程：

1.準備階段：協調者詢問參與者事務是否執行成功；

2.提交階段：如果事務在每個參與者上都執行成功，協調者發送通知讓參與者提交事務；否則，協調者發送通知讓參與者回滾事務。

需要注意的是，在準備階段，參與者執行了事務，但是還未提交。只有在提交階段接收到協調者發來的通知后，才進行提交或者回滾。

存在的問題

參與者發生故障。解決方案：可以給事務設置一個超時時間，如果某個參與者一直不響應，那么認為事務執行失敗。

協調者發生故障。解決方案：將操作日志同步到備用協調者，讓備用協調者接替后續工作。

Paxos

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

基于消息傳遞通信模型的分布式系統，不可避免的會發生以下錯誤：進程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重復，在基礎Paxos場景中，先不考慮可能出現消息篡改即拜占庭錯誤的情況。

Paxos算法解決的問題是在一個可能發生上述異常的分布式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議的一致性 。

主要有三類節點：

1.提議者（Proposer）：提議一個值；

2.接受者（Acceptor）：對每個提議進行投票；

3.告知者（Learner）：被告知投票的結果，不參與投票過程。

過程：

規定一個提議包含兩個字段：[n, v]，其中 n 為序號（具有唯一性），v 為提議值。

下圖演示了兩個 Proposer 和三個 Acceptor 的系統中運行該算法的初始過程，每個 Proposer 都會向所有 Acceptor發送提議請求。

當 Acceptor 接收到一個提議請求，包含的提議為 [n1, v1]，并且之前還未接收過提議請求，那么發送一個提議響應，設置當前接收到的提議為 [n1,v1]，并且保證以后不會再接受序號小于 n1 的提議。

如下圖，Acceptor X 在收到 [n=2, v=8] 的提議請求時，由于之前沒有接收過提議，因此就發送一個 [no previous] 的提議響應，并且設置當前接收到的提議為 [n=2, v=8]，并且保證以后不會再接受序號小于 2 的提議。其它的 Acceptor 類似。

如果 Acceptor 接受到一個提議請求，包含的提議為 [n2, v2]，并且之前已經接收過提議 [n1, v1]。如果 n1 >n2，那么就丟棄該提議請求；否則，發送提議響應，該提議響應包含之前已經接收過的提議 [n1, v1]，設置當前接收到的提議為 [n2,v2]，并且保證以后不會再接受序號小于 n2 的提議。

如下圖，Acceptor Z 收到 Proposer A 發來的 [n=2, v=8] 的提議請求，由于之前已經接收過 [n=4, v=5] 的提議，并且 n > 2，因此就拋棄該提議請求；Acceptor X 收到 Proposer B 發來的 [n=4, v=5] 的提議請求，因為之前接收到的提議為 [n=2, v=8]，并且 2 <= 4，因此就發送 [n=2, v=8] 的提議響應，設置當前接收到的提議為 [n=4,v=5]，并且保證以后不會再接受序號小于 4 的提議。Acceptor Y 類似。

當一個 Proposer 接收到超過一半 Acceptor 的提議響應時，就可以發送接受請求。

Proposer A 接受到兩個提議響應之后，就發送 [n=2, v=8] 接受請求。該接受請求會被所有 Acceptor 丟棄，因為此時所有Acceptor 都保證不接受序號小于 4 的提議。

Proposer B 過后也收到了兩個提議響應，因此也開始發送接受請求。需要注意的是，接受請求的 v 需要取它收到的最大 v 值，也就是 8。因此它發送[n=4, v=8] 的接受請求。

Acceptor 接收到接受請求時，如果序號大于等于該 Acceptor 承諾的最小序號，那么就發送通知給所有的 Learner。當 Learner 發現有大多數的 Acceptor 接收了某個提議，那么該提議的提議值就被 Paxos 選擇出來。

Raft

簡化，更容易理解，也更容易實現。

引入主節點，通過競選。節點類型：Follower、Candidate 和 Leader

Leader 會周期性的發送心跳包給 Follower。每個 Follower 都設置了一個隨機的競選超時時間，一般為150ms~300ms，如果在這個時間內沒有收到 Leader 的心跳包，就會變成 Candidate，進入競選階段。

流程：

① 下圖表示一個分布式系統的最初階段，此時只有 Follower，沒有 Leader。Follower A 等待一個隨機的競選超時時間之后，沒收到 Leader 發來的心跳包，因此進入競選階段。

② 此時 A 發送投票請求給其它所有節點。

③ 其它節點會對請求進行回復，如果超過一半的節點回復了，那么該 Candidate 就會變成 Leader。

④ 之后 Leader 會周期性地發送心跳包給 Follower，Follower 接收到心跳包，會重新開始計時。

多個 Candidate 競選

① 如果有多個 Follower 成為 Candidate，并且所獲得票數相同，那么就需要重新開始投票，例如下圖中 Candidate B 和 Candidate D 都獲得兩票，因此需要重新開始投票。

② 當重新開始投票時，由于每個節點設置的隨機競選超時時間不同，因此能下一次再次出現多個 Candidate 并獲得同樣票數的概率很低。

日志復制

① 來自客戶端的修改都會被傳入 Leader。注意該修改還未被提交，只是寫入日志中。

② Leader 會把修改復制到所有 Follower。

③ Leader 會等待大多數的 Follower 也進行了修改，然后才將修改提交。

④ 此時 Leader 會通知的所有 Follower 讓它們也提交修改，此時所有節點的值達成一致。

來源：qczhang

AI TCP/IP 分布式

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。