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

拜占庭將軍問(wèn)題

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

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

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

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

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

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

2PC(2 Phase Commit)

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

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

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

3PC

• 角色：coordinator協(xié)調(diào)者, 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特點(diǎn)：
  1. c, p端都引入超時(shí)機(jī)制, 解決單點(diǎn)故障， 各節(jié)點(diǎn)事務(wù)性阻塞
  2. 數(shù)據(jù)不一致
     • 由于網(wǎng)絡(luò)原因，協(xié)調(diào)者發(fā)送的abort響應(yīng)沒(méi)有及時(shí)被參與者接收到，那么參與者在等待超時(shí)之后執(zhí)行了commit操作。這樣就和其他接到abort命令并執(zhí)行回滾的參與者之間存在數(shù)據(jù)不一致的情況。

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

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

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

State Machine

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

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

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

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

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

• 同步操作
  操作必須是確定性的，如跟時(shí)間、隨機(jī)數(shù)相關(guān)的的操作就會(huì)導(dǎo)致各節(jié)點(diǎn)操作的結(jié)果不一致。
• 同步操作后的值
  操作先作用到Primary節(jié)點(diǎn)上，即使操作本身是不確定的，但結(jié)果的值是確定的。其他節(jié)點(diǎn)同步操作后的值，數(shù)據(jù)具有一致性。
  進(jìn)階：如果數(shù)據(jù)值本身比較大，同步值的做法IO代價(jià)較高。可以在primary節(jié)點(diǎn)將非確定的操作的確定實(shí)現(xiàn)同步，譬如，同步操作ADD Random()，隨機(jī)值為ADD 2

Primary-backup

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

Paxos

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

• 角色： Proposer, Acceptor, Learner
• 原則：
  1.prepare | promise stage
  - Acceptor 回復(fù)（promise)收到的第一個(gè)proposal或大于當(dāng)前接受proposal編號(hào)的proposal

2. Accept stage
   - Proposer 獲得大多數(shù)（過(guò)半數(shù)）Acceptor 的promise則向回復(fù)promise的Acceptor發(fā)送accept請(qǐng)求
3. 其他Learner學(xué)習(xí) Acceptor的結(jié)果

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

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

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

• 角色：leader, follower

1. Broadcast stage

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

2. Recovery

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

Raft

raft https://www.jianshu.com/p/8e4bbe7e276c
動(dòng)畫演示： http:///raft/

• 角色： Follower，Candidate，Leader
• 過(guò)程

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