[[171774]]

一：引子

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

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

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

三：內(nèi)存模型

內(nèi)存模型決定里CPU怎樣訪問內(nèi)存,以及并發(fā)情況下各CPU之間的影響。但是內(nèi)存模型并不包括虛擬地址轉(zhuǎn)換,因為最終CPU訪問的內(nèi)存的物理地址，內(nèi)存模型主要關(guān)心的是CPU和內(nèi)存之間數(shù)據(jù)和物理地址的傳輸。不同硬件之間內(nèi)存模型的差異在于硬件是根據(jù)怎樣的順序來執(zhí)行l(wèi)oad和store指令，改變執(zhí)行順序或許有可能帶性能的提升，除此之外,內(nèi)存模型還指定了多個處理器訪問同一內(nèi)存地址的行為，最簡單的內(nèi)存模型就是順序內(nèi)存模型(sequential memory model),也稱為strong ordering，在這個模型下,所有的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)行順序，但是多個CPU對同一個內(nèi)存地址的訪問順序確實(shí)不確定的，而正是因為少里訪問的確定性從而導(dǎo)致競爭(race condition)條件的發(fā)生。為了說明這個問題，假設(shè)有一個全局的計數(shù)器counter，CPU操作每次將該值加1，同時要求該計數(shù)器需要非常精確的展示當(dāng)前CPU的操作次數(shù) 。

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

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

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

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

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

五：原子操作

為了保證同一時刻只允許一個CPU執(zhí)行臨界區(qū)，當(dāng)前硬件都提供里基于原子的read-modify-write操作。read-modify-write操作允許一個CPU讀取一個值，修改該值,并將修改完成的值寫回到內(nèi)存的三個操作作為一個原子總線操作，其在CPU中是一個特別的指令，并且只有在需要同步的時候才使用。對于具體進(jìn)行怎樣的modify操作每個實(shí)現(xiàn)標(biāo)準(zhǔn)可能并不相同，但通常來說，目前的CPU都支持test-and-set(TAS)指令，該指令從內(nèi)存中讀取一個字節(jié)或者一個word(4個字節(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)造更高級別的同步操作，如spin lock(自旋鎖)，semephore(信號量)。

六：自旋鎖

在TAS的基礎(chǔ)上，可以實(shí)現(xiàn)很多互斥的數(shù)據(jù)結(jié)構(gòu)，而spin lock則是使用最為廣泛,也最為簡單的一種互斥結(jié)構(gòu)。spin lock使用來對short-term critical section進(jìn)行互斥的數(shù)據(jù)結(jié)構(gòu)，特別需要注意的是，spin lock用來互斥的critical section的代碼應(yīng)該比較少，即一般可以較快執(zhí)行完代碼，并釋放spin lock，因為spin lock會使其它需要獲取鎖的線程進(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指令對內(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的值，因為即使本操作沒有修改addr的值，其它CPU也可能修改該值,那么在這中情況下，可能會導(dǎo)致執(zhí)行test_and_set得到錯誤的結(jié)果。swap_atomic函數(shù)執(zhí)行swap-atomic的硬件指令,并返回交換前內(nèi)存中addr的值，test-and-set操作是由兩個獨(dú)立的操作組合為一個指令，***個階段是將addr中的值設(shè)置為1,第二階段比較之前取得的結(jié)果。初始化時，將其值設(shè)置為0 。

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

使用前面的TAS方法講一個spin lock對象上鎖 

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

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