Paxos是一个分布式选举协议,被广泛用在很多分布式系统中,比如Google的Chubby,MegaStore,Linux的Ceph。它的目的是为了让一群机器通过选举的方式达成一个一致性的决议。比如现在有5台MySQL服务器,它们要选举一个Master出来(无人工干预),所有的数据修改请求都发给这个Master,其它的做为Slave,以备在Master死掉后自动顶上去。
Paxos协议将参与通信的主体分为两个角色:proposer和acceptor。它的基本框架是:
- 一个proposer提出一个提案,然后把这个提案发给所有的acceptor。
- acceptor可以选择接受或者拒绝这个提案。
- 一个提案如果被过半数的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服务,每台机器存储一个本地的计数器就可以了。
int globalClock::incrementAndGet(){ return (MAX_SERVER_ID+1)*++localCounter+serverID; }
由 udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!