来源：
()是分布式事务中绕不开的一个重要概念，但有趣的是几个主流分布式数据库对它都有不同的实现，甚至是主要区别点之一。 本文讲述时间戳的前世今生。 为了使讨论集中在主题上，假设读者对数据库的MVCC、2PC、一致性和隔离级别的概念有基本的了解。
为什么需要时间戳？
自从MVCC发明以来，那个时代的几乎所有数据库都放弃了（或者部分放弃）两阶段锁的并发控制方式，原因无他——性能太差。 当分布式数据库逐渐兴起时，设计者几乎都选择MVCC作为并发控制方案。
并发控制的几种方法
MVCC的全称是多版本并发控制（Multi-）。 这个名字似乎暗示我们必须有一个版本号（时间戳）。 然而事实上，时间戳确实没有必要。 MySQL的实现是根据事务ID大小和活跃事务列表进行可见性判断。
事务ID在事务启动时分配，反映事务开始的顺序； 提交时间戳是在事务提交时分配的，反映了事务的顺序。
分布式数据库-XL也采用了同样的方案，只不过把这套逻辑放在全局事务管理器（GTM）中，GTM集中维护集群中所有事务的状态，并为每个事务生成状态。 这种集中式的设计很容易出现性能瓶颈，从而限制了集群的可扩展性。
另一个解决方案是引入时间戳。 通过比较数据的写入时间戳（即写入数据的事务的提交时间戳）和数据的读取时间戳，可以判断可见性。 在独立数据库中生成时间戳很简单，使用原子递增的整数来高性能地分配时间戳。 这是使用的计划。
MVCC原理图解：比较数据上的读时间戳和写时间戳，最大但不超过读时间戳的版本为可见版本
在分布式数据库中，最直接的替代方案是引入一个集中式分配器，称为TSO（这不是另一个），TSO提供单调递增的时间戳。 TSO看似是单点，但考虑到每个节点可以批量（一次K个）取时间戳，即使集群的负载很高，也不会对TSO造成很大的压力。 TiDB 采用了这种解决方案。
MVCC 和 有什么区别？ 前者侧重于描述数据库的并发控制实现，而后者则从隔离级别的角度定义了一种语义。 在本文中我们不区分这两个概念。
线性化
线性化（）或线性一致性意味着操作的时间与物理时间（如外部观察者所看到的）一致，因此有时被称为外部一致性。 注意不要将一致性与隔离级别混淆，它们是不同维度的概念。 理想情况下，数据库应该满足要求，即达到隔离级别和一致性。 本文重点关注一致性。
隔离性（）与一致性（）
这里直接得出结论：TSO时间戳可以提供线性一致性保证。 完整的证明超出了本文的范围，这里只是一个直观的解释：用于判断可见性的和来自集群中唯一的TSO，而TSO作为单点可以保证时间戳的顺序关系和分布时间戳的物理时序是一致的。
线性化是一个优秀的特性，用户根本不需要考虑一致性问题，但代价是必须引入中心化的TSO。 正如我们稍后将看到的，通过去中心化来维持线性化是极其困难的。
它是一个面向全球部署的数据库。 如果使用TSO解决方案，则需要获取跨越半个世界的时间戳，而这个延迟可能是秒级的。 但一些工程师认为这是必要的，而且就是这样。
分散式时间戳是使用原子钟和 GPS 实现的。 但原子钟和GPS提供的时间也存在误差，本文将误差范围εε设置为7ms。 换句话说，如果两个时间戳的差值小于2ε2ε，我们就无法确定它们的物理顺序，这被称为“不确定性窗口”。
等待
处理这个问题的方法也很简单——等待不确定性窗口过去。 交易提交过程中，会额外等待，直到满足TT.now()−>2ε TT.now()−>2ε，然后提交成功返回给客户端。 之后，无论从哪里发起读请求，都一定会得到一个更大的时间戳，所以一定能够读到刚才的写入。
时钟和 HLC
时钟是逻辑时钟（Clock）最简单的实现。 它用一个整数来表示时间，记录事件的顺序/因果关系（）：如果事件A引发了事件B，那么A的时间戳必须小于B的时间戳。当消息在分布式系统中的节点之间传递时，消息会附带发送者的时间戳，接收者将始终使用消息中的时间戳来“推高”本地时间戳：=max(Tmsg,)+=max(Tmsg,)+1。
钟
时钟只是一个从0开始的整数。为了使其更有意义，我们可以在其高位存储物理时间戳，在其低位存储逻辑时间戳。 当物理时间戳增加时，逻辑位被清除。 这就是 HLC（时钟）。 显然，从尺寸关系来看，HLC和LC没有区别。
HLC
HLC/LC也可以用于分布式事务。 我们将时间戳附加到所有与事务相关的 RPC，即 Begin 和这些消息：
HLC/LC不满足线性一致性。 我们可以构造一个场景，事务A和事务B发生在不相交的节点上。 例如，交易TATA位于节点1，交易TBTB位于节点2。此时，TATA和TBTB的时间戳是彼此独立生成的。 ，不能保证两者之间存在任何先前关系。 具体来说，假设TATA在TBTB之前物理提交，但节点2上发起的TBTB可能滞后（太小），因此无法读取TATA写入的数据。
T1: w(C1)
T1: commit
T2: r(C2) (not visible! assuming T1.commit_ts < T2.snapshot_ts)
HLC/LC 满足因果一致性（ ）或一致性，但是对于数据库来说这不足以满足用户需求。 想象一个场景：应用程序中使用连接池，有可能使用A提交事务TATA（用户注册），然后使用B提交事务TBTB（订单），其他并发事务可能会看到订单（ TBTB）但看到找不到相应的用户（TATA）。
如果连接池的例子不能让你信服，你可以想象一下：微服务节点A负责用户注册，然后它向微服务节点B发送消息，通知节点B下单，但是B却找不到此时该用户的记录。 根本问题是应用程序无法感知数据库的时间戳。 如果应用程序也能像数据库一样在调用RPC时传递时间戳，也许因果一致性就足够了。
有限误差 HLC
上一节介绍的HLC物理时间戳部分仅用于查看，并没有起到实质性作用。 创造性地引入了NTP授时协议。 NTP的精度当然远不如原子钟，误差大约在100ms到250ms左右。 如果应用如此大的误差，交易延迟将高得令人无法接受。
要求所有数据库节点之间的时钟偏移不能超过250ms，后台线程会不断检测节点之间的时钟偏移，一旦超过阈值就立即自杀。 这样，节点之间的时钟偏移就被限制在一个有限的范围内，即所谓的半同步时钟（semi-）。
下面是最关键的部分：在Read的过程中，一旦遇到不确定性窗口[,+]内的数据，就意味着无法判断这条记录是否可见，整个事务将会重新开始（并且等它过去）然后再读一本新的。
读取机制
有了这个额外的机制，在上一节的“先读后写”场景中，保证读事务TBTB一定能读到TATA的写入。 具体来说，由于 TATA 提交是在 TBTB 之前发起的，所以 TATA 的写入时间戳必须小于 B.+，因此要么读取可见结果（< B.），要么重新启动事务并用 a 读取可见结果。新的时间戳结果。
那么，它满足线性化吗？ 答案是否定的。 一份测试报告提到了如下“双写”场景（数据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机制只能阻止数据的存在，而无能为力此类不存在的数据（C1）。
总结一下：仅对单行事务保证线性化，对涉及多行的事务不保证线性化。 这种级别的一致性是否满足业务需求？ 这个问题留给读者自己判断。
结合 TSO 和 HLC
最近看到 TiDB 的 Async 设计文档，引起了我的兴趣。 Async的设计动机是为了减少提交延迟。 TiDB 最初的 2PC 实现需要以下四个步骤：
：将修改写入 TiKV 并从 TSO 获取提交时间戳和其他密钥（异步）
为了减少提交延迟，我们希望将步骤2到4做成异步的。 但获取这一步对于TSO时间戳来说是必不可少的一步！ （否则无法保证后面的事务会比当前事务大。）为此，Async修改了TSO时间戳模型的事务提交部分，引入了HLC提交方式：
你可以和上面的HLC提交流程对比一下，基本是一样的。 请注意，交易一开始仍然是从 TSO 中获取，这一点保持不变。
如果只有3到4步异步的话，岂不是很麻烦？ 这不是真的。 如果在提交时已经采取但没有持久化，那么当事务恢复时，它就不知道用什么来完成提交（roll）； 为了计算一个合法的值，它返回到这个解决方案。
之前我们说过TSO时间戳可以保证线性一致性，但是这样修改之后还可以吗？ 异步设计文档没有给出答案。 我们尝试引入上一节中的“双写”场景，发现由于对TSO的依赖，T1和T2的时间戳仍然可以保证正确的顺序关系，但是稍微修改一下，我们就可以构造一个失败的场景（这里假设在事务开始时获取）：
T2: begin (snapshot_ts = 101)
T1: begin (snapshot_ts = 102)
T3: begin (snapshot_ts = 104)
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，这违反了线性化。 根本原因是一样的：两个交易T1和T2的提交时间戳都是由各自的节点计算的，无法保证顺序关系。
对于用户场景来说，如果用户在两个不同的通道上启动一个事务，写入两行不同的数据，然后依次提交，数据库会将它们视为并发事务，时序可能会颠倒过来。 此场景比故障场景严格得多。 至于是否会影响用户的使用，就留给读者自己判断了。
综上所述，上述已知的时间戳方案中，只有TSO和TSO可以保证线性一致性； Clock方案只能保证一致性； HLC方案只能保证行级线性一致性，不保证多行事务的线性一致性； TiDB Async 的解决方案结合了 TSO 和 HLC，不保证多行并发事务的线性一致性。 – : 的 – – OSDI'12 : beta- – 和 – 异步 ( )
好了，今天的主题就讲到这里吧，不管如何，能帮到你我就很开心了，如果您觉得这篇文章写得不错，欢迎点赞和分享给身边的朋友。
