文档章节

分布式数据库中的事务时序

o
 osc_a22drz29
发布于 2019/03/25 09:25
字数 2766
阅读 12
收藏 0

精选30+云产品,助力企业轻松上云!>>>

概述

在单机数据库领域,我们为每个事务都分配一个序列号,比如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

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
分布式事务:两阶段提交与三阶段提交

在分布式系统中著有 CAP 理论,该理论由加州大学伯克利分校的 Eric Brewer 教授提出,阐述了在一个分布式系统中不可能同时满足 一致性(Consistency)、可用性(Availability),以及 分区容...

zhenchao
2016/08/23
1.6K
2
当数据库遇到分布式

概述 NewSQL日渐火热,无论还是开源的TiDB,CockroachDB还是互联网大厂的Spanner,Oceanbase都号称NewSQL,也就是分布式数据库。NewSQL的典型特征就是,支持SQL,支持事务,高性能,低成本,...

osc_xgk2otgu
04/16
2
0
当数据库遇到分布式

概述 NewSQL日渐火热,无论还是开源的TiDB,CockroachDB还是互联网大厂的Spanner,Oceanbase都号称NewSQL,也就是分布式数据库。NewSQL的典型特征就是,支持SQL,支持事务,高性能,低成本,...

天士梦
2019/04/14
0
0
一文读懂分布式事务一致性

转载自:https://blog.csdn.net/w05980598/article/details/79305239 一、概述 在支付、交易、订单等强一致性系统中,我们需要使用分布式事务来保证各个数据库或各个系统之间的数据一致性。 ...

jason.bai
2019/06/03
0
0
以交易系统为例,看分布式事务架构的五大演进

作者介绍 在支付、交易、订单等强一致性系统中,我们需要使用分布式事务来保证各个数据库或各个系统之间的数据一致性。 举个简单的例子来描述一下这里数据一致性的含义。 程序员小张向女友小...

梁阳鹤
2017/04/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

将分段视频合并

环境 操作系统:Ubuntu Kylin 优麒麟 20.04 LTS 适用架构:AMD64、ARM64(鲲鹏、飞腾) 方法 将下载的视频分片段放入同一个文件夹。按片段排序的文件名汇入list.txt。 ls qq_video*.mp4 | s...

chipo
25分钟前
13
0
C#和C++混合编程系列1-内存管理

2篇前置博文: Http服务器-第十步加入基于Mono平台的C#脚本支持 https://my.oschina.net/kkkkkkkkkkkkk/blog/4322402 架构9-引入C#混合编程-服务端概述 https://my.oschina.net/kkkkkkkkkkk...

梦想游戏人
29分钟前
18
0
SQL使用SELECT * [columnA除外] FROM tableA排除列?

问题: We all know that to select all columns from a table, we can use 我们都知道要从表中选择所有列,我们可以使用 SELECT * FROM tableA Is there a way to exclude column(s) from......

fyin1314
44分钟前
12
0
LVS-NAT模式示例配置

实验环境 Centos 7.6.1810 + ipvsadm v1.27 配置脚本 Director配置(1台) yum install -y ipvsadm; echo 1 > /proc/sys/net/ipv4/ip_forward; ipvsadm -C; # 清空所有集群配置 ipvsadm -A -......

月下狼
44分钟前
9
0
linux 复制 黏贴

飞雪无痕
54分钟前
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部