bookstack
distributed system 分布式系统

时间与顺序

什么是顺序，为什么它重要？

你说“什么是顺序”是什么意思？

我的意思是，为什么我们如此执着于顺序？我们为什么在乎A发生在B之前？我们为什么不关心其他属性，比如“颜色”？

好吧，我的疯狂朋友，让我们回到分布式系统的定义来回答这个问题。

正如你可能记得的，我将分布式编程描述为使用多台计算机解决可以在单台计算机上解决的相同问题的艺术。

这实际上是对顺序执着的核心。任何只能一次做一件事的系统都会创建一个操作的总顺序。就像人们通过一个单一的门，每个操作都会有一个明确的前驱和后继。这基本上是我们努力保持的编程模型。

传统模型是：一个程序，一个进程，一个内存空间在一个CPU上运行。操作系统抽象掉了可能存在多个CPU和多个程序的事实，并且计算机上的内存实际上是共享给多个程序的。我并不是说线程编程和事件驱动编程不存在；只是它们是在“一/一/一”模型之上的特殊抽象。程序被编写为以有序的方式执行：你从顶部开始，然后向下走。

顺序作为一个属性受到了如此多的关注，因为定义“正确性”的最简单方法是说“它的工作方式就像在单台机器上一样”。这通常意味着a)我们运行相同的操作，b)我们以相同的顺序运行它们——即使有多台机器。

保持顺序（如单一系统定义的那样）的分布式系统的好处在于它们是通用的。你不需要关心操作是什么，因为它们将像在单台机器上一样被执行。这很好，因为你知道无论操作是什么，你都可以使用相同的系统。

实际上，分布式程序在多个节点上运行；有多个CPU和多个操作流进入。你仍然可以分配一个总顺序，但这需要准确的时钟或某种形式的通信。你可以使用完全准确的时钟为每个操作打上时间戳，然后用它来确定总顺序。或者你可能有某种通信系统，使得可以像在总顺序中那样分配顺序号。

总顺序与部分顺序

在分布式系统中，自然状态是部分顺序。网络和独立节点都不对相对顺序做出任何保证；但在每个节点上，你可以观察到一个局部顺序。

总顺序是一个二元关系，它为某个集合中的每个元素定义了一个顺序。

当其中一个元素大于另一个元素时，两个不同的元素是可比较的。在部分有序集中，某些元素对是不可比较的，因此部分顺序并不指定每个项目的确切顺序。

总顺序和部分顺序都是传递的和反对称的。以下陈述在总顺序和部分顺序中对X中的所有a、b和c都成立：

如果a ≤ b且b ≤ a，则a = b（反对称性）； 如果a ≤ b且b ≤ c，则a ≤ c（传递性）；

然而，总顺序是完全的：

对于X中的所有a、b，a ≤ b或b ≤ a（完全性）

而部分顺序仅是自反的：

对于X中的所有a，a ≤ a（自反性）

请注意，完全性意味着自反性；因此，部分顺序是总顺序的一个较弱变体。在部分顺序中，某些元素不满足完全性属性——换句话说，某些元素是不可比较的。

Git分支是部分顺序的一个例子。正如你可能知道的，git版本控制系统允许你从单个基础分支创建多个分支——例如，从主分支。每个分支代表基于共同祖先的源代码更改历史：

[ branch A (1,2,0)]  [ master (3,0,0) ]  [ branch B (1,0,2) ]
[ branch A (1,1,0)]  [ master (2,0,0) ]  [ branch B (1,0,1) ]
                  \  [ master (1,0,0) ]  /

分支A和B是从共同祖先派生的，但它们之间没有明确的顺序：它们代表不同的历史，不能在没有额外工作的情况下简化为单一线性历史（合并）。当然，你可以将所有提交放在某种任意顺序中（例如，先按祖先排序，然后通过将A排在B之前或B排在A之前来打破平局）——但这会通过强制不存在的总顺序而丢失信息。

在由一个节点组成的系统中，总顺序是必然出现的：指令以特定的、可观察的顺序在单个程序中执行，消息被处理。我们已经依赖于这种总顺序——它使程序的执行变得可预测。这个顺序可以在分布式系统中保持，但代价很高：通信成本昂贵，时间同步困难且脆弱。

什么是时间？

时间是顺序的来源——它允许我们定义操作的顺序——巧合的是，这也有一个人们可以理解的解释（秒、分钟、天等等）。

在某种意义上，时间就像任何其他整数计数器。它恰好重要到大多数计算机都有一个专用的时间传感器，也称为时钟。它如此重要，以至于我们已经找到了如何使用一些不完美的物理系统（从蜡烛到铯原子）合成同一计数器的近似值。通过“合成”，我的意思是我们可以通过某种物理属性在物理上遥远的地方近似整数计数器的值，而无需直接进行通信。

时间戳确实是一个简写值，用于表示从宇宙开始到当前时刻的世界状态——如果某个事件发生在特定的时间戳上，那么它可能受到之前发生的所有事件的影响。这个想法可以推广为因果时钟，它明确跟踪原因（依赖关系），而不仅仅假设在时间戳之前的所有内容都是相关的。当然，通常的假设是我们只应关注特定系统的状态，而不是整个世界。

假设时间在各处以相同的速度推进——这是一个我稍后会回到的重要假设——时间和时间戳在程序中有几种有用的解释。这三种解释是：

  • 顺序
  • 持续时间
  • 解释

_顺序_。当我说时间是顺序的来源时，我的意思是：

  • 我们可以将时间戳附加到无序事件上以对其进行排序
  • 我们可以使用时间戳来强制执行操作或消息传递的特定顺序（例如，如果操作以错误的顺序到达，则延迟该操作）
  • 我们可以使用时间戳的值来确定某件事情是否在时间上发生在另一件事情之前

_解释_——时间作为一个普遍可比较的值。时间戳的绝对值可以解释为一个日期，这对人们来说是有用的。根据日志文件中记录的停机开始的时间戳，你可以知道这是上周六，当时有一场雷暴。

_持续时间_——以时间测量的持续时间与现实世界有某种关系。算法通常不关心时钟的绝对值或其作为日期的解释，但它们可能会使用持续时间来做出一些判断。特别是，等待的时间可以提供线索，表明系统是分区的还是仅仅经历高延迟。

由于其本质，分布式系统的组件并不以可预测的方式运行。它们不保证任何特定的顺序、推进速率或延迟的缺乏。每个节点确实有一些局部顺序——因为执行是（大致上）顺序的——但这些局部顺序是相互独立的。

施加（或假设）顺序是减少可能执行和可能发生事件空间的一种方式。当事情可以以任何顺序发生时，人类很难进行推理——考虑的排列组合实在是太多了。

时间在各处以相同的速度推进吗？?

我们都有一个基于个人经验的直观时间概念。不幸的是，这种直观的时间观念使得想象总顺序比想象部分顺序更容易。想象一个事情一个接一个发生的序列，而不是并发发生的序列更容易。推理关于单一消息顺序比推理关于消息以不同顺序和不同延迟到达更容易。

然而，在实现分布式系统时，我们希望避免对时间和顺序做出强假设，因为假设越强，系统对“时间传感器”或内部时钟的问题就越脆弱。此外，施加顺序会带来成本。我们能够容忍的时间非确定性越多，我们就越能利用分布式计算的优势。

对于“时间在各处以相同的速度推进吗？”这个问题，有三种常见的回答。这些是：

  • “全球时钟”：是的
  • “局部时钟”：不，但
  • “没有时钟”：不！

这些大致对应于我在第二章中提到的三种时间假设：同步系统模型有一个全球时钟，部分同步模型有一个局部时钟，而在异步系统模型中根本无法使用时钟。让我们更详细地看看这些。

假设“全球时钟”的时间

全球时钟假设是指存在一个完美准确的全球时钟，并且每个人都可以访问该时钟。这是我们倾向于思考时间的方式，因为在人的交互中，时间上的小差异并不重要。

全球时钟基本上是一个总顺序的来源（即使这些节点从未通信，每个节点上每个操作的确切顺序）。

然而，这是一种理想化的世界观：实际上，时钟同步只能在有限的准确度范围内实现。这受到商品计算机时钟准确度的限制，如果使用像NTP这样的时钟同步协议，还受到延迟的限制，根本上还受到时空的性质的限制。

假设分布式节点上的时钟是完美同步的，这意味着假设时钟以相同的值开始并且从未偏离。这是一个不错的假设，因为你可以自由使用时间戳来确定一个全球总顺序——受时钟漂移而非延迟的限制——但这是一项非平凡的操作挑战，也是潜在的异常来源。有许多不同的场景，其中简单的故障——例如用户意外更改机器上的本地时间，或过时的机器加入集群，或同步时钟以略微不同的速率漂移等——可能导致难以追踪的异常。

尽管如此，确实有一些现实世界的系统做出了这个假设。Facebook的Cassandra就是一个假设时钟同步的系统示例。它使用时间戳来解决写入之间的冲突——具有较新时间戳的写入获胜。这意味着如果时钟漂移，新的数据可能会被旧的数据忽略或覆盖；再次强调，这是一项操作挑战（据我所知，人们对此非常关注）。另一个有趣的例子是谷歌的Spanner：论文描述了他们的TrueTime API，它同步时间但也估计最坏情况下的时钟漂移。

假设“局部时钟”的时间

第二个，或许更合理的假设是每台机器都有自己的时钟，但没有全球时钟。这意味着你无法使用本地时钟来确定远程时间戳是在本地时间戳之前还是之后；换句话说，你无法有意义地比较来自两台不同机器的时间戳。

局部时钟假设与现实世界更为接近。它分配了一个部分顺序：每个系统上的事件是有序的，但仅使用时钟无法对跨系统的事件进行排序。

然而，你可以使用时间戳来对单台机器上的事件进行排序；只要小心不让时钟跳动，你可以在单台机器上使用超时。当然，在由最终用户控制的机器上，这可能假设得过于理想：例如，用户在使用操作系统的日期控制查找日期时，可能会意外将日期更改为不同的值。

假设“没有时钟”的时间

最后，还有逻辑时间的概念。在这里，我们根本不使用时钟，而是以其他方式跟踪因果关系。请记住，时间戳只是表示截至该点的世界状态的简写——因此我们可以使用计数器和通信来确定某件事情是在另一件事情之前、之后还是同时发生的。

通过这种方式，我们可以确定不同机器之间事件的顺序，但无法说出任何关于间隔的事情，也无法使用超时（因为我们假设没有“时间传感器”）。这是一种部分顺序：可以使用计数器在单个系统上对事件进行排序，而无需通信，但跨系统排序事件需要消息交换。

在分布式系统中，最常引用的论文之一是Lamport关于时间、时钟和事件排序的论文。向量时钟是该概念的一种推广（我将更详细地介绍），是一种在不使用时钟的情况下跟踪因果关系的方法。Cassandra的兄弟系统Riak（Basho）和Voldemort（Linkedin）使用向量时钟，而不是假设节点可以访问一个完美准确的全球时钟。这使得这些系统能够避免之前提到的时钟准确性问题。

当不使用时钟时，跨远程机器对事件进行排序的最大精度受限于通信延迟。

时间在分布式系统中的使用

时间有什么好处？

  1. 时间可以定义系统中的顺序（无需通信）
  2. 时间可以为算法定义边界条件

事件的顺序在分布式系统中很重要，因为许多分布式系统的属性是根据操作/事件的顺序来定义的：

  • 正确性依赖于（对）正确事件排序的协议，例如分布式数据库中的可串行化性
  • 当资源争用发生时，顺序可以用作平局打破者，例如如果有两个订单请求一个小部件，先满足第一个并取消第二个

全球时钟将允许在两台不同机器上的操作进行排序，而无需这两台机器直接通信。没有全球时钟，我们需要进行通信以确定顺序。

时间还可以用于为算法定义边界条件——具体来说，用于区分“高延迟”和“服务器或网络链接故障”。这是一个非常重要的用例；在大多数现实世界系统中，超时用于确定远程机器是否已失败，或者它只是经历了高网络延迟。做出这种判断的算法称为故障检测器；我会很快讨论它们。

向量时钟（因果顺序的时间）

之前，我们讨论了关于分布式系统中时间进展速率的不同假设。假设我们无法实现准确的时钟同步——或者以我们的系统不应对时钟同步问题敏感为目标，我们如何对事物进行排序？

Lamport时钟和向量时钟是物理时钟的替代品，它们依赖于计数器和通信来确定分布式系统中事件的顺序。这些时钟提供了一个可以在不同节点之间进行比较的计数器。

_一个Lamport时钟_是简单的。每个进程使用以下规则维护一个计数器：

  • 每当进程执行工作时，递增计数器
  • 每当进程发送消息时，包含计数器
  • 当接收到消息时，将计数器设置为max(local_counter, received_counter) + 1

Expressed as code:

function LamportClock() {
  this.value = 1;
}

LamportClock.prototype.get = function() {
  return this.value;
}

LamportClock.prototype.increment = function() {
  this.value++;
}

LamportClock.prototype.merge = function(other) {
  this.value = Math.max(this.value, other.value) + 1;
}

一个Lamport时钟允许在系统之间比较计数器，但有一个警告：Lamport时钟定义了一个部分顺序。如果timestamp(a) < timestamp(b)：

  • a可能发生在b之前，或者
  • a可能与b不可比较

这被称为时钟一致性条件：如果一个事件发生在另一个事件之前，那么该事件的逻辑时钟在其他事件之前。如果a和b来自同一因果历史，例如两个时间戳值都是在同一进程上生成的；或者b是对在a中发送的消息的响应，那么我们知道a发生在b之前。

直观上，这意味着Lamport时钟只能携带关于一个时间线/历史的信息；因此，比较从未相互通信的系统的Lamport时间戳可能会导致并发事件看起来是有序的，而实际上并非如此。

想象一个系统，在初始阶段后分为两个独立的子系统，这两个子系统从未相互通信。

对于每个独立系统中的所有事件，如果a发生在b之前，那么ts(a) < ts(b)；但是如果你从不同的独立系统中取两个事件（例如，因果上无关的事件），那么你无法对它们的相对顺序做出任何有意义的判断。虽然系统的每个部分都为事件分配了时间戳，但这些时间戳之间没有关系。两个事件可能看起来是有序的，即使它们是无关的。

然而——这仍然是一个有用的属性——从单台机器的角度来看，任何带有ts(a)的消息发送后都会收到一个带有ts(b)的响应，而ts(b)将大于ts(a)。

_向量时钟_是Lamport时钟的扩展，它维护一个数组[ t1, t2, ... ]，其中包含N个逻辑时钟——每个节点一个。每个节点在每个内部事件中将其在向量中的逻辑时钟加一，而不是递增一个公共计数器。因此，更新规则为：

  • 每当进程执行工作时，递增向量中节点的逻辑时钟值
  • 每当进程发送消息时，包含完整的逻辑时钟向量
  • 当接收到消息时：
    • 将向量中的每个元素更新为max(local, received)
    • 递增表示当前节点的逻辑时钟值

Again, expressed as code:

function VectorClock(value) {
  // expressed as a hash keyed by node id: e.g. { node1: 1, node2: 3 }
  this.value = value || {};
}

VectorClock.prototype.get = function() {
  return this.value;
};

VectorClock.prototype.increment = function(nodeId) {
  if(typeof this.value[nodeId] == 'undefined') {
    this.value[nodeId] = 1;
  } else {
    this.value[nodeId]++;
  }
};

VectorClock.prototype.merge = function(other) {
  var result = {}, last,
      a = this.value,
      b = other.value;
  // This filters out duplicate keys in the hash
  (Object.keys(a)
    .concat(b))
    .sort()
    .filter(function(key) {
      var isDuplicate = (key == last);
      last = key;
      return !isDuplicate;
    }).forEach(function(key) {
      result[key] = Math.max(a[key] || 0, b[key] || 0);
    });
  this.value = result;
};

这个插图（来源）展示了一个向量时钟：

每个节点（A、B、C）都跟踪向量时钟。随着事件的发生，它们会用当前的向量时钟值进行时间戳标记。检查一个向量时钟，例如{ A: 2, B: 4, C: 1 }，可以准确识别出（可能）影响该事件的消息。

向量时钟的问题主要在于它们需要每个节点一个条目，这意味着对于大型系统，它们可能变得非常庞大。已经应用了多种技术来减少向量时钟的大小（要么通过定期进行垃圾回收，要么通过限制大小来降低准确性）。

我们已经看到了如何在没有物理时钟的情况下跟踪顺序和因果关系。现在，让我们看看如何使用时间持续时间来进行截止。

故障检测器（用于截止的时间）

正如我之前所述，等待的时间可以提供线索，表明系统是分区的还是仅仅经历高延迟。在这种情况下，我们不需要假设一个完美准确的全球时钟——只要有一个足够可靠的本地时钟就足够了。

给定在一个节点上运行的程序，如何判断远程节点是否已失败？在缺乏准确信息的情况下，我们可以推断，在经过一段合理的时间后，一个无响应的远程节点已经失败。

但什么是“合理的时间”？这取决于本地节点和远程节点之间的延迟。与其明确指定具有特定值的算法（在某些情况下不可避免地会出错），不如处理一个合适的抽象。

故障检测器是一种抽象出确切时间假设的方法。故障检测器通过心跳消息和定时器来实现。进程之间交换心跳消息。如果在超时发生之前未收到消息响应，则该进程会怀疑另一个进程。

基于超时的故障检测器存在过于激进（错误地声明节点已失败）或过于保守（花费很长时间检测崩溃）的风险。故障检测器需要多准确才能可用？

Chandra等人（1996）在解决共识的背景下讨论了故障检测器——这是一个特别相关的问题，因为它是大多数复制问题的基础，其中副本需要在存在延迟和网络分区的环境中达成一致。

他们通过两个属性来表征故障检测器，完整性和准确性：

强完整性。

每个崩溃的进程最终都会被每个正确的进程怀疑。

弱完整性。

每个崩溃的进程最终都会被某个正确的进程怀疑。

强准确性。

没有正确的进程会被怀疑。

弱准确性。

某些正确的进程永远不会被怀疑。

完整性比准确性更容易实现；实际上，所有重要的故障检测器都实现了这一点——你所需要做的就是不等待永远去怀疑某人。Chandra等人指出，具有弱完整性的故障检测器可以转化为具有强完整性的故障检测器（通过广播有关被怀疑进程的信息），使我们能够集中关注准确性属性的范围。

除非能够假设消息延迟有一个硬性上限，否则避免错误地怀疑非故障进程是困难的。这个假设可以在同步系统模型中做出——因此，在这样的系统中，故障检测器可以是强准确的。在不对消息延迟施加硬性限制的系统模型下，故障检测最多只能是最终准确的。

Chandra等人表明，即使是一个非常弱的故障检测器——最终弱故障检测器⋄W（最终弱准确性 + 弱完整性）——也可以用来解决共识问题。下面的图（来自论文）说明了系统模型与问题可解性之间的关系：

正如你所看到的，在异步系统中，某些问题在没有故障检测器的情况下是不可解的。这是因为在没有故障检测器（或对时间边界的强假设，例如同步系统模型）的情况下，无法判断远程节点是崩溃了，还是仅仅经历了高延迟。这个区分对于任何旨在实现单副本一致性的系统都是重要的：失败的节点可以被忽略，因为它们无法导致分歧，但分区的节点不能安全地被忽略。

如何实现故障检测器？从概念上讲，简单的故障检测器并没有太多内容，它在超时到期时简单地检测故障。最有趣的部分与如何判断远程节点是否已失败有关。

理想情况下，我们希望故障检测器能够适应不断变化的网络条件，并避免将超时值硬编码到其中。例如，Cassandra使用一种累积故障检测器，它输出一个怀疑级别（介于0和1之间的值），而不是二元的“正常”或“故障”判断。这使得使用故障检测器的应用程序能够自行决定在准确检测和早期检测之间的权衡。

时间、顺序与性能

之前，我提到过必须为顺序付出代价。我是什么意思？

如果你正在编写一个分布式系统，你大概拥有不止一台计算机。自然（和现实）的世界观是部分顺序，而不是总顺序。你可以将部分顺序转换为总顺序，但这需要通信、等待，并施加限制，限制在任何特定时间点可以工作的计算机数量。

所有时钟都是仅仅是近似值，受限于网络延迟（逻辑时间）或物理学。即使在多个节点之间保持一个简单的整数计数器同步也是一项挑战。

虽然时间和顺序通常一起讨论，但时间本身并不是一个特别有用的属性。算法并不太关心时间，而更关心更抽象的属性：

  • 事件的因果顺序
  • 故障检测（例如，消息传递的上限近似值）
  • 一致快照（例如，能够检查系统在某个时间点的状态；这里不讨论）

施加总顺序是可能的，但代价高昂。它要求你以共同的（最低）速度进行操作。确保事件以某种定义的顺序交付的最简单方法通常是指定一个单一的（瓶颈）节点，通过该节点传递所有操作。

时间/顺序/同步真的必要吗？这要看情况。在某些用例中，我们希望每个中间操作将系统从一个一致状态移动到另一个一致状态。例如，在许多情况下，我们希望数据库的响应代表所有可用信息，并希望避免处理系统可能返回不一致结果的问题。

但在其他情况下，我们可能不需要那么多时间/顺序/同步。例如，如果你正在运行一个长时间的计算，并且在最后之前并不关心系统的表现——那么只要你能保证答案是正确的，你实际上并不需要太多同步。

同步通常作为一种粗糙的工具应用于所有操作，而实际上只有一部分情况对最终结果真正重要。什么时候需要顺序来保证正确性？CALM定理——我将在最后一章讨论——提供了一个答案。

在其他情况下，给出一个仅代表最佳已知估计的答案是可以接受的——也就是说，基于系统中仅包含的总信息的一个子集。特别是在网络分区期间，可能需要仅在部分系统可访问的情况下回答查询。在其他用例中，最终用户实际上无法区分一个相对较新的、可以便宜获得的答案和一个保证正确但计算成本高的答案。例如，某个用户X的Twitter关注者数量是X还是X+1？或者电影A、B和C是某个查询的绝对最佳答案吗？进行一次便宜的、基本正确的“最佳努力”是可以接受的。

在接下来的两章中，我们将研究用于容错强一致性系统的复制——这些系统在提供强保证的同时，对故障的抵抗力越来越强。这些系统为第一种情况提供了解决方案：当你需要保证正确性并愿意为此付出代价时。然后，我们将讨论具有弱一致性保证的系统，这些系统在面对分区时仍然可以保持可用，但只能给出“最佳努力”的答案。

推荐阅读

Lamport clocks, vector clocks

Failure detection

Snapshots

Causality