【分布式计算：原理、算法和系统】第三章 逻辑时间【待补全】

【分布式计算：原理、算法和系统】第三章 逻辑时间【待补全】

3.1 引言

事件之间因果关系的概念是并行、分布式计算和操作系统设计和分析的基础。通常情况，使用物理时间（physical time）跟踪因果关系。但是，在分布式系统中，不可能有全局物理时间，实际的可能仅是它的近似。

As asynchronous distributed computations make progress in spurts, it turns out that the logical time, which advances in jumps, is sufficient to capture the fundamental monotonicity property associated with causality in distributed systems. 随着分布式计算的迅猛发展，出现了以跳跃方式行进的逻辑时间的概念，它能充分捕获与分布式系统因果关系有联系的基本的单调性特性。

本章讨论实现逻辑时间的三种方法（即标量时间、矢量时间和矩阵时间）以捕获分布式计算时间之间的因果关系。

有关进程事件之间因果优先关系的知识有助于解决分布式系统的各种问题:

1. Distributed algorithms design。事件之间因果优先关系的知识，有助于保证互斥算法的活性和公平性，有助于维护复制型数据中的一致性，有助于设计正确的死锁检测算法以避免幻影和未检测出的死锁。
2. Tracking of dependent events。分布式查错中，关于事件之间的因果依赖知识有助于为恢复重新执行而构建一个一致状态；故障恢复中，它有助于建立一个检查点；复制型数
   据库中，假设网络分块的话，它有助于检测非一致性。
3. Knowledge about the progress。有关事件间因果依赖的知识，有助于测量分布式计算中进程的进度，这在抛弃过时的信息、收集垃圾和终止检测中是有用的。
4. Concurrency measure。了解有多少事件是因果相关的，对于测量计算中的并发量非常有用。

在一个逻辑时钟系统中，每一个进程都有一个按规则运行的逻辑时钟。每个事件都赋予一个时间戳（timestamp），事件之间的因果关系一般从它们的时间戳推导出来。赋予事件的时间戳遵守基本单调性。这就是说，事件a的因果性影响事件b,那么α的时间戳就比b的时间戳小。

本章将首先提出分布式系统中逻辑时钟系统的一个一般性框架，然后讨论在一个分布式系统中实现逻辑时间的主要方法。第一种方法是Lamport标量时钟，其时间用非负整数表示；第二种方法，其时间用一个非负整数的向量表示；第三种方法，时间用一个非负整数的数组表示。我们也讨论有效实现向量时钟系统的方法。

本章以讨论虚拟时间作为结尾，虚拟时间的实现是使用时间变形(time-warp)机制，并简要说明物理时钟同步和网络时间协议。

3.2 逻辑时钟框架

3.2.1 定义

逻辑时钟系统由一个时间域（time domain） $T$ 和一个逻辑时钟 $C$ 组成。 $T$ 的元素形成一个关系 $<$ 上的偏序集合（partially ordered set）。这种关系通常称作先发生或因果优先，从直观上来说，这种关系类似于物理时间的早于关系。逻辑时钟 $C$ 是一个函数，他把分布式系统中的事件 $e$ 影射到时间域 $T$ 中的一个元素，表示为 $C(e)$ 且成为 $e$ 的时间戳，定义如下：
$$C:H\mapsto T$$
使得下面的性质被满足:

• 对两个事件 $e_i$ 和 $e_j$，$e_i\to e_j\Rightarrow C(e_i)<C(e_j)$
  • 这种单调性被称为时钟一致性条件,当 $T$ 和 $C$ 满足下面条件:
• 对两个事件 $e_i$ 和 $e_j$，$e_i\to e_j\iff C(e_i)<C(e_j)$
  • 则说这个系统是强一致的。

偏序：设 R 为非空集合 A 上的关系，如果 R 是自反的、反对称的和可传递的，则称 R 为 A 上的偏序关系，简称偏序

3.2.2 实现逻辑时钟

实现逻辑时钟需要解决两个问题:本地每个进程表示逻辑时间的数据结构和更新数据结构以保证一致性条件的协议(规则集合)。

每个进程 $p_i$ 维护数据结构使其有下面两种能力

• 一个本地逻辑时钟，表示为 $l{c}_i$，帮助进程 $p_i$ 测量自己的进度。
• 一个全局时钟，表示为 $g{c}_i$ ，它表示进程 $p_i$ 从本地角度所见的全局逻辑时间。它使进程能给本地事件赋予一致的时间戳。具有代表性的情况是 $l{c}_i$为 $g{c}_i$ 的一部分。

协议保证对进程本地时钟（也就是以它的角度所见的全局时间）进行一致地管理。它由下面两个规则组成：

(1) R1规则。此规则控制进程在执行一个事件(发送、接收或内部的事件)时如何更新本地逻辑时钟。

(2) R2规则。此规则管理流程如何更新其全局逻辑时钟，以更新其全局时间和全局进度视图。它规定了关于逻辑时间的哪些信息承载在消息中，以及接收进程如何使用该信息更新其全局时间视图。

3.3 标量时间（Scalar time）

3.3.1 定义

1978年Lamport[9]提出了标量表示法，以便对分布式系统中的事件进行全排序。在该表示法中的时间域是非负整数集合。进程 $p_i$ 的本地逻辑时钟和本地所见的全局时间被挤入一个整数变量 $C_i$ 。

R1规则和R2规则更新时钟如下：

• R1：在执行一个事件之前，进程 $p_i$ 执行如下动作：
  $$C_i:=C_i+dd>0$$
  一般来说，每次执行R1规则，d就可能有不同的值，且这个值往往依赖于不同的应用。典型的d值保持为1，这足以把一个进程中每个事件的时间标识为唯一的，且d的增量保持最低的级数。

• R2：每个消息附加有它的发送方在发送时的时钟值，当进程 $p_i$ 接收到一个带有时间戳 $C_{msg}$ 的消息时，它执行如下动作：

  1. $C_i:=max(C_i,C_{msg})$
  2. 执行R1规则
  3. 传递该消息

图3.1显示了d=1的标量时间的演化过程。

图3.1 标量时间变化

3.3.2 基本性质

1、一致性（Consistency property）

对两个事件 $e_i$ 和 $e_j$，$e_i\to e_j\Rightarrow C(e_i)<C(e_j)$

2、全序（Total Ordering）

标量时钟能用于排列分布式系统的全序事件。全序事件的主要问题是在不同进程中可能会有两个或两个以上的事件有相同时间戳(对两个事件 $e_i$ 和 $e_j$，$C(e_i)=C(e_j)\Rightarrow e_i||e_j$)。例如，在图3.1中，进程 $p_1$ 的第三个事件和进程 $p_2$ 的第二个事件有相同的标量时间戳。因此，为对这样的事件排序，需要一个打破均衡的机制。典型的情形可按下述方法进行额外比较：进程标识符按线性排序并且有相同标量时间戳事件之间的相等关系以过程标识符为根据被打破。进程标识符排位越低，则优先级越高。一个事件的时间戳用 $(t,i)$对表示，其中 $t$ 是发生时间，$i$是它在进程的标识。各带有时间戳 $(h,i)$ 和 $(k,i)$ 的两个事件 $x$ 和 $y$ 的全序关系 $\prec$ 定义如下：
$$x\prec y\iff (h<kor(h=kandi<j))$$
这里需要说明:KaTeX parse error: Undefined control sequence: \or at position 29: …tarrow x\to y\ \̲o̲r̲ ̲\ x||y

3、事件计数（Event counting）

如果 $d$ 的增加值总是1，则标量时间有下面有趣的性质：如果事件 $e$ 有一个 $h$ 的时间戳，那么 $h-1$ 表示在产生事件 $e$ 之前，所需要的以事件为计数单位的最小逻辑持续时间，我们称其为事件 $e$ 的高度。换句话说，在事件 $e$ 产生之前，已顺序产生了 $h-1$ 个事件，而不管这些事件是哪些进程产生的。例如，图3.1中，在以 $b$ 为终点的最长因果路径(the longest causal path)上，有5个事件先于事件 $b$。

4、非强一致性（No strong consistency）

例如，在图3.1中进程 $p_1$ 的第三个事件的标量时间戳比进程 $p_2$ 的第三个事件小，而前者并没有在后者之前发生。

标量时钟不是强一致性的原因是：一个进程的本地逻辑时钟和本地全局时钟被压缩成一个，导致了不同进程的事件之间因果依赖信息的缺失（the loss causal dependency information among events at different processes.）。例如，图3.1中，进程 $p_2$ 接收到进程 $p_1$ 的消息时，它更新它的时钟为3，忘掉它所依赖的 $p1$ 上的最近事件的时间戳2。

3.4 向量时间（Vector time）

3.4.1 定义

向量时钟系统由Fidge、Mattern和Schmuck独立开发出来，在向量时钟系统中，时间域由 $n$ 维非负整数向量集合表示。每个进程 $p_i$ 维护一个向量 $v{t}_i[1\dots n]$,其中 $v{t}_i[i]$ 是 $p_i$ 的本地逻辑时钟并描述在进程 $p_i$ 上逻辑时间的进度。$v{t}_i[j]$ 表示进程 $p_i$ 的有关进程 $p_j$ 本地时间最近的信息。如果 $v{t}_i[j]=x$ 那么 $p_i$ 就知道进程 $p_j$ 的逻辑时间已进展到 $x$ 。用整个向量 $v{t}_i$ 代替 $p_i$ 所见的全局时间，并且用于给事件打上时间戳。

进程 $p_i$ 使用下面的 R1 规则和 R2 规则更新它的时钟

• R1：在执行一个事件之前，进程 $p_i$ 更新其本地逻辑时间如下：
  $$v{t}_i[i]:=v{t}_i[i]+dd>0$$

• R2：把每个消息 $m$ 加入到发送方进程在发送时的向量时钟 $vt$。一旦接收到这样一个消息 $(m,vt)$ ,进程 $p_i$ 执行如下一系列动作：

  1. 更新它的全局逻辑时间如下
     $$1\le k\le n:v{t}_i[k]:=max(v{t}_i[k],vt[k])$$

  2. 执行R1规则

  3. 传递该消息

一个事件的时间戳是该事件执行时它的进程的向量时钟的值。图3.2显示了增量 $d=1$ 的向量时钟进度的例子。最初，向量时钟是$[0,0,0，\dots .，0]$。

定义下面的关系以比较两个向量时间戳 $vh$ 和 $vk$：

3.4.2 基本性质（Basic properties）

1、同构（Isomorphism）

如果分布式系统的事件用向量时钟系统来打时间戳，就具有如下的性质：

• 如果两个事件 $x$ 和 $y$ 分别有时间戳 $vh$ 和 $vk$，那么
  $$\begin{gathered} x\to y\iff vh<vk \\ x||y\iff vh||vk \end{gathered}$$
  这样，由分布式计算产生的偏序事件集合与它们的向量时间戳之间是同构关系。

如果发生一个事件的过程是已知的，那么比较两个时间戳的测试能被简化如下：如果事件 $x$ 和 $y$ 分别发生在进程 $p_i$ 和 $p_j$ 并且分别给它们赋时间戳 $vh$ 和 $vk$，那么
KaTeX parse error: Undefined control sequence: \and at position 72: … (vh[i]>vk[i] )\̲a̲n̲d̲ ̲(vh[j]

2、强一致性（Strong consistency）

向量时钟系统具有强一致性。因此，通过查看两个事件的向量时间戳，我们就能确定这两个事件是否有因果关系。总之，Charron-Bost指出，为具有这种性质，向量时钟的维数（也就是分布式计算中进程的总数）不能小于n。

3、事件计数（Event counting）

如果在R1规则中d总是1，那么在进程 $p_i$ 中向量的第i个元素 $v{t}_i[i]$表示在 $p_i$ 上知道该瞬间之前发生的事件数。这样，如果事件 $e$ 有时间戳 $vh$ ,那么 $vh[j]$ 就表示进程 $p_j$ 执行的因果关系先于 $e$ 的事件数。$\sum vh[j]-1$表示在分布式计算中因果关系先于 $e$ 的事件总数。

4、应用

由于向量时间准确跟踪了因果依赖关系，因此它有各种广泛的应用。例如，应用于分布式查错，实现因果排序的通信和因果分布式共享存储。建立全局断点，在最佳恢复中确定检查点的一致性。

3.5 向量时钟的有效实现

3.5.1 差量技术（Singhal–Kshemkalyani’s differential technique）

Singhal-Kshemkalyani的差量技术是基于这样的观察结果：在向同一进程连续发送消息之间，发送方进程的向量时钟中只有少数条目可能会更改，因为在传递消息时，仅有向量时钟中的某些项会频繁的交互作用，所以当进程的数量巨大时，上述情况更有可能出现。在这种技术中，当进程 $p_i$ 向进程 $p_j$ 发送一条消息时，它只携带与最后一条发送给 $p_j$ 的消息不同的向量时钟项。

该技术的工作原理如下：从上次发送给 $p_j$ 消息以来，$p_i$ 向量时钟的项 $i_1，i_2，\cdots ，i_{n1}$ 已经更新为 $v_1，v_2，\cdots ，v_{n1}$，则进程 $p_i$ 可把$\{(i_1,v_1),(i_2,v_2),\cdots ,(i_{n1},v_{n1})\}$这样的压缩时间戳附加在发往 $p_j$ 的消息中。当 $p_j$ 接收到消息时，更新它的向量时钟：
$$v{t}_i[i_k]=max(v{t}_i[i_k],v_k),k=1,2,...,n_1$$
这个技术的实现要求每个进程记住它上一次发给其他所有进程消息的向量时间戳,该技术的直接实现将导致在每个进程上有 $O(n^2)$ 的存储开销，为传递消息，该技术同样要求通信通道遵守$FIFO$规则。

Singhal和Kshemkalyani开发了一个聪明的技术，该技术把在每个进程上的存储开销削减到$O(n)$数量级，以如下方式工作。进程 $p_i$ 维护下面两个附加的向量：

• $L{S}_i[\mathrm{1...}n]$(‘Last Sent’):

  $L{S}_i[j]$表示当进程 $p_i$ 最后一次向进程 $p_j$ 发送消息时 $v{t}_i$ 的值。

• $L{U}_i[\mathrm{1...}n]$(‘Last Update’):

  $L{U}_i[j]$表示当进程 $p_i$ 最后一次更新 $v{t}_j$ 时 $v{t}_i$ 的值。

当进程 $p_i$ 接收到消息后，捕获到进程 $p_j$ 新进展后，更新 $v{t}_i[j]$ ，$L{U}_i[j]$ 也将更新。当进程 $p_i$ 向 $p_j$ 发送消息时，$L{S}_i[j]$将更新。如果从上次 $p_i$ 到 $p_j$ 通信以来，向量时钟只有$v{t}_i[k]$被更新，那么$L{S}_i[j]<L{U}_i[k]$成立。因此 ，仅有这些元素需要通过消息从 $p_i$ 发送到 $p_j$ ，当 $p_i$ 发送消息到 $p_j$ ，它只需要发一个元组集合：
$$\{(x,v{t}_i[x])|L{S}_i[j]<L{U}_i[j]\}$$
作为一个时间戳给 $p_j$ , 而不是发送消息中的n项向量。这样，并不是大小为的整个向量和消息一起发送，而仅是从上次发送给那个进程消息以来向量时钟中已经改变的那些元素以$\{(p_1,latest\_value),(p_2,latest\_value),\dots \}$
格式发送，其中 $p_i$ 表示向量时钟的第 $p_i$ 个成分已改变。

这种压缩的方法可以用图3.4显示，例如 $p_3$ 到 $p_2$ 的第三个消息（包含时间戳{(3,2)})通知 $p_2$ ，向量时钟的第三个成分已经被修改，且新的值为2。这是因为进程 $p_3$ 自发送给 $p_2$ 的最后一条消息以来，已将时钟值从1提高到2。

图3.4

使用这种技术，能实质性地减少在大的系统中维护向量时钟的开销，尤其是进程的相互作用表现出瞬时性和空间局部性时。这项技术在包括分布式因果存储共享、分布式死锁检测、互斥的执行及局部化通信等各种应用中都是有用的。在分布式系统中，这些都是显而易见的。

3.5.2 直接依赖技术（Fowler–Zwaenepoel’s direct-dependency technique）

该技术通过在一条消息中只传递一个标量值来减少消息的大小。

每个进程 $p_i$ 维护一个依赖向量 $D_i$，初始化为：
$$D_i[j]=0forj=1,...,n$$
$D_i$被更新如下：

1. 当一个事件发生在 $p_i$ 处时， $D_i[i]:=D_i[i]+1$
2. 当进程 $p_i$ 向进程 $p_j$ 发送消息时，它将在消息中携带更新后的 $D_i[i]$ 的值
3. 当 $p_i$ 接收到来自 $p_j$ 装有d值的消息时， $p_i$ 更新它的依赖向量如下： D i [ j ] : = max ⁡ { D i [ j ] , d } D_i[j]:=\max\{D_i[j],d\} Di​[j]:=max{Di​[j],d}

这样，依赖向量 $D_i$ 仅仅反映直接依赖，在任何瞬间， $D_i[j]$ 表示在进程 $p_j$ 上直接影响当前状态的上次事件的序列号。

图3.5展示了Fowler-Zwaenepoel技术。例如，当进程p4向进程p3发送一条消息时，它携带了一个标量，表示由于这条消息，p3对p4的直接依赖关系。随后，进程p3向进程p2发送了一个消息，该消息附带了一个标量，表明p2因为这个消息而直接依赖于p3。现在，进程p2实际上间接依赖于进程p4，因为进程p3依赖于进程p4。然而，进程p2从未被告知它对p4的间接依赖。

图3.5 用Fowler-Zwaenepoel计算的向量时钟进展

虽然传递（间接）依赖关系并没有通过这种方式维护，这些依赖关系能通过脱机的递归跟踪事件的直接依赖向量来获得。这个技术对于可以通过离线方式计算因果关系的应用来说是理想的，像因果断点（causal breakpoints）和异步检测点的恢复（asynchronous checkpoint recovery）。

3.6 Jard–Jourdan的自适应技术

Fowler-Zwaenepoel直接依赖技术并不能在进程执行期间实时捕获传递依赖关系。而且，一个进程在接收一个消息之后而不是在发送出任何消息之前，必须观察一个事件（更新和记录它的依赖关系向量）。否则，依据直接依赖向量重构一个向量时间戳期间，将不能捕获全部的因果依赖关系。如果事件的发生非常频繁，该技术将要求记录大量事件的历史。

在Jard-Jourdan的技术[8]中，可以自适应地观察事件，同时保持检索所观察事件的所有因果依赖性的能力。观察一个事件意味着记录关于其依赖关系的信息。

这个方法使用了这样的思想：当一个被观察的事件记录它的依赖关系时，跟随其后发生的这些事件就能够确定它们的传递依赖关系。这就是说， 间接依赖该事件的集合使用了记录有关 $e$ 的信息

3.7 矩阵时间（Matrix time）

3.7.1 定义

在一个矩阵时钟系统中，用一个非负整数 $n\times n$ 的集合表示时间。其中，进程 $p_i$ 维护一个矩阵 $m{t}_i[\mathrm{1..}n,1.n]$,

• $m{t}_i[i,i]$表示 $p_i$ 的本地逻辑时钟并跟踪在进程 $p_i$ 上的计算进度。
• $m{t}_i[i,j]$表示 $p_i$ 具有的有关进程 $p_j$ 本地逻辑时钟 $m{t}_i[j,j]$的最新了解。
• $m{t}_i[j,k]$表示 $p_i$ 具有的有关进程 $p_j$ 的知识 , 该知识是进程 $p_j$ 具有的有关进程 $p_k$ 本地逻辑时钟$m{t}_k[k,k]$的最近知识

整个矩阵$m{t}_i$表示本地所见的全局逻辑时钟， 一个事件的矩阵时间戳是当一个事件执行时，进程矩阵时钟的值 。

进程 $p_i$ 使用下面的 R1 规则和 R2 规则更新它的时钟

• R1：在执行一个事件之前，进程 $p_i$ 更新其本地逻辑时间如下：
  $$m{t}_i[i,i]:=m{t}_i[i,i]+dd>0$$

• R2：每个消息 $m$ 中装入矩阵时间$mt$。一旦接收到这样一个消息 $(m,mt)$ ,进程 $p_i$ 执行如下一系列动作：

  1. 更新它的全局逻辑时间如下

     1. $1\le k\le n:m{t}_i[i,k]:=\max (m{t}_i[i,k],mt[j,k])$，也就是说，用接收到的时间戳 $mt$ 中$p_j$的行更新它的行$m{t}_i[i,\ast ]$。
     2. $1\le k,l\le n:m{t}_i[k,l]:=max(m{t}_i[k,l],mt[k,l])$

  2. 执行R1规则

  3. 传递该消息

参考资料

[1] Ajay D. Kshemkalyani, & Mukesh Singhal (2008). Distributed Computing: Principles, Algorithms, and Systems