1. 算法背景
狀態(tài)復(fù)制(State Replication). 對(duì)于一組節(jié)點(diǎn)，如果所有節(jié)點(diǎn)均以相同的順序執(zhí)行一個(gè)（可能是無(wú)限的）命令序列c1, c2, c3, ..., 則這組節(jié)點(diǎn)實(shí)現(xiàn)了狀態(tài)復(fù)制。
—— 《區(qū)塊鏈核心算法解析》
在許多分布式系統(tǒng)中，都有分布式的節(jié)點(diǎn)保持狀態(tài)一致的要求，例如在分布式數(shù)據(jù)庫(kù)中要保證 log 文件在各節(jié)點(diǎn)一致，那么就需要使用分布式一致性算法，如 Paxos。 對(duì)于金融科技行業(yè)的從業(yè)人員來(lái)說(shuō)，狀態(tài)復(fù)制經(jīng)常等同于區(qū)塊鏈。
2. 消息模型
在我們下面要討論的分布式系統(tǒng)中，設(shè)定了下面幾條消息傳遞的規(guī)則：
- 消息傳遞（Message Passing）：在分布式系統(tǒng)中，各個(gè)節(jié)點(diǎn)都可以通過發(fā)送消息（Message）來(lái)與其他節(jié)點(diǎn)通信
- 消息丟失（Message Loss）：在消息傳遞的過程中，任何一條消息都不能保證可以安全地到達(dá)消息的接受者
- 消息確認(rèn)（Acknowledgements）：當(dāng)接受者接收到消息后，可以根據(jù)之前設(shè)定的規(guī)則選擇是否回復(fù)消息的確認(rèn)
- 可變消息延遲（Variable Message Delay）：每條消息在實(shí)際應(yīng)用中傳遞是時(shí)間是不定的，也不一定相同
- 非拜占庭問題（non-Byzantine Problem）：消息在傳遞的過程中不存在被篡改的問題
3. 討論 Paxos 之前
實(shí)現(xiàn) node 間的狀態(tài)復(fù)制，我們很容易想到下面的解決辦法：
3.1 單服務(wù)器實(shí)現(xiàn)狀態(tài)一致
使用單個(gè)服務(wù)器，很容易知道，我們只需要從所有發(fā)送到服務(wù)器的value中選取一個(gè)作為最終的存儲(chǔ)對(duì)象，再將所選中的value發(fā)送給分布式系統(tǒng)中的其他所有節(jié)點(diǎn)即可。
很明顯這種方法下，只有一個(gè)服務(wù)器，存在單點(diǎn)故障的問題
3.2 Two-Phase Protocol
兩階段協(xié)議（Two-Phase Protocol），簡(jiǎn)述就是一個(gè)client在企圖向所有的分布式server提交value時(shí)，必須獲得所有server的鎖，然后才能向server發(fā)送提交value的命令；如果不能獲得所有server的鎖則釋放已經(jīng)獲得的鎖，重新嘗試獲得所有鎖。
兩階段協(xié)議相比上面所述的單服務(wù)器協(xié)議而言，所需條件更為嚴(yán)格，因?yàn)橐粋€(gè)client必須同時(shí)獲得所有server的鎖才能提交value。
4. Paxos 算法
4.1 介紹
Paxos 算法在網(wǎng)絡(luò)上已經(jīng)有許多人以各種簡(jiǎn)單易懂的方式解釋過（推薦知乎這個(gè)問題下的第2個(gè)與第1個(gè)回答），本文主要記錄自己在思考中所遇到的一些問題。
在Paxos 系統(tǒng)中存在這三種角色， proposer acceptor learner，在Paxos 算法的執(zhí)行過程中主要有這兩個(gè)階段（這里直接截取了paxos make simple論文）：
而對(duì)一個(gè)value存在這三個(gè)階段：prepare accept chosen
4.2 思考
網(wǎng)絡(luò)上很多帖子講不清楚 Paxos 算法的問題都在于，沒有講清楚最后一個(gè)value被accept與被chosen的區(qū)別。在知乎這個(gè)回答下面其實(shí)作者已經(jīng)快完全說(shuō)清了 Paxos 算法（舉的例子也很生動(dòng)），但是最后沒有說(shuō)明白value被accpet與chosen的區(qū)別與聯(lián)系，所以就會(huì)有如下圖中這樣的評(píng)論
可以看到我給這條評(píng)論點(diǎn)了贊，因?yàn)橹拔乙脖贿@個(gè)問題困擾過。產(chǎn)生這個(gè)問題的原因就是：混淆了accpet與chosen。
因?yàn)橹拔覀円恢睆?qiáng)調(diào) Paxos 算法有兩個(gè)階段，以及強(qiáng)調(diào)當(dāng)一個(gè)value被某acceptor accept，該acceptor就不會(huì)accept其他value。
4.3 說(shuō)明
以剛才說(shuō)的那個(gè)知乎回答為例，我們假設(shè)在一個(gè)系統(tǒng)中有兩個(gè) proposer三個(gè)acceptor，暫時(shí)不提learner，該系統(tǒng)發(fā)生了如下時(shí)間線的事情：
|- proposer1 拿到了3個(gè)acceptor對(duì) prepare 請(qǐng)求的確認(rèn)回復(fù)，開始向3個(gè)acceptor發(fā)送accept請(qǐng)求
| |- proposer1 的accpet 請(qǐng)求順利到達(dá)acceptor1，acceptor1 accept 了 value1
| |- 因?yàn)檠訒r(shí)等問題proposer1發(fā)出的accept請(qǐng)求沒能及時(shí)到達(dá)acceptor2與acceptor3
|- proposer2 更新了acceptor2與acceptor3的 prepare number
| |- proposer2 向三個(gè)acceptor都發(fā)送accept請(qǐng)求，acceptor2與acceptor3 accept了value2，acceptor1則拒絕了value2
之前的疑惑就在于，以為 acceptor1 accept 了 value1后，value就被選定了，acceptor2與acceptor3 不能再accept 其他value了，但其實(shí)acceptor1 accept 了 value1后，該value只是被aaceptor1 accept，并沒有被整個(gè)系統(tǒng) chosen。
我們回顧一下論文中對(duì)chosen 的定義：
也就是說(shuō)，在上面的例子中value真正被chosen是在acceptor2與acceptor3 accept 了value2 那一刻，而不是 acceptor1 accept 了 value1 那一刻。
Q1：有人要問了，那acceptor1 accept了 value1，acceptor2與acceptor3 accept 了value2 ，那豈不是沒有實(shí)現(xiàn)狀態(tài)一致嗎？出現(xiàn)這個(gè)問題除了之前說(shuō)的，混淆了accept與chosen以外，也和網(wǎng)絡(luò)上很多關(guān)于Paxos 算法的文章省略了對(duì)learner的討論有關(guān)系。
A1：首先我們應(yīng)該明確，一個(gè)value是否被chosen與acceptor是無(wú)關(guān)的，acceptor在accept一個(gè)value之后，它的使命就完成了，至于這個(gè)value最后是否能夠被chosen不是它考慮的問題。
Q2：有人又要問了，那acceptor怎么知道自己accept的value 有沒有被chosen呢？答案是：其實(shí)它沒有知道的必要，如果它想知道的話，通過learner。
A2：如果acceptor想知道哪個(gè)value被chosen的話，可以通過詢問learner（learner可以有一個(gè)也可以有多個(gè)），如果此時(shí)已經(jīng)有value被chosen了，learner可以告訴該acceptor被chosen的value2，然后該acceptor記錄下被chosen的value（如果它有必要記錄的話）
其實(shí)我們?cè)谏厦娴睦又?，如果開上帝視角的話，在acceptor2與acceptor3 accept 了value2 的那一刻，value2的值已經(jīng)被chosen了，但是此時(shí)learner節(jié)點(diǎn)們還不知道，所有就需要learner去learn哪個(gè)value被chosen了（To learn that a value has been chosen）
關(guān)于learner 如何learn 到哪個(gè)value被chosen，在 Paxos make simple 的論文中有討論，也比較簡(jiǎn)單（其實(shí)就是通過消息去詢問或者被告知是否有一個(gè)value被大多數(shù)（超過一半）acceptor accept）。論文中該部分截圖如下：
5. 結(jié)語(yǔ)
這篇文章主要不是介紹怎么去形象地理解 Paxos 算法，而是將自己在理解中遇到的一些問題整理回顧一下。回到開篇中我們說(shuō)到的分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)保持狀態(tài)一致的問題，其實(shí)看到這里我們應(yīng)該能想到，只要在每個(gè)節(jié)點(diǎn)中，都有一個(gè)扮演 learner 的進(jìn)程，那么如果有一個(gè) value被chosen，那么該系統(tǒng)就可以實(shí)現(xiàn)對(duì)某一個(gè)值或某一個(gè) log 文件達(dá)成各節(jié)點(diǎn)一致。之所以說(shuō)如果有一個(gè)，是因?yàn)?Paxos 算法存在活鎖的問題，有可能永遠(yuǎn)也選不出一個(gè)value被chosen，這也就是FLP 不可能性。
我的第一篇博文，獻(xiàn)給 zyy 同學(xué)（推眼鏡
