文章目錄

• 拜占庭將軍問題
• Paxos
• • 問題描述
  • 執行過程
  • • Prepare階段
    • Accept階段
    • Learner獲取提案
  • 活鎖問題
• Raft
• • 狀態機
  • 執行流程
  • • 主節點選舉
    • 數據同步

---

拜占庭將軍問題

拜占庭位于如今的土耳其的伊斯坦布爾，是東羅馬帝國的首都。由于當時拜占庭羅馬帝國國土遼闊，為了達到防御目的，每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳消息。在戰爭的時候，拜占庭軍隊內所有將軍和副官必須達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內有可能存有叛徒和敵軍的間諜，叛徒可以任意行動以達到以下目標：欺騙某些將軍采取進攻行動；促成一個不是所有將軍都同意的決定，如當將軍們不希望進攻時促成進攻行動；或者迷惑某些將軍，使他們無法做出決定。如果叛徒達到了這些目的之一，則任何攻擊行動的結果都是注定要失敗的，只有完全達成一致的努力才能獲得勝利。

這時候，在已知有成員謀反的情況下，其余忠誠的將軍在不受叛徒的影響下如何達成一致的協議，拜占庭問題就此形成 。

拜占庭將軍問題的核心在于在缺少可信任的中央節點和可信任的通道的情況下，分布在不同地方的各個節點應如何達成共識。我們可以將這個問題延伸到分布式計算領域中。

在分布式計算領域中，試圖在異步系統和不可靠的通道上達到一致性狀態是不可能的，因此在對一致性的研究過程中，都往往假設信道是可靠的，而事實上，大多數系統都是部署在同一個局域網中，因此消息被篡改的情況非常罕見；另一方面，由于機器硬件和網絡原因導致的消息不完整問題，也僅僅只需要一套簡單的校驗算法即可避免。

那么當我們假設拜占庭問題不存在（所有消息都是完整的，沒有被篡改），那么這種情況下需要什么算法來保證一致性呢？拜占庭將軍問題的提出者Lamport提出了一種非拜占庭將軍問題的一致性解決方案——Paxos算法

---

Paxos

問題描述

與拜占庭將軍問題一樣，Lamport同樣使用故事的方式來提出Paxos問題

希臘島嶼Paxon上的議員在議會大廳中表決通過法律，并通過服務員傳遞紙條的方式交流信息，每個議員會將通過的法律記錄在自己的賬目上。問題在于執法者和服務員都不可靠，他們隨時會因為各種事情離開議會大廳，并隨時可能有新的議員進入議會大廳進行法律表決，使用何種方式能夠使得這個表決過程正常進行，且通過的法律不發生矛盾。

不難看出故事中的議會大廳就是分布式系統，議員對應節點或進程，服務員傳遞紙條的過程就是消息傳遞的過程，法律即是我們需要保證一致性的值。議員和服務員的進出對應著節點/網絡的失效和加入，議員的賬目對應節點中的持久化存儲設備。上面表決過程的正常進行可以表述為進展需求：當大部分議員在議會大廳呆了足夠長時間，且期間沒有議員進入或者退出，那么提出的法案應該被通過并被記錄在每個議員的賬目上。

Paxos算法需要解決的問題就是如何在上述分布式系統中，快速且正確地在集群內部對某個數據的值達成一致，并且保證不論發生以上任何異常，都不會破壞整個系統的一致性。

Paxos解決的問題

為了能夠使得表決過程正常進行，且通過的法律不發生矛盾，那么我們需要保證以下幾點

• 在這些被提出的提案中，最后只能有一個被選定
• 如果沒有提案被提出，那么就不會有被選定的提案
• 當一個提案被選定后，節點們應該可以獲取被選定的提案信息

在Paxos算法中，主要有以下三種角色，并且一個節點可能同時擔任幾種角色

• 提議者（Proposer）：負責提出提議；
• 接受者（Acceptor）：對每個提議進行投票；
• 告知者（Learner）：被告知投票的結果，不參與投票過程。

各節點之間的關系

同時，假設不同參與者之間通過收發消息來進行通信，那么我們需要具備以下條件

• 每個參與者可能會因為出錯而導致停止、重啟等情況，
• 雖然消息在傳輸過程中可能會出現不可預知的延遲、重復、丟失等情況，但是消息不會被損壞或篡改（即不存在拜占庭問題）
  
  

執行過程

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

Paxos執行過程主要分為兩個階段，與之前講過的2PC（二階段提交協議）類似。

• Prepare階段
• Accept階段

如下圖

Paxos算法流程

Prepare階段

首先，每個Proposer都會向所有的Acceptor發送一個Prepare請求。

當Acceptor接收到一個Prepare請求，提議內容為[n1,v1]，由于之前還未接受過Prepare請求，那么它會返回一個[no previous]的Prepare響應，并且設置當前接受的提議為[n1,v1]，同時保證以后不會再接收序號小于n1的提議。

如果Acceptor再次收到一個Prepare請求，提議內容為[n2,v2]，此時會有兩種情況。

• 如果n2 < n1，此時Acceptor就會直接拋棄該請求
• 如果n2 >= n1，此時Acceptor就會發送一個[n1,v1]的Prepare響應，設置當前接受到的提議為[n2,v2]，同時保證與上一步邏輯相同，保證以后不會再接受序號小于n2的提議。
  
  

Accept階段

當一個Proposer接收到超過一半的Acceptor的Prepare響應時，此時它就會發送一個針對[n,v]提案的Accept請求給Acceptor。

如果一個Acceptor收到一個編號為n的提案的Accept請求，此時有兩種情況。

• 如果該Acceptor沒有對編號大于n的Prepare請求做出過響應，它就會接受該提案，并發送Learn提議給Learner
• 如果該Acceptor接受過編號大于n的Prepare請求，那么它就會拒絕、不回應或回復error。（如果一個Proposer沒有收到過半的回應，那他就會重新進入第一階段，遞增提案號后重新提出Prepare請求）

在上述過程中，每一個Proposer都有可能會產生多個提案。但只要每個Proposer都遵循如上述算法運行，就一定能保證算法執行的正確性。

Learner獲取提案

在Accept階段之后Acceptor選定提案后，根據具體的應用場景不同，Learner主要采用以下三種方案來學習選定的提案

方案優點缺點

Acceptor直接將提議發給所有的Learner	Learner能夠快速獲取被選定的提議	通信次數過多，每個Acceptor都要和Learn產生通信（M * N）
Acceptor接受提議后將提議發給主Learner，主Learner再通知其他Learner	通信次數減少（M + N - 1）	單點問題（主Learner出現故障就會崩潰）
Acceptor將提議發一個Learner集合，Learener集合再發給其他Learener	解決了單點問題，集合中Learner個數越多就越可靠	網絡通信復雜度變高

當Learner們發現有大多數的Acceptor接受了某一個提議，那么該提議的提議值則就是Paxos最終選擇出來的結果。

活鎖問題

在Paxos算法實際運作的時候還存在這樣一種極端的情況——當有兩個Proposer依次提出了一系列編號遞增的提案，此時就會導致陷入死循環，無法完成第二階段，也就是無法選定一個提案，如以下場景。

Proposer P1發出編號為n1的Prepare請求，收到過半響應，完成了階段一的流程。

同時，Proposer P2發出編號為n2的Prepare請求（n2 > n1），也收到了過半的響應，完成了階段一的流程，并且Acceptor承諾不再接受編號小于n2的提案。

P1進入第二階段時，由于Acceptor不接受小于n2的提案，所以P1重新回到第一階段，遞增提案號為n3后重新發出Prepare請求

緊接著，P2進入第二階段，由于Acceptor不接受小于n3的提案，此時它也重新回到第一階段，遞增提案號后重新發出Prepare請求

于是P1、P2陷入了死循環，誰都無法完成階段二，這也就導致了沒有value能被選定。

為了保證Paxos算法的可持續性，以避免陷入上述提到的死循環，就必須選擇一個主Proposer，并規定只有主Proposer才能夠提出提案。這樣一來，只要主Proposer和過半的Acceptor能夠正常進行網絡通信，那么肯定會有一個提案被批準（第二階段的accept），則可以解決死循環導致的活鎖問題。

---

Raft

從上面可以看出，Paxos算法相對來說較為復雜且難以理解，因此在后來又出現了一種用于替代Paxos的算法——Raft

Raft算法是一種簡單易懂的共識算法，所謂共識，就是多個節點對某個事情達成一致的看法，即使是在部分節點故障、網絡延時、網絡分割的情況下。它依靠狀態機和主從同步的方式，在各個節點之間實現數據的一致性。

Raft算法的核心主要為以下兩部分，下面將進行具體講解

• 主節點選舉（Leader Election）
• 數據同步（Log Replication）
  
  

狀態機

在Raft中節點中存在三種狀態，狀態之間可以相互進行轉換

• Leader（主節點）

• Follower（從節點）

• Candidate（競選節點）

同時，每個節點上會存放一個倒計時器（Election Timeout），時間隨機在150ms到300ms之間。Leader節點會周期性的向所有Follower發送一個心跳包（Heartbeat），收到心跳包的節點會將其計時器清零后重新計時，如果在倒計時結束前沒有收到Leader的心跳包，此時Follower就會變為Candidate，開始進入競選狀態。

具體的狀態轉移如下圖

狀態轉換圖

執行流程

主節點選舉

介紹了狀態機后，下面就來看看主節點的選舉流程

第一步，在一開始時，由于沒有Leader，所以此時所有節點的身份都是Follower，每一個節點上都有著自己的計數器，當計時器達到了超時時間后，該節點就會轉換為Candidate，開始選舉過程。

第一步：開始選舉

第二步，成為Candidate的節點首先會給自己投一張票，然后向集群中的其他所有節點發起投票請求。

第二步：開始拉票

第三步，收到投票請求并且還未投票的Follower節點會向發起者回復投票反饋，如果收到了超過半數的回復，此時Candidate選舉成功，狀態轉變為Leader。

第三步：選舉成功

第四步，Leader節點會立刻向其他節點發出通告，告知其他節點它已成功選舉成Leader，收到通知的節點會轉換為Follower。并且Leader會周期性的發送心跳包給所有Follower來表明它還存活，當Follower接收到心跳包時，就會重置計時器。

第四步：Leader向其他節點發送通知

一旦Leader節點掛掉，它就無法發出心跳包來重置Follower的倒計時器，那么當Follower的超時時間到達后，其就會轉換成Candidate節點，再次重復以上過程。


上面介紹的是單節點的選舉，倘若同時有多個Follower同時倒計時結束后成為Candidate，同時開始選舉，并且在選舉過程中所獲得的票數相同，此時就陷入了僵局，誰都無法成為Leader。

多個Candidate選舉時出現僵局

在重新選舉時，由于每個節點設置的超時時間都是隨機的，因此下一次同時出現多個Candidate并獲得同樣票數導致選舉失敗的情況的概率則非常低。

隨機化超時時間避免沖突

數據同步

Raft中數據同步的方式與之前寫過的2PC（二階段提交協議）有一些相似，也是分為投票和提交兩個階段，具體流程如下。

第一步，客戶端將修改傳入Leader中（此時修改并沒有提交，只是寫入日志中）。

客戶端將修改傳入Leader

第二步，Leader將修改復制到集群內的所有Follower節點上，如果復制失敗，會不斷進行重試直至成功。

Leader將修改復制到所有Follower

第三步，Follow節點們成功接收到復制的數據后，會反饋結果給Leader節點，如果Leader節點接收到超過半數的Follower反饋，則表明復制成功，于是提交自己的數據，并且通知客戶端數據提交成功。

Follower接受成功后反饋結果

第四步，提交成功后，Leader會通知所有的Follower讓它們也提交修改，此時所有節點的值達成一致，完成數據同步流程。

Leader通知所有節點提交，完成數據同步

為了便于理解，可以結合下面的Raft原理動畫一同學習。

Raft原理動畫

除了上面介紹的Paxos、Raft，還有其他的一些解決分布式一致性的共識算法，如Zookeeper使用的ZAB，區塊鏈中使用的PBFT等，在未來的博客中，如果有機會我還會繼續為大家分享這些內容。

總結

以上是生活随笔為你收集整理的分布式系统概念 | 一致性协议：拜占庭将军问题、Paxos、Raft的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。