MatrixOne悲观事务实现
作者：张旭 MO研发工程师
目录
1. MatrixOne的事务杂谈
2. MatrixOne事务
3. RC（Read Committed）
4. 悲观事务
本文字数：2000+字
阅读时间：20分钟
本文主要介绍 MatrixOne 的事务相关设计、思考、以及实现细节。
Part 1
MatrixOne事务特性
MO之前仅支持基于SI（Snapshot Isolation）的乐观事务。
目前已支持悲观事务以及RC隔离级别。RC和SI的事务可以同时在一个MO集群中运行。
乐观事务和悲观事务不能同时运行，集群中要么使用悲观事务模型，要么使用乐观事务模型。
Part 2
MatrixOne事务
一个MatrixOne集群由CN（Compute Node）、DN（Data Node）、LogService三个内置服务，以及一个外部的对象存储服务组成。
CN（Compute Node）
计算节点，MO中所有的繁重的工作都在CN完成。每一个事务客户端（JDBC，mysql客户端）都只会和一个CN建立链接，在这个链接上发起的事务，都会在对应的CN上创建，每个事务都会在CN创建一个workspace，来存放事务的写入的临时数据。在事务提交的时候，workspace中的事务的写入的临时数据会发送给DN节点做Commit处理。
DN（Data Node）
数据节点，所有CN的事务都会提交到DN节点。DN负责写入事务的提交日志到LogService，并且写入提交数据到内存。当内存增长满足一定条件，会把内存数据提交到对象存储，并且同时清理LogService中对应的日志。
LogService
日志节点，可以认为日志节点是DN节点的WAL。LogService使用Raft协议把日志存储为多份（默认是3份），提供高可用和强一致性。MO可以随时随地通过LogService来恢复DN节点。
LogService中存储的Log不会一直无限制的增长，当日志的大小满足一定大小的时候，DN会把存放在LogService中的Log对应的数据写入到外部对象存储，并且会Truncate掉LogService中的Log。
MO把存放在LogService中的数据称为LogTail。所以对象存储中的数据+LogTail就是MO数据库的所有的数据。
时钟方案
MO的时钟方案采用的是使用HLC，并且和内置的MORPC集成起来，来同步CN，DN之间的时钟。由于篇幅原因，这里就不展开介绍HLC了。
事务的读操作
事务的读操作发生在CN节点，能够看到MVCC的哪些版本的数据，取决于事务的SnapshotTS。
当事务确定了事务的SnapshotTS之后，就需要看到一个完整的数据集。完整的数据集包含2部分，一部分在对象存储中，还有一部分在LogTail中，这部分数据在DN的内存中。
读对象存储中的数据，可以直接访问对象存储，并且CN提供了一个Cache来加速这部分数据的读取。
读LogTail中的数据，0.8版本之前，都会根据SnapshotTS来强制和DN同步一次需要的LogTail数据，我们称之为Pull模式。Pull模式下，只有事务开始后，才主动的和DN同步LogTail，并且在不同的事务中，传输的LogTail有很多数据都是重复的。显而易见，Pull模式的性能是比较差的，延迟高，吞吐差。
0.8版本开始，MO实现了Push模式。LogTail的同步不再是事务开始的时候主动发起同步LogTail的请求。修改为CN级别的订阅的方式，DN在每次LogTail变更的时候，把增量LogTail同步给订阅的CN。
在Push模式下，每个CN都会持续不断的收到DN Push过来的LogTail，并且在CN维护一个和DN一样的内存数据结构（数据还是按照MVCC的方式组织）以及一个最后消费的LogTail的时间戳。一旦一个事务的SnapshotTS被确定，只需要等到最后消费的LogTail的时间戳>=SnapshotTS就意味着，CN拥有用了完整的SnapshotTS的数据集。
数据可见性
一个事务能够读到哪些数据，取决于事务的SnaphotTS。
如果每个事务都使用最新的时间戳作为事务的SnapshotTS，那么这个事务一定可以读到这个事务之前Commit的任何数据，这样看到的数据是最新鲜的，但是这样会付出一些性能的代价。
在Pull模式下，需要在同步LogTail的时候，在DN节点等待SnapshotTS之前的事务全部被Commit，SnapshotTS越新，需要等待的Commit越多，延迟就越大。
在Push模式下，在CN节点需要等待SnapshotTS之前的事务的Commit的LogTail被消费，SnapshotTS越新，需要等待的Commit越多，延迟就越大。
但是在很多时候，我们不需要一直看到最新的数据，MO目前给了2种数据新鲜度级别：
永远看到最新的数据，SnapshotTS使用当前时间戳
使用当前CN节点消费完的最大LogTail时间戳作为SnapshotTS
对于第2种方式，好处是事务没有任何延迟，就可以立即开始读写数据，因为满足条件的LogTail都已经全部具备了，性能和延迟会表现的很好。但是带来的问题就是同一个数据库链接上的多个事务，有可能后一个事务看不到前一个事务的写入操作，这是因为后一个事务开始的时候，DN还没有把前一个事务的Commit的LogTail Push到当前CN，这样后一个事务就会使用一个较早的SnapshotTS，导致看不到之前事务的写入。
为了解决这个问题，MO维护了2个时间戳，一个是当前CN最后一个事务的CommitTS记做CNCommitTS，一个是当前Session（数据库连接）最后一个事务的CommitTS记做SessionCommitTS。并且给出了2个数据可见性的级别（我们把当前CN消费的最大的LogTail的TS记做LastLogTailTS）：
Sessin级别的数据可见性，使用Max(SessionCommitTS, LastLogTailTS)作为事务的SnapshotTS，这样保证了一个Session上发生的事务的数据的可见性。
CN级别的数据可见性，使用Max(CNCommitTS, LastLogTailTS)作为事务的SnapshotTS，这样保证了同一个CN上发生的事务的数据的可见性。
冲突处理
MO以前的事务模型是乐观事务，所有的冲突处理都发生在Commit阶段，在DN处理。冲突处理比较简单，就不展开了，主要就是检查写写冲突，检查事务的[SnapshotTS, CommitTS]之间有没有交集。
Part 3
RC（Read Committed）
上面的章节主要介绍了MO的事务的处理。MO之前只支持SI的隔离级别，基本MVCC来实现的，数据都是有多版本的。目前已支持RC（Read Committed）事务的隔离级别。
需要考虑在多版本上实现RC的隔离级别，对于SI的事务来说，在事务的生命周期，需要保持一个一致性的Snapshot，不管什么时候去读，读到数据都是一样的。对于RC需要看到最新的提交数据，可以理解成这个一致性的Snapshot不再是事务生命周期的，而是属于每个查询。每个查询开始的时候，使用当前的时间戳来作为事务的SnapshotTS，来保证查询可以看到查询之前的提交的数据。
RC模式下，对于带有更新的语句（UPDATE, DELETE, SELECT FOR UPDATE），一旦遇到写写冲突，意味着查询修改的数据被其他的并发事务修改了，由于RC需要看到最新的写入，所以这个时候，一旦冲突的事务提交了，那么需要更新事务的SnapshotTS，重试。
Part 4
悲观事务
本章节主要介绍MO如何实现悲观事务，以及一些设计思考。
需要解决的核心问题
MO实现悲观事务需要有一些问题需要解决：
如何提供锁服务
锁服务，用来锁住单条记录，一个范围，甚至一个Table。
可扩展的锁服务的性能
去掉Commit阶段的冲突检测
悲观模式下，MO集群存在多个DN的情况下，如何确保去掉Commit阶段的冲突检测是安全的。
锁服务
MO已实现了LockService来提供锁服务。提供加锁，解锁，锁冲突检测，锁等待以及死锁检测的能力。
LockService不是一个独立部署的组件，是CN的一个组件。在一个MO集群中，与多少个CN就有多少个LockService实例。
LockService内部会感知到集群中其他LockService的实例，并且协调集群中的所有的LockService实例一起工作。每个CN都只会访问当前节点的LockService实例，不会感知到其他LockService实例。对于CN来说，当前节点的LockService表现的和单机组件一样。
4.2.1 LockTable
一个Table的锁信息都放在一个叫LockTable的组件中，一个LockService会包含很多的LockTable。
MO集群中，任意一个LockService第一次访问一个Table的锁服务的时候，会创建一个LockTable实例，这个LockTable会被挂载到这个CN的LockService实例中。这个LockTable在LockService内部被标记为一个LocalLockTable，表示这个LockTable是一个本地的LockTable。
当其他CN的也访问这个Table的锁服务的时候，这个CN对应的LockService也会持有一个这个Table的LockTable，但是会被标记为RemoteLockTable，来表示这个是一个在其他LockService实例上的LockTable。
所以在整个MO集群中，一个LockTable会有1个LocalLockTable和N个RemoteLockTable实例。只有LocalLockTable是真正保存锁信息的，RemoteLockTable就是一个访问LocalLockTable的代理。
4.2.2 LockTableAllocator
LockTableAllocator是用来分配LockTable的组件，在内存中记录了MO集群中所有的LockTable的分布情况。
LockTableAllocator不是一个独立部署的组件，是DN的一个组件。
LockTable和LockService的绑定是会发生变化的，比如LockTableAllocator检测到CN下线，绑定关系就会发生变化，每次发生变化，绑定版本号都会递增。
在[事务开始，事务提交]的时间窗口中，LockTable和LockService的绑定关系是有可能变化的，这种不一致带来了数据冲突，导致悲观事务模型失效。所以LockTableAllocator是一个DN的组件，在处理事务Commit之前，检查一下绑定版本是否有变化，如果发现一个事务访问过的LockTable的绑定关系过时了，就会abort掉这个事务，来确保正确性。
4.2.3 分布式死锁检测
所有的活跃事务所持有的锁会分布在多个LockService的LocalLockTable中。所以我们需要一个分布式的死锁检测机制。
每个LockService中都有一个死锁检测模块，检测机制大致是这样：
在内存中为每一个锁维护一个等待队列；
当一个新的事务发生冲突的时候，需要把这个事务加入到锁持有者的等待队列中；
启动一个异步任务，递归的查找这个等待队列中所有的事务所持有的锁，检查是否有等待的环。如果遇到远程事务的锁，使用RPC来获取远程事务持有的所有的锁信息。
4.2.4 可靠性
整个锁服务的关键数据，都是存放在内存的，比如锁信息以及LockTable和LockService的绑定关系。
对于LocalLockTable内部记录的锁信息，如果CN宕机，那么和这个CN链接的事务都会失败，因为数据库连接断开了。然后LockTableAllocator会重新分配LockTable和LockService的绑定关系，整个锁服务可以正常服务。
LockTableAllocator运行在DN中，一旦DN宕机，HAKeeper会修复一个新的DN，所有的绑定关系在新DN全部失效，新DN全部没有，这意味着所有的当前活跃事务都会因为绑定关系不匹配提交失败。
如何使用锁服务
为了优雅的使用锁服务，MO实现了一个Lock的算子，这个算子负责调用和处理锁服务。
SQL在Plan阶段，如果发现是悲观事务，会处理对应的情况，在执行的阶段，会在合适的位置插入Lock算子。
>>> Insert
对于insert操作，Plan阶段会在Insert其他的算子之前首先放入Lock算子，后续执行的时候，只有加锁成功后，才会执行后续的算子。
>>> Delete
和Insert类似，也是在Plan阶段在Delete的其他算子之前放入Lock算子，后续执行的时候，只有加锁成功后，才会执行后续的算子。
>>> Update
Update在Plan阶段会被拆解成Delete+Insert，所以会有2次加锁的阶段（如果没有修改主键，那么会优化成1次加锁，Insert阶段就不会加锁）。