Lamport’s Logical Clocks 和 Vector Clock

栏目: 数据库 · 发布时间: 6年前

内容简介:编:关于早在在1978年,逻辑时钟本质上定义了一种

编:关于 Vector Clock 之前看过几眼,但是多数讲解地都不是很清楚,一直没太弄清楚。直到有一天,又看了看,终于弄明白了。

早在在1978年, Leslie Lamport 就提出逻辑时钟的概念。在分布式环境中,通过一系列规则来定义逻辑时钟的变化。从而能通过逻辑时钟来对分布式系统中的事件的先后顺序进行判断。

逻辑时钟本质上定义了一种 happen before 关系,记作 ->a->b 意味着所有的进程都“认可”事件 a 发生在事件 b 之前。 happen before 关系满足传递性:即 (a->b && b->c) 可以推导出 (a->c)

Lamport’s Logical Clocks

lamport逻辑时钟算法:

  • 每个事件对应一个Lamport时间戳,初始值为0
  • 如果事件在节点内发生,时间戳加1
  • 如果事件属于发送事件,时间戳加1并在消息中带上该时间戳
  • 如果事件属于接收事件,时间戳 = Max(本地时间戳,消息中的时间戳) + 1

三个机器上各自跑着一个进程,分别为

,由于不同的机器上的物理时钟、CPU负载、或者CPU频率不一样,所以不同的机器上的时钟速率可能是不同的,例如当 所在的机器tick了6次, 所在的机器tick了8次,就是 异步网络

中指的漂移时钟不同。

Lamport’s Logical Clocks 和 Vector Clock

图中,

发送了消息 上附带了发送 时的时钟6,随后 收到了 ,根据 接收到 时的时钟,认为传输消息花了16-6=10个tick,随后, 发送消息 附带的发送时钟是60。由于 的时钟走的比 的慢,所以接收到 时,本机的时钟56比发送时钟60小,这是不合理的,需要调整时钟,如图中,将 的56调整为61,即

的发送时钟加1。

当不同事件在不同进程间并行时:

Lamport’s Logical Clocks 和 Vector Clock

我们以B4事件为中心,来分析:

happens before

lamport逻辑时钟规定:按事件的时间戳大小为时间排序,任何两个时间不可能在同一时间发生,任何消息收到的时间都应该比发送的时间晚。

Vector Clock

Vector Clock 是在Lamport时间戳基础上演进的另一种逻辑时钟方法,它通过vector结构不但记录本节点的Lamport时间戳,同时也记录了其他节点的Lamport时间戳。 Vector Clock 的原理与Lamport时间戳类似,使用原理如下:

  • 本地 Vector Clock 中每一个槽 记录系统中对应进程 的逻辑时间戳;
  • 初始化 Vector Clock 中每一个槽为0;
  • 每一次处理内完内部事件,将本地的 Vector Clock 中自己槽中的逻辑时间戳+1;
  • 每一次发送一个消息的时候,需要将本地的 Vector Clock 和消息一起发送;
  • 每一次接收到一个消息的时候,需要将本地的 Vector Clock 中自己槽中的逻辑时间戳+1,同时更新本地的 Vector Clock 中每一个槽中的逻辑时间戳。

Vector Clock 规定:

  • 对应的 Vector Clock 中,每一个进程 的逻辑时间戳 都满足 时,我们称 happen before
  • 否则,即 Vector Clock 中,存在 ,使得 ,我们称 是并发关系(或者没有因果关系);

因此在前面讲到的那个多进程并行时间的例子中:

Lamport’s Logical Clocks 和 Vector Clock

B4事件的 Vector Clock[A:2,B:4,C:1] ,根据 Vector Clock 的规定,我们可以很好的判断出灰色区域 happens before B4事件,B4时间 happens before 红色区域。白色区域与B4事件没有因果关系。

参考


以上所述就是小编给大家介绍的《Lamport’s Logical Clocks 和 Vector Clock》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

CSS与DHTML精髓(第2版)

CSS与DHTML精髓(第2版)

Dan Livingston / 清华大学 / 2003-7-1 / 34.00

CSS与DHTML精髓(第二版),ISBN:9787302066941,作者:战晓苏译;战晓苏译一起来看看 《CSS与DHTML精髓(第2版)》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

URL 编码/解码
URL 编码/解码

URL 编码/解码

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具