資源描述：
《paxos made simple》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、PaxosMadeSimpleAuthor:LeslieLamportPresenter:ZhouFanfuJune20,2010OutlineBackgroundTheProblemAlgorithmBackgroundPaxos算法是LesileLamport提出的一種基于消息傳遞的一致性算法。這種算法被認(rèn)為是類似算法中最有效地。微軟公司為簡化的Paxos算法申請了專利。谷歌公司在其分布式鎖服務(wù)(Chubbylock)中應(yīng)用了Paxos算法。Chubbylock應(yīng)用于Bigtable。“ThePart-TimeParliament”Lamport于1998，這是該算法第一次公開發(fā)表?！?/p>
2、PaxosMadeSimple”2001,Lamport覺得同行無法接受他的幽默感，于是用容易接受的方法重新描述了一番。TheProblem&HypothesisPaxos算法解決的問題是一個(gè)分布式系統(tǒng)如何就某個(gè)value（決議）達(dá)成一致。一個(gè)典型的場景是，在一個(gè)分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個(gè)節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個(gè)一致的狀態(tài)。為保證每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個(gè)“一致性算法”，以保證每個(gè)節(jié)點(diǎn)看到的指令一致。TheProblem&Hypothesis(2)為描述Paxos算法，Lamport虛擬了一個(gè)叫做Paxos的希臘城
3、邦，這個(gè)島按照議會民主制的政治模式制訂法律，但是沒有人愿意將自己的全部時(shí)間和精力放在這種事情上。所以無論是議員，議長或者傳遞紙條的服務(wù)員都不能承諾別人需要時(shí)一定會出現(xiàn)，也無法承諾批準(zhǔn)決議或者傳遞消息的時(shí)間。但是這里假設(shè)沒有拜占庭將軍問題；只要等待足夠的時(shí)間，消息就會被傳到。另外，Paxos島上的議員是不會反對其他議員提出的決議的。TheProblem&Hypothesis(3)Lamport虛擬了一個(gè)叫做Paxos的希臘城邦，這個(gè)島按照議會民主制的政治模式制訂法律，但是沒有人愿意將自己的全部時(shí)間和精力放在這種事情上。所以無論是議員，議長或者傳遞紙條的服務(wù)員都不能承諾別人需要時(shí)一定會出現(xiàn)，也
4、無法承諾批準(zhǔn)決議或者傳遞消息的時(shí)間。但是這里假設(shè)沒有拜占庭將軍問題；只要等待足夠的時(shí)間，消息就會被傳到。另外，Paxos島上的議員是不會反對其他議員提出的決議的。對應(yīng)于分布式系統(tǒng)，議員對應(yīng)于各個(gè)節(jié)點(diǎn)，制定的法律對應(yīng)于系統(tǒng)的狀態(tài)。Algorithm(1)首先將議員的角色分為proposers，acceptors，和learners（允許身兼數(shù)職）。proposers提出決議，acceptors批準(zhǔn)決議，learners(學(xué)習(xí))決議。一致性滿足的必備條件：決議（value）只有在被proposers提出后才能批準(zhǔn)（未經(jīng)批準(zhǔn)的決議稱為提案（proposal））；在一次Paxos算法的執(zhí)行實(shí)例中，
5、只批準(zhǔn)一個(gè)Value；learners只能獲得被批準(zhǔn)（chosen）的Value。另外還需要保證Progress。Algorithm(2)批準(zhǔn)value的過程中，首先proposers將value發(fā)送給acceptors，之后acceptors對value進(jìn)行批準(zhǔn)。為了滿足只批準(zhǔn)一個(gè)value的約束，要求經(jīng)多數(shù)派（majority）批準(zhǔn)的value成為正式的決議（稱為通過決議）。這是因?yàn)闊o論是按照人數(shù)還是按照權(quán)重劃分，兩組多數(shù)派至少有一個(gè)公共的acceptor，如果每個(gè)acceptor只能接受一個(gè)value，約束2就能保證。Algorithm(3)P1：一個(gè)acceptor只能批準(zhǔn)它接收到
6、的第一個(gè)value。P2：一旦一個(gè)value被通過，那么之后通過的value必須和這個(gè)value一樣。P2a：一旦一個(gè)valuev被通過，那么之后任何acceptor再批準(zhǔn)的value必須是v。P2b：一旦一個(gè)valuev被通過，那么以后proposer提出的新提案必須具有valuev。P2c：如果一個(gè)編號為n的提案具有valuev，那么存在一個(gè)多數(shù)派，要么他們中沒有人批準(zhǔn)過編號小于n的任何提案，要么他們進(jìn)行的最近一次批準(zhǔn)具有valuev。Algorithm(4) Chooseavalue通過一個(gè)決議分為兩個(gè)階段：prepare階段：proposer選擇一個(gè)提案編號n并將prepare請求
7、發(fā)送給acceptors中的一個(gè)多數(shù)派；acceptor收到prepare消息后，如果提案的編號大于它已經(jīng)回復(fù)的所有prepare消息，則acceptor將自己上次的批準(zhǔn)回復(fù)給proposer，并承諾不再批準(zhǔn)小于n的提案；批準(zhǔn)階段：當(dāng)一個(gè)proposor收到了多數(shù)acceptors對prepare的回復(fù)后，就進(jìn)入批準(zhǔn)階段。它要向回復(fù)prepare請求的acceptors發(fā)送accept請求，包括編號n和根據(jù)P2c決定的v
