关于java:分布式事务中的时间戳老大难了…

本文作者：Eric Fu

本文链接：https://ericfu.me/timestamp-i…

工夫戳（timestamp）是分布式事务中绕不开的重要概念，有意思的是，当初支流的几个分布式数据库对它的实现都不尽相同，甚至是次要辨别点之一。

本文聊一聊工夫戳的前世今生，为了把探讨集中在主题上，假如读者曾经对数据库的 MVCC、2PC、一致性、隔离级别等概念有个根本的理解。

为什么须要工夫戳？

自从 MVCC 被创造进去之后，那个时代的简直所有数据库都摈弃（或局部摈弃）了两阶段锁的并发管制办法，起因无它——性能太差了。当分布式数据库逐步衰亡时，设计者们简直都抉择 MVCC 作为并发管制计划。

MVCC 的全称是多版本并发管制（Multi-Version Concurrency Control），这个名字仿佛暗示咱们肯定会有个版本号（工夫戳）存在。然而事实上，工夫戳还真不是必须的。MySQL 的 ReadView 实现就是基于事务 ID 大小以及沉闷事务列表进行可见性判断。

事务 ID 在事务开启时调配，体现了事务 begin 的程序；提交工夫戳 commit_ts 在事务提交时调配，体现了事务 commit 的程序。

分布式数据库 Postgres-XL 也用了同样的计划，只是将这套逻辑放在全局事务管理器（GTM）中，由 GTM 集中式地保护集群中所有事务状态，并为各个事务生成它们的 Snapshot。这种中心化的设计很容易呈现性能瓶颈，制约了集群的扩展性。

另一套计划就是引入工夫戳，只有比拟数据的写入工夫戳（即写入该数据的事务的提交工夫戳）和 Snapshot 的读工夫戳，即可判断出可见性。在单机数据库中产生工夫戳很简略，用原子自增的整数就能以很高的性能调配工夫戳。Oracle 用的就是这个计划。

MVCC 原理示意：比拟 Snapshot 读取工夫戳和数据上的写入工夫戳，其中最大但不超过读工夫戳的版本，即为可见的版本

而在分布式数据库中，最间接的代替计划是引入一个集中式的分配器，称为 TSO（Timestamp Oracle，此 Oracle 非彼 Oracle），由 TSO 提供枯燥递增的工夫戳。TSO 看似还是个单点，然而思考到各个节点取工夫戳能够批量（一次取 K 个），即使集群的负载很高，对 TSO 也不会造成很大的压力。TiDB 用的就是这套计划。

MVCC 和 Snapshot Isolation 有什么区别？前者是侧重于形容数据库的并发管制 实现 ，后者从隔离级别的角度定义了一种 语义。本文中咱们不辨别这两个概念。

可线性化

可线性化 （linearizable）或 线性一致性 意味着操作的时序和（内部观察者所看到的）物理工夫统一，因而有时也称为 内部一致性。具体来说，可线性化假如读写操作都须要执行一段时间，然而在这段时间内必然能找出一个工夫点，对应操作真正“产生”的时刻。

线性一致性的解释。其中 (a)、(b) 满足线性一致性，因为如图所示的时间轴即能解释线程 A、B 的行为；(c) 是不容许的，无论如何 A 都该当看到 B 的写入

留神不要把一致性和隔离级别一概而论，这齐全是不同维度的概念。现实状况下的数据库应该满足 strict serializability，即隔离级别做到 serializable、一致性做到 linearizabile。本文次要关注一致性。

TSO 工夫戳可能提供线性一致性保障。残缺的证实超出了本文的领域，这里只说说直觉的解释：用于判断可见性的 snapshot_ts 和 commit_ts 都是来自于集群中惟一的 TSO，而 TSO 作为一个单点，可能确保工夫戳的程序关系与调配工夫戳的物理时序统一。

可线性化是一个极好的个性，用户齐全不必思考一致性方面的问题，然而代价是必须引入一个中心化的 TSO。咱们后边会看到，想在去中心化的状况下放弃可线性化是极为艰难的。

TrueTime

Google Spanner 是一个定位于寰球部署的数据库。如果用 TSO 计划则须要横跨半个地球拿工夫戳，这个提早可能就奔着秒级去了。然而 Google 的工程师认为 linearizable 是必不可少的，这就有了 TrueTime。

TrueTime 利用原子钟和 GPS 实现了工夫戳的去中心化。然而原子钟和 GPS 提供的工夫也是有误差的，在 Spanner 中这个误差范畴 εε 被设定为 7ms。换句话说，如果两个工夫戳相差小于 2ε2ε，咱们就无奈确定它们的物理先后顺序，称之为“不确定性窗口”。

Spanner 对此的解决办法也很简略——期待不确定性窗口工夫过来。

在事务提交过程中 Spanner 会做额定的期待，直到满足 TT.now()−Tstart>2εTT.now()−Tstart>2ε，而后才将提交胜利返回给客户端。在此之后，无论从哪里发动的读申请必然会拿到一个更大的工夫戳，因此必然能读到刚刚的写入。

Lamport 时钟与 HLC

Lamport 时钟是最简略的逻辑时钟（Logical Clock）实现，它用一个整数示意工夫，记录事件的先后 / 因果关系（causality）：如果 A 事件导致了 B 事件，那么 A 的工夫戳肯定小于 B。

当分布式系统的节点间传递音讯时，音讯会附带发送者的工夫戳，而接管方总是用音讯中的工夫戳“推高”本地工夫戳：Tlocal=max(Tmsg,Tlocal)+1Tlocal=max(Tmsg,Tlocal)+1。

Lamport Clock 只是个从 0 开始增长的整数，为了让它更有意义，咱们能够在它的高位寄存物理工夫戳、低位寄存逻辑工夫戳，当物理工夫戳减少时逻辑位清零，这就是 HLC（Hybrid Logical Clock）。很显然，从大小关系的角度看，HLC 和 LC 并没有什么不同。

HLC/LC 也能够用在分布式事务中，咱们将工夫戳附加到所有事务相干的 RPC 中，也就是 Begin、Prepare 和 Commit 这几个音讯中：

• Begin：取本地工夫戳 local_ts 作为事务读工夫戳 snapshot_ts
• Snapshot Read: 用 snapshot_ts 读取其余节点数据（MVCC）
• Prepare：收集所有事务参与者的以后工夫戳，记作 prepare_ts
• Commit：计算推高后的本地工夫戳，即 commit_ts = max{prepare_ts} + 1

HLC/LC 并不满足线性一致性。咱们能够结构出这样的场景，事务 A 和事务 B 产生在不相交的节点上，比方事务 TATA 位于节点 1、事务 TBTB 位于节点 2，那么这种状况下 TATA、TBTB 的工夫戳是彼此独立产生的，二者之前没有任何先后关系保障。具体来说，假如 TATA 物理上先于 TBTB 提交，然而节点 2 上发动的 TBTB 的 snapshot_ts 可能滞后（偏小），因而无奈读到 TATA 写入的数据。

T1: w(C1)
T1: commit
T2: r(C2)   (not visible! assuming T2.snapshot_ts < T1.commit_ts)

HLC/LC 满足因果一致性（Causal Consistency）或 Session 一致性，然而对于数据库来说这并不足以满足用户需要。设想一个场景：应用程序中应用了连接池，它有可能先用 Session A 提交事务 TATA（用户注册），再用 Session B 进行事务 TBTB（下订单），然而 TBTB 却查不到下单用户的记录。

如果连接池的例子不能压服你，能够设想一下：微服务节点 A 负责用户注册，之后它向微服务节点 B 发送音讯，告诉节点 B 进行下订单，此时 B 却查不到这条用户的记录。基本问题在于利用无奈感知数据库的工夫戳，如果利用也能向数据库一样在 RPC 调用时传递工夫戳，或者因果一致性就够用了。

无限误差的 HLC

上个大节中介绍的 HLC 物理工夫戳局部仅供参观，并没有施展实质性的作用。CockroachDB 创造性地引入了 NTP 对时协定。NTP 的精度当然远远不如原子钟，误差大概在 100ms 到 250ms 之间，如此大的误差下如果再套用 TrueTime 的做法，事务提早会高到无奈承受。

CockroachDB 要求所有数据库节点间的时钟偏移不能超过 250ms，后盾线程会一直探测节点间的时钟偏移量，一旦超过阈值立刻他杀。通过这种形式，节点间的时钟偏移量被限度在一个无限的范畴内，即所谓的 半同步时钟（semi-synchronized clocks）。

上面是最要害的局部：进行 Snapshot Read 的过程中，一旦遇到 commit_ts 位于不确定性窗口 [snapshot_ts, snapshot_ts + max_clock_shift] 内的数据，则意味着无奈确定这条记录到底是否可见，这时将会 重启整个事务（并期待 max_clock_shift 过来），取一个新的 snapshot_ts 进行读取。

有了这套额定的机制，上一节中的“写后读”场景下，能够保障读事务 TBTB 肯定能读到 TATA 的写入。具体来说，因为 TATA 提交先于 TBTB 发动，TATA 的写入工夫戳肯定小于 B.snapshot_ts + max_clock_shift，因而要么读到可见的后果（A.commit_ts < B.snapshot_ts），要么事务重启、用新的工夫戳读到可见的后果。

那么，CockroachDB 是否满足可线性化呢？答案是否定的。Jepsen 的一篇测试报告中提到以下这个“双写”场景（其中，数据 C1、C2 位于不同节点上）：

                        T3: r(C1)      (not found)
T1: w(C1)
T1: commit
            T2: w(C2)
            T2: commit                 (assuming T2.commit_ts < T3.snapshot_ts due to clock shift)
                        T3: r(C2)      (found)
                        T3: commit

尽管 T1 先于 T2 写入，然而 T3 却看到了 T2 而没有看到 T1，此时事务的体现等价于这样的串行执行序列：T2 -> T3 -> T1（因而合乎可串行化），与物理程序 T1 -> T2 不同，违反了可线性化。归根结底是因为 T1、T2 两个事务的工夫戳 由各自的节点独立产生，无奈保障先后关系 ，而 Read Restart 机制只能避免数据 存在 的状况，对于这种尚不存在的数据（C1）就无能为力了。

Jepsen 对此总结为：CockroachDB 仅对单行事务保障可线性化，对于波及多行的事务则无奈保障。这样的一致性级别是否能满足业务须要呢？这个问题就留给读者判断吧。

联合 TSO 与 HLC

最近看到 TiDB 的 Async Commit 设计文档 引起了我的趣味。Async Commit 的设计动机是为了升高提交提早，在 TiDB 本来的 Percolator 2PC 实现中，须要通过以下 4 个步骤：

1. Prewrite：将 buffer 的批改写入 TiKV 中
2. 从 TSO 获取提交工夫戳 commit_ts
3. Commit Primary Key
4. Commit 其余 Key（异步进行）

为了升高提交提早，咱们心愿将第 3 步也异步化。然而第 2 步中获取的 commit_ts 须要由第 3 步来保障长久化，否则一旦协调者在 2、3 步之间宕机，事务复原时就不晓得用什么 commit_ts 持续提交（roll forward）。为了避开这个麻烦的问题，设计文档对 TSO 工夫戳模型的事务提交局部做了批改，引入 HLC 的提交办法：

• Prewrite

  1. TiDB 向各参加事务的 TiKV 节点收回 Prewrite 申请
  2. TiKV 长久化 Prewrite 的数据以及 min_commit_ts，其中 min_commit_ts = 本地最大工夫戳 max_ts
  3. TiKV 返回 Prewrite 胜利音讯，蕴含刚刚的 min_commit_ts

• Finalize

  （异步）：计算 commit_ts = max{min_commit_ts}，用该工夫戳进行提交

  1. Commit Primary Key
  2. Commit 其余 Key

上述流程和 HLC 提交流程根本是一样的。留神，事务开始时依然是从 TSO 获取 snapshot_ts，这一点保持原状。

咱们尝试代入上一节的“双写”场景发现：因为依赖 TSO 提供的 snapshot_ts，T1、T2 的工夫戳仍然能保障正确的先后关系，然而只有稍作批改，即可结构出失败场景（这里假如 snapshot_ts 在事务 begin 时获取）：

T1: begin   T2: begin   T3: begin       (concurrently)
T1: w(C1)
T1: commit                              (assuming commit_ts = 105)
            T2: w(C2)
            T2: commit                  (assuming commit_ts = 103)
                        T3: r(C1)       (not found)
                        T3: r(C2)       (found)
                        T3: commit

尽管 T1 先于 T2 写入，但 T2 的提交工夫戳却小于 T1，于是，并发的读事务 T3 看到了 T2 而没有看到 T1，违反了可线性化。根本原因和 CockroachDB 一样：T1、T2 两个事务的提交工夫戳由各自节点计算得出，无奈确保先后关系。

Async Commit Done Right

上个大节给出的 Async Commit 计划毁坏了本来 TSO 工夫戳的线性一致性（尽管仅仅是个十分边缘的场景）。这里特别感谢 @Zhifeng Hu 的揭示，在 #8589 中给出了一个奇妙的解决方案：引入 prewrite_ts 工夫戳，即可让并发事务的 commit_ts 从新变得有序。残缺流程如下，留神 Prewrite 的第 1、2 步：

• Prewrite

  1. TiDB 从 TSO 获取一个 prewrite_ts，附带在其中一个 Prewrite 申请上发送给 TiKV
  2. TiKV 用 prewrite_ts（如果收到的话）推高本地最大工夫戳 max_ts
  3. TiKV 长久化 Prewrite 的数据以及 min_commit_ts = max_ts
  4. TiKV 返回 Prewrite 胜利音讯，蕴含刚刚的 min_commit_ts

• Finalize

  （异步）：计算 commit_ts = max{min_commit_ts}，用该工夫戳进行提交

  1. Commit Primary Key
  2. Commit 其余 Key

对应到下面的用例中，当初 T1、T2 两个事务的提交工夫戳不再是独立计算，依附 TSO 提供的 prewrite_ts 能够构建出 T1、T2 的正确程序：T2.commit_ts >= T2.prewrite_ts > T1.commit_ts，从而防止了上述异样。

更进一步，该计划可能满足线性一致性 。这里只给一个直觉的解释：咱们将 TSO 看作是内部物理工夫，依附 prewrite_ts 能够保障 commit_ts 的取值位于 commit 申请 开始之后 ，而通过本地 max_ts 计算出的 commit_ts 肯定在 commit 申请 完结之前，故 commit_ts 取值落在执行提交申请的工夫范畴内，满足线性一致性。

总结

1. 上述已知的工夫戳计划中，仅有 TSO 和 TrueTime 可能保障线性一致性；
2. Logical Clock 计划仅能保障 Session 一致性；
3. Cockroach 的 HLC 计划仅能保障行级线性一致性，不保障多行事务的线性一致性；
4. TiDB Async Commit 通过引入 Prewrite 工夫戳放弃了内部一致性；但如果去掉 Prewrite 工夫戳、应用 HLC 的提交形式，则不保障多行的并发事务的线性一致性。

另外，关注公众号 Java 技术栈，在后盾回复：面试，能够获取我整顿的 Java/ 分布式系列面试题和答案，十分齐全。

References

1. https://en.wikipedia.org/wiki…
2. https://www.slideshare.net/jo…
3. https://jepsen.io/analyses/co…
4. https://www.cockroachlabs.com…
5. https://sergeiturukin.com/201…
6. https://github.com/tikv/sig-t…
7. https://github.com/tikv/tikv/…

近期热文举荐：

1.600+ 道 Java 面试题及答案整顿(2021 最新版)

2. 终于靠开源我的项目弄到 IntelliJ IDEA 激活码了，真香！

3. 阿里 Mock 工具正式开源，干掉市面上所有 Mock 工具！

4.Spring Cloud 2020.0.0 正式公布，全新颠覆性版本！

5.《Java 开发手册（嵩山版）》最新公布，速速下载！

感觉不错，别忘了顺手点赞 + 转发哦！