分布式事务是分布式数据库最难的技术之一。分布式事务为分布式数据库提供一致的数据访问支持，保证全局读写的原子性和隔离性，提供一体化的分布式数据库用户体验。本文主要分享分布式数据库中的时钟解决方案和分布式事务管理技术方案。HybridLogicalClock（HLC）可以在本地获取，避免了中央时钟的性能瓶颈和单点故障，同时保持了跨实例事务或事件的因果关系（happenbefore）。本次分享主要围绕以下两个方面：时钟方案分布式事务管理一、时钟方案1、数据库为什么需要时钟？归根结底，数据库就是对每笔交易进行排序。在单机的情况下，事务排序可以很简单的实现，但是在分布式环境下如何进行事务排序呢？数据库通过事务对外提供与数据相关的操作的ACID。数据库对事务顺序的识别决定了事务的原子性和隔离性。原子性是指一个事务是完整的，不管它是否发生，也就是说每一个事务都是独立的。隔离意味着交易彼此隔离。时钟有多种方法来识别事务的顺序。例如，Oracle中的每条日志都有一个日志序列号LSN、事务ID和时间戳。目前很多商业和开源的数据库产品都支持MVCC。MVCC通过支持多版本数据，允许读写相同的数据，实现并发，在读多写少的场景下大大提升了性能。多个版本出现后，暗示了交易的顺序。当一个事务开始时，需要判断数据的哪个版本是可见的，哪个版本是不可见的，所以这就涉及到多系统、多版本、版本回收等问题。一个很经典的场景，淘宝或者天猫的购物场景，有一个商品记录，用户每购买一个商品，就对商品数量记录进行一次扣减。产品记录版本会变得很长，把所有版本都存起来是不合理的，否则整个存储容量会不断增加。那么如何回收版本呢？回收的时候，还需要有一个命令来确定回收哪些版本？2、分布式数据库下的时钟分布式数据库下的时钟和单机数据库下的时钟有什么区别？首先，单机数据库的时钟排序很简单，事务的顺序可以用日志序号或者事务ID来表示。在分布式数据库下，由于数据库运行在多台服务器上，每个数据库实例都有独立的时钟或日志（LSN），每个本地时钟不能反映全局顺序。服务器之间会有时钟偏移。理想情况是在一个分布式数据库中部署100个节点，100个节点的时钟完全同步。但在现实中需要检查机房时钟是否出轨，因为服务器与服务器之间的时钟点速度存在差异，所以分布式数据库下的时钟无法反映到全局环境。3、时钟方案时钟方案有很多种，比如采用统一的中心节点，或者采用独立的服务器生成分布式时钟。另一种解决方案是逻辑时间，Lamport时钟是一个逻辑时钟。逻辑时钟是指没有中心节点产生时间，每个节点都有自己的本地逻辑时间。比如有十个Oracle数据库，每个节点都有自己的LSN。如果节点有很多事务，事务ID将运行得更快。如果节点事务较少，则事务ID运行速度会较慢。下图是目前主流的几种时钟方案，其中TIDB是国人的骄傲，TIDB采用的是中央时钟。另外，Postgres-XL使用了GTM，也属于中央时钟。Oracle使用逻辑时钟SCN。CockraochDB是一个模仿Spanner的分布式数据库，使用混合逻辑时钟。还有最知名的GoogleCloudSpanner，它对硬件的依赖很大，用的是Truetime。Truetime本质上是一个原子钟，通过原子钟计时保证两台服务器之间的时钟偏移在一个很小的范围内。4.逻辑时钟逻辑时钟在分布式环境下是如何实现的？如下图所示，有A、B、C三个节点，每个节点都会有自己的逻辑时间。逻辑时间可以简单理解为一个单调递增的自然数。0,1,2,3....事务开始后加1，新事务开始时加1。在整个分布式环境中，三个节点是完全独立的，相互之间没有任何关系。如果交易跨越多个节点，涉及到多个节点的交互，则在交易产生时，本地时钟必须加1。发送消息时，必须发送消息正文，本地时间也必须发送到另一个节点。收到消息节点后，需要对消息进行处理。从接收到的消息中，对时间和本地逻辑时间进行取值，取最大值作为本地时间。如果节点A发布速度快，第一笔交易完成后，第二笔交易就要完成。这时候和B节点有通信，A加1，然后把时钟带到B节点，B节点直接从0跳到2，这样两个时钟就建立了连接。通过建立连接，两个节点之间的逻辑时钟被调平。这时，它们之间的happenbefore关系就建立起来了，也就是说节点A的事务在节点B的事务中。在新的事务开始之前完成。在分布式数据库中，如果两个事务不在同一个节点上运行，则它们是无关紧要的。不相关的交易可以被认为是乱序的。但是当一个事务跨越多个节点时，多个节点之间的关系就建立起来，成为一个关联事务，事务之间的因果序列就被构建出来了。所谓因果顺序，如果两个交易也来了，一个交易操作AB节点，另一个交易操作BC节点，因为他们已经在B节点上建立了连接。通过B节点之间的关系，维护交易的顺序。纯逻辑时钟可以实现因果一致性和因果排序能力。逻辑时钟最大的问题是什么？在最极端的情况下，节点之间永远不会有任何连接，两个节点之间的逻辑时钟差距会越来越大。这时候如果两个节点之间有查询或者备份，就需要强制他们建立关系，两个节点之间的差距就会变得很大。5.Hybridclock虽然物理时钟在机器之间是有偏移的，但是如果有NTP校准或者像Google的Truetime这样的时钟服务器，物理时钟之间的差异是非常小的。混合时钟将分布式时钟分为两部分，上半部分填充物理时钟，下半部分填充逻辑时钟。填充在一起成为HLC时钟，它是一种混合逻辑时钟。它既有物理时钟部分，也有逻辑时钟部分。由于物理时钟服务器之间的差异不是特别大，所以可以比较物理时钟大小。但是，物理时钟有一定的偏差。在一定的偏差范围内，可以使用逻辑时钟进行校准。下图是一个混合逻辑时钟的例子。发送消息时，首先要将逻辑时钟的物理时钟部分与当前时钟进行比较。如果当前物理时钟是4点钟，新事务产生后，因为物理时钟没有变化，所以新事务被加到逻辑时钟上（加1）。如果物理时钟从4:01变为4:01，则??将物理时钟提前。如果物理时钟不提前，则添加逻辑时钟。如果物理时钟发生变化，则物理时钟上推，逻辑时钟部分置零。6、HLC和中心时钟的区别基于中心时钟的方案的时间是通过事务ID来判断的，从而对所有事物进行排序。在分布式数据库中，需要去掉中心节点。一种方法是纯逻辑时钟，但是逻辑时钟无法在大小上进行比较。另一种方法是混合逻辑时钟(HLC)，它为数据库定义了一类因果事务。混合逻辑时钟没有中心节点，使用本地物理时间加上逻辑时间。本地产生的交易顺序没有保证，但是如果交易跨节点，它的因果关系是有序的。如下图，T1、T2、T3代表提交时间，T1为分布式事务，T2为单机事务，T3为分布式事务。因为T1是一个分布式事务，在数据库节点上progress1先于progress2执行，所以在整个时钟中，progress1小于progress2，progress1也小于progress3。这样，序列安排关联交易。7.中央VS。分布式VS。TrueTime如下图，中央时钟的优势一目了然，可以保证时间全局一致。分布式数据库下时钟的好处是没有中心化的性能，也没有HA瓶颈，因为不需要中心化的授时服务。分布式数据库下的时钟主要有两个能力。第一个能力是实现计算和存储的水平扩展。另外，由于分布式数据库将一个业务的工作负载拆分到了不同的机器上，单点故障的影响也降低了。核心数据库被拆分成数百个副本，任何一个单点数据库故障都会导致整个系统可用性的极小下降。这就解释了为什么现在分布式和互联网+的结合比较流行。一个重要的原因是分布式降低了单点故障对业务可用性的影响。不只是互联网公司，金融银行也想去分布式。一方面是为了解决容量和扩展性的问题，另一方面也是为了解决高可用的问题。中心式的缺点是会出现单点故障。分布式时钟虽然消除了单点的影响，但时钟无法排序，无法实现真正??的外设一致性。外围一致性意味着每两个事务都可以排序。分布式时钟只能对相关事务进行排序，实现因果顺序。Google的Truetime的优点是保证全球时间一致，简化应用程序开发。缺点首先是它需要专有硬件。如果Truetime的原子钟为时间服务，也会有一定的时钟偏差，这是物理上无法克服的。在GoogleSpanner的论文中可以发现，每次事务的提交都要等待一段时间，就是等待这个clockskew。二、分布式事务管理1、两阶段提交分布式事务管理是保证全局读写的原子性和隔离性。一笔交易需要跨越两个节点，此时有失败的可能。如果一个节点成功，一个节点失败，看到的结果就会不一致，失去了事务的原子性。还有一种就是在两个节点上都提交成功了，但是因为两个节点的时间不一样，所以提交的时间也不一样。如果用MVCC读取这个事务，可以看到一半，另一半可能不可见，因此无法保证事务的原子性。关于事务的原子性，目前相关技术已经非常成熟，即两阶段提交。如果要保证分布式事务的成功或失败，可以使用两阶段提交技术，先做一个preparetransaction，如果prepare都ok，再commit。2.其他分布式事务管理技术常见的分布式事务管理技术分为三类。第一类是两阶段提交技术，包括准备阶段和提交阶段。第二种是基于MVOCC的，其中FOUNDATIONDB是Apple开源的分布式数据库，它使用的是MVOCC，可以理解为OCC（乐观并发控制）。OCC是指在事务提交时检查是否存在冲突，并根据冲突设置冲突检测算法和权重算法，最终选择销毁或提交哪个事务。对于锁，事前和更新时加锁，提交时检查冲突。当冲突不严重时，由于没有加锁开销，整体吞吐量很高。在冲突严重的情况下，大量中止的事务会反复回滚。第三类技术主要针对确定性交易，比如FAUNA技术。美国一位教授提出了确定性事务，并基于确定性事务模型创立了一家公司，创建了分布式数据库（FAUNA）。确定性事务指的是完整的而非交互的事务。例如，像淘宝这样的互联网公司处理的是非确定性交易。非确定性事务只有begintransactions、selecttransactions等，每个操作都是交互的，即APP需要和DataBase进行交互。从数据库的角度来看，数据库永远无法预测下一条语句，这样的事情是非确定性的。确定性事务是一次性写出一个事务的所有逻辑，然后发送到DataBase。当DataBase收到一个事务，它就知道这个事务需要操作哪些表，读取哪些记录，执行哪些操作。从数据库的角度来看，事务是完全确定的。得到一个确定性的交易，你可以提前安排好这些交易。如果两个交易之间操作相同的记录，则将它们依次排列。如果不操作相同的记录，则同时发出。使用这种方式后提交时既不能加锁也不能做冲突检测。但它的要求是交易不能交互。3.HLC和两阶段提交混合逻辑时钟（HLC）格式如下。如果是64字节，先预留5字节保证兼容性。在进行系统设计时，通常需要预留一些字节，或者出现问题时没有可用字节。中间留出43个字节给物理时钟。接下来的16个字节用作逻辑时钟。如果时钟精确到毫秒级别，43字节的物理时钟意味着279年，也就是说数据库一直在运行，279年都不会挂。一般来说，这不太可能。如果物理时钟到了天级，一天只能变化一位，那么物理时钟就失去了意义。16个字节就是65536，65536表示一毫秒内可以发起65536笔交易。一般在开始和结束时消耗两个时钟。除以二，一毫秒内可处理超过3万笔交易，单节点一秒内可处理超过3000万笔交易。4、HLC时钟偏斜问题HLC与交易吞吐量有关，因为它有物理时钟，可以显示不同节点间的时钟差异。如果确实发生时钟偏移怎么办？下图提供了一个简单的公式。在没有偏差的情况下，理论上节点可以做到3000万TPS，当然在工程上是不可能的。如果两个节点时钟之间的偏移量为5毫秒，则只能由逻辑时钟在5毫秒内进行补偿。如果原来60000个逻辑时钟可以在1毫秒内完成，现在需要5毫秒，导致整个事务的吞吐量减少了600万。所以clockskew会导致peakTPS明显下降。下图展示了几种解决方案。允许设置最大时钟偏移相对简单。如果整个机房或集群中两个节点之间的最大偏移量超过100毫秒，异常节点将被清除。目前机房有NTP授时服务，所以出现这么大的时钟偏移的概率很小。另一种方式是不清除异常节点，而是让逻辑时钟溢出到物理时钟部分，使逻辑时钟变大，从而允许在当前时钟内发生更多事务。
