ZNBase 时钟同步技术解析:原子钟实现 Ture-time 机制

原创
前天 14:52
阅读数 1.1K

导读

在分布式数据库系统中,为了解决不同集群、节点事件发生的先后顺序问题,时钟同步至关重要。本文将为大家介绍业界现有的几种主流的时钟同步解决方案,以及分布式数据库 ZNBase 基于原子钟技术实现的 Ture-time 机制。

业内的时钟方案

目前业内主流的分布式数据库系统中,采用的时钟同步方案各不相同。

国内比较热门的 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 的误差,这会造成分布式节点间时钟误差较大,从而影响数据库的高并发性能。 

2. 逻辑时钟(LC)

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

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

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

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

3. 向量时钟(VC)

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

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

4. 混合逻辑时钟(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 数据库的读写并发量,成为一个亟待解决的问题。

5. True-time 机制

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

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

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

ZNBase 的原子钟方案

ZNBase 是由浪潮开源的一款 NewSQL 云原生分布式数据库,与 CockroachDB、TiDB 一样同为参考自谷歌的 Spanner+F1 论文设计,具备强一致、高可用分布式架构、分布式水平扩展、高性能、企业级安全等特性。其时钟同步方案经过优化迭代,目前采用的也是业界领先的 ture-time 方案。 

ZNBase 最初采用的时钟同步方案也是 NTP 对时+HLC。由于前文提到的 NTP 协议存在误差的问题,导致集群内节点存在 500ms 左右的误差,很大程度上影响了数据库的高并发性能。为解决这一问题,ZNBase 团队决定舍弃 HLC 模块,引入更高精度的原子钟+PTP 协议,实现了自己的 ture-time 方案。 

PTP 即精确时间同步协议,是一种在硬件层面实现的时间同步协议,一般采用硬件时间戳,并配合比 NTP 更高精度的延时测量算法。PTP 可以直接在 MAC 层进行 PTP 协议包分析 , 这样可以不经过 UDP 协议栈 , 减少 PTP 在协议栈中驻留时间 , 从而提高时间同步的精确度。

以下是 ZNBase 团队针对 NTP 与 PTP 进行的实验对比数据:

通过在不同并发场景下的压测 TPMC 结果,原子钟与原有方案的性能数据相比,原子钟方案性能提升 10%-20%。并且,原子钟方案与原有方案相比,更加适合高并发及事务冲突场景。

由于谷歌 Spanner 的 true-time 机制是配合原子钟+GPS 的硬件实现的,相关的软件部分并未开源,无法直接照搬或借鉴。ZNBase 团队在落地自身的 ture-time 机制过程中遇到了诸多挑战。 

针对这种情况,ZNBase 研发团队查阅了大量的论文及技术资料,研究 true-time 的技术理论,通过前期的大量压测及开展校企合作的方式,并与大学科研机构开展相关子课题的研究。最终,通过大量理论与实践研究的工作,ZNBase 实现了现有的原子钟方案。

目前,ZNBase 的 true-time 方案基于高精度时间同步主时钟实现。支持 PTP/NTP/GPS/北斗/原子钟五种模式。使用 GPS/北斗作为参考时钟时,跟踪 UTC 的精度优于 100ns,可通过以太网提供百纳秒级的时间信号源,极大地缩小了不同服务器之间的时钟偏移范围。

高精度时间同步主时钟

通过将 NTP+HLC 方案优化成 PTP+原子钟方案,ZNBase 将集群内的节点误差控制在了 1ms 以内,解决了异地多中心部署时,分布式节点间时钟误差较大的问题。

总结

本文介绍了分布式数据库系统常用的几种时钟同步解决方案,以及 ZNBase 的时钟同步方案的优化迭代过程。欢迎对相关技术感兴趣的朋友留言讨论,不足之处也欢迎指出。


关于 ZNBase 的更多详情可以查看:

官方代码仓库:https://gitee.com/ZNBase/zn-kvs

ZNBase 官网:http://www.znbase.com/ 

对相关技术或产品有任何问题欢迎提 issue 或在社区中留言讨论。同时欢迎广大对分布式数据库感兴趣的开发者共同参与 ZNBase 项目的建设。

联系邮箱:haojingyi@inspur.com

展开阅读全文
打赏
0
2 收藏
分享
加载中
打赏
0 评论
2 收藏
0
分享
返回顶部
顶部