分布式一致性算法Paxos

　　Paxos是一種基于消息傳遞的分布式一致性算法，由Leslie Lamport（萊斯利·蘭伯特）于1990提出。是目前公認(rèn)的解決分布式一致性問題的最有效算法之一。
?

要解決的問題及應(yīng)用場(chǎng)景

?
　　Paxos算法要解決的問題，可以理解為：一個(gè)異步通信的分布式系統(tǒng)中，如何就某一個(gè)值（決議）達(dá)成一致。
　　而此處異步通信是指，消息在網(wǎng)絡(luò)傳輸過程中存在丟失、超時(shí)、亂序現(xiàn)象。
?
　　其典型應(yīng)用場(chǎng)景為：
　　在一個(gè)分布式系統(tǒng)中，如果各節(jié)點(diǎn)初始狀態(tài)一致，而且每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，那么最后就可以得到一個(gè)一致的狀態(tài)。為了保證每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，即需要在每一條指令上執(zhí)行一致性算法（如Paxos算法），來保證每個(gè)節(jié)點(diǎn)指令一致。
?

概念定義

?
　　Proposal：為了就某一個(gè)值達(dá)成一致而發(fā)起的提案，包括提案編號(hào)和提案的值。
?
　　涉及角色如下：
　　Proposer：提案發(fā)起者，為了就某一個(gè)值達(dá)成一致，Proposer可以以任意速度、發(fā)起任意數(shù)量的提案，可以停止或重啟。
　　Acceptor：提案批準(zhǔn)者，負(fù)責(zé)處理接收到的提案，響應(yīng)、作出承諾、或批準(zhǔn)提案。
　　Learner：提案學(xué)習(xí)者，可以從Acceptor處獲取已被批準(zhǔn)的提案。
?

約定

?
　　Paxos需要遵循如下約定：
　　1、一個(gè)Acceptor必須批準(zhǔn)它收到的第一個(gè)提案。
　　2、如果編號(hào)為n的提案被批準(zhǔn)了，那么所有編號(hào)大于n的提案，其值必須與編號(hào)為n的提案的值相同。
?

算法描述

?
　　階段一：準(zhǔn)備階段
?
　　1、Proposer選擇一個(gè)提案編號(hào)n，向Acceptor廣播Prepare(n)請(qǐng)求。
　　2、Acceptor接收到Prepare(n)請(qǐng)求，如果編號(hào)n大于之前已經(jīng)響應(yīng)的所有Prepare請(qǐng)求的編號(hào)，那么將之前批準(zhǔn)過的最大編號(hào)的提案反饋給Proposer，并承諾不再接收編號(hào)比n小的提案。否則不予理會(huì)。
?
　　階段二：批準(zhǔn)階段
?
　　1、Proposer收到半數(shù)以上的Acceptor響應(yīng)后，如果響應(yīng)中不包含任何提案，那么將提案編號(hào)n和自己的值，作為提案發(fā)送Accept請(qǐng)求給Acceptor。否則將編號(hào)n，與收到的響應(yīng)中編號(hào)最大的提案的值，作為提案發(fā)送Accept請(qǐng)求給Acceptor。
　　2、Acceptor收到編號(hào)為n的Accept請(qǐng)求，只要Acceptor尚未對(duì)編號(hào)大于n的Prepare請(qǐng)求做出響應(yīng)，就可以批準(zhǔn)這個(gè)提案。
?

死循環(huán)問題

?
　　如果Proposer1提出編號(hào)為n1的提案，并完成了階段一。與此同時(shí)Proposer2提出了編號(hào)為n2的提案，n2>n1，同樣也完成了階段一。于是Acceptor承諾不再批準(zhǔn)編號(hào)小于n2的提案，當(dāng)Proposer1進(jìn)入階段二時(shí)，將會(huì)被忽略。同理，此時(shí)，Proposer1可以提出編號(hào)為n3的提案，n3>n2，又會(huì)導(dǎo)致Proposer2的編號(hào)為n2的提案進(jìn)入階段二時(shí)被忽略。以此類推，將進(jìn)入死循環(huán)。
?
　　解決辦法：
?
　　可以選擇一個(gè)Proposer作為主Proposer，并約定只有主Proposer才可以提出提案。因此，只要主Proposer可以與過半的Acceptor保持通信，那么但凡主Proposer提出的編號(hào)更高的提案，均會(huì)被批準(zhǔn)。
?

Learner

?
　　一旦Acceptor批準(zhǔn)了某個(gè)提案，即將該提案發(fā)給所有的Learner。為了避免大量通信，Acceptor也可以將批準(zhǔn)的提案，發(fā)給主Learner，由主Learner分發(fā)給其他Learner。考慮到主Learner單點(diǎn)問題，也可以考慮Acceptor將批準(zhǔn)的提案，發(fā)給主Learner組，由主Learner組分發(fā)給其他Learner。
?

參考文檔

?
　　Paxos Made Simple（中文翻譯版）
　　微信自研生產(chǎn)級(jí)paxos類庫(kù)PhxPaxos實(shí)現(xiàn)原理介紹
　　【原創(chuàng)】一步一步理解Paxos算法
?

后記

?
　　Paxos算法相對(duì)難以理解和實(shí)現(xiàn)，因此后來又出現(xiàn)了更容易理解和實(shí)現(xiàn)的Raft算法。
　　后續(xù)會(huì)單獨(dú)總結(jié)。