原文链接：https://www.cockroachlabs.com/blog/living-without-atomic-clocks/

CockroachDB 是基于 Google 的 Spanner 设计的数据存储系统。Spanner 最令人惊讶和最受启发的方面之一是它使用原子钟和 GPS 时钟为参与节点提供 真正 准确的时间同步。Spanner 的设计者将此称为 “TrueTime”，它为系统中任意两个节点之间的时钟偏移提供了严格的界限。这让他们可以做一些非常漂亮的事情！我们将在下面详细说明其中的一些，但其中最主要的是它们能够利用紧密同步的时钟来提供高水平的外部一致性（我们将解释这是什么）。

如果有人对 Spanner 有一点了解，他们的第一个问题就是：“如果你正在构建一个开源数据库，你就不能使用原子钟；那么 CockroachDB 到底是如何工作的呢？”

这是一个很好的问题，我们（尝试）在这里详细说明。作为一个源自 Spanner 的系统，我们的挑战在于提供类似的外部一致性保证，而无需使用神奇的时钟。CockroachDB 旨在在现成的商业硬件上运行，在任意节点集合上运行。它是“云中立的”，因为它可以使用您最喜欢的虚拟化层很好地跨越多个公共云和私有云。

需要对专用硬件进行外部依赖以进行时钟同步将是一件大事。那么 CockroachDB 会做什么呢？好吧，在回答这个问题之前，让我们更深入地了解一下为什么 TrueTime 是为 Spanner 构思的。

时间在分布式系统中的重要性

时间是一个善变的东西。对于不熟悉分布式系统中时间复杂性的读者来说，需要了解的是：系统中的每个节点都有自己的时间视图，由自己的片上时钟设备提供支持。这个时钟设备很少会与系统中的其他节点完全同步，因此，没有“绝对”时间可以参考。

除了存在主义，完美同步的时钟是分布式系统研究的圣杯。从本质上讲，它们提供了一种对事件进行绝对排序的方法，而不管事件起源于哪个节点。当性能受到威胁时，这可能特别有用，允许节点子集向前推进而不考虑集群的其余部分（看到每个其他节点都看到相同的“绝对”时间），同时仍然保持全局排序保证。我们最喜欢的图灵奖得主在这里就这个主题写了几句话 。

线性化

相比之下，没有完美同步时钟的系统，如果希望建立完整的全局排序，则必须在每次操作时与单一时间源进行通信。这就是Percolator使用的“全局时间戳分配器”背后的动机 。一个系统按照 \[T1 ,T2 ] 的顺序对事务 T1 和 T2 进行排序，只要 T2 在 T1 完成后开始，无论观察者如何，都提供了称为 “外部一致性”的最强一致性保证。为了进一步混淆，这就是人们可以互换地称为“线性化”或“严格串行化”的东西。Andrei 对这种 一致性模型有更多的看法。

可串行化

让我们再切入一点，介绍“可序列化”的概念。大多数数据库开发人员都熟悉可串行化作为 ANSI SQL 标准提供的最高隔离级别。它保证事务中的组成读取和写入发生，就好像该事务在其执行期间被授予对数据库的独占访问权限，保证没有事务相互干扰。换句话说，没有并发事务 T2 能够读取事务 T1 的任何部分写入状态或执行导致事务 T1 在其执行过程中读取相同Key的不同值的写入。

在非分布式数据库中，可串行化意味着事务的线性化，因为单个节点具有单调递增的时钟（或者应该，无论如何！）。如果事务 T1 在开始事务 T2 之前提交，则事务 T2 只能在以后提交。

在分布式数据库中，事情可能会变得很复杂。如果系统中的节点具有不同步的时钟，很容易出现违反因果关系的并发事务。假设有两个节点 N1 和 N2 ，以及两个事务 T1 和 T2 ，分别在 N1 和 N2 提交。因为我们没有参考单一的全局时间源，所以事务使用节点本地时钟来生成提交时间戳。为了说明这方面的技巧，假设 N1 有一个准确的时钟，但 N2 有一个时钟滞后 100ms。我们从 T1 开始，寻址 N1 ，它能够在 ts=150ms 时提交。外部观察者看到 T1 提交，因此在 50 毫秒后（在 t=200 毫秒）启动 T2 （寻址 N2 ）。由于 T2 使用从 N2 的滞后时钟检索到的时间戳进行注释，因此它在 ts=100ms 时“在过去”提交。现在，任何在 N1 和 N2 上读取Key的观察者都会看到相反的顺序，T2 的写入（在 ts=100ms 时）似乎发生在 T1 的（在 ts=150ms 时）之前，尽管情况正好相反。（请注意，只有当两个事务访问一组不相交的Key时才会发生这种情况。）

图 1. 由于时钟不同步而导致无序提交的因果相关事务。

上述“异常”（如图 1 所示）是我们所说的“因果反转”。虽然 Spanner 提供了可线性化，但 CockroachDB 仅声称可串行化，尽管有一些功能可以帮助弥合实践中的差距。我会（懒惰地）再次听从 Andrei 的意见，他确实在 这里涵盖了很多领域。 

TrueTime 如何提供线性化

回到 Spanner 和 TrueTime。请务必记住，TrueTime 不保证时钟完全同步。相反，TrueTime 给出了集群中节点之间时钟偏移的上限。同步硬件有助于最小化上限。在 Spanner 的案例中，Google 提供了 7 毫秒的上限，这很精确；相比之下，使用 NTP 进行时钟同步的时间可能在 100 毫秒到 250 毫秒之间。

那么，鉴于时钟之间仍然存在不准确性，Spanner 如何使用 TrueTime 来提供线性化？它实际上非常简单。它等待。在允许节点报告事务已提交之前，它必须等待 7ms。因为系统中的所有时钟都在 7ms 之内，所以等待 7ms 意味着没有后续事务可以在较早的时间戳提交，即使较早的事务是在时钟快了最大 7ms 的节点上提交的。相当聪明。

细心的读者会发现，整个“等待不确定性”的想法并不是基于周围有原子钟。人们可以很好地等待任何系统中的最大时钟偏移并实现线性化。在每次写入时都必须吃掉 NTP 偏移量当然是不切实际的，尽管 最近 在该领域的研究可能有助于将其降低到毫秒以下。

有趣的事实：早期的 CockroachDB 有一个隐藏的 --linearizable 开关，基本上可以完成上述操作，所以理论上，如果你 确实有原子钟（或通常可接受的最大时钟偏移），你会得到类似 Spanner 的行为开箱即用. 考虑到它的测试不足，我们已经将其删除，但随着云提供商倾向于公开类似 TrueTime 的 API，复活它也许是有意义的 。芯片级原子钟已成为现实；将一个放在服务器主板上会击败石英晶体振荡器。

线性化有多重要

更强的保证是一件好事，但有些比其他的更有用。重新排序因果相关事务的提交时间戳的可能性在实践中可能是一个边缘问题。可能发生的情况是，以历史时间戳检查数据库可能会产生矛盾的情况，即事务 T1 尚不可见，而事务 T2 可见，即使已知事务 T1 早于 T2 ，因为它们是因果相关的。但是，只有在 (a) 事务期间读取或写入的Key之间没有重叠，以及 (b) 客户端之间存在可能影响 DBMS 活动的外部低延迟通信通道时，才会发生这种情况。

对于重新排序可能有问题的情况，CockroachDB 使用“因果关系令牌”，这只是事务期间遇到的最大时间戳。它在因果链中从一个参与者传递到下一个参与者，并用作连续事务的最小时间戳，以确保每个事务都具有正确排序的提交时间戳。当然，这种机制并不能正确排序独立的因果链，尽管想象一个有问题的用例需要创造力。

但 TrueTime 有一个比订购交易更重要的用途。当开始从多个节点读取数据的事务时，必须选择一个时间戳，该时间戳保证至少与所有节点的最高提交时间一样大。如果不是这样，那么新事务可能无法读取已经提交的数据——这是不可接受的一致性破坏。使用 TrueTime，解决方案很简单；只需选择当前的 TrueTime。由于每个已经提交的事务必须至少在 7 毫秒前提交，因此当前节点的挂钟必须具有大于或等于最近提交的事务的时间。哇，这既简单又高效。那么 CockroachDB 是做什么的呢？

CockroachDB 如何选择事务时间戳

CockroachDB 会在事务进行时发现一个适当的时间戳，如果需要，有时会在稍后的时间戳重新启动它。

如前所述，我们为事务选择的时间戳必须大于或等于我们打算读取的所有节点的最大提交时间戳。如果我们提前知道要读取的节点，我们可以发送一个并行请求，要求每个节点的最大时间戳，并使用最新的。但这有点笨拙，因为 CockroachDB 旨在支持读/写集不确定的会话 SQL，我们 无法 提前知道节点。这也是低效的，因为我们甚至必须在开始执行之前等待最慢的节点响应。旁白：读者可能对 Calvin 和 SLOG感兴趣，围绕预先声明读/写集（尽管放弃了会话 SQL）而开发的一系列研究系统，因此设法避免了此类问题。

CockroachDB 所做的实际上与 Spanner 所做的惊人地相似，但时钟同步要求要宽松得多。简单地说：

虽然 Spanner 总是在写入后等待，但 CockroachDB 有时会重试读取。

CockroachDB 启动事务时，它会根据当前节点的时间选择一个临时提交时间戳。它还通过添加集群的最大时钟偏移量来建立所选挂钟时间的上限 \[commit timestamp, commit timestamp + maximum clock offset]。该时间间隔代表不确定性窗口。

当事务从各个节点读取数据时，只要没有遇到在此间隔内写入的Key，它就会毫无困难地继续进行。如果事务遇到低于其临时提交时间戳的时间戳的值，它会在读取期间简单地观察该值并在写入期间覆盖较高时间戳的值。只有当观察到一个值在不确定区间内时，CockroachDB 特定的机制才会启动。这里的核心问题是，鉴于时钟偏移，我们无法确定遇到的值是否 在 我们的事务开始之前提交。在这种情况下，我们只需执行 不确定性重新启动即可，使临时提交时间戳刚好高于遇到的时间戳。至关重要的是，不确定性区间的上限在重启时不会改变，因此不确定性窗口会缩小。从许多节点读取不断更新的数据的事务可能会被迫多次重启，但永远不会超过不确定间隔，每个节点也不会超过一次。

如上所述，Spanner 和 CockroachDB 的对比是，Spanner 总是将写入延迟一小段时间，而 CockroachDB 有时会延迟读取。这延迟多长时间？它主要取决于几乎同时读取和写入同一行的频率。大多数情况下，读取只是重试一次，因此假设的 2ms 读取变为 4ms。如果运气不好，可能不得不多次重试读取。根据时钟的同步方式，可以重试的次数有上限。对于 NTP，这可能是 250 毫秒，因此即使是最不走运的事务也不必因为时钟相关原因重试超过 250 毫秒。

因为 CockroachDB 依赖于时钟同步，所以节点会定期比较它们之间的时钟偏移。如果任何节点超过了配置的最大偏移量，它就会自行终止。如果您对违反最大时钟偏移量时会发生什么感到好奇，我们在 这里已经考虑过。