1彤断、一致性算法Paxos
1.1 基礎(chǔ)概念
Paxos算法是Lamport提出的一種基于消息傳遞的分布式一致性算法。
Paxos成就：
自Paxos問世以來就持續(xù)壟斷了分布式一致性算法畅哑，Paxos這個(gè)名詞幾乎等同于分布式一致性。Google的很多大型分布式系統(tǒng)都采用了Paxos算法來解決分布式一致性問題勋陪，如Chubby揩瞪、Megastore以及Spanner等。開源的ZooKeeper拧略，以及MySQL 5.7推出的用來取代傳統(tǒng)的主從復(fù)制的MySQL Group Replication等紛紛采用Paxos算法解決分布式一致性問題芦岂。
然而，Paxos的最大特點(diǎn)就是難垫蛆，不僅難以理解禽最，更難以實(shí)現(xiàn)。
Paxos主要解決的問題
主要是用來解決分布式系統(tǒng)一致性問題袱饭。
| 說明： 分布式系統(tǒng)才用多副本進(jìn)行存儲(chǔ)數(shù)據(jù) , 如果對(duì)多個(gè)副本執(zhí)行序列不控制, 那多個(gè)副本執(zhí)行更新操作,由于網(wǎng)絡(luò)延遲 超時(shí)等故障到值各個(gè)副本的數(shù)據(jù)不一致川无。 我們希望每個(gè)副本的執(zhí)行序列是 [ op1 op2 op3 .... opn ] 不變的, 相同的。 Paxos算法就是將依次來確定不可變變量 op[i]的取值 , 每次確定完op[i]之后,各個(gè)副本執(zhí)行op[i]操作,一次類推虑乖。 結(jié)論： Paxos算法需要解決的問題就是如何在一個(gè)可能發(fā)生上述異常的分布式系統(tǒng)中懦趋，快速且正確地在集群內(nèi)部對(duì)某個(gè)數(shù)據(jù)的值達(dá)成一致。 注：這里某個(gè)數(shù)據(jù)的值并不只是狹義上的某個(gè)數(shù)决左，它可以是一條日志愕够，也可以是一條命令（command）走贪。。惑芭。根據(jù)應(yīng)用場(chǎng)景不同坠狡，某個(gè)數(shù)據(jù)的值有不同的含義。 |
| 引出問題： 我們假設(shè)一種情況遂跟，在一個(gè)集群環(huán)境中逃沿，要求所有機(jī)器上的狀態(tài)是一致的，其中有2臺(tái)機(jī)器想修改某個(gè)狀態(tài)幻锁，機(jī)器A 想把狀態(tài)改為1凯亮，機(jī)器 B 想把狀態(tài)改為2，那么到底聽誰(shuí)的呢哄尔？ 可能會(huì)想到假消，可以像 2PC，3PC 一樣引入一個(gè)協(xié)調(diào)者岭接，誰(shuí)先到富拗，聽誰(shuí)的。 但是如果鸣戴，協(xié)調(diào)者宕機(jī)了呢啃沪？所以需要對(duì)協(xié)調(diào)者也做備份，也要做集群窄锅。這時(shí)候创千，問題來了，這么多協(xié)調(diào)者入偷，聽誰(shuí)的呢追驴？Paxos 算法就是為了解決這個(gè)問題而生的。 |
1.2Paxos術(shù)語(yǔ)
Proposal（提案）：Proposal信息包括提案編號(hào) (Proposal ID) 和提議的值 (Value)
client（客戶端）：客戶端向分布式系統(tǒng)發(fā)出請(qǐng)求 盯串，并等待響應(yīng) 氯檐。例如，對(duì)分布式文件服務(wù)器中文件的寫請(qǐng)求体捏。
Proposer（提案發(fā)起者）：提案者提倡客戶請(qǐng)求，試圖說服Acceptor對(duì)此達(dá)成一致糯崎，并在發(fā)生沖突時(shí)充當(dāng)協(xié)調(diào)者以推動(dòng)協(xié)議向前發(fā)展几缭。
Acceptor（決策者）：可以批準(zhǔn)提Acceptor可以接受（accept）提案；如果某個(gè)提案被選定（chosen）沃呢，那么該提案里的value就被選定了年栓。
Learners（最終決策的學(xué)習(xí)者）：學(xué)習(xí)者充當(dāng)該協(xié)議的復(fù)制因素。
1.3Paxos算法推導(dǎo)過程
假設(shè)有一組可以提出提案的進(jìn)程集合薄霜，那么對(duì)于一個(gè)一致性算法需要保證以下幾點(diǎn)：
1某抓、在這些被提出的提案中纸兔，只有一個(gè)會(huì)被選定
2、如果沒有提案被提出否副，就不應(yīng)該有被選定的提案汉矿。
3、當(dāng)一個(gè)提案被選定后备禀，那么所有進(jìn)程都應(yīng)該能學(xué)習(xí)（learn）到這個(gè)被選定的value
1.3.1只有一個(gè)Accpetor
假設(shè)只有一個(gè)Acceptor（可以有多個(gè)Proposer）洲拇，只要Acceptor接受它收到的第一個(gè)提案，則該提案被選定曲尸，該提案里的value就是被選定的value赋续。這樣就保證只有一個(gè)value會(huì)被選定。
但是另患，如果這個(gè)唯一的Acceptor宕機(jī)了纽乱，那么整個(gè)系統(tǒng)就無(wú)法工作了！為了了保證高可用必須要有多個(gè)Acceptor昆箕！
1.3.2多個(gè)Accptor
多個(gè)Acceptor的情況如下圖鸦列。那么，如何保證在多個(gè)Proposer和多個(gè)Acceptor的情況下選定一個(gè)value呢为严？
首先我們希望即使只有一個(gè)Proposer提出了一個(gè)value敛熬，該value也最終被選定。那么必須有個(gè)約束
P1：一個(gè)Acceptor必須接受它收到的第一個(gè)提案第股。
但是应民，這又會(huì)引出另一個(gè)問題：如果每個(gè)Proposer分別提出不同的value，發(fā)給不同的Acceptor夕吻。根據(jù)P1規(guī)則诲锹，Acceptor分別接受自己收到的第一個(gè)提案，就導(dǎo)致不同的value被選定涉馅。出現(xiàn)了不一致归园。如下圖：
因此需要添加一條規(guī)定
規(guī)定：一個(gè)提案被選定需要被半數(shù)以上的Acceptor接受
這個(gè)規(guī)定又暗示了：『一個(gè)Acceptor必須能夠接受不止一個(gè)提案！』不然可能導(dǎo)致最終沒有value被選定稚矿。比如上圖的情況庸诱。v1、v2晤揣、v3都沒有被選定桥爽，因?yàn)樗鼈兌贾槐灰粋€(gè)Acceptor的接受。
所以在這種情況下昧识，我們使用一個(gè)全局的編號(hào)來標(biāo)識(shí)每一個(gè)Acceptor批準(zhǔn)的提案钠四，當(dāng)一個(gè)具有某value值的提案被半數(shù)以上的Acceptor批準(zhǔn)后，我們就認(rèn)為該value被選定了跪楞。
根據(jù)上面的內(nèi)容缀去，我們現(xiàn)在雖然允許多個(gè)提案被選定侣灶，但必須保證所有被選定的提案都具有相同的value值。否則又會(huì)出現(xiàn)不一致缕碎。
于是有了下面的約束：
P2：如果某個(gè)value編號(hào)為v的提案被選定了褥影，那么每個(gè)編號(hào)更高的被選定提案的value必須也是v。
一個(gè)提案只有被Acceptor接受才可能被選定阎曹，因此我們可以把P2約束改寫成對(duì)Acceptor接受的提案的約束P2a伪阶。
P2a：如果某個(gè)value編號(hào)為v的提案被選定了，那么每個(gè)編號(hào)更高的被Acceptor接受的提案的value必須也是v处嫌。
只要滿足了P2a栅贴，就能滿足P2。
但是熏迹，考慮如下的情況：假設(shè)總的有5個(gè)Acceptor檐薯。Proposer2提出[M1,V1]的提案，Acceptor25（半數(shù)以上）均接受了該提案注暗，于是對(duì)于Acceptor25和Proposer2來講坛缕，它們都認(rèn)為V1被選定。Acceptor1剛剛從宕機(jī)狀態(tài)恢復(fù)過來（之前Acceptor1沒有收到過任何提案）捆昏，此時(shí)Proposer1向Acceptor1發(fā)送了[M2,V2]的提案（V2≠V1且M2>M1）赚楚，對(duì)于Acceptor1來講，這是它收到的第一個(gè)提案骗卜。根據(jù)P1（一個(gè)Acceptor必須接受它收到的第一個(gè)提案宠页。）,Acceptor1必須接受該提案！同時(shí)Acceptor1認(rèn)為V2被選定寇仓。這就出現(xiàn)了兩個(gè)問題：
1. Acceptor1認(rèn)為V2被選定举户，Acceptor2~5和Proposer2認(rèn)為V1被選定。出現(xiàn)了不一致遍烦。
1. V1被選定了俭嘁，但是編號(hào)更高的被Acceptor1接受的提案[M2,V2]的value為V2，且V2≠V1服猪。這就跟P2a（如果某個(gè)value為v的提案被選定了供填，那么每個(gè)編號(hào)更高的被Acceptor接受的提案的value必須也是v）矛盾了。
所以我們要對(duì)P2a約束進(jìn)行強(qiáng)化罢猪！
P2b：如果某個(gè)value為v的提案被選定了捕虽，那么之后任何Proposer提出的編號(hào)更高的提案的value必須也是v。
那么坡脐，如何確保在某個(gè)value為v的提案被選定后，Proposer提出的編號(hào)更高的提案的value都是v呢房揭？
P2c：對(duì)于任意的Mn和Vn,如果提案[Mn,Vn]被提出备闲，那么肯定存在一個(gè)由半數(shù)以上的Acceptor組成的集合S晌端，滿足以下兩個(gè)條件
中的任意一個(gè)：
要么S中每個(gè)Acceptor都沒有接受過編號(hào)小于Mn的提案。
要么S中所有Acceptor批準(zhǔn)的所有編號(hào)小于Mn的提案中恬砂，編號(hào)最大的那個(gè)提案的value值為Vn
1.3.3 Proposer生成提案
在P2c的基礎(chǔ)上如何進(jìn)行提案的生成咧纠，這里有個(gè)比較重要的思想：Proposer生成提案之前，應(yīng)該先去『學(xué)習(xí)』已經(jīng)被選定或者可能被選定的value泻骤，然后以該value作為自己提出的提案的value漆羔。如果沒有value被選定，Proposer才可以自己決定value的值狱掂。這樣才能達(dá)成一致演痒。這個(gè)學(xué)習(xí)的階段是通過一個(gè)『Prepare請(qǐng)求』實(shí)現(xiàn)的。
于是我們得到了如下的提案生成算法：
1. Proposer選擇一個(gè)新的提案編號(hào)N趋惨，然后向某個(gè)Acceptor集合（半數(shù)以上）發(fā)送請(qǐng)求鸟顺，要求該集合中的每個(gè)Acceptor做出如下響應(yīng)（response）：
(a) Acceptor向Proposer承諾保證不再接受任何編號(hào)小于N的提案。
(b) 如果Acceptor已經(jīng)接受過提案器虾，那么就向Proposer反饋已經(jīng)接受過的編號(hào)小于N的讯嫂，但為最大編號(hào)的提案的值。
我們將該請(qǐng)求稱為編號(hào)為N的Prepare請(qǐng)求兆沙。
1. 如果Proposer收到了半數(shù)以上的Acceptor的響應(yīng)欧芽，那么它就可以生成編號(hào)為N，Value為V的提案[N,V]葛圃。這里的V是所有的響應(yīng)中編號(hào)最大的提案的Value千扔。如果所有的響應(yīng)中都沒有提案，那么此時(shí)V就可以由Proposer自己選擇装悲。
生成提案后昏鹃，Proposer將該提案發(fā)送給半數(shù)以上的Acceptor集合，并期望這些Acceptor能接受該提案诀诊。我們稱該請(qǐng)求為Accept請(qǐng)求洞渤。
1.3.4 Acceptor接受提案
上邊可以知道一個(gè)Acceptor可能會(huì)受到來自Proposer的兩種請(qǐng)求，分別是Prepare請(qǐng)求和Accept請(qǐng)求属瓣，對(duì)這兩類請(qǐng)求作出響應(yīng)的條件分別如下
Prepare請(qǐng)求：Acceptor可以在任何時(shí)候響應(yīng)一個(gè)Prepare請(qǐng)求载迄。
Accept請(qǐng)求：在不違背Accept現(xiàn)有承諾的前提下，可以任意響應(yīng)Accept請(qǐng)求抡蛙。
因此护昧，對(duì)Acceptor接受提案給出如下約束：
P1a：一個(gè)Acceptor只要尚未響應(yīng)過任何編號(hào)大于N的Prepare請(qǐng)求，那么他就可以接受這個(gè)編號(hào)為N的提案粗截。
1.3.5算法優(yōu)化
上面的內(nèi)容中惋耙，分別從Proposer和Acceptor對(duì)提案的生成和批準(zhǔn)兩方面來講解了Paxos算法在提案選定過程中的算法細(xì)節(jié)，同時(shí)也在提案的編號(hào)全局唯一的前提下，獲得了一個(gè)提案選定算法绽榛，接下來我們?cè)賹?duì)這個(gè)初步算法做一個(gè)小優(yōu)化湿酸，盡可能的忽略Prepare請(qǐng)求
[圖片上傳失敗...(image-5e6068-1611737863794)]
如果Acceptor收到一個(gè)編號(hào)為N的Prepare請(qǐng)求，在此之前它已經(jīng)響應(yīng)過編號(hào)大于N的Prepare請(qǐng)求灭美。根據(jù)P1a推溃，該Acceptor不可能接受編號(hào)為N的提案。因此届腐，該Acceptor可以忽略編號(hào)為N的Prepare請(qǐng)求铁坎。
通過這個(gè)優(yōu)化，每個(gè)Acceptor只需要記住它已經(jīng)批準(zhǔn)的提案的最大編號(hào)以及它已經(jīng)做出Prepare請(qǐng)求響應(yīng)的提案的最大編號(hào)犁苏，以便出現(xiàn)故障或節(jié)點(diǎn)重啟的情況下硬萍，也能保證P2c的不變性，而對(duì)于Proposer來說傀顾，只要它可以保證不會(huì)產(chǎn)生具有相同編號(hào)的提案襟铭，那么就可以丟棄任意的提案以及它所有的運(yùn)行時(shí)狀態(tài)信息。
1.3.6Paxos算法描述
綜合前面的講解短曾，我們來對(duì)Paxos算法的提案選定過程進(jìn)行下總結(jié)寒砖，那結(jié)合Proposer和Acceptor對(duì)提案的處理邏輯，就可以得到類似于兩階段提交的算法執(zhí)行過程嫉拐。
階段一：
(a) Proposer選擇一個(gè)提案編號(hào)N哩都，然后向半數(shù)以上的Acceptor發(fā)送編號(hào)為N的Prepare請(qǐng)求。
(b) 如果一個(gè)Acceptor收到一個(gè)編號(hào)為N的Prepare請(qǐng)求婉徘，且N大于該Acceptor已經(jīng)響應(yīng)過的所有Prepare請(qǐng)求的編號(hào)漠嵌，那么它就會(huì)將它已經(jīng)接受過的編號(hào)最大的提案（如果有的話）作為響應(yīng)反饋給Proposer，同時(shí)該Acceptor承諾不再接受任何編號(hào)小于N的提案盖呼。
階段二：
(a) 如果Proposer收到半數(shù)以上Acceptor對(duì)其發(fā)出的編號(hào)為N的Prepare請(qǐng)求的響應(yīng)儒鹿，那么它就會(huì)發(fā)送一個(gè)針對(duì)[N,V]提案的Accept請(qǐng)求給半數(shù)以上的Acceptor。注意：V就是收到的響應(yīng)中編號(hào)最大的提案的value几晤，如果響應(yīng)中不包含任何提案约炎，那么V就由Proposer自己決定。
(b) 如果Acceptor收到一個(gè)針對(duì)編號(hào)為N的提案的Accept請(qǐng)求蟹瘾，只要該Acceptor沒有對(duì)編號(hào)大于N的Prepare請(qǐng)求做出過響應(yīng)圾浅，它就接受該提案。
1.3.7Learner學(xué)習(xí)被選定的value
方案一： Learner獲取一個(gè)已經(jīng)被選定的提案的前提是憾朴，該提案已經(jīng)被半數(shù)以上的Acceptor批準(zhǔn)狸捕，因此，最簡(jiǎn)單的做法就是一旦Acceptor批準(zhǔn)了一個(gè)提案众雷，就將該提案發(fā)送給所有的Learner很顯然灸拍，這種做法雖然可以讓Learner盡快地獲取被選定的提案做祝，但是卻需要讓每個(gè)Acceptor與所有的Learner逐個(gè)進(jìn)行一次通信，通信的次數(shù)至少為二者個(gè)數(shù)的乘積株搔。
方案二：另一種可行的方案是剖淀，我們可以讓所有的Acceptor將它們對(duì)提案的批準(zhǔn)情況，統(tǒng)一發(fā)送給一個(gè)特定的Learner（稱為主Learner）, 各個(gè)Learner之間可以通過消息通信來互相感知提案的選定情況纤房，基于這樣的前提，當(dāng)主Learner被通知一個(gè)提案已經(jīng)被選定時(shí)翻诉，它會(huì)負(fù)責(zé)通知其他的learner在這種方案中炮姨，Acceptor首先會(huì)將得到批準(zhǔn)的提案發(fā)送給主Learner,再由其同步給其他Learner.因此較方案一而言，方案二雖然需要多一個(gè)步驟才能將提案通知到所有的learner碰煌，但其通信次數(shù)卻大大減少了舒岸，通常只是Acceptor和Learner的個(gè)數(shù)總和，但同時(shí)芦圾，該方案引入了一個(gè)新的不穩(wěn)定因素：主Learner隨時(shí)可能出現(xiàn)故障蛾派。
方案三：在講解方案二的時(shí)候，我們提到个少，方案二最大的問題在于主Learner存在單點(diǎn)問題洪乍，即主Learner隨時(shí)可能出現(xiàn)故障，因此夜焦，對(duì)方案二進(jìn)行改進(jìn)壳澳，可以將主Learner的范圍擴(kuò)大，即Acceptor可以將批準(zhǔn)的提案發(fā)送給一個(gè)特定的Learner集合茫经，該集合中每個(gè)Learner都可以在一個(gè)提案被選定后通知其他的Learner巷波。這個(gè)Learner集合中的Learner個(gè)數(shù)越多，可靠性就越好卸伞，但同時(shí)網(wǎng)絡(luò)通信的復(fù)雜度也就越高抹镊。
1.3.8如何保證Paxos算法的活性
根據(jù)前面的內(nèi)容講解，我們已經(jīng)基本上了解了Paxos算法的核心邏輯荤傲，那接下來再來看看Paxos算法在實(shí)際過程中的一些細(xì)節(jié)
活性：最終一定會(huì)發(fā)生的事情：最終一定要選定value垮耳。
假設(shè)存在這樣一種極端情況，有兩個(gè)Proposer依次提出了一系列編號(hào)遞增的提案弃酌，導(dǎo)致最終陷入死循環(huán)氨菇，沒有value被選定,具體流程如下:
解決：通過選取主Proposer，并規(guī)定只有主Proposer才能提出議案妓湘。這樣一來只要主Proposer和過半的Acceptor能夠正常進(jìn)行網(wǎng)絡(luò)通信查蓉，那么但凡主Proposer提出一個(gè)編號(hào)更高的提案，該提案終將會(huì)被批準(zhǔn)榜贴，這樣通過選擇一個(gè)主Proposer豌研，整套Paxos算法就能夠保持活性妹田。
