一致性模型之Sequential Consistency

Sequential Consistency的定義

Sequential Consistency的精確定義來自於Leslie Lamport老哥(以後我們會多次提到他)。

他本來是定義了基於共享內存的多CPU並行計算的一致性模型，但是也可以推廣到分散式系統中，實際上多CPU並行計算也都可以認為是分散式系統。

模型的定義是

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program

放到分散式系統里，意思就是不管系統怎麼運行，得到的結果就好像把所有節點的所有操作按照某個sequential order排序後運行，但是在這個sequential order順序中，來自同一個節點的操作仍然保持著它們在節點中被指定的順序。

Sequential Consistency的例子

Leslie Lamport老哥的說法一貫的佶屈聱牙，我們通過幾個例子來看一下。圖中從左向右表示物理時間，W(a)表示寫入數據a，R(a)表示讀出數據a。

可以看出，這兩個系統都不是很完美，但是它們的模型都可以看做Sequential Consistency，因為通過如下變換，總是可以自圓其說，也就是可以找到符合定義的sequential order。

Sequential Consistency和硬體

也許有人會問，同一個進程中保留操作順序不是顯而易見的么?實際上隨著硬體技術，尤其是多核、多CPU技術的發展，一個CPU核心運行的進程，不一定能觀測到另一個核心進程的操作順序。

在論文中，Leslie Lamport老哥舉了這樣一個例子，有一個互斥演算法，要求兩個進程不能同時執行臨界區方法，a和b兩個變數初始值為0。正常情況下，最多一個進程執行臨界區方法。

進程1執行序列如下：

a = 1

if (b!=0){

臨界區方法

}

進程2執行序列如下：

b = 1

if (a!=0){

臨界區方法

}

這個程序在多核CPU機器上運行時，有可能兩個進程同時進入臨界區。為什麼呢?

我們先看一下現代CPU的架構

CPU一般具有多個核心，每個核心都有自己的L1 cache和L2 cache，cache之上還有Load Buffer和Store Buffer。寫入時，處理器很有可能僅僅將數據寫入Store Buffer，稍後再將Store Buffer中的數據統一寫回cache，有可能再過一會兒才將cache的數據寫回內存。同樣，一個核心讀取的數據說不定也已經被另一個核心修改過，只是它不知道而已。

所以上述進程對a和b的賦值，很有可能沒被對方感知。

為了保證Sequential Consistency，Leslie Lamport老哥在論文中提出了兩個要求:

Each processor issues memory requests in the order specified by its program

Memory requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request on this queue.

但是如果在硬體層滿足Sequential Consistency，肯定會大大降低效率，所以一般這些工作就會交給上層的軟體開發人員來做。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！