前言
Paxos 一致性協(xié)議可以說是一致性協(xié)議研究的起點，也以難以理解聞名。其實協(xié)議本身并沒有多難理解，它的難理解性主要體現(xiàn)在：為何如此設(shè)計協(xié)議以及如何證明其正確性。本文嘗試通過流程圖來說明協(xié)議的內(nèi)容以及基本應(yīng)用過程，不涉及如何證明其正確性。
基本概念
Paxos 可以分為兩種：
- Single-Decree Paxos：決策單個 Value
- Multi-Paxos：連續(xù)決策多個 Value，并且保證每個節(jié)點上的順序完全一致，多 Paxos 往往是同事運行多個單 Paxos 協(xié)議共同執(zhí)行的結(jié)果。
本文只關(guān)注單 Paxos 的原理，理解了單 Paxos，多 Paxos 也就不難理解了。
Paxos 協(xié)議中的三種角色
- 倡議者（Proposer）：倡議者可以提出提議（數(shù)值或者操作命令）以供投票表決
- 接受者（Acceptor）：接受者可以對倡議者提出的提議進行投票表決，提議有超半數(shù)的接受者投票即被選中
- 學(xué)習(xí)者（Learner）：學(xué)習(xí)者無投票權(quán)，只是從接受者那里獲知哪個提議被選中
在協(xié)議中，每個節(jié)點可以同時扮演以上多個角色。
Paxos 的特點
- 一個或多個節(jié)點可以提出提議
- 系統(tǒng)必須針對所有提案中的某個提案達成一致（超過半數(shù)的接受者選中）
- 最多只能對一個確定的提議達成一致
- 只要超半數(shù)的節(jié)點存活且可互相通信，整個系統(tǒng)一定能達成一致狀態(tài)，即選擇一個確定的提議
協(xié)議圖示
通過上面的流程，如果有多個節(jié)點同時提出各自的提議，Paxos 就可以保證從中選出一個唯一確定的值，保證分布式系統(tǒng)的一致性。
實例
下面我們通過例子來理解 Paxos 的實際應(yīng)用過程。
假設(shè)現(xiàn)在有五個節(jié)點的分布式系統(tǒng)，此時 A 節(jié)點打算提議 X 值，E 節(jié)點打算提議 Y 值，其他節(jié)點沒有提議。
假設(shè)現(xiàn)在 A 節(jié)點廣播它的提議（也會發(fā)送給自己），由于網(wǎng)絡(luò)延遲的原因，只有 A，B，C 節(jié)點收到了。注意即使 A，E 節(jié)點的提議同時到達某個節(jié)點，它也必然有個先后處理的順序，這里的“同時”不是真正意義上的“同時”。
A，B，C接收提議之后，由于這是第一個它們接收到的提議，acceptedProposal 和 acceptedValue 都為空。
由于 A 節(jié)點已經(jīng)收到超半數(shù)的節(jié)點響應(yīng)，且返回的 acceptedValue 都為空，也就是說它可以用 X 作為提議的值來發(fā)生 Accept 請求，A，B，C接收到請求之后，將 acceptedValue 更新為 X。
A，B，C 會發(fā)生 minProposal 給 A，A 檢查發(fā)現(xiàn)沒有大于 1 的 minProposal 出現(xiàn)，此時 X 已經(jīng)被選中。等等，我們是不是忘了D，E節(jié)點？它們的 acceptedValue 并不是 X，系統(tǒng)還處于不一致狀態(tài)。至此，Paxos 過程還沒有結(jié)束，我們繼續(xù)看。
此時 E 節(jié)點選擇 Proposal ID 為 2 發(fā)送 Prepare 請求，結(jié)果就和上面不一樣了，因為 C 節(jié)點已經(jīng)接受了 A 節(jié)點的提議，它不會三心二意，所以就告訴 E 節(jié)點它的選擇，E 節(jié)點也很紳士，既然 C 選擇了 A 的提議，那我也選它吧。于是，E 發(fā)起 Accept 請求，使用 X 作為提議值，至此，整個分布式系統(tǒng)達成了一致，大家都選擇了 X。
上面是 Paxos 的一個簡單應(yīng)用過程，其他復(fù)雜的場景也可以根據(jù)流程圖慢慢推導(dǎo)，這里只是拋磚引玉。
