๐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
35bool 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
ไธบไบๆฃๆตๆญป้็ไบๅก๏ผ้ฆๅ ๅบ่ฏฅๆๅปบไธไธช wait for graphใ
็ถๅ่ฟ่ก DFS ๅคๆญ็ฏ็็ฎๆณๆฃๆตๅพไธญๆฏๅฆๅญๅจ็ฏใ
ๅฆๆๅ็ฐๆญป้็ไบๅก๏ผๅฐๅฎ Aborted ๅ๏ผๅฆไฝ้็ฅๅ ถไปไบๅก็ปง็ปญ่ทๅพ tuple-lock ๅข๏ผ่ฟ้้็จไบ็พคๅๆไพ็ๆ่ทฏ
่ฟๅ ฅๆกไปถๅ้็ญๅพ ๆถ๏ผไฝฟ็จๅๅธ่กจไฟๅญ
txn_id_t -> RID็ๆ ๅฐใๆพๅฐๆญป้่็นๅ๏ผ่ฎพ็ฝฎไธบ 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
5cd build
make lock_manager_test
make transaction_test
./test/lock_manager_test
./test/transaction_testๆ ผๅผ้ช่ฏ
1
2
3make 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
20zip 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 ๆไบคไปฃ็
Last updated