Paxos介紹
分布式系統中，只有出現故障節點(fault node),但不存在惡意節點(corrupt node)下達成共識的問題。
問題起源
故事背景為古希臘的Paxon島上有諸位法官要對某一件法案進行裁決並如何達成共識的結果。
過程中法官會透過傳訊關傳遞訊息，但法官可能中途離席，而服務員可能偷懶睡覺。
故Paxos算法基於"兩階段提交"來確保法官們可以得到共識結果的一致性。
Paxos特性
Paxos將參與節點中分為三類：
- Proposer(客戶端): 提出一個案子，等待大家批准並得到答案。
- Acceptor(服務端): 接受提案，並進行投票。
- Learner(客戶端or服務端): 被告知提案結果，並將自己的狀態與結果更新。
過程中必須滿足分散式系統共識所必須的兩特性：
- Safty：保證決議結果是對的，無異議，並不會出現錯誤情況。
- Liveness：保證在"有限"時間內完成共識結果。
Paxos過程
- 由Proposer提出提案，爭取Acceptors的支持。
- 超過一半的Acceptors支持，則發送該提案結果給所有人進行確認。
兩階段提繳
Step 1: Prepare階段
- Proposer發送自己的計畫給多個Acceptors.
- Acceptor根據該計畫的編號，若是最新的編號則保留，反之則退回。
Step 2: Commit階段
- Proposer收到Accpetor的確認回覆。若收到的回覆中不帶有新的提案請求，表示鎖定成功。
- 若沒有收到超過1/2個Accpetor的回覆。
特殊情況
- 若Proposer在提案過程中發生故障，可以透過超時機制票選下一位Proposer。
- Paxos算法保證在正常節點有 1/2個以上時，可滿足共識的Safety和Liveness.
Raft介紹
為Paxos的簡化版本。
參與者
包括三種角色： 1.Leader 2.Candidate 3.Follower
共識流程
- Leader選舉：每個Candidate在一定時間內會提出選舉方案，而選舉結果的那位成為Leader.
- 同步每個Replication的Log: Leader會找到系統中的Log檔案上最新的紀錄，並要求所有Follower根據該最新紀錄同步到他們自己的Log檔案上。
log檔可能為系統上發生的動作紀錄。
小結
Paxos和Raft為目前分散式系統的帶來不錯的共識結果，其他共識演算法像是PBFT (practical byzantine fault tolerant protocal)以及目前由Amis團隊所於etherum上所實現的BFT算法- Istanbul BFT，都算是本次筆記提到的再進階的共識算法，有興趣的讀者可以在到以下連結去深入瞭解。
