๐Ÿ˜‰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 ๆไบคไปฃ็ 

Last updated