逻辑时间和Lamport时钟(第1部分)

在本系列的整个过程中,我们看到了许多实例,说明事情可能比看起来复杂得多。我们看到了失败,然后看到了复制。最近,我们发现甚至时间的概念也比我们原本想的要复杂。

但是,当你认为自己知道的事情比以往更令人费解时,有时答案就是保持简单。换句话说,我们可以通过剥离容易混淆的部分并将其修整到最重要的部分来简化问题。实际上,这种方法正是70年代末一位计算机科学家(就像我们一样)试图弄清楚如何在分布式系统中理解时间的方式。

时钟的前两篇文章以及分布式系统中事件的顺序都已经建立,我们终于可以发现这个话题:逻辑时间和Lamport时钟有很多要讨论的内容,因此我们将在两篇文章中进行介绍。让我们直接进入第一部分

因果关系和“之前发生的事情”

逻辑时钟的故事始于1978年,当时在ACM通讯杂志上发表了一篇文章,该文章将载入史册。马萨诸塞州计算机协会的计算机科学家莱斯利·兰普特(Leslie Lamport)撰写了有关分布式系统中订购事件的研究。这篇题为“分布式系统中的时间,时钟和事件的排序”的论文将继续成为计算机科学中被引用最多的论文之一,并且还将获得“分布式计算原理性论文奖” 20年之后。

Lamport的因果排序论文于1978年发表

在论文中,Lamport概述了我们如何以人类的方式思考时间,以及为什么在涉及分布式系统时我们需要改变我们的范式,以及部分排序的思想。他解释说:“在分布式系统中,有时不可能说两个事件之一先发生”。

为什么我们关心订购事件?这样我们就可以追踪因果关系

正如兰莫特(Lamport)在他的论文中所引用的,我们之所以在意时间,是因为我们可以弄清事情发生的顺序。虽然在分布式系统中这样做确实比较困难(有时甚至是不可能),但我们想知道系统中某些事件的顺序的原因都源于相同的愿望:我们关心事件的排序,因此我们可以确定如何这些事件是关联的。在任何系统中处理事件时,我们实际上要对其进行排序的原因是为了使我们能够看到系统中的事件链。特别是在分布式系统中,这意味着我们经常尝试确定一个节点上的事件是否影响或导致另一节点上的事件。

但是,正如我们在对分布式系统的研究中看到的那样,这项任务并非易事。当分布式系统时,没有全局时钟,这意味着我们不能依赖任何中央时间源。这也意味着我们系统中的事件未完全排序,这意味着我们无法确定系统中每个事件的确切发生时间。 Lamport的论文承认了所有这些限制,并同情这个问题的实际棘手性

Lamport的解决方案是改变我们的思维方式。他提出了一个新颖的想法:实际上,我们不需要在开始整体订购的情况下考虑因果关系。相反,他说,我们可以从事件的部分排序开始,然后再处理找出哪些事件在其他事件之前发生。一旦确定了部分排序,就可以将其转变为一致的全部排序。

Lamport的逻辑时钟使我们能够从发生的“时间”转变为“发生的时间”。

那么我们该怎么做呢?好吧,首先,我们需要从思考事件何时发生转变为事件发生之前的思考。

从“何时”转换为“之前”

一件事比另一件事先发生的想法是兰莫特论文的中心。他使用→速记符号表示发生在关系之前的事件,或者一个事件发生在另一事件之前的事实。例如,如果我们知道一个事件a在另一个事件b之前发生,那么我们可以说a→b或a在b之前发生。

关系也可以过渡应用之前发生的事情。换句话说,我们可以创建一个事件链,其中一个事件先于另一个事件发生。如果我们说a→b和b→c,那么通过使用传递性,我们可以说a→c或a发生在c之前。正如我们可以想象的,我们可以很容易地将一系列事件串在一起,其中一个事件发生在另一个事件之前,另一个事件发生在另一个事件之前,依此类推。

了解“之前发生”的符号。

但是请稍等……我们一直在谈论系统中的不同事件,但是我们还没有真正弄清一个事件可能是什么事实证明,分布式系统中的事件可以采用不同的形式。众所周知,分布式系统中可以有许多不同的节点。每个节点都有自己的本地系统时钟,并且能够处理自己的任务。但是,节点之间也可以相互通信,来回发送消息。

事件涵盖了系统中节点之间以及节点之间可能发生的所有不同事件。事件可能是在单个进程或节点上发生的事件。事件还包括任何发送事件,其中节点将消息发送到另一个节点或进程。相反,当节点从系统其他位置接收到传入消息时,我们还必须考虑接收事件。

在上面的示例中,我们可以看到所有这三个事件的示例。我们有两个进程,P和Q。有一个事件Q3,它发生在进程Q上,与发送或接收任何消息都不相关。这是我们的基本事件,表明进程Q的节点上发生了某些事情。但是,我们还有一些发送事件:P1,Q1,Q4。这些都是表明我们正在将消息从节点发送到系统中其他位置的事件。另一方面,P2,P3和Q2分别是接收事件,表明我们已经从系统中的另一个节点接收到一些消息。

现在我们了解了系统中的事件可能是什么,我们可以回到关系发生之前的事件。当我们说事件a→b时,我们断言该事件a在b之前发生,因为a在b之前发生。我们可以说这两个事件是有因果关系的,其中事件的顺序取决于一个事件导致另一个事件的发生。

跨两个过程的因果事件和并发事件。

有一些因果排序规则对我们来说很重要。为了对a→b进行因果排序,必须满足以下三种情况之一:

  1. 事件a和b必须在同一进程上发生,并且a必须在b在进程上发生之前发生。
  2. 只要a是与b对应的发送事件(必须是其接收事件),这些事件就可以在不同的进程中发生。
  3. 这些事件与系统中的另一个事件可传递地链接在一起,但是在b之前仍然发生。例如,如果a发生在c之前,而c发生在b之前,那么我们知道a→b。

随着消息从一个过程到另一个过程在时间和空间上传播,我们可以开始构建因果事件链(也称为因果路径),并查看跨过程的不同事件如何彼此关联。例如,在进程P和Q中,Q1_→_ P3(通过事件P2),以及P1→Q4(通过事件Q2和Q3)。

最后,值得一提的是,如果两个事件a和b没有先后发生,那么我们可以说a≠> b和b≠> a,并且这两个事件是并发的。我们将在本文的第二部分中更深入地讨论这一点,但就目前而言,我们应该注意,并发事件没有从一个事件到另一个事件的因果关系。

逻辑时钟到达舞台

除了“之前发生”的概念外,兰莫特在论文中引入的另一个核心概念是逻辑时钟。众所周知,分布式系统中的每个节点或进程都有自己的时间概念或本地时钟。但是,兰莫特采用本地时钟的方式与我们以前看到的有所不同。

时钟如何计算?

Lamport建议使用与我们都想到的典型物理时钟不同的东西。我们可以使用计数器来代替使用每个进程的物理时钟来跟踪事件的顺序。计数器可以以初始时间(例如0)开始,并且我们可以将该计数器视为进程自己的本地时钟。

Lamport继续提出这一想法,提出不仅在分布式系统中的每个进程都将拥有自己的计数器时钟,而且记录在进程中的每个事件也应在该进程的本地时钟上具有一个值。此外,时钟上每个事件的值必须反映关系发生之前的任何事件。例如,如果事件a→b,则事件a发生时的时钟时间必须小于事件b发生时的时钟时间;换句话说,clock(a)

通过使用基本计数器而不是物理时钟,Lamport将时钟简化为更易于处理的内容。这些计数器时钟称为逻辑时钟。逻辑时钟与物理时钟完全不同,因为没有中央时间概念,并且时钟只是一个计数器,它会根据系统中的事件进行递增。

逻辑时钟:定义。

分布式系统中的每个进程都可以使用逻辑时钟对与之相关的所有事件进行因果排序。当事件发生在某个进程中时(无论是发送还是接收事件),该进程的时钟计数器将增加任意数量。我们将在本文的第二部分中详细了解该方法的工作原理。我们还将向我们介绍Lamport的递增计数器算法,以及如何遵循流程之间的因果关系。有很多有趣的东西要学习;值得庆幸的是,我们有更多时间和另一篇文章来介绍这一切

资源资源

兰珀特在逻辑时钟和因果排序方面的工作很容易掌握和编写。有很多很棒的资源介绍这些主题,但复杂性各不相同。如果你想进一步阅读,请查看下面列出的一些我喜欢的资源

  1. Leslie Lamport在分布式系统中的时间,时钟和事件排序

  2. 区域中事件的时间,时钟和顺序。系统,Dan Rubenstein

  3. 时间和顺序:Lamport时间戳记,Indranil Gupta

  4. Lamport的逻辑时钟,Michael Whittaker

  5. 逻辑时钟,Paul Krzyzanowski教授

资讯来源:由0x资讯编译自DEV,原文:https://dev.to/vaidehijoshi/logical-time-and-lamport-clocks-part-1-9e0 ,版权归作者所有,未经许可,不得转载
提示:投资有风险,入市需谨慎,本资讯不作为投资理财建议。请理性投资,切实提高风险防范意识;如有发现的违法犯罪线索,可积极向有关部门举报反映。
你可能还喜欢