paxos made simple

《paxos made simple》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、PaxosMadeSimpleAuthor:LeslieLamportPresenter:ZhouFanfuJune20,2010OutlineBackgroundTheProblemAlgorithmBackgroundPaxos算法是LesileLamport提出的一种基于消息传递的一致性算法。这种算法被认为是类似算法中最有效地。微软公司为简化的Paxos算法申请了专利。谷歌公司在其分布式锁服务(Chubbylock)中应用了Paxos算法。Chubbylock应用于Bigtable。“ThePart-TimeParliament”Lamport于1998，这是该算法第一次公开发表。“

2、PaxosMadeSimple”2001,Lamport觉得同行无法接受他的幽默感，于是用容易接受的方法重新描述了一番。TheProblem&HypothesisPaxos算法解决的问题是一个分布式系统如何就某个value（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”，以保证每个节点看到的指令一致。TheProblem&Hypothesis(2)为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城

3、邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。TheProblem&Hypothesis(3)Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也

4、无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。Algorithm(1)首先将议员的角色分为proposers，acceptors，和learners（允许身兼数职）。proposers提出决议，acceptors批准决议，learners(学习)决议。一致性满足的必备条件：决议（value）只有在被proposers提出后才能批准（未经批准的决议称为提案（proposal））；在一次Paxos算法的执行实例中，

5、只批准一个Value；learners只能获得被批准（chosen）的Value。另外还需要保证Progress。Algorithm(2)批准value的过程中，首先proposers将value发送给acceptors，之后acceptors对value进行批准。为了满足只批准一个value的约束，要求经多数派（majority）批准的value成为正式的决议（称为通过决议）。这是因为无论是按照人数还是按照权重划分，两组多数派至少有一个公共的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，那么存在一个多数派，要么他们中没有人批准过编号小于n的任何提案，要么他们进行的最近一次批准具有valuev。Algorithm(4)Chooseavalue通过一个决议分为两个阶段：prepare阶段：proposer选择一个提案编号n并将prepare请求

7、发送给acceptors中的一个多数派；acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息，则acceptor将自己上次的批准回复给proposer，并承诺不再批准小于n的提案；批准阶段：当一个proposor收到了多数acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和根据P2c决定的v