使用逻辑时钟重述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; } 正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
