TiDB 悲观锁实现原理

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

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

鸟瞰悲观锁

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

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

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

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

  1. 从 PD 获取当前 tso 作为当前锁的 for_update_ts

  2. TiDB 将写入信息写入 TiDB 的内存中(与乐观锁相同)

  3. 使用 for_update_ts 并发地对所有涉及到的 Key 发起加悲观锁(acquire pessimistic lock)请求,

  4. 如果加锁成功,TiDB 向客户端返回写成功的请求

  5. 如果加锁失败

  6. 如果遇到 Write Conflict, 重新回到步骤 1 直到加锁成功。

  7. 如果超时或其他异常,返回客户端异常信息

细说加锁

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

  1. 其他数据库一般读数据时直接上锁,然后再修改
  2. 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,所以死锁时失败的事务无法确定。

目前性能测试结果如下:

image

总结与展望

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

1赞