Innodb是mysql數據庫中目前最流行的存儲引擎，innodb相對其它存儲引擎一個很大的特點是支持事務，並且支持行粒度的鎖。今天我重點跟大家分享下innodb行鎖實現的基礎知識。由於篇幅比較大，文章會按如下的目錄結構展開。
{
innodb鎖結構
鎖機制關鍵流程
innodb行鎖開銷
innodb鎖同步機制
innodb等待事件實現
}
先從一個簡單的例子說起，如下表1
時間軸
A用戶(T1)
B用戶(T2)
t1
select * from t where id=1 for update
t2
select * from t where id=1 for update
t3
掛起狀態
t4
commit
t5
執行成功
表1
t1時刻A用戶獲得表t中id為1這條記錄的排它鎖，那麼當t2時刻B用戶再請求該記錄的排它鎖時，則需要等待；t4時刻A用戶提交事務後，則B用戶立即也執行成功。這個簡單例子的背後有幾個問題需要我們思考，第一，innodb如何掛起B用戶的執行線程的；第二，用戶B又如何在A用戶提交事務後，立即執行成功返回的。上面例子本質上是innodb使用鎖達到了A用戶和B用戶有序操作id為1這條記錄的目的，下文會詳細介紹這個實現過程，同時會介紹鎖相關的一些基礎知識。
1. Innodb鎖結構
Innodb鎖結構通過lock_sys管理，所有的行鎖lock_t對象都插入hash表中，通過維護hash表，來管理行鎖對象，hash表的key值通過頁號(space_id,page_no)計算得到。
1) 鎖系統結構圖
2) 重要數據結構
1 lock_sys
2 {
3 hash_table_t* rec_hash; //行鎖hash表
4 srv_slot_t* waiting_threads; //等待對象數組
5 }
6
7 lock_rec_t
8 {
9 ulint space; //表空間編號
10 ulint page_no; //數據頁編號
11 ulint n_bits; //數據頁包含的記錄
12 byte bitmap[1+n_bits/8] //bitmap數組
13 };
2.關鍵流程
1) 創建鎖【lock_rec_create】
a)計算頁面中的記錄數目，
b)按每個記錄一個bit存儲，計算需要的存儲空間
c)申請lock_t的存儲空間
d)初始化bitmap，將heap_no對應的bit位置1，表示上鎖
e)將鎖對象指針插入hash鏈表
f)將鎖對象插入到事務的鎖鏈表
2) 查詢某一個記錄上鎖情況：(是否上鎖，鎖類型)
a) 獲取記錄信息: (space_id,page_no)，和heap_no
b) 根據(space_id,page_no)查找hash表，獲取鎖對象lock _t
c) 根據鎖對象內容，判斷是共享鎖還是排它鎖
d) 若存在，遍歷鎖對象的bitmap，確定heap_no對應的位是否為1。
e) 為1，表示已經加鎖
3) 上行鎖
a) 查找hash表，判斷頁面上是否有鎖
b) 若不存在，則創建鎖，將鎖對象插入hash鏈表
c) 若存在，判斷是否事務已有更強的鎖存在 (lock_rec_has_expl)
d) 若是，跳轉5，若不是，跳轉6(lock_rec_lock_slow)
e) 根據頁面的heap_no設置bit位，結束。
f) 判斷請求鎖是否有鎖沖突
g)若是，創建鎖(模式LOCK_WAIT)，設置wait_lock (lock_rec_enqueue_waiting)
h)若不是，上鎖成功，加入鎖隊列(lock_rec_add_to_queue)
i) 上層調用根據返回的錯誤碼，調用鎖等待邏輯(lock_wait_suspend_thread)
4) 鎖等待【lock_wait_suspend_thread】
a) 根據工作線程信息獲取事務信息；
b) 申請slot節點(lock_wait_table_reserve_slot),初始化等待事件；
c) 設置等待事件(linux中通過條件變量實現)，將線程掛起
調用堆棧
#0 pthread_cond_wait #1 os_cond_wait(pthread_cond_t*, os_fast_mutex_t*) () #2 os_event_wait_low(os_event*, long) () #3 lock_wait_suspend_thread(que_thr_t*) () #4 row_mysql_handle_errors(dberr_t*, trx_t*, que_thr_t*, trx_savept_t*) ()
5) 釋放鎖
innodb的行鎖在事務提交或回滾後才釋放。釋放鎖後，會檢查是否有等待該鎖的鎖對象，若有，則將其釋放，喚醒對應的線程。
a) 提取鎖類型為LOCK_WAIT鎖，判斷是否需要繼續等待。
b) 若不需要等待，則授權lock_grant
c) 根據鎖對象找到找到對應的事務(lock_t->trx)信息,
d) 通過事務找到對應的工作線程(trx_lock_t->wait_thr)信息
e) 通過thr信息找到對應的slot(等待事件)
f) 調用os_event_set觸發事件
調用堆棧 #0 os_event_set(thr->slot->event); #1 lock_wait_release_thread_if_suspended #2 lock_grant #3 lock_rec_dequeue_from_page #4 lock_trx_release_locks
6) slot的管理
鎖等待通過slot對象上的等待事件event實現(下文會講)，每個slot對象包含一個等待事件，slot個數與運行的線程相關。因為阻塞的主體是線程，因此只需要初始化與最大線程數目相同的slot節點即可。slot信息存儲在lock_sys的waiting_threads中。需要slot時，從數組中獲取。
slot初始化
lock_sys = static_cast<lock_sys_t*>(mem_zalloc(lock_sys_sz)); lock_stack = static_cast<lock_stack_t*>( mem_zalloc(sizeof(*lock_stack) * LOCK_STACK_SIZE)); void* ptr = &lock_sys[1]; lock_sys->waiting_threads = static_cast<srv_slot_t*>(ptr);
3. innodb行鎖開銷
innodb行鎖采用位圖存儲，理論上一個記錄只需要一個bit位。鎖的基本單位是行，但鎖是通過事務和頁來進行管理和組織，創建鎖的實例是lock_t，一個lock_t實例對應於一個索引頁面的所有記錄。
1) 行鎖代價計算
內存開銷主要來源於指針和存儲鎖信息的bitmap。bitmap中的一個bit對應page的一條記錄，一個200條記錄的Page,一個行鎖對象大小約為 100bytes。若頁面只鎖一行，代價為100byte/行，而如果所有記錄公用一把鎖，則代價為100byte/200=4bit/行。實際情況下，只有當同一個事務鎖住了頁面的所有記錄，並且鎖模式相同，才可能保證一個頁面只有一把鎖。
一個lock_t對象占用的內存空間
1 /* Make lock bitmap bigger by a safety margin */ 2 n_bits = page_dir_get_n_heap(page) + LOCK_PAGE_BITMAP_MARGIN; 3 n_bytes = 1 + n_bits / 8; 4 lock = static_cast<lock_t*>( 5 mem_heap_alloc(trx->lock.lock_heap, sizeof(lock_t) + n_bytes));
2) 鎖重用
innodb鎖機制利用鎖重用方式，保證鎖的內存開銷盡可能小。具體而言，同一個事務鎖住同一個頁面的記錄,並且鎖模式相同; 同一個事務，對於同一條記錄，已有的鎖強於請求的鎖模式，這兩種情況下都不需要重新創建鎖對象。
4. Innodb鎖同步機制(spinlock+mutex+條件變量)
innodb沒有直接采用原生的同步方式比如spinlock，mutex或是條件變量實現，而是將幾種方式進行融合，達到最優的目的。主要函數的實現在於mutex_enter_func和mutex_exit兩個函數。
1) 數據結構
ib_mutex_t
{
os_event_t event; //等待事件
volatile lock_word_t lock_word; //鎖變量
os_fast_mutex_t os_fast_mutex; //不支持原子鎖系統，使用互斥量
ulint waiters; //是否有等待線程
}
2) 獲取互斥量流程【mutex_enter_func(ib-mutex)】
a) 首先進行自旋，檢查mutex->lock_word，判斷是否可以獲得該鎖
b) 對於不支持spinlock的系統，采用pthread_mutex_trylock方式，利用os_fast_mutex保護mutex->lock_word，判斷是否可以獲得該鎖
c) 若不能獲得，則從全局變量 sync_wait_array分配一個cell，並將cell的wait_object設置為ib-mutex
d) 將ib-mutex的waiters設為1
e) 調用os_event_wait_low(ib-mutex->event)，將線程掛起
f) 獲得信號量後，線程跳轉步驟a)重新開始執行。
3) 釋放互斥量流程【mutex_exit_func(ib-mutex)】
a) 重置mutex->lock_word，
b) 對於自旋鎖，通過os_atomic_test_and_set_byte設置
c) 對於不支持自旋鎖的系統，釋放os_fast_mutex，將lock_word設置為0
d) 判斷ib-mutex對象waiters是否為1(是否有線程掛起)
e) 調用mutex_signal_object(ib-mutex->event)
f) 調用pthread_cond_broadcast(event->cond)喚醒所有等待的線程
5. innodb等待事件實現
1) event的結構
os_event
{
os_cond_t cond_var; //條件變量
ibool is_set; //為ture時，線程不會阻塞在事件上
os_fast_mutex_t os_mutex; //保護條件變量的互斥量
}
2) os_event_set 流程
a) 獲取互斥量os_mutex
b) 若is_set為true，什麼也不做，釋放os_mutex
c) 若is_set為false，設置is_set為true
d) 調用pthread_cond_broadcast廣播條件變量，喚醒所有等待線程
3) os_event_wait 流程
a) 獲取互斥量os_mutex
b) 判斷is_set為true，則什麼也不做，釋放os_mutex
c) 若is_set為false，調用pthread_cond_wait，將自己掛起等待
d) 被喚醒後，釋放互斥量os_mutex
回到文章開始提到的問題，假設表t，id=1的記錄所在的頁面為(1,20)，如圖2所示，則鎖節點可以紅色的框表示，一個節點表示一個鎖對象。另外，事務T2和T3已經在頁面(0,200)上了2把鎖，這裡解釋下，為啥同一個頁面有2把鎖。這是因為，鎖對象的擁有者不同。不同事務即使是對同一條記錄上同樣模式的鎖，也需要分別創建一個鎖對象，所謂的鎖重用是針對同一個事務鎖同一個頁面的多個記錄而言。若T1也需要對(0,200)上鎖，若上鎖的記錄與已有鎖沖突，則創建鎖，並掛起等待；否則，創建鎖，返回成功。
