[[171774]]

一：引子

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

二：為什么要同步機制

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

三：內存模型

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

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

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

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

雖然順序內存模型的執(zhí)行順序是根據程序的運行順序，但是多個CPU對同一個內存地址的訪問順序確實不確定的，而正是因為少里訪問的確定性從而導致競爭(race condition)條件的發(fā)生。為了說明這個問題，假設有一個全局的計數器counter，CPU操作每次將該值加1，同時要求該計數器需要非常精確的展示當前CPU的操作次數 。

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

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

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

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

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

五：原子操作

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

六：自旋鎖

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

七：自旋鎖實現

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

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修飾詞告訴編譯器從內存中讀取addr的值，因為即使本操作沒有修改addr的值，其它CPU也可能修改該值,那么在這中情況下，可能會導致執(zhí)行test_and_set得到錯誤的結果。swap_atomic函數執(zhí)行swap-atomic的硬件指令,并返回交換前內存中addr的值，test-and-set操作是由兩個獨立的操作組合為一個指令，***個階段是將addr中的值設置為1,第二階段比較之前取得的結果。初始化時，將其值設置為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); 
    }  

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