使用逻辑时钟重述paxos协议

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

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

  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协议的证明就已经很复杂,如同天书。后来工程师所做的边边角角的改进,综合起来之后,更是让证明变得困难很多很多倍。下面简述一些比较典型的。

(待续)

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥