分享人：北侠   PolarDB专家

正文：本文详细介绍了分布式一致性和分布式事务之间的关系。

一、分布式架构

分布式数据库的架构分为两层，底层是分布的KVstore，上层是分布式的SQL层。分布式KVstore将数据库的表分成多个shat，每个分区通过高可用的多复本，通过分布式一致性协议，做高可用的多复本，同时在底层存储负责做shat的管理、拆分、合并，底层提供KV接口。上层是分布式SQL层，SQL层主要是分布性事务在这一层，当然底层的分布式KV也要提供相应的接口。

分布式一致性和分布式事务的关系是什么呢？分布式一致性协议在分布式数据库中的发挥的作用，在底层做高可用的分布式KV，分布式一致性将五个数据切分成了多个切片，它是关注一个分片数据内部的数据可用性问题，也可以说它是负责单行数据的事务，当一个事务跨了多个机器上的行，如何保证跨机达到满足事务一致性的算法，分布式事务算法有两个：一是基于锁的算法，另一个是Lock free的算法，基于锁的算法是比较经典的，目前多数的SQL、DB都借鉴这种算法的思想。那基于big table，借助big table的时间维度来实现的，从而达到了query的隔离级别。

和事物相关的有三个列：第一个是Lock 列，事务在运行提交时会写这种列，记录未提交事务锁的信息，当事务成功提交之后，这一列就会被清理掉，格式是Key加上开始的时间戳，它的value对应primary key，primary key的主要作用是做原子提交。第二个value记录了lock的类型。第二列是Data column，是用户存储的真正数据，它的Key是和时间戳的组合，本质上是提供了一个数据的版本的服务。第三列是right column，对比下单机数据库里面的话，当他提交的时候，在right column里面寄一条数据,说明整个事物就提交了，只有当该列被正确的写入之后，整个事务的修改才会被其他事物看到。读请求是在整个列里寻找一个最新的开始时间戳，通过开始时间戳去决定到Data column里面去读取相应的版本。

算法分成两部分，第一个阶段叫做private。这阶段客户端要获取一个全局唯一的时间戳作为事物的开始时间，客户端会从所有的key里随机选一个key，这个key就作为primary key。这时会将所有的KV数据协助请求并发的发给所有的存储节点。存储节点收到这些Key后，要做相应的处理。存储节点要做重组检测 ,就是写写的冲突检测，在存储侧一个存储地点同时会收多个事务的提交请求，就会出现冲突。

如何解决写写的冲突检测呢？通过lock column来决定。比如T1在提交过程中， T2已经完成提交了，有可能是事务开始的比较晚，事务T1开始之后T2才开始，事务2运行的比较快又先提交了，T1提交的时候，就相当于是一个写写冲突，别人已经提交了，它就不允许提交。因为这两个事务是并发的关系。

如何得到两个事务的并发关系，通过跟事务相关的三个列来判断，首先它是从right column里面获取当前最新的数据。如果说key的提交时间大于的开始时间，说明这个事务在我开始后做了提交，这个事物的更新过程和其他事务key的提交是有冲突的。第二检测key是否已经被上锁，有可能在更新的过程中，其它的事务对它也做了更新并没有提交，这种情况是两个事务同时对一个key做更新，这也是一种写写冲突。

如果协议冲突检测通过没有冲突了，这个存储节点就将事务数据写入到到lock column里，对这一行做上诉，类似于PostgreSQL里写锁对这一行的写锁，也就是记录锁行锁，它记录的是事务的开始时间戳，和key同时指向一个primary key引用。这样写入这三条数据的时候，就对key做了一个加锁，如果当前key被选为primary key，它要做一下标记。如果当前不是一个primary key，它就会记录primary key的信息。接下来读取right column判断冲突，通过检测后向lock column里对这行数据上一个行锁，然后向Data column写真正的数据了。

这个阶段大家是并发执行的阶段。比如你一个事务里面更新了100行数据，100行数据又涉及到三个节点，它会把这些数据并行的发给三个节点，三个节点完成对100个数据写入的过程。这个过程完成后相当于所有存储节点已经完成了相关数据的修改，但是还没有进行提交。

下面进入commit阶段，首先客户端要获取一个全局的时间戳作为提交时间。

第二步是向primary key的存储节点发送commit的请求，在算法里面第一阶段会随机选一个作为primary key，向primary key所在的地点，发一个commit请求。完成后就标记事务做了一个原子提交，整个事物就已经提交完成了。

接下来系统里面会向密布的、并行的、其他的不是primary的节点，异步发送的请求，存储节点客户端的存储节点如何处理这个请求呢？

首先要获取这个key，看一下这个key是不是合法的，将key和它的提交时间戳、开始时间同时写入right column里。

第三步完成了提交后，primary key就可以在第一阶段上的行锁清理掉。那么这里面我们要强调一点啊，一旦这个primary的节点提交成功之后，整个事务就算是提交成功了。

提交后，其它的事务如何去读取？ right column里记录了key的提交记录，客户端去提交key的时候，首先要从right column里面读取这个key，找到这个key最新的开始时间，得到最新已经提交的开始时间戳作为它的版本。接下来从数据列找到相应的版本，就能读上来了。那接下来我们可以去这样去比较一下这个Paxos的算法和经典的单机的并发协议的关系。本质上来说，可能的算法，它是分布式版本的算法，在PG的数据库里面，事务在提交的时候，也要上行锁。要先对页面上锁，找到对应的行，对这个行再上一个行锁。如果事务在上行锁的时候，发现已经上了其它事物的行锁，PG就根据当前事务的隔离级别来做相应的处理。比如说当前让RC的话，就允许往下执行，如果当前高于RC，当前的事物就不要再往下执行了。PG数据库在上行锁的时候，如何判断其它事务与当前事物是属于并发关系呢？那么他的病，它要先读取当前事务对应的行锁，如果上行锁的事务比我自己发生的要晚，那也是并发关系，或者说它已经提交了，在我之后发生的事，我提交了，也是一个并发关系。

PG数据库在做整理提交的时候，最重要的是做一个C log的写入，那么C log里面会记录事务的状态。那么如果分布式之后，像big table里面没有中心化的C log文件，因此它就随机的选择一个key，这个可以来负责记录事务的起跳状态。commit阶段完成之后，会异步的向所有的key把它的事务状态更新掉，原子的提交就发生在primary key的身上。这也就是我们今天要讨论的这个Paxos算法的一个大致的流程。

第二个分布式的事务算法是无锁的分布式算法。那么这个分布式事务的算法主要是来自一篇论文这篇论文。这篇文章提到最核心的观点是，如果要去实现创新化隔离级别的系统，不需要做写写冲突的检测，只需要做读写冲突检测，这个系统就足够去支持创新化隔离级别。这个算法流程也比较简单的，是occ的乐观的并发控制，每个事务的修改先将它的堵集合和写集合缓存在本地。在真正提交的时候运行算法的并发控制协议。

并发控制协议也分成两部分：首先，它去做读写冲突检测，那么怎么样去检测呢？第一步是建立自己的堵集合，看一下自己在事务的运行过程中，比如做了100条数据，这100条数据是不是被变化的事务修改了？如果没有变化的事务修改，就直接将自己的写集合，有可能读了100条数据，写了200条数据。接下来将两百条数据写下去，所有事务都按照这个协议运行，就能拿到创新化的隔离级别。如何判断它的读集合有没有被并发事务修改呢？记录并发事务的写集合，如果被其它事务改了一些数据，就要做记录，然后他用自己的读集合，比如说他100条数据过一下，用一条数据到并发执行的事务去看一下是否改正在读的数据，如果有就直接就abort掉了，如果没有就进入真正的提交阶段。经典的单机并发控制协议。这两种算法是非常相似的，经典的单机MVCC，在它实验时通过锁来做协议冲突检测，即使通过锁做到了协议冲突检测，仍然不能达到创新化的隔离级别，因为存在写偏差的问题。writer的isolation是通过乐观锁来做事故更新，提交时不做协助写写冲突检测，只要做读写冲突检测。这样就支持创意级别的隔离，读写冲突检测直接解决了写的这个问题。

二、算法

比如Proclunta算法，事务执行过程是客户端要更新两条数据，比如要更新K1和K2，首先把数据发送给其中一个事务的节点，这个节点是，作为两阶段提交的协调节点，节点会创建standards的事务状态的记录。要到table server上插入一条记录，这条记录是当前事务的状态。接下来要写真正的数据，要更新的K1 K2，可能涉及多个分组，这两条数据并行发送给数据所在的Raft group的leader进程，数据就发过去了， leader进程收到数据后运行它，把数据更新发给Follow节点，这就是对应的procright阶段。

下面开始进入commit阶段，procright算法里面，通过随机选一个key，用来担当事务的状态。有一个文件来记录不同事物的状态，提交的时候插入了一个事务状态的记录，提交的时候由pending状态改成commit状态或abort状态。它是通过新生成专门的记录，来记录事务的状态。

基于lock free的并发控制，以pythonDB为例。它基本上是完整的参考了读写冲突检测无锁的论文来实现的。它实现的策略是将整个事务拆分成多个组件，比如像中心化的节点来做时间的授时。另外一个分布式的多集群节点用来做读写的冲突检测，还有一些节点做log的记录，还有一些节点来做storage system做数据最终的持久化。事务的提交过程是典型occ过程，首先是客户端去读数据，它决定要提交时把自己大号里面的保存的数据，发送给proxy的节点， proxy就担当整个事务提交的协调节点。接着数据要去获取时间戳，从中心化的授时里面请求一个时间戳，作为事务提交的执行戳，把要更新的集合分发给按照不同的冲突检测的节点，它上面记录了并发事故的读写集合，就做一个冲突检测的算法，那么这个冲突检测如果说通过之后，proxy节点再去发起真正的事务的写过程，将它的写放到一个log层上面。那storage system集群异步的拖日志。是一个分布式无锁的并发的事务控制协议。

每一个事务都会有开始时间和结束时间，这个时间是用来做什么呢？单机的数据库存的时间是在做两个事务的关系判断，要知道两个事务的大小关系，通过时间戳来做。单机是通过单调递增的事务id来做逻辑上的时钟。

在分布式环境下，不同的节点是有物理时间差的，同一个物理节点的时间也会错乱，这时如果开始了一个事务，要对位于两个节点上的key更新，这两个节点的时间戳是不一样的，如果采用单机的做法，拿到了1150的id作为事务，另一个节点时间是靠后的，即使提交了，仍然认为是堵不到这个数据的，就不符合线性一致性的要求。

三、时钟

原子时钟的服务对最核心的想法是通过GPS授时，GPS保证所有集群的节点时间戳的误差有上限。在执行事务时发现，读到的数据时间戳跟自己的时间戳在误差范围之内，它就要去等待，等物理时钟跳过误差，跳过误差后才能判断大小，在误差之内是不能判断的，这就是原子时钟的解决方案。

tso中心化授时就要解决中心化授时的一些问题。中心化节点要做单点的高可用，为了提高性能，中心化授时不用每个事务都要做时间戳。

混合逻辑时钟，始终那么混合逻辑始终的想法是什么呢？最开始纯的逻辑时钟，原理是只要事务之间有一个关系，比如事件a和事件B之间的发生有前后关系，根据他们的关系就可以赋予不同的ID，比如一个节点下面发生了两个事件，事件a和事件B之间的逻辑时钟是可以比较出来的，单机的就可以让B的逻辑时钟大于a的逻辑时钟。如果这个节点向另外一个节点发消息，需要把本地的时钟带过去对吧。可能是本机上发生了事件a、事件B，事件b要向另外一个点发送一条消息，等他它的响应。另外一条时间收到 b的消息包后，就会发出一个事件c，事件c的逻辑时钟就可以保证是小于b 的。只要有事件的串联的关系，就能把时钟构造出来。

向量时钟是可以保证一致性的，维护整个集群里面任何一个事件的发生，它不是维护单一的时钟而是维护一个向量，向量里包含了整个集群的个数，比如说集群里有100个节点，每一个时钟不是单一的数字，而是由100个数字构成的向量。向量可以保证每一次数据消息的发送，单机内部发生了事件的递推的关系，它知道在自己的纬度上增加，这就是单一纬度的时间，如果发生关系，它要把 100个整数的向量带过去，因为当前时间的逻辑时钟发送给其它的节点，还把自己观察到的其它节点的逻辑使用关系也带给其它的节点，那么其它节点的运行对每个纬度来进行更新的算法，它就能学习到整个集群里面所有实验的过程。

向量时钟虽然看起来很好，它不能做集群的扩充，集群扩充很麻烦，比如这个集群做得很大有1000个节点，向量就会变大。向量时钟更新的数据包，发送的消息也很大。逻辑时钟不能打照快。HLC混合逻辑就是一个逻辑时钟，时钟的整数的做了一些修改，做了一些增强，将整数拆分成了两部分，高52位表示当前本地的物理时钟，后12位表示在物理时钟下发生事件的逻辑关系。52位标记了它可以精确到毫秒级。在数据中心各个节点之间时钟会有偏移，偏移也是有底线的。我们通过52位的毫秒级别的本地逻辑的物理时钟，来做高位的判断。在做数据交互的时候会将物理时钟分发给其它的节点，其它节点在收到逻辑时钟后会做更新策略，它先比较下高位是否一样，比如收到一个包，高52位比自己大，说明它收到了一个来自于时间比较早的机械的请求，另一个节点比它靠前，对它来说是收到了一个未来的数据包。

它判断出自己的物理时间落后了，这时就将自己的物理时钟对维护HMC的高52位进行更新，这个过程它就学习到了最新的时间。

如果这时发现两个节点之间没有时间偏差，那这时就通过第12位来做事件的关系的维护。通过物理时钟混合逻辑时钟的理念，这样在打快照的时候，拿到的任何一个时间都可以通过解析高52位就可以大概事件发生的时间点，排查问题也比较方便。

纯逻辑的时钟，很难推算出对应的具体物理时钟的时间点，分布式一致性在做log日志时，要给每一个日志编号，它的三个节点在group里是单调递增的，分布式事物里面也需要一个像HLC有维护单调递增的需求，

那么这两者有什么关系呢？可以先看一下Raft的协议，这个共识协议和HLC分别是用来做什么的，那Raft是做什么呢？它是将数据分成不同的shat，它用来维护shat内容的数据一致性。HLC逻辑时钟维护节点之间的大小关系，Raft是group级别的。首先它们工作的层次是不一样的。另外呢，就是Raft在做每次数据写入的时候，都会分配单调递增的逻辑上的ID。HLC融合了物理始终，它实际上跟物理时钟是有关系的。不同节点之间的HLC是可以比较的，但是Raft group的Raft的日志号是没办法比较的，这个是完全没有关系的，完全隔离的。Raft是维护单条数据的事务性。因为单条数据最终要落到Raft的里面。Raft group对这三条数据做复制。HLC的作用是维护分布式事务和理念事务之间的变化关系。他来维护这个跨Raft group是如何做实验比较的？他们都是单效递增的。