Paxos作用
功能: 在多個(gè)節(jié)點(diǎn)協(xié)同工作的場(chǎng)景下，一致性地決定一個(gè)變量的值
理解的重點(diǎn)
在每一個(gè)中間條件被推導(dǎo)出來(lái)的時(shí)候晾虑，都必須思考一下玉组，Paxos如何保持節(jié)點(diǎn)之間的一致性静袖。是預(yù)設(shè)條件還是條件中已經(jīng)包含了一致性寡痰。
Paxos模型
下面使用論文中的模型敘述推導(dǎo)過(guò)程(省去listener以簡(jiǎn)化模型)抗楔，其中:
- 實(shí)體
- Value(決議): 變量的值棋凳，下面會(huì)用v代稱(chēng)
- Proposal(議案): 包含決議和一個(gè)唯一的id，下面會(huì)用p{n, v}代稱(chēng)
- proposer(提案人): 提出議案的節(jié)點(diǎn)
- accepter(接受人): 決定議案是否被接受的節(jié)點(diǎn)
- 動(dòng)作
- prepare request: 由proposer發(fā)起
- response(回應(yīng)): accepter對(duì)proposer的prepare request的回應(yīng)
- choose(選擇) / accept(確認(rèn)): accepter對(duì)proposer的accept request的回應(yīng)连躏。
Paxos的推導(dǎo)
那么現(xiàn)在就需要從必要條件剩岳，推導(dǎo)出可實(shí)行的充分條件。在滿(mǎn)足這些充分條件的情況下入热，就能得出變量的值一致這個(gè)斷言拍棕。
模型等價(jià)必要條件: 多數(shù)派accepter選擇了同一個(gè)決議
那么可以先推導(dǎo)出充分條件的一部分:
P1: 每個(gè)accepter必須接受他第一個(gè)收到的決議
其中P1可以充分保證，即使僅僅一個(gè)Proposer提出了一個(gè)決議才顿，這個(gè)決議也會(huì)被選擇。假如沒(méi)有P1尤蒿，那么accepter完全可以等待永遠(yuǎn)不會(huì)到來(lái)的下一個(gè)決議郑气，那么最終可能出現(xiàn)無(wú)休止等待的結(jié)果。P1保證了accepter最終將選擇一個(gè)決議腰池。
但是P1仍然不能充分保證尾组，多數(shù)派accepter選擇同一個(gè)決議。比如一共三個(gè)accepter示弓，都各自選擇了不同的決議的情況讳侨。所以我們需要完善P1，引出P2去充分保證奏属，多數(shù)派accepter選擇同一個(gè)決議跨跨。
P2: 如果一個(gè)決議v被多數(shù)派選擇，那么編號(hào)更高且被選擇的決議囱皿，必須包含v
首先描述一下新的模型: proposer可以提出議案勇婴，accepter可以批準(zhǔn)多個(gè)議案，每個(gè)議案包含一個(gè)決議和唯一編號(hào)嘱腥。那么我們現(xiàn)在想要推導(dǎo)的條件變成了耕渴，多數(shù)派accepter選擇了同一個(gè)提案。這個(gè)新條件蘊(yùn)含前一個(gè)模型的條件（多數(shù)派accepter選擇了同一個(gè)決議）齿兔。
下面詳細(xì)推理一下P2是如何解決多數(shù)派這個(gè)問(wèn)題的橱脸。因?yàn)榇蠖鄶?shù)中文論壇上并沒(méi)有詳細(xì)描述，所以我用榆木腦子腦補(bǔ)了一天分苇，得到了P2的完整詳細(xì)描述:
- 多數(shù)派選擇提案添诉，并不意味著多數(shù)派的accepter全部已經(jīng)選擇了提盤(pán)p{n,v}，而是多數(shù)派中所有accepter医寿，或者選擇了提案p{n,v}吻商，或者還沒(méi)有選擇任何提案
- 如果一個(gè)決議v被任意多數(shù)派選擇，這意味著只要存在足夠的 選擇了決議v的accepter 和 沒(méi)有選擇任何決議的accepter糟红，這兩者的數(shù)量和超過(guò)半數(shù)艾帐。那么這兩個(gè)集合就可以組合成一個(gè)選擇了決議v的多數(shù)派
- 編號(hào)更高且被選擇的提案包含v乌叶，這意味著所有accepter在2條件達(dá)成以后，所能選擇的決議一定是v柒爸。這樣2條件中的多數(shù)派中准浴，沒(méi)有選擇任何提案的accepter，最后選擇的決議也一定是v捎稚，防止了翻轉(zhuǎn)乐横。
- 最重要的就是保證多數(shù)派的弱一致性，無(wú)論通信今野、計(jì)算是否異步葡公，請(qǐng)求到達(dá)順序、中間過(guò)程如何条霜，多數(shù)派都會(huì)達(dá)到最終一致的狀態(tài)催什，選擇了同一個(gè)提案。最終使用了二階段執(zhí)行宰睡，來(lái)保證多數(shù)派的弱一致性蒲凶。
為了保證多數(shù)派一致性，P2并不類(lèi)似與P1拆内，要求單節(jié)點(diǎn)選擇第一個(gè)收到的提案旋圆。所以P2也蘊(yùn)含了一個(gè)風(fēng)險(xiǎn)，因?yàn)椴粩嗟絹?lái)的新提案麸恍，永遠(yuǎn)無(wú)法到達(dá)最終一致的狀態(tài)灵巧。
P2A. 如果一個(gè)議案{n, v}被選擇，那么任何acceptor批準(zhǔn)的議案（編號(hào)更高）包含的決議都是v抹沪。
相比P2孩等，P2A的要求更加具體，容易實(shí)現(xiàn)采够。同時(shí)P2A包含P2肄方。
P2B. 如果一個(gè)議案{n, v}被選擇，那么此后蹬癌，任何proposer提出的議案（編號(hào)更高）包含的決議都是v权她。
通過(guò)限制“提出議案”的行為，可以間接限制“批準(zhǔn)議案”的行為逝薪。P2B與P2A基本等效隅要，不過(guò)P2B相比起來(lái)有更高的容錯(cuò)性，它有效阻止了部分Acceptor因?yàn)殄礄C(jī)等原因產(chǎn)生的錯(cuò)誤的批準(zhǔn)行為董济。
P2C. 對(duì)于任意的v和n步清，如果議案{n, v}被提出，那么存在一個(gè)由acceptor的多數(shù)派組成的集合S，或者a) S中沒(méi)有acceptor批準(zhǔn)過(guò)編號(hào)小于n的議案廓啊，或者b) 在S的任何acceptor批準(zhǔn)的所有議案（編號(hào)小于n）中欢搜，v是編號(hào)最大的議案的決議。
P2C(a)意味著存在一個(gè)多數(shù)派沒(méi)有選擇過(guò)議案谴轮，P2C(b)意味著存在一個(gè)多數(shù)派已經(jīng)選擇了議案(n{m, v})炒瘟，只有這兩種情況下能夠提出議案。這意味著如果一個(gè)議案已經(jīng)被多數(shù)派選擇第步，那么accepter只能批準(zhǔn)相同提議(v)的序號(hào)更高的議案疮装，也就是P2A。多以P2C包含P2B包含P2A粘都。
P2C相比P2B廓推，其實(shí)是增加了沒(méi)有議案被多數(shù)派選擇前的行為指導(dǎo)。更加具體更易實(shí)現(xiàn)翩隧。同時(shí)P2C已經(jīng)解決了多數(shù)派弱一致的具體實(shí)現(xiàn)的問(wèn)題樊展，就是由Proposer去尋找并判定多數(shù)派的最終一致結(jié)果，并維護(hù)這個(gè)結(jié)果鸽心。因此即使多數(shù)派仍然處于不一致?tīng)顟B(tài)(部分節(jié)點(diǎn)未批準(zhǔn)決議v)滚局，但因?yàn)樾碌淖h案必定包含v居暖，所以這些不一致節(jié)點(diǎn)最終也會(huì)達(dá)到一致?tīng)顟B(tài)顽频。
但是P2C距離真正的弱一致性還缺一個(gè)鎖，因?yàn)?strong>查詢(xún)最終一致結(jié)果和提出符合最終一致結(jié)果的議案之間太闺，可能會(huì)產(chǎn)生查詢(xún)結(jié)果變更糯景。因?yàn)榭展?jié)點(diǎn)（未批準(zhǔn)任何提案的節(jié)點(diǎn)）可以屬于任何一個(gè)多數(shù)派，如果它在兩階段中間批準(zhǔn)了舊的提案省骂，并且這一行為導(dǎo)致了原先多數(shù)派消失(因?yàn)槭タ展?jié)點(diǎn)蟀淮，所以數(shù)量不足)，那么第二階段的提案就會(huì)導(dǎo)致最終一致性的混亂钞澳。
因此在兩階段之間的鎖是有必要的怠惶，通過(guò)改進(jìn)P1來(lái)實(shí)現(xiàn)這個(gè)鎖:
P1A. acceptor可以批準(zhǔn)一個(gè)編號(hào)為n的議案，當(dāng)且僅當(dāng)它沒(méi)有回應(yīng)過(guò)一個(gè)編號(hào)大于n的prepare請(qǐng)求轧粟。
P1A就像是一個(gè)前向鎖策治，鎖住了舊提案的批準(zhǔn)請(qǐng)求，但是又防止了死鎖的風(fēng)險(xiǎn)兰吟，因?yàn)樗试S被新提案所覆蓋通惫。
具體實(shí)現(xiàn)
經(jīng)過(guò)一番條件推導(dǎo)，具體實(shí)現(xiàn)已經(jīng)很簡(jiǎn)單了混蔼，可以細(xì)化到各節(jié)點(diǎn)的行為:
Accepter
- 如果接收到的prepare請(qǐng)求的編號(hào)n大于它已經(jīng)回應(yīng)的任何prepare請(qǐng)求履腋，它就回應(yīng)已經(jīng)批準(zhǔn)的編號(hào)最高的議案（如果有的話），并承諾不再回應(yīng)任何編號(hào)小于n的議案
- 如果收到了議案{n, v}的accept請(qǐng)求，它就批準(zhǔn)該議案遵湖，除非它已經(jīng)回應(yīng)了一個(gè)編號(hào)大于n的議案悔政。
Proposer
- Proposer選擇一個(gè)議案編號(hào)n，向acceptor的多數(shù)派發(fā)送編號(hào)也為n的prepare請(qǐng)求奄侠。
- 如果收到了多數(shù)acceptor對(duì)prepare請(qǐng)求（編號(hào)為n）的回應(yīng)卓箫，它就向這些acceptor發(fā)送議案{n, v}的accept請(qǐng)求，其中v是所有回應(yīng)中編號(hào)最高的議案的決議垄潮，或者是proposer選擇的值烹卒，如果回應(yīng)說(shuō)還沒(méi)有議案。
偽代碼
func accepter(request) {
static atomic accepted = 0 // 批準(zhǔn)的提案號(hào)
static atomic responsed = 0 // 回應(yīng)的提案號(hào)
if (request.type == PREPARE and
request.seq > responsed) { // 如果接收到的prepare請(qǐng)求編號(hào)大于已回應(yīng)編號(hào)
responsed = request.req
response(request.src, accepted) // 回應(yīng)已經(jīng)批準(zhǔn)的提案
}
if (request.type == ACCEPT and
accepted <= request.seq) { // 如果收到的accept請(qǐng)求編號(hào)不小于已批準(zhǔn)提案
accepted = request.seq
accept(request) // 批準(zhǔn)提案
}
}
func proposer(stage=INIT) {
static atomic seq = 0
switch (stage):
case INIT: // Init階段
// proposer需要知道集群目前最大的n弯洗，才能提出更新的議案
request(SEQ,
callback = lambda ret: set_seq(ret)
)
break
case PREAPRE: // Prepare階段
request_multi(PREPARE,
seq = seq,
callback = lambda ret: quorum_max(ret)
)
break
case ACCEPT: // Accept階段
request_multi(
seq = seq
)
break
}
