# 分布式时钟

![left](./student-guide/diagram/11-Clock-01-01.png)
-------------------------------------------------------------

在《A Critique of ANSI SQL Isolation Levels》论文中，提出了 Snapshot Isolation 的一般方案：
  1. 事务的读操作从 Committed 快照中读取数据，快照时间可以是事务的第一次读操作之前的任意时间，记为StartTimestamp。
  2. 事务准备提交时，获取一个CommitTimestamp，它需要比现存的StartTimestamp和CommitTimestamp都大。
  3. 事务提交时进行冲突检查，如果没有其它事务在[StartTS, CommitTS]区间内提交了与自己的 WriteSet 有交集的数据，则本事务可以提交；这里阻止了 Lost Update 异常。
  4. SI 允许事务用很旧的StartTS来执行，从而不被任何的写操作阻塞，或者读一个历史数据；当然，如果用一个很旧的CommitTS提交，大概率是会 Abort 的。

从上面的方案来看，核心都是需要一个递增序列号来实现 StartTS 和 CommitTS ，而分布式存储系统为了实现递增序列号通常有两种方案：全局发号器和时钟，由于在分布式系统中不存在绝对的时间一致，因此分化出两种方案：绝对时间 和 相对时间，其中绝对时间的方案主要是 Google 的 TrueTime 方案，而相对时间包含了物理时钟（Physical Clocks）、逻辑时钟（Logic Clocks）、向量时钟（Vector Clocks）、混合逻辑时钟（Hybrid Logic Clocks）等方案。

通常实现 Snapshot Isolation 的时钟方案有三大类：全局发号器方案、TrueTime 方案和混合逻辑时钟方案。其中，Percolator 和 TiDB 采用了全局发号器方案；Spanner 率先提出和使用了基于原子时钟和 GPS 构建的 TrueTime 方案；MongoDB、CockroachDB 和 YugaByteDB 采用了基于混合逻辑时钟方案。下表中简单列举了三种方案的典型实现：
  - TrueTime，TrueTime 是 Google Spanner 使用的方式，不过它需要硬件 GPS + 原子钟支持，外面要自己实现难度比较大。
  - HLC，HLC 是一种混合逻辑时钟，它使用 Physical Time 和 Logical Clock 来确定事件的先后顺序，HLC 已经在一些应用中使用，但 HLC 依赖 NTP，如果 NTP 精度误差比较大，很可能会影响 commit wait time，内网环境下误差在500ms以内。
  - TSO，TSO 是一个全局授时器，它直接使用一个单点服务来分配时间。TSO 的方式很简单，但会有单点故障问题，单点也可能会有性能问题。