分布式系统的时间

103次阅读

共计 3817 个字符，预计需要花费 10 分钟才能阅读完成。

大家都知道，Linearizability 在一些系统（譬如分布式数据库）里面是非常重要的，我们不能允许数据更新之后仍然能读到原先的值，譬如银行转账，用户 A 有 100 元，转给用户 B 10 元，这个操作之后用户 A 只可能有 90 元了，但如果 A 后续发起了另一个转账请求给 C 转 10 元的时候，事务里面读到 A 的余额仍然是 100 元，这个问题就大了。

一个更简化的说明，假设在某个时间点 t 我们写入了一条数据，譬如set a = 10，那么在 t 之后，所有的 read a 读到的都应该是 10，而不是 a 以前的值。

那么，我们如何确定 read a 读到的一定是最新的数据呢？在一个系统里面，如果一个事件 a 发生在另一个事件 b 的前面，我们就可以认为 a happended before b, 可以用 a -> b 来表示。

如果 a 和 b 是在同一个进程里面执行，（注：这里我们假定进程是顺序执行 event 的），那么我们可以很容易的就知道 a 在 b 之前发生，因为 a 在进程里面是先执行的。

但在分布式系统里面，a 和 b 可能在不同的进程里面（当然这两个进程一定会相互通讯），这件事情就不是特别容易判断了，我们得找到一个基准用来衡量到底谁先谁后。

我们首先就想到的是时间，我们只要知道 a 和 b 发生的时间就能够知道先后顺序了，但是我们都知道，每台机器的时间都不是一致的，虽然能通过 NTP 协议进行相互校对，但总有误差。所以我们不能直接使用系统时间来判断事件的先后顺序。

Lamport（这个大牛就不用多介绍了）在上世纪 70 年代，就提出了使用 Logic Clock 来确定事件的先后顺序。

我们可以认为 Logic Clock 就是一个不断增长的 number，假设两个进程 P1 和 P2，两个事件 a 和 b，我们用 C(a)，C(b)来表示这两个事件的 logic clock。

如果 a 和 b 都是在 P1 里面发生，如果 a -> b，那么我们一定可以知道 C(a) < C(b)。

现在复杂的是 a 在 P1 里面发生，但 b 在 P2 里面发生，首先我们需要明确 P1 和 P2 一定能够相互通讯，a 发生之后，P1 会给 P2 发送相关消息，同时会带上 C(a)，P2 接受到这个消息之后再处理 b，因为 P2 明确知道这个消息是从 P1 发过来的，如果 P2 当前的 clock 为 C(old)并且小于或者等于 C(a)，那么会将自己的 clock 更新为大于 C(a)的任意值，不过通常就是 C(a) + 1 了，这时候在执行 b，我们就一定能知道 C(b) > C(a)了。

当然，上面 a 和 b 必须是相关的事件，也就是 a -> b，如果 a 和 b 是独立的，那么 P1 和 P2 就不需要进行相关的交互了。

可以看到，Logic Vector 的原理是非常简单的，但是它因为没有实际的物理时间概念，所以如果我们想根据某一个真实的时间来查询相关事件，这个办不到了。

在 Logic Clock 之后，人们又引入了 Vector Clock，但 vector clock 也有 logic clock 同样的问题，不能依据真实的时间来查询，这里就不多介绍 vector clock 了。

前面我们说了，NTP 是有误差的，而且 NTP 还可能出现时间回退的情况，所以我们不能直接依赖 NTP 来确定一个事件发生的时间。在 Google Spanner 里面，通过引入 True Time 来解决了分布式时间问题。

Spanner 通过使用 GPS + Atomic Clock 来对集群的机器进行校时，精度误差范围能控制在 ms 级别，通过提供一套 TrueTime API 给外面使用。

TrueTime API 很简单，只有三个函数:

Method	Return
TT.now()	TTinterval: [earliest, latest]
TT.after(t)	true if t has definitely passed
TT.before(t)	true if t has definitely not arrived

首先 now 得到当前的一个时间区间，spanner 不能得到精确的一个时间点，只能得到一段区间，但这个区间误差范围很小，也就是 ms 级别，我们用 ε 来表示，也就是 [t – ε, t + ε] 这个范围，

假设事件 a 发生绝对时间为 tt.a，那么我们只能知道 tt.a.earliest <= tt.a <= tt.a.latest, 所以对于另一个事件 b，只要 tt.b.earliest > tt.a.latest，我们就能确定 b 一定是在 a 之后发生的，也就是说，我们需要等待大概 2ε 的事件才能去提交 b，这个就是 spanner 里面说的 commit wait time。

可以看到，虽然 spanner 引入了 TrueTime 可以得到全球范围的时序一致性，但相关事务在提交的时候会有一个 wait 时间，只是这个时间很短，而且 spanner 后续都准备将其优化到 ε < 1ms，也就是对于关联事务，仅仅在上一个事务 commit 之后等待 2ms 之后就能执行，性能还是很强悍的。

但 spanner 有一个最大的问题，TrueTime 是基于硬件的，而现在对于很多企业来说，是没有办法搞定这套部署的。所以如果 Google 能将 TrueTime 的硬件设计开源，那我觉得更加造福社区了。

既然 TrueTime 这种硬件方案很多人搞不定，那么我们就采用软件方案了。

Cockroachdb 使用了 Hybrid Logic Clock（HLC）来解决分布式时间的问题。

HLC 是基于 NTP 的，但它只会读取当前系统时间，而不会去修改，同时 HLC 又能保证在 NTP 出现同步问题的时候仍能够很好的进行容错处理。对于一个 HLC 的时间 t 来时，它总是大于等于当前的系统时间，并且与其在一个很小的误差范围里面，也就是 |l – pt| < ε。

HLC 由两部分组成，physical clock + logic clock，l.j 维护的是节点 j 当前已知的最大的物理时间，c.j 则是当前的逻辑时间。那么判断两个事件的先后顺序就很容易了，先判断物理时间 pt，在判断逻辑时间 ct。

HLC 的算法如下，在节点 j 上面：

初始化: l.j = 0, c.j = 0

给另一个进程发送或者处理自己的事件：

  l'.j = l.j;
  // 跟当前系统时间比较，得到 pt
  l.j = max(l'j, pt.j)
  // 如果 pt 没有变化，则 c.j 加 1，如果有变化，因为这时候
  // 铁定 PT 变大了，所以我们可以将 ct 清零
  if (l.j = l'.j) {c.j = c.j + 1} else {c.j = 0}

  // Timestamp with l.j, c.j

接受某一个节点 m 的消息事件

  l'.j = l.j;
  // 跟当前系统事件以及节点 m 的 pt 比较，得到 pt
  l.j = max(l'.j, l.m, pt.j)
  if (l.j = l'.j = l.m) {
      // pt 一样，获取最大的 ct，并加 1
      c.j = max(c.j, c.m) + 1
  } else if (l.j = l'j) {
      // 这里表明 j 原来的 pt 比 m 大，只需要增加 ct
     c.j = c.j + 1
  } else if (l.j = l.m) {
      // 这里表明 m 的 pt 比 j 原来的要大，所以直接可以用 m 的 ct + 1
      c.j = c.m + 1
  } else {
      // pt 变化了，ct 清零
      c.j = 0
  }

  // Timestamp with l.j, c.j

具体的实现算法，可以看 cockroachdb 的 HLC 实现。

HLC 虽然方便，它毕竟是基于 NTP 的，所以如果 NTP 出现了问题，可能导致 HLC 与当前系统 pt 的时间误差过大，其实已经不怎么精确了，HLC 论文提到对于一些 out of bounds 的 message 可以直接忽略，然后加个 log 让人工后续处理，而 cockroachdb 是直接打印了一个 warning log。

无论上面的 Ture Time 还是 Hybrid Logic Time，都是为了在分布式情况下获取全局唯一时间，如果我们整个系统不复杂，而且没有 spanner 那种跨全球的需求，有时候一台中心授时服务没准就可以了。

在 Google Percolator 系统这，他们就提到使用了一个 timestamp oracle（TSO）的服务来提供统一的授时服务，为啥叫 oracle，我猜想可能底层用的就是 oracle 数据库。。。

使用 TSO 的好处在于因为只有一个中心授时，所以我们一定能确定所有时间的时间，但 TSO 需要关注几个问题：

网络延时，因为所有的事件都需要从 TSO 获取时间，所以 TSO 的场景通常都是小集群，不能是那种全球级别的数据库。
性能，TSO 是一个非常高频的操作，但鉴于它只干一件事情，就是授时，通常一个 TSO 每秒都能支持 10w+ 以上的 QPS，而这个对很多应用来说是绰绰有余的。
容错，TSO 是一个单点，所以不得不考虑容错，而这个现在基于 zookeeper，etcd 也不是特别困难的事情。

所以，如果我们没法实现 TrueTime，同时又觉得 HLC 太复杂，但又想获取全局时间，TSO 没准是一个很好的选择，因为它足够简单高效。

我们现在的数据库产品就使用的是 TSO 方案，但也不排除以后为了支持全球同步，而考虑使用 TureTime 或者 HLC 的方案。

在分布式领域，我们很自然的会想到用时间来解决事件的时序问题，但如何保证时间的获取是全局一致并且正确的，并不是一件容易的事情，笔者认为，只要能搞定时间问题，后面编写 Linearizability 的系统就比较容易了。当然，如果我们还需要支持分布式事务，还有更多的事情需要考虑的，如果后面有时间，在慢慢总结吧。

本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-10/148143.htm

正文完

星哥说事-微信公众号