使用逻辑时钟重述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协议

Paxos是一个分布式选举协议。我们将参与通信的主体分为两个角色:proposer和acceptor。proposer和acceptor可以位于同一台机器上,但是它们必须有各自独立的localClock。

Paxos协议分为两个阶段。

1. 设置时钟:proposer令localClock=globalClock.incrementAndGet()。

2. prepare:proposer向所有acceptor发送一个prepare消息。接收方应返回它最近一次accept的value,以及accept的时间,若在它还没有accept过value,那么就返回空。proposer只有在收到过半数的response之后,才可进入下一个阶段。一旦收到reject消息,那么就从头来。

3. 构造Proposal:proposer从prepare阶段收到的所有values中选取时间戳最新的一个。如果没有,那么它自己提议一个value。

4. 发送Proposal:proposer把value发送给其它所有机器,消息的时间戳取自localClock。接收方只要检查消息时间戳合法,那么就接受此value,把这个value和时间戳写入到硬盘上,然后答复OK,否则拒绝接受。proposer若收到任何的reject答复,则回到step1。否则,在收到过半数的OK后,此Proposal被通过。

globalClock的实现

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

int globalClock::incrementAndGet(){
   return (MAX_SERVER_ID+1)*++localCounter+serverID;
}
我来评几句
登录后评论

已发表评论数()

相关站点

热门文章