聊聊分布式一致性算法協(xié)議 Paxos
Google的粗粒度鎖服務(wù)Chubby的設(shè)計開發(fā)者Burrows曾經(jīng)說過：所有一致性協(xié)議本質(zhì)上要么是Paxos要么是其變體。
Paxos是什么？
難以理解 在工程是實(shí)現(xiàn)上比較復(fù)雜。
問題產(chǎn)生的背景
“ 這里某個數(shù)據(jù)的值并不只是狹義上的某個數(shù)，它可以是一條日志，也可以是一條命令（command）。根據(jù)應(yīng)用場景不同，某個數(shù)據(jù)的值有不同的含義。
”
相關(guān)概念
Proposer (提案者) Acceptor (人大代表) Learners (廣大群眾)
初次認(rèn)識
回到剛剛說的『對某個數(shù)據(jù)的值達(dá)成一致』，指的是Proposer、Acceptor、Learner都認(rèn)為同一個value被選定（chosen）。那么，Proposer、Acceptor、Learner分別在什么情況下才能認(rèn)為某個value被選定呢？
Proposer：只要Proposer發(fā)的提案被Acceptor接受（剛開始先認(rèn)為只需要一個Acceptor接受即可，在推導(dǎo)過程中會發(fā)現(xiàn)需要半數(shù)以上的Acceptor同意才行），Proposer就認(rèn)為該提案里的value被選定了。
Acceptor：只要Acceptor接受了某個提案，Acceptor就認(rèn)為該提案里的value被選定了。
Learner：作為一個學(xué)習(xí)者，Acceptor告訴Learner哪個value被選定，Learner就認(rèn)為那個value被選定。
問題描述
只有被提出的value才能被選定。 只有一個value被選定。 如果某個進(jìn)程認(rèn)為某個value被選定了，那么這個value必須是真的被選定的那個。
“ Paxos的目標(biāo)：保證最終有一個value會被選定，當(dāng)value被選定后，進(jìn)程最終也能獲取到被選定的value。 ”
每個角色以各自任意的速度進(jìn)行通信執(zhí)行，在這個過程中可能會因?yàn)楦鞣N原因出錯而導(dǎo)致執(zhí)行停止或重啟。當(dāng)一個value被選定之后，因?yàn)楣收显虿呕謴?fù)正常的角色因?yàn)槭チ四承┲匾男畔ⅲ瑢?dǎo)致它們無法確定被選定的值。
消息在傳遞過程中可能出現(xiàn)任意時長的延遲，可能會重復(fù)，也可能丟失。但是消息不會被損壞，即消息內(nèi)容不會被篡改（拜占庭將軍問題）。
推導(dǎo)過程
最簡單的方案——只有一個Acceptor
多個Acceptor
“ P1：一個Acceptor必須接受它收到的第一個提案。
”
但是，這樣又會出現(xiàn)其它的問題：如果每個Proposer所提出的提案value是不同的，并且將提案發(fā)送給不同的Acceptor。根據(jù)P1約束，每個Acceptor都接受它收到的第一個提案，就會出現(xiàn)不同value被選定的情況，出現(xiàn)了不一致。
剛剛是因?yàn)椤阂粋€提案只要被一個Acceptor接受，則該提案的value就被選定了』才導(dǎo)致了出現(xiàn)上面不一致的問題。因此，我們需要加一個規(guī)定：
“ 規(guī)定：一個提案被選定需要被半數(shù)以上的Acceptor接受 ”
“ P2：如果某個value為v的提案被選定了，那么每個編號更高的被選定提案的value必須也是v。
”
一個提案只有被Acceptor接受才可能被選定，因此我們可以把P2約束改寫成對Acceptor接受的提案的約束P2a。
“ P2a：如果某個value為v的提案被選定了，那么每個編號更高的被Acceptor接受的提案的value必須也是v。
”
人大代表1認(rèn)為V2被選定，人大代表2-5和人民法院認(rèn)為V1被選定。出現(xiàn)了不一致。 V1被選定了，但是編號更高的被人大代表1接受的提案[M2,V2]的value為V2，且V2≠V1。這就跟P2a（如果某個value為v的提案被選定了，那么每個編號更高的被Acceptor接受的提案的value必須也是v）矛盾了。
所以，我們要對P2a約束進(jìn)行加強(qiáng)！
P2a是對Acceptor接受的提案約束，但其實(shí)提案是Proposer提出來的，所有我們可以對Proposer提出的提案進(jìn)行約束。得到P2b：
“ P2b：如果某個value為v的提案被選定了，那么之后任何Proposer提出的編號更高的提案的value必須也是v。
”
“ P2c：對于任意的N和V，如果提案[N, V]被提出，那么存在一個半數(shù)以上的Acceptor組成的集合S，滿足以下兩個條件中的任意一個：
S中每個Acceptor都沒有接受過編號小于N的提案。
S中Acceptor接受過的最大編號的提案的value為V。
”
Proposer生成提案
Proposer選擇一個新的提案編號N，然后向某個Acceptor集合（半數(shù)以上）發(fā)送請求，要求該集合中的每個Acceptor做出如下響應(yīng)（response）。
(a) 向Proposer承諾保證不再接受任何編號小于N的提案。
(b) 如果Acceptor已經(jīng)接受過提案，那么就向Proposer響應(yīng)已經(jīng)接受過的編號小于N的最大編號的提案。
我們將該請求稱為編號為N的Prepare請求。
如果Proposer收到了半數(shù)以上的Acceptor的響應(yīng)，那么它就可以生成編號為N，Value為V的提案[N,V]。這里的V是所有的響應(yīng)中編號最大的提案的Value。如果所有的響應(yīng)中都沒有提案，那 么此時V就可以由Proposer自己選擇(一般為當(dāng)前提案)。
生成提案后，Proposer將該提案發(fā)送給半數(shù)以上的Acceptor集合，并期望這些Acceptor能接受該提案。我們稱該請求為Accept請求。（注意：此時接受Accept請求的Acceptor集合不一定是之前響應(yīng)Prepare請求的Acceptor集合）
Acceptor接受提案
Acceptor可以忽略任何請求（包括Prepare請求和Accept請求）而不用擔(dān)心破壞算法的安全性。因此，我們這里要討論的是什么時候Acceptor可以響應(yīng)一個請求。
我們對Acceptor接受提案給出如下約束：
“ P1a：一個Acceptor只要尚未響應(yīng)過任何編號大于N的Prepare請求，那么他就可以接受這個編號為N的提案。
”
如果Acceptor收到一個編號為N的Prepare請求，在此之前它已經(jīng)響應(yīng)過編號大于N的Prepare請求。根據(jù)P1a，該Acceptor不可能接受編號為N的提案。因此，該Acceptor可以忽略編號為N的Prepare請求。當(dāng)然，也可以回復(fù)一個error，讓Proposer盡早知道自己的提案不會被接受。
因此，一個Acceptor只需記住：1. 已接受的編號最大的提案 2. 已響應(yīng)的請求的最大編號。
Paxos算法描述
Proposer選擇一個提案編號N，然后向半數(shù)以上的Acceptor發(fā)送編號為N的Prepare請求。
如果一個Acceptor收到一個編號為N的Prepare請求，且N大于該Acceptor已經(jīng)響應(yīng)過的所有Prepare請求的編號，那么它就會將它已經(jīng)接受過的編號最大的提案（如果有的話） 作為響應(yīng)反饋給Proposer，同時該Acceptor承諾不再接受任何編號小于N的提案。
如果Proposer收到半數(shù)以上Acceptor對其發(fā)出的編號為N的Prepare請求的響應(yīng)，那么它就會發(fā)送一個針對[N,V]提案的Accept請求給半數(shù)以上的Acceptor（和之前的Acceptor不一定相同）。注意：V就是收到的響應(yīng)中編號最大的提案的value，如果響應(yīng)中不包含任何提案，那么V就由Proposer自己決定。
如果Acceptor收到一個針對編號為N的提案的Accept請求，只要該Acceptor沒有對編號大于N的Prepare請求做出過響應(yīng)，它就接受該提案。
Learner學(xué)習(xí)被選定的value
Learner學(xué)習(xí)（獲取）被選定的value有如下三種方案：
方案一
Acceptor接受到一個提案，就將該提案發(fā)送給所有Learners.
優(yōu)點(diǎn)：Learner能夠快速獲取被選定的value
缺點(diǎn)：通信次數(shù)為M*N（M為提案數(shù)，N為Learner數(shù)）
方案二
Acceptor接受一個提案，就將提案發(fā)送給主Learner,主Learner再通知其它Learner
優(yōu)點(diǎn)：通信次數(shù)減少（M+N-1）（M為提案數(shù)，N為Learner數(shù)，M個提案發(fā)送給主Learner，然后主Learner通知N-1個Learner）
缺點(diǎn)：單點(diǎn)故障問題（主Learner可能出現(xiàn)故障）
方案三
Acceptor接受一個提案，就將提案發(fā)送給Learner團(tuán),Learner團(tuán)再通知其它Learner
優(yōu)點(diǎn)：解決了方案二單點(diǎn)故障問題，可靠性好
缺點(diǎn)：實(shí)現(xiàn)復(fù)雜，網(wǎng)絡(luò)通信復(fù)雜度高
如何保證Paxos算法的活性
通過選取主Proposer，就可以保證Paxos算法的活性。通過選取主Proposer，并規(guī)定只有主Proposer才能提出議案。這樣一來只要主Proposer和過半的Acceptor能夠正常進(jìn)行網(wǎng)絡(luò)通信，那么但凡主Proposer提出一個編號更高的提案，該提案終將會被批準(zhǔn)，這樣通過選擇一個主Proposer，整套Paxos算法就能夠保持活性。至此，我們得到一個既能保證安全性，又能保證活性的分布式一致性算法——Paxos算法。
總結(jié)
到此，我們針對Paxos算法是什么、它的特性以及算法的具體推導(dǎo)過程做了詳細(xì)的闡述。Paxos算法是現(xiàn)在很多一致性算法的變體，非常值得我們學(xué)習(xí)~
來源：碼哥字節(jié)
（版權(quán)歸原作者所有，侵刪）
