Paxos Made Simple.ppt

《Paxos Made Simple.ppt》由会员分享，可在线阅读，更多相关《Paxos Made Simple.ppt（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Paxos Made SimpleAuthor: Leslie LamportPresenter: Zhou FanfuJune 20, 2010Outline1.Background2.The Problem3.Algorithm BackgroundPaxos 算法是Lesile Lamport 提出的一种基于消息传递的一致性算法。这种算法被认为是类似算法中最有效地。微软公司为简化的Paxos算法申请了专利。谷歌公司在其分布式锁服务(Chubby lock)中应用了Paxos算法。Chubby lock应用于Bigtable。“The Part-Time Parliament” Lampo

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

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

4、种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题；只要等待足够的时间，消息就会被传到。另外，Paxos 岛上的议员是不会反对其他议员提出的决议的。对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。Algorithm(1)首先将议员的角色分为 proposers，acceptors，和 learners（允许身兼数职）。proposers 提出决议，acceptors 批准决议，learners(学习)决议。一致性满足的必备条件：-决议（value）只有在被 proposers

5、提出后才能批准（未经批准的决议称为提案（proposal）； -在一次 Paxos 算法的执行实例中，只批准一个 Value； -learners 只能获得被批准（chosen）的 Value。 另外还需要保证 Progress。Algorithm(2)批准 value 的过程中，首先 proposers 将 value 发送给 acceptors，之后 acceptors 对 value 进行批准。为了满足只批准一个 value 的约束，要求经多数派（majority）批准的 value 成为正式的决议（称为通过决议）。这是因为无论是按照人数还是按照权重划分，两组多数派至少有一个公共的 ac

6、ceptor，如果每个 acceptor 只能接受一个 value，约束2就能保证。Algorithm(3)P1：一个 acceptor 只能批准它接收到的第一个 value。P2：一旦一个 value 被通过，那么之后通过的 value 必须和这个 value 一样。P2a：一旦一个 value v 被通过，那么之后任何 acceptor 再批准的 value 必须是 v。 P2b：一旦一个 value v 被通过，那么以后 proposer 提出的新提案必须具有 value v。P2c：如果一个编号为 n 的提案具有 value v，那么存在一个多数派，要么他们中没有人批准过编号小于 n

7、的任何提案，要么他们进行的最近一次批准具有 value v。 Algorithm(4) Choose a value通过一个决议分为两个阶段：prepare 阶段： proposer 选择一个提案编号 n 并将 prepare 请求发送给 acceptors 中的一个多数派； acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 acceptor 将自己上次的批准回复给 proposer，并承诺不再批准小于 n 的提案； 批准阶段： 当一个 proposor 收到了多数 acceptors 对 prepare 的回复后，就进入批准阶段。它

8、要向回复 prepare 请求的 acceptors 发送 accept 请求，包括编号 n 和根据 P2c 决定的 value（如果根据 P2c 没有决定 value，那么它可以自由决定 value）。 在不违背自己向其他 proposer 的承诺的前提下，acceptor 收到 accept 请求后即批准这个请求。 Algorithm(5) Learning a Chosen Value一个显而易见的方法是当 acceptors 批准一个 value 时，将这个消息发送给所有 learner。由于假设没有 Byzantine failures，learners 可以通过别的 learner

9、s 获取已经通过的决议。因此 acceptors 只需将批准的消息发送给指定的某一个 learner，其他 learners 向它询问已经通过的决议。这个方法降低了消息量，但是指定 learner 失效将引起系统失效。因此 acceptors 需要将 accept 消息发送给 learners 的一个子集，然后由这些 learners 去通知所有 learners。但是由于消息传递的不确定性，可能会没有任何 learner 获得了决议批准的消息。当 learners 需要了解决议通过情况时，可以让一个 proposer 重新进行一次提案。注意一个 learner 可能兼任 proposer。A

10、lgorithm(6) Progress根据上述过程当一个 proposer 发现存在编号更大的提案时将终止提案。这意味这提出一个编号更大的提案会终止之前的提案过程。如果两个 proposer 在这种情况下都转而提出一个编号更大的提案，就可能陷入活锁，违背了 Progress 的要求。这种情况下的解决方案是选举出一个 president，仅允许 president 提出提案。但是由于消息传递的不确定性，可能有多个 proposer 自认为自己已经成为 president。Lamport 在”The Part-Time Parliament” 一文中描述并解决了这个问题。Thank you!Any Questions?