概覽分布式一致性協(xié)議和算法 2PC 3PC 拜占庭將軍問題 Paxos ZAB Raft

拜占庭將軍問題

byzantine https://www.jianshu.com/p/8bcef0ca676c

拜占庭問題，假設節(jié)點總數是N，叛徒節(jié)點數為F。如果需要達成一致性的認識，則當 N 》= 3F+1 時，問題才有解，共識才能達成，這就是Byzantine Fault Tolerant（BFT）算法。

Quorum NRW系統(tǒng)一致性策略

N: 分布式系統(tǒng)的副本總數
R: 讀操作需要參與確認的最少副本數
W: 寫操作需要參與確認的最少副本數
若 R+W>N，那么系統(tǒng)可以保證強一致性；
若 R=1, W=N，適用于頻繁讀、對讀性能要求低，對寫性能要求高的系統(tǒng)；
若 R=N, W=1，適用于頻繁寫、對讀性能要求低，對寫性能要求高的系統(tǒng)；
R=W=ceil(N/2), 讀寫性能平衡。

分布式事務協(xié)議 2PC 3PC

2pc 3pc https://blog.csdn.net/skyie53101517/article/details/80741868

2PC(2 Phase Commit)

• 角色：coordinator協(xié)調者, participants參與者

1. 事務請求階段（commit-request stage)
   c–request–>p
   p: lock resource, undo redo
   p – ack / no–> c
2. 提交階段
   c --commit / abort --> p
   p – ack ->c

• 問題：
  1. c單點故障
  2. 各節(jié)點事務性阻塞
  3. 數據不一致
     • 腦裂：協(xié)調者在發(fā)出commit消息之后宕機，如果只有部分參與者接收并執(zhí)行了Commit請求,會導致節(jié)點數據不一致。如果這些接受到Commit消息的部分參與者也都宕機，那么即使協(xié)調者通過選舉協(xié)議產生了新的協(xié)調者，這條事務的狀態(tài)也是不確定的，沒人知道事務是否被已經提交。

3PC

• 角色：coordinator協(xié)調者, participants參與者
  1.CanCommit Stage
  c–CanCommit–>p
  p – ack / reject --> c

2. PreCommit
   c–PreCommit–>p
   p: lock resource, undo redo
   p – ack / no–> c (if timeout, c sends abort request in 3rd stage)
3. DoCommit
   c --commit / abort --> p (if timeout, p commit)
   p – ack ->c

• 相比2PC特點：
  1. c, p端都引入超時機制, 解決單點故障， 各節(jié)點事務性阻塞
  2. 數據不一致
     • 由于網絡原因，協(xié)調者發(fā)送的abort響應沒有及時被參與者接收到，那么參與者在等待超時之后執(zhí)行了commit操作。這樣就和其他接到abort命令并執(zhí)行回滾的參與者之間存在數據不一致的情況。

So, here is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. --Mike Burrows

狀態(tài)機副本集和分布式主備系統(tǒng)

state machine replication vs primary-backup https://www.jianshu.com/p/4dcf3325269d

State Machine

• 狀態(tài)機：一組狀態(tài)之間的轉換關系。帶狀態(tài)的，（用函數式編程的說法是非函數式的）
• InitialState – Commandx --> StateA – Commandy --> StateB…
• 狀態(tài)機的輸出依賴于當前的輸入（命令）和歷史的輸入
• 狀態(tài)機是確定性的，在給定兩次運行的情況下，它接收到相同的請求序列，它總是進行相同的內部狀態(tài)轉換并產生相同的回復。

分布式系統(tǒng)模型

分布式系統(tǒng)模型：

• 在一個由一組進程 {P1, P2, …, Pn}組成的分布式系統(tǒng)中，其每個進程都有各自的存儲設備，進程間通過相互通信來實現(xiàn)消息的傳遞。
• 每個進程隨時有可能崩潰退出(進入DOWN狀態(tài))，在退出后還有可能再次加入(重新進入UP狀態(tài))。
• 每個進程持有的上下文即為進程的狀態(tài)，這樣的進程可以視為一個狀態(tài)機，分布式系統(tǒng)可視為分布式的狀態(tài)機。

分布式系統(tǒng)間的同步方式

• 同步操作
  操作必須是確定性的，如跟時間、隨機數相關的的操作就會導致各節(jié)點操作的結果不一致。
• 同步操作后的值
  操作先作用到Primary節(jié)點上，即使操作本身是不確定的，但結果的值是確定的。其他節(jié)點同步操作后的值，數據具有一致性。
  進階：如果數據值本身比較大，同步值的做法IO代價較高?？梢栽趐rimary節(jié)點將非確定的操作的確定實現(xiàn)同步，譬如，同步操作ADD Random()，隨機值為ADD 2

Primary-backup

• 同步操作后的值（傳統(tǒng)狀態(tài)機副本集同步操作）

Paxos

https://www.jianshu.com/p/06a477a576bf

• 角色： Proposer, Acceptor, Learner
• 原則：
  1.prepare | promise stage
  - Acceptor 回復（promise)收到的第一個proposal或大于當前接受proposal編號的proposal

2. Accept stage
   - Proposer 獲得大多數（過半數）Acceptor 的promise則向回復promise的Acceptor發(fā)送accept請求
3. 其他Learner學習 Acceptor的結果

ZAB(Zookeeper Atomic Broadcast)協(xié)議

zab https://www.cnblogs.com/wttttt/p/7500663.html

zookeeper 分布式協(xié)調服務，是一種分布式主備系統(tǒng)。Primary Order.

• 角色：leader, follower

1. Broadcast stage

   • 消息廣播過程使用的是一個原子廣播協(xié)議，類似于一個二階段提交過程。
   • leader server會為每個follower分配一個單獨的隊列(基于具有FIFO特性的TCP協(xié)議)，事務的有序性質（Int64 ZXID,high32 for epoch/term, low 32 increment id)
   • 過半數的follower反饋Ack之后就可以提交事務Proposal

2. Recovery

   1. Discover
      • 【大家公示信息、投票】leader選舉: 各個節(jié)點廣播自己事務proposal的最大ZXID, 同時接受其他節(jié)點的廣播。若發(fā)現(xiàn)更大的ZXID廣播（比自己或其他節(jié)點），則向廣播發(fā)出節(jié)點ack，否則。 選舉出來的leader服務器擁有集群中所有機器最高編號(即ZXID最大)的事務proposal
   2. Sync
   • follower節(jié)點同步新的leader

Raft

raft https://www.jianshu.com/p/8e4bbe7e276c
動畫演示： http:///raft/

• 角色： Follower，Candidate，Leader
• 過程

1. 選主 Leader Election
   • 【自薦、拉票階段】各個節(jié)點Vote：Follower timer timeout --> candidate --> self vote —> request other nodes to vote
   • 收到過半數的ack的Candidate成為leader, 若同時有多個Candidate相同票數，進行下一輪投票，直到分出高下
   • leader 與各個follower 建立heartbeat
2. 復制日志 Log Replication
   • follower 同步leader的日志，丟棄無效的，接受并提交錯過的等。