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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Paxos Made Simple
限制150内