😉Concurrency Control

PROJECT #4 - CONCURRENCY CONTROL

这个 project 主要是实现数据库的锁管理（Lock Manager），并且支持并发查询执行。LM 负责管理事务发出的 tuple-level 锁，并且 LM 还有基于事务的隔离级别实现 Shared & Exclusive 锁的授予和释放。

TASK #1 - LOCK MANAGER

下面主要是 LM 需要实现的函数的思路，注意每个调用下面的每个函数应该先获得 LM 的 latch_。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
bool LockManager::LockShared(Transaction *txn, const RID &rid) {
    // Note that: READ UNCOMMITTED no S-Lock.
    /**
     * 1. Checking txn state. Txn should abort if its state isn't growing.
     * 2. Append lock request to this RID request queue. If the rid exist X-Lock previous, 
     *	  then txn blocked(lock_table_[rid].cv_.wait()). Otherwise S-Lock can granted.
     * 3. The S-Lock request is granted.
     */
}
bool LockManager::LockExclusive(Transaction *txn, const RID &rid) {
    // Note that: READ UNCOMMITTED no S-Lock.
    /**
     * 1. Checking txn state. Txn should abort if its state isn't growing.
     * 2. Append lock request to this RID request queue. If the rid exist S/X-Lock previous,
     *	  then txn blocked. Otherwise X-Lock can granted.
     * 3. X-Lock can be acquired only if txn in front of queue. Otherwise, it will be blocked.
     * 4. the X-Lock request is granted.
     */
}
bool LockManager::LockUpgrade(Transaction *txn, const RID &rid) {
    /**
     * 1.1 Checking txn state. Txn should abort if txn's state isn't growing.
     * 1.2 Whether another txn already ready upgrading.
     * 2. find correct postion to upgrade S-Lock to X-Lock
     * 3. Update txn request lock message.
     */
}
bool LockManager::Unlock(Transaction *txn, const RID &rid) {
    /**
     * 1. If txn doesn't have any this tuple lock, then return false.
     * 2. Delete this txn in request queue, and release tuple lock hold by txn.
     * 3. txn's state is growing when txn release lock, then set txn state is shrinking,
     *	  so txn can't acquire any lock. Note that: it is used in REPEATABLE READS isolation level
     */
}

TASK #2 - DEADLOCK DETECTION

  1. 为了检测死锁的事务，首先应该构建一个 wait for graph。

  2. 然后运行 DFS 判断环的算法检测图中是否存在环。

如果发现死锁的事务，将它 Aborted 后，如何通知其他事务继续获得 tuple-lock 呢？这里采用了群友提供的思路

  1. 进入条件变量等待时，使用哈希表保存 txn_id_t -> RID 的映射。

  2. 找到死锁节点后，设置为 Aborted，唤醒 txn_id_t 对应的 RID 请求队列，唤醒后进行状态检查。如果事务的状态的 Aborted，那么抛出异常。

TASK #3 - CONCURRENT QUERY EXECUTION

  • 对于 SeqScan：如果隔离级别是 READ_UNCOMMITTED，则不需要加锁；如果隔离级别是 READ_COMMITTED 和 REPEATABLE_READ，则访问某个 RID 时需要对它加 S-Lock

  • 对于 Delete 和 Update：如果当前 RID 拥有 S-Lock，则需要将 S-Lock 升级为 X-Lock，否则对这个 RID 加 X-Lock

测试/验证/打包

  • 测试

1
2
3
4
5
cd build
make lock_manager_test
make transaction_test
./test/lock_manager_test
./test/transaction_test

  • 格式验证

1
2
3
make format
make check-lint
make check-clang-tidy

  • 打包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
zip project4-submission.zip src/include/buffer/lru_replacer.h src/buffer/lru_replacer.cpp \
	src/include/buffer/buffer_pool_manager.h src/buffer/buffer_pool_manager.cpp \
	src/include/storage/page/b_plus_tree_page.h src/storage/page/b_plus_tree_page.cpp \
	src/include/storage/page/b_plus_tree_internal_page.h src/storage/page/b_plus_tree_internal_page.cpp \
	src/include/storage/page/b_plus_tree_leaf_page.h src/storage/page/b_plus_tree_leaf_page.cpp \
	src/include/storage/index/b_plus_tree.h src/storage/index/b_plus_tree.cpp \
	src/include/storage/index/index_iterator.h src/storage/index/index_iterator.cpp \
	src/include/catalog/catalog.h src/include/execution/execution_engine.h src/include/storage/index/index.h \
	src/include/execution/executor_factory.h src/execution/executor_factory.cpp \
	src/include/execution/executors/seq_scan_executor.h src/execution/seq_scan_executor.cpp \
	src/include/execution/executors/index_scan_executor.h src/execution/index_scan_executor.cpp \
	src/include/execution/executors/insert_executor.h src/execution/insert_executor.cpp \
	src/include/execution/executors/update_executor.h src/execution/update_executor.cpp \
	src/include/execution/executors/delete_executor.h src/execution/delete_executor.cpp \
	src/include/execution/executors/nested_loop_join_executor.h src/execution/nested_loop_join_executor.cpp \
	src/include/execution/executors/nested_index_join_executor.h src/execution/nested_index_join_executor.cpp \
	src/include/execution/executors/limit_executor.h src/execution/limit_executor.cpp \
	src/include/execution/executors/aggregation_executor.h src/execution/aggregation_executor.cpp \
	src/include/storage/index/b_plus_tree_index.h src/storage/index/b_plus_tree_index.cpp \
	src/concurrency/lock_manager.cpp src/include/concurrency/lock_manager.h

然后前往 https://www.gradescope.com 提交代码

PreviousQuery ExecutionNextCMU 15-721

Last updated