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