锁机制

OceanBase 数据库使用了多版本两阶段锁来维护其并发控制模型的正确性，锁机制是保证正确的数据并发性和一致性很重要的一点。

OceanBase 数据库的锁机制使用了以数据行为级别的锁粒度。同一行不同列之间的修改会导致同一把锁上的互斥；而不同行的修改是不同的两把锁，因此是无关的。类似于其余的多版本两阶段锁的数据库，OceanBase 数据库的读取是不上锁的，因此可以做到读写不互斥从而提高用户读写事务的并发能力。对于锁的存储模式，选择将锁存储在行上（可能存储在内存与磁盘上）从而避免在内存中维护大量锁的数据结构。其次，会在内存中维护锁之间的等待关系，从而在锁释放的时候唤醒等待在锁上面的其余事务。

锁机制的使用

在深入之前，我们先来看一下如何使用 OceanBase 数据库的行锁能力。如下所示是一个很常见的业务 SQL 来更新货物的信息。

UPDATE GOODS
SET    PRICE = ?, AMOUNT = ?
WHERE  GOOD_ID = ?
AND    LOCATION = ?;

在上述 SQL 中，根据用户填入的货物 ID 和地址，去更新对应的价格和存量。对应事务中的一个 SQL，在事务结束前，对应货物 ID 和 地址的数据的一行会被加上行锁，所有并发的更新都会被阻塞并等待。从而预防并发的修改导致的脏写（Dirty Write）。由此可见用户在更新数据的同时，隐式地为修改的数据行上加上了对应的锁，用户无需显示地指示锁的范围等的情况下, 就可以依赖 OceanBase 数据库内部的机制做到并发控制的效果。

当然用户可以显式地指定使用锁机制。如下所示是一个很常见的业务 SQL 来互斥地获取货物的信息。

SELECT PRICE, AMOUNT
FROM   GOODS
WHERE  GOOD_ID = ?
AND    LOCATION = ?
FOR UPDATE;

在上述 SQL 中，根据用户填入的货物 ID 和地址，去获取对应的价格和存量。对应事务中的一个 SQL，在事务结束前，对应货物 ID 和地址的数据的一行会被加上行锁，所有并发的更新都会被阻塞并等待。从而做到用户指定的显示加锁。在不同的业务需求下，是极其重要的一点。

锁机制的粒度

OceanBase 数据库支持表锁和行锁，并且行锁是互斥的。

表锁主要是用来实现一些较为复杂的 DDL 操作，用于在操作期间阻止对整个数据库表的并发访问，以确保事务的原子性和一致性。表锁的粒度较大，因此能够锁定的对象比行锁更多，但它也会减少并发性，因为其它所有尝试访问该表的操作都会被阻塞，直到这个表锁被释放。表锁通常用于那些无法细分锁定级别（如行锁或页锁）的场景，或者在知道接下来的操作会影响表中的大部分数据时使用。这种锁通常用于数据定义语言（DDL）操作，如创建或修改表的结构。

在事务处理方面，当更新同一行的不同列时，由于OceanBase 使用行锁，不同事务会互相阻塞，这样做是为了减少锁数据结构在行上的存储开销。而在更新不同行的数据时，事务之间不会互相影响，实现事务的并发执行。

锁机制的互斥

OceanBase 数据库使用了多版本两阶段锁，事务的修改每次并不是原地修改，而是产生新的版本。因此读取可以通过一致性快照获取旧版本的数据，因而不需要行锁依旧可以维护对应的并发控制能力，因此能做到执行中的读写不互斥，这极大提升了 OceanBase 数据库的并发能力。比较特殊的是 SELECT ... FOR UPDATE，此类执行依旧会加上行锁，并与修改或 SELECT ... FOR UPDATE 产生互斥与等待。而修改操作则会与所有需要获取行锁的操作产生互斥。

锁机制的存储

OceanBase 数据库的锁存储在行上，从而减少内存中所需要维护的锁数据结构带来的开销。在内存中，当事务获取到行锁时，会在对应的行上设置对应的事务标记，即行锁持有者。当事务尝试获取行锁时，会通过对应的事务标记发现自己不是行锁持有者而放弃并等待或发现自己是行锁持有者后获得行的使用能力。当事务释放行锁后，就会在所有事务涉及的行上解除对应的事务标记，从而允许之后的事务继续尝试获取。

当数据被转储到 SSTable 后，在宏块内部的数据上，记录着对应的事务标记。其余事务依旧需要通过事务标识来辨识是否可以允许访问对应的数据。与内存中的锁机制不同的是，由于 SSTable 不可变的特性，无法在事务释放行锁后，立即清除宏块内部的数据上的事务标记。当然依旧可以通过事务标识来确认找到对应的事务信息来确认事务是否已经解锁。

锁机制的释放

类似于大部分的两阶段锁实现，OceanBase 数据库的锁在事务结束（提交或回滚）的时候释放的，从而避免数据不一致性的影响。OceanBase 数据库还存在其余的释放时机，即 SAVEPOINT，当用户选择回滚至 SAVEPOINT 后，事务内部会将 SAVEPOINT 及之后所有涉及数据的行锁，全部根据 OceanBase 数据库锁机制的互斥 中介绍的机制进行释放。

锁机制的唤醒

为了唤醒事务，当产生互斥后，会在内存中维护行与事务的等待关系，如图所示，行 A 被事务 B 持有，被事务 C 与事务 D 等待。此等待关系的维护，是为了行锁释放的时候可以唤醒对应的事务 C 与 D。当事务 B 释放行 A 后，会根据顺序唤醒事务 C，并依赖事务 C 唤醒事务 D。

除了行与事务的等待关系，OceanBase 数据库可能会维护事务与事务的等待关系。为了减小对于内存的占用，OceanBase 数据库内部可能会将行与事务的等待关系转换为事务与事务的等待关系。如图所示，行 A 被事务 B 持有，被事务 C 与事务 D 等待，并被转换为事务 B 被事务 C 与事务 D 等待。当事务 B 结束后，由于不明确知道行之间的锁等待关系，会同时唤醒事务 C 与事务 D。

锁机制的死锁

锁机制的实现会导致死锁，死锁是指对于资源的循环依赖，举例来说，当事务 A 与事务 B 同时获取资源 C 与 D 的情况下，若事务 A 优先获取到资源 C 并去获取资源 D；而事务 B 优先获取到资源 D 并去获取资源 C。此时若没有任何人愿意放弃自己已经获取到的资源，就没有事务可以正常结束。

基于超时的死锁解决

OceanBase 数据库 V3.2 版本之前，未包含主动死锁检测的能力。因此我们主要是依赖超时回滚机制来解决业务逻辑上的死锁。

存在三种超时机制用来解决对应的问题：

• 锁超时机制：配置项名称为 ob_trx_lock_timeout，默认为语句超时时间，若加锁等待超过锁超时时间，则会回滚对应的语句，并返回锁超时对应的错误码。此时，由于某一个循环依赖中的资源依赖已经消失，因此就不再存在死锁。以事务 B 获取资源 C 超时为例，只要事务 B 结束，则事务 A 就可以获取到对应的资源 D。

• 语句超时机制：配置项名称为 ob_query_timeout，默认为 10s，若加锁等待超过语句超时时间，则会回滚对应的语句，并返回语句超时对应的错误码。此时，由于某一个循环依赖中的资源依赖已经消失，因此就不再存在死锁。以事务 B 获取资源 C 超时为例，只要事务 B 结束，则事务 A 就可以获取到对应的资源 D。

• 事务超时机制：配置项名称为 ob_trx_timeout，默认为 86400s，若加锁等待超过事务超时时间，则会回滚对应的事务，并返回语句事务对应的错误码。由于某一个循环依赖中的资源依赖已经消失，因此就不再存在死锁。以事务 B 超时为例，由于事务 B 结束，事务 A 就可以获取到对应的资源 D。

主动死锁检测

从 OceanBase 数据库 V3.2 版本开始，除了以上基于超时的死锁解决机制，我们还实现了主动死锁检测机制。

目前 OceanBase 数据库实现的死锁检测称为 LCL（Lock Chain Length）死锁检测方案，是一种基于优先级的多出度分布式死锁检测方案，OceanBase 数据库的死锁检测算法可以保证不误杀或多杀事务。

基于优先级是指，在互相形成死锁的多个事务中，LCL 死锁检测方案总是倾向于杀掉其中优先级最低的事务来解除死锁，目前在死锁检测中事务的优先级指标主要为事务的开启时间，越晚开启的事务具有越低的优先级。

多出度是指，每一个事务都可以同时等待超过一个的其他事务。

分布式死锁检测是指，每一个代表事务进行死锁检测的节点仅知道该节点自身的依赖信息，在不需要全局的锁管理器的情况下即可探测节点间的死锁。

实现原理

一个分布式事务为提高执行效率通常需要同时访问多个分区的数据，并可能同时发现存在多个锁冲突事件，此时为提高死锁检测的效率，可以描述出一个事务同时等待多个事务的单向依赖的有向边，称为多出度。

常见的死锁检测方案多采用路径推动算法（path-pushing algorithm），这种算法应用在多出度场景下大多存在多杀以及误杀的问题。LCL 死锁检测方案采用的是一种经过特殊设计的边跟踪算法（edge-chasing algorithm），在 LCL 死锁检测方案中，每个节点维护两个状态，分别称为深度值以及令牌值，为防止多杀，一个节点维护的令牌值数量不能多于一个，令牌值之间可以比较，并使大的令牌值覆盖小的令牌值，如此可以保证在一个环路中，只有最大令牌值的节点可以探测到死锁，可以避免多杀的问题。

在边跟踪算法中死锁探测的基本原理是令牌值可以经由自己发出后回到自己，但是在多出度场景下采用单令牌值设计时可能出现死锁环路中最大的令牌值并不属于这个环路中的任何一个节点的情况，此情况下将检测不到死锁，该场景称为"环外污染"，因此 LCL 死锁检测方案引入了"路径深度"概念，每个节点维护一个路径深度值，在环路中的节点的路径深度值随时间推移可以无限增长，而不在环路中也不被环路中节点所触达的节点的路径深度值存在增长上限，约束节点只能接受路径深度至少和自己一样大的节点传递的令牌来避免"环外污染"，并通过定期清理节点上当前的令牌值来消除在算法运行早期阶段已经出现的"环外污染"，由此保证算法工作在多出度下的正确性。

具体实现

当一个事务 A 遇到加行锁失败时，事务 A 在等待行锁解开的同时，会获取持有行锁的事务 B 的 ID，并创建出一个死锁检测节点 a（下文称为 Detector(a)），为 Detector(a) 记录到事务 B 的 Detector(b) 的单向依赖关系。

每个节点要维护以下状态：

当一个 Detector 节点被建出时生成两个令牌状态，一个公共令牌值（public label），一个私有令牌值（private label），它根据自己的优先级生成一个全局唯一性令牌（优先级越高的节点，令牌值越大），并用其初始化两个令牌值，并同时生成一个初始为 0 的深度值 lclv ((Lock Chain Length)。

每一个 Detector 节点都维护一个依赖列表，列表中记录了依赖的其他节点的网络位置信息。

从时间轴划分，每 1.4s 划分为一个 LCL 周期。

在每个周期开始的时候，每个节点重置自己的 public label 为自己的 private label。

LCL 周期的前 700ms 称为 LCLP 周期（Lock Chain Length Proliferating），每个节点在该周期中定期将自己的状态的 lclv 值发送给依赖列表中的所有下游节点，每个节点在接收到上游节点发送来的 lclv 值后，将自己的 lclv 值更新为 max(lclv, received_lclv + 1)。

LCL 周期的后 700ms 称为 LCLS 周期（Lock Chain Length Spreading），每个节点在该周期中定期将自己的状态的 { lclv, public label } 发送给依赖列表中的所有下游节点，每个节点在接收到上游节点发送来的值后，若其 lclv 值不小于自己当前的 lclv 值，则更新自己的 public label 为 min(public label, received public label)，更新自己的 lclv 值为 received lclv。

检测到死锁：当一个节点收到的 public label 是自己的 private lavel 时，它就发现了死锁。

视图

视图 CDB_OB_DEADLOCK_EVENT_HISTORY 记录了所有发生过的死锁事件以及参与这些事件的事务，并注明了在一个死锁事件中哪个事务最终被 kill 掉。