1. 算法背景

狀態(tài)復(fù)制(State Replication). 對于一組節(jié)點，如果所有節(jié)點均以相同的順序執(zhí)行一個（可能是無限的）命令序列c₁, c₂, c₃, ..., 則這組節(jié)點實現(xiàn)了狀態(tài)復(fù)制。
—— 《區(qū)塊鏈核心算法解析》

在許多分布式系統(tǒng)中，都有分布式的節(jié)點保持狀態(tài)一致的要求，例如在分布式數(shù)據(jù)庫中要保證 log 文件在各節(jié)點一致，那么就需要使用分布式一致性算法，如 Paxos。 對于金融科技行業(yè)的從業(yè)人員來說，狀態(tài)復(fù)制經(jīng)常等同于區(qū)塊鏈。

2. 消息模型

在我們下面要討論的分布式系統(tǒng)中，設(shè)定了下面幾條消息傳遞的規(guī)則：

• 消息傳遞（Message Passing）：在分布式系統(tǒng)中，各個節(jié)點都可以通過發(fā)送消息（Message）來與其他節(jié)點通信
• 消息丟失（Message Loss）：在消息傳遞的過程中，任何一條消息都不能保證可以安全地到達(dá)消息的接受者
• 消息確認(rèn)（Acknowledgements）：當(dāng)接受者接收到消息后，可以根據(jù)之前設(shè)定的規(guī)則選擇是否回復(fù)消息的確認(rèn)
• 可變消息延遲（Variable Message Delay）：每條消息在實際應(yīng)用中傳遞是時間是不定的，也不一定相同
• 非拜占庭問題（non-Byzantine Problem）：消息在傳遞的過程中不存在被篡改的問題

3. 討論 Paxos 之前

實現(xiàn) node 間的狀態(tài)復(fù)制，我們很容易想到下面的解決辦法：

3.1 單服務(wù)器實現(xiàn)狀態(tài)一致

使用單個服務(wù)器，很容易知道，我們只需要從所有發(fā)送到服務(wù)器的value中選取一個作為最終的存儲對象，再將所選中的value發(fā)送給分布式系統(tǒng)中的其他所有節(jié)點即可。
很明顯這種方法下，只有一個服務(wù)器，存在單點故障的問題

3.2 Two-Phase Protocol

兩階段協(xié)議（Two-Phase Protocol），簡述就是一個client在企圖向所有的分布式server提交value時，必須獲得所有server的鎖，然后才能向server發(fā)送提交value的命令；如果不能獲得所有server的鎖則釋放已經(jīng)獲得的鎖，重新嘗試獲得所有鎖。
兩階段協(xié)議相比上面所述的單服務(wù)器協(xié)議而言，所需條件更為嚴(yán)格，因為一個client必須同時獲得所有server的鎖才能提交value。

4. Paxos 算法

4.1 介紹

Paxos 算法在網(wǎng)絡(luò)上已經(jīng)有許多人以各種簡單易懂的方式解釋過（推薦知乎這個問題下的第2個與第1個回答），本文主要記錄自己在思考中所遇到的一些問題。

在Paxos 系統(tǒng)中存在這三種角色， proposer acceptor learner，在Paxos 算法的執(zhí)行過程中主要有這兩個階段（這里直接截取了paxos make simple論文）：

階段1

階段2

而對一個value存在這三個階段：prepare accept chosen

4.2 思考

網(wǎng)絡(luò)上很多帖子講不清楚 Paxos 算法的問題都在于，沒有講清楚最后一個value被accept與被chosen的區(qū)別。在知乎這個回答下面其實作者已經(jīng)快完全說清了 Paxos 算法（舉的例子也很生動），但是最后沒有說明白value被accpet與chosen的區(qū)別與聯(lián)系，所以就會有如下圖中這樣的評論

某評論

可以看到我給這條評論點了贊，因為之前我也被這個問題困擾過。產(chǎn)生這個問題的原因就是：混淆了accpet與chosen。
因為之前我們一直強調(diào) Paxos 算法有兩個階段，以及強調(diào)當(dāng)一個value被某acceptor accept，該acceptor就不會accept其他value。

4.3 說明

以剛才說的那個知乎回答為例，我們假設(shè)在一個系統(tǒng)中有兩個 proposer三個acceptor，暫時不提learner，該系統(tǒng)發(fā)生了如下時間線的事情：

|- proposer1 拿到了3個acceptor對 prepare 請求的確認(rèn)回復(fù)，開始向3個acceptor發(fā)送accept請求
|    |- proposer1 的accpet 請求順利到達(dá)acceptor1，acceptor1 accept 了 value1
|    |- 因為延時等問題proposer1發(fā)出的accept請求沒能及時到達(dá)acceptor2與acceptor3
|- proposer2 更新了acceptor2與acceptor3的 prepare number
|    |- proposer2 向三個acceptor都發(fā)送accept請求，acceptor2與acceptor3 accept了value2，acceptor1則拒絕了value2

之前的疑惑就在于，以為 acceptor1 accept 了 value1后，value就被選定了，acceptor2與acceptor3 不能再accept 其他value了，但其實acceptor1 accept 了 value1后，該value只是被aaceptor1 accept，并沒有被整個系統(tǒng) chosen。
我們回顧一下論文中對chosen 的定義：

chosen的定義

Q1：有人要問了，那acceptor1 accept了 value1，acceptor2與acceptor3 accept 了value2 ，那豈不是沒有實現(xiàn)狀態(tài)一致嗎？出現(xiàn)這個問題除了之前說的，混淆了accept與chosen以外，也和網(wǎng)絡(luò)上很多關(guān)于Paxos 算法的文章省略了對learner的討論有關(guān)系。
A1：首先我們應(yīng)該明確，一個value是否被chosen與acceptor是無關(guān)的，acceptor在accept一個value之后，它的使命就完成了，至于這個value最后是否能夠被chosen不是它考慮的問題。

Q2：有人又要問了，那acceptor怎么知道自己accept的value 有沒有被chosen呢？答案是：其實它沒有知道的必要，如果它想知道的話，通過learner。
A2：如果acceptor想知道哪個value被chosen的話，可以通過詢問learner（learner可以有一個也可以有多個），如果此時已經(jīng)有value被chosen了，learner可以告訴該acceptor被chosen的value2，然后該acceptor記錄下被chosen的value（如果它有必要記錄的話）

其實我們在上面的例子中，如果開上帝視角的話，在acceptor2與acceptor3 accept 了value2 的那一刻，value2的值已經(jīng)被chosen了，但是此時learner節(jié)點們還不知道，所有就需要learner去learn哪個value被chosen了（To learn that a value has been chosen）

關(guān)于learner 如何learn 到哪個value被chosen，在 Paxos make simple 的論文中有討論，也比較簡單（其實就是通過消息去詢問或者被告知是否有一個value被大多數(shù)（超過一半）acceptor accept）。論文中該部分截圖如下：

how value be chosen

how value be chosen

5. 結(jié)語

這篇文章主要不是介紹怎么去形象地理解 Paxos 算法，而是將自己在理解中遇到的一些問題整理回顧一下。回到開篇中我們說到的分布式系統(tǒng)中各個節(jié)點保持狀態(tài)一致的問題，其實看到這里我們應(yīng)該能想到，只要在每個節(jié)點中，都有一個扮演 learner 的進(jìn)程，那么如果有一個 value被chosen，那么該系統(tǒng)就可以實現(xiàn)對某一個值或某一個 log 文件達(dá)成各節(jié)點一致。之所以說如果有一個，是因為 Paxos 算法存在活鎖的問題，有可能永遠(yuǎn)也選不出一個value被chosen，這也就是FLP 不可能性。

我的第一篇博文，獻(xiàn)給 zyy 同學(xué)（推眼鏡