在上一篇《白话悲观锁》中我们介绍了什么是悲观锁，悲观锁的使用场景，以及与 MySQL 的区别和联系。本文我们将深入底层，从开发者的角度，分享悲观锁的实现细节，希望能够让大家在熟悉悲观锁的同时，具备参与到相关优化中来的能力。

此外，TiDB 先有乐观锁后有悲观锁，两者共享了不少逻辑，本文将重点关注悲观锁独有的实现细节，与乐观锁相关的更多逻辑部分大家可以在《乐观事务》查阅。

鸟瞰悲观锁

TiDB 悲观锁复用了乐观锁的两阶段提交逻辑，重点在 DML 执行时做了改造。在两阶段提交之前增加了 Acquire Pessimistic Lock 阶段, 简要步骤如下：

【与乐观锁共用】TiDB 收到来自客户端的 begin 请求，获取当前版本号作为本事务的 StartTS
TiDB 收到来自客户端的更新数据的请求: TiDB 向 TiKV 发起加悲观锁请求，该锁持久化到 TiKV。
【与乐观锁共用】client 发起 commit ，TiDB 开始执行与乐观锁一样的两阶段提交。

有了以上大致的印象后，我们具体来看看悲观锁事务的执行流程细节

细心如你，对比乐观锁的实现流程，悲观锁只有一个地方有区别，即如上图红色框内，在 TiDB 收到写入请求后，TiDB 按照如下方式开始加锁：

从 PD 获取当前 tso 作为当前锁的 for_update_ts
TiDB 将写入信息写入 TiDB 的内存中（与乐观锁相同）
使用 for_update_ts 并发地对所有涉及到的 Key 发起加悲观锁（acquire pessimistic lock）请求，
如果加锁成功，TiDB 向客户端返回写成功的请求
如果加锁失败
如果遇到 Write Conflict，重新回到步骤 1 直到加锁成功。
如果超时或其他异常，返回客户端异常信息

细说加锁

因为 TiDB 先有乐观事务，为了保证用户能够同时使用乐观事务和悲观事务，TiDB 在加悲观锁时，需要时刻确保不影响原有乐观事务的逻辑。也因此，TiDB 加悲观锁的逻辑与其他数据库的加锁逻辑迥然不同，因而存在与其他数据库不一样的地方，主要如下：

其他数据库一般读数据时直接上锁，然后再修改
TiDB 需要执行完 DML 后才会得到需要加锁的具体 key, 这个时候才会加锁。

对谁加悲观锁

在《说计算》一文的开头我们知道 TiDB 是如何将数据从关系型的表结构转化成 Key-Value 结构存储的，因而知道，TiDB 表中的一条数据，最后会对应多个 Key-Value 去存储。我们来一起回顾一下重点：这些 Key-Value 分为两类：

RowID => Value : 该类数据存储着当前对应行的所有信息。
Index Key => RowID: 索引信息，该类数据为索引到 RowID 的映射。表有多少的索引，每行数据就有多少个这样的 Key-Value。

在实现悲观锁的时候，我们根据不同的 DML 类型，制定了不同的加锁规则，旨在实现悲观锁逻辑的基础上，加更少的锁，实现更高的性能。目前加锁规则如下：

插入（ Insert）
- 如果存在唯一索引，对应唯一索引所在 Key 加锁
- 如果表的主键不是自增 ID，跟索引一样处理，加锁。
删除（Delete）
- RowID 加锁
更新 (update)
- 对旧数据的 RowID 加锁
- 如果用户更新了 RowID, 加锁新的 RowID
- 对更新后数据的唯一索引都加锁

如何加悲观锁

本章我们来仔细了解一下，TiKV 中 acquire pessimistic lock 接口的具体处理逻辑，具体步骤如下：

检查 TiKV 中锁情况，如果发现有锁
- 不是当前同一事务的锁，返回 KeyIsLocked Error
- 锁的类型不是悲观锁，返回锁类型不匹配（意味该请求已经超时）
- 如果发现 TiKV 里锁的 for_update_ts 小于当前请求的 for_update_ts(同一个事务重复更新)，使用当前请求的 for_update_ts 更新该锁
- 其他情况，为重复请求，直接返回成功
检查是否存在更新的写入版本，如果有写入记录
- 若已提交的 commit_ts 比当前的 for_update_ts 更新，说明存在冲突，返回 WriteConflict Error
- 如果已提交的数据是当前事务的 Rollback 记录，返回 PessimisticLockRollbacked 错误
- 若已提交的 commit_ts 比当前事务的 start_ts 更新，说明在当前事务 begin 后有其他事务提交过
  - 检查历史版本，如果发现当前请求的事务有没有被 Rollback 过，返回 PessimisticLockRollbacked 错误
给当前请求 key 加上悲观锁，并返回成功

以上便是悲观锁请求加锁的一个全过程。

等锁与唤醒

在上一节中我们学习了悲观锁加锁中的各种处理逻辑及异常，在这些异常中最常见的一种就是：KeyIsLocked, 也就是当前 Key 被其他事务锁住了。这种场景下，一个正常的处理逻辑便是等待这个锁被释放。那么下面我们一起来思考一下，等锁逻辑放在哪里比较合适呢？

客户端

根据 MySQL 的行为来看，一般是加一个超时逻辑。也就是当 DML 执行超时后，根据业务场景决定是否需要进行重试。这里 TiDB 行为与 MySQL 兼容，MySQL 用户不需要改任何代码直使用即可。

TiDB-Server

TiDB-Server 虽然知道事务诸多细节，但是因为 TiDB-Server 是无状态的，等待的锁所对应的事务可能并不在同一个 TiDB-Server 实例上，实现起来极其复杂。但是对 TiDB 而言，一个加锁请求超时时间是可以控制的。因此，当等锁超过一定时长（如 innodb_lock_wait_timeout），TiDB 会不再继续重试加锁和等待，向用户侧返回等锁超时的错误信息，用户可以根据业务场景和冲突程度，进行配置。

TiKV-Server

TiKV-Server 可以拿到所有等待这个 Key 的事务实时状态，似乎最适合处理等锁及唤醒处理。在 4.0 中，TiKV-Server 内存中维护了一个等锁队列来进行等锁和唤醒逻辑的处理。

等锁入队

当 TiKV 发现需要加锁的 Key 已经被其他事务锁住，需要等待时，就会将该请求放入等锁队列，直到被唤醒才会返回给 TiDB。

唤醒出队

所有等待队列中的事务出队后，都是返回 Write Conflict 异常，等待 TiDB 再进行重试。唤醒后不立刻加锁的原因是：重试后可能不需要再加该锁，如重试之后语句所需要的加锁的 key 个数可能会发生变化。

目前事务出队方式主要分为以下两种

等待的事务释放了锁，按照是否在队首唤醒方式不同，主要分为以下两种
- 按照 start_ts 排列，在等待队列的队首，会被立刻唤醒。
- 非等待队列队首请求，超过了 wake-up-delay-duration，与所有队列中的其他请求一同被唤醒。wake-up-delay-duration 的作用是让加锁更加有序同时减少无用的竞争。
超过了最长等待时间 wait-for-lock-timeout，为了防止一直被推迟导致饥饿或其他问题。

死锁检测

在《白话悲观锁》中，我们一起学习过死锁产生的原因以及 TiDB 在遇到死锁时的行为。在上一节中，我们讲了 TiKV 中是如何处理等锁与唤醒的。有等待逻辑就会造成死锁。 TiDB 目前采用了全局死锁检测的方式，如果发现当前的等锁行为会形成死锁，就会立刻返回给 TiDB 告知死锁异常，通过这种方式直接把死锁拒绝在源头。

为了保证死锁检测服务的高可用，我们将该服务放在了特定 region leader 所在的 TiKV 实例上，当需要等待锁时，如果发现不是事务加的第一个锁就需要检测死锁，死锁检测请求中会携带如下信息：

代表当前事务 ID(start_ts)
等待事务的 ID(start_ts)
等待的 Key 的信息（目前用 key 的 hash 表示）

目前死锁检测算法为：

维护全局的 wait-for-graph，该图保证无环。
每个请求会尝试在图中加一条 txn -> wait_for_txn 的 edge，若新加的导致有环则发生了死锁。
因为需要发 RPC，所以死锁时失败的事务无法确定。

目前性能测试结果如下：

总结与展望

本文主要介绍了悲观锁实现的原理细节，主要包括加锁逻辑、等锁唤醒、死锁检测。在这个过程中，帮助大家了解更多关于悲观锁内部的实现原理与细节，相信大家在读完本文后，在有所收获的同时，也想到了很多改进优化的建议。悲观锁看似复杂的逻辑背后，还是需要我们一步一步脚踏实地地去实现、完善与提升，如果大家对这一块感兴趣，想要参与到我们的具体开发工作中来，欢迎关注我们 github 上事务 SIG project，同时，也欢迎加入我们的 Slack，共同探讨与学习。

TiDB 悲观锁实现原理