概述
在单机数据库领域, 我们为每个事务都分配一个序列号, 比如 Oracle 的 SCN(SystemChangeNumber),MySQL 的 LSN(LogSequenceNumber), 这个序列号可以是逻辑的, 也可以是物理的. 我们依赖这个序列号对系统中发生的事务进行排序, 确保所有事务都有严格的先后关系. 数据库中所有的事务都按分配的序列号排序, 对于任何时间点发生的读, 保证能读到这个时间点之前的提交的事务, 并且读不到之后发生的事务. 所以, 一般来说, 无论系统中序列号是逻辑还是物理的, 都与真实的物理时间有一个对应的单独递增关系. 在单机数据库时代, 这个相对容易做到, 系统中有一个唯一的序列号分配器, 保证有序.
来到分布式数据时代, 一个数据库系统不再只有一个节点可以处理事务, 多个节点上发生的事务如何保证有序是本文想要讨论的问题. 最简单的想法是, 我们在数据库系统中专门添加一个组件, 这个组件作用就是分配时间戳, 付出的代价是, 任何一个事务提交, 都需要有一个网络 RTT 的消耗, 并且分配时间戳的组件是整个系统的单点, 可能成为系统的瓶颈. 实际上, 目前主流分布式数据库系统还提供了两个可选方案, 一种是 Spanner 数据库的 TrueTime 机制, 另外一种 CockroachDB 数据库的 HLC(HybridLogicClock)机制.
HLC 机制
先说说 HLC 的由来, 我们前面提到分布式数据库中, 要为每个事务都分配一个合理的序列号比较麻烦, 实际上这不单单是数据库的问题, 还是所有分布式系统中的共性问题, 如何为系统中发生的事件排序. 既然各个节点的物理时钟不一致, 不如都采用逻辑时钟(LogicClock), 逻辑时钟只保证因果一致性, 即不保证全局有序, 只保证有先后顺序的事件有序. 哪些事件有先后关系, 主要包括两类, 1. 单节点内部先后发生的事件; 2. 节点间有通信的事件, 发送消息的节点一定早于接收消息的节点. 由于分配的序列号与物理时钟完全无关, 真实时间无法与序列号对应, 导致无法用于实际的生产环境. HLC 源于 LC, 是对 LC 的改进, 同样是保证因果序, 但引入了物理时间戳作为序列号的一部分, 这样能与物理时钟对应起来, 采用物理时钟 + 逻辑时钟混合的方式作为序列号, 提供一种事务序列号的分配方法.
接下里我们看看 HLC 是怎么实现的? HLC 分配算法很简单, 源于[论文](https://cse.buffalo.edu/tech-reports/2014-04.pdf).
l.j 表示本地 HLC,pt.j 表示物理时间戳, c.j 表示逻辑时间戳, 对于发送事件或是本地事件, 递增逻辑时间戳部分, 确保本地事件有序; 对于接收事件节点, 取本地时间戳和发送节点时间戳的最大值, 如果物理时间戳部分相同, 则递增逻辑时间戳部分. 整个逻辑是简单清晰的, 回归到数据库系统, 则是事务提交时, 如果是本地事务, 则取本地 HLC 和本地物理时间的最大值, 避免时钟跳变; 对于分布式事务, 则选择多个参与者节点中最大的 HLC, 并且推高各个节点的本地 HLC, 从而保证事务的序列号 HLC 一直都是单调递增的.
在分布式数据库领域引入 HLC 算法能为每个事务都分配一个合理序列号, 并且保证有因果关系的事务通过序列号就能确定. 在数据库领域, 怎么定义因果关系, 对于单节点事务而言, 如果事务严格时间先后发生顺序(事务 A 提交后, 事务 B 才开始), 或者存在依赖关系(比如更新同一行), 则认为存在因果关系; 如果事务能并发执行提交, 但不存在依赖关系, 则不存在因果关系, 事务序列号分配没有约束. 对于跨节点分布式事务而言, 如果涉及到节点更新与其它事务有依赖关系, 则存在因果序, 否则没有. 数据库系统引入 HLC 机制后, 能够保证有依赖关系的事务, 分配的序列号也一定有先后顺序. HLC 由物理时钟 + 逻辑时钟两部分组成, 论文中建议 48 位作为物理时钟位, 16 位作为逻辑时钟位, 那么提供的时钟精度大约是 15 微妙, 每个微妙的逻辑时钟 LC 可以跳变 65536 次.
TrueTime 机制
前面提到了 TrueTime 机制, 在对比两种分配序列号机制之前, 先简单介绍下 TrueTime. 我们之所以使用 LC,HLC 主要原因是我们各个节点的物理时钟不一致, 我们无法按单机思维来解决分布式系统问题. TrueTIme 机制是通过在集群中引入原子钟和 GPS 等硬件设备, 来确保集群中各个节点的物理时钟误差在一定范围内, 配合特殊的事务 commit-wait 逻辑, 保证全局的事务有序.
我们看一个问题, 假设集群最大物理时钟误差是 100, 用户先后执行了两个事务 A 和 B, 分别在节点 Node1 和 Node2 上提交, Node1 的物理时钟比 Node2 物理时钟快 70, 事务 A 的提交时间物理时间戳为 120, 记为 t1; 事务 B 的提交物理时间戳为 55, 记为 t2, 显然从时间戳来看 t1>t2, 但是事务 A 却先于事务 B 发生, 这显然与实际情况不符. 由于事务 A 和 B 并没有任何交集, 按我们的定义, 它们之间没有因果关系, 所以 HLC 机制不保证最终分配的时间戳 HLC(A) <HLC(B).
现在看看 TrueTime 机制如何给两个事务排序. 假设事务 A 提交时, 通过 TrueTime-API 获得的是一个时间戳是一个范围, 比如 [t1-ε1,t1+ε1], 事务 B 开始时, 获取的时间戳范围是[t2-ε2,t2+ε2], 由于事务 A 先于事务 B 发生, 因此需要能保证 t1+ε1 < t2-ε2,t2-t1> ε1+ε2, 那么显然只要事务提交时, 等待(ε1+ε2) 时间, 那么一定能满足 t1+ε1 < t2-ε2, 也就是事务 A 提交时间戳<事务 B 提交的时间戳. 实际上 TrueTime 机制保证的时间戳误差最大在 7ms, 那么事务提交时, 则必须等待大概 14ms, 才能保证事务有序. 对于分布式事务, 事务会跨多个节点, 事务的时间戳会选取几个节点中最大的时间戳. 因此, 实际上对于集群中任何一个节点无论是本地事务还是分布式事务, 发生的先后顺序都与时间戳顺序一致, 也就能保证所谓的外部一致性. TrueTime 机制通过 commit-wait 的模式通过牺牲延迟, 保证了全局顺序.
TrueTime 机制引入了特殊的硬件设备, 外加 commit-wait 机制, 通过牺牲一定的 latency, 来保证全局事务的顺序. HLC 机制对于写请求则相对轻量, 尤其是本地事务, 没有任何网络交互, 也不需要额外的时间等待, 不同节点上有先后顺序事务, 实际上分配的序列号没有严格的先后顺序, 只能保证因果序.
全局序 VS 因果序
如果采用专门的事务序列号分配组件服务, 比如 TSO(TimeStamp Oracle), 显然所有事务都是有序的, 类似于单机数据库; 如果是 TrueTime 机制, 对于任何一个时间戳, 读取的快照误差都在指定的范围(7ms 以内), 结合 commit-wait, 也能保证全局有序; 而对于 HLC 机制, 由于并没有解决物理时钟问题, 要控制误差可能需要借助 NTP 等服务, 当然这个误差可能在 150ms 或更多, 不如原子钟和 GPS 精确, 如果采用 commit-wait 机制, 事务延迟过大, 就无法用于实际生产环境了, 所以无法提供全局序. 那么全局序和因果序对于读有什么影响? 对于快照读, HLC 机制如果只根据本地 HLC 时间戳生成, 那么因为时钟误差, 可能会漏掉部分已提交的事务; 如果与所有节点通信并获取 HLC, 那么至少当前的这个快照是能读到所有已提交的事务的, 但读性能开销就比较大了(与所有节点都有网络交互). 当然, 这个就看场景了, 比如要建全局索引, 通过与所有节点通信获取 HLC, 实际上就相当于与所有节点都有因果关系, 间接得到了一个全局一致性快照. 这个快照点以前的事务都可以读取到, 这个点以后的事务都不读到. 显然, 全局序更贴合实际应用场景, 但我们也可以具体问题具体分析, 不能说只提供因果序的系统没有价值.
总结
数据库系统中, 给事务分配合理的序列号, 需要与实际发生的事务先后顺序保证单调递增关系. 这个需求在单机数据库时代很容易满足, 因为只有一个时钟源. 进入分布式数据库时代, 由于一个数据库系统中有多个节点, 每个节点都需要承担分配事务序列号的任务, 但天然的各个节点时钟存在误差, 导致需要引入特殊的事务序列号分配机制, 比如 HLC 机制, 或者 TrueTime 机制. TrueTime 机制本质就是硬件方案, 将集群中节点间的物理时钟误差控制在很小的范围内, 结合 commit-wait 模式, 保证所有事务全局有序, 理论上要保证全局有序, TrueTime 并非是充分条件, 只需要 commit-wait 即可, 就看 wait 的时间长短了. HLC 机制则是软件方案, 只保证事务因果序, 并且解决了本地时钟跳变问题. HLC 机制配合 NTP 服务, 也能提供一定误差范围内的快照读.
参考文档
https://cse.buffalo.edu/tech-reports/2014-04.pdf
来源: https://www.cnblogs.com/cchust/p/10591943.html