526互联

Project #4 - Concurrency Control 题目要求

发布时间 2023-04-20 22:00:19作者: Angelia-Wang

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 实现的正确性，不需要任何死锁处理。
  • 你将需要一些方法来跟踪哪些事务正在等待一个锁。看看 LockRequestQueue class in lock_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