KunlunBase全局死锁检测技术

事务死锁是基于事务锁的数据库系统中的常见现象，在MySQL、Oracle等单机数据库中都有相应的死锁处理机制。在KunlunBase这种分布式数据库系统中，可能发生全局死锁，存储节点的死锁处理机制无法解除，需要分布式数据库集群层面的全局死锁处理机制才能检测和解除。本文主要介绍全局死锁的发生机理和KunlunBase 集群全局死锁检测和处理机制。

本文首先介绍单机数据库中并行执行的事务为什么会发生死锁及其探测和解除方式。然后介绍分布式集群场景下的全局死锁，以及KunlunBase集群的全局死锁处理机制。

数据库事务死锁的基础知识、发生的机理和危害

数据库系统通常使用事务锁做并发控制，防止有逻辑上冲突关系的两个操作相互干扰。比如，如果一个连接conn1中用户要drop table t1;另一个连接conn2中用户发起了insert into t1 插入数据到t1, 那么这两个操作就是相互冲突的；或者conn1中要把一行R1做修改，conn2中也要对R1做修改，那么这两个操作也是冲突的。为了避免这些冲突，数据库系统在读写数据时，先锁住数据所在的表、页面和/或行，获得锁之后在执行操作，然后事务提交时再释放这些事务锁。有些数据库系统的存储引擎比如InnoDB 使用多版本并发控制(Multi-versioned concurrency control, MVCC) 做读操作的并发控制，使用事务锁做写操作的并发控制。MVCC不获取任何事务锁，因此使用MVCC做读操作的并发控制的话，读操作不会被写操作阻塞也不会形成死锁，系统可以有更高的并发性能。

从上面的例子可以看出，事务锁分为多个层级，包括表级，页级和/或行级。执行任何一个DDL或者DML语句，都需要先获得表级事务锁，然后有些系统支持页级事务锁，有些支持行级事务锁，有些两者都支持。事务锁的粒度越小，其并发程度越高。DML获取的表级锁通常是意向锁，因此多个DML获得的表级锁并不冲突，也就不影响并发性能；DDL获得的表级锁通常是非意向锁，所以一个DDL语句会与同一个表的其他DDL或者DML语句冲突。

冲突矩阵定义了数据库中针对同一个数据库对象的事务锁的冲突关系，事务锁系统根据冲突矩阵决定两个事务锁是否冲突。不同的数据库系统的锁类型以及冲突定义可以略有不同，不过下图的这部分锁类型和冲突关系是所有事务数据库系统的冲突矩阵共同的。

T.X和T.S是表级互斥和共享锁，通常对一个表执行DDL语句需要先获取其T.X

T.IX：表级意向写锁，T.IS:表级意向读锁：表级意向锁通常由DML语句获取，可以防止执行增删改查时表被truncate/drop/rename等

R.X：行级写锁，要修改、插入、删除一行时要先获得其行级写锁。如果读操作并发控制使用MVCC那么不需要行级共享锁，否则需要获取行级和表级共享锁R.S和T.S。

矩阵里面的X代表针对同一个表或者某个表的同一行的两个锁请求是冲突的，来自多个事务的事务锁请求不能同时获得；√ 表示这两个锁请求不冲突，是相容的，多个事务可以同时获得它们请求的事务锁。

冲突矩阵示例

数据库中死锁是自然发生的，发生死锁不是错误也不是数据库系统或者应用系统的bug。数据库系统必须要能够自动发现和解除死锁，然后返回错误给客户端，客户端要处理执行语句返回的错误，通常的处理方法是回滚这个事务，不过对一些应用来说一个DML操作失败了可以再试一次，那么应用软件也可以决定在收到死锁错误后重新执行同一个DML操作，或者做适当调整后再次执行它，甚至直接忽略这个失败的语句（此处理方法比较罕见）。

数据库死锁发生有以下3个条件：

1、得不到新锁事务就阻塞无法继续执行。否则就可能读到正在被改写的完全无意义和不合理的数据，也叫做“脏数据”。

2、事务不结束则不释放已持有的锁。这也叫做两阶段锁定(Two Phase Locking, 2PL)，这是一种有效减少死锁的方法，也是数据库系统事务ACID的要求。

3、形成环路等待：两个事务trx1和trx2各自获得对方需要的事务锁，就会形成环路等待条件。下图是一个环路等待条件的示例。

死锁的环路等待示例

数据库事务死锁的危害及解除

死锁如果不能尽快解除的话，会导致查询超时，语句失败，系统吞吐率下降，被锁住的对象和被卡住的事务越来越多，数据库系统逐渐无法继续运行。

目前常见的事务存储引擎都支持事务死锁的检测和解除，方法是在无法获取事务锁时以及定期由死锁处理器完成一轮死锁检测：扫描锁系统的锁等待关系，找到锁等待环路，然后选择环路中的一个事务作为所谓的victim来拒绝其锁请求，这样，这个victim事务正在执行的DML语句就会返回错误，客户端需要处理这个错误，比如回滚这个事务或者重新执行这个语句。

MySQL的InnoDB存储引擎有自己的死锁检测机制，就按照这个方法来做死锁检测和解除。

KunlunBase分布式数据库集群的全局死锁的形成机理

Klustron的存储节点Klustron-storage 目前支持InnoDB和RocksDB两种存储引擎，它们都是通过行级事务锁做插入、更新、删除的并发控制，因此其事务分支都会获取行锁（对于InnoDB来说还可能是GAP锁等特殊形式的事务锁，但对于全局死锁处理来说无需区分），这就会造成事务分支之间的锁等待关系，从而形成全局死锁。

全局死锁是一种新型的数据库事务死锁，它发生在分布式数据库集群的全局层面，是单一存储节点的死锁处理器无法发现或者解除的。不过其发生机理和发生条件与上述单机数据库情况下完全相同。

下图是一个全局死锁示例，GT1在shard1主节点SM1上的事务分支GT1.T11更新了R1, GT2在shard2主节点SM2上的事务分支GT2.T22更新了R2, 然后 GT1在SM2上的事务分支GT1.T12要更新R2，试图获取R2的行级写事务锁时被GT2.T22 阻塞，这就造成了GT1等待GT2, 记为 GT1 -> GT2；

同时, GT2在SM1上的事务分支GT2.T21要更新R1，试图获取R1的行级写事务锁时被GT1.T11 阻塞。这就造成了GT2等待GT1, 记为 GT2 -> GT1；

这就形成了环路等待条件，也就是一个全局死锁。在SM1和SM2看来，并没有发生死锁，因为在SM1看来，只有锁等待关系T21->T11, 在SM2看来，只有锁等待关系 T12->T21，因此SM1和SM2 都无法发现或者解除这个全局死锁。这时就需要KunlunBase的全局死锁处理器来做全局死锁检测和解除。

全局死锁有这几个特点：

1、存储节点事务分支的局部等待导致全局事务的等待，全局事务构成了环路等待关系。

2、在每个存储节点内部没有发生死锁（即使发生了也会由它自动解除，不在本节讨论），存储节点无法自动发现或解除全局死锁。

3、全局死锁环路中的全局事务可以是来自从多个计算节点启动的事务，也可以都来自同一个计算节点。

社区版Percona-MySQL-server 的全局死锁

对于社区版Percona-MySQL-server 来说，虽然它支持InnoDB和RocksDB两种存储引擎，但是并没有提供MySQL server层的死锁探测和解锁机制，这就导致可能在percona-server实例内部出现类似上文描述的死锁： 假设有表t1和t2, t1在InnoDB引擎中，t2在RocksDB引擎中。事务T1 更新了 表t1的一行R1，同时事务T2更新了表t2的一行R2。然后T1要更新t2.R2并且T2要更新t1.R1，此时T1和T2就发生了MySQL server层的死锁。

这个死锁是InnoDB和RocksDB都无法发现的，因为他们只能看到本引擎内部的锁表和锁对象，也就是InnoDB看到的事T1等待T2, RocksDB看到的事T2等待T1，都没有看到T1和T2相互等待的环路，也就无法解锁，只能等待锁超时完成解锁。但是锁超时通常需要若干秒，以便正常运行的负载较重的数据库系统不会因为锁超时导致语句频繁失败。这也就会导致MySQL server层的死锁带来数据更新性能显著下降。

Klustron的全局死锁检测机制可以发现和解除单一的存储节点内的跨引擎死锁，这样就可以大幅提升系统性能。

KunlunBase分布式数据库集群的全局死锁的解锁方式

与单机数据库中的死锁一样，全局死锁也是自然发生的，不是数据库系统的bug也不是应用软件的错误。KunlunBase可以自动发现和解除全局死锁，并向victim所在的连接中返回给客户端一个错误，客户端同样也要处理这个错误：回滚事务，或者重新（调整语句后）执行这个语句，或者忽略这个错误继续执行下一条语句（这样处理比较少见）。

KunlunBase发现和处理全局死锁分为以下几步：首先要从集群所有的存储集群主节点获取当前每个存储节点内的本地事务锁等待关系，从而构建全局事务锁等待关系图。然后，遍历这个图，寻找等待环路，找到一个环路就从环路中选择一个victim 来拒绝其锁请求，这样客户端就会受到语句执行错误，处理错误方式如上文所述。

构造全局事务等待图

KunlunBase的全局死锁处理器(global deadlock detector, gdd)从一个本集群的每个shard主节点M1,M2,...Mn 中获得本地事务局部事务锁等待关系图 g1,g2,...gn，使用的SQL语句如下。此语句由死锁检测后台进程发送给KunlunBase每个shard的主节点。

合并g1,g2...gn 为一个图G:全局事务等待关系图。

上述查询语句为什么就可以得到每一个存储节点内的局部等待关系g呢？因为information_schema.innodb_trx是MySQL的一个系统视图，提供了每一个运行中的事务的基本信息。我们感兴趣的是正在运行的XA事务，因为只有它们能够作为全局事务分支构成全局死锁；Information_schema.data_lock_waits 是一个事务锁等待关系的视图，从中我们可以知道任何两个innodb事务的等待关系。如上面SQL语句，三表连接就可以得到每个存储节点内活跃的XA事务的等待关系，也就是gi.

在任意的局部等待关系图gi中, 单个shard的事务分支的等待关系意味着其所属的全局事务的等待关系： ti -> tj => GTi -> GTj, ti 是GTi在shard_i的事务分支。

以GT1,GT2,...GTx 为节点，他们的等待关系为边，构成的等待关系图记为G。由于KunlunBase支持在计算节点和存储节点之间并行执行查询，所以计算节点可以异步地向多个shard的主节点发送INSERT/DELETE/UPDATE语句，然后这些语句可能在多个shard上形成局部等待关系，这就导致G的每个全局事务节点可能有多个出边，也就是一个全局事务可能同事依赖于多个全局事务。KunlunBase的gdd可以正确处理这类复杂情况。

从Klustron-1.3开始，支持了针对RocksDB引擎的全局死锁检测和解除，因此Klustron-server的全局死锁处理器还会从Klustron-storage的RocksDB 事务状态视图中获取锁等待关系，用这两套锁等待关系构成全局锁等待图，从而支持访问了混合引擎（InnoDB和RocksDB）的事务，以及单一引擎（InnoDB 或者RocksDB）的事务。

KunlunBase全局死锁的检测和解除

获得G后，就在G中做图遍历，寻找（多个）全局事务等待环路。

找到一个环路后，在环路中按照某个淘汰规则选择victim，kill掉其在所有shard的语句，G中的一个环路就解除了。目前KunlunBase支持的全局死锁淘汰策略包括一下几种，可以设置配置选项 global_deadlock_detector_victim_policy 来选择。策略名称基本可以说明策略逻辑，列表如下。每一种策略可能都有一定的道理，如果确实需要精确调整再设置，否则就使用系统默认设置。

KILL_OLDEST ：Kill掉运行时间最长的事务

KILL_YOUNGEST ：Kill掉运行时间最短的事务

KILL_MOST_ROWS_CHANGED ：Kill掉更新了行数最多的事务

KILL_LEAST_ROWS_CHANGED ：Kill掉更新了行数最少的事务

KILL_MOST_ROWS_LOCKED ：Kill掉锁住最多行的事务

KILL_MOST_WAITING_BRANCHES ：Kill掉有最多事务分支在等待事务锁的事务

KILL_MOST_BLOCKING_BRANCHES：Kill掉有最多事务分支阻塞了其他事务的事务

KunlunBase全局死锁检测和解除的代码实现位于

https://gitee.com/zettadb/kunlun/blob/main/src/backend/access/remote/remote_xact.c

全局死锁测试代码：我们测试过多种https://gitee.com/zettadb/kunlun/blob/main/src/test/kunlun/gdd/gdd2.py

在全局死锁检测算法设计和测试过程中，我们考虑过下图所有的死锁环路情况，当然，此算法能够处理包含更加复杂情况在内的所有的全局死锁情况。

KunlunBase全局死锁检测的触发和客户端处理

KunlunBase全局死锁检测机制是kunlun-server 计算节点的一个模块，在计算节点启动后作为后台进程运行，称为全局死锁检测后台进程(gdd)。如果某个增删改DML语句执行过程中，发给存储节点一个语句后超过一定时间（start_global_deadlock_detection_wait_timeout）没有返回，那么计算节点就会通知global_deadlock_detector进程触发其做一轮全局死锁检测&解除。同时，gdd也会在后台定期运行，时间间隔设置global_deadlock_detector.naptime=3s。

被选为victim的全局事务执行语句会返回错误 ER_QUERY_CANCLED 给客户端，默认情况下该事务在计算节点内部自动被回滚，用户在本事务后续语句全部忽略直到事务结束。

KunlunBase也支持MySQL的事务处理模式，如果在事务启动之前预先设置enable_stmt_subxact = true，那么语句执行错误就不会自动回滚事务，而是由客户端代码决定如何处理错误，这一机制适用于所有错误，不仅仅是死锁错误；也同时适用于MySQL连接和PostgreSQL连接。客户端收到任何语句执行错误，可以忽略该错误继续运行后续SQL语句，最后提交事务；或重新执行这个SQL语句，以及其后面的语句，最后提交事务；或直接回滚该事务，然后可以重新执行该事务。

kunlun-server会在其运行日志中记录每一次全局死锁检测所回滚的全局事务，供用户追溯和检查。

总结

KunlunBase全局死锁检测机制快速有效的发现和检测全局死锁，确保KunlunBase集群高效流畅运行。应用软件开发者需要按照本文所述正确地处理死锁错误。这样，应用系统就可以有效地处理KunlunBase分布式数据库集群运行过程中发生的死锁，保持应用系统高效运行。