数据库内核月报

数据库内核月报 - 2020 / 04

MySQL · 引擎特性 · 8.0 Lock Manager

Author: 攀峰

Basic Data Structure

struct lock_sys_t {
char pad1[INNOBASE_CACHE_LINE_SIZE];
/*!< padding to prevent other
memory update hotspots from
residing on the same memory
cache line */
LockMutex mutex;              /*!< Mutex protecting the
locks */
hash_table_t *rec_hash;       /*!< hash table of the record
locks */
hash_table_t *prdt_hash;      /*!< hash table of the predicate
lock */
hash_table_t *prdt_page_hash; /*!< hash table of the page
lock */
#ifdef UNIV_DEBUG
/** Lock timestamp counter */
uint64_t m_seq;
#endif /* UNIV_DEBUG */
};

Initialization at server boot up time (i.e., srv_start())

void lock_sys_create(
ulint n_cells) /*!< in: number of slots in lock hash table */
{
mutex_create(LATCH_ID_LOCK_SYS, &lock_sys->mutex);
lock_sys->rec_hash = hash_create(n_cells);
lock_sys->prdt_hash = hash_create(n_cells);
lock_sys->prdt_page_hash = hash_create(n_cells);
}
lock_sys_create(srv_lock_table_size);
/* normalize lock_sys */
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.

/** Resize the lock hash tables.
@param[in]  n_cells  number of slots in lock hash table */
void lock_sys_resize(ulint n_cells) {
hash_table_t *old_hash;
lock_mutex_enter();
old_hash = lock_sys->rec_hash;
lock_sys->rec_hash = hash_create(n_cells);
HASH_MIGRATE(old_hash, lock_sys->rec_hash, lock_t, hash, lock_rec_lock_fold);
hash_table_free(old_hash);
lock_mutex_exit();
}

Mutex is used to sync all operations need to acquire rec/prdt locks.

static void row_ins_foreign_trx_print(trx_t *trx) /*!< in: transaction */
{
lock_mutex_enter();
n_rec_locks = lock_number_of_rows_locked(&trx->lock);
n_trx_locks = UT_LIST_GET_LEN(trx->lock.trx_locks);
heap_size = mem_heap_get_size(trx->lock.lock_heap);
lock_mutex_exit();
}
//Create a row lock
lock_t *RecLock::create(trx_t *trx, bool add_to_hash, const lock_prdt_t *prdt) {
//create lock record
lock_t *lock = lock_alloc(trx, m_index, m_mode, m_rec_id, m_size);
//hookup to the lock hash table
lock_add(lock, add_to_hash);
}
/**
Record lock ID */
struct RecID {
/**
Tablespace ID */
space_id_t m_space_id;
/**
Page number within the space ID */
page_no_t m_page_no;
/**
Heap number within the page */?????
uint32_t m_heap_no;
/**
Hashed key value */
ulint m_fold;
};

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:

dberr_t lock_rec_insert_check_and_lock {
const lock_t *wait_for =
lock_rec_other_has_conflicting(type_mode, block, heap_no, trx);
if (wait_for != NULL) {
RecLock rec_lock(thr, index, block, heap_no, type_mode);
// This will trigger the deadlock detection
err = rec_lock.add_to_waitq(wait_for);
}
}

Basic idea:

find a circle in the wait graph (i.e. directed graph).

Basic data structure:

class DeadlockChecker {
@param trx the start transaction (start node)
@param wait_lock lock that a transaction wants
@param mark_start visited node counter */
DeadlockChecker(const trx_t *trx, const lock_t *wait_lock,
uint64_t mark_start)
}

Basic DFS search structure:

/** DFS state information, used during deadlock checking. */
struct state_t {
const lock_t *m_lock;      /*!< Current lock */
const lock_t *m_wait_lock; /*!< Waiting for lock */
ulint m_heap_no;           /*!< heap number if rec lock */
};

Basic Entry Point

/** Check and resolve any deadlocks
@param[in, out] lock    The lock being acquired
@return DB_LOCK_WAIT, DB_DEADLOCK, or
DB_SUCCESS_LOCKED_REC; DB_SUCCESS_LOCKED_REC means that
there was a deadlock, but another transaction was chosen
as a victim, and we got the lock immediately: no need to
wait then */
dberr_t RecLock::deadlock_check(lock_t *lock) {
const trx_t *victim_trx = DeadlockChecker::check_and_resolve(lock, m_trx);
{
/* Try and resolve as many deadlocks as possible. */
do {
DeadlockChecker checker(trx, lock, s_lock_mark_counter);
victim_trx = checker.search();
} while (victim_trx != NULL && victim_trx != trx);
}

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