Paxos是一个分布式选举协议，被广泛用在很多分布式系统中，比如Google的Chubby，MegaStore，Linux的Ceph。它的目的是为了让一群机器通过选举的方式达成一个一致性的决议。比如现在有5台MySQL服务器，它们要选举一个Master出来（无人工干预），所有的数据修改请求都发给这个Master，其它的做为Slave，以备在Master死掉后自动顶上去。

Paxos协议将参与通信的主体分为两个角色：proposer和acceptor。分别各有多个。分布式选举协议的基本框架是：

1. 一个proposer提出一个提案，然后把这个提案发给所有的acceptor。

2. acceptor可以选择接受或者拒绝这个提案。

3. 一个提案如果被过半数的acceptor接受，那么此提案被选中（chosen）。

一个系统中可以同时有多个proposer提出多个提案，但是最终只能有一个被选中。并且应该至少有一个被选中。

选举过程中机器可能crash掉，或者网络中断，机器一会儿死了一会儿活了。但是无论如何，只要死掉的机器数不过半，选举就应正常进行下去。

Paxos协议是一个被公认的晦涩难懂的协议。但是今天突然发现，如果按照逻辑时钟的角度去阐述它，它就变得简单清晰了许多。下面介绍如何利用带逻辑时钟的RPC协议来实现Paxos。

基于逻辑时钟的RPC协议

为了让这套系统能正确运行，我们需要一个精确的时钟。由于操作系统的物理时钟经常是有偏差的，所以我们决定采用一个逻辑时钟。时钟的目的是给系统中发生的每一个事件编排一个序号。

逻辑时钟可以利用全局计数器来实现。我们可以找一台机器提供一个全局的计数服务。它只支持一个方法：incrementAndGet()。这个方法的作用是将计数器的值加一，并且返回增加后的值。我们将这个计数器称为globalClock。globalClock的初始值为0。

然后，系统中的每个其它机器，都有一个自己的localClock,它的初始值来自globalClock。

假设机器和机器之间通过request-response这样的模式通讯。每条网络消息的类型要么是reqeust，要么是response。response又分为两种：OK和Rejected。

我们规定无论什么类型的网络消息，都必须带有一个时间戳，时间戳取自这台机器的localClock。我们规定消息的接收方必须执行以下行为：

if(message.timestamp<localClock && message.type==“request”)   reject(message);else{  localClock=message.timestamp;   process(message);}

简而言之就是：我们不处理过时的请求。并且利用网络间传输的消息作为时钟同步机制。一旦收到过时的请求，就返回Rejected类型的答复。

另外，我们要求时钟不能倒流。我们必须容忍机器突然crash。在机器重新起来之后，要么localClock从globalClock取一个新值，要么localClock每次更新的时候都必须写入到本地硬盘上，重启之后从那再读进来。我们偏向于第二种方案，因为我后面将会讲怎么去掉globalClock这个服务器。

Paxos协议

proposer和acceptor可以位于同一台机器上，但是它们必须有各自独立的localClock。

我们允许一个acceptor在一轮选举中接受多个提案，但是最终只有票数最高的那个会被选中(chosen)。

Paxos的Request信息分为两种：prepare和accept。

1. 设置时钟：proposer令localClock=globalClock.incrementAndGet()。
2. 发送prepare消息:proposer向所有acceptor发送一个prepare消息。接收方应返回它最近一次接受的提案，以及接受的时间，若在它还没有接受过提案，那么就返回空。proposer只有在收到过半数的response之后，才可进入下一个阶段。一旦收到reject消息，那么goto step1.
3. 构造Proposal: proposer从prepare阶段收到的所有提案中选取时间戳最新的一个。如果没有，那么它自己创建一个提案。意即：如果有人提名了，它就只能跟票。否则，它可以提名新的候选人。
4. 发送accept消息，请求接受此Proposal: proposer把提案发送给所有的acceptor，消息的时间戳取自localClock。acceptor只要检查消息时间戳合法，那么就接受此提案，把这个提案和当前时间戳写入到硬盘上，然后答复OK，否则拒绝接受。proposer若收到任何的reject答复，则回到step1。否则，在收到过半数的OK后，此提案被通过。注意：只有这个proposer知道此提案被通过了，其它的proposer和acceptor都不知道。

globalClock的实现

如果系统中每台机器都有一个唯一的整数Id，那么我们就不需要一台专门的机器来提供clock服务，每台机器存储一个本地的计数器就可以了。

每台机器的clock由(roundNumber,serverid)这两个整型字段组成。roundNumber初始值为1。不同的服务器之间roundNumber可以重复。不再有全局的clock服务。

clock支持以下三种操作：

自增操作：roundNumber++, serverid=self.serverid
比较操作：先比较round number,再比较serverid。
赋值操作：对roundNumber和serverid分别赋值。

因为serverId是唯一的，所以inc操作产生的时间戳肯定是唯一的。因为先比较round number，后比较serverid，所以inc可以保证每次总是产生一个更大的时间戳。赋值操作可能会导致时钟的serverid和自己真实的serverid不相符，但是这没有关系，下次执行自增操作的时候会纠正过来。

Paxos协议的改进

原始的Paxos协议几乎不可在实际环境中使用。很多人对它做了很多改进，可惜改进后是否正确往往是不知道的。因为原始的Paxos协议的证明就已经很复杂，如同天书。后来工程师所做的边边角角的改进，综合起来之后，更是让证明变得困难很多很多倍。下面简述一些比较典型的。

建议继续学习：

1. 分布式缓存系统 Memcached 入门    (阅读：14787)
2. Zookeeper工作原理    (阅读：10511)
3. GFS, HDFS, Blob File System架构对比    (阅读：9442)
4. Zookeeper研究和应用    (阅读：8575)
5. 分布式日志系统scribe使用手记    (阅读：8095)
6. 一致性哈希算法及其在分布式系统中的应用    (阅读：7994)
7. 分布式哈希和一致性哈希    (阅读：7729)
8. HBase技术介绍    (阅读：6822)
9. 分布式系统的事务处理    (阅读：6097)
10. Memcache分布式部署方案    (阅读：5504)