1. 项目整体设计与思路拆解如果你正在写 CMU 15-445 2023 Fall 的 Project 4恭喜你终于到了整个课程最“玄学”的一环。前面 Buffer Pool 和 BTree 只要你盯住并发与数据结构的交互基本能撑得住P3 Query Execution 更偏向纯实现把算子逻辑搞对就行。但 P4 的 Concurrency Control 完全不一样代码量不算大核心就是 LockManager 的几个函数加一个死锁检测线程可一旦跑起来你会同时面对永久卡死、事务莫名 abort、条件变量失效、Sanitizer 报警这一套组合拳。我写这个项目时最大的感受是它不是让你“写功能”而是让你“写机制”。你要在极其有限的骨架里搭建一套多线程环境下不会出错的事务锁调度系统。项目文档里会反复强调一个概念你的锁管理器必须在高并发下依然正确且不能出现死锁或饿死。这个要求听起来简单实际做的时候你会发现任何一处“提前唤醒”“重复加锁”“忘记标记事务状态”都会带来一连串诡异行为。这个项目适合两类人一是正在上学、想把这门课完整刷完的在校生二是工作后想补数据库内核基础、准备面试或转岗的工程师。它解决的问题非常明确当多个事务同时对同一张表或同一行做读写时如何保证数据一致性同时不让系统卡死。这也是你简历上能写出来的最硬核的“并发控制”实战经历。在开始写代码之前建议你把“锁”和“闩锁latch”的区别想清楚。P2 里 BTree 用的 latch 是保护内存中的物理结构比如一个 page、一个 node线程拿到 latch 是为了防止物理数据被破坏持有时间极短。而 P4 的 lock 是数据库管理系统给上层事务用的逻辑锁保护的是“逻辑资源”比如一行数据、一张表持有时间横跨整个事务生命周期。二者互不替代P4 里你处理的是后者这是一个完全不同维度的问题。1.1 2023 Fall 版本到底让你做什么2023 Fall 的 Project 4 不像往年那样要求实现一个完整的多粒度锁管理器而是给了一个 LockManager 骨架让你的事务在执行时能够并发地读取和修改数据。项目拆成几个模块在 Transaction 类里维护每个事务当前持有的锁信息表锁集合、行锁集合、独占锁集合等。实现 LockManager 的 LockShared 和 LockExclusive分别针对表和行共四个核心入口。实现 Unlock 方法负责释放表锁和行锁并唤醒等待线程。实现一个后台死锁检测线程周期性构建 waits-for 图发现环之后选择一个事务中止。配合 TransactionManager 的 Commit 和 Abort确保锁在事务结束时全部释放。如果你拿到的是 2023 Fall 的仓库下载完代码后直接翻 src/concurrency/lock_manager.cpp里面几乎全是 TODO。打开 src/include/concurrency/lock_manager.h能看到锁管理器已经预留了表锁和行锁的内部数据结构这个 header 里的注释写得非常详细一定要逐字读。这里很多人会犯一个认知错误觉得只要 LockManager 能让两个线程“一个等另一个”就算完成了。实际上 2023 Fall 的测试框架里除了正确性测试还有性能测试。评测程序会开多个线程同时跑事务每个事务随机选择一些 key 做读写然后验证最终结果是否一致。如果你的锁管理器实现得过慢比如频繁持有全局大锁、频繁 notify_all、死锁检测线程每次都做全表扫描就会让整个吞吐量掉得厉害。1.2 为什么锁管理器要设计成“请求-等待-授予”模型理解锁管理器最好的方式是把每个锁对象看成一个“会议室”。会议室有一份记录表上面写着谁正在使用这个会议室持有者集合。新来的人如果发现会议室正被占用而自己需要的权限和当前占用者冲突就得把自己的名字写到“候补名单”里然后在一个专门的通知窗口前等着。等会议室里的人用完了管理员会广播一声候补名单上的人再根据顺序和权限判断能否进去。映射到代码里会议室就是锁对象某个 table_oid_t 或某个 RID记录表就是 LockManager 内部维护的锁请求列表候补名单就是等待队列通知窗口就是条件变量。LockManager 的职责就是协调这些会议室的使用保证任何时刻不会出现“两个事务同时以 X 模式持有同一个资源”。这里的关键设计决策是所有锁请求都必须排队但持锁不是严格的先来后到。你不能简单地把等待队列做成 FIFO因为课程允许你已经持有 S 锁的线程在请求 X 锁时进行锁升级而锁升级要优先于新来的 X 请求处理否则容易死锁。1.3 与往年版本的区别隔离级别的加入2023 Fall 项目相对往年最明显的差异是把隔离级别的概念直接做进了锁管理器。Transaction 类里有 GetIsolationLevel()可能返回 REPEATABLE_READ 或 READ_COMMITTED。这意味着你在实现 LockShared 时必须根据当前事务的隔离级别决定 S 锁是否立即释放如果是 READ_COMMITTEDS 锁在获取后要立刻调用 Unlock如果是 REPEATABLE_READ则要保留到事务结束。这个设计让项目的复杂度上了一个台阶因为你不能只在 Commit 时一把梭释放所有锁还需要在锁请求路径里嵌入“解锁”逻辑。而且 READ_COMMITTED 只对 S 锁生效X 锁无论在哪个隔离级别下都必须持有到事务结束。原因很直接写锁的作用是防止其他事务覆盖你正在修改的数据如果写锁提前释放事务还没提交其他事务就可能基于中间状态再做修改造成级联回滚问题。2. 核心细节解析与实操要点2.1 LockManager 内部数据结构的选择与理由我先说结论不需要设计特别复杂的数据结构但一定要把“锁对象”和“等待关系”这两层信息维护得清清楚楚。打开 lock_manager.h 会看到类似这样的结构省略完整实现只讲思路struct LockRequest { txn_id_t txn_id_; LockMode lock_mode_; bool granted_; }; struct LockRequestQueue { std::listLockRequest request_queue_; std::condition_variable cv_; // 当前持有该锁的事务以及对应的锁模式 std::maptxn_id_t, LockMode granted_map_; };这里最容易被忽略的是 granted_map_。很多人在刚开始实现时只维护 request_queue_把所有请求都塞进队列然后扫描整个队列看看谁能被授予。这种做法在低并发下没问题但一旦某个请求被 cancel 或升级你就很难判断当前到底是谁持有锁。granted_map_ 的作用是让你 O(1) 地知道“哪些事务已经拿到了这个锁以什么模式”。对应到 LockManager 顶层你需要两个哈希表std::unordered_maptable_oid_t, std::shared_ptr table_lock_map_;std::unordered_mapRID, std::shared_ptr row_lock_map_;每个 map 的 value 都是一个共享指针指向锁请求队列。共享指针的好处是即使某个锁对象对应的资源被删除只要还有线程在等待它这个队列就不会被提前析构避免悬空引用。还有一个非常关键的辅助字段waits_for_ 信息。课程要求死锁检测线程能够知道“哪些事务在等哪些事务”因此你的 LockManager 里最好能维护每个事务当前正在等待的锁对象集合。我在实现时选择在 LockManager 里加了一个成员std::unordered_maptxn_id_t, std::unordered_setstd::string txn_waiting_on_;这里的 std::string 可以是锁对象的 ID我用一个简单的字符串来统一表锁和行锁表锁就拼 T: table_oid行锁就拼 R: rid.ToString()方便死锁检测统一处理。这属于实现自由但不是课程要求的一部分属于我自己加的中间状态。2.2 表锁、行锁与隔离级别的联动规则很多人在 P4 栽跟头不是因为 LockTable 没写对而是因为没搞懂表锁和行锁之间的嵌套关系。规则其实很清晰要获取行锁必须先确保当前事务已经持有对应的表锁。更具体一点要获取一行的 S 锁需要先持有对应表的 S 锁在简化版中已经够用完整多粒度锁协议里是 IS 锁但 2023 Fall 只涉及 S 和 X。要获取一行的 X 锁需要先持有对应表的 X 锁。如果你在调用 LockRow(S, rid) 时发现事务还没有任何表锁就直接报错或者返回 false否则后续释放行锁时会出现表锁和行锁生命周期不匹配的问题。有一个简单的自查方法写一个 GetTableLockMode(transaction, oid) 的辅助函数返回当前事务对该表持有的锁模式每次 LockRow 前都调用它如果没有锁或者锁等级不够就先调 LockTable 升级到目标等级。隔离级别的联动主要体现在 LockShared 方法里。代码逻辑大致是void LockManager::LockShared(Transaction *txn, table_oid_t oid, bool is_row, const RID rid) { // 1. 加锁保护 LockManager 内部数据结构 // 2. 判断事务状态如果已经 aborted 直接抛异常 // 3. 将请求插入 lock request queue // 4. 检查是否与当前持有者冲突 // 5. 如果冲突则加入等待队列更新 txn_waiting_on_ // 6. 等待条件变量 // 7. 被唤醒后检查锁是否被授予以及事务是否被死锁检测线程中止 // 8. 如果事务被中止抛出 ExecutionException // 9. 如果隔离级别是 READ_COMMITTED 且是行锁获取后立即 Unlock }重点是第 9 步这个 Unlock 必须在成功获取锁之后立刻执行但不能把 Table 锁也一起释放。也就是说在 READ_COMMITTED 下一行数据读完就解锁但表锁继续持有直到事务结束。为什么要这样因为表锁的主要目的是防止 DDL 之类的操作并发修改表结构它的开销远小于行锁而且在整个事务里可能多次访问同一张表保留表锁可以减少反复获取表锁的开销。2.3 死锁检测waits-for 图的构建与裁决策略死锁检测是 P4 最抽象的模块。课程要求你启动一个后台线程每隔固定时间通常是 1 秒扫描一次当前所有锁请求找出循环等待关系然后 abort 其中一个事务。构建 waits-for 图的关键数据来源有两个一是每个锁对象的 granted_map_二是每个事务当前正在等待的锁对象。我的做法是遍历所有事务可以通过 TransactionManager 拿到所有事务的指针或者在自己的 LockManager 里增量为每个发起锁请求的事务做一个注册表。对每个正在等待的事务 t找到它在等的锁对象 L。遍历 L 的 granted_map_每一个持有者 h 都是一条有向边 t - h含义是“t 等着 h 释放锁”。如果 t 也在 granted_map_ 里且请求模式和当前持有模式不兼容比如 t 已经持有 S 锁又在等 S 锁这是同一模式理论上不会冲突需要特殊处理锁升级的情况防止把这种“等待自己”判定成死锁。这里有一个很容易踩的坑当 t 已经持有 S 锁且正在等待 X 锁时grants_map_ 中有 twaits_for 图中会有一条 t - t 的自环。如果你的死锁检测一看到环就 abort就会把正常的锁升级误判成死锁。正确处理是如果环的长度为 1 且请求者是唯一持有者应该允许锁升级而不是 abort。但课程 2023 Fall 对锁升级的支持态度比较暧昧文档里没有专门要求测试用例里也很少出现。稳妥起见我建议你在实现时对该情况单独判断至少不要一上来就 abort。选 victim 的策略上课程没有强约束但我推荐 abort txn_id 较大较新的事务。理由很简单旧事务通常已经做了更多工作回滚代价更高。你可以在检测到环之后遍历环里的所有事务找到最大 txn_id 的那个调用 TransactionManager::Abort。3. 实操过程从骨架到跑通测试3.1 环境搭建与测试命令2023 Fall 的仓库用的是 CMake Ninja。克隆代码后建议直接在 build 目录下编译mkdir build cd build cmake -DCMAKE_BUILD_TYPEDebug .. make -j8 lock_manager_test ./test/lock_manager_test如果机器核心数多把 -j8 改大一点。注意先用 Debug 模式因为测试里附带了很多检查逻辑一旦触发会打印帮助信息。等你把正确性全部跑过之后可以再切到 Release 模式去跑性能测试看 leaderboard 成绩。官方测试文件比较多关键是 lock_manager_test、transaction_test、deadlock_test、isolation_level_test。我的建议是每实现一个函数就立刻编一个对应的简单测试不要等全写完再统一跑。因为并发 bug 的定位成本极高你多写一个断言后面就能少熬一小时。3.2 LockTable / LockRow 的等待与唤醒流程先把锁请求的伪代码流程写出来这是我反复调整后觉得最不容易出错的版本LockShared(txn, oid): lock manager mutex 若 txn 状态是 ABORTED - 抛异常 获取 table_lock_map_[oid] 对应的 queue 生成 lock request {txn, SHARED, grantedfalse} 加入 queue.request_queue_ 记录 txn 在等待该锁对象用于死锁检测 loop: 若 txn 被标记 ABORTED - 从队列移除等待抛异常 若本请求是 queue 中第一个未授予请求且当前持有者集合与该请求兼容: 授予锁更新 granted_map_ 标记 grantedtrue 移除 txn_waiting_on_ break 否则: 等待 queue.cv_ 通知 若隔离级别为 READ_COMMITTED 不是表锁: 调用 Unlock(txn, oid, rid)整个流程里最容易写错的是“判断第一个未授予请求”这个逻辑。如果你只是简单地“从队头开始找”那一旦队头请求不兼容后面即使有兼容的请求也不能授予否则会破坏公平性。我在调试时发现课程没有强制要求公平调度但是为了保证高并发下不会饿死仍然建议采用“头部按序检查”的方式只有队首请求或按请求到达顺序最早的请求才有资格被授予。LockExclusive 的逻辑基本一样区别在于检查兼容性时更严格只有当 granted_map_ 为空或者只有自己且要升级时X 锁才能被授予。等待唤醒还有一个细节必须注意线程被 condition_variable 唤醒后不能直接认为锁已经拿到了。外面还有一层 while 循环重新检查锁请求是否真的被授予了。这是因为 notify_all 会唤醒所有等待线程但它们之间是竞争关系可能你的请求还没排到就被另一个线程抢了先。这种情况在 test 里经常出现属于正常现象不是 bug。3.3 事务提交、中止与锁清理锁释放的入口是 Unlock 和 TransactionManager::Commit/Abort。Commit 和 Abort 时你要遍历事务持有的所有表锁和行锁一一从 LockManager 中移除并 notify。2023 Fall 的 Transaction 类里预置了几个 lock setGetSharedLockSet() / GetExclusiveLockSet()记录行锁。GetSharedTableLockSet() / GetExclusiveTableLockSet()记录表锁。每次你成功授予一个锁都要把资源 ID 加进对应的 lock set每次释放锁都要从 lock set 里删除。很多人的 bug 出在“锁管理器都不知道这个事务持有哪些锁”于是 Abort 时漏释放导致其他事务永远等不到锁。所以你在实现 Lock 函数时必须把“在事务里记录持锁”和“在 LockManager 里记录持锁”同步做好二者缺一不可。关于锁释放顺序我没有发现课程测试有严格要求先释放表锁还是先释放行锁但为了避免极端情况下的死锁我选择先释放所有行锁再释放所有表锁。这个顺序跟正常加锁顺序先表后行正好相反符合“后加锁先释放”的直觉。4. 常见问题与排查技巧实录下面这些问题都是我在自己实现和帮同学 review 时真实遇到过的整理成速查表放在这里遇到类似情况可以直接对照。现象可能原因排查方向测试卡住不退出有线程在条件变量上永久等待检查 unlock 后是否每个等待请求都收到 notify检查 aborted 事务是否唤醒等待者死锁检测从未触发waits-for 图边构建错误打印 txn_waiting_on_ 和 granted_map_看边是否反了事务被莫名 abort死锁检测把正常锁升级判成环对自环单独处理判断是否唯一持有者锁请求永远不被授予公平性检查算法有误确认只有最早到达的请求才有资格授予数据不一致但无死锁读已提交下 S 锁释放时序不正确检查是否是行锁而非表锁被提前释放编译报错说 LockManager 不可复制内部含 mutex / condition_variable不要把 LockManager 按值传递或放进 STL 容器4.1 锁被永久阻塞死锁检测又不触发这是我遇到最多的情况。有一回我的测试在某个特定 seed 下永远卡死我怀疑是死锁但等了很久也没 abort。最后发现原因不是死锁而是两个线程都在等待同一个锁但持锁者在事务提交后没有被唤醒。罪魁祸首是 Unlock 函数里没做对 target 的精准通知。我当时对等待队列做了简化释放锁后直接 cv_.notify_all()理论上所有等待者都会醒来重新竞争。但由于等待者醒来后要先抢 LockManager 的全局 mutex而持锁线程释放锁时还握着那个 mutex这就导致某些线程饿死。具体表现是A 释放锁后B 和 C 同时被唤醒B 抢到了 mutex 并且发现自己可以持锁于是进入临界区执行逻辑C 一直抢不到 mutex处于 runnable 状态但测试主线程已经结束了整个进程就卡在退出阶段。解决方式是在 LockManager 的析构函数里遍历所有 lock request queue调用 notify_all()。同时确保 Abort 事务时把该事务的所有等待请求从队列中移除再 notify_all() 唤醒剩余线程。4.2 死锁检测线程构建了一条错误的边waits-for 的方向性特别容易搞反。正确的语义是“等待者 - 持有者”。如果你画成“持有者 - 等待者”那原来的循环等待关系就变成了反向环检测出来的死锁完全错误而且会因为 abort 了错误的 victim 导致事务无谓回滚。我建议你在死锁检测线程里加一个调试输出每当检测到一个环就把整条环路径打印出来。比如Deadlock detected: txn 2 - txn 5 - txn 7 - txn 2 Aborting txn 7这一步能显著降低你推导逻辑的难度。如果打印出来的环路径里出现了非法的节点那就是图构建错了。4.3 用 Sanitizer 和日志工具提升定位效率并发 bug 最难的地方在于不可复现。2023 Fall 的测试框架经常通过一个 random seed 来决定事务序列同一个 seed 在 Debug 和 Release 下的行为可能不一样因为时序变了。我的建议是直接用 ThreadSanitizer 编译跑测试-fsanitizethread它比 valgrind 更适合定位数据竞争。给 LockManager 增加日志开关宏定义 DEBUG_LOG把关键路径加锁、阻塞、唤醒、解锁、abort打出来。启用 AddressSanitizer 检查内存错误尤其是你在等待队列里使用裸指针时要格外谨慎。在实际使用中TSan 能帮你找到很多“你以为没竞争但实际有竞争”的问题。有一个印象很深的案例我在 LockRow 里直接对 rid 对象调用了 ToString()而这个 rid 对象的生命周期归属在 DataTable 里另一个线程可能已经把它销毁了。TSan 直接报告 heap-use-after-free这个 bug 如果靠肉眼盯着代码几乎不可能发现。5. Bonus Tasks性能优化与 Leaderboard 冲刺2023 Fall 的 Bonus 部分是 Open-ended 的性能调优最终结果根据 leaderboard 上的吞吐量排名给分。也就是说即使你正确性全部拿满如果吞吐量靠后也不会得到额外的 bonus 分。这个部分没有标准答案但根据我实际调优的经验优化方向集中在几个方面。5.1 从全局大锁走向分区锁骨架代码为了让你快速实现正确性会在 LockManager 里放一把全局的 std::mutex保护所有 table_lock_map_ 和 row_lock_map_。这把锁在最坏情况下会成为整个系统的串行点所有锁请求都要先抢这把锁然后操作自己的队列再释放。并发度一上去就变成“所有线程轮流通过一个只允许单人通过的闸门”吞吐量自然上不去。一个立竿见影的优化是按锁对象粒度拆分互斥锁。比如给每个 LockRequestQueue 内部加一把自己的 std::mutexLockTable/LockRow 先通过全局锁找到对应的 queue 指针然后立刻释放全局锁转而去操作 queue 自己的锁。这样不同资源上的锁请求可以完全并行只有访问 map 本身时才需要全局锁。但这里有一个很大的坑死锁检测线程需要遍历所有锁对象的持有者信息如果你做了锁拆分遍历时也要遵循某种加锁顺序否则可能在检测线程和请求线程之间产生新的死锁。我的做法是死锁检测过程先获取全局锁把所有 granted_map_ 和等待关系复制一份快照然后释放全局锁在快照上做图分析。快照的轻微不一致是可以接受的死锁检测本身是周期性操作不要求精确到每个瞬间。5.2 条件变量与等待队列的精细控制默认实现里释放锁后普遍用 cv_.notify_all()这个操作会让该锁对象上的所有等待线程全部醒来然后大部分线程发现自己的请求依然不兼容又回去睡觉。这种惊群效应在高并发下非常浪费。优化思路是只唤醒队首请求对应的线程。课程提供的 LockRequestQueue 里没有直接的线程 ID 到条件变量的映射但你可以给每个 LockRequest 增加一个 std::condition_variable* 指针或者在队列里额外保存一个“优先唤醒目标”的字段。释放锁时找到队列里第一个未授予的请求仅 notify 它的条件变量。这样其他线程不会被无谓唤醒等待队列的竞争压力会小很多。不过要提醒一句这个优化对正确性没有任何帮助纯粹是性能问题。如果你的正确性测试还没跑满不要轻易动这块否则只会增加调试难度。5.3 死锁检测与锁调度的调参经验死锁检测线程每 1 秒跑一次这个频率其实很保守。性能测试里事务的生命周期都很短大量事务在毫秒级完成死锁发生的概率不高。如果你每 1 秒才扫描一次碰巧在两次扫描之间发生了死锁这些事务就会白白阻塞 1 秒严重拖低吞吐量。我自己的做法是把检测周期做成动态的如果上次扫描没有发现任何环就适当拉大间隔比如从 1 秒增加到 2 秒如果发现过环就缩短间隔比如降到 200 毫秒。同时在检测线程里如果连续几次都发现了环说明系统正处于死锁高发期可以持续保持短间隔。这种自适应策略能让死锁被更快解除同时不至于让检测线程本身成为性能瓶颈。选 victim 的策略上除了选择 txn_id 最大的事务还可以结合“当前持有锁数量”作为权重持有锁数量越少的事务回滚代价越低优先 abort 它。这需要在 waits-for 图分析阶段顺便统计每个事务在环里的持锁量代码量不大但对整体吞吐量的提升比较明显。写在最后的一点经验项目写到后期你会发现P4 考验的其实是你对“阻塞”和“唤醒”这两个基本操作的理解有多深。很多同学纠结于各种精妙的数据结构但真正的难点全在条件变量的正确性上唤醒之后要重新检查状态移除等待请求时要同步更新多个结构abort 时要保证所有等待者都能被唤醒并感知到事务已经中止。我个人的体会是一定要保持代码的单步可读性。不要在 LockManager 里塞过多花哨的优化逻辑先把最朴素、最直接的方案跑通再逐层叠加性能改进。每加一层优化就全量跑一遍测试因为并发问题往往不是某一行逻辑错了而是两个看似无关的操作在时间上产生了交错。最后再分享一个小技巧在你初步实现完死锁检测后可以临时把检测周期改成 1 毫秒故意让系统频繁扫描然后观察 waits-for 图打印。这个“暴力测试法”能帮你快速暴露图构建阶段的错误比如边方向反了、节点缺失、环路径重复等问题。等图构建完全正确后再把周期调回正常值性能分和稳定性都能兼得。