分布式一致性Paxos算法学习笔记（一）：paxos大杂烩

声明：Paxos算法学习笔记系列摘自：http://www.cnblogs.com/ychellboy

取名

    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的复制也有使用了paxos算法。在本系列的后续文章中将重点介绍对其中一些实现的理解，以及给libpaxos做跨windows平台移植遇到的问题。

 

 

关于本学习笔记

    Paxos算法学习笔记系列文章记录了本人这半年多对paxos学习和应用的一些理解，因水平有限可能有很多理解上的错误，欢迎大家批评！在此要感谢Marco的帮助，感谢川大智胜胡术老师及其带领的空管部网络组的支持。

 

后续：“分布式一致性Paxos算法学习笔记（二）：算法详解”

Reference

[1]维基百科，Paxos算法：http://zh.wikipedia.org/wiki/Paxos算法#.E9.97.AE.E9.A2.98.E5.92.8C.E5.81.87.E8.AE.BE

[2]Lamport, The part-time parliament, ACM Transactions on Computer Systems 16(2):133-169, 1998

[3]Lamport, Paxos made simple, SIGACT News 32(4):18-25, 2001.