分布式系统：向量时钟

栏目: 后端 · 发布时间: 6年前

内容简介：在上一篇文章我们可以发现在进程 P2 中，Tr(m1) < Ts(m3)，说明 m3 是在 m1 被接收之后发送的，也就是说 m3 的发送跟 m1 的接收有关系。难道通过 Lamport 时间戳就能区分事件的因果的关系了吗？答案是 No，我们仔细看可以发现，虽然 Tr(m1) < Ts(m2)，但实际上 m2 的发送跟 m1 并没有关系。综上所述，我们可以发现 Lamport 逻辑时钟算法中每个进程只拥有自己的本地时间，没有其他进程的时间，导致无法描述事件的因果关系。如果每个进程都能够知道其他所有进程的时间

在上一篇文章分布式系统：Lamport 逻辑时钟中我们知道Lamport 逻辑时钟帮助我们得到了分布式系统中的事件全序关系，但是对于同时发生的关系却不能很好的描述，导致无法描述事件的因果关系。向量时钟是在 Lamport 时间戳基础上演进的另一种逻辑时钟方法，它通过向量结构不但记录本节点的 Lamport 时间戳，同时也记录了其他节点的 Lamport 时间戳，因此能够很好描述同时发生关系以及事件的因果关系。

注意：

本文中的因果关系指的是时序关系，即时间的前后，并不是逻辑上的原因和结果
本文中提及的时间戳如无特别说明，都指的是Lamport 逻辑时钟的时间戳，不是物理时钟的时间戳

为什么需要向量时钟

首先我们来回顾一下 Lamport 逻辑时钟算法，它提供了一种判断分布式系统中事件全序关系的方法：如果 a -> b，那么 C(a) < C(b)，但是 C(a) < C(b) 并不能说明 a -> b。也就是说** C(a) < C(b) 是 a -> b 的必要不充分条件，我们不能通过 Lamport 时间戳对事件 a、b 的因果关系进行判断。** 下面我们举一个例子来说明。

假设有三个进程在发消息，Ts(mi)表示消息mi的发送时间戳，Tr(mi)表示消息mi的接受时间戳，显然 Ts(mi) < Tr(mi)，但是这个能说明什么呢？

我们可以发现在进程 P2 中，Tr(m1) < Ts(m3)，说明 m3 是在 m1 被接收之后发送的，也就是说 m3 的发送跟 m1 的接收有关系。难道通过 Lamport 时间戳就能区分事件的因果的关系了吗？答案是 No，我们仔细看可以发现，虽然 Tr(m1) < Ts(m2)，但实际上 m2 的发送跟 m1 并没有关系。

综上所述，我们可以发现 Lamport 逻辑时钟算法中每个进程只拥有自己的本地时间，没有其他进程的时间，导致无法描述事件的因果关系。如果每个进程都能够知道其他所有进程的时间，是否就能够得到事件的因果关系了呢？为此，有人提出了向量时钟算法，在 Lamport 逻辑时钟的基础上进行了改良，提出了一种在分布式系统中描述事件因果关系的算法。

什么是向量时钟

如何实现向量时钟

向量时钟应用示例

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

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

码农书籍

Beginning XML with DOM and Ajax

Sas Jacobs / Apress / 2006-06-05 / USD 39.99

Don't waste time on 1,000-page tomes full of syntax; this book is all you need to get ahead in XML development. Renowned web developer Sas Jacobs presents an essential guide to XML. Beginning XML with......一起来看看《Beginning XML with DOM and Ajax》这本书的介绍吧!

码农工具