我的书签
添加书签
移除书签Basic Data Structure
1. struct lock_sys_t {
2. char pad1[INNOBASE_CACHE_LINE_SIZE];
3. /*!< padding to prevent other
4. memory update hotspots from
5. residing on the same memory
6. cache line */
7. LockMutex mutex; /*!< Mutex protecting the
8. locks */
9. hash_table_t *rec_hash; /*!< hash table of the record
10. locks */
11. hash_table_t *prdt_hash; /*!< hash table of the predicate
12. lock */
13. hash_table_t *prdt_page_hash; /*!< hash table of the page
14. lock */
15. #ifdef UNIV_DEBUG
16. /** Lock timestamp counter */
17. uint64_t m_seq;
18. #endif /* UNIV_DEBUG */
19. };
Initialization at server boot up time (i.e., srv_start())
1. void lock_sys_create(
2. ulint n_cells) /*!< in: number of slots in lock hash table */
3. {
4. mutex_create(LATCH_ID_LOCK_SYS, &lock_sys->mutex);
5. lock_sys->rec_hash = hash_create(n_cells);
6. lock_sys->prdt_hash = hash_create(n_cells);
7. lock_sys->prdt_page_hash = hash_create(n_cells);
8. }
9. lock_sys_create(srv_lock_table_size);
10. /* normalize lock_sys */
11. srv_lock_table_size = 5 * (srv_buf_pool_size / UNIV_PAGE_SIZE);
Initially, we assume there might be 5 row locks per page. We might need to change the size of lock hash table which is also protected by the mutex.
1. /** Resize the lock hash tables.
2. @param[in] n_cells number of slots in lock hash table */
3. void lock_sys_resize(ulint n_cells) {
4. hash_table_t *old_hash;
5. lock_mutex_enter();
6. old_hash = lock_sys->rec_hash;
7. lock_sys->rec_hash = hash_create(n_cells);
8. HASH_MIGRATE(old_hash, lock_sys->rec_hash, lock_t, hash, lock_rec_lock_fold);
9. hash_table_free(old_hash);
10. lock_mutex_exit();
11. }
Mutex is used to sync all operations need to acquire rec/prdt locks.
1. static void row_ins_foreign_trx_print(trx_t *trx) /*!< in: transaction */
2. {
3. lock_mutex_enter();
4. n_rec_locks = lock_number_of_rows_locked(&trx->lock);
5. n_trx_locks = UT_LIST_GET_LEN(trx->lock.trx_locks);
6. heap_size = mem_heap_get_size(trx->lock.lock_heap);
7. lock_mutex_exit();
8. }
9. //Create a row lock
10. lock_t *RecLock::create(trx_t *trx, bool add_to_hash, const lock_prdt_t *prdt) {
11. //create lock record
12. lock_t *lock = lock_alloc(trx, m_index, m_mode, m_rec_id, m_size);
13. //hookup to the lock hash table
14. lock_add(lock, add_to_hash);
15. }
16. /**
17. Record lock ID */
18. struct RecID {
19. /**
20. Tablespace ID */
21. space_id_t m_space_id;
22. /**
23. Page number within the space ID */
24. page_no_t m_page_no;
25. /**
26. Heap number within the page */?????
27. uint32_t m_heap_no;
28. /**
29. Hashed key value */
30. ulint m_fold;
31. };
DeadLock Detection
Not all operations will trigger the deadlock detection. It will only be triggered by If we cannot get the required lock immediately. For example:
1. dberr_t lock_rec_insert_check_and_lock {
2. const lock_t *wait_for =
3. lock_rec_other_has_conflicting(type_mode, block, heap_no, trx);
4. if (wait_for != NULL) {
5. RecLock rec_lock(thr, index, block, heap_no, type_mode);
6. // This will trigger the deadlock detection
7. err = rec_lock.add_to_waitq(wait_for);
8. }
9. }
Basic idea:
find a circle in the wait graph (i.e. directed graph).
Basic data structure:
1. class DeadlockChecker {
2. @param trx the start transaction (start node)
3. @param wait_lock lock that a transaction wants
4. @param mark_start visited node counter */
5. DeadlockChecker(const trx_t *trx, const lock_t *wait_lock,
6. uint64_t mark_start)
7. }
Basic DFS search structure:
1. /** DFS state information, used during deadlock checking. */
2. struct state_t {
3. const lock_t *m_lock; /*!< Current lock */
4. const lock_t *m_wait_lock; /*!< Waiting for lock */
5. ulint m_heap_no; /*!< heap number if rec lock */
6. };
Basic Entry Point
1. /** Check and resolve any deadlocks
2. @param[in, out] lock The lock being acquired
3. @return DB_LOCK_WAIT, DB_DEADLOCK, or
4. DB_SUCCESS_LOCKED_REC; DB_SUCCESS_LOCKED_REC means that
5. there was a deadlock, but another transaction was chosen
6. as a victim, and we got the lock immediately: no need to
7. wait then */
8. dberr_t RecLock::deadlock_check(lock_t *lock) {
9. const trx_t *victim_trx = DeadlockChecker::check_and_resolve(lock, m_trx);
10. {
11. /* Try and resolve as many deadlocks as possible. */
12. do {
13. DeadlockChecker checker(trx, lock, s_lock_mark_counter);
14. victim_trx = checker.search();
15. } while (victim_trx != NULL && victim_trx != trx);
16. }
Background reading
INNODB LOCK
https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html
How to create a deadlock
https://stackoverflow.com/questions/31552766/how-to-cause-deadlock-on-mysql
How to detect circle in directed graph
https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ https://www.youtube.com/watch?v=joqmqvHC_Bo
