分布式一致性算法——Paxos
Paxos分析
Paxos算法是萊斯利·蘭伯特(Leslie Lamport)1990年提出的一種基于消息傳遞的一致性算法卜录。
Paxos算法目前在Google的Chubby牛曹、MegaStore、Spanner等系統(tǒng)中得到了應(yīng)用，Hadoop中的ZooKeeper也使用了Paxos算法盖奈，在上面的各個系統(tǒng)中恶守，使用的算法與Lamport提出的原始Paxos并不完全一樣，這個以后再慢慢分析破加。
Paxos算法解決的問題是一個分布式系統(tǒng)如何就某個值（決議）達(dá)成一致俱恶。在工程實(shí)踐意義上來說，就是可以通過Paxos實(shí)現(xiàn)多副本一致性范舀，分布式鎖合是，名字管理，序列號分配等锭环。比如聪全，在一個分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致辅辩，每個節(jié)點(diǎn)執(zhí)行相同的操作序列难礼，那么他們最后能得到一個一致的狀態(tài)。為保證每個節(jié)點(diǎn)執(zhí)行相同的命令序列玫锋，需要在每一條指令上執(zhí)行一個“一致性算法”以保證每個節(jié)點(diǎn)看到的指令一致蛾茉。
基于Paxos協(xié)議構(gòu)建的系統(tǒng)，只需要系統(tǒng)中超過半數(shù)的節(jié)點(diǎn)在線且相互通信正常即可正常對外提供服務(wù)撩鹿。它的核心實(shí)現(xiàn)Paxos Instance主要包括兩個階段:準(zhǔn)備階段(prepare phase)和提議階段(accept phase)谦炬。
在Paxos算法中，分為4種角色：
- Proposer ：提議者
- Acceptor：決策者
- Client：產(chǎn)生議題者
- Learner：最終決策學(xué)習(xí)者
上面4種角色中三痰，提議者和決策者是很重要的吧寺，其他的2個角色在整個算法中應(yīng)該算做打醬油的
為什么需要3個Acceptor？因?yàn)锳cceptor必須是最少大于等于3個散劫，并且必須是奇數(shù)個稚机，因?yàn)橐纬啥鄶?shù)派嘛，如果是偶數(shù)個获搏，比如4個赖条，2個接受2個不接受，各執(zhí)己見常熙，沒法搞下去了纬乍。
為什么是3個Proposer？ 其實(shí)無所謂是多少個了裸卫，1~n 都可以的仿贬；如果是1個proposer，毫無競爭壓力墓贿，很順利的完成2階段提交茧泪，Acceptor們最終批準(zhǔn)了事蜓氨。如果是多個proposer就比較復(fù)雜了
概念與術(shù)語
- Proposer：提議發(fā)起者，處理客戶端請求队伟，將客戶端的請求發(fā)送到集群中穴吹，以便決定這個值是否可以被批準(zhǔn)。
- Acceptor：提議批準(zhǔn)者嗜侮，負(fù)責(zé)處理接收到的提議港令，他們的回復(fù)就是一次投票，會存儲一些狀態(tài)來決定是否接收一個值锈颗。
- replica：節(jié)點(diǎn)或者副本顷霹，分布式系統(tǒng)中的一個server，一般是一臺單獨(dú)的物理機(jī)或者虛擬機(jī)宜猜，同時(shí)承擔(dān)paxos中的提議者和接收者角色泼返。
- ProposalId：每個提議都有一個編號，編號高的提議優(yōu)先級高姨拥。
- Paxos Instance：Paxos中用來在多個節(jié)點(diǎn)之間對同一個值達(dá)成一致的過程绅喉，比如同一個日志序列號：logIndex，不同的logIndex屬于不同的Paxos Instance叫乌。
- acceptedProposal：在一個Paxos Instance內(nèi)柴罐，已經(jīng)接收過的提議
- acceptedValue：在一個Paxos Instance內(nèi)，已經(jīng)接收過的提議對應(yīng)的值憨奸。
- minProposal：在一個Paxos Instance內(nèi)革屠，當(dāng)前接收的最小提議值，會不斷更新
背景
在計(jì)算機(jī)通信理論中排宰，有一個著名的兩軍問題(two-army problem)似芝，講述通信的雙方通過ACK來達(dá)成共識，永遠(yuǎn)會有一個在途的ACK需要進(jìn)行確認(rèn)板甘，因此無法達(dá)成共識党瓮。
兩軍問題和Basic Paxos非常相似
- 通信的各方需要達(dá)成共識；
- 通信的各方僅需要達(dá)成一個共識盐类；
- 假設(shè)的前提是信道不穩(wěn)定寞奸，有丟包、延遲或者重放在跳，但消息不會被篡改枪萄。
Basic Paxos最早以希臘議會的背景來講解，但普通人不理解希臘議會的運(yùn)作模式猫妙，因此看Basic Paxos的論文會比較難理解瓷翻。兩軍問題的背景大家更熟悉，因此嘗試用這個背景來演繹一下Basic Paxos。
為了配合Basic Paxos的多數(shù)派概念逻悠，把兩軍改為3軍元践；同時(shí)假設(shè)了將軍和參謀的角色。
假設(shè)的3軍問題
- 1支紅軍在山谷里扎營童谒，在周圍的山坡上駐扎著3支藍(lán)軍；
- 紅軍比任意1支藍(lán)軍都要強(qiáng)大沪羔；如果1支藍(lán)軍單獨(dú)作戰(zhàn)饥伊，紅軍勝；如果2支或以上藍(lán)軍同時(shí)進(jìn)攻蔫饰，藍(lán)軍勝琅豆；
- 三支藍(lán)軍需要同步他們的進(jìn)攻時(shí)間；但他們惟一的通信媒介是派通信兵步行進(jìn)入山谷篓吁，在那里他們可能被俘虜茫因，從而將信息丟失；或者為了避免被俘虜杖剪，可能在山谷停留很長時(shí)間冻押；
- 每支軍隊(duì)有1個參謀負(fù)責(zé)提議進(jìn)攻時(shí)間；每支軍隊(duì)也有1個將軍批準(zhǔn)參謀提出的進(jìn)攻時(shí)間盛嘿；很明顯洛巢，1個參謀提出的進(jìn)攻時(shí)間需要獲得至少2個將軍的批準(zhǔn)才有意義；
- 問題：是否存在一個協(xié)議次兆，能夠使得藍(lán)軍同步他們的進(jìn)攻時(shí)間稿茉？
接下來以兩個假設(shè)的場景來演繹BasicPaxos；參謀和將軍需要遵循一些基本的規(guī)則
- 參謀以兩階段提交（prepare/commit）的方式來發(fā)起提議芥炭，在prepare階段需要給出一個編號漓库；
- 在prepare階段產(chǎn)生沖突，將軍以編號大小來裁決园蝠，編號大的參謀勝出渺蒿；
- 參謀在prepare階段如果收到了將軍返回的已接受進(jìn)攻時(shí)間，在commit階段必須使用這個返回的進(jìn)攻時(shí)間砰琢；
兩個參謀先后提議的場景
- 參謀1發(fā)起提議蘸嘶，派通信兵帶信給3個將軍，內(nèi)容為（編號1）陪汽；
- 3個將軍收到參謀1的提議训唱，由于之前還沒有保存任何編號，因此把（編號1）保存下來挚冤，避免遺忘况增；同時(shí)讓通信兵帶信回去，內(nèi)容為（ok）训挡；
- 參謀1收到至少2個將軍的回復(fù)澳骤，再次派通信兵帶信給3個將軍歧强，內(nèi)容為（編號1，進(jìn)攻時(shí)間1）为肮；
- 3個將軍收到參謀1的時(shí)間摊册，把（編號1，進(jìn)攻時(shí)間1）保存下來颊艳，避免遺忘茅特；同時(shí)讓通信兵帶信回去，內(nèi)容為（Accepted）棋枕；
- 參謀1收到至少2個將軍的（Accepted）內(nèi)容白修，確認(rèn)進(jìn)攻時(shí)間已經(jīng)被大家接收；
- 參謀2發(fā)起提議重斑，派通信兵帶信給3個將軍兵睛，內(nèi)容為（編號2）；
- 3個將軍收到參謀2的提議窥浪，由于（編號2）比（編號1）大祖很，因此把（編號2）保存下來，避免遺忘寒矿；又由于之前已經(jīng)接受參謀1的提議突琳，因此讓通信兵帶信回去，內(nèi)容為（編號1符相，進(jìn)攻時(shí)間1）拆融；
- 參謀2收到至少2個將軍的回復(fù)，由于回復(fù)中帶來了已接受的參謀1的提議內(nèi)容啊终，參謀2因此不再提出新的進(jìn)攻時(shí)間镜豹，接受參謀1提出的時(shí)間；
兩個參謀交叉提議的場景
- 參謀1發(fā)起提議蓝牲，派通信兵帶信給3個將軍趟脂，內(nèi)容為（編號1）；
3個將軍的情況如下
將軍1和將軍2收到參謀1的提議例衍，將軍1和將軍2把（編號1）記錄下來昔期，如果有其他參謀提出更小的編號，將被拒絕佛玄；同時(shí)讓通信兵帶信回去硼一，內(nèi)容為（ok）；
負(fù)責(zé)通知將軍3的通信兵被抓梦抢，因此將軍3沒收到參謀1的提議般贼；
- 參謀2在同一時(shí)間也發(fā)起了提議，派通信兵帶信給3個將軍，內(nèi)容為（編號2）哼蛆；
3個將軍的情況如下
將軍2和將軍3收到參謀2的提議蕊梧，將軍2和將軍3把（編號2）記錄下來，如果有其他參謀提出更小的編號腮介，將被拒絕肥矢；同時(shí)讓通信兵帶信回去，內(nèi)容為（ok）叠洗；
負(fù)責(zé)通知將軍1的通信兵被抓橄抹，因此將軍1沒收到參謀2的提議；
- 參謀1收到至少2個將軍的回復(fù)惕味，再次派通信兵帶信給有答復(fù)的2個將軍，內(nèi)容為（編號1玉锌，進(jìn)攻時(shí)間1）名挥；
2個將軍的情況如下
將軍1收到了（編號1，進(jìn)攻時(shí)間1）主守，和自己保存的編號相同禀倔，因此把（編號1，進(jìn)攻時(shí)間1）保存下來参淫；同時(shí)讓通信兵帶信回去救湖，內(nèi)容為（Accepted）；
將軍2收到了（編號1涎才，進(jìn)攻時(shí)間1）鞋既，由于（編號1）小于已經(jīng)保存的（編號2），因此讓通信兵帶信回去耍铜，內(nèi)容為（Rejected邑闺，編號2）；
參謀2收到至少2個將軍的回復(fù)棕兼，再次派通信兵帶信給有答復(fù)的2個將軍陡舅，內(nèi)容為（編號2，進(jìn)攻時(shí)間2）伴挚；
將軍2和將軍3收到了（編號2靶衍，進(jìn)攻時(shí)間2），和自己保存的編號相同茎芋，因此把（編號2颅眶，進(jìn)攻時(shí)間2）保存下來，同時(shí)讓通信兵帶信回去败徊，內(nèi)容為（Accepted）帚呼；
參謀2收到至少2個將軍的（Accepted）內(nèi)容，確認(rèn)進(jìn)攻時(shí)間已經(jīng)被多數(shù)派接受；
參謀1只收到了1個將軍的（Accepted）內(nèi)容煤杀，同時(shí)收到一個（Rejected眷蜈，編號2）；參謀1重新發(fā)起提議沈自，派通信兵帶信給3個將軍酌儒，內(nèi)容為（編號3）；
3個將軍的情況如下
將軍1收到參謀1的提議枯途，由于（編號3）大于之前保存的（編號1）忌怎，因此把（編號3）保存下來；由于將軍1已經(jīng)接受參謀1前一次的提議酪夷，因此讓通信兵帶信回去榴啸，內(nèi)容為（編號1，進(jìn)攻時(shí)間1）晚岭；
將軍2收到參謀1的提議鸥印，由于（編號3）大于之前保存的（編號2），因此把（編號3）保存下來坦报；由于將軍2已經(jīng)接受參謀2的提議库说，因此讓通信兵帶信回去，內(nèi)容為（編號2片择，進(jìn)攻時(shí)間2）潜的；
負(fù)責(zé)通知將軍3的通信兵被抓，因此將軍3沒收到參謀1的提議字管；
- 參謀1收到了至少2個將軍的回復(fù)啰挪，比較兩個回復(fù)的編號大小，選擇大編號對應(yīng)的進(jìn)攻時(shí)間作為最新的提議纤掸；參謀1再次派通信兵帶信給有答復(fù)的2個將軍脐供，內(nèi)容為（編號3，進(jìn)攻時(shí)間2）借跪；
- 將軍1和將軍2收到了（編號3政己，進(jìn)攻時(shí)間2），和自己保存的編號相同掏愁，因此保存（編號3歇由，進(jìn)攻時(shí)間2），同時(shí)讓通信兵帶信回去果港，內(nèi)容為（Accepted）沦泌；
- 參謀1收到了至少2個將軍的（accepted）內(nèi)容，確認(rèn)進(jìn)攻時(shí)間已經(jīng)被多數(shù)派接受辛掠；
小結(jié)
BasicPaxos算法難理解谢谦，除了講故事的背景不熟悉之外释牺，還有以下幾點(diǎn)
- 參與的各方并不是要針鋒相對，拼個你死我活回挽；而是要合作共贏没咙，最終達(dá)成一個共識；當(dāng)大家講起投票的時(shí)候千劈，往往第一反應(yīng)是要針鋒相對祭刚，沒想到是要合作共贏；很明顯可以想到墙牌，在第二個場景下涡驮，如果參謀1為了逞英雄，強(qiáng)行要提交他提出的進(jìn)攻時(shí)間1喜滨，那么最終是無法達(dá)成一個共識的捉捅；這里的點(diǎn)就在于參謀1違反了規(guī)則，相當(dāng)于產(chǎn)生了拜占庭錯誤虽风；
- 常規(guī)的通信協(xié)議設(shè)計(jì)锯梁，對于寫操作，通常都是只返回成功和失敗的狀態(tài)焰情，不會返回更多的東西；但BasicPaxos的prepare和commit剥懒，將軍除了返回成功還是失敗的狀態(tài)之外内舟，還會把之前已經(jīng)發(fā)生的一些狀態(tài)帶回給參謀，這個和常規(guī)的通信協(xié)議是不同的初橘；
- 在兩軍問題的背景下验游，其實(shí)知道進(jìn)攻時(shí)間被至少2個將軍接受的是參謀，而不是將軍保檐；在“兩個參謀交叉提議的場景”下耕蝉，當(dāng)參謀1沒有做第2次prepare之前，將軍1記錄的其實(shí)是一個錯誤的進(jìn)攻時(shí)間夜只；理論上來說垒在，任何一個將軍在任何一個時(shí)刻都無法判斷自己不是處在將軍1的場景下；因此BasicPaxos在3個藍(lán)軍組成的系統(tǒng)中達(dá)成了一個共識扔亥，但并沒有為每個將軍明確了共識场躯；
- 本文的兩個場景都以“兩個參謀”來講，這里的“兩個參謀”可能是真的兩個不同的參謀旅挤，也可能是同一個參謀因?yàn)槟撤N原因先后做了多次提議踢关；對應(yīng)分布式系統(tǒng)的場景
- 真的有兩個并發(fā)的client
- 兩個client一先一后；第一個client執(zhí)行到某個步驟因?yàn)槟撤N原因停止了粘茄；過了一段時(shí)間签舞，另外一個client接著操作同一個數(shù)據(jù)
- 同一個client重試秕脓；第一次執(zhí)行到某一步驟因?yàn)槟撤N原因停止了，立即或者稍后進(jìn)行了重試
Tips
Paxos的關(guān)鍵所在儒搭，后者認(rèn)同前者吠架，否則整個決定過程永無止境。
Paxos主要用于保證分布式存儲中副本（或者狀態(tài)）的一致性师妙。副本要保持一致诵肛，那么，所有副本的更新序列就要保持一致默穴。因?yàn)閿?shù)據(jù)的增刪改查操作一般都存在多個客戶端并發(fā)操作怔檩，到底哪個客戶端先做，哪個客戶端后做蓄诽，這就是更新順序薛训。如果不是分布式，那么可以利用加鎖的方法仑氛，誰先申請到鎖乙埃，誰就先操作。但是在分布式條件下锯岖，存在多個副本介袜，如果依賴申請鎖+副本同步更新完畢再釋放鎖，那么需要有分配鎖的這么一個節(jié)點(diǎn)（如果是多個鎖分配節(jié)點(diǎn)出吹，那么又出現(xiàn)分布式鎖管理的需求遇伞，把鎖給哪一個客戶端又成為一個難點(diǎn)），這個節(jié)點(diǎn)又成為單點(diǎn)捶牢，豈不是可靠性不行了鸠珠，失去了分布式多副本的意義，同時(shí)性能也很差秋麸，另外渐排，還會出現(xiàn)死鎖等情況。
