前言

現(xiàn)代操作系統(tǒng)以及硬件基本都支持并發(fā)程序，而在并發(fā)程序設(shè)計中，各個進(jìn)程或者線程需要對公共變量的訪問加以制約，此外，不同的進(jìn)程或者線程需要協(xié)同工作以完成特征的任務(wù)，這就需要一套完善的同步機制，在Linux內(nèi)核中有相應(yīng)的技術(shù)實現(xiàn)，包括原子操作，信號量，互斥鎖，自旋鎖，讀寫鎖等。InnoDB考慮到效率和監(jiān)控兩方面的原因，實現(xiàn)了一套獨有的同步機制，提供給其他模塊調(diào)用。本文的分析默認(rèn)基于MySQL 5.6，CentOS 6，gcc 4.8，其他版本的信息會另行指出。

基礎(chǔ)知識

同步機制對于其他數(shù)據(jù)庫模塊來說相對獨立，但是需要比較多的操作系統(tǒng)以及硬件知識，這里簡單介紹一下幾個有用的概念，便于讀者理解后續(xù)概念。

內(nèi)存模型 :主要分為語言級別的內(nèi)存模型和硬件級別的內(nèi)存模型。語言級別的內(nèi)存模型，C/C++屬于weak memory model，簡單的說就是編譯器在進(jìn)行編譯優(yōu)化的時候，可以對指令進(jìn)行重排，只需要保證在單線程的環(huán)境下，優(yōu)化前和優(yōu)化后執(zhí)行結(jié)果一致即可，執(zhí)行中間過程不保證跟代碼的語義順序一致。所以在多線程的環(huán)境下，如果依賴代碼中間過程的執(zhí)行順序，程序就會出現(xiàn)問題。硬件級別的內(nèi)存模型，我們常用的cpu，也屬于弱內(nèi)存模型，即cpu在執(zhí)行指令的時候，為了提升執(zhí)行效率，也會對某些執(zhí)行進(jìn)行亂序執(zhí)行（按照wiki提供的資料，在x86 64環(huán)境下，只會發(fā)生讀寫亂序，即讀操作可能會被亂序到寫操作之前），如果在編程的時候不做一些措施，同樣容易造成錯誤。

內(nèi)存屏障 :為了解決弱內(nèi)存模型造成的問題，需要一種能控制指令重排或者亂序執(zhí)行程序的手段，這種技術(shù)就叫做內(nèi)存屏障，程序員只需要在代碼中插入特定的函數(shù)，就能控制弱內(nèi)存模型帶來的負(fù)面影響，當(dāng)然，由于影響了亂序和重排這類的優(yōu)化，對代碼的執(zhí)行效率有一定的影響。具體實現(xiàn)上，內(nèi)存屏障技術(shù)分三種，一種是full memory barrier，即barrier之前的操作不能亂序或重排到barrier之后，同時barrier之后的操作不能亂序或重排到barrier之前，當(dāng)然這種full barrier對性能影響最大，為了提高效率才有了另外兩種：acquire barrier和release barrier，前者只保證barrier后面的操作不能移到之前，后者只保證barrier前面的操作不移到之后。

互斥鎖 :互斥鎖有兩層語義，除了大家都知道的排他性（即只允許一個線程同時訪問）外，還有一層內(nèi)存屏障（full memory barrier）的語義，即保證臨界區(qū)的操作不會被亂序到臨界區(qū)外。Pthread庫里面常用的mutex，conditional variable等操作都自帶內(nèi)存屏障這層語義。此外，使用pthread庫，每次調(diào)用都需要應(yīng)用程序從用戶態(tài)陷入到內(nèi)核態(tài)中查看當(dāng)前環(huán)境，在鎖沖突不是很嚴(yán)重的情況下，效率相對比較低。

自旋鎖 :傳統(tǒng)的互斥鎖，只要一檢測到鎖被其他線程所占用了，就立刻放棄cpu時間片，把cpu留給其他線程，這就會產(chǎn)生一次上下文切換。當(dāng)系統(tǒng)壓力大的時候，頻繁的上下文切換會導(dǎo)致sys值過高。自旋鎖，在檢測到鎖不可用的時候，首先cpu忙等一小會兒，如果還是發(fā)現(xiàn)不可用，再放棄cpu，進(jìn)行切換。互斥鎖消耗cpu sys值，自旋鎖消耗cpu usr值。

遞歸鎖 :如果在同一個線程中，對同一個互斥鎖連續(xù)加鎖兩次，即第一次加鎖后，沒有釋放，繼續(xù)進(jìn)行對這個鎖進(jìn)行加鎖，那么如果這個互斥鎖不是遞歸鎖，將導(dǎo)致死鎖?？梢园堰f歸鎖理解為一種特殊的互斥鎖。

死鎖 :構(gòu)成死鎖有四大條件，其中有一個就是加鎖順序不一致，如果能保證不同類型的鎖按照某個特定的順序加鎖，就能大大降低死鎖發(fā)生的概率，之所以不能完全消除，是因為同一種類型的鎖依然可能發(fā)生死鎖。另外，對同一個鎖連續(xù)加鎖兩次，如果是非遞歸鎖，也將導(dǎo)致死鎖。

原子操作

現(xiàn)代的cpu提供了對單一變量簡單操作的原子指令，即這個變量的這些簡單操作只需要一條cpu指令即可完成，這樣就不用對這個操作加互斥鎖了，在鎖沖突不激烈的情況下，減少了用戶態(tài)和內(nèi)核態(tài)的切換，化悲觀鎖為樂觀鎖，從而提高了效率。此外，現(xiàn)在外面很火的所謂無鎖編程（類似CAS操作），底層就是用了這些原子操作。gcc為了方便程序員使用這些cpu原子操作，提供了一系列__sync開頭的函數(shù)，這些函數(shù)如果包含內(nèi)存屏障語義，則同時禁止編譯器指令重排和cpu亂序執(zhí)行。

InnoDB針對不同的操作系統(tǒng)以及編譯器環(huán)境，自己封裝了一套原子操作，在頭文件os0sync.h中。下面的操作基于Linux x86 64位環(huán)境， gcc 4.1以上的版本進(jìn)行分析。

os_compare_and_swap_xxx(ptr, old_val, new_val)類型的操作底層都使用了gcc包裝的__sync_bool_compare_and_swap(ptr, old_val, new_val)函數(shù)，語義為，交換成功則返回true，ptr是交換后的值，old_val是之前的值，new_val是交換后的預(yù)期值。這個原子操作是個內(nèi)存屏障（full memory barrier）。

os_atomic_increment_xxx類型的操作底層使用了函數(shù)__sync_add_and_fetch，os_atomic_decrement_xxx類型的操作使用了函數(shù)__sync_sub_and_fetch，分別表示原子遞增和原子遞減。這個兩個原子操作也都是內(nèi)存屏障（full memory barrier）。

另外一個比較重要的原子操作是os_atomic_test_and_set_byte(ptr, new_val)，這個操作使用了__sync_lock_test_and_set(ptr, new_val)這個函數(shù)，語義為，把ptr設(shè)置為new_val，同時返回舊的值。這個操作提供了原子改變某個變量值的操作，InnoDB鎖實現(xiàn)的同步機制中，大量的用了這個操作，因此比較重要。需要注意的是，參看gcc文檔，這個操作不是full memory barrier，只是一個acquire barrier，簡單的說就是，代碼中__sync_lock_test_and_set之后操作不能被亂序或者重排到__sync_lock_test_and_set之前，但是__sync_lock_test_and_set之前的操作可能被重排到其之后。

關(guān)于內(nèi)存屏障的專門指令，MySQL 5.7提供的比較完善。os_rmb表示acquire barrier，os_wmb表示release barrier。如果在編程時，需要在某個位置準(zhǔn)確的讀取一個變量的值時，記得在讀取之前加上os_rmb，同理，如果需要在某個位置保證一個變量已經(jīng)被寫了，記得在寫之后調(diào)用os_wmb。

條件通知機制

條件通知機制在多線程協(xié)作中非常有用，一個線程往往需要等待其他線程完成指定工作后，再進(jìn)行工作，這個時候就需要有線程等待和線程通知機制。Pthread_cond_XXX類似的變量和函數(shù)來完成等待和通知的工作。InnoDB中，對Pthread庫進(jìn)行了簡單的封裝，并在此基礎(chǔ)上，進(jìn)一步抽象，提供了一套方便易用的接口函數(shù)給調(diào)用者使用。

系統(tǒng)條件變量

在文件os0sync.cc中，os_cond_XXX類似的函數(shù)就是InnoDB對Pthread庫的封裝。常用的幾個函數(shù)如：

os_cond_t是核心的操作對象，其實就是pthread_cond_t的一層typedef而已，os_cond_init初始化函數(shù)，os_cond_destroy銷毀函數(shù)，os_cond_wait條件等待，不會超時，os_cond_wait_timed條件等待，如果超時則返回，os_cond_broadcast喚醒所有等待線程，os_cond_signal只喚醒其中一個等待線程，但是在閱讀源碼的時候發(fā)現(xiàn)，似乎沒有什么地方調(diào)用了os_cond_signal。。。

此外，還有一個os_cond_module_init函數(shù)，用來window下的初始化操作。

在InnoDB下，os_cond_XXX模塊的函數(shù)主要是給InnoDB自己設(shè)計的條件變量使用。

InnoDB條件變量

如果在InnoDB層直接使用系統(tǒng)條件變量的話，主要有四個弊端，首先，弊端1，系統(tǒng)條件變量的使用需要與一個系統(tǒng)互斥鎖（詳見下一節(jié)）相配合使用，使用完還要記得及時釋放，使用者會比較麻煩。接著，弊端2，在條件等待的時候，需要在一個循環(huán)中等待，使用者還是比較麻煩。最后，弊端3，也是比較重要的，不方便系統(tǒng)監(jiān)控。

基于以上幾點，InnoDB基于系統(tǒng)的條件變量和系統(tǒng)互斥鎖自己實現(xiàn)了一套條件通知機制。主要在文件os0sync.cc中實現(xiàn)，相關(guān)數(shù)據(jù)結(jié)構(gòu)以及接口進(jìn)一層的包裝在頭文件os0sync.h中。使用方法如下：

InnoDB條件變量核心數(shù)據(jù)結(jié)構(gòu)為os_event_t，類似pthread_cont_t。如果需要創(chuàng)建和銷毀則分別使用os_event_create和os_event_free函數(shù)。需要等待某個條件變量，先調(diào)用os_event_reset（原因見下一段），然后使用os_event_wait，如果需要超時等待，使用os_event_wait_time替換os_event_wait即可，os_event_wait_XXX這兩個函數(shù)，解決了弊端1和弊端2，此外，建議把os_event_reset返回值傳給他們，這樣能防止多線程情況下的無限等待（詳見下下段）。如果需要發(fā)出一個條件通知，使用os_event_set。這個幾個函數(shù)，里面都插入了一些監(jiān)控信息，方便InnoDB上層管理。怎么樣，方便多了吧~

多線程環(huán)境下可能發(fā)生的問題

首先來說說兩個線程下會發(fā)生的問題。創(chuàng)建后，正常的使用順序是這樣的，線程A首先os_event_reset（步驟1），然后os_event_wait（步驟2），接著線程B做完該做的事情后，執(zhí)行os_event_set（步驟3）發(fā)送信號，通知線程A停止等待，但是在多線程的環(huán)境中，會出現(xiàn)以下兩種步驟順序錯亂的情況：亂序A： 步驟1--步驟3--步驟2，亂序B: 步驟3--步驟1--步驟2。對于亂序B，屬于條件通知在條件等待之前發(fā)生，目前InnoDB條件變量的機制下，會發(fā)生無限等待，所以上層調(diào)用的時候一定要注意，例如在InnoDB在實現(xiàn)互斥鎖和讀寫鎖的時候為了防止發(fā)生條件通知在條件等待之前發(fā)生，在等待之前對lock_word再次進(jìn)行了判斷，詳見InnoDB自旋互斥鎖這一節(jié)。為了解決亂序A，InnoDB在核心數(shù)據(jù)結(jié)構(gòu)os_event中引入布爾型變量is_set，is_set這個變量就表示是否已經(jīng)發(fā)生過條件通知，在每次調(diào)用條件通知之前，會把這個變量設(shè)置為true（在os_event_reset時改為false，便于多次通知），在條件等待之前會檢查一下這變量，如果這個變量為true，就不再等待了。所以，亂序A也能保證不會發(fā)生無限等待。

接著我們來說說大于兩個線程下可能會發(fā)生的問題。線程A和C是等待線程，等待同一個條件變量，B是通知線程，通知A和C結(jié)束等待?？紤]一個亂序C：線程A執(zhí)行os_event_reset（步驟1），線程B馬上就執(zhí)行os_event_set（步驟2）了，接著線程C執(zhí)行了os_event_reset（步驟3），最后線程A執(zhí)行os_event_wait（步驟4），線程C執(zhí)行os_event_wait（步驟5）。乍一眼看，好像看不出啥問題，但是實際上你會發(fā)現(xiàn)A和C線程在無限等待了。原因是，步驟2，把is_set這個變量設(shè)置為false，但是在步驟3，線程C通過reset又把它給重新設(shè)回false了。。然后線程A和C在os_event_wait中誤以為還沒有發(fā)生過條件通知，就開始無限等待了。為了解決這個問題，InnoDB在核心數(shù)據(jù)結(jié)構(gòu)os_event中引入64位整形變量signal_count，用來記錄已經(jīng)發(fā)出條件信號的次數(shù)。每次發(fā)出一個條件通知，這個變量就遞增1。os_event_reset的返回值就把當(dāng)前的signal_count值取出來。os_event_wait如果發(fā)現(xiàn)有這個參數(shù)的傳入，就會判斷傳入的參數(shù)與當(dāng)前的signal_count值是否相同，如果不相同，表示這個已經(jīng)通知過了，就不會進(jìn)入等待了。舉個例子，假設(shè)亂序C，一開始的signal_count為100，步驟1把這個參數(shù)傳給了步驟4，在步驟4中，os_event_wait會發(fā)現(xiàn)傳入值100與當(dāng)前的值101（步驟2中遞增了1）不同，所以線程A認(rèn)為信號已經(jīng)發(fā)生過了，就不會再等待了。。。然而。。線程C呢？步驟3返回的值應(yīng)該是101，傳給步驟5后，發(fā)生于當(dāng)前值一樣。。繼續(xù)等待。。。仔細(xì)分析可以發(fā)現(xiàn)，線程C是屬于條件變量通知發(fā)生在等待之前（步驟2，步驟3，步驟5），上一段已經(jīng)說過了，針對這種通知提前發(fā)出的，目前InnoDB沒有非常好的解法，只能調(diào)用者自己控制。

總結(jié)一下， InnoDB條件變量能方便InnoDB上層做監(jiān)控，也簡化了條件變量使用的方法，但是調(diào)用者上層邏輯必須保證條件通知不能過早的發(fā)出，否則就會有無限等待的可能。

互斥鎖

互斥鎖保證一段程序同時只能一個線程訪問，保證臨界區(qū)得到正確的序列化訪問。同條件變量一樣，InnoDB對Pthread的mutex簡單包裝了一下，提供給其他模塊用（主要是輔助其他自己實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，不用InnoDB自己的互斥鎖是為了防止遞歸引用，詳見輔助結(jié)構(gòu)這一節(jié)）。但與條件變量不同的是，InnoDB自己實現(xiàn)的一套互斥鎖并沒有依賴Pthread庫，而是依賴上述的原子操作（如果平臺不支持原子操作則使用Pthread庫，但是這種情況不太會發(fā)生，因為gcc在4.1就支持原子操作了）和上述的InnoDB條件變量。

系統(tǒng)互斥鎖

相比與系統(tǒng)條件變量，系統(tǒng)互斥鎖除了包裝Pthread庫外，還做了一層簡單的監(jiān)控統(tǒng)計，結(jié)構(gòu)名為os_mutex_t。在文件os0sync.cc中，os_mutex_create創(chuàng)建mutex，并調(diào)用os_fast_mutex_init_func創(chuàng)建pthread的mutex，值得一提的是，創(chuàng)建pthread mutex的參數(shù)是my_fast_mutexattr的東西，其在MySQL server層函數(shù)my_thread_global_init初始化 ，只要pthread庫支持，則默認(rèn)成初始化為PTHREAD_MUTEX_ADAPTIVE_NP和PTHREAD_MUTEX_ERRORCHECK。前者表示，當(dāng)鎖釋放，之前在等待的鎖進(jìn)行公平的競爭，而不是按照默認(rèn)的優(yōu)先級模式。后者表示，如果發(fā)生了遞歸的加鎖，即同一個線程對同一個鎖連續(xù)加鎖兩次，第二次加鎖會報錯。另外三個有用的函數(shù)為，銷毀鎖os_mutex_free，加鎖os_mutex_enter，解鎖os_mutex_exit。

一般來說，InnoDB上層模塊不需要直接與系統(tǒng)互斥鎖打交道，需要用鎖的時候一般用InnoDB自己實現(xiàn)的一套互斥鎖。系統(tǒng)互斥鎖主要是用來輔助實現(xiàn)一些數(shù)據(jù)結(jié)構(gòu)，例如最后一節(jié)提到的一些輔助結(jié)構(gòu)，由于這些輔助結(jié)構(gòu)可能本身就要提供給InnoDB自旋互斥鎖用，為了防止遞歸引用，就暫時用系統(tǒng)互斥鎖來代替。

InnoDB自旋互斥鎖

為什么InnoDB需要實現(xiàn)自己的一套互斥鎖，不直接用上述的系統(tǒng)互斥鎖呢？這個主要有以下幾個原因，首先，系統(tǒng)互斥鎖是基于pthread mutex的，Heikki Tuuri（同步模塊的作者，也是Innobase的創(chuàng)始人）認(rèn)為在當(dāng)時的年代pthread mutex上下文切換造成的cpu開銷太大，使用spin lock的方式在多處理器的機器上更加有效，尤其是在鎖競爭不是很嚴(yán)重的時候，Heikki Tuuri還總結(jié)出，在spin lock大概自旋20微秒的時候在多處理的機器下效率最高。其次，不使用pthread spin lock的原因是，當(dāng)時在1995年左右的時候，spin lock的類似實現(xiàn)，效率很低，而且當(dāng)時的spin lock不支持自定義自旋時間，要知道自旋鎖在單處理器的機器上沒什么卵用。最后，也是為了更加完善的監(jiān)控需求。總的來說，有歷史原因，有監(jiān)控需求也有自定義自旋時間的需求，然后就有了這一套InnoDB自旋互斥鎖。

InnoDB自旋互斥鎖的實現(xiàn)主要在文件sync0sync.cc和sync0sync.ic中，頭文件sync0sync.h定義了核心數(shù)據(jù)結(jié)構(gòu)ib_mutex_t。使用方法很簡單，mutex_create創(chuàng)建鎖，mutex_free釋放鎖，mutex_enter嘗試獲得鎖，如果已經(jīng)被占用了，則等待。mutex_exit釋放鎖，同時喚醒所有等待的線程，拿到鎖的線程開始執(zhí)行，其余線程繼續(xù)等待。mutex_enter_nowait這個函數(shù)類似pthread的trylock，只要已檢測到鎖不用，就直接返回錯誤，不進(jìn)行自旋等待。總體來說，InnoDB自旋互斥鎖的用法和語義跟系統(tǒng)互斥鎖一模一樣，但是底層實現(xiàn)卻大相徑庭。

在ib_mutex_t這個核心數(shù)據(jù)結(jié)構(gòu)中，最重要的是前面兩個變量：event和lock_word。lock_word為0表示鎖空閑，1表示鎖被占用，InnoDB自旋互斥鎖使用__sync_lock_test_and_set這個函數(shù)對lock_word進(jìn)行原子操作，加鎖的時候，嘗試把其設(shè)置為1，函數(shù)返回值不指示是否成功，指示的是嘗試設(shè)置之前的值，因此如果返回值是0，表示加鎖成功，返回是1表示失敗。如果加鎖失敗，則會自旋一段時間，然后等待在條件變量event（os_event_wait）上，當(dāng)鎖占用者釋放鎖的時候，會使用os_event_set來喚醒所有的等待者。簡單的來說，byte類型的lock_word基于平臺提供的原子操作來實現(xiàn)互斥訪問，而event是InnoDB條件變量類型，用來實現(xiàn)鎖釋放后喚醒等待線程的操作。

接下來，詳細(xì)介紹一下，mutex_enter和mutex_exit的邏輯，InnoDB自旋互斥鎖的精華都在這兩個函數(shù)中。

mutex_enter的偽代碼如下：

if (__sync_lock_test_and_set(mutex->lock_word, 1) == 0) { 
 
    get mutex successfully; 
 
    return; 
 
} 
 
loop1: 
 
    i = 0; 
 
loop2: 
 
    /*指示點1*/ 
 
    while (mutex->lock_word ! = 0 && i < SPIN_ROUNDS) { 
 
             random spin using ut_delay, spin max time depend on SPIN_WAIT_DELAY; 
 
             i++; 
 
} 
 
if (i == SPIN_ROUNDS) { 
 
    yield_cpu; 
 
} 
 
/*指示點2*/ 
 
if (__sync_lock_test_and_set(mutex->lock_word, 1) == 0) { 
 
    get mutex successfully; 
 
    return; 
 
} 
 
if (i < SPIN_ROUNDS) { 
 
     goto loop2 
 
} 
 
/*指示點4*/ 
 
get cell from sync array and call os_event_reset(mutex->event); 
 
mutex->waiter =1; 
 
/*指示點3*/ 
 
for (i = 0; i < 4; i++) { 
 
    if (__sync_lock_test_and_set(mutex->lock_word, 1) == 0) { 
 
        get mutex successfully; 
 
        free cell; 
 
        return; 
 
    } 
 
} 
 
sync array wait and os_event_wait(mutex->event); 
 
goto loop1; 

代碼還是有點小復(fù)雜的。這里分析幾點如下：

1. SPIN_ROUNDS控制了在放棄cpu時間片（yield_cpu）之前，一共進(jìn)行多少次忙等，這個參數(shù)就是對外可配置的innodb_sync_spin_loops，而SPIN_WAIT_DELAY控制了每次忙等的時間，這個參數(shù)也就是對外可配置的innodb_spin_wait_delay。這兩個參數(shù)一起決定了自旋的時間。Heikki Tuuri建議在單處理器的機器上調(diào)小spin的時間，在對稱多處理器的機器上，可以適當(dāng)調(diào)大。比較有意思的是innodb_spin_wait_delay的單位，這個是100MHZ的奔騰處理器處理1毫秒的時間，默認(rèn)innodb_spin_wait_delay配置成6，表示最多在100MHZ的奔騰處理器上自旋6毫秒。由于現(xiàn)在cpu都是按照GHZ來計算的，所以按照默認(rèn)配置自旋時間往往很短。此外，自旋不真是cpu傻傻的在那邊100%的跑，在現(xiàn)代的cpu上，給自旋專門提供了一條指令，在筆者的測試環(huán)境下，這條指令是pause，查看Intel的文檔，其對pause的解釋是：不會發(fā)生用戶態(tài)和內(nèi)核態(tài)的切換，cpu在用戶態(tài)自旋，因此不會發(fā)生上下文切換，同時這條指令不會消耗太多的能耗。。。所以那些說spin lock太浪費電的不攻自破了。。。另外，編譯器也不會把ut_delay給優(yōu)化掉，因為其里面估計修改了一個全局變量。

2. yield_cpu 操作在筆者的環(huán)境中，就是調(diào)用了pthread_yield函數(shù)，這個函數(shù)把放棄當(dāng)前cpu的時間片，然后把當(dāng)前線程放到cpu可執(zhí)行隊列的末尾。

3. 在指示點1后面的循環(huán)，沒有采用原子操作讀取數(shù)據(jù)，是因為，Heikki Tuuri認(rèn)為由于原子操作在內(nèi)存和cpu cache之間會產(chǎn)生過的數(shù)據(jù)交換，如果只是讀本地的cache，可以減少總線的爭用。即使本地讀到臟的數(shù)據(jù)，也沒關(guān)系，因為在跳出循環(huán)的指示點2，依然會再一次使用原子操作進(jìn)行校驗。

4. get cell這個操作是從sync array執(zhí)行的，sync array詳見輔助數(shù)據(jù)結(jié)構(gòu)這一節(jié)，簡單的說就是提供給監(jiān)控線程使用的。

5. 注意一下，os_event_reset和os_event_wait這兩個函數(shù)的調(diào)用位置，另外，有一點必須清楚，就是os_event_set（鎖持有者釋放所后會調(diào)用這個函數(shù)通知所有等待者）可能在這整段代碼執(zhí)行到任意位置出現(xiàn)，有可能出現(xiàn)在指示點4的位置，這樣就構(gòu)成了條件變量通知在條件變量等待之前，會造成無限等待。為了解決這個問題，才有了指示點3下面的代碼，需要重新再次檢測一下lock_word，另外，即使os_event_set發(fā)生在os_event_reset之后，有了這些代碼，也能讓當(dāng)前線程提前拿到鎖，不用執(zhí)行后續(xù)os_event_wait的代碼，一定程度上提高了效率。

mutex_exit的偽代碼就簡單多了，如下：

__sync_lock_test_and_set(mutex->lock_word, 0);  
 
/* A problem: we assume that mutex_reset_lock word                                                                     
 
        is a memory barrier, that is when we read the waiters                                                                   
 
        field next, the read must be serialized in memory                                                                       
 
        after the reset. A speculative processor might                                                                         
 
        perform the read first, which could leave a waiting                                                                     
 
        thread hanging indefinitely.                                                                                                                                                                                                                         
 
Our current solution call every second                                                                                 
 
        sync_arr_wake_threads_if_sema_free()                                                                                   
 
        to wake up possible hanging threads if                                                                                 
 
        they are missed in mutex_signal_object. */ 
 
  
 
if (mutex->waiter != 0) { 
 
     mutex->waiter = 0; 
 
     os_event_set(mutex->event); 
 
} 

1. waiter是ib_mutex_t中的一個變量，用來表示當(dāng)前是否有線程在等待這個鎖。整個代碼邏輯很簡單，就是先把lock_word設(shè)置為0，然后如果發(fā)現(xiàn)有等待者，就把所有等待者給喚醒。facebook的mark callaghan在2014年測試過，相比現(xiàn)在已經(jīng)比較完善的pthread庫，InnoDB自旋互斥鎖只在并發(fā)量相對較低（小于256線程）和鎖等待時間比較短的情況下有優(yōu)勢，在高并發(fā)且較長的鎖等待時間情況下，退化比較嚴(yán)重，其中一個很重要的原因就是InnoDB自旋互斥鎖在鎖釋放的時候需要喚醒所有等待者。由于os_event_ret底層通過pthread_cond_boardcast來通知所有的等待者，一種改進(jìn)是把pthread_cond_boardcast改成pthread_cond_signal，即只喚醒一個線程，但I(xiàn)naam Rana Mark測試后發(fā)現(xiàn)，如果只喚醒一個線程的話，在高并發(fā)的情況下，這個線程可能不會立刻被cpu調(diào)度到。。由此看來，似乎喚醒一個特定數(shù)量的等待者是一個比較好的選擇。

2. 偽代碼中的這段注釋筆者估計加上去的，大意是由于編譯器或者cpu的指令重排亂序執(zhí)行，mutex->waiter這個變量的讀取可能在發(fā)生在原子操作之前，從而導(dǎo)致一些無線等待的問題。然后還專門開了一個叫做sync_arr_wake_threads_if_sema_free的函數(shù)來做清理。這個函數(shù)是在后臺線程srv_error_monitor_thread中做的，每隔1秒鐘執(zhí)行一次。在現(xiàn)代的cpu和編譯器上，完全可以用內(nèi)存屏障的技術(shù)來防止指令重排和亂序執(zhí)行，這個函數(shù)可以被去掉，官方的意見貌似是，不要這么激進(jìn)，萬一其他地方還需要這個函數(shù)呢。。詳見BUG #79477。

總體來說，InnoDB自旋互斥鎖的底層實現(xiàn)還是比較有意思的，非常適合學(xué)習(xí)研究。這套鎖機制在現(xiàn)在完善的Pthread庫和高達(dá)4GMHZ的cpu下，已經(jīng)有點力不從心了，mark callaghan研究發(fā)現(xiàn)，在高負(fù)載的壓力下，使用這套鎖機制的InnoDB，大部分cpu時間都給了sys和usr，基本沒有空閑，而pthread mutex在相同情況下，卻有平均80%的空閑。同時，由于ib_mutex_t這個結(jié)構(gòu)體體積比較龐大，當(dāng)buffer pool比較大的時候，會發(fā)現(xiàn)鎖占用了很多的內(nèi)存。最后，從代碼風(fēng)格上來說，有不少代碼沒有解耦，如果需要把鎖模塊單獨打成一個函數(shù)庫，比較困難。

基于上述幾個缺陷，MySQL 5.7及后續(xù)的版本中，對互斥鎖進(jìn)行了大量的重新，包括以下幾點(WL#6044)：

1. 使用了C++中的類繼承關(guān)系，系統(tǒng)互斥鎖和InnoDB自己實現(xiàn)的自旋互斥鎖都是一個父類的子類。

2. 由于bool pool的鎖對性能要求比較高，因此使用靜態(tài)繼承（也就是模板）的方式來減少繼承中虛指針造成的開銷。

3. 保留舊的InnoDB自旋互斥鎖，并實現(xiàn)了一種基于futex的鎖。簡單的說，futex鎖與上述的原子操作類似，能減少用戶態(tài)和內(nèi)核態(tài)切換的開銷，但同時保留類似mutex的使用方法，大大降低了程序編寫的難度。

InnoDB讀寫鎖

與條件變量、互斥鎖不同，InnoDB里面沒有Pthread庫的讀寫鎖的包裝，其完全依賴依賴于原子操作和InnoDB的條件變量，甚至都不需要依賴InnoDB的自旋互斥鎖。此外，讀寫鎖還實現(xiàn)了寫操作的遞歸鎖，即同一個線程可以多次獲得寫鎖，但是同一個線程依然不能同時獲得讀鎖和寫鎖。InnoDB讀寫鎖的核心數(shù)據(jù)結(jié)構(gòu)rw_lock_t中，并沒有等待隊列的信息，因此不能保證先到的請求一定會先進(jìn)入臨界區(qū)。這與系統(tǒng)互斥量用PTHREAD_MUTEX_ADAPTIVE_NP來初始化有異曲同工之妙。

InnoDB讀寫鎖的核心實現(xiàn)在源文件sync0rw.cc和sync0rw.ic中，核心數(shù)據(jù)結(jié)構(gòu)rw_lock_t定義在sync0rw.h中。使用方法與InnoDB自旋互斥鎖很類似，只不過讀請求和寫請求要調(diào)用不同的函數(shù)。加讀鎖調(diào)用rw_lock_s_lock, 加寫鎖調(diào)用rw_lock_x_lock，釋放讀鎖調(diào)用rw_lock_s_unlock, 釋放寫鎖調(diào)用rw_lock_x_unlock，創(chuàng)建讀寫鎖調(diào)用rw_lock_create，釋放讀寫鎖調(diào)用rw_lock_free。函數(shù)rw_lock_x_lock_nowait和rw_lock_s_lock_nowait表示，當(dāng)加讀寫鎖失敗的時候，直接返回，而不是自旋等待。

核心機制

rw_lock_t中，核心的成員有以下幾個：lock_word, event, waiters, wait_ex_event，writer_thread, recursive。

與InnoDB自旋互斥鎖的lock_word不同，rw_lock_t中的lock_word是int 型，注意不是unsigned的，其取值范圍是(-2X_LOCK_DECR, X_LOCK_DECR]，其中X_LOCK_DECR為0x00100000，差不多100多W的一個數(shù)。在InnoDB自旋互斥鎖互斥鎖中，lock_word的取值范圍只有0，1，因為這兩個狀態(tài)就能把互斥鎖的所有狀態(tài)都表示出來了，也就是說，只需要查看一下這個lock_word就能確定當(dāng)前的線程是否能獲得鎖。rw_lock_t中的lock_word也扮演了相同的角色，只需要查看一下當(dāng)前的lock_word落在哪個取值范圍中，就確定當(dāng)前線程能否獲得鎖。至于rw_lock_t中的lock_word是如何做到這一點的，這其實是InnoDB讀寫鎖乃至InnoDB同步機制中最神奇的地方，下文我們會詳細(xì)分析。

event是一個InnoDB條件變量，當(dāng)當(dāng)前的鎖已經(jīng)被一個線程以寫鎖方式獨占時，后續(xù)的讀鎖和寫鎖都等待在這個event上，當(dāng)這個線程釋放寫鎖時，等待在這個event上的所有讀鎖和寫鎖同時競爭。waiters這變量，與event一起用，當(dāng)有等待者在等待時，這個變量被設(shè)置為1，否則為0，鎖被釋放的時候，需要通過這個變量來判斷有沒有等待者從而執(zhí)行os_event_set。

與InnoDB自旋互斥鎖不同，InnoDB讀寫鎖還有wait_ex_event和recursive兩個變量。wait_ex_event也是一個InnoDB條件變量，但是它用來等待第一個寫鎖（因為寫請求可能會被先前的讀請求堵?。?，當(dāng)先前到達(dá)的讀請求都讀完了，就會通過這個event來喚醒這個寫鎖的請求。

由于InnoDB讀寫鎖實現(xiàn)了寫鎖的遞歸，因此需要保存當(dāng)前寫鎖被哪個線程占用了，后續(xù)可以通過這個值來判斷是否是這個線程的寫鎖請求，如果是則加鎖成功，否則失敗，需要等待。線程的id就保存在writer_thread這個變量中。

recursive是個bool變量，用來表示當(dāng)前的讀寫鎖是否支持遞歸寫模式，在某些情況下，例如需要另外一個線程來釋放這個讀寫鎖（insert buffer需要這個功能）的時候，就不要開啟遞歸模式了。

接下來，我們來詳細(xì)介紹一下lock_word的變化規(guī)則：

1. 當(dāng)有一個讀請求加鎖成功時，lock_word原子遞減1。

2. 當(dāng)有一個寫請求加鎖成功時，lock_word原子遞減X_LOCK_DECR。

3. 如果讀寫鎖支持遞歸寫，那么第一個遞歸寫鎖加鎖成功時，lock_word依然原子遞減X_LOCK_DECR，而后續(xù)的遞歸寫鎖加鎖成功是，lock_word只是原子遞減1。

在上述的變化規(guī)則約束下，lock_word會形成以下幾個區(qū)間：

• lock_word == X_LOCK_DECR: 表示鎖空閑，即當(dāng)前沒有線程獲得了這個鎖。
• 0 < lock_word < X_LOCK_DECR: 表示當(dāng)前有X_LOCK_DECR – lock_word個讀鎖
• lock_word == 0: 表示當(dāng)前有一個寫鎖
• -X_LOCK_DECR < lock_word < 0: 表示當(dāng)前有-lock_word個讀鎖，他們還沒完成，同時后面還有一個寫鎖在等待
• lock_word <= -X_LOCK_DECR: 表示當(dāng)前處于遞歸鎖模式，同一個線程加了2 – (lock_word + X_LOCK_DECR)次寫鎖。

另外，還可以得出以下結(jié)論

1. 由于lock_word的范圍被限制（rw_lock_validate）在(-2X_LOCK_DECR, X_LOCK_DECR]中，結(jié)合上述規(guī)則，可以推斷出，一個讀寫鎖最多能加X_LOCK_DECR個讀鎖。在開啟遞歸寫鎖的模式下，一個線程最多同時加X_LOCK_DECR+1個寫鎖。

2. 在讀鎖釋放之前，lock_word一定處于(-X_LOCK_DECR, 0)U(0, X_LOCK_DECR)這個范圍內(nèi)。

3. 在寫鎖釋放之前，lock_word一定處于(-2*X_LOCK_DECR, -X_LOCK_DECR]或者等于0這個范圍內(nèi)。

4. 只有在lock_word大于0的情況下才可以對它遞減。有一個例外，就是同一個線程需要加遞歸寫鎖的時候，lock_word可以在小于0的情況下遞減。

接下來，舉個讀寫鎖加鎖的例子，方便讀者理解讀寫鎖底層加鎖的原理。假設(shè)有讀寫加鎖請求按照以下順序依次到達(dá)：R1->R2->W1->R3->W2->W3->R4，其中W2和W3是屬于同一個線程的寫加鎖請求，其他所有讀寫請求均來自不同線程。初始化后，lock_word的值為X_LOCK_DECR（十進(jìn)制值為1048576）。R1讀加鎖請求首先到，其發(fā)現(xiàn)lock_word大于0，表示可以加讀鎖，同時lock_word遞減1，結(jié)果為1048575，R2讀加鎖請求接著來到，發(fā)現(xiàn)lock_word依然大于0，繼續(xù)加讀鎖并遞減lock_word，最終結(jié)果為1048574。注意，如果R1和R2幾乎是同時到達(dá)，即使時序上是R1先請求，但是并不保證R1首先遞減，有可能是R2首先拿到原子操作的執(zhí)行權(quán)限。如果在R1或者R2釋放鎖之前，寫加鎖請求W1到來，他發(fā)現(xiàn)lock_word依舊大于0，于是遞減X_LOCK_DECR，并把自己的線程id記錄在writer_thread這個變量里，再檢查lock_word的值（此時為-2），由于結(jié)果小于0，表示前面有未完成的讀加鎖請求，于是其等待在wait_ex_event這個條件變量上。后續(xù)的R3, W2, W3, R4請求發(fā)現(xiàn)lock_word小于0，則都等待在條件變量event上，并且設(shè)置waiter為1，表示有等待者。假設(shè)R1先釋放讀鎖(lock_word遞增1)，R2后釋放(lock_word再次遞增1)。R2釋放后，由于lock_word變?yōu)?了，其會在wait_ex_event上調(diào)用os_event_set，這樣W3就被喚醒了，他可以執(zhí)行臨界區(qū)內(nèi)的代碼了。W3執(zhí)行完后，lock_word被恢復(fù)為X_LOCK_DECR，然后其發(fā)現(xiàn)waiter為1，表示在其后面有新的讀寫加鎖請求在等待，然后在event上調(diào)用os_event_set，這樣R3, W2, W3, R4同時被喚醒，進(jìn)行原子操作執(zhí)行權(quán)限爭搶(可以簡單的理解為誰先得到cpu調(diào)度)。假設(shè)W2首先搶到了執(zhí)行權(quán)限，其會把lock_word再次遞減為0并自己的線程id記錄在writer_thread這個變量里，當(dāng)檢查lock_word的時候，發(fā)現(xiàn)值為0，表示前面沒有讀請求了，于是其就進(jìn)入臨界區(qū)執(zhí)行代碼了。假設(shè)此時，W3得到了cpu的調(diào)度，由于lock_word只有在大于0的情況下才能遞減，所以其遞減lock_word失敗，但是其通過對比writer_thread和自己的線程id，發(fā)現(xiàn)前面的寫鎖是自己加的，如果這個時候開啟了遞歸寫鎖，即recursive值為true，他把lock_word再次遞減X_LOCK_DECR（現(xiàn)在lock_word變?yōu)?X_LOCK_DECR了），然后進(jìn)入臨界區(qū)執(zhí)行代碼。這樣就保證了同一個線程多次加寫鎖也不發(fā)生死鎖，也就是遞歸鎖的概念。后續(xù)的R3和R4發(fā)現(xiàn)lock_word小于等于0，就直接等待在event條件變量上，并設(shè)置waiter為1。直到W2和W3都釋放寫鎖，lock_word又變?yōu)閄_LOCK_DECR，最后一個釋放的，檢查waiter變量發(fā)現(xiàn)非0，就會喚醒event上的所有等待者，于是R3和R4就可以執(zhí)行了。

讀寫鎖的核心函數(shù)函數(shù)結(jié)構(gòu)跟InnoDB自旋互斥鎖的基本相同，主要的區(qū)別就是用rw_lock_x_lock_low和rw_lock_s_lock_low替換了__sync_lock_test_and_set原子操作。rw_lock_x_lock_low和rw_lock_s_lock_low就按照上述的lock_word的變化規(guī)則來原子的改變（依然使用了__sync_lock_test_and_set）lock_word這個變量。

在MySQL 5.7中，讀寫鎖除了可以加讀鎖(Share lock)請求和加寫鎖(exclusive lock)請求外，還可以加share exclusive鎖請求，鎖兼容性如下：

LOCK COMPATIBILITY MATRIX 
 
    S SX  X 
 
S  +  +  - 
 
SX +  -  - 
 
X  -  -  - 

按照WL#6363的說法，是為了修復(fù)index->lock這個鎖的沖突。

輔助結(jié)構(gòu)

InnoDB同步機制中，還有很多使用的輔助結(jié)構(gòu)，他們的作用主要是為了監(jiān)控方便和死鎖的預(yù)防和檢測。這里主要介紹sync array, sync thread level array和srv_error_monitor_thread。

sync array主要的數(shù)據(jù)結(jié)構(gòu)是sync_array_t，可以把他理解為一個數(shù)據(jù)，數(shù)組中的元素為sync_cell_t。當(dāng)一個鎖（InnoDB自旋互斥鎖或者InnoDB讀寫鎖，下同）需要發(fā)生os_event_wait等待時，就需要在sync array中申請一個sync_cell_t來保存當(dāng)前的信息，這些信息包括等待鎖的指針（便于死鎖檢測），在哪一個文件以及哪一行發(fā)生了等待（也就是mutex_enter, rw_lock_s_lock或者rw_lock_x_lock被調(diào)用的地方，只在debug模式下有效），發(fā)生等待的線程（便于死鎖檢測）以及等待開始的時間（便于統(tǒng)計等待的時間）。當(dāng)鎖釋放的時候，就把相關(guān)聯(lián)的sync_cell_t重置為空，方便復(fù)用。sync_cell_t在sync_array_t中的個數(shù)，是在初始化同步模塊時候就指定的，其個數(shù)一般為OS_THREAD_MAX_N，而OS_THREAD_MAX_N是在InnoDB初始化的時候被計算，其包括了系統(tǒng)后臺開啟的所有線程，以及max_connection指定的個數(shù)，還預(yù)留了一些。由于一個線程在某一個時刻最多只能發(fā)生一個鎖等待，所以不用擔(dān)心sync_cell_t不夠用。從上面也可以看出，在每個鎖進(jìn)行等待和釋放的時候，都需要對sync array操作，因此在高并發(fā)的情況下，單一的sync array可能成為瓶頸，在MySQL 5.6中，引入了多sync array, 個數(shù)可以通過innodb_sync_array_size進(jìn)行控制，這個值默認(rèn)為1，在高并發(fā)的情況下，建議調(diào)高。

InnoDB作為一個成熟的存儲引擎，包含了完善的死鎖預(yù)防機制和死鎖檢測機制。在每次需要鎖等待時，即調(diào)用os_event_wait之前，需要啟動死鎖檢測機制來保證不會出現(xiàn)死鎖，從而造成無限等待。在每次加鎖成功（lock_word遞減后，函數(shù)返回之前）時，都會啟動死鎖預(yù)防機制，降低死鎖出現(xiàn)的概率。當(dāng)然，由于死鎖預(yù)防機制和死鎖檢測機制需要掃描比較多的數(shù)據(jù)，算法上也有遞歸操作，所以只在debug模式下開啟。

死鎖檢測機制主要依賴sync array中保存的信息以及死鎖檢測算法來實現(xiàn)。死鎖檢測機制通過sync_cell_t保存的等待鎖指針和發(fā)生等待的線程以及教科書上的有向圖環(huán)路檢測算法來實現(xiàn)，具體實現(xiàn)在sync_array_deadlock_step和sync_array_detect_deadlock中實現(xiàn)，仔細(xì)研究后發(fā)現(xiàn)個小問題，由于sync_array_find_thread函數(shù)僅僅在當(dāng)前的sync array中遍歷，當(dāng)有多個sync array時（innodb_sync_array_size > 1）,如果死鎖發(fā)生在不同的sync array上，現(xiàn)有的死鎖檢測算法將無法發(fā)現(xiàn)這個死鎖。

死鎖預(yù)防機制是由sync thread level array和全局鎖優(yōu)先級共同保證的。InnoDB為了降低死鎖發(fā)生的概率，上層的每種類型的鎖都有一個優(yōu)先級。例如回滾段鎖的優(yōu)先級就比文件系統(tǒng)page頁的優(yōu)先級高，雖然兩者底層都是InnoDB互斥鎖或者InnoDB讀寫鎖。有了這個優(yōu)先級，InnoDB規(guī)定，每個鎖創(chuàng)建是必須制定一個優(yōu)先級，同一個線程的加鎖順序必須從優(yōu)先級高到低，即如果一個線程目前已經(jīng)加了一個低優(yōu)先級的鎖A，在釋放鎖A之前，不能再請求優(yōu)先級比鎖A高(或者相同)的鎖。形成死鎖需要四個必要條件，其中一個就是不同的加鎖順序，InnoDB通過鎖優(yōu)先級來降低死鎖發(fā)生的概率，但是不能完全消除。原因是可以把鎖設(shè)置為SYNC_NO_ORDER_CHECK這個優(yōu)先級，這是最高的優(yōu)先級，表示不進(jìn)行死鎖預(yù)防檢查，如果上層的程序員把自己創(chuàng)建的鎖都設(shè)置為這個優(yōu)先級，那么InnoDB提供的這套機制將完全失效，所以要養(yǎng)成給鎖設(shè)定優(yōu)先級的好習(xí)慣。sync thread level array是一個數(shù)組，每個線程單獨一個，在同步模塊初始化時分配了OS_THREAD_MAX_N個，所以不用擔(dān)心不夠用。這個數(shù)組中記錄了某個線程當(dāng)前鎖擁有的所有鎖，當(dāng)新加了一個鎖B時，需要掃描一遍這個數(shù)組，從而確定目前線程所持有的鎖的優(yōu)先級都比鎖B高。

最后，我們來講講srv_error_monitor_thread這個線程。這是一個后臺線程，在InnoDB啟動的時候啟動，每隔1秒鐘執(zhí)行一下指定的操作。跟同步模塊相關(guān)的操作有兩點，去除無限等待的鎖和報告長時間等待的異常鎖。

去除無線等待的鎖，如上文所屬，就是sync_arr_wake_threads_if_sema_free這個函數(shù)。這個函數(shù)通過遍歷sync array，如果發(fā)現(xiàn)鎖已經(jīng)可用(sync_arr_cell_can_wake_up)，但是依然有等待者，則直接調(diào)用os_event_set把他們喚醒。這個函數(shù)是為了解決由于cpu亂序執(zhí)行或者編譯器指令重排導(dǎo)致鎖無限等待的問題，但是可以通過內(nèi)存屏障技術(shù)來避免，所以可以去掉。

報告長時間等待的異常鎖，通過sync_cell_t里面記錄的鎖開始等待時間，我們可以很方便的統(tǒng)計鎖等待發(fā)生的時間。在目前的實現(xiàn)中，當(dāng)鎖等待超過240秒的時候，就會在錯誤日志中看到信息。如果同一個鎖被檢測到等到超過600秒且連續(xù)10次被檢測到，則InnoDB會通過assert來自殺。。。相信當(dāng)做運維DBA的同學(xué)一定看到過如下的報錯：

InnoDB: Warning: a long semaphore wait: 
 
--Thread 139774244570880 has waited at log0read.h line 765 for 241.00 seconds the semaphore: 
 
Mutex at 0x30c75ca0 created file log0read.h line 522, lock var 1 
 
Last time reserved in file /home/yuhui.wyh/mysql/storage/innobase/include/log0read.h line 765, waiters flag 1 
 
InnoDB: ###### Starts InnoDB Monitor for 30 secs to print diagnostic info: 
 
InnoDB: Pending preads 0, pwrites 0 

一般出現(xiàn)這種錯誤都是pread或者pwrite長時間不返回，導(dǎo)致鎖超時。至于pread或者pwrite長時間不返回的root cause常常是有很多的讀寫請求在極短的時間內(nèi)到達(dá)導(dǎo)致磁盤扛不住或者磁盤已經(jīng)壞了。。。

總結(jié)

本文詳細(xì)介紹了原子操作，條件變量，互斥鎖以及讀寫鎖在InnoDB引擎中的實現(xiàn)。原子操作由于其能減少不必要的用戶態(tài)和內(nèi)核態(tài)的切換以及更精簡的cpu指令被廣泛的應(yīng)用到InnoDB自旋互斥鎖和InnoDB讀寫鎖中。InnoDB條件變量使用更加方便，但是一定要注意條件通知必須在條件等待之后，否則會有無限等待發(fā)生。InnoDB自旋互斥鎖加鎖和解鎖過程雖然復(fù)雜但是都是必須的操作。InnoDB讀寫鎖神奇的lock_word控制方法給我們留下了深刻影響。正因為InnoDB底層同步機制的穩(wěn)定、高效，MySQL在我們的服務(wù)器上才能運行的如此穩(wěn)定。