分布式数据库与时间 - 因果序和逻辑时钟

为什么全局时间是不可能的

在单台服务器上,每个事件都可以有唯一的时间戳,事件顺序是完全确定的。分布式系统放弃了这种便利。多个节点各自维护自己的时钟,网络延迟不可预测,因此判断两个事件哪个先发生从根本上就是困难的。这不是工程上的懒惰,而是物理分离系统的固有属性。

即使使用 NTP 同步,仍然存在毫秒到数十毫秒的偏差。如果事件 A 在节点 A 上发生于 12:00:00.005,事件 B 在节点 B 上发生于 12:00:00.008,在 NTP 的误差范围内实际顺序无法确定。这种不确定性从根本上挑战了分布式数据库中的事务一致性,该领域已经花了数十年开发变通方案。

Lamport 时钟 - 通过因果关系实现偏序

Leslie Lamport 1978 年提出的逻辑时钟通过追踪事件之间的因果关系 (happened-before 关系) 来排序,而不依赖物理时间。每个节点维护一个计数器,在本地事件时递增,将计数器附加到发出的消息中,在接收时更新为 max(本地值, 接收值) + 1。结果是即使没有时钟同步,也能产生尊重因果序的时间戳。

Lamport 时钟保证如果 A 导致了 B,那么 A 的时间戳小于 B 的。但反过来不成立:较小的时间戳并不意味着因果关系。系统无法区分并发事件和因果相关的事件。向量时钟正是为了克服这一限制而发明的,通过携带更多信息来解决问题。

向量时钟 - 检测并发

在一个 N 节点系统中,向量时钟将时间表示为 N 维向量,每个节点一个计数器。比较两个事件的向量可以判断一个是否发生在另一个之前 (一个向量在每个维度上都不小于另一个) 还是它们是并发的 (两者都不占优)。Amazon 的 Dynamo (2007 年论文) 使用向量时钟来检测写入冲突。

缺点是向量随集群增长。拥有数千个节点的系统需要在每条消息上附加数千个计数器,带宽和存储开销变得相当大。实际系统通过裁剪向量或切换到混合逻辑时钟等替代方案来避免这个扩展问题。

Google Spanner 的 TrueTime - 拥抱不确定性

Google 的 Spanner (2012) 采用了一种独特的方法,在其 API 中暴露物理时钟的不确定性。TrueTime API 返回当前时间作为一个区间 [最早, 最晚],而不是单一值。通过在每个数据中心安装 GPS 接收器和原子钟,Spanner 通常将不确定性控制在约 7 毫秒以内。

Spanner 的事务在提交前等待 TrueTime 不确定性区间过去 (commit-wait),从而保证外部一致性 (线性化)。在 7 毫秒不确定性下,每个事务增加 7 毫秒的等待。该设计用专用硬件 (GPS 加原子钟) 换取了其他系统难以匹敌的强分布式事务保证。

混合逻辑时钟 - 实用的折中方案

混合逻辑时钟 (HLC) 将物理时钟和逻辑时钟组合为单一时间戳对 (物理时间, 逻辑计数器)。正常情况下物理时间占主导,但在同一物理毫秒内的事件由逻辑计数器排序。CockroachDB 采用 HLC 来提供强一致性,而不需要专用硬件。

HLC 的吸引力在于它可以在普通的 NTP 同步服务器上工作,并产生接近人类可读物理时间的时间戳。它不及 Spanner 的严格性,但在 NTP 误差范围内通过重试解决不确定性窗口内的冲突,提供了实用的一致性。对于无法在数据中心安装 GPS 的大多数分布式数据库来说,HLC 是最合理的折中方案。