前言
Paxos 一致性協(xié)議可以說(shuō)是一致性協(xié)議研究的起點(diǎn)浅碾，也以難以理解聞名部翘。其實(shí)協(xié)議本身并沒(méi)有多難理解，它的難理解性主要體現(xiàn)在：為何如此設(shè)計(jì)協(xié)議以及如何證明其正確性营密。本文嘗試通過(guò)流程圖來(lái)說(shuō)明協(xié)議的內(nèi)容以及基本應(yīng)用過(guò)程始腾，不涉及如何證明其正確性仁连。
基本概念
Paxos 可以分為兩種：
- Single-Decree Paxos：決策單個(gè) Value
- Multi-Paxos：連續(xù)決策多個(gè) Value蓝丙，并且保證每個(gè)節(jié)點(diǎn)上的順序完全一致邪铲，多 Paxos 往往是同事運(yùn)行多個(gè)單 Paxos 協(xié)議共同執(zhí)行的結(jié)果硫豆。
本文只關(guān)注單 Paxos 的原理龙巨，理解了單 Paxos，多 Paxos 也就不難理解了熊响。
Paxos 協(xié)議中的三種角色
- 倡議者（Proposer）：倡議者可以提出提議（數(shù)值或者操作命令）以供投票表決
- 接受者（Acceptor）：接受者可以對(duì)倡議者提出的提議進(jìn)行投票表決旨别，提議有超半數(shù)的接受者投票即被選中
- 學(xué)習(xí)者（Learner）：學(xué)習(xí)者無(wú)投票權(quán)，只是從接受者那里獲知哪個(gè)提議被選中
在協(xié)議中汗茄，每個(gè)節(jié)點(diǎn)可以同時(shí)扮演以上多個(gè)角色秸弛。
Paxos 的特點(diǎn)
- 一個(gè)或多個(gè)節(jié)點(diǎn)可以提出提議
- 系統(tǒng)必須針對(duì)所有提案中的某個(gè)提案達(dá)成一致（超過(guò)半數(shù)的接受者選中）
- 最多只能對(duì)一個(gè)確定的提議達(dá)成一致
- 只要超半數(shù)的節(jié)點(diǎn)存活且可互相通信，整個(gè)系統(tǒng)一定能達(dá)成一致?tīng)顟B(tài)洪碳，即選擇一個(gè)確定的提議
協(xié)議圖示
通過(guò)上面的流程胆屿，如果有多個(gè)節(jié)點(diǎn)同時(shí)提出各自的提議，Paxos 就可以保證從中選出一個(gè)唯一確定的值偶宫，保證分布式系統(tǒng)的一致性非迹。
實(shí)例
下面我們通過(guò)例子來(lái)理解 Paxos 的實(shí)際應(yīng)用過(guò)程。
假設(shè)現(xiàn)在有五個(gè)節(jié)點(diǎn)的分布式系統(tǒng)纯趋，此時(shí) A 節(jié)點(diǎn)打算提議 X 值憎兽，E 節(jié)點(diǎn)打算提議 Y 值，其他節(jié)點(diǎn)沒(méi)有提議吵冒。
假設(shè)現(xiàn)在 A 節(jié)點(diǎn)廣播它的提議（也會(huì)發(fā)送給自己）纯命，由于網(wǎng)絡(luò)延遲的原因，只有 A痹栖，B亿汞，C 節(jié)點(diǎn)收到了。注意即使 A揪阿，E 節(jié)點(diǎn)的提議同時(shí)到達(dá)某個(gè)節(jié)點(diǎn)疗我，它也必然有個(gè)先后處理的順序，這里的“同時(shí)”不是真正意義上的“同時(shí)”南捂。
A吴裤，B，C接收提議之后溺健，由于這是第一個(gè)它們接收到的提議麦牺，acceptedProposal 和 acceptedValue 都為空。
由于 A 節(jié)點(diǎn)已經(jīng)收到超半數(shù)的節(jié)點(diǎn)響應(yīng)，且返回的 acceptedValue 都為空剖膳，也就是說(shuō)它可以用 X 作為提議的值來(lái)發(fā)生 Accept 請(qǐng)求魏颓，A，B吱晒，C接收到請(qǐng)求之后甸饱，將 acceptedValue 更新為 X。
A枕荞，B柜候，C 會(huì)發(fā)生 minProposal 給 A，A 檢查發(fā)現(xiàn)沒(méi)有大于 1 的 minProposal 出現(xiàn)躏精，此時(shí) X 已經(jīng)被選中渣刷。等等，我們是不是忘了D矗烛，E節(jié)點(diǎn)辅柴？它們的 acceptedValue 并不是 X，系統(tǒng)還處于不一致?tīng)顟B(tài)瞭吃。至此碌嘀，Paxos 過(guò)程還沒(méi)有結(jié)束，我們繼續(xù)看歪架。
此時(shí) E 節(jié)點(diǎn)選擇 Proposal ID 為 2 發(fā)送 Prepare 請(qǐng)求股冗，結(jié)果就和上面不一樣了，因?yàn)?C 節(jié)點(diǎn)已經(jīng)接受了 A 節(jié)點(diǎn)的提議和蚪，它不會(huì)三心二意止状，所以就告訴 E 節(jié)點(diǎn)它的選擇，E 節(jié)點(diǎn)也很紳士攒霹，既然 C 選擇了 A 的提議怯疤，那我也選它吧。于是催束，E 發(fā)起 Accept 請(qǐng)求集峦，使用 X 作為提議值，至此抠刺，整個(gè)分布式系統(tǒng)達(dá)成了一致塔淤，大家都選擇了 X。
上面是 Paxos 的一個(gè)簡(jiǎn)單應(yīng)用過(guò)程矫付，其他復(fù)雜的場(chǎng)景也可以根據(jù)流程圖慢慢推導(dǎo)凯沪，這里只是拋磚引玉。
