description |
---|
PROJECT #4 - CONCURRENCY CONTROL |
这个 project 主要是实现数据库的锁管理(Lock Manager),并且支持并发查询执行。LM 负责管理事务发出的 tuple-level 锁,并且 LM 还有基于事务的隔离级别实现 Shared & Exclusive 锁的授予和释放。
下面主要是 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
*/
}
- 为了检测死锁的事务,首先应该构建一个 wait for graph。
- 然后运行 DFS 判断环的算法检测图中是否存在环。
如果发现死锁的事务,将它 Aborted 后,如何通知其他事务继续获得 tuple-lock 呢?这里采用了群友提供的思路
- 进入条件变量等待时,使用哈希表保存
txn_id_t -> RID
的映射。- 找到死锁节点后,设置为 Aborted,唤醒
txn_id_t
对应的 RID 请求队列,唤醒后进行状态检查。如果事务的状态的 Aborted,那么抛出异常。
- 对于 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 提交代码