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