[[171774]]

一：引子

InnoDB是符合MVCC(Multi-Version Concurrency Control)規(guī)范的，通俗的講就是寫加鎖，讀不加鎖，讀寫不沖突(有些情況下是不符合MVCC的，比如當(dāng)isolation級(jí)別為serializable時(shí)，是讀寫沖突的，這又跟autocommit參數(shù)的值有關(guān)，這里不展開講)。有這么一個(gè)前提mysql才能對(duì)并發(fā)有不錯(cuò)的處理能力，但是很多時(shí)候我們不希望多個(gè)線程同時(shí)修改同一個(gè)數(shù)據(jù)，我們的做法就是設(shè)置isolation的級(jí)別，保證數(shù)據(jù)的一致性。我們接下來就來探討下InnoDB中的同步機(jī)制。

二：為什么要同步機(jī)制

比如我們現(xiàn)在mysql-server上跟客戶端建立里3個(gè)連接,某一時(shí)刻這個(gè)三個(gè)連接同時(shí)發(fā)來了一個(gè)請(qǐng)求，需要把名為"bugall"的用戶的money增加10000，在這個(gè)時(shí)候你不希望別的連接再來修改這個(gè)值，通常我們會(huì)在"bugall"這個(gè)用戶的數(shù)據(jù)上加一把排它鎖，這樣的話所有的對(duì)"bugall"對(duì)應(yīng)數(shù)據(jù)做修改的請(qǐng)求連接都會(huì)被序列化，對(duì)"bugall"做修改的時(shí)候其它修改的請(qǐng)求都會(huì)被阻塞。這個(gè)阻塞過程是怎么實(shí)現(xiàn)的呢?或是說這個(gè)同步機(jī)制是怎么實(shí)現(xiàn)的?我們接著往下看。

三：內(nèi)存模型

內(nèi)存模型決定里CPU怎樣訪問內(nèi)存,以及并發(fā)情況下各CPU之間的影響。但是內(nèi)存模型并不包括虛擬地址轉(zhuǎn)換,因?yàn)樽罱KCPU訪問的內(nèi)存的物理地址，內(nèi)存模型主要關(guān)心的是CPU和內(nèi)存之間數(shù)據(jù)和物理地址的傳輸。不同硬件之間內(nèi)存模型的差異在于硬件是根據(jù)怎樣的順序來執(zhí)行l(wèi)oad和store指令，改變執(zhí)行順序或許有可能帶性能的提升，除此之外,內(nèi)存模型還指定了多個(gè)處理器訪問同一內(nèi)存地址的行為，最簡(jiǎn)單的內(nèi)存模型就是順序內(nèi)存模型(sequential memory model),也稱為strong ordering，在這個(gè)模型下,所有的load和store指令是根據(jù)程序運(yùn)行順序執(zhí)行的。

load %r1,A //將內(nèi)存地址A中的值放入寄存器r1 
load %r2,B //將內(nèi)存地址B中的值放入寄存器r2 
add %r3,%r1,%r2 //將寄存器r1與r2的值相加,并放入寄存器r3 
store %r3,c //將寄存器r3中的值寫入到內(nèi)存地址c中  

在數(shù)序內(nèi)存模型下,執(zhí)行的順序都是按照程序運(yùn)行的順序進(jìn)行的，若還未將內(nèi)存地址A中的值取到，則不能執(zhí)行從內(nèi)存地址B中取值的操作除了要求內(nèi)存操作的順序與程序運(yùn)行順序一致，順序內(nèi)存模型， 還要求從CPU或者I/O設(shè)備中讀取或者寫入操作是原子的,即一旦開始了，這些操作就不能被其他的內(nèi)存操作中斷 。

四：臨界區(qū)與互斥

雖然順序內(nèi)存模型的執(zhí)行順序是根據(jù)程序的運(yùn)行順序，但是多個(gè)CPU對(duì)同一個(gè)內(nèi)存地址的訪問順序確實(shí)不確定的，而正是因?yàn)樯倮镌L問的確定性從而導(dǎo)致競(jìng)爭(zhēng)(race condition)條件的發(fā)生。為了說明這個(gè)問題，假設(shè)有一個(gè)全局的計(jì)數(shù)器counter，CPU操作每次將該值加1，同時(shí)要求該計(jì)數(shù)器需要非常精確的展示當(dāng)前CPU的操作次數(shù) 。

load %r1,counter //將計(jì)數(shù)器counter的值讀取到寄存器r1 
add %r1,1 //將寄存器r1中的值加1 
store %r1,counter //并存放到計(jì)數(shù)器counter中 

 接下來有兩種CPU順序的執(zhí)行累加操作

 在該順序下,兩個(gè)CPU執(zhí)行的時(shí)間交錯(cuò),沒有發(fā)生race condition，因此***得到的值符合之前的預(yù)期,然而,還有一種可能性。

可以發(fā)現(xiàn):若當(dāng)兩個(gè)CPU同時(shí)進(jìn)行l(wèi)oad操作時(shí),那么最終將會(huì)產(chǎn)生錯(cuò)誤的結(jié)果。因?yàn)槊總€(gè)CPU在自增前讀到的數(shù)據(jù)都是0,那么不管之后的操作順尋如何,得到的結(jié)果永遠(yuǎn)會(huì)是1,而正確的值應(yīng)為2。 

在兩個(gè)或者多個(gè)CPU之間更新共享的數(shù)據(jù)結(jié)構(gòu)指令序列會(huì)產(chǎn)生race condition，指令序列本身稱為臨界區(qū)(critical section)，操作的數(shù)據(jù)稱為臨界資源(critical resource)。如上面代碼中的三個(gè)指令序列可視為臨界區(qū),為里消除多個(gè)CPU并發(fā)訪問臨界區(qū)而導(dǎo)致的race condition，故需要限制同一個(gè)時(shí)刻只允許一個(gè)CPU執(zhí)行臨界區(qū)，而這就是互斥(mutex exclusion)。

五：原子操作

為了保證同一時(shí)刻只允許一個(gè)CPU執(zhí)行臨界區(qū)，當(dāng)前硬件都提供里基于原子的read-modify-write操作。read-modify-write操作允許一個(gè)CPU讀取一個(gè)值，修改該值,并將修改完成的值寫回到內(nèi)存的三個(gè)操作作為一個(gè)原子總線操作，其在CPU中是一個(gè)特別的指令，并且只有在需要同步的時(shí)候才使用。對(duì)于具體進(jìn)行怎樣的modify操作每個(gè)實(shí)現(xiàn)標(biāo)準(zhǔn)可能并不相同，但通常來說，目前的CPU都支持test-and-set(TAS)指令，該指令從內(nèi)存中讀取一個(gè)字節(jié)或者一個(gè)word(4個(gè)字節(jié))，然后和0進(jìn)行比較，并且無條件的將其在內(nèi)存中的值設(shè)置為1，所有這些操作都是原子操作。一旦CPU在執(zhí)行test-and-set操作，其它任何CPU和I/O設(shè)備都不能使用總線，通過test-and-set指令，操作系統(tǒng)或者數(shù)據(jù)庫系統(tǒng)可以構(gòu)造更高級(jí)別的同步操作，如spin lock(自旋鎖)，semephore(信號(hào)量)。

六：自旋鎖

在TAS的基礎(chǔ)上，可以實(shí)現(xiàn)很多互斥的數(shù)據(jù)結(jié)構(gòu)，而spin lock則是使用最為廣泛,也最為簡(jiǎn)單的一種互斥結(jié)構(gòu)。spin lock使用來對(duì)short-term critical section進(jìn)行互斥的數(shù)據(jù)結(jié)構(gòu)，特別需要注意的是，spin lock用來互斥的critical section的代碼應(yīng)該比較少，即一般可以較快執(zhí)行完代碼，并釋放spin lock，因?yàn)閟pin lock會(huì)使其它需要獲取鎖的線程進(jìn)入忙等,占用CPU。為在多CPU環(huán)境中利用test_and_set指令實(shí)現(xiàn)進(jìn)程互斥，硬件需要提供進(jìn)一步的支持，以保證test_and_set指令執(zhí)行的原子性。這種支持目前多以"鎖總線"(bus locking)的形式提供的，由于test_and_set指令對(duì)內(nèi)存的兩次操作都需要經(jīng)過總線,在執(zhí)行test_and_set指令之前鎖住總線,在執(zhí)行test_and_set指令后鎖定總線,即可保證test_and_set指令執(zhí)行的原子性。

七：自旋鎖實(shí)現(xiàn)

實(shí)現(xiàn)最基本的TAS指令就是使用swap-atomic操作。該操作僅僅將寄存器中的值與內(nèi)存的值進(jìn)行交換，通過swap-atomic 可以用來構(gòu)造test-and-set操作，首先將寄存器中的值設(shè)置為1，然后執(zhí)行atomic swap,***和寄存器中的值進(jìn)行比較。

int 
  test_and_set(volatile int* addr){ 
      int old_value; 
      old_value = swap_atomic(addr,1); 
      if(old_value==0){ 
          return 0; 
      } 
      return 1; 
  }   

變量addr的類型是init，表明需要操作的單位是word.volatile修飾詞告訴編譯器從內(nèi)存中讀取addr的值，因?yàn)榧词贡静僮鳑]有修改addr的值，其它CPU也可能修改該值,那么在這中情況下，可能會(huì)導(dǎo)致執(zhí)行test_and_set得到錯(cuò)誤的結(jié)果。swap_atomic函數(shù)執(zhí)行swap-atomic的硬件指令,并返回交換前內(nèi)存中addr的值，test-and-set操作是由兩個(gè)獨(dú)立的操作組合為一個(gè)指令，***個(gè)階段是將addr中的值設(shè)置為1,第二階段比較之前取得的結(jié)果。初始化時(shí)，將其值設(shè)置為0 。

typedef init lock_t 
   void 
   initlock(volatile lock_t *lock_status){ 
       *lock_status =  0; 
   }  

使用前面的TAS方法講一個(gè)spin lock對(duì)象上鎖 

void 
    lock(volatile lock_t* lock_statue){ 
        while(test_and_set(lock_status)==1); 
    }  

當(dāng)lock_status的值為0時(shí),test_and_set返回的結(jié)果為0,上鎖成功。若該對(duì)象已經(jīng)被使用,那么需要在while中循環(huán)(spin),知道對(duì)象釋放鎖。這也是spin lock名字的由來。