一.簡(jiǎn)要介紹
在《聊聊分布式存儲(chǔ)——問(wèn)題與矛盾》中已經(jīng)提到液荸，在對(duì)一個(gè)分布式系統(tǒng)進(jìn)行架構(gòu)設(shè)計(jì)時(shí)拇砰，往往會(huì)在可用性和一致性之間反復(fù)權(quán)衡。為了解決分布式一致性問(wèn)題匕垫，產(chǎn)生了一系列一致性協(xié)議和算法。其中比較著名的有：二階段提交協(xié)議（2PC）虐呻、三階段提交協(xié)議（3PC）象泵、Paxos 算法、Raft 算法等斟叼。
我們知道偶惠，信息交換一般有兩種方式，一種是通過(guò)共享內(nèi)存共用一份數(shù)據(jù)朗涩；另一種是通過(guò)消息投遞來(lái)完成信息的傳遞忽孽。
在分布式系統(tǒng)中，節(jié)點(diǎn)之間主要使用消息投遞方式來(lái)完成。但通過(guò)消息投遞的方式會(huì)遇到很多意外的情況兄一，例如網(wǎng)絡(luò)問(wèn)題厘线、進(jìn)程掛掉、機(jī)器掛掉出革、進(jìn)程很慢沒(méi)有響應(yīng)造壮、進(jìn)程重啟等情況，這就會(huì)造成消息重復(fù)骂束、一段時(shí)間內(nèi)部不可達(dá)等現(xiàn)象耳璧。而 Paxos 算法就是基于消息傳遞且具有高度容錯(cuò)特性的一致性算法。換句話說(shuō)展箱，Paxos算法的作用就是在可能發(fā)生這些異常情況的分布式系統(tǒng)中旨枯，快速且正確地在集群內(nèi)部對(duì)某個(gè)數(shù)據(jù)的值達(dá)成一致。
二.背景約束
在各類(lèi)介紹 Paxos 算法的文章中混驰，都會(huì)提到著名的“拜占庭將軍問(wèn)題”召廷，以及偶爾也會(huì)提到的“兩軍問(wèn)題”。關(guān)于這兩個(gè)問(wèn)題的詳細(xì)介紹可以閱讀這篇下面這篇文章账胧，基本講清楚了竞慢。
簡(jiǎn)單的來(lái)說(shuō)，拜占庭將軍問(wèn)題描述了這樣一個(gè)場(chǎng)景：
拜占庭帝國(guó)有許多支軍隊(duì)治泥，不同軍隊(duì)的將軍之間必須制訂一個(gè)統(tǒng)一的行動(dòng)計(jì)劃筹煮，從而做出進(jìn)攻或者撤退的決定，同時(shí)居夹，各個(gè)將軍在地理上都是被分隔開(kāi)來(lái)的败潦，只能依靠軍隊(duì)的通訊員來(lái)進(jìn)行通訊。然而准脂，在所有的通訊員中可能會(huì)存在叛徒劫扒，這些叛徒可以任意篡改消息，從而達(dá)到欺騙將軍的目的狸膏。
這就是著名的“拜占廷將軍問(wèn)題”沟饥。從理論上來(lái)說(shuō)，在分布式計(jì)算領(lǐng)域湾戳，試圖在異步系統(tǒng)和不可靠的通道上來(lái)達(dá)到一致性狀態(tài)是不可能的贤旷。因此在對(duì)一致性的研究過(guò)程中，往往假設(shè)信道是可靠的砾脑。事實(shí)上幼驶，大多數(shù)系統(tǒng)都是部署在同一個(gè)局域網(wǎng)中的，因此消息被篡改的情況非常罕見(jiàn)韧衣；另一方面盅藻，由于硬件和網(wǎng)絡(luò)原因而造成的消息不完整問(wèn)題购桑，只需一套簡(jiǎn)單的校驗(yàn)算法即可避免——因此，在實(shí)際工程實(shí)踐中氏淑，可以假設(shè)不存在拜占庭問(wèn)題勃蜘，即假設(shè)所有消息都是完整的，沒(méi)有被篡改的夸政。
三.基本思路
Paxos 算法是分布式技術(shù)大師 Lamport 提出的元旬。Lamport 為了講述這個(gè)算法，假想了一個(gè)叫做 Paxos 的希臘城邦進(jìn)行選舉的情景守问。這個(gè)算法也是因此而得名匀归。在他的假想中，這個(gè)城邦要采用民主提議和投票的方式選出一個(gè)最終的決議耗帕，但由于城的居民沒(méi)有人原意把全部時(shí)間和精力放在這種事情上穆端，所以他們只能不定時(shí)的來(lái)參加提議，不定時(shí)來(lái)了解提議仿便、投票進(jìn)展体啰，不定時(shí)的表達(dá)自己的投票意見(jiàn)。 Paxos 算法的目標(biāo)就是讓他們按照少數(shù)服從多數(shù)的方式嗽仪，最終達(dá)成一致意見(jiàn)荒勇。
四.算法描述
主要角色
Proposer（提案者/提議者）：提議一個(gè)值，用于被投票決議闻坚。
Acceptor（附議者/接受者）：對(duì)每個(gè)提議進(jìn)行投票沽翔。
Learner（學(xué)習(xí)者/告知者）：被告知投票的結(jié)果，不參與投票過(guò)程窿凤。
執(zhí)行過(guò)程
規(guī)定一個(gè)提議包含兩個(gè)字段：[n, v]仅偎，其中 n 為序號(hào)（具有唯一性），v 為提議值雳殊。
下圖演示了兩個(gè) Proposer（提案者） 和三個(gè) Acceptor（附議者） 的系統(tǒng)中運(yùn)行該算法的初始過(guò)程橘沥，每個(gè) Proposer 都會(huì)向所有 Acceptor 發(fā)送提議請(qǐng)求。
當(dāng) Acceptor 接收到一個(gè)提議請(qǐng)求夯秃，包含的提議為 [n1, v1]座咆，并且之前還未接收過(guò)提議請(qǐng)求，那么發(fā)送一個(gè)提議響應(yīng)寝并，設(shè)置當(dāng)前接收到的提議為 [n1, v1]箫措，并且保證以后不會(huì)再接受序號(hào)小于 n1 的提議。
如下圖衬潦，Acceptor X 在收到 [n=2, v=8] 的提議請(qǐng)求時(shí)，由于之前沒(méi)有接收過(guò)提議植酥，因此就發(fā)送一個(gè) [no previous] （尚無(wú)提案）的提議響應(yīng)镀岛，并且設(shè)置當(dāng)前接收到的提議為 [n=2, v=8]弦牡，并且保證以后不會(huì)再接受序號(hào)小于 2 的提議。其它的 Acceptor 類(lèi)似漂羊。
如果 Acceptor 接收到一個(gè)提議請(qǐng)求驾锰，包含的提議為 [n2, v2]，并且之前已經(jīng)接收過(guò)提議 [n1, v1]走越。如果 n1 > n2椭豫，那么就丟棄該提議請(qǐng)求；否則旨指，發(fā)送提議響應(yīng)赏酥，該提議響應(yīng)包含之前已經(jīng)接收過(guò)的提議 [n1, v1]，設(shè)置當(dāng)前接收到的提議為 [n2, v2]谆构，并且保證以后不會(huì)再接受序號(hào)小于 n2 的提議裸扶。
如下圖，Acceptor Z 收到 Proposer A 發(fā)來(lái)的 [n=2, v=8] 的提議請(qǐng)求搬素，由于之前已經(jīng)接收過(guò) [n=4, v=5] 的提議呵晨，并且 n > 2，因此就拋棄該提議請(qǐng)求熬尺；Acceptor X 收到 Proposer B 發(fā)來(lái)的 [n=4, v=5] 的提議請(qǐng)求摸屠，因?yàn)橹敖邮盏降奶嶙h為 [n=2, v=8]，并且 2 <= 4粱哼，因此就發(fā)送 [n=2, v=8] 的提議響應(yīng)季二，設(shè)置當(dāng)前接收到的提議為 [n=4, v=5]，并且保證以后不會(huì)再接受序號(hào)小于 4 的提議皂吮。Acceptor Y 類(lèi)似戒傻。
當(dāng)一個(gè) Proposer 接收到超過(guò)一半 Acceptor 的提議響應(yīng)時(shí)，就可以發(fā)送接受請(qǐng)求蜂筹。
Proposer A 接收到兩個(gè)提議響應(yīng)之后需纳，就發(fā)送 [n=2, v=8] 接受請(qǐng)求。該接受請(qǐng)求會(huì)被所有 Acceptor 丟棄艺挪，因?yàn)榇藭r(shí)所有 Acceptor 都保證不接受序號(hào)小于 4 的提議不翩。
Proposer B 過(guò)后也收到了兩個(gè)提議響應(yīng)，因此也開(kāi)始發(fā)送接受請(qǐng)求麻裳。需要注意的是口蝠，接受請(qǐng)求的 v 需要取它收到的最大 v 值，也就是 8津坑。因此它發(fā)送 [n=4, v=8] 的接受請(qǐng)求妙蔗。
Acceptor 接收到接受請(qǐng)求時(shí)，如果序號(hào)大于等于該 Acceptor 承諾的最小序號(hào)疆瑰，那么就發(fā)送通知給所有的 Learner（學(xué)習(xí)者）眉反。當(dāng) Learner 發(fā)現(xiàn)有大多數(shù)的 Acceptor 接收了某個(gè)提議昙啄，那么該提議的提議值就被 Paxos 選擇出來(lái)。
【參考文獻(xiàn)】
《從Paxos到ZooKeeper》
原載于本人個(gè)人網(wǎng)站：聊聊分布式存儲(chǔ)-圖解paxos
