分布式一致性演算法，你確定不了解一下？

• 集中式與分布式
  • 集中式
  • 分布式
  • 分布式事務
• 一致性協議
  • 2PC：Two-Phase Commit二階段提交協議
  • 3PC:Three-phase Commit 三階段提交協議
  • Paxos演算法
  • RAFT演算法
• 總結

集中式與分布式

集中式

就是將所有的業務都部署在一個中心主機（節點）上，所有的功能都由這個主機集中處理，

特點

部署結構簡單、不需要考慮多個主機之間的分布式協作問題，

分布式

分布式系統：指將硬體或者軟體組件部署在不同的網路計算機上，彼此之間僅僅通過訊息傳遞進行通信和協調的系統，

特點

1. 分布性：多臺計算機可空間上隨意分布，跨機房、跨城市都可以，
2. 對等性：分布式系統中沒有主/從之分，都是對等的節點或者服務，
   • 副本：指分布式系統對資料或服務冗余，以此提供高可用，
   • 資料副本：是指在不同的節點上持久化一份資料，當某一個節點上存盤的資料丟失時，可以從副本上讀取到該資料，這是分布式系統資料丟失問題最為有效的手段，
   • 服務副本：指多個節點提供同樣的服務，每個節點都有能力接收來自外部的請求并進行相應的處理，
3. **并發性：**分布式系統中的多個節點，可能會并發地操作一些共享資源，諸如資料庫或分布式存盤等，
4. **缺乏全域時鐘：**一個典型的分布式系統是由一系列在空間上隨意分布的行程組成，行程彼此之間通過訊息進行通信，因此，無法判斷兩個事件誰先誰后，可使用邏輯時鐘，
5. **故障總是會發生：**除非需求指標允許，在系統設計時不能放過任何例外情況，如宕機、網路磁區、網路超時等，

每一次分布式系統的請求與回應三態：成功，失敗，超時，

超時情況：

1. 沒有成功發送到接收方，在發送程序中發生資訊丟失，
2. 成功發送到接收方，并成功處理，但回傳給發送方程序中發生資訊丟失，

所以需要有冪等，

分布式事務

分布式事務是指事務的參與者，支持事務的服務器，資源服務器以及事務管理器分別位于分布式系統的**不同節點之上，**通常一個分布式事務中會涉及對多個資料源或業務系統的操作，分布式事務也可以被定義為一種嵌套型的事務，同時也就具有了ACID事務的特性，

CAP理論

• Consistency(一致性)：資料一致更新，所有資料變動都是同步的（強一致性），

• Availability(可用性)：好的回應性能

• Partition tolerance(磁區容錯性) ：可靠性

磁區容錯性：分布式系統在遇到任何網路磁區故障的時候，任然需要保證對外提供滿足一致性和可用性的服務，除非是整個網路環境都發生了故障，

網路磁區：是指在分布式系統中，不同的節點分布在不同的子網路（機房或異地網路等）中，由于一些特殊的原因導致這些子網路之間出現網路不連通的狀況，但各個子網路的內部網路是正常的，從而導致整個網路的環境被切成了若干個孤立的區域，

定理：任何分布式系統只可同時滿足二點，沒法三者兼顧，

需要根據實際業務進行取舍，

• CA系統（放棄P）：指將所有資料（或者僅僅是那些與事務相關的資料）都放在一個分布式節點上，就不會存在網路磁區，所以強一致性以及可用性得到滿足，
• CP系統（放棄A）：如果要求資料在各個服務器上是強一致的，然而網路磁區會導致同步時間無限延長，那么如此一來可用性就得不到保障了，堅持事務ACID（原子性、一致性、隔離性和持久性）的傳統資料庫以及對結果一致性非常敏感的應用通常會做出這樣的選擇，
• AP系統（放棄C）：這里所說的放棄一致性，并不是完全放棄資料一致性，而**是放棄資料的強一致性，而保留資料的最終一致性，**如果即要求系統高可用又要求磁區容錯，那么就要放棄一致性了，因為一旦發生網路磁區，節點之間將無法通信，為什么滿足高可用，每個節點只能用本地資料提供服務，這樣就會導致資料不一致，一些遵守BASE原則資料庫，（如：Cassandra、CouchDB等）往往會放寬對一致性的要求（滿足最終一致性即可），一次來獲取基本的可用性，

BASE理論

• Basically Available基本可用：指分布式系統在出現不可預知的故障的時候，允許損失部分可用性——但不是系統不可用，
  • 回應時間上的損失：假如正常一個在線搜索0.5秒之內回傳，但由于故障（機房斷電或網路不通），查詢結果的回應時間增加到1—2秒，
  • 功能上的損失：如果流量激增或者一個請求需要多個服務間配合，而此時有的服務發生了故障，這時需要進行服務降級，進而保護系統穩定性，
• Soft state軟狀態：允許系統在不同節點的資料副本之間進行資料同步的程序存在延遲，
• Eventually consistent最終一致：最終資料是一致的就可以了，而不是時時高一致，

BASE思想主要強調基本的可用性，如果你需要High 可用性，也就是純粹的高性能，那么就要以一致性或容錯性為犧牲，

一致性協議

一致性協議：為了使基于分布式系統架構下的所有節點進行事務處理程序中能夠保持原子性和一致性而設計的一種演算法，通常有二階段提交協議、三階段提交協議、Paxos、Zookeeper的ZAB協議、Raft、Pbft等，

2PC、3PC引入了兩個概念，

**協調者：**負責統一調度分布式節點的執行邏輯

參與者：被調度的分布式節點

2PC：Two-Phase Commit二階段提交協議

二階段主要采取：先嘗試，后提交，

2PC優缺點

• 二階段優點：原理簡單，實作方便；解決分布式事務的原子性，要么全部執行成功，要么全部執行失敗
• 二階段缺點：
  1. 同步阻塞：在提交執行程序中，各個參與者都在等待其他參與者回應的程序中，將無法執行其他操作，
  2. 單點問題：只有一個協調者，協調者掛掉，整個二階段提交流程無法執行；更為嚴重是，在階段二時，協調者出現問題，那參與者將會一直處于鎖定事務狀態中，無法繼續完成事務操作，
  3. 資料不一致：在階段二，協調者發送了Commit請求后，發生了網路故障，導致只有部分參與者收到commit請求，并執行提交操作，就導致資料不一致問題，
  4. 太過保守：階段一中，若參與者出現故障，協調者無法收到參與者的詢問反饋，只能通過自身超時機制來中斷事務，這樣的策略顯得過于保守，

3PC:Three-phase Commit 三階段提交協議

因為2PC有很多問題，所以在2PC基礎上，改進為3PC：canCommit、preCommit、doCommit三個階段，

改進點：

1. 3PC是將2PC的第一階段分為兩個階段，先發起事務詢問，再執行事務，
2. 同時在協調者、參與者中引入超時機制，

3PC-第一階段 3PC-事務中斷1 3PC-第三階段 3PC-事務中斷2

3PC優缺點

• 三階段優點：

  • 降低了二階段的同步阻塞范圍（在第二階段，只要參與者收到preCommit請求，就會執行事務，此后，不管能不能收到協調者的doCommit請求,都會執行事務提交，不會出現阻塞問題）
  • 解決單點問題：進入階段三會出現兩種情況： 1：協調者出現問題； 2：協調者與參與者之間出現網路故障；
    • 都導致參與者無法收到doCommit請求，但參與者在超時之后都會提交事務

• 三階段缺點：

  • 資料不一致：參與者收到preCommit請求，此時如果出現網路磁區，協調者與參與者之間無法進行正常網路通信，參與者在超時之后還是會進行事務提交，就會出現資料不一致，

所以2PC、3PC各有優缺點，可根據實際業務場景進行選擇，既然2PC、3PC都會產生資料不一致，下面我們來看一看分布式領域常用的一致性演算法，

Paxos演算法

Paxos演算法是萊斯利·蘭伯特(Leslie Lamport)1990年提出的基于訊息傳遞且具有高度容錯特性的一致性演算法，是目前公認的解決分布式一致性問題最有效的演算法之一， Paxos演算法解決的問題是一個分布式系統如何就某個值（決議）達成一致，

Paxos以及下面的RAFT都假設不存在拜占庭將軍問題，只考慮節點宕機、網路磁區、訊息不可靠等問題，屬于CFT（Crash Fault Tolerance）演算法，

系統中有三種角色proposers，acceptors，和 learners，可以一個節點多個角色，

1. proposers 提出提案，提案資訊包括提案編號和提議的 value；
2. acceptor 收到提案后可以接受（accept）提案，若提案獲得多數派（majority）的 acceptors 的接受，則稱該提案被批準（chosen）；
3. learners 只能“學習”被批準的提案，

多數派：指 n / 2 +1 ，n為總節點數量，

Paxos演算法分為兩個階段，具體如下：

• 階段一：

  • Proposer選擇一個提案編號N，然后向半數以上的Acceptor發送編號為N的Prepare請求，

  • 如果一個Acceptor收到一個編號為N的Prepare請求，且N大于該Acceptor已經回應過的所有Prepare請求的編號，那么它就會將它已經接受過的編號最大的提案（如果有的話）作為回應反饋給Proposer，同時該Acceptor承諾不再接受任何編號小于N的提案，

    例如：一個acceptor已經回應過的所有prepare請求對應的提案編號分別為1、2、，，，，5和7，那么該acceptor在接收到一個編號為8的prepare請求后，就會將編號為7的提案作為回應反饋給Proposer，

• 階段二

  • 如果Proposer收到半數以上Acceptor對其發出的編號為N的Prepare請求的回應，那么它就會發送一個針對**[N,V]提案的Accept請求給半數以上的Acceptor，注意：V就是階段一收到的回應中編號最大的提案的value**，如果回應中不包含任何提案，那么V就由Proposer自己決定（任意值），
  • 如果Acceptor收到一個針對編號為N的提案的Accept請求，只要該Acceptor沒有對編號大于N的Prepare請求做出過回應，它就接受該提案，

注意：Proposer可以隨時丟棄提案，并且提出新的提案；Acceptor也可以隨時回應，接受編號更大的提案，

思考：如果兩個Proposer還處于第一階段時，互相提出編號更大的提案？會發生什么？

這時候會出現“活鎖”狀態，陷入了無限死回圈中（破壞了演算法活性），

那需要怎么防止呢？

可以選出一個主Proposer，只有主Proposer可以提出提案，

至于怎么選擇，不屬于Paxos的范疇，可以參考RAFT使用競選，誰快誰當選；也可以參考PBFT的依次成為leader等，

RAFT演算法

RAFT演算法分為兩個階段：Leader選舉，日志復制，也有三種角色，分別為：

1. Leader（領導者）：負責發送要進行共識的資料，如果客戶端發送的資料不是發送到Leader而是其他角色，其他角色會進行轉發至Leader，
2. Follower（追隨者）：參與共識的角色
3. Candidate（候選者）：如果Follower沒有收到Leader的心跳回應超過150——300ms，會進行Leader選舉，

每個節點的身份都可以是以上三種中的其一，

• Leader選舉階段：

  • 所有節點初始狀態為Follower狀態，此時沒有Leader，肯定會與Leader的心跳超時（一般150——300ms，隨機的，這樣就是想誰先發出競選，誰當選leader），此時Candidate就會發出leader競選給其他節點（大家快選我啊，leader掛掉了）；其他節點收到競選請求，會回應同意，當一個Candidate收到大多數（n/2 + 1）節點的回復，就成為leader，然后與Candidate保持心跳連接，Raft有個Term（任期）的概念，只有在發生Leader選舉階段，term+1，表示新的leader產生，掛掉的節點，或者掛掉的leader重啟后，會發現自己的term小于最新的，此時就會切換到日志復制，去同步之前丟失的訊息，
  • 如果同時有多個Candidate發出競選，并且都沒有獲得大多數投票，會一直進行競選，直到選出leader

• 日志復制（是一個2PC提交）

  • leader收到客戶端或者其他節點轉發過來需要共識的值，會跟隨心跳一起廣播給其他節點，進行寫入
  • 其他節點寫入后回應成功給leader，當leader收到大多數的follower回應的成功，發出commit命令
  • 其他節點收到commit后，進行事務提交，回應成功為leader，leader收到大多數的commit成功，Raft完成，

  如果leader沒有掛掉，或者發生網路磁區，就會一直是這個leader進行事務發起，

我這里只是對于演算法正常流程的描述，強烈推薦影片版RAFT（看不懂算我輸，不過記得回來點個贊，哈哈哈）

總結

本文從集中式到分布式理論CAP、BASE以及2PC、3PC流程，描述了分布式事務常用的思想；再詳細說明了Paxos以及Raft演算法流程等，Paxos以及Raft演算法屬于CFT演算法范疇，都能容忍最多n/2（向下取整）的節點出現宕機、網路磁區等的強一致性演算法，Paxos屬于比較晦澀的演算法，工程實作比較復雜，但其思想很有借鑒意義，有興趣的可以去看看Paxos的推導程序，個人認為很有意思，能夠想明白每一步，對于理解其他演算法，也大有幫助；也可以去看看Zookeerper的ZAB演算法，后面有機會專門寫一篇，但這些演算法不能真正意義上用于區塊鏈共識，畢竟leader說什么，其他節點就會執行，沒有節點之間的共識程序，那什么演算法可以用于區塊鏈共識呢？

參考書籍：

《從Paxos到Zookeeper++分布式一致性原理與實踐++》

參考鏈接：

PAXOS演算法

RAFT影片版

本文使用 mdnice 排版

標籤：區塊鏈

上一篇：北斗同步時鐘（主時鐘控制器）應用于電氣化鐵道遠動系統

下一篇：Substrate開發者檔案入口收藏