paxos算法学习.docx

取名?? ?Paxos（Greek: Παξο?,?pronounced?Paksi in English?）又名Paxi是希腊西南部一个风景如画的小岛。而Paxos算法则是现在很火的分布式一致性算法，为何以一个希腊小岛名字算法？Lamport这样解释道：I thought, and still think, that Paxos is an important algorithm.? Inspired by my success at popularizing the consensus problem by describing it with Byzantine generals, I decided to cast the algorithm in terms of a parliament on an ancient Greek island.? Leo Guibas suggested the name?Paxos?for the island.为描述 Paxos 算法，Lamport 虚拟了一个叫做 Paxos 的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员 都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos 岛上的议员是不会反对其他议员提出的决议的[1]。??背景?? ?Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是?LaTeX?中的La，此人现在在微软研究院） 于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，使Lamport在八年后重新发表到TOCS上[2]。即 便如此paxos算法还是没有得到重视，2001年Lamport用可读性比较强的叙述性语言给出算法描述[3]。可见Lamport对paxos算法情 有独钟。近几年paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。06年google的三篇论文初现“云”的端倪，其中的chubby锁 服务使用paxos作为chubby cell中的一致性算法，paxos的人气从此一路狂飙。??Paxos是什么？?? ?Paxos 算法是分布式一致性算法用来解决一个分布式系统如何就某个值(决议)达成一致的问题。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态 一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态[1]。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个一致性 算法以保证每个节点看到的指令一致。这里想提一下一些中文的paxos算法理解的文章中用分布式系统竞争锁的场景作例子介绍paxos算法的过程，就我 个人感觉不是很合适，因为paxos算法是一个较高效的一致性算法，和传统的分布式锁算法还是不太一样的，比如RA算法，它和单机上的加锁解锁有一个最大 的共同点就是有很明显的“请求--等待”的过程，而paxos算法每一个实例之间相对独立，选举过程可以平行执行，后发生的实例是可以再先发生的实例之前 表决的，并没有明显的“请求--等待”的感觉。在具体的应用时，分布式锁算法更多的是“互斥”的感觉，一致性算法更多的是“同步”的感觉。??Paxos适合什么场合？?? ?参考转载的《Paxos算法在大型系统中常见的应用场景》，在chubby中paxos用于保持chubby cell内部所有主机操作序列的一致性，同时也用于选举出chubby cell中的master或者说是leader。??Paxos的实现？?? ?chubby中有paxos的具体实现可惜看不到代码，表现形式也不确定，可能是以库的形式提供也可能散布在程序的很多地方。现在手里能拿到的一个是 sourceforge上的开源库libpaxos，作者是一位意大利的帅小伙Marco。和Marco交流后发现他对paxos的理解确实挺深的。虽然 libpaxos现在还没得到商用，但感觉还是挺有前途的；另一个实现是在北大天网实验室的类chubby实现---debby，是使用ICE现实的，看 过之后总觉得有些不太通顺的地方，似乎代码的实现并没有严格遵循paxos算法（很可能是本人水平不足，没看出其中的玄机）；还有一个是Diskless Paxos的实现，不使用disk保存状态怎么实现各个角色的“可重启”呢？还没时间研究，应该还是挺有意思的；除了这些，在google code上有paxos的java实现，BerkeleyDB