大綱
https://www.zybuluo.com/yulongsun/note/1012707
1. Paxos算法是什么?
Paxos算法是基于消息傳遞且具有高效容錯(cuò)特性的一致性算法,目前公認(rèn)的解決分布式一致性問題最有效的算法之一.
Paxos算法基于2PC,并進(jìn)行了擴(kuò)展.
2. Paxos算法產(chǎn)生背景
2.1 "拜占庭將軍問題"
拜占庭是古代東羅馬帝國的首都桩蓉，由于地域?qū)拸V，守衛(wèi)邊境的多個(gè)將軍（系統(tǒng)中的多個(gè)節(jié)點(diǎn)）需要通過信使來傳遞消息劳闹，達(dá)成某些一致的決定院究。但由于將軍中可能存在叛徒（系統(tǒng)中節(jié)點(diǎn)出錯(cuò)）洽瞬，這些叛徒將努力向不同的將軍發(fā)送不同的消息，試圖會(huì)干擾一致性的達(dá)成业汰。
2.2 Paxos算法由來
故事背景是古希臘 Paxos島上的多個(gè)法官在一個(gè)大廳內(nèi)對(duì)一個(gè)議案進(jìn)行表決伙窃，如何達(dá)成統(tǒng)一的結(jié)果。他們之間通過服務(wù)人員來傳遞紙條样漆，但法官可能離開或進(jìn)入大廳为障，服務(wù)人員可能偷懶去睡覺。
1990 年由 Leslie Lamport 提出的Paxos共識(shí)算法放祟，在工程角度實(shí)現(xiàn)了一種最大化保障分布式系統(tǒng)一致性（存在極小的概率無法實(shí)現(xiàn)一致）的機(jī)制鳍怨。Paxos 被廣泛應(yīng)用在 Chubby、ZooKeeper 這樣的系統(tǒng)中跪妥，Leslie Lamport 因此獲得了 2013 年度圖靈獎(jiǎng)鞋喇。
2.3 產(chǎn)生背景
在常見的分布式系統(tǒng)中，總會(huì)發(fā)生節(jié)點(diǎn)宕機(jī)或網(wǎng)絡(luò)異常(包括消息的重復(fù)骗奖、丟失确徙、延遲、亂序执桌、網(wǎng)絡(luò)分區(qū))等情況鄙皇。
Paxos算法主要就是解決如何在一個(gè)發(fā)生如上故障的分布式系統(tǒng)中，快速正確的在集群內(nèi)**對(duì)某個(gè)值達(dá)成一致**仰挣，并且保證整個(gè)系統(tǒng)的一致性伴逸。
3. 算法詳解
3.1 角色&提案
- [x] 提案(Proposal)
注意：提案的范圍>value.后面會(huì)講到，[提案=編號(hào)+Value].也可表示為[M,V].
以下描述中暫定:提案=P膘壶，Value=V. -
[x] 角色
1错蝴、Proposer ：Proposer可以提出提案(Proposal).
2、Accecptor: Acceptor可以接受提案.一旦接受提案颓芭，提案里面的value值就被選定了.
3顷锰、Learner: Acceptor告訴Learner哪個(gè)提案被選定了，那么Learner就學(xué)習(xí)這個(gè)被chosen的value.
概念關(guān)系圖 - 在具體的實(shí)現(xiàn)中亡问，一個(gè)進(jìn)程即可能是Proposer,也可能是Acceptor官紫，也可能是Learner.
3.2 問題描述
Paxos算法的核心是一致性。所以將從一致性問題的描述來講解該算法怎么解決實(shí)際問題.
- [x] 對(duì)于一個(gè)一致性算法的前置條件：
1州藕、在被提出的P中束世，只有一個(gè)V被chosen.
2、如果沒有P被提出床玻，就沒有V被chosen.
3毁涉、在P被選定后，進(jìn)程都可以學(xué)習(xí)被chose的P. - [x] 假設(shè)不同角色之間可以通過發(fā)送消息來進(jìn)行通信锈死，那么：
1贫堰、每個(gè)角色以任意的速度執(zhí)行穆壕，可能因出錯(cuò)而停止，也可能會(huì)重啟严嗜。一個(gè)value被選定后粱檀，所有的角色可能失敗然后重啟，除非那些失敗后重啟的角色能記錄某些信息漫玄，否則等他們重啟后無法確定被選定的值。（角色有記錄信息的功能）压彭。
2睦优、消息在傳遞過程中可能出現(xiàn)任意時(shí)長的延遲，可能會(huì)重復(fù)壮不，也可能丟失汗盘。但是消息不會(huì)被損壞.（即消息內(nèi)容不會(huì)被篡改--拜占庭將軍問題）。
3.3 推導(dǎo)過程--(在于理解過程)
3.3.1 只有一個(gè)Acceptor
一個(gè)Acceptor接受一個(gè)P询一，那么只有一個(gè)V被選定隐孽。
缺點(diǎn)：如果這個(gè)Acceptor宕機(jī)，那么整個(gè)系統(tǒng)服務(wù)不可用健蕊。
3.3.2 多Acceptor
- 問題：如何在多Proposer和多Acceptor情況下菱阵，選定一個(gè)value?
- 講解步驟分兩階段：約定P1和約定P2.
3.3.2.1 約定P1
P1：一個(gè)Acceptor必須接受一個(gè)它收到的第一個(gè)P.
//我的疑問：接受==被選定？
在此約定在會(huì)產(chǎn)生的問題是：如果每個(gè)Proposer會(huì)產(chǎn)生不同的P,那么多Proposer必定產(chǎn)生多P缩功，發(fā)給多個(gè)Acceptor晴及。根據(jù)約定P1，Acceptor分別接受到P嫡锌，就會(huì)導(dǎo)致不同的V被選定.如下圖所示：
上圖虑稼，P1會(huì)產(chǎn)生的問題:v1、v2势木、v3都沒有被選定蛛倦，因?yàn)樗麄冎挥斜灰粋€(gè)Acceptor接受.
對(duì)于上述問題，我們需要一個(gè)額外的約定:
P1a:一個(gè)提案P被選定啦桌，需要被半數(shù)以上Acceptor接受.
對(duì)于P1a,其實(shí)就意味著【一個(gè)Acceptor必須接受不止一個(gè)提案】.
顯然溯壶，這與P1相矛盾，所以需要重新設(shè)計(jì)提案震蒋。原來的設(shè)計(jì)是:提案P=value茸塞，現(xiàn)在重新設(shè)計(jì):提案P=提案編號(hào)+value,可表示為[M，V].
新問題：多提案被選定查剖，如何保證被選定的提案P具有相同的value?
3.3.2.2 約定P2
P2: 如果提案P[M0,V0]被選定了钾虐，那么所有比M0編號(hào)更高的，且[被選定]的P笋庄，其value值也是V0.
對(duì)于P2中的“被選定”：一個(gè)提案要被選定效扫，首先至少要被一個(gè)Acceptor批準(zhǔn)倔监。因此，可以理解P2為：
P2a:如果提案P[M0,V0]被選定了菌仁，那么所有比M0編號(hào)更高的浩习，且[被Acceptor批準(zhǔn)]的P，其value值也是V0.
只要滿足P2a济丘，就能滿足P2.
多提案被選擇的問題解決了谱秽，但是由于網(wǎng)絡(luò)不穩(wěn)定或者宕機(jī)的原因（不可避免），會(huì)產(chǎn)生新問題：
假設(shè)有5個(gè)Acceptor摹迷。Proposer2提出[M1,V1]的提案疟赊，Acceptor2~5（半數(shù)以上）均接受了該提案，于是對(duì)于Acceptor2~5和Proposer2來講峡碉，它們都認(rèn)為V1被選定近哟。Acceptor1剛剛從宕機(jī)狀態(tài)恢復(fù)過來（之前Acceptor1沒有收到過任何提案），此時(shí)Proposer1向Acceptor1發(fā)送了[M2,V2]的提案（V2≠V1且M2>M1）鲫寄，對(duì)于Acceptor1來講吉执，這是它收到的第一個(gè)提案。根據(jù)P1（一個(gè)Acceptor必須接受它收到的第一個(gè)提案地来。）,Acceptor1必須接受該提案戳玫！同時(shí)Acceptor1認(rèn)為V2被選定。這就出現(xiàn)了兩個(gè)問題：
1靠抑、Acceptor1認(rèn)為V2被選定量九，Acceptor2~5和Proposer2認(rèn)為V1被選定。出現(xiàn)了不一致颂碧。
2荠列、V1被選定了，但是編號(hào)更高的被Acceptor1接受的提案[M2,V2]的value為V2载城，且V2≠V1肌似。這就跟P2a（如果某個(gè)value為v的提案被選定了，那么每個(gè)編號(hào)更高的被Acceptor接受的提案的value必須也是v）矛盾了。
基于以上問題，所有就有了P2b:
P2b:如果P[M0,V0]被選定后廉涕，任何Proposer產(chǎn)生的P，其值也是V0.
- 對(duì)于P2b中的描述固额，那么怎樣保證：“任何Proposer產(chǎn)生的P，其值也是V0.”呢煞聪？
只要滿足P2c即可：
P2c:對(duì)于任意的M斗躏、V,如果[M,V]被提出，那么存在一個(gè)半數(shù)以上的Acceptor組成的結(jié)合S昔脯，滿足以下兩個(gè)條件中的任何一個(gè)：
① S中沒有一個(gè)接受過編號(hào)小于M的提案啄糙。
② S中的Acceptor接受過的最大編號(hào)的提案的value為V笛臣。
推導(dǎo)完畢.
3.4 算法流程
3.4.1 Propose提出提案
總體思路如下：
1、學(xué)習(xí)階段：Prepare請求
Proposer選擇一個(gè)新的提案P[MN,?]向Acceptor集合S（半數(shù)以上）發(fā)送請求隧饼，要求S中的每一個(gè)Acceptor做出如下響應(yīng)：
1.1 如果Acceptor沒有接受過提案沈堡，則向Proposer保證：不再接受編號(hào)小于N的提案。
1.2 如果Acceptor接受過請求燕雁，則向Proposer返回【已經(jīng)接受過的編號(hào)小于N的編號(hào)最大的提案】诞丽。
2、接受階段：Acceptor請求
2.1 如果Proposer收到【半數(shù)以上】Acceptor響應(yīng)拐格，則生成編號(hào)為N率拒，value為V的提案[MN,V],V為所有響應(yīng)中編號(hào)最大的提案的value.
2.2 如果Proposer收到的響應(yīng)中沒有提案，那么value由Proposer自己生成禁荒，生成后將此提案發(fā)給S，并期望Acceptor能接受此提案角撞。
3.4.2 Acceptor接受提案
Acceptor可以忽略任何請求（包括Prepare請求和Accept請求）而不用擔(dān)心破壞算法的安全性呛伴。因此，我們這里要討論的是什么時(shí)候Acceptor可以響應(yīng)一個(gè)請求谒所。
我們對(duì)Acceptor接受提案給出如下約束：
P1b：一個(gè)Acceptor只要尚未響應(yīng)過任何編號(hào)大于N的Prepare請求热康，那么他就可以接受這個(gè)編號(hào)為N的提案。
如果Acceptor收到一個(gè)編號(hào)為N的Prepare請求劣领，在此之前它已經(jīng)響應(yīng)過編號(hào)大于N的Prepare請求姐军。根據(jù)P1b，該Acceptor不可能接受編號(hào)為N的提案尖淘。因此奕锌，該Acceptor可以忽略編號(hào)為N的Prepare請求。當(dāng)然村生，也可以回復(fù)一個(gè)error惊暴，讓Proposer盡早知道自己的提案不會(huì)被接受。
因此趁桃，一個(gè)Acceptor只需記琢苫啊：1. 已接受的編號(hào)最大的提案 2. 已響應(yīng)的請求的最大編號(hào)。
Paxos算法描述
3.4.3 Learner學(xué)習(xí)提案
Learner學(xué)習(xí)（獲任啦 ）被選定的value有如下三種方案:
4. 如何保證Paxos算法的活性
參考：
1油啤、http://www.cnblogs.com/linbingdong/p/6253479.html
2、《從Paxos到ZooKeeper》
