Spanner Truetime

󰃭 2024-11-12

时间: TrueTime

书接上回, Lamport 老爷子的工作证明了用Wall Clock的可行性, 这回我们来看看工业界是如何基于Wall Clock来做serializable的.

2012 年 Google推出 Spanner的时候发布了 TrueTime API. 10多年后, AWS在re:Invent上介绍Xanadu时提到了Bounded Clock, 很明显是抄TrueTime的作业. 这也侧面印证了基于物理时间戳的快照隔离是真的香.

本文重点关注TrueTime的工作原理, SI(Snapshot Isolation)会是另一篇文章了.

理论工作

看过上篇博客关于论文前半部分的讨论之后我们已经知道, 分布式系统中的不同节点间是很难在时间上达成共识的. 每个节点的时钟都有误差, 读取自己的本地时间并仅不能产生全序,还会引发神经错乱. 逻辑时钟可以解决这个问题, 但一个系统总要和外部交互, 这又会带来因外部消息导致的因果关系错乱问题.

这次我们继续回到上篇文章的后半部分, 仔细看一下 Lamport 老爷子对于物理时钟需要满足条件的定义, 以及延申的定理.

要解决因外部事件导致的因果关系错乱, Lamport 引入了物理时钟. 但物理时钟也有它的固有问题:

  1. 分布式系统中不存在单一的权威时间源, 这会导致单点故障,性能瓶颈等问题. 且即使存在也会因权威授时本身忽快忽慢以及信息传播延迟的不确定性导致没法完全时间同步.
  2. 时钟漂移: 由于硬件差异, 环境等因素, 每个节点的时钟都以不同的速率在运行, 且这个速率本身也在不断变化. 装逼的说法就是一个时钟的一阶导数不为1, 且它的二阶导数不为0.

Lamport做出以下假设:

  1. 系统中消息传递的延迟是不确定的, 但存在一个已知的上限 $\delta$. 也就是说系统内任何消息的传播时间都不会超过 $\delta$
  2. 存在一个时钟漂移率的上限 $\rho$, 表示为时钟频率相对于理想时钟频率的最大偏差. 例如 $\rho=10^{-5}$ 表示理想时钟走过 $1s$ 后某个实际时钟的偏差最多是 $10^{-5}$. 如果某一时刻某个时钟 $C$ 和理想时间完全对齐, 则理想时钟 $T$ 过去 $1s$, $C$ 的时间会在 $[T+1-10^{-5}, T+1+10^{-5}]$ 之间.

此时, 系统中任意两节点间的最大时钟误差 $\epsilon$ 可以表示为:

$$\epsilon = \delta + 2 \rho T $$

也就是说,在最坏情况下:

  • 消息以最大延迟 $\delta$ 传播.
  • 两个时钟以相反方向发生时钟漂移偏离真实时间, 此时在距离上次时钟同步的时间间隔 $T$ 内, 因时钟漂移导致的误差最多为 $2 \rho T$

那如果两个事件的物理时间戳相隔的时间超过了最大误差 $\epsilon$, 我们就可以确定事件发生的顺序.

那现在工程上需要做的事情就很显而易见了. 为了提高分布式系统的整体性能, 我们需要保持一个较小的误差 $\epsilon$ 来尽快确定有因果关系的事件的顺序. 为了控制误差 $\epsilon$ 我们需要:

  1. 减小消息延迟 ($\delta$): 铺光缆, 搭专线, 优化网络性能, 最好在每个机房都放几个Time Master.
  2. 降低时钟漂移率 ($\rho$): 高精度原子钟! GPS接收器!
  3. 缩短时间同步间隔 ($T$): 更频繁的进行时间同步.

时钟同步

这里还存在一个问题, 就是刚才提到的对单个时钟的依赖. 为了解决这个问题, 一个机器在进行同步时会像多个服务器请求时间, 并在多个时间中选择一个最可信的时间. 这部分听上去很像 Network Time Protocol(NTP)对吧, 没错TrueTime本质上就是个高富帅版的NTP. Google 在每个数据中心都配置了若干带有GPS或原子钟的Time Master, 并搭配频繁的时间同步(每30s), 把时钟的平均误差缩小到了 $4ms$ NTP中涉及到的Marzullo算法本质上是一个 “Maximum number of overlapping Intervals” 问题. Marzullo算法的 “选择相信大多数时间服务器重叠的区间” 这个想法很符合直觉, 其背后的数学逻辑是最大似然估计(Maximum Likelihood Estimation).

TrueTime

API

  1. TT.now() 返回一个 TTinterval [earliest, latest];
  2. TT.after(t) 在时间 $t$ 一定过去了时返回True;
  3. TT.before(t) 在时间 $t$ 一定没到来时返回True.

事务序列化

这里先说两条规则:

  1. Start: 事务 $T_i$ 提交时, 事务的协调者必须要选择一个大于等于TT.now().latest的时间作为时间戳 $S_i$
  2. Commit Wait: 协调者必须在 TT.after(Si) 时才能提交数据.

举个例子:

有三台数据库实例 ${S_1,S_2,S_3}$, 他们各自的时钟相比真实时间$T$的offset分别是 ${+5, -4, -2 }$.

现在有一个事务 $T_1$, 参与者是 $S_1,S_2$:

  1. 在 $T=10$时 $S_1$的部分提交, 时间戳是 $C_{S_1} = 15$
  2. 在 $T=11$时 $S_2$的部分提交, 时间戳是 $C_{S_2} = 7$
  3. $S_2$作为协调者选择 $C_{S_1} = 15$ 作为整个事务的时间戳 $s_1$

还有另一个事务 $T_2$, 参与者是 $S_2,S_3$:

  1. 在 $T=15$时 $S_3$的部分提交, 时间戳是 $C_{S_3} = 13$
  2. 在 $T=16$时 $S_2$的部分提交, 时间戳是 $C_{S_2} = 12$
  3. $S_2$作为协调者选择 $C_{S_3} = 13$ 作为整个事务的时间戳 $s_2$

此时会发生在真实之间中更晚执行的 $T_2$ 提交却比 $T_1$ 早的错误.

有了TrueTime:

假设TrueTime的时钟误差 $\epsilon$ 为 7ms, 也就是论文中提到的最大误差.

$S_2$ 在提交 $T_1$ 时:

  1. 根据 Start 规则, 选择事务参与者中最大的时间戳, 与协调者自身的 TT.now().latest 中的最大值. 即 $s_1 = max(15, 7+7) = 15$
  2. 根据 Commit Wait 规则等待 $s_1$ 成为过去, 即等待 TT.after(15) 为 True 后再提交数据. 也就是说当 $S_2$ 调用 TT.now() 得到 $[ 16, 30 ]$时, $S_2$的本地时间是 $23$, 提交的绝对时间是 $27$.

$S_2$ 在提交 $T_2$ 时:

  1. 根据 Start 规则, 选择事务参与者中最大的时间戳, 与协调者自身的 TT.now().latest 中的最大值. 即 $s_2 = max(13, 12+7) = 19$
  2. 根据 Commit Wait 规则等待 $s_2$ 成为过去, 即等待 TT.after(19) 为 True 后再提交数据. 也就是说当 $S_2$ 调用 TT.now() 得到 $[ 20, 34 ]$时, $S_2$的本地时间是 $27$, 提交的绝对时间是 $31$.

此时, 我们就可以保证对涉及到同一数据修改的事务的序列化. 论文中给出的平均误差是 4ms, 且一次事务需要等待过去两个误差, 平均每个事务的等待时间是 8ms. 那就是说对于同一数据的事务并发量是 $125/s$.