黄东旭解析 TiDB 的核心优势
1360
2023-04-03
分布式数据库中的事务时序
概述
在单机数据库领域,我们为每个事务都分配一个序列号,比如***的SCN(SystemChangeNumber),MySQL的LSN(LogSequenceNumber),这个序列号可以是逻辑的,也可以是物理的。我们依赖这个序列号对系统中发生的事务进行排序,确保所有事务都有严格的先后关系。数据库中所有的事务都按分配的序列号排序,对于任何时间点发生的读,保证能读到这个时间点之前的提交的事务,并且读不到之后发生的事务。所以,一般来说,无论系统中序列号是逻辑还是物理的,都与真实的物理时间有一个对应的单独递增关系。在单机数据库时代,这个相对容易做到,系统中有一个唯一的序列号分配器,保证有序。
来到分布式数据时代,一个数据库系统不再只有一个节点可以处理事务,多个节点上发生的事务如何保证有序是本文想要讨论的问题。最简单的想法是,我们在数据库系统中专门添加一个组件,这个组件作用就是分配时间戳,付出的代价是,任何一个事务提交,都需要有一个网络RTT的消耗,并且分配时间戳的组件是整个系统的单点,可能成为系统的瓶颈。实际上,目前主流分布式数据库系统还提供了两个可选方案,一种是Spanner数据库的TrueTime机制,另外一种CockroachDB数据库的HLC(HybridLogicClock)机制。
HLC机制
先说说HLC的由来,我们前面提到分布式数据库中,要为每个事务都分配一个合理的序列号比较麻烦,实际上这不单单是数据库的问题,还是所有分布式系统中的共性问题,如何为系统中发生的事件排序。既然各个节点的物理时钟不一致,不如都采用逻辑时钟(LogicClock),逻辑时钟只保证因果一致性,即不保证全局有序,只保证有先后顺序的事件有序。哪些事件有先后关系,主要包括两类,1.单节点内部先后发生的事件;2.节点间有通信的事件,发送消息的节点一定早于接收消息的节点。由于分配的序列号与物理时钟完全无关,真实时间无法与序列号对应,导致无法用于实际的生产环境。HLC源于LC,是对LC的改进,同样是保证因果序,但引入了物理时间戳作为序列号的一部分,这样能与物理时钟对应起来,采用物理时钟+逻辑时钟混合的方式作为序列号,提供一种事务序列号的分配方法。
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 ***),显然所有事务都是有序的,类似于单机数据库;如果是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服务,也能提供一定误差范围内的快照读。
参考文档
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。