OVERVIEW
这个项目是关于在 BusTub 中增加对事务的支持！为了实现这个目标，你将在你的数据库系统中添加一个 lock manager，然后用它来支持并发查询的执行。lock manager 负责跟踪 tables 和 tuples 上的 lock，有五种不同的模式：intention-shared, intention-exclusive, shared-intention-exclusive, shared, and exclusive。lock manager 将处理来自事务的锁请求，向事务授予锁，并根据事务的隔离级别检查锁是否被适当释放。
PROJECT SPECIFICATION
本项目的正确性取决于你对以前项目的实现是否正确；除了 Project #3 中的 B+ Tree wrapper 外，我们不会提供解决方案或二进制文件。
Task #1 - Lock Manager
为确保事务操作的正确并发，DBMS 将使用 Lock Manager (LM) 来控制何时允许事务访问数据项。 LM 的基本思想是它维护一个由当前 active 事务持有的 lock 的内部数据结构。 事务在允许访问数据项之前要向 LM 发出锁请求。 LM 将选择：授予该事务锁 / block 该事务 / abort 该事务。
在你的实现中，整个系统将有一个全局 LM (类似于 buffer pool manager)。每当一个事务想要访问/修改一个 tuple 时，TableHeap 和 Executor 类将使用 LM 来获取 tuple records (by record id RID) 的锁。
这项任务要求你实现一个 table-level 和 tuple-level 的 LM，支持三种常见的隔离级别：READ_UNCOMMITED，READ_COMMITTED，和 REPEATABLE_READ。Lock Manager 应根据事务的隔离级别授予或释放锁。请参考 lecture slides ，了解隔离级别的复习情况。
我们为你提供了一个 Transaction context handle (include/concurrency/transaction.h)，其中有一个隔离级别属性 (i.e., READ_UNCOMMITED, READ_COMMITTED, and REPEATABLE_READ) 以及关于其获取的 locks 的信息。LM 将需要检查事务的隔离级别，并在 lock/unlock 请求上做出正确的行为。任何失败的锁操作都应该导致 ABORTED 事务状态 (隐式 abort ) 并抛出一个异常。transaction manager (include/concurrency/transaction_manager.h) 将进一步捕捉这个异常，并回滚由事务执行的写操作。
我们推荐你阅读这篇文章以回顾C++并发知识。这里有更详细的文档。
REQUIREMENTS
Task1 中你只需要修改LockManager 类 (concurrency/lock_manager.cpp and include/concurrency/lock_manager.h)。需要实现以下函数：
LockTable(Transaction, LockMode, TableOID)UnlockTable(Transction, TableOID)LockRow(Transaction, LockMode, TableOID, RID)UnlockRow(Transaction, TableOID, RID)
lock manager 采取的具体锁机制取决于事务隔离级别，是 table-level lock 还是 tuple-level lock，以及涉及的锁的类型。你应该先看一下 transaction.h 和 lock_manager.h ，熟悉我们提供的 API 和成员变量。然后，仔细阅读 [LOCK_NOTE], [UNLOCK_NOTE], 以及 lock_manager.h 中的各个函数规范，了解你的 LM 的预期行为。
我们还建议回顾一下隔离级别和 hierarchical locking 的概念，因为这些函数的实现应与提出锁定/解锁请求的事务的隔离级别兼容。你可以在 lock_manager.h 中自由添加任何必要的数据结构。你应该参考教科书中的 Chapters 15.1-15.2 和 Lecture 中涉及的隔离级别概念，以确保你的实现满足要求。
HINTS
- 虽然你的 Lock Manager 需要使用死锁检测，但我们建议在添加检测机制之前，先测试和验证你的 Lock Manager 实现的正确性，不需要任何死锁处理。
- 你将需要一些方法来跟踪哪些事务正在等待一个锁。看看
LockRequestQueueclass inlock_manager.h - 什么时候需要升级一个锁？当你需要更新 table/tuple lock 时，需要对
LockRequestQueue进行哪些操作？ - 当有锁竞争时，你将需要某种方式来通知正在等待的事务。我们推荐使用作为
LockRequestQueue的一部分提供的std::condition_variable。 - 你应该维护一个事务的状态。例如，由于解锁操作，事务的状态可能从
GROWING阶段变为SHRINKING阶段 (提示：查看transaction.h中的方法)。 - 你还应该使用
*_lock_set_跟踪事务获得的锁，这样当TransactionManager想要 commit/abort 事务时，LM 可以正确地释放这些锁。 - 将一个事务的状态设置为 ABORTED 隐式 abort 了该事务，但直到
TransactionManager::Abort被调用时才会显式地 abort。你应该通读这个函数和提供的测试，以了解它的作用，以及你的 lock manager 在 abort过程中是如何使用的。
Task #2 - Deadlock Detection
你的 lock manager 应该在后台运行死锁检测，以中止阻塞的事务。
更确切地说，这意味着一个后台线程应该定期地在运行中建立一个 waits-for 图，并打破任何循环。
REQUIREMENTS
你必须实现并用于你的周期检测以及测试的 graph API是如下：
AddEdge(txn_id_t t1, txn_id_t t2): 在你的图中添加一条从t1到t2的边。如果这条边已经存在，你不必做任何事情。RemoveEdge(txn_id_t t1, txn_id_t t2): 从你的图中删除边t1到t2。如果不存在这样的边，你不必做任何事情。HasCycle(txn_id_t& txn_id): 通过使用深度优先搜索 (DFS) 算法来寻找一个 cycle。如果找到一个 cycle，HasCycle应该在txn_id中存储该 cycle 中最年轻的 transaction id，并返回 true。你的函数应该返回它找到的第一个 cycle。如果你的图没有循环，HasCycle应该返回 false。GetEdgeList(): 返回一个代表你的图中的边的 tuple list。我们将用它来测试你的图形的正确性。(t1,t2) pair 对应于从 t1 到 t2 的一条边。RunCycleDetection(): 包含在后台运行周期检测的骨架代码。你应该在这里实现你的周期检测逻辑。
NOTES
- 你的后台线程应该在每次唤醒时都建立 graph。你不应该维护一个 graph，它应该在每次线程唤醒时被建立和销毁。
- 你的DFS周期检测算法必须是确定性的。为了做到这一点，你必须总是选择首先探索最低的 transaction id。这意味着当选择哪个未探索的节点来运行 DFS 时，总是选择具有最低 transaction id 的节点。这也意味着在探索邻居时，要按照从低到高的排序来探索它们。
- 当你发现一个 cycle 时，应中止最年轻的 transaction，通过将该 transaction 的状态设置为 ABORTED 来打破 cycle。
- 当你的检测线程被唤醒时，它负责打破所有存在的 cycle。如果你遵循上述要求，你将总是以确定的顺序找到循环。这也意味着，当你构建你的 graph 时，你不应该为 aborted 的事务添加节点，也不应该为 aborted 的事务画边。
- 你的后台检测算法可能要获取一个事务的指针
txn_id，我们增加了一个静态方法Transaction* GetTransaction(txn_id_t txn_id)来让你做这个。 - 你可以使用
std::this_thread::sleep_for来排序线程来编写测试案例。你也可以在测试用例中调整common/config.h中的CYCLE_DETECTION_INTERVAL。
HINTS
- A waits for graph is a directed graph.
- 当一个事务在等待另一个事务时，waits for graphe 会画一条边。请记住，如果多个事务在同一个对象上持有锁，一个事务可能在等待多个事务。
- 当一个事务被中止时，请确保将该事务的状态设置为
ABORTED。transaction manager 将处理明确的 abort 和 rollback。 - 一个等待锁的事务可能会被后台周期检测线程中止。你必须有办法通知等待中的事务他们已经被中止了。
Task #3 - Concurrent Query Execution
Leaderboard Task (Optional)
INSTRUCTIONS
本地测试
$ cd build
$ make lock_manager_test
$ make deadlock_detection_test
$ make transaction_test
$ ./test/lock_manager_test
$ ./test/deadlock_detection_test
$ ./test/transaction_test
SUBMISSION
make format
make check-lint
make check-clang-tidy-p4