一.簡(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 算法等州邢。
本文主要介紹?Paxos 算法。
我們知道褪子，信息交換一般有兩種方式量淌，一種是通過(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á)成一致隶校。
二.背景約束
在各類介紹?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)哥放。
四.算法描述
主要角色
1.?Proposer（提案者/提議者）：提議一個(gè)值歼指，用于被投票決議。
2.?Acceptor（附議者/接受者）：對(duì)每個(gè)提議進(jìn)行投票甥雕。
3.?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 類似石景。
如果?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 類似映凳。
當(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)。
