深入淺析一致性模型之Linearizability

在Sequential Consistency之後，Linearizability出現了，它具有更強的一致性。

Linearizability的官方定義是來自於《Linearizability: A Correctness Condition for Concurrent Objects》，相比於Sequential Consistency定義的簡潔，它的定義可是非常詳細，我們一起簡要的看一下吧。

history

一個並行系統的一個執行序列叫做一個history，由一系列的invocation和response事件組成。

invocation事件一般寫作

x是操作對象，op表示操作，args*是參數列表，A是進程。

Invocation的response寫作

term表示終止條件，res*是結果的列表。

如果一個response和invocation的進程和操作對象一致，認為這個response match這個invocation。

假設H是一個history，那麼complete(H)是H只包含invocation和對應的match的response的最長子序列。

sequential history

sequential history的定義很簡單：

第一個事件是invocation

如果一個invocation不是在最後，那麼每個invocation後面都緊跟著match的response。每個response後面都緊跟著invocation。

原文中的定義是

Each invocation, except possibly the last, is immediately followed by a matching response. Each response is immediately followed by a matching invocation.

我感覺有問題，因為response可以match invocation，而invocation怎麼match response則沒有定義。

這裡可以看出，sequential history中，操作沒有互相覆蓋，每個操作都認為是原子的，瞬時生效。

legal sequential history

對象x在history H的子歷史是H中所有對象為x的子序列。寫作

H|x

對象x應該定義一個sequential specification，表示它的行為屬性，比如先進先出就是隊列的行為屬性。

對一個sequential history H，如果每個對象的子歷史都符合這個對象的sequential specification，就說明H是legal的。

equivalent history

進程P在history H中的子歷史指的是H中所有進程為P的子序列。寫作

H|P

對於歷史H和H』來說，如果對每個進程P，都有H|P=H』|P，那麼H和H』就是equivalent

linearizable history

對於一個history H，我們定義一個偏序關係h，如果操作a的response早於操作b的invocation，那麼a p= b。注意這裡的「早於」比較的是真實的物理時間(real-time)。=

注意這是一個偏序關係而不是全序關係，因此在H中，有可能存在操作X和Y，既不存在Xh p= h= x，例如下圖中a和b就不存在這種關係。= y=

給定一個history H，我們可以在H結尾追加任意個數的response使之變成H』

當H』滿足以下條件時，認為H是linearizable：

complete(H』)和某個legal sequential history S是equivalent的

h p= s=

我的理解是，linearizable history和一個保留了原來真實時間順序的legal sequential history等效了。

下面的執行歷史可以認為是linearizable。

因為可以找到某個符合條件的S。

注意，W(1)h p= h= r(1)，這兩個關係必須要保留，但w(1)和w(3)則不存在先後關係。=

Linearizability和Sequential Consistency

Linearizability比Sequential Consistency要嚴格很多，實際上Sequential Consistency僅僅要求本地順序得到保留，而Linearizability要求保留真實時間順序。

下面的系統可以認為Sequential Consistency，但不是Linearizability。

Linearizability和Serializability

Linearizability經常和Serializability混淆，實際上Serializability一般指的是資料庫的隔離級別，兩者描述的不是同一個領域的東西。

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