An article to talk about the internal implementation mechanism of Mysql lock

This article will talk about the internal implementation mechanism of Mysql lock. I hope it will be helpful to everyone.

Note: The codes listed are all from Mysql-5.6

## Although relational databases are becoming more and more popular nowadays The more similar they are, but the implementation mechanisms behind them may be quite different. In terms of actual use, because of the existence of SQL syntax specifications, it is not difficult for us to be familiar with multiple relational databases, but there may be as many lock implementation methods as there are databases.

Microsoft Sql Server2005 only provided page locks before. It was not until the 2005 version that it began to support

optimistic concurrency, pessimistic concurrency. Row-level locks are allowed in optimistic mode. In Sql In the design of Server, locks are a scarce resource. The more locks there are, the greater the overhead. In order to avoid a cliff-like drop in performance due to a rapid increase in the number of locks, it supports a method called lock upgrade mechanism, once the row lock is upgraded to a page lock, the concurrency performance returns to the original point.

In fact, even in the same database, different execution engines still have different interpretations of the lock function. For MyISAM, it only supports table locks. Concurrent reading is acceptable, but concurrent modification is insufficient. Innodb is very similar to Oracle, providing support for

non-locking consistent reads and row locks. The obvious difference from Sql Server is that as the total number of locks increases, Innodb only needs to pay A small price to pay.

Row lock structure

Innodb supports row locks, and there is no particularly large overhead in describing the locks. Therefore, there is no need for a lock upgrade mechanism as a rescue measure after a large number of locks cause performance degradation.

Excerpted from the

lock0priv.h file, Innodb’s definition of row locks is as follows:

/** Record lock for a page */
struct lock_rec_t {
    /* space id */
    ulint  space;	
    
    /* page number */
    ulint  page_no;
    
    /**
     * number of bits in the lock bitmap; 
     * NOTE: the lock bitmap is placed immediately after the lock struct 
     */
    ulint  n_bits;			
};

It is not difficult to see that although concurrency control can be refined to the row level, locks are based on pages Granular organizational management. In the design of Innodb, the only data page can be determined through the two necessary conditions of space id and page number. n_bits indicates how many bits are needed to describe the row lock information of the page.

In the same data page, each record is allocated to the unique continuous increase number: Heap_no. If you want to know if a line of record is locked, you only need to determine whether the number of the position of the position chart Heap_no can be one. Since the lock bitmap allocates memory space based on the number of records in the data page, it is not explicitly defined, and the page records may continue to increase, so a space of LOCK_PAGE_BITMAP_MARGIN size is reserved.

/** 
 * Safety margin when creating a new record lock: this many extra records
 * can be inserted to the page without need to create a lock with 
 * a bigger bitmap
 */
#define LOCK_PAGE_BITMAP_MARGIN	 64

Assume that the data page with space id = 20, page number = 100 currently has 160 records, and the records with heap_no of 2, 3, and 4 have been locked, then the corresponding lock_rec_t structure and data page should be like this Depiction:

Note:

The lock bitmap in the memory should be linearly distributed. The two-dimensional structure shown in the figure is In order to facilitate the description
• The bitmap and lock_rec_t structures are a continuous memory, and the reference relationship in the figure is also required for drawing

You can see the second, third and fourth positions of the bitmap corresponding to the page Setting all to one describes that the memory consumed by a data page row lock is quite limited from the perspective of perception. How much does it occupy specifically? We can calculate:

160 / 8 8 1 = 29byte.

160 records correspond to 160bit
• 8 is because 64bit needs to be reserved
• 1 is because 1 byte is reserved in the source code

There is an extra 1 here, probably to avoid the problem of small result values ​​due to integer division. If there are 161 records, if it is not 1, the calculated 20 bytes are not enough to describe the lock information of all records (without using reserved bits).

Excerpted from

lock0priv.h file:

/* lock_rec_create函数代码片段 */
n_bits = page_dir_get_n_heap(page) + LOCK_PAGE_BITMAP_MARGIN;
n_bytes = 1 + n_bits / 8;

/* 注意这里是分配的连续内存 */
lock = static_cast<lock_t>(
    mem_heap_alloc(trx->lock.lock_heap, sizeof(lock_t) + n_bytes)
);


/**
 * Gets the number of records in the heap.
 * @return number of user records 
 */
UNIV_INLINE ulint page_dir_get_n_heap(const page_t* page)	
{
    return(page_header_get_field(page, PAGE_N_HEAP) & 0x7fff);
}</lock_t>

Table lock structure

Innodb also supports table locks, which can be divided into two categories: intention Lock, the data structure of the auto-increment lock is defined as follows:

Excerpted from

lock0priv.hFile

struct lock_table_t {
    /* database table in dictionary cache */
    dict_table_t*  table;
    
    /* list of locks on the same table */
    UT_LIST_NODE_T(lock_t)  locks;
};

Excerpted from

ut0lst.hFile

struct ut_list_node {
    /* pointer to the previous node, NULL if start of list */
    TYPE*  prev;
    
    /* pointer to next node, NULL if end of list */
    TYPE*  next;
};


#define UT_LIST_NODE_T(TYPE)  ut_list_node<type></type>

Description of locks in transactions

The above lock_rec_t and lock_table_t structures are just separate definitions. Locks are generated in transactions, so the row locks and table locks corresponding to each transaction will have a corresponding lock structure. , its definition is as follows:

Excerpted from

lock0priv.h file

/** Lock struct; protected by lock_sys->mutex */
struct lock_t {
    /* transaction owning the lock */
    trx_t*  trx;
    
    /* list of the locks of the transaction */
    UT_LIST_NODE_T(lock_t)  trx_locks;	
    
    /** 
     * lock type, mode, LOCK_GAP or LOCK_REC_NOT_GAP,
     * LOCK_INSERT_INTENTION, wait flag, ORed 
     */
    ulint  type_mode;
    
    /* hash chain node for a record lock */
    hash_node_t  hash;	
    
    /*!<p>      lock_t是根据每个事务每个页(或表)来定义的，但是一个事务往往涉及到多个页，因此需要链表<strong>trx_locks</strong>串联起一个事务相关的所有锁信息。除了需要根据事务查询到所有锁信息，实际场景还要求系统必须能够快速高效的检测出某个行记录是否已经上锁。因此必须有一个全局变量支持对行记录进行锁信息的查询。Innodb选择了哈希表，其定义如下:</p><p>      摘自<strong>lock0lock.h</strong>文件</p><pre class="brush:php;toolbar:false">/** The lock system struct */
struct lock_sys_t {
    /* Mutex protecting the locks */
    ib_mutex_t  mutex;		
    
    /* 就是这里: hash table of the record locks */
    hash_table_t*  rec_hash;	
    
    /* Mutex protecting the next two fields */
    ib_mutex_t  wait_mutex;
    
    /** 
     * Array  of user threads suspended while waiting forlocks within InnoDB,
     * protected by the lock_sys->wait_mutex 
     */
    srv_slot_t*  waiting_threads;
    
    /*
     * highest slot ever used in the waiting_threads array,
     * protected by lock_sys->wait_mutex 
     */
    srv_slot_t*  last_slot;
    
    /** 
     * TRUE if rollback of all recovered transactions is complete. 
     * Protected by lock_sys->mutex 
     */
    ibool  rollback_complete;
		
    /* Max wait time */
    ulint  n_lock_max_wait_time;

    /**
     * Set to the event that is created in the lock wait monitor thread.
     * A value of 0 means the thread is not active
     */
    os_event_t	timeout_event;		

    /* True if the timeout thread is running */
    bool  timeout_thread_active;
};

      函数lock_sys_create在database start之际负责初始化lock_sys_t结构。rec_hash的hash slot数量由srv_lock_table_size变量决定。rec_hash哈希表的key值通过页的space id，page number计算得出。

      摘自lock0lock.ic、ut0rnd.ic 文件

/**
 * Calculates the fold value of a page file address: used in inserting or
 * searching for a lock in the hash table.
 *
 * @return folded value 
 */
UNIV_INLINE ulint lock_rec_fold(ulint space, ulint page_no)
{
    return(ut_fold_ulint_pair(space, page_no));
}


/**
 * Folds a pair of ulints.
 *
 * @return folded value 
 */
UNIV_INLINE ulint ut_fold_ulint_pair(ulint n1, ulint n2)
{
    return (
        (
            (((n1 ^ n2 ^ UT_HASH_RANDOM_MASK2) <p>      这将意味着无法提供一个手段使得我们可以直接得知某一行是否上锁。而是应该先通过其所在的页得到space id、page number通过<strong>lock_rec_fold</strong>函数得出key值而后经过hash查询得到lock_rec_t，而后根据heap_no扫描bit map，最终确定锁信息。<strong>lock_rec_get_first</strong>函数实现了上述逻辑:</p><p>      这里返回的其实是<strong>lock_t</strong>对象，摘自<strong>lock0lock.cc</strong>文件</p><pre class="brush:php;toolbar:false">/**
 * Gets the first explicit lock request on a record.
 *
 * @param block   : block containing the record 
 * @param heap_no : heap number of the record 
 *
 * @return first lock, NULL if none exists 
 */
UNIV_INLINE lock_t* lock_rec_get_first(const buf_block_t* block, ulint heap_no)
{
    lock_t*  lock;

    ut_ad(lock_mutex_own());

    for (lock = lock_rec_get_first_on_page(block); lock;
         lock = lock_rec_get_next_on_page(lock)
    ) {
        if (lock_rec_get_nth_bit(lock, heap_no)) {
            break;
        }
    }

    return(lock);
}

      锁维护以页的粒度，不是一个最高效直接的方式，明显的时间换空间，这种设计使得锁的开销很小。某一事务对任一行上锁的开销都是一样的，锁数量的上升也不会带来额外的内存消耗。

      每个事务都对应一个trx_t的内存对象，其中保存着该事务锁信息链表和正在等待的锁信息。因此存在如下两种途径对锁进行查询:

• 根据事务: 通过trx_t对象的trx_locks链表，再通过lock_t对象中的trx_locks遍历可得某事务持有、等待的所有锁信息。
• 根据记录: 根据记录所在的页，通过space id、page number在lock_sys_t结构中定位到lock_t对象，扫描bitmap找到heap_no对应的bit位。

      上述各种数据结构，对其整理关系如下图所示:

注:

• lock_sys_t中的slot颜色与lock_t颜色相同则表明lock_sys_t slot持有lock_t
  指针信息，实在是没法连线，不然图很混乱

【相关推荐：mysql视频教程】

The above is the detailed content of An article to talk about the internal implementation mechanism of Mysql lock. For more information, please follow other related articles on the PHP Chinese website!