背景

在計(jì)算機(jī)通信理論中，有一個(gè)著名的兩軍問(wèn)題(two-army problem)，講述通信的雙方通過(guò)ACK來(lái)達(dá)成共識(shí)，永遠(yuǎn)會(huì)有一個(gè)在途的ACK需要進(jìn)行確認(rèn)，因此無(wú)法達(dá)成共識(shí)。

兩軍問(wèn)題和Basic Paxos非常相似

1） 通信的各方需要達(dá)成共識(shí)；

2） 通信的各方僅需要達(dá)成一個(gè)共識(shí)；

3） 假設(shè)的前提是信道不穩(wěn)定，有丟包、延遲或者重放，但消息不會(huì)被篡改。

Basic Paxos最早以希臘議會(huì)的背景來(lái)講解，但普通人不理解希臘議會(huì)的運(yùn)作模式，因此看Basic Paxos的論文會(huì)比較難理解。兩軍問(wèn)題的背景大家更熟悉，因此嘗試用這個(gè)背景來(lái)演繹一下Basic Paxos。

為了配合Basic Paxos的多數(shù)派概念，把兩軍改為3軍；同時(shí)假設(shè)了將軍和參謀的角色。

假設(shè)的3軍問(wèn)題

1） 1支紅軍在山谷里扎營(yíng)，在周圍的山坡上駐扎著3支藍(lán)軍；

2） 紅軍比任意1支藍(lán)軍都要強(qiáng)大；如果1支藍(lán)軍單獨(dú)作戰(zhàn)，紅軍勝；如果2支或以上藍(lán)軍同時(shí)進(jìn)攻，藍(lán)軍勝；

3） 三支藍(lán)軍需要同步他們的進(jìn)攻時(shí)間；但他們惟一的通信媒介是派通信兵步行進(jìn)入山谷，在那里他們可能被俘虜，從而將信息丟失；或者為了避免被俘虜，可能在山谷停留很長(zhǎng)時(shí)間；

4） 每支軍隊(duì)有1個(gè)參謀負(fù)責(zé)提議進(jìn)攻時(shí)間；每支軍隊(duì)也有1個(gè)將軍批準(zhǔn)參謀提出的進(jìn)攻時(shí)間；很明顯，1個(gè)參謀提出的進(jìn)攻時(shí)間需要獲得至少2個(gè)將軍的批準(zhǔn)才有意義；

5） 問(wèn)題：是否存在一個(gè)協(xié)議，能夠使得藍(lán)軍同步他們的進(jìn)攻時(shí)間？

接下來(lái)以兩個(gè)假設(shè)的場(chǎng)景來(lái)演繹BasicPaxos；參謀和將軍需要遵循一些基本的規(guī)則

1） 參謀以兩階段提交（prepare/commit）的方式來(lái)發(fā)起提議，在prepare階段需要給出一個(gè)編號(hào)；

2） 在prepare階段產(chǎn)生沖突，將軍以編號(hào)大小來(lái)裁決，編號(hào)大的參謀勝出；

3） 參謀在prepare階段如果收到了將軍返回的已接受進(jìn)攻時(shí)間，在commit階段必須使用這個(gè)返回的進(jìn)攻時(shí)間；

兩個(gè)參謀先后提議的場(chǎng)景

1） 參謀1發(fā)起提議，派通信兵帶信給3個(gè)將軍，內(nèi)容為（編號(hào)1）；

2） 3個(gè)將軍收到參謀1的提議，由于之前還沒(méi)有保存任何編號(hào)，因此把（編號(hào)1）保存下來(lái)，避免遺忘；同時(shí)讓通信兵帶信回去，內(nèi)容為（ok）；

3） 參謀1收到至少2個(gè)將軍的回復(fù)，再次派通信兵帶信給3個(gè)將軍，內(nèi)容為（編號(hào)1，進(jìn)攻時(shí)間1）；

4） 3個(gè)將軍收到參謀1的時(shí)間，把（編號(hào)1，進(jìn)攻時(shí)間1）保存下來(lái)，避免遺忘；同時(shí)讓通信兵帶信回去，內(nèi)容為（Accepted）；

5） 參謀1收到至少2個(gè)將軍的（Accepted）內(nèi)容，確認(rèn)進(jìn)攻時(shí)間已經(jīng)被大家接收；

6） 參謀2發(fā)起提議，派通信兵帶信給3個(gè)將軍，內(nèi)容為（編號(hào)2）；

7） 3個(gè)將軍收到參謀2的提議，由于（編號(hào)2）比（編號(hào)1）大，因此把（編號(hào)2）保存下來(lái)，避免遺忘；又由于之前已經(jīng)接受參謀1的提議，因此讓通信兵帶信回去，內(nèi)容為（編號(hào)1，進(jìn)攻時(shí)間1）；

8） 參謀2收到至少2個(gè)將軍的回復(fù)，由于回復(fù)中帶來(lái)了已接受的參謀1的提議內(nèi)容，參謀2因此不再提出新的進(jìn)攻時(shí)間，接受參謀1提出的時(shí)間；

兩個(gè)參謀交叉提議的場(chǎng)景

1） 參謀1發(fā)起提議，派通信兵帶信給3個(gè)將軍，內(nèi)容為（編號(hào)1）；

2） 3個(gè)將軍的情況如下

a) 將軍1和將軍2收到參謀1的提議，將軍1和將軍2把（編號(hào)1）記錄下來(lái)，如果有其他參謀提出更小的編號(hào)，將被拒絕；同時(shí)讓通信兵帶信回去，內(nèi)容為（ok）；

b) 負(fù)責(zé)通知將軍3的通信兵被抓，因此將軍3沒(méi)收到參謀1的提議；

3） 參謀2在同一時(shí)間也發(fā)起了提議，派通信兵帶信給3個(gè)將軍，內(nèi)容為（編號(hào)2）；

4） 3個(gè)將軍的情況如下

a) 將軍2和將軍3收到參謀2的提議，將軍2和將軍3把（編號(hào)2）記錄下來(lái)，如果有其他參謀提出更小的編號(hào)，將被拒絕；同時(shí)讓通信兵帶信回去，內(nèi)容為（ok）；

b) 負(fù)責(zé)通知將軍1的通信兵被抓，因此將軍1沒(méi)收到參謀2的提議；

5） 參謀1收到至少2個(gè)將軍的回復(fù)，再次派通信兵帶信給有答復(fù)的2個(gè)將軍，內(nèi)容為（編號(hào)1，進(jìn)攻時(shí)間1）；

6） 2個(gè)將軍的情況如下

a) 將軍1收到了（編號(hào)1，進(jìn)攻時(shí)間1），和自己保存的編號(hào)相同，因此把（編號(hào)1，進(jìn)攻時(shí)間1）保存下來(lái)；同時(shí)讓通信兵帶信回去，內(nèi)容為（Accepted）；

b) 將軍2收到了（編號(hào)1，進(jìn)攻時(shí)間1），由于（編號(hào)1）小于已經(jīng)保存的（編號(hào)2），因此讓通信兵帶信回去，內(nèi)容為（Rejected，編號(hào)2）；

7） 參謀2收到至少2個(gè)將軍的回復(fù)，再次派通信兵帶信給有答復(fù)的2個(gè)將軍，內(nèi)容為（編號(hào)2，進(jìn)攻時(shí)間2）；

8） 將軍2和將軍3收到了（編號(hào)2，進(jìn)攻時(shí)間2），和自己保存的編號(hào)相同，因此把（編號(hào)2，進(jìn)攻時(shí)間2）保存下來(lái)，同時(shí)讓通信兵帶信回去，內(nèi)容為（Accepted）；

9） 參謀2收到至少2個(gè)將軍的（Accepted）內(nèi)容，確認(rèn)進(jìn)攻時(shí)間已經(jīng)被多數(shù)派接受；

10） 參謀1只收到了1個(gè)將軍的（Accepted）內(nèi)容，同時(shí)收到一個(gè)（Rejected，編號(hào)2）；參謀1重新發(fā)起提議，派通信兵帶信給3個(gè)將軍，內(nèi)容為（編號(hào)3）；

11） 3個(gè)將軍的情況如下

a) 將軍1收到參謀1的提議，由于（編號(hào)3）大于之前保存的（編號(hào)1），因此把（編號(hào)3）保存下來(lái)；由于將軍1已經(jīng)接受參謀1前一次的提議，因此讓通信兵帶信回去，內(nèi)容為（編號(hào)1，進(jìn)攻時(shí)間1）；

b) 將軍2收到參謀1的提議，由于（編號(hào)3）大于之前保存的（編號(hào)2），因此把（編號(hào)3）保存下來(lái)；由于將軍2已經(jīng)接受參謀2的提議，因此讓通信兵帶信回去，內(nèi)容為（編號(hào)2，進(jìn)攻時(shí)間2）；

c) 負(fù)責(zé)通知將軍3的通信兵被抓，因此將軍3沒(méi)收到參謀1的提議；

12） 參謀1收到了至少2個(gè)將軍的回復(fù)，比較兩個(gè)回復(fù)的編號(hào)大小，選擇大編號(hào)對(duì)應(yīng)的進(jìn)攻時(shí)間作為最新的提議；參謀1再次派通信兵帶信給有答復(fù)的2個(gè)將軍，內(nèi)容為（編號(hào)3，進(jìn)攻時(shí)間2）；

13） 將軍1和將軍2收到了（編號(hào)3，進(jìn)攻時(shí)間2），和自己保存的編號(hào)相同，因此保存（編號(hào)3，進(jìn)攻時(shí)間2），同時(shí)讓通信兵帶信回去，內(nèi)容為（Accepted）；

14） 參謀1收到了至少2個(gè)將軍的（accepted）內(nèi)容，確認(rèn)進(jìn)攻時(shí)間已經(jīng)被多數(shù)派接受；

小結(jié)

BasicPaxos算法難理解，除了講故事的背景不熟悉之外，還有以下幾點(diǎn)

1） 參與的各方并不是要針?shù)h相對(duì)，拼個(gè)你死我活；而是要合作共贏，最終達(dá)成一個(gè)共識(shí)；當(dāng)大家講起投票的時(shí)候，往往第一反應(yīng)是要針?shù)h相對(duì)，沒(méi)想到是要合作共贏；很明顯可以想到，在第二個(gè)場(chǎng)景下，如果參謀1為了逞英雄，強(qiáng)行要提交他提出的進(jìn)攻時(shí)間1，那么最終是無(wú)法達(dá)成一個(gè)共識(shí)的；這里的點(diǎn)就在于參謀1違反了規(guī)則，相當(dāng)于產(chǎn)生了拜占庭錯(cuò)誤；

2） 常規(guī)的通信協(xié)議設(shè)計(jì)，對(duì)于寫(xiě)操作，通常都是只返回成功和失敗的狀態(tài)，不會(huì)返回更多的東西；但BasicPaxos的prepare和commit，將軍除了返回成功還是失敗的狀態(tài)之外，還會(huì)把之前已經(jīng)發(fā)生的一些狀態(tài)帶回給參謀，這個(gè)和常規(guī)的通信協(xié)議是不同的；

3） 在兩軍問(wèn)題的背景下，其實(shí)知道進(jìn)攻時(shí)間被至少2個(gè)將軍接受的是參謀，而不是將軍；在“兩個(gè)參謀交叉提議的場(chǎng)景”下，當(dāng)參謀1沒(méi)有做第2次prepare之前，將軍1記錄的其實(shí)是一個(gè)錯(cuò)誤的進(jìn)攻時(shí)間；理論上來(lái)說(shuō)，任何一個(gè)將軍在任何一個(gè)時(shí)刻都無(wú)法判斷自己不是處在將軍1的場(chǎng)景下；因此BasicPaxos在3個(gè)藍(lán)軍組成的系統(tǒng)中達(dá)成了一個(gè)共識(shí)，但并沒(méi)有為每個(gè)將軍明確了共識(shí)；

4） 本文的兩個(gè)場(chǎng)景都以“兩個(gè)參謀”來(lái)講，這里的“兩個(gè)參謀”可能是真的兩個(gè)不同的參謀，也可能是同一個(gè)參謀因?yàn)槟撤N原因先后做了多次提議；對(duì)應(yīng)分布式系統(tǒng)的場(chǎng)景

a） 真的有兩個(gè)并發(fā)的client

b） 兩個(gè)client一先一后；第一個(gè)client執(zhí)行到某個(gè)步驟因?yàn)槟撤N原因停止了；過(guò)了一段時(shí)間，另外一個(gè)client接著操作同一個(gè)數(shù)據(jù)

c） 同一個(gè)client重試；第一次執(zhí)行到某一步驟因?yàn)槟撤N原因停止了，立即或者稍后進(jìn)行了重試

后記

寫(xiě)這篇文章的時(shí)候，參考了以下兩篇文章。

Paxos算法細(xì)節(jié)詳解(一)--通過(guò)現(xiàn)實(shí)世界描述算法

http://www.cnblogs.com/endsock/p/3480093.html

第一篇文章用了我們喜聞樂(lè)見(jiàn)的背景，大部分內(nèi)容非常容易理解，尤其是用比特幣來(lái)映射編號(hào)，非常貼切；只是對(duì)于proposer-1小姐最后的“背叛”會(huì)有點(diǎn)違反常識(shí)。看完這個(gè)故事之后就一直在想更貼切的背景。在兩軍問(wèn)題中，藍(lán)軍各方是要合作達(dá)成一個(gè)共識(shí)；對(duì)于參謀來(lái)說(shuō)，獲得了前一個(gè)參謀的提議就接受，而不再提出自己的提議是符合邏輯的，這個(gè)和paxos也更加吻合。在實(shí)際的分布式系統(tǒng)中，如果遇到?jīng)_突，涉及的各方也不是要針?shù)h相對(duì)爭(zhēng)個(gè)你死我活，想要的只是能發(fā)現(xiàn)沖突，只有一方成功、或者全部失敗都無(wú)所謂，只要能保證數(shù)據(jù)一致就行。

以兩軍問(wèn)題為背景，在提議編號(hào)上找不到合適的映射點(diǎn)，比較生硬，這一點(diǎn)不如第一遍文章中的故事。

Question 7: The Two Generals’ Problem of reaching consensus on when to attack is unsolvable, how come it’s possible to have consensus with Paxos?

http://bogdan.pistol.gg/2014/10/20/paxos-algorithm-explained-part-2-insights/#q7

paxos最終仍然無(wú)法解決兩軍問(wèn)題，即使是擴(kuò)展到3軍也是無(wú)法解決的。在3軍背景下，按paxos算法的定義，最后是達(dá)成了一個(gè)共同的進(jìn)攻時(shí)間，3軍中的任何一方都可以通過(guò)paxos算法讀取出這個(gè)進(jìn)攻時(shí)間。但3軍怎么知道在什么時(shí)候去讀取、其他人是否已經(jīng)讀取，這是一個(gè)和兩軍問(wèn)題同樣的問(wèn)題；同時(shí)由于通信兵可能無(wú)限延遲，可能部分藍(lán)軍在進(jìn)攻時(shí)間之前讀取到了，部分藍(lán)軍可能在進(jìn)攻時(shí)間之后才讀取到，所以兩軍最終還是無(wú)解的。第二篇參考文章中也詳細(xì)描述了這些問(wèn)題。所以寫(xiě)paxos和兩軍問(wèn)題，不是說(shuō)paxos解決了兩軍問(wèn)題，只是借用兩軍問(wèn)題的背景來(lái)演繹paxos。