背景

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

兩軍問題和Basic Paxos非常相似

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

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

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

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

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

假設(shè)的3軍問題

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

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

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

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

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

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

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

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

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

兩個參謀先后提議的場景

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

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

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

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

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

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

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

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

兩個參謀交叉提議的場景

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

2） 3個將軍的情況如下

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

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

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

4） 3個將軍的情況如下

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

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

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

6） 2個將軍的情況如下

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

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

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

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

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

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

11） 3個將軍的情況如下

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

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

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

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

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

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

小結(jié)

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

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

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

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

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

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

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

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

后記

寫這篇文章的時候，參考了以下兩篇文章。

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

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

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

以兩軍問題為背景，在提議編號上找不到合適的映射點(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最終仍然無法解決兩軍問題，即使是擴(kuò)展到3軍也是無法解決的。在3軍背景下，按paxos算法的定義，最后是達(dá)成了一個共同的進(jìn)攻時間，3軍中的任何一方都可以通過paxos算法讀取出這個進(jìn)攻時間。但3軍怎么知道在什么時候去讀取、其他人是否已經(jīng)讀取，這是一個和兩軍問題同樣的問題；同時由于通信兵可能無限延遲，可能部分藍(lán)軍在進(jìn)攻時間之前讀取到了，部分藍(lán)軍可能在進(jìn)攻時間之后才讀取到，所以兩軍最終還是無解的。第二篇參考文章中也詳細(xì)描述了這些問題。所以寫paxos和兩軍問題，不是說paxos解決了兩軍問題，只是借用兩軍問題的背景來演繹paxos。