Zookeeper - 簡述分布式一緻性協定（2pc、3pc、paxos、zab）

分布式一緻性協定

• 二階段送出協定（2pc）
• 三階段送出協定（3pc）
• paxos
• zab

在分布式系統中，每個機器都可以确定自己進行的事務操作是否成功，但是無法直接了解其他機器的操作結果。是以，當一個分布式事務操作需要保持ACID 特性時，就需要一個“協調者”節點排程其他“參與者”節點來進行分布式事務操作。

二階段送出（2pc）

送出事務請求 -> 執行事務送出；缺點：同步阻塞（參與者之間阻塞）、單點問題，腦裂（導緻資料不一緻問題）；主要用于關系型資料庫中，解決了分布式事務的原子性問題；

1. 送出事務請求

1. 協調者向參與者發送事務，并詢問是否可以執行事務送出操作，等待參與者響應；
2. 參與者執行事務，将操作寫入本地事務日志，向協調者發送回報；

2. 執行事務送出

參與者回報，全部ACK

1. 協調者向參與者發送Commit；
2. 參與者執行事務送出，釋放事務資源，回報ACK，；
3. 協調者收到回報完成事務

參與者回報，存在NO；協調者等待逾時

1. 協調者向參與者發送RollBack；
2. 參與者利用undo，進行事務復原；
3. 參與者事務復原之後，向協調者發送ACK 回報；
4. 協調者接收到ACK，完成事務中斷；

三階段送出（3pc）

cancommit -> precommit -> docommit；優缺點：降低了參與者同步阻塞範圍，但是又引入了資料不一緻性問題（若出現網絡分區）、單點問題依然存在；

1. CanCommit

1. 協調者向參與者發送cancommit 請求（包含事務内容），等待參與者回報；
2. 參與者接收到cancommit 請求之後，回報ACK或者NO；

2. PreCommit

參與者回報，全部ACK

1. 協調者向參與者發送precommit 請求，等待回報；
2. 參與者執行事務，将操作寫入本地事務日志，向協調者發送回報；

參與者回報，存在NO；協調者等待逾時

1. 協調者向參與者發送abort 請求；
2. 參與者無論是接收到abort 請求還是等待逾時都會中斷事務；

3. DoCommit

參與者回報，全部ACK

1. 協調者向參與者發送docommit 請求，等待回報；
2. 參與者執行事務送出，釋放事務資源，回報ACK，；
3. 協調者接收回報，完成事務送出；

參與者回報，存在NO；協調者等待逾時

1. 協調者向參與者發送abort 請求；
2. 參與者進行事務復原；
3. 參與者回報ACK；
4. 協調者接收到ACK，完成事務中斷；

paxos 算法

• paxos 基于消息傳遞并具有高度容錯性；
• paxos 算法的核心是，分布式系統如何就某個狀态（提案）達成一緻；
• paxos 算法假設不存在“拜占庭将軍問題”；
• paxos 算法中的角色：proposer、acceptor、learner；

• proposer：發送提案；
• acceptor：裁決提案；隻能準許一個提案；過半準許原則；
• learner：學習提案；

1. prepare 階段（生成提案）

• proposer 提出編号為Mn 的提案，向acceptor 集合發送prepare 請求；
• acceptor 回報；

• 保證不再接收編号小于Mn 的提案；
• 傳回已經準許的，編号最大的提案的Value；
• 若Mn 小于已經準許的最大編号，則忽略Mn；（優化）

• proposer 收到過半響應，則發送accept 請求（Mn，Vn）給acceptor 集合；Vn 是接收回的最大編号提案的Value；若無Value 可選（acceptor 都未接收提案），Vn 可為任意值；

2. accept 階段（準許提案）

acceptor 接收到accept 請求之後，隻要Mn 不小于已接受提案最大的編号，則準許提案；

learner 擷取提案（學習政策）

1. 一旦提案被準許（過半），則發送給所有learner；
2. 提案準許，則發送給一個learner，該learner再發送給其他learner；
3. 提案準許，則發送給一個learner集合，該learner集合再發送給其他learner；

優化

問題：proposer1 與 proposer2 兩者陷入死循環；

解決：選出主proposer，隻要主proposer 和 過半acceptor 能保持正常，那麼但凡主proposer 能提出一個編号更高的提案，這個提案最終将會準許；

應用

zab 協定