TSO - Time Stamp Oracle

国内比较热门的 TiDB 和 OceanBase 使用的是 Timestamp Oracle (TSO)方案,即中心化授时方案。TSO 采用单时间源、单点授时的方式实现全局时钟,用一个全局唯一的时间戳作为全局事务 id。其中,TiDB 的事务模型是基于 Google Percolator 的,所以从一开始就使用的是类似 Percolator 的 TSO 机制。TiDB 通过集群管理模块 PD 统一进行时间的分配,以保障整个系统时间的全局同步。这种模式的优势是实现简单,在同一个数据中心下网络开销非常小,但在跨地域的使用场景中延迟较高。并且,中心化授时方案会成为整个系统的性能bottleneck,且授时服务的单点故障会直接导致整个分布式集群的不可用。

此外,CockroachDB 采用的是 HLC 作为时钟同步方案;Google 的 Spanner 使用的是结合原子钟+GPS 硬件的 ture-time 机制,实现了全球化低延迟部署。

数据库的核心就是将每一个事务的操作进行排序,在传统的单机架构下,事务的排序可以通过日志序列号或事务 ID 轻松实现。但是在分布式架构下,数据库运行在多台服务器上,每个数据库实例有独立的时钟或日志(LSN),而服务器和服务器之间时钟点有快慢之差,所以分布式数据库下的时钟无法反映全局的事物顺序。作为分布式数据库的关键技术之一,时钟同步技术就是为了解决分布式数据库中事件发生的先后顺序问题而存在。

随着分布式系统规模的不断扩大,不同集群和不同节点的时间同步问题变得异常复杂。目前,分布式数据库业界普遍采用的时钟同步方案包括物理时钟、逻辑时钟、向量时钟、混合逻辑时钟、True-Time 机制五大类。

  1. 物理时钟(PT)

物理时钟即机器本地的时钟,而由于设备硬件不同,本身存在偏差,一天的误差可能有毫秒甚至秒级,所以需要对不同的机器时钟进行同步使得机器之间的时间进行相对统一。通常使用中心化的全局时间同步来保证各节点的时间统一。

NTP 是目前比较常用的同步时间的方式。NTP 协议(Network Time Protocol)是用来使计算机时间同步化的一种网络协议,它可以使计算机对其服务器或时钟源(如石英钟,GPS 等等)做同步化,可以提供较高精准度的时间校正。其机制为 C/S 架构,即每台机器上存在一个 NTP 的客户端,与 NTP 的服务端进行同步,校准本地的时间。

然而,在分布式数据库中采用 NTP 协议进行对时,仍会存在 100-500ms 的误差,这会造成分布式节点间时钟误差较大,从而影响数据库的高并发性能。

  1. 逻辑时钟(LC)

逻辑时钟是由图灵奖得主 Leslie Lamport 于 1978 年提出的概念,是一种在分布式系统中用于区分事件的发生顺序的时间机制。逻辑时钟没有任何一个中心节点来产生时间,每一个节点都有自己本地的逻辑时间,主要通过 happened-before 关系确定事务的逻辑顺序,从而确定事务的偏序关系。

比如在两个不同的实例中,A 节点先产生事务 1,事务 1 与其他任何节点没有产生联系,此时 A 节点逻辑时钟+1,其他节点不变;A 节点再产生事务 2,事务 2 与 B 节点产生联系,此时 A 节点逻辑时钟+1,B 节点逻辑时钟直接 +2,从而与 A 节点时钟同步。通过在两个时钟之间建立联系,将两个节点之间的逻辑时钟同步,这时候就构建了它们之间的 happened-before 的先后关系,代表 A 节点的事务是在 B 节点的新事务开始之前完成的。

分布式数据库中,如果两个事务没有操作同样的节点,则两个事务是无关的事务。无关的事务可以认为是没有先后顺序的。但是当一个事务横跨多个节点的时候,将多个节点之间的关系建立起来,就变成有关系的事务,构建的是事务间的因果序。

而逻辑时钟的问题主要在于仅能保证同一个进程内的事件有序执行,当涉及到不同进程时,无法确定合适的全序关系,容易造成冲突。

  1. 向量时钟(VC)

向量时钟是在 Lamport 算法基础上演进的另一种逻辑时钟方法,它通过向量结构,不仅记录本节点的 Lamport 时间戳,同时也记录了其他节点的 Lamport 时间戳,因此能够很好描述同时发生关系以及事件的因果关系。

向量时钟在每个节点存储一个向量,向量的每个元素就是各个节点的逻辑时钟,本质上是通过存储所有节点的时钟备份来解决逻辑时钟的冲突问题。但由于时钟向量的维度等于节点数量,因此空间复杂度较高,影响了数据库存储和传输的效率。

  1. 混合逻辑时钟(HLC)

混合逻辑时钟是一种将物理时钟和逻辑时钟进行组合的解决方案。

混合逻辑时钟把分布式下的时钟切成两部分,上半部分用物理时钟来填充,下半部分用逻辑时钟来填充。即在物理时钟的基础上,在一定的偏差范围内引入逻辑时钟进行校准,尽可能使得两者达成一致。其核心内容包括以下 4 点:

(a)满足 LC 的因果一致性 happened-before。

(b)单个时钟 O(1) 的存储空间(VC 是 O(n),n 为分布式系统下的节点个数)。

(c)单个时钟的大小有确定的边界(不会无穷大)。

(d)尽可能接近物理时钟 PT,也就是说,HLC 和 PT 的差值有个确定的边界。

混合逻辑时钟一共 64 位,前 32 位表示物理时钟,后 32 位用于逻辑计数。

前文提到的物理时钟同步精度问题也是 HLC 目前面临的主要问题之一。在云原生的 NewSQL 数据库中,使用 HLC 时钟也需要在物理时钟层面进行高精度对时。然而基于 NTP 的 HLC 协议,在局域网下的延迟较小,误差小,但在广域网下时延长而且不稳定,对于多地域的分布式集群来说误差很大,极大的限制了云原生 NewSQL 数据库的并发量。如何提升对时精度,从而提升云原生 NewSQL 数据库的读写并发量,成为一个亟待解决的问题。

  1. True-time 机制

True-time 机制是 Google 公司在 Spanner 论文中提出的时间同步机制,该机制假设系统中每台机器产生的时间戳都有误差,整个系统中达成了关于时间戳误差范围的共识,进而延迟提交事务,延迟时间和时间戳误差有关,因此谷歌每个数据中心都部署了基于 GPS 和原子钟的主时钟服务器,保证延持提交的等待时间尽可能短。

True-time 本质上是确保两个服务器之间时钟偏移在很小的范围之内,因此对机器的物理时钟精度提出了极高的要求。Google 通过在各个数据中心部署昂贵的原子钟+GPS 系统,来同步数据中心里各个机器的时间。与传统石英钟一天毫秒甚至秒级的误差相比,原子钟的精度可到达 2000 万年差一秒。

当然,这种方案的缺点也显而易见,因为是结合硬件实现的解决方案,成本高昂,难以在其他地方大规模推广。

3 个赞