分布式数据库中的一致性与时间戳

许多分布式系统中都有一致性和时间戳的概念，PolarDB-X 作为一款分布式关系型数据库，分布式一致性（Consistency）是其中极为重要的话题。今天这篇文章就来谈谈：什么是理想的一致性？以及如何让整个分布式系统具有这样一致性？

什么是一致性？

一致这个词在各种场景下都被赋予了不同的含义，在开始话题之前，我们先明确下今天要讨论的“一致性”是个什么含义。想象现在你有一个包含多个副本的数据库系统，为了简化模型，这里的数据库仅仅存储一个变量 X 的值，它所支持的操作只有两种：Write（向 X 写入新的值）和 Read（读取 X 的值）。

直觉上，如果 A 做了一次 Write，那么 B 做 Read 时必然要读到刚刚写入的值。但是作为懂并发编程的程序员，你知道这样的性质并非唾手可得。如果有多个线程访问同一个变量，那么我们需要将其声明为原子的（atomic），才能获得理想中的结果——线程 A 写入的值立即能被线程 B 读到。

现在，我们将上面的理想情况用更形式化的方式进行描述。无论是多么快的操作，它都必须会进行一段时间，而不是“一瞬间”。但可以确定的是，如果线程 A 的 Write 操作已经完成，在此之后去读 X，一定能读到 Write 之后的值：

但是如果 Write 和 Read 操作的时间存在哪怕一点点重叠，Read 的结果就不好说了，Read 可能看到 Write 之前的值，也可能看到 Write 之后的值，这是因为我们并不知道，最终在 CPU 的指令流水线上到底是哪一个请求先被执行了。下图中，Read 和 Write 操作发生的时间段是一模一样的，可以看出，无论 Read 读出 X = 1 还是 2 都可以说得通，都是正确的。

换用一种等价的说法，如果我们能为每个操作分配一个时间点（称为 Linearization Point），该时间点位于操作执行的时间段之内，在时间点上得到的执行结果和这些操作事实上的执行结果一致，那么该系统是强一致的，或者说线性一致性（Linearizabile）。

线性一致性的基本的想法是让一个系统看起来好像只有一个数据副本，而且所有的操作都是原子性的。有了这个保证，即使实际中可能有多个副本，应用也不需要担心它们的影响。

弱一致性

在分布式系统中，达到上述的一致性模型要比想象中更困难。举个例子，很多业务中使用了读写分离技术，让备库承担一部分的读请求以降低数据库主节点的压力。如果客户端向主库写入之后，立即从备库读取这条数据，很有可能读到旧的、写入之前的数据。这一模型下仅仅满足顺序一致性，而非上文说的线性一致性。

上面这张图来自 Jepsen 博客，其中 Strict Serializable 描述了最理想的一致性与隔离性，其中左边的子树表示隔离性级别（越往下越宽松），右边的子树表示一致性级别（越往下越宽松）。

数据库中，两种常见的一致性，分别是最终一致性和会话一致性。

最终一致性（Eventual Consistency） 用更直白的说法，它代表没有任何一致性保证。最终一致性的的代表是 Amazon Dynamo 以及它的开源对标产品 Apache Cassandra。没有一致性保证的系统并非一无是处，比如用户购物车、临时缓存等，放弃一致性也让这类系统有着极高的可用性保证。

对于关系型数据库，最终一致性是无法接受的，数据库的约束（例如唯一键）、二级索引的维护等等都要求一定的一致性保证。这也是为什么市面上的最终一致性数据库大多是 KV 数据库。

会话一致性（Session Consistency） 并不位于上面的图中，它是从客户端的角度定义的一致性级别。会话一致性要求一个会话本身看起来是强一致的，但是如果从上帝视角来看却并非如此。比如客户端 B 某一刻执行了 Write(x,2)，客户端 A 对此并不知情，它的 Read(x) 可能返回的依旧是 1 而非 2。但如果是 A 自身做的任何操作都不会出现这样的情况。

会话一致性在某些情况下是可以接受的，但是要举出 bad case 也十分容易，比如，当应用节点 A 写入数据之后，向应用节点 B 发送 RPC 服务调用，应用节点 B 可能无法立即读取到 A 写入的结果；或者，如果应用使用了连接池，不同的连接可能对应不同的数据库节点，可能换一个 Session 读到滞后的数据。

在 PolarDB-X 中，我们选择支持线性一致性而非上述这些弱一致性，其目的是让整个数据库看起来和一个单机数据库一样，不会因为分布式系统特有的一致性问题增加迁移成本。

分布式事务的一致性

说完一致性，现在开始考虑时间戳的问题。何为"时间戳"？

时间戳是一个通用的概念，其目的是为系统中的事件建立一个先后关系，在谈论这个概念是，我们并不关心写入的数据是什么，仅仅关心事件的先后顺序，时间戳越大表示事件的顺序越靠后。举个例子，一个读请求 Read(x) 到底应该读到怎样的数据，取决于 Write(x, v1)、Write(x, v2) 的时间戳为多少，

• 如果 Read(x) < Write(x, v1) < Write(x, v2) ，那么 Read(x) 应该读到空值
• 如果 Write(x, v1) < Read(x) < Write(x, v2) ，那么 Read(x) 应该读到 V1
• 如果 Write(x, v1) < Write(x, v2) < Read(x) ，那么 Read(x) 应该读到 V2

在数据库中，事务是最基本的操作单位，数据库的读和写都以事务的形式发生在系统中。为了简化起见，我们暂不讨论读写混合的事务，下面依旧使用 Read/Write 代表读取和写入的事务，读取事务需要指定读取的时间戳 $T_{read}$，写入事务（提交事务）也需要指定提交时间戳 $T_{commit}$，而 Read 能读到怎样的值就取决于 Write 的时间戳关系，就像上面的例子那样。

Lamport Clock

时间戳的抽象让我们能更专注于讨论一致性问题，所谓保证一致性，就是保证版本号的大小关系符合一致性的要求。真实系统还要负责将时间戳对应成真正的数据，但那已经超出了我们的讨论范围。

Lamport Clock 是最简单的时间戳实现，它用一个自增整数表示时间，记录事件的先后/因果关系（causality）：如果 A 事件导致了 B 事件，那么 A 的时间戳一定小于 B。当分布式系统的节点间传递消息时，消息会附带发送者的时间戳，而接收方总是用消息中的时间戳“推高”本地时间戳：$T_{local} = \max(T_{msg}, T_{local}) + 1$。

Lamport Clock 只是个从 0 开始增长的整数，为了让它更有意义，我们可以在它的高位存放物理时间戳、低位存放逻辑时间戳，当物理时间戳增加时逻辑位清零，这就是 HLC（Hybrid Logical Clock）。很显然，从大小关系的角度看，HLC 和 LC 并没有什么不同。

HLC/LC 并不满足线性一致性。我们可以构造出这样的场景，事务 A 和事务 B 发生在不相交的节点上，比如事务 $T_A$ 位于节点 1、事务 $T_B$ 位于节点 2，那么这种情况下 $T_A$、$T_B$ 的时间戳是彼此独立产生的，二者之前没有任何先后关系保证。具体来说，假设 $T_A$ 物理上先于 $T_B$ 提交，但是节点 2 上发起的 $T_B$ 的 snapshot_ts 可能滞后（偏小），因此无法读到 $T_A$ 写入的数据。

T1: w(C1)
T1: commit
T2: r(C2)   (假设 T2.read_ts < T1.commit_ts ，则无法读到 T1 的写入)

PolarDB-X 在选型时也认真考虑过是否要使用 HLC 作为默认的事务时间戳，但是最终还是因为缺少线性一致性而否定了这一提案。但是，在跨地域场景下我们部分采用了 HLC 的思想，具体做法我们会在之后的文章中介绍。

有限误差的 HLC

上个小节中介绍的 HLC 物理时间戳部分仅供观赏，并没有发挥实质性的作用。上面的 bad case 其根本原因是节点 1 和节点 2 上的有误差，所以 T2 读取了过期的数据。那能不能以某种方式去除这个时钟误差的干扰呢？

CockroachDB 要求所有数据库节点间的时钟偏移不能超过 250ms，后台线程会不断探测节点间的时钟偏移量，一旦超过阈值立即自杀。通过这种方式，节点间的时钟偏移量被限制在一个有限的范围内，即所谓的半同步时钟（semi-synchronized clocks）。

下面是最关键的部分：进行 Read 的过程中，一旦遇到 $T_{commit} $ 位于不确定性窗口 $[ T_{read}, T_{read} + max_clock_shift] $ 内的数据，则意味着无法确定这条记录到底是否可见，这时将会重启整个事务（并等待 max_clock_shift 过去），取一个新的 $T_{read}$ 进行读取。

有了这套额外的机制，上一节中的“写后读”场景下，可以保证读事务 $T_B$ 一定能读到 $T_A$ 的写入。具体来说，由于 $T_A$ 提交先于 $T_B$ 发起，$T_A$ 的写入时间戳一定小于 B.snapshot_ts + max_clock_shift，因此要么读到可见的结果（A.commit_ts < B.snapshot_ts），要么事务重启、用新的时间戳读到可见的结果。

那么，CockroachDB 是否满足可线性化呢？答案是否定的。Jepsen 的一篇测试报告中提到以下这个“双写”场景（其中，数据 C1、C2 位于不同节点上）：

                        T3: r(C1)      (C1 不存在)
T1: w(C1)
T1: commit
            T2: w(C2)
            T2: commit                 (假设由于时钟漂移导致 T2.commit_ts < T3.read_ts)
                        T3: r(C2)      (C2 存在)
                        T3: commit

虽然 T1 先于 T2 写入，但是 T3 却看到了 T2 而没有看到 T1，此时事务的表现等价于这样的串行执行序列：T2 -> T3 -> T1（因此符合可串行化），与物理顺序 T1 -> T2 不同，违反了可线性化。归根结底是因为 T1、T2 两个事务的时间戳由各自的节点独立产生，无法保证先后关系，而 Read Restart 机制只能防止数据存在的情况，对于这种尚不存在的数据（C1）就无能为力了。

Jepsen 对此总结为：CockroachDB 仅对单行事务保证可线性化，对于涉及多行的事务则无法保证。这样的一致性级别是否能满足业务需要呢？这个问题就留给读者判断吧。

TSO：集中式分配器

在分布式系统中，达到线性一致性是很困难的事情，上面的两种方案都没有达到线性一致性。TSO 方案则是放弃了去中心化，而是转而采用一个中心化的方案去处理时间戳问题。

TSO 全称为 Timestamp Oracle，这里的 Oracle 表示先知、神谕的本义，TSO 服务器负责给整个分布式集群的所有事务分配时间戳。

一旦回到单机系统中，事情变得明朗了很多。TSO 时间戳的正确性简单直接，上文我们说到，线性一致性可以定义为：如果我们能为每个操作找到这样一个时间点（这个时间点位于操作开始和结束的时间范围内），使得这些操作的结果和这些时间点上的结果符合，那么就满足线性一致性。

而在 TSO 时间戳中，TSO 作为一个单机节点，它很容易得地保证：所有分配的时间戳都与它们实际发生的物理顺序一致，其他节点只要保证调用 GetTimestamp RPC 发生在操作的时间范围内，那么 TSO 回应的时间戳就一定满足线性一致性的要求。

PolarDB-X 默认情况下采用 TSO 时间戳，事实证明 TSO 简单可靠，很大程度上简化了事务系统的设计，也给用户带来了“透明”的分布式数据库体验。

有读者可能会担心 TSO 称为集群扩展性的单点瓶颈，这个担心不无道理，但是实际中我们往往通过 Grouping 优化让分配时间戳的代价降的非常低，我们会在以后的文章中详细介绍我们 TSO 服务器的实现。

TrueTime：原子钟与GPS

TSO 的最大问题在于光速，光的传播需要时间，绕地球赤道一周需要 142ms，而实际的互联网中还有许多次转发和路由，数据包的传播还要比光慢的多。Google Spanner 是一个定位于全球部署的数据库，如果用 TSO 方案则需要横跨半个地球拿时间戳，这个延迟是无法接受的。但是 Google 认为线性一致性是必不可少的，于是发明了 TrueTime。

TrueTime 利用原子钟和 GPS 实现了时间戳的去中心化。但是原子钟和 GPS 提供的时间也是有误差的，在 Spanner 中这个误差范围 $\varepsilon$ 被设定为 7ms。换句话说，如果两个时间戳相差小于 $2\varepsilon$ ，我们就无法确定它们的物理先后顺序，称之为“不确定性窗口”。

Spanner 对此的处理方法也很简单——等待不确定性窗口时间过去。在事务提交过程中 Spanner 会做额外的等待（称为 Commit Wait），直到满足 $TT.now() - T_{start} > 2\varepsilon$，然后才将提交成功返回给客户端。在此之后，无论从哪里发起的读请求必然会拿到一个更大的时间戳，因而必然能读到刚刚的写入。

TrueTime 交出一个非常漂亮的答案，至少在全球部署这一项上达到了满分。但是另一方面，Commit Wait 也严重增加了事务延迟，并非所有业务都能接受；而 TrueTime 也是一个软硬结合的系统，对于其他公司，很难做到在每个机房安装维护这些硬件。

PolarDB-X 中的时间戳

PolarDB-X 2.0 目标是让用户透明地使用分布式数据库，因此在事务的技术选型上采用了中心化的 TSO 时间戳方案，提供强一致性（线性一致性）的保证。

PolarDB-X 中的 TSO 服务通过 Paxos 保证高可用，并且 TSO 的实现中通过 Grouping 等优化让 TSO 不会成为系统的性能瓶颈。而在跨地域场景中，我们借鉴了 Logical Clock/HLC 的思想，避免跨地域带来的网络延迟。在未来的文章中，我们会对这两个主题做更详尽的介绍，敬请期待。

References

1. Lamport timestamp - Wikipedia
2. Spanner: Google’s Globally-Distributed Database - OSDI’12 Presentation
3. Jepsen: CockroachDB beta-20160829
4. Living Without Atomic Clocks - Cockroach Labs
5. Consistency Models