分布式存储漫游指南 5: 时间!!顺序!!

分布式系统的时钟和顺序，体现了相对论思想？让我们探索分布式系统的 “时钟” 与 “顺序”。

目录计划

• 分布式存储漫游指南 1: 2025年了，存储硬件啥样了？
• 分布式存储漫游指南 2: 单机磁盘 IO 的二三事 (同步 I/O 篇)
• 分布式存储漫游指南 3: 单机磁盘 IO 的二三事 (异步 I/O 篇)
• 分布式存储漫游指南 4: 分布式系统的混沌日常
• 分布式存储漫游指南 5: 时间!!顺序!!
• 分布式存储漫游指南 6: 复制和分区, 我变复杂了、但也可靠了
• 分布式存储漫游指南 7: 控制节点 —— 数据节点的管理、路由与迁移修复
• 分布式存储漫游指南 8: 元数据服务与垃圾回收 (GC)
• 分布式存储漫游指南 9: S3 协议, 对象存储的事实标准
• 分布式存储漫游指南 番外1: CDN, 其实我也是存储节点
• 分布式存储漫游指南 10: 容灾与跨区异步复制

1 引例：球赛与因果顺序

让我们考察一个现实世界的小引例。

QUIZ: 让我们试着对所有事件进行全局排序。

什么？你一定觉得这个挑战很简单，因为我们已经明确知道了每一个事件的准确发生事件！简直问了个寂寞！

但现实世界和分布式世界都是复杂的，不存在一个绝对精确、地球上任何角落都能一致的物理时钟。如果我们说 15:00 是赛事 APP 观测得到的，15:01 是 Tom 手机上观测得到的，我们还能如此自信的瞬间给出答案吗？

我们的手表时间可能会不准确，手机上的时间可能会偏移，时间的观测视角不同。我们只凭借 15:00 < 15:01，是无法判断出事件 A 先于事件 B 的。

但实际上，即使忽略所有的时间标签，仍然可以对上述事件进行排序 —— 通过因果关系分辨 “先发生” 的事件。球赛的结束必然是所有事件的初始，Tom 查询得到结果后才会去给 Jerry 打电话…… 以此类推，得到事件 A -> B -> C -> D -> E。

绝对时间是我们人类最基础的思维常识。但考虑和现实世界相似的分布式环境中，我们必须重新审视，尝试进入到逻辑时钟的世界。

这就是分布式系统的核心挑战之一：我们失去了一个绝对、可靠、全局可见的“现在”。 没有上帝视角的统一时钟，每个节点都活在自己对时间的感知里。“时间” 不再是简单读个数字，而是变成了一个需要精心设计和协商才能部分达成共识的复杂概念。理解这种 “时间困境” 是构建可靠、一致分布式系统的基石。

2 逻辑时钟 (Logical Clocks)

Lamport 在 1978年的重要论文¹明确指出了偏序关系(Partial Ordering) 和逻辑时钟(Logical Clocks)。

2.1 系统建模

对我们的分布式系统做如下抽象

• 系统由一组进程组成
• 每个进程由一系列事件构成
• 单个进程是有序的

图: 论文中的系统建模¹

先发生 (happened before) 的定义

1. 如果 (a) 和 (b) 是同一进程中的事件，且 (a) 在 (b) 之前发生，那么 (a \to b) 。
2. 如果 (a) 是一个进程发送一条消息， (b) 是另一个进程接收同一条消息，那么 (a \to b)。
3. 如果 (a \to b) 且 (b \to c)，那么 (a \to c)。如果 (a \nrightarrow b) 且 (b \nrightarrow a)，则称两个不同的事件 (a) 和 (b) 是并发的。

2.2 逻辑时钟

系统中开始引入逻辑时钟。这个逻辑时钟只是用于给每个事件分配一个数字。这个时钟和真实的物理时间之间，不做任何假设。

每个进程 (P_{i}) 都可以有自己的一个逻辑时钟 (C_{i})。这个逻辑时钟给事件分配数字 (C_{i}(a))。

我们定义如下的时钟条件：对于任何事件b，如果(a \to b)，那么(C{a} < C{b})。

但反过来显然是不成立的，因为我们没办法确定他们的顺序，或者说我们手中的信息不足以确定他们的顺序。在这个逻辑时钟下，认为其是并发关系。

实现以下约束：

• 同一进程中后发生的事件逻辑时间更大
• 发送方在进程的通信消息中携带自己的逻辑时间信息
• 接收方让自己的逻辑时钟永远比消息中的大

图: 论文中的逻辑 tick¹

则我们就可以将所有的时间划分为 tick。不同的 tick 之间便能够分辨全局逻辑次序。

3 物理时钟 (Physical Clocks)

论文指出，物理时钟仍然是必要的。逻辑时钟虽能对事件进行全序排序，但可能出现与用户感知的时间顺序冲突的 “异常行为”（如外部通信导致的事件先后关系未被系统识别）。物理时钟基于真实物理时间，可通过满足 “强时钟条件”（若事件 a 在物理上先于 b，则 a 的时钟值小于 b）避免此类异常。

那么问题来了，物理时钟虽然不能做到绝对精确，但需要精确到什么程度呢？

3.1 精度要求

Lamport 在论文中提出了如下要求

• 时钟运行速率需接近真实时间：存在常数 (\kappa)（远小于 1），确保时钟速率与真实时间速率的偏差不超过 (\kappa)（如晶体时钟 (\kappa \leq 10^{-6})）；
• 时钟同步精度需足够高：不同时钟的读数差异需小于常数 (\epsilon)，保证时间一致性。

3.2 同步算法

发送消息时附带发送方时钟的时间戳，接收方根据消息的最小延迟和时间戳调整自身时钟（确保不回拨），以满足同步要求。

Lamport 通过定理证明，在网络直径为 (d)、消息传输频率和延迟可控的情况下，物理时钟的最大偏差 (\epsilon) 可被界定为 (\approx d(2\kappa\tau+\xi))（其中 (\tau) 为消息发送间隔，(\xi) 为不可预测延迟），确保同步精度能避免异常行为。

3.3 理解和讨论

笔者在实际工作中是这么理解的：如果时钟的精度误差远远小于我们执行操作的时间粒度，那这个时钟就是可用的。

考虑一个数据传输导致的定序问题：

• OP A 在节点 1 上操作，OP B 在节点 2 上操作。
• OP A 在节点 1 记录的物理时间，比 OP B 在节点 2 记录的物理时间早了数个小时
• 节点 1,2 能够保证上的本地物理时间戳误差和偏移在秒级别

则我们就是可以认为 OP A 早于 OP B。

4 分布式事务与时间

分布式事务
什么场景定序和时间是极度重要的呢？分布式事务是其中之一。

分布式事务是指跨多个分布式节点（如多台数据库服务器、不同服务实例）的事务操作，需要保证这些分散在不同节点上的操作要么 “全部成功执行”，要么 “全部不执行”。

时间服务
事务的一致性高度依赖对 “操作顺序” 的准确判断。因此时间服务的设计。有了时间服务，我们才能保证事务的可见性和隔离性，比如下列设计目标：

• 一个事务的中间状态不能被其他事务看到
• 已提交事务必须被后续事务看到

备注：为每个操作定序是有代价的，应当根据系统设计目标选择合适的一致性和隔离级别。比如，在 PolarDB-X 的博客²中，提到本地域事务是保证外部一致性的，而跨地域不做保证。这种级别是业务可以接受的，减少了跨地域事务的时延。

5 案例分析

让我们分析两个分布式数据库的实际的工程用例。在 Spanner 和 TiKV 中，时间都在它们的分布式事务中扮演了重要角色。

5.1 Spanner 与 TrueTime

TrueTime 是 Google 分布式数据库 Spanner³ 中实现全局一致性的核心技术。思路是为分布式系统提供高精度、可验证的物理时间同步，从而解决了传统分布式系统中因时钟偏差导致的一致性难题。

TrueTime
TrueTime 是全球分布的原子钟和 GPS 接收器组成的时间服务，每个 Spanner 集群节点都能通过它获取当前时间的 “可信区间”。

调用 TT.now() 时，会得到一个时间区间 [earliest, latest]，表示 “真实物理时间一定在这个区间内”，这个精度是毫秒级别。

由于 TrueTime 部署在 Google 的全球的机房，跨地域不需要频繁协调就能拿到事务需要的时间。TrueTime 的思路从增强物理时钟的精确性来协助解决分布式数据库的一致性问题。

5.2 TiKV/TiDB 与 TSO

TSO 全称为中心授时(Timestamp Oracle)。TSO 由 TiKV 的控制节点 PD 分发。

图：TiDB 架构图⁴

TSO 是一个 int64 的整形，它由 physical time + logical time 两个部分组成。Physical time 是当前 unix time 的毫秒时间，而 logical time 则是一个最大 1 << 18 的计数器⁵。

• TSO 是一个全局的时间戳，它是 TiDB 实现分布式事务的基石
• 对于 PD，保证它能快速大量的为事务分配 TSO
• 保证分配的 TSO 一定是单调递增的，不可能出现回退
• PD 自身是一个 raft 组共识的三节点，成为 leader 的节点会持久化 tso 时间到 etcd。

客户端的每个 txn，都需要申请得到一个唯一的 tso 作为时间戳。写 txn 在提交时，还会申请一次 tso 作为提交时间，从而为读写 txn 的一致性和隔离性提供时钟前提。

tso 服务是否容易成为瓶颈，PD 对此进行了大量的工程优化。

因此，tikv 的思路便和 truetime 不同，是引入了集群内唯一的、权威的时间戳观测者，发放全局递增、唯一的时间戳，从而完成了事务定序。

6 小结

通过引例，我们了解了时钟和顺序是分布式系统重要基础。随即了解了逻辑时钟、物理时钟的概念。最终探索了实际的工程案例。

对数学定义和相关理论有兴趣的读者可参考 “继续阅读” 章节。

7 继续阅读

• 偏序关系和全序关系
• Lamport 时钟
• 向量时钟 (Vector Clock)
• Spanner 和 Percolator 的分布式事务原理
  • 尤其是其中因果定序的逻辑
• 偏序、全序与时空，现实世界是一个模拟世界？⁶

其他

1. 本文标题来自于 Lamport 在分布式领域的重要论文 Time, Clocks, and the Ordering of Events in a Distributed System ¹。论文直接指出了 Time, Clocks 和 Ordering 是分布式系统中的重要基础。
2. 共识算法 Paxos、排版系统 LaTex、形式化证明语言 TLA+ 都是 Lamport 的杰作。
3. 分布式事务是一个复杂的学术和工程主题，受限于笔者的背景和水平，有兴趣的读者可继续深入研究。