CockroachDB博客翻译：Living without atomic clocks（上） 独家

最近看到了CockroachDB的这篇博客 Living without atomic clocks: Where CockroachDB and Spanner diverge（不依赖原子钟：CockroachDB和Spanner的分野。原文地址 https://www.cockroachlabs.com/blog/living-without-atomic-clocks/）。

这篇博客算是把分布式系统中的时间问题，讲的比较透彻了，所以就抽时间翻译了一下。因为原文比较长，所以就拆成上下两篇发了，这是上篇。

(资料图片仅供参考)

话不多说，下面就是正文了。

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

如果有人对Spanner略知一二，那么他们首先要问的问题之一是：“如果你要写一个开源数据库，你就不能使用原子钟；那么CockroachDB到底是怎么工作的呢？”（译者注：这里给不了解Spanner的读者预先解释一下，原子钟是非常昂贵的设备，并且Spanner的TureTime对原子钟的使用方法也是没有开源的。所以一个开源的数据库，必定不能依赖原子钟来工作，因为那样哪怕你开源了，大家也完全没有办法去使用）

这是一个非常好的问题，也是我们（试图）在这里详细阐述的问题。作为一个受Spanner启发的系统，我们面临的挑战在于在没有神奇全局时钟（译者注：原文为“magical clock”）的情况下提供类似的外部一致性保证。CockroachDB旨在在现成的商品硬件上运行，在任何任意的节点集合上运行。它是“云中立的”，因为它可以很好地跨多个公共和/或私有云，使用您喜欢的任何虚拟化层。如果需要外部依赖于专门的硬件来进行时钟同步，那是一件不现实的事情。

那么CockroachDB是怎么做的呢？好吧，在回答这个问题之前，让我们更深入地了解为什么TrueTime是为Spanner设计的。

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

时间是一件变化无常的事情。对于不熟悉分布式系统研究中时间复杂性的读者来说，需要了解的是：系统中的每个节点都有自己的时间，由自己的本地时钟提供。这个时钟设备很少能与系统中的其他节点完全同步，因此，没有“绝对”时间可以参考。

抛开是否存在不谈，完全同步的时钟是分布式系统研究的圣杯（译者注：这句话的意思是，虽然完全同步的时钟不可能实现（不过也不完全绝对，万一未来可以做到量子通信呢），但我们还是可以幻想一下完全同步的时钟如果存在，会对分布式系统带来多大的变革）。从本质上讲，无论事件起源于哪个节点，（完全同步的时钟）都能提供一种绝对排序事件的方法。当性能受到威胁时，这一点尤其有用，允许节点子集在不考虑集群其他部分的情况下向前推进（就像其他节点都看到了相同的“绝对”时间一样），同时仍然保持全局排序保证。我们最喜欢的图灵奖得主（译者注：指Barbara Liskov老太太，2008 年因“对编程语言和系统设计的实践与理论基础，尤其是数据抽象化、容错和分布式计算的贡献”获得图灵奖，她发明了CLU编程语言，目前常用的C++、Java、Python都受到CLU的影响）在这篇论文中（译者注：指Practical uses of synchronized clocks in distributed systems，Barbara Liskov于1978年发表的一篇讨论分布式系统中同步时钟应用的论文，Spanner也引用了这篇论文）写了一些关于这个主题的内容。

Linearizability（译者注：直译是线性化，也可以翻译成“线性一致性”）

相比之下，没有完全同步时钟的系统（实际上是所有的系统）想要建立一个完整的全局排序，必须在每次操作中与单个时间源通信。这就是Percolator使用的“timestamp oracle”背后的动机。假设从外部来看，一个指定了事务T1、T2的顺序为[T1,T2]的系统在任何情况下都能给出事务T2在事务T1结束之后开始的强一致性保证的话，我们称这系统具备了“外部一致性（external consistency）”。（译者注：这句话比较难理解，实际上是呼应开头，给出了external consistency的释义：一个系统如果具备了external consistency，那么它在任何情况下都会给外部呈现一个符合Linearizability的结果。这句话看起来有点像重复了1+1=2，但实际上，确实就是1+1=2（哈哈）。后文里external consistency就等同于Linearizability）。为了进一步混淆（译者注：这里作者有点开玩笑摆烂的意思，分布式领域这些一致性概念确实非常混乱，很多时候为了解释这些模棱两可的名词就要费很大的劲，比如各种各样的consistency（笑）。各位读者在这里没太有必要纠结于弄懂这几个词的含义，看本段最后的注解就OK了），这就是人们可互换地称之为“Linearizability（线性一致性）”或“Strict Serializability（严格可串行化）”的东西。Andrei（译者注：指作者同事Andrei Matei）对这种一致性模型有更多的描述。

（译者注：其实这段只说了一件事：本文中，External Consistency = Linearizability = Strict Serializability。（大家记住这一句就行，不要在这过于纠结了）

关于Linearizability，这里给大家再解释一下。线性一致性其实是并发系统中的一个概念，指的是对单个顺序的一组操作提供了一个符合客观时间顺序的排序操作。在这篇文章中，实际上是把线性一致性扩大到和Strict Serializability等同的地步了，也就是说比下文要讨论的Serializability更进一步，是隔离级别更上层的一个概念。哪怕在事务逻辑中不相干的事务，也要符合这个特性。就比如说事务T2在事务T1提交之后开始，T1在1ms开始，3ms提交，那么T2开始的点就必须晚于3ms，哪怕他们俩完全没有交集，比如T1修改了a，T2修改了B。所以说在事务中，我们是不需要External Consistency/Linearizability/Strict Serializability 这么严格的保证的（虽然Spanner和单机数据库做到了这点），这也是后文要论证的。）

Serializability（译者注：可串行化，也称“可序列化”）

让我们再切入一个线索，引入“Serializability”的概念。大多数数据库开发人员都熟悉Serializability，因为它是ANSI SQL标准提供的最高隔离级别。它保证一个事务在读取和写入时，就好像在这期间只有这一个事务在访问数据库一样，从而完全避免了事务间的互相干扰。换句话说，并发执行的事务T1和T2，T2读取不到T1的任何中间状态，从而让两者在执行过程中对同一key可以读取不同的值。

在非分布式数据库中，Serializability意味着事务的Linearizability，因为单个节点的时钟单调递增（这就是关键所在！）。如果事务T1 在启动事务T2之前提交, 那么事务T2 只能在以后提交。

在分布式数据库中，这套逻辑就不成立了。很容易就可以想到，如果系统中的节点具有不同步的时钟，那么两个有先后关系事务（译者注：原文为“causally-related transaction”。举个例子，假设A的账户扣款后，就会触发给B发一个短信，这是两个事务，但事务B又一定要在事务A之后执行，因为它们在外部逻辑上存在先后顺序关系，这就可以理解为“causally-related transacgtion”）的顺序很有可能就被颠倒过来了。

（译者注：！！重点！！这里是最重要的逻辑，大家一定要把这里弄懂，再看后面的内容才有意义。这里最核心的点是，Serializability是对于事务隔离级别的一致性保证，而Linearizability是对任何有顺序关系事务的一致性保证。所以时钟的差异就造成了影响，在单机库中，Serializability = Linearizability；分布式库中，Serializability < Linearizability。）

假设有两个节点，N1 和N2, 以及两个事务，T1 和T2，在N1和N2节点分别提交。因为我们没有全局唯一的时间来源，所以事务使用节点本地时钟来生成提交时间戳。为了说明这方面的棘手之处，我们假设N1节点有一个准确的本地时钟，但N2的本地时钟滞后100毫秒。事务T1先在N1上执行, 其在ts＝150ms时提交。50ms后（t=200ms时），外部观察者看到T1提交并由此启动T2（在N2节点上执行)。但因为N2的本地时钟滞后100ms，所以T2提交的时间为一个过去的时间，即ts=100ms。现在，我们在N1上读取和N2上读取将看到相反的顺序，T2的写入（ts=100ms）似乎发生在T1的写入之前（ts=150ms），尽管情况正好相反。这就麻烦了呀！（请注意，只有当两个事务访问一组不相交的key时，才会发生这种情况。）

（译者注：结合上面银行扣款的例子，就很好理解了。虽然在逻辑中是A的账户扣款后触发给B发短信，但因为分布式系统内不同步的时钟，表现为先给B发了短信，50ms后才对A进行扣款。这就是这里的问题所在。要强调的是，这里必须是两个没有重叠key的事务才会有这种问题，如果有重叠key，会有事务的锁机制或其他机制来干扰）

（译者注：再强调一遍，其实这段这么多内容就只是为了说明一件事：时钟的差异造成了影响，在单机库中，Serializability = Linearizability；分布式库中，Serializability < Linearizability。）

上面描述的“异常”，如图1所示，是我们称之为“顺序颠倒”的东西。虽然Spanner提供了Linearizability保证，但CockratchDB只声称可以Serializability，尽管在实践中有一些功能可以帮助弥补这一差距。我会（懒洋洋地）再次听从Andrei的话，他确实在这里占据了很多位置（译者注：指作者同事Andrei Matei写的有关CockroachDB一致性模型的另一篇文章，CockroachDB's consistency model。链接：https://www.cockroachlabs.com/blog/consistency-model/）。

未完待续...

关键词：