本文來自Raft作者Diego Ongaro，對Paxos的講解影片。主要涉及了Paxos協議的基本部分。Diego Ongaro的講解簡單易懂，是瞭解Paxos的最佳入門方式。
Replicated State machine
資料備份模型
primary backup system：client 請求到達的時候，Primary apply到自己的state machine，而後將計算結果複製到backup
replicated state machine：client 請求到達的時候，node透過一致性協議將請求轉發至其他node
分歧與細節：
primary backup system的崩潰恢復：
Primary 將操作 apply到自己的
state machine
後崩潰，而這個操作最終沒有提交，那麼需要對這個操作進行回滾
一般地，只要這個請求未被提交，state machine都需要回滾已經apply的操作。
Log傳遞開銷：
PBS下，只需要傳遞狀態即可。如果執行後發現狀態未改變，其實不需要向backup傳遞資訊。
SMR下，log都需要傳遞，可能存在額外的開銷。log compaction可以緩解這個問題。
deterministic命令：
PBS下，Primary apply op的動作，將random等non-deterministic的操作轉化為deterministic的
RSM下，需要專門對
non-deterministic
的命令進行處理
replicated state machine：
共識模組
負責log的複製
只要majority的節點還在執行，系統保證RSM的進展
故障模型：fail-stop & 非同步模型
問題分解
Basic Paxos
一個或多個伺服器propose values
這些伺服器組成的系統需要選擇
唯一一個
值作為
共識值
從頭到尾只選了一個值
Multi-Paxos
將多組Basic Paxos例項組合起來，然後來達成一系列的共識
Requirements
Safety
Only a single value that has been proposed may be chosen。
A node never learns that a value has been chosen unless it actually has been。（如果某個程序認為某個提案被選定了，那麼這個提案必須是真的被選定的那個。）
Liveness
Some proposed value is eventually chosen。
If a value has been chosen， a node can eventually learn the value。
演算法角色
Proposer
RPC發起方：提出值以供被選擇
處理客戶端的請求
Acceptor
RPC接收方：響應來自Proposer的資訊
響應結果代表著形成共識的投票
需要對選擇的值、程序狀態進行持久化
想要知道哪個值被選擇了。這個性質是Lamport制定的Learner角色所需要的性質，在這裡討論的時候，把Learner與Acceptor合併來看。
節點與角色：每個節點可以承擔多種角色，這裡討論認為每個節點同時承擔Proposer和Acceptor兩種角色
如何滿足Safety
Safety： Only a single value that has been proposed may be chosen。
要求：
如果有值已經被chosen，那麼proposer不能再發起propose
如果有多個同時被Proposed的值，Acceptor應當提供一種機制拒絕掉競爭失敗的值被accepted
解決方案：
Proposal有唯一的編號，高編號的優先順序高於低編號的
Proposer發起新proposal時，需要保證使用一個它所知道的更高的proposalId
一個簡單實現：
ID：Round + ServerId
每個伺服器持久化當前Round
當宕機重啟時，不能重用之前儲存下來的Round作為proposalId
Basic Paxos
階段1：Proposer廣播Prepare RPC，目的：
進行決議，選出一個值接下來被chosen
階段2：Proposer廣播Accept RPC
讓所有Acceptor來accept一個階段1得到的值
State：
Proposer‘s and volatile：
value： proposer將要讓acceptor accept的值
Acceptor’s and persistent：
minProposal： acceptor目前見到過的最大的proposalId
acceptedProposal： acceptor目前accept過的最大的proposalId
acceptedValue： acceptor目前accept過的最大的proposalId對應的值
Prepare RPC：
arguments：
proposal number： n
result：
acceptedProposal
acceptedValue
receiver implementation：
1。 if n > minProposal then
minProposal = n
minProposal表示acceptor能接受的最小編號的提案編號
Accept RPC：
arguments：
proposal number： n
proposal value： value
result：
minProposal
receiver implementation：
1。 if n >= minProposal then
minProposal = n，
acceptedProposal = n，
acceptedValue = value
生成一個proposal Id 為 n，有一個潛在的需要達成共識的值value
Phase1：Prepare Phase
Proposer -> Acceptor：向所有節點廣播
Prepare RPC
收到majority返回的結果後，如果Acceptor返回了一個它已經accept了的proposal資訊，那麼接下來要求別人確認的值（value）就應當是這個值
Phase2：Accept Phase
Proposer -> Acceptor：向所有節點廣播
Accept RPC
如果發現返回值的majority <= n，那麼value就被chosen；否則決議失敗，必須重新發起一次決議
例子
前提：S1和S4、S5有一定的網路不穩定；S5和S1、S2有一定的網路不穩定
情況：
S1向全部發送了Prepare請求，S1、S2、S3得到應答
S5向全部發送了Prepare請求，S3、S4、S5得到應答
隨後S1、S2分別傳送Accept請求
關鍵點：
由於S5的
round number
更高，因此S3接收到S1的Accept請求時，會將其拒絕掉
因此S1的Phase2會失敗，S1需要重新選擇一個更高的proposalId；而此時，S1發起的Accept RPC的值一定是Y了
如何知道
chosen value
只有proposer才知道哪個值是chosen value
其他人如果想知道chosen value
Multi-Paxos
將待決議的值視作log中的一項
為Basic Paxos加上
log index
的約束，這樣就可以發起多個共識決議了
問題：client 請求和
log entry
怎麼一一對應？
解答：選擇log index的策略：
找到log entry中第一個沒被chosen的槽位
如果該槽位有值，拿這個值執行一遍Basic Paxos；如果該槽位沒有值，拿期望決議的值執行一遍Basic Paxos
一直找下去，直到chosen的值是我們期望決議的值
一些注意點：
某個機器上被accepted的值，不一定是chosen的值。存在被修改的可能
這種情況下，提交log並取得共識的效率會很高，可以併發執行
但是對取得共識的log進行apply的時候需要小心注意，因為有時候需要按一定的先後順序apply。這時就需要在log中新增一些表示順序的資訊，以在apply時阻塞等待一下前置步驟的完成
效率與活鎖：Liveness是怎麼受損的
活鎖：兩個節點交錯Prepare & Accept，但是始終沒辦法達成共識
效率：
Liveness：在多proposer併發的情況下，衝突、造成活鎖的情況會很容易出現
RPC本身效率：每個值都要至少兩個2RPC來達成決議
解決方案：
選擇一個Leader：任意時間只有一個node作為Proposer，其他的都是Acceptor
最佳化掉大多數的Prepare RPC
批處理：將多個槽的log進行prepare
這樣絕大多數log entires能在一個round實現決議
Leader Election
server有編號，ID最大的當選leader
每T ms，每個節點向其他所有節點發送一個heartbeat資訊
如果server在 2T ms，沒有收到其他更高ID的server的heartbeat資訊，那自己就表現得像個leader
處理client的請求
作為proposer & acceptor進行提議
如果server不是leader
拒絕其他
客戶端
的客戶端請求（或重定向到其他leader）
只作為一個acceptor
消除 Prepare RPC
Prepare RPC的意義
拒絕老的Proposal提議
返回可能被chosen的Proposal（包括值和id）
思考：
消除Prepare RPC需要透過某種方式來保證上述的兩個作用仍能生效
Accept RPC 可以做到拒絕老的Proposal
如上圖，S2後續和S1的交流中Prepare請求是可以被最佳化的。因為S2從來沒有收到過其他人的prepare請求，S2對S1的Prepare請求回覆總是相同的。
併發度的思考
如果同一時間，我們從客戶端收到了多個請求需要達成共識
這個時候
log array
中的多個index位置都需要run Basic Paxos
實際上他們的這種執行是相似的
那有沒有可能讓他們一起進行呢？
改進：
「拒絕老的Proposal提議」的改進
直接透過Accept RPC來保障拒絕老的Proposal。
Accept RPC 只有在 n > minProposal 時，才會更新 proposalId和 value
當proposer收到了一個大於當前自己持有的proposalId時，它可以意識到，這個RPC被拒絕了
「返回可能被chosen的Proposal（包括值和id）」的改進
原先僅返回最大的 proposalId 及其對應的 proposal 值。
配合改進一，增加新欄位「noMoreAccepted」：
如果後面的Proposal沒有acceptedValue的時候返回noMoreAccepted。
這樣，一個acceptor一旦用noMoreAccepted回覆Prepare之後，Proposer就不需要再向其傳送Prepare了。
併發度的改進
原先的請求
作用域
是一個Index，對multi-paxos改進時，作用域擴充套件為所有槽
即原先的prepare rpc中指涉log index的引數變成了一個指涉全域性log array的引數
這個引數鎖住了log array
某種意義上說，這個引數有點像 Raft 協議中的term
一個proposer如果prepare成功，意味著同期沒有人和他一起競爭
一般使用leader也會保證這種效果
因此，一次prepare之後，proposer就沒必要重複發起
prepare rpc
了
因為上一次prepare的時候，沒有人和他競爭，也就沒有人讓acceptor accept資訊。
prepare是為了確認最新的accepted的資訊，而這個資訊又是上一輪proposer自己發的
所以，這個資訊其實是已知的。因此無需重複發prepare rpc
在一個值被accept之後，直接accept其他值即可
這兩條一起幫助每個LogEntry只需要1 round RPC就可以實現決議了。
其他問題
Full Replication：複製的完整性，全部節點都需要得知達成共識的值
Client protocol：客戶端和
服務端
之間溝通應該怎麼設計
節點增減：成員變更處理
Ensuring Full Replication
目標：
目前不一定全部節點都得到了共識值，需要全部節點都得到共識值
目前只有proposer才知道值被chosen了，需要全部節點都知道這個值被chosen了
解決方案：
向未響應Accept RPC請求的節點持續傳送Accept RPC，直到響應為止
保證所有節點都得到了共識值
將chosen的值的proposalId設定為無窮大。
可以拒絕之後任意的proposal
相當於一個標記位，如果發現某個槽位的proposalId是無窮大，那麼就說明這個槽位的決議已經確定了
每個server維護一個firstUnchosenIndex的變數，表示第一個還未達成一致的槽位。
改造Accept RPC，讓RPC的接受者可以得知某值被chosen的資訊
將log entry中所有符合條件的entry的proposalId設定為無限大：
entryIndex < rpcArgs。firstUnchosenIndex 且
log［entryIndex］。proposalId == rpcArgs。proposalId
為了為值的被選定做保證，引入Success RPC
Accept RPC的返回值新增acceptor的firstUnchosenIndex
如果 proposer 的 firstUnchosenIndex > 返回值的firstUnchosenIndex，那麼傳送Success RPC
proposer 的 firstUnchosenIndex 更大，說明acceptor的某些日誌是不確定的（這個槽位的值不認為被chosen了，沒有設定成無限大）
這時proposer需要把不確定的值發給acceptor
Success RPC：
argument：
index： firstUnchosenIndex of received Accept RPC
value： value of firstUnchosenIndex of proposal
return：
firstUnchosenIndex
receiver‘s implementation：
1。 acceptedValue［index］ = value
2。 acceptedProposalId［index］ = ∞
辨析
用日誌來管理叢集配置變更。當前的叢集配置作為一條log entry被複制同步。
state machine在接收到配置變更命令後，會修改配置值
配置生效的時刻有系統變數alpha決定
alpha表示，系統apply了配置變更之後，在alpha個command被chosen後生效
如下圖，C1的配置變更被記錄在槽1中，但是它沒有立即生效，而是在alpha=3個command被記錄了之後，整個系統再用C1的配置進行決議。C2的配置變更同理
如果必要的話，在提交了C1變更後，我們可以提交若干個無實義的noop來使得C1生效
解決方案
保證在任何時候都不能出現兩個不重疊的
多數派
目標：
原先的叢集是S1~S3，新添加了兩臺S4、S5
如果有proposer分別以舊配置的Majority（S1&S2）和新配置的Majority（S3~S5）分別發起決議，就會出問題
問題：
叢集配置變更
依賴於客戶端自己保證。如果客戶端對同一個僅需執行一次的命令，生成了兩個uniqueId，那就會出問題
問題：
客戶端需要為每條命令提供一個唯一的 ID
由apply command的state machine來確定這個命令需不需要執行
解決：
客戶端重試可能會導致某個命令被多次執行
問題：
Client Protocol
proposer向某個acceptor傳送了Accept RPC
此時的proposer是server4
此時的round是3
RPC想要確定的是index = 8的值，待確定的值是v
目前log的情況
4號槽位的日誌是server5發來的round2時確認的值
6號位的值來源和RPC傳送者相同，而且是同一個round收到的
RPC分析，proposer處，6號位已經確定了，最低的未確認的位是第7位
而6號位的round號、server號又和RPC保持一致，因此6號槽位的值就是chosen的值
而4號槽位一致沒能確認，因此需要Success RPC來進行確認
下一步proposer將會透過Success RPC傳送4號位的值給這個acceptor來達成共識。
辨析
Accepted & chosen：被majority of nodes 給 accepted了，才是chosen
Reference
https：//www。
youtube。com/watch？
v=JEpsBg0AO6o
