分布式系統一致性的發展歷史（一）

編者按：本文來自 “點融黑幫”（微信號：DianrongMafia）吳強，前盛大架構師，現在在點融網任首席社交平臺架構師。專注分布式系統和移動應用，有十三年的開發經驗，目前在點融做最愛的兩件事情：寫代碼和重構代碼。

分布式系統是一個非常有趣的話題, 在我之前的幾年工作當中發現很多開發人員在評估和使用分布式系統的時候比較關注 benchmark 和高可用性, 但經常不太關心分布式系統的一致性問題, 所以我打算在業余時間花點時間寫這樣一個系列文章來幫助開發人員更好的理解一致性問題.

1. 前言

在一個理想的世界里, 我們應該只有一個一致性模型. 但是多路處理器和分布式系統中的一致性問題是一個非常難以解決的問題. 當系統大多還都是單體應用, 處理器性能提升還是靠縮小晶體管體積的年代, 一致性問題還不是一個非常大的問題, 但是從 90年 代開始, 互聯網公司大量出現, 互聯網公司處理的數據量遠遠超過了人類歷史上任何一個時期的傳統企業所需要處理的數據量, 大型的互聯網公司甚至開始自己采購零部件自己組裝服務器, 服務器市場上排名除了 IBM, HP 之外還出現了 “Others”. NoSQL 已經被互聯網公司廣泛接受, Micro Service 的出現讓數據和計算的分布比歷史上任何時期都更加的水平, 在這個背景下, 分布式系統給一致性問題帶來了巨大的挑戰, 理想情況下的一致性模型在分布式系統中幾乎無法實現, 所以我們不得不設計應用于不同場景的各種一致性模型.

實際上在互聯網蓬勃發展之前, 有些有遠見的科學家們從 70年 代就開始在多路處理器級別上研究一致性模型. 過去的 10年 間, 計算機處理器的速度提升越來越困難, 摩爾在 1965年 告訴我們 12 個月晶體管密度提升一倍, 計算性能提升一倍 (1975 修正為 24 個月), 但是 2002年1月Moore 在 Intel 開發者論壇上提出 Moore’ s Law 預計會在 2017年 終結, 一旦晶體管體積進入皮米級別, 晶體管將不得不接近原子大小, 我們很快將無法突破物理的基礎限制. 事實上從 2012年 開始晶體管密度和主頻速度的提高速度明顯放慢. 人們不得不開始轉向橫向伸縮, 提高處理器的并行處理能力. 下圖顯示了在 2012年 出現了晶體管體積縮小速度的突然放緩.

圖片來源: futuretimeline.net

而這個過程中, 一致性問題逐漸愈發重要. 本文的目的就是帶你回顧從 70年 代起, 到如今百花齊放的分布式系統中一致性問題的發展和演化. 你可能已經了解了某些一致性模型, 本文會幫你把它們按照發展歷程穿連起來, 如果你對一致性模型了解很少, 本文可以幫助你從一千英尺的高空俯瞰一致性問題, 通過非數學的語言, 結合工程中的例子, 幫你入門. 這個系列的文章可能需要你放慢閱讀速度, 如果有些地方看不明白或者想更深入的探討, 你可以去查閱所引用的論文. 由于過程倉促, 難免有疏漏和錯誤, 還夾雜著個人觀點, 如有錯誤歡迎指出: daniel.y.woo@gmail.com.

本篇文章作為本系列的第一篇文章將會介紹 1978年 提出的 Lamport Clock 對分布式系統的啟發, 1979年 提出的 Sequential Consistency 和 1987年 提出的最重要的一致性模型 Linearizability.

2. 開天辟地：時間，時間和順序，1978

狹義上的分布式系統是指通過網絡連接的計算機系統, 每個計算節點承擔獨立的計算和存儲, 節點之間通過網絡協同工作, 因此整個系統中的事件可以同時發生. 一致性不是簡單的讓兩個節點最終對一個值的結果一致, 很多時候還需要對這個值的變化歷史在不同節點上的觀點也要一致. 比如一個變量 x 如果在一個進程上看到的狀態是從 1 變成 2 再變成 4, 最后變成 3, 而另外一個進程看到的狀態變化是 1, 4, 3, 那么根據應用的場景, 有可能沒問題, 也有可能會有嚴重的問題. 各個節點觀察到的順序不同是因為計算機網絡絕大多數都是異步的, 盡管單個 TCP 連接內可以保證消息有序, 但是一旦網絡出現問題, 你會不得不重建 TCP 連接, 而多個 TCP 連接之間的消息沒有順序約定, 異步網絡的延時和順序還是沒有保證的, 你不能簡單的以接受到消息的時間作為事件的順序判斷的依據. 在多路處理器上也有同樣類似的一致性問題, 因為多個處理器或者處理器核心之間也需要面對不可預料的事件順序問題. 所以, 一致性并不是一個簡單的問題.

舉個現實的例子, 比如你有兩個數據中心, 你通過 DNS 解析把用戶分別引導到離用戶最近的數據中心, 然后數據中心之間做雙向數據同步. 但是如果用戶使用你的系統的時候前后兩個寫入正好發生在切換網絡的時候 (或者更換了代理服務器, 或者換了手機操作, DNS 解析調整, 等等), 那么用戶可能會把兩個請求寫入了兩個數據中心. 因為兩個數據中心沒有辦法保證時間精確同步, 網絡的延遲也很大, 這兩個寫入操作的時間順序就非常重要, 想要合并和同步這兩個寫入操作并不是那么簡單的. 如果這兩個操作之間是有因果關系的, 比如第二個請求是基于第一個請求的返回結果的, 那么這兩個請求之間的邏輯順序就非常重要.

要理解一致性模型, 先要理解分布式系統中的時間, 事件和順序, 我們先來介紹事件發生的物理時間 (physical time), 邏輯時間 (logical time).

事件不是一個瞬間的事情, 它有一個起始和結束的時刻, 由于這個特性, 事件之間會有部分重疊. 比如下圖中, A 和 B 兩個進程或者節點分別對一個隊列 enqueue 了 x 和 y, 然后再分別 dequeue. 你可以看到 enqueue 操作雖然是 A 先開始, B 后發生, 但是在時間上他們有重疊, 這就是并行, 二者之間的物理時間上順序可以說是不分先后的, 但是兩個 dequeue 的物理時間上一定是發生在兩個 enqueue 之前的.

物理時間雖然很重要, 但是在分布式系統中物理時間很難同步, 有時候我們更關心程序的邏輯順序. 從物理角度看當然事件 A 和 B 總是有先后順序或者同時發生, 但是在分布式系統中你非常難判斷兩個事件發生的先后順序, 無論是 NTP 還是原子鐘, 都存在誤差, 你永遠無法同步兩臺計算機的時間, 不考慮重力和加速度對時間的影響, 在同一個物理時刻 t 發生了一個事件 x, A 節點在他的時間參考系內可能會認為 x 發生在 t – 1ns, 而 B 節點可能認為在它自己的時間參照系里 x 發生在 t+1ns 的時刻. 這 2ns 就是 A 和 B 不同步造成誤差. 假設我們把模型縮小到單個計算機, 想象一下兩顆 CPU 在主板上的距離如果有 3CM, 假設信號可以通過接近光速傳遞, 那么兩顆處理器之間這 3CM 就要傳輸任何信息至少有 1ns 的延遲, 而兩個處理器分別會有自己的時間參考系, 二者之間必然有差別, 從更宏觀的角度來看, 在一個分布式系統中一個節點看到另外一個節點的計算結果, 就像我們通過天文望遠鏡看其他星系一樣, 那已經是幾億年之前的歷史了, 我們永遠無從得知現在那個星系是什么樣子, 甚至是否還存在. 所以依賴于物理時間我們是很難找到事件的順序的. 兩個事件的先后關系在分布式系統或者多路處理器系統中只能退化為先后順序的偏序關系 (partital order), 有時候只要能找出兩個事件的因果關系就行, 并不需要物理時鐘, 有時候甚至因果關系 (causal relation) 都不重要, 本系文章后面要介紹的 PRAM 和 Weak Consistency 就不需要因果關系.

Leslie Lamport 是分布式系統一致性研究的早期科學家, 圖靈獎獲得者, 他在 1978年 的論文中提出了一個分辨分布式系統中的事件因果關系的算法, 后來大家把它叫做 Lamport Timestamp 或者 Lamport Clock. Lamport Clock 是一種表達邏輯時間的邏輯時鐘 (logical clock), 它讓我們能夠把所有的歷史事件找到偏序關系, 而且不僅在各自節點的邏輯時間參考系內順序一致, 全局上的順序也是一致的. 有人會問, 我用一個全局的鎖服務來協同處理不就好了么, 干嘛搞一個這么復雜的東西, 其實不然, 全局協同服務有單點故障的問題, 另外全局鎖是通過互斥 (mutal exclusion) 讓整個系統串行化, 但是這樣子整個系統就失去了并發能力, 而且某個進程的失效可能會導致整個系統進入等待狀態. 那么有人問了, 如果允許并發不用互斥, 但是讓一個全局的 scheduler 作為法官來根據他自己對整個系統的觀察來決斷事件的歷史順序可以么? 答案是, 也不行. 舉個例子, 下圖中 P0 假設是全局的 scheduler, 他作為法官一樣來解讀系統中事件的順序. P1 如果發了一個事件消息 A 給 P0, 然后再發一個事件消息 B 給 P2, P2 接收到 B 之后再發一個事件消息 C 給 P0, 我們用 X->Y 來表示” X 早于或者同時于 Y” 的偏序關系,那么從 P0 的角度來看 A->C, 從 P1 看起來是 A->B, P2 看到的是 B->C, 由偏序關系的傳導性, 我們知道事件的全局順序應該就是 A->B->C, 沒有沖突矛盾, 很不錯對吧.

但是消息的傳遞在分布式系統中要經過網絡, 在多路處理器中要經過 cache coherence 協議, 如果 A 消息耗時比較久, 在 C 之后才到達 P0 呢?

這時候, 從 P0 的角度來看 C->A, 從 P1 的角度來看 A->B, 從 P2 的角度來看 B->C, 看出來沒, P1 和 P2 的觀點還好, 但是 P0 和 P2 的觀點就互相矛盾了. 如果 P0 和 P1 是正確的, 因為 C->A 并且 A->B, 根據傳導性, 那么應該有 C->A->B, 也即是 C->B, 而 P2 看來 B->C, 他們的觀點互相矛盾了, 結點彼此看到的全局順序的不一致了. 有些應用場景可以接受這種情況, 但是有些應用場景是不能接受這種情況的.

由于網絡是異步的, 系統之間的物理時鐘是不能精確同步的, 所以這里的 P0 作為全局的 scheduler 永遠無法知道基于物理時間的全局順序是怎樣的. 用一個 scheduler 就可以解決事件的全序集問題了么? 顯然, 不行.

擴展一下這個例子到在實際應用, 你把 P0 想象成為一個 NoSQL 數據庫的后端存儲節點, P1 和 P2 作為客戶端, 如果 P1 寫入一個數據 A 到 P0, 然后 P1 又發消息 B 通知 P2 做一個耗時的計算, 讓 P2 去把 A 消息經過一系列計算來驗證 A 是否被篡改或者損壞過. 如果 P2 的驗證計算結果表明 A 是正確的, 那么 P2 什么也不用做, 否則要去把 A 修復的結果作為 C 消息存儲到 P0, 那么由于網絡的延遲, 如果 P0 先收到了 C 消息, 后來才收到 A 消息, P0 按照時間順序操作那么就會把錯誤的 A 替換掉正確的 C. 聰明的讀者可能會想到 Riak 的 Vector Clock, 但是在那之前, 我們先來看看 Lamport Clock.

Lamport 在他的論文中舉了一個例子, 下面的圖中 P/Q/R 是三個進程 (這里的進程可以是多路處理器系統其中的一個處理器, 也可以是分布式系統中的一個節點), 從下往上代表物理時間的流逝, p1, p2, q1, q2, r1, r2 …. 表示事件, 嚴格講這些事件因為有起始和結束過程, 應該是沿著時間線的一段加粗線, 這里為了簡化, 縮小到了一個點. 波浪線表示事件的發送, 比如 p1->q2 表示 P 把 p1 事件發送給了 Q, Q 接受此消息作為 q2 事件. 假設 C 是 Lamport Clock, 并且是一個單調遞增的計數器函數, 那么 C 應該滿足任何兩個事件 a, b, 如果存在偏序關系 (a 先于或同時于 b 發生) a->b, 必然有 C (a) < C (b).

圖片來源: Time, Clocks, and the Ordering of Events in a Distributed System

為了滿足這個 Clock 我們需要兩個條件:

C1. 對于單個進程 Pi, 如果 a 發生早于 b, 那么 Ci (a) < Ci (b)C2. 對于跨進程的情況, 如果 Pi 發送 a 到 Pj 作為 b, 那么 Ci (a) < Ci (b)

要滿足第一個條件 C1, 很簡單, 只要 Pi 每次兩個連續事件發生中都要遞增 Ci 即可. 要滿足第二個條件, 稍微麻煩點, 就是要 Pi 把 a 附帶上自己的 Ci 傳遞給 Pj, 然后 Pj 要遞增到 max (Ci, Cj) + 1.

這樣剛才的圖就可以變成下面的圖:

圖片來源: Time, Clocks, and the Ordering of Events in a Distributed System

橫向虛線就變成了全局的 clock tick, 而每個進程的 clock 都是一致的. Lamport Clock 的作用就是找到 causally related 關系, 之后 1988年 出現的 Vector Clock 是一個更加實用的算法. 關于 Vector Clock, Riak 的工程師有兩篇非常好的文章大家可以去看看 Why Vector Clocks Are Easy 和 Why Vector Clocks Are Hard). 這里受制于篇幅此處不再詳細描述, 在后繼介紹 Casual Consistency 的時候會給大家詳細介紹. 對于 1978年 這篇論文有興趣的同學可以去檢索 Time, Clock, and Ordering of Events in a Distributed System. 這篇論文被認為是分布式系統的一致性問題的開山之作, 其中 max (Ci, Cj) + 1 這個單調遞增的 timestamp 后來影響了很多的設計, 比如 Vector Clock, 比如一些 Conflict-free Replicated Data Types, Paxos 和 Raft 等. 這篇論文也是 Leslie Lamport 被引用最多的文章, 按照 Lamport 自己的說法, 這篇論文影響了后人對于分布式系統的一致性問題的思考方式, 而后基于人們對一致性, 性能, 實現難度之間的平衡, 產生了很多不同的一致性模型.

3. 理想的一致性模式

對于一致性, 我們需要不同的模型, 不同的級別. 理想的情況下任何事件都準確無誤的” 瞬時” 對其他進程或者節點可見. 比如, 一個服務節點對某個狀態的寫入, 瞬時可以被另外一個服務器同步復制, 因為” 瞬時” 的要求, 即便是 Lamport Clock 本質上是個 Logical Clock, 而非 Physical Clock, 所以也達不到這個要求. 如果存在這樣的模型, 我們不需要通過 Logical Clock 去找事件之間的因果關系 (causality), 事件的結束時間就可以解決事件的全序關系了. 有人稱作這種模型叫做 strict consistency. 實際上, 這在現實世界上根本不存在這樣理想的模型, 兩個服務器無論是通過金屬電路還是光學載體連接, 都會有傳輸延遲, 這是物理決定的, 物理時間在分布式系統中永遠不可能同步, 因此我們對于一致性的時間要求必須降低, 比如 Linearizability (strong consistency) 或者 Sequential consistency. 實際中我們經常比較關心兩個有因果關系的事件的順序而對于可以并行無因果關系的事件我們不太關心他們的順序, 再考慮到并發能力和實現難度. 我們需要多種不同的一致性模型.

4. Sequential Consistency, 1979

Leslie Lamport 在 Lamport Clock 之后第二年1979年 提出了 Sequential Consistency, Leslie Lamport 的定義如下:

這看起來很晦澀, 我們用通俗但不嚴謹的語言來表述, 他蘊含了兩個部分, 第一是事件歷史在各個進程上看全局一致, 第二是單個進程的事件歷史在全局歷史上符合程序順序 (program order).

第一個要求比較容易理解, 給個例子: 假設有四個進程 P0, P1, P2, P3 分別讀取和寫入一個變量 x, 橫軸從左往右表示物理時間的流逝. 對于下圖中 A 的情況這就是大家比較容易理解的情況, 這就是 Sequential Consistency. B 圖中你可能覺得, 好像 P2 和 P3 讀出來的 x 變量順序和物理時間不一致了么, 但是對于 P2 和 P3 來說, 他們雖然對 x 的歷史的順序和真實物理時間不一致, 但是 P2 和 P3 至少” 錯的一致” 啊, 所以只要 P0, P1, P2, P3 全體都認為 x 是先被 P2 寫入的 2, 后被 P0 寫入的 1, 那么我們認為這種情況仍然是一致的. 這樣的一致性模型就是 Sequential Consistency.

如果像下面這樣, 那么 P3 和 P2 互相就不一致了, 這就不能滿足 sequential consistency 了.

如果對于 x 的兩次寫入都是發生在同一個進程, 比如 P0, 那么前面 B 的情況也不符合 Sequential Consistency 了. 為什么呢? 因為這樣此 P0 就不符合 program order 了. 我們來看 Lamport 的定義中第二個方面關于 program order 的解釋.

第二個方面對于沒有多線程開發經驗的工程師稍微難理解一些. 比如兩個進程 P1, P2 上發生的事件分別是 1,2, 3, 4 和 5, 6, 7, 8, 如下圖所示. 那么從全局來看我們必須要讓事件交錯成一個有序的集合. 從下圖右邊 global-1 的觀點來看這樣的交錯和 P1/P2 是符合 Sequential Consistency 的, 但是 global-2 就不是, 其中 1,4,3,2 的順序并不是 P1 的” program order”. 第一種情況中 P1 和 P2 的原始順序在交錯中仍然得到了保留, 這個過程叫做 arbitrary order-preserving interleaving.

不熟悉多線程編程的工程師可能會問, 為什么 P1 和 global-2 中對于 3 和 2 的順序有不同的觀點? 為什么 program order 還會變? 我這里稍微解釋一下 CPU 讀寫內存的工作原理, 熟悉 C++/Java 內存模型的程序員可以跳過這部分.

下面是典型的志強兩路處理器的樣子. 每個處理器的每個 core 有自己的 L1/L2 cache, 所有的 core 共享 L3 cache, 然后兩顆處理器之間通過環形 QPI 通道實現 cache coherence. 這樣, 整個 cache 系統就成為了所有處理器核心看內存的窗口, 或者說是唯一事實.

處理器的一個 cycle 很快, 1ns 都不到, 而內存訪問很慢, 需要幾百個 cycle 了, 就算是最快的 L1 的訪問也需要三個 cycle, 只有寄存器能跟得上 CPU cycle, 所以為了充分利用處理器, 在 core 和 L1 之間插入了接近寄存器速度的 Load Buffer 和 Store Buffer.

LB 和 SB 有多重方式可以提高處理器整體性能. 比如你對一個線程間的共享變量做密集的循環, 這個變量的 i++ 可能是發生在寄存器內或者 store buffer 內, 當循環結束的時候才寫入 L1 cache, 然后通過 QPI 讓另外的處理器看到變化, 在這個密集循環過程中另外一個處理是看不到這個變量的變化歷史的. 還有就是如果你對三個變量寫入, 那么三次內存訪問需要大概 900 個 cycle, 如果這三個變量地址連續, 那么很有可能他們碰巧在同一個 cache line 里, 那么處理器可能會把三個變量先寫入 store buffer, 稍后合并成一次寫操作回到 L1 cache, 這就只需要 300 個 cycle, 這種優化叫做 write combine. Store Buffer 提升了處理器利用率但是會導致一個 CPU 的內存寫入對另外一個 CPU 的讀取顯現出延遲或者不可見. Java 里面 volatile 就是放了一個 full memory fence 等待 write buffer flush 到緩存系統處理結束. (很多 Java 程序員認為 volatile 是讓 CPU 直接訪問主存來避免 visibility 問題, 這是錯誤的觀點).

從另外一個角度看, 讀取也有 stale 的問題. 因為解析地址和讀取內存也是非常慢, 總共要幾百個 cycle, 所以處理器會使用 speculative read, 說白了就是打亂指令順序提前發 fetch 到內存, 然后干別的事情去了, 這樣讀出來的內容放在 load buffer 里, 處理器稍后真用這個變量的時候再去 load buffer 讀取. 但是這樣你會讀到過期的數據. 要讀到最新的數據, 也需要一個 memory fence 讓之前 load buffer 內的數據被處理完.

所以, 處理器之間的可見性問題和亂序問題, 會讓每個處理器對歷史事件產生不同的觀點. write combine 和 speculative read 再加上其他的優化會讓處理器執行產生 reordering. (memory fence 會打破處理器的 pipeline 產生 stall, 目前的主流服務器處理器有 48 個 pipeline stages, 產生一次 stall 的代價非常高. 這就是為什么我們需要共享控制變量或者變量之間存在因果關系的時候我們才需要 memory fence, 這也是為什么我們需要將來會介紹的 Causal Consistency 和 Weak Consistency 模型.)

好了, 你現在明白了為什么 program order 會被 reorder, 現在回過來看看 Lamport 在他的論文中為了闡述 Sequential Consistency 而提出的這個有趣的小例子, 從一個更高層的角度, 程序員的角度來看第二個條件.

這看起來像是 Dekker 的 Mutual Exclusion 算法去掉 turn 變量的簡化版, a 和 b 初始為 0, 分別是兩個進程的控制變量來阻止對方進入 critical section, 如果系統滿足 sequential consistency, 那么 process 1 和 2 是不能同時進入 critical section 的. 這兩個進程可能都無法進入, 但是最多有一個進程可以進入. 但是如果系統不滿足 sequential consistency 的第二個條件, 那么有可能兩個進程同時進入這段 critical section. 你可能會問, 怎么可能? 如果你看明白了上面關于處理器訪問內存的原理, 你會知道有可能進程 1 寫入 a=1 被 write combine 延遲了, 或者判斷 b=0 的那個讀取被 speculative read 了, 那么兩個進程就會同時進入 critical section.

Leslie Lamport 為此提出了如何實現 sequential consistency 的內存訪問:

1) Each processor issues memory requests in the order specified by the program.

2) Memory requests to any individual memory module are serviced from a single FIFO queue.

第一點就是禁止 reordering, 第二點就是 FIFO 的內存控制器. 這樣的系統可想而知, 會比我們今天使用的系統慢幾百倍, 沒有任何一款主流處理器能夠達到 sequential consistency. 所以為了換取效率, 維護數據一致性變成了開發人員的責任, 系統只提供給你 memory fence, CAS, LL/SC 之類的基礎工具. 無論你是 C++ 還是 Java 開發人員都要非常小心的使用線程, 其實即便是非常有經驗的開發人員有時候也會在線程上犯錯, 近年來出現的 lock-free 和 wait-free 的數據結構比基于鎖的實現運行期更加動態, 更加難以正確實現, 出現了 bug 之后非常難解決. 所以我們必須深入理解一致性, 在設計的時候想清楚各種邊際條件來避免多線程的問題.

早期一致性問題都是在多路處理器級別研究的, 但是往更宏觀的分布式系統來看, 多個服務器節點的寫操作也經常會有本地 buffer, 也會產生類似 write combine 的副作用, 這些問題在不同規模上看都是類似的.

大家或許注意到了, Sequential Consistency 對于時間不敏感, 只要存在一致的全序關系即可, 所以又出現了對時間敏感, 一致性強于 Sequential Consistency 的 Linearizability.

5. Linearizability, 1987

Linearizability 模型的一致性高于 sequential consistency, 有時候也叫做 strong consistency 或者 atomic consistency, 可以說是我們能夠實現的最高的一致性模型. 它是 Herlihy and Wing 在 1987年 提出的. 通過前面的討論我們現在知道 sequential consistency 只關心所有進程或者節點的歷史事件存在唯一的偏序關系, 它不關心時間順序. 而 linearizability 相當于在 sequential consistency 的基礎上再去關心時間順序, 在不依賴物理時鐘的前提下, 區分非并發操作的先后. Linearizability 是一個很重要的概念, 如果你不了解它你就無法真正理解 Raft 算法等.

我們可以用一個高等數據結構比如隊列來描述 Linearizability 的定義 (來源于 Herlihy & Wing). 假設 Enq x A 表示 A 進程開始嘗試把 x 加入隊列尾部, OK A 表示操作結束, Deq A 表示 A 進程開始從隊列頭部取出一個元素, OK y A 表示取出了 y 并操作結束. 下面左邊是物理時間上的操事件順序, 那么我們如果再最后面加一個 OK A 那么, 你會發現所有的事件的起始 / 結束都是成對的.

Enq x A, OK A, Deq B, OK x B, Enq y A

如果 H 能夠通過追加 0 到 1 個事件成為 H’, 并且 H’ 中的事件是起始 / 結束成對的 (H’ 是 H 的完整歷史), 那么 H’ 可以線性化為全序關系 S, 使得

1). S 中所有的事件起始 / 結束是” 緊挨著” 的, 事件具有原子性不可拆開.2). 并且一個事件 e0 的結束早于 e1 的開始, 那么這個全序關系在 S 中仍然存在.

那么在不違背隊列的正確行為的前提下, S 就是 H 的一個 linearization. 下面的例子中, 最左邊是物理時間上發生的 H, 中間是補齊成對之后的 H’, 右邊是 H’ 的一個 linearization.

用通俗但是不嚴謹的話來說, Linearization 蘊含了兩個特性, 第一, S 中的事件起始 / 結束是” 緊挨著” 的表示粒度上必須是整個事件, 事件之間不能交錯, (就是假設一個調用的結束事件返回之前我們就認為事件已經完成了, 把并發的調用時間縮短來產生順序關系). 第二, H 中全序關系延續到 S 中, 說明 S 仍然存在原始事件的物理時間的順序. 如果你沒看明白這么拗口的定義, 沒關系, 看看下面這個圖你就很容易明白了.

并不是所有的情況都是 Linerizable 的, 比如我們的隊列行為是這樣的:

1. Enq x A
2. OK A
3. Enq y B
4. Deq A
5. OK B
6. OK y A

因為 OK A 早于 Enq y B, 那么接下來的事件歷史中 x 就應該比 y 早出來, 而這個例子中 y 先出來了, 這違背了隊列這種數據結構的定義, 除非程序寫錯了否則不應該有這樣的歷史. 如果我們嘗試滿足那兩個條件, 那么這個歷史有兩種排法:

Enq x A -> OK A -> Deq A -> OK y A -> Enq y B -> OK B

Enq x A -> OK A -> Enq y B -> OK B -> Deq A -> OK y A

但是這兩個排法都違背了隊列的 FIFO 行為, 這樣的事件順序不符合 Linearizable.

再給一個例子, 這個是可以的

1. Enq x A
2. Deq B
3. OK x B

首先補齊結尾的 OK A 變成 H’, 然后可以把 S 排成:

Enq x A -> OK A -> Deq B -> OK x B

你要是覺得這種定義很晦澀, 沒關系, 用通俗的語言來講, 就是 A 寫入了 x 結束后, 接下來 B 一定能讀出來, 這雖然不嚴謹, 但是確實是 Linearizability 的本質. 下圖中從左往右是物理時間, 長條是指我們觀察到的一個事件的開始和結束, 其中 P0 把 x 的值從 0 改寫為 1. 長條是一個事件的時間窗口. 這個過程中如果 P1 去讀取 x, 如果 P1 的讀和 P0 的寫在時間上有重疊, 二者是并發的, 那么 P1 讀出來的無論是 0 還是 1, 都算符合 linearizability, 你認為 P1 的讀事件發生在 P0 的寫事件之前或者之后,都可以. P2 和 P0 之間也是這樣. 但是如果 P2 的個讀也發生在 P1 上, 那么兩個讀的結果必須要么 0-0, 要么 0-1, 要么 1-1, 但是不能是 1-0. 最后的 P3 因為起始晚于 P0 的結束, 所以要符合 linerizability 就只能讀出 x=1 才行, 我們必須認為 P3 的讀事件發生在 P0 的寫事件之后.

當事件之間沒有重疊, 中間有個” 小間隔” 的時候, Linearizability 必須給出明確的先后順序. 而前面介紹的 sequential consistency 則不需要這樣的要求, 如果上面的例子中如果 P3 讀出來是 0, 那么也是符合 Sequential Consistency 的.

當多個事件之間有重疊, 他們實際是并行的, Linearizability 要求不管是不是并行的事件, 所有進程都必須給出一致的事件順序, 這樣所有進程都會對事件歷史有完全同樣的線性觀點, 這就像是一個消除并行的過程, 所叫我們稱之為做 Linearization. 一個歷史可以有多種 Linearziation, 比如前面的例子中 P0 和 P1 的事件是并行的, 可以互換順序, 所以這個歷史至少可以有兩種 linearization. 要所有進程都全局一致還需要其他的條件, 本系列文章后面要介紹的 Paxos 算法就是這樣一個例子.

下面是 Herlihy 和 Wing 的論文中給出的例子, 大家可以看看, 哪些是符合 Linearizability 的?

圖片來源: Linearizability : A Correctness Condition for Concurrent Objects

Linearizability 的兩個很好的特性 Locality 和 Non-blocking, 有興趣的同學可以自己去看看, 限于篇幅本文不再介紹了. 如果你的理解還有點不清晰, 下一篇文章中我們介紹 Paxos 算法的時候你應該能更好的理解它.

Linearizability 和 Sequential Consistency 你可以把它們想象成一個燒烤架, 上面有很多烤串, 你不可以把肉和洋蔥在一個烤叉上互換位置 (單個進程需要符合 program order), 但是你可以撥動所有烤叉上的肉和洋蔥, 讓他們從左往右排列出來一個先后順序. 不管是 Linearizability 還是 Sequential Consistency, 那么下面 A 和 C 誰在前面都可以, 因為 A 和 C 是并行的, 但是 C 和 B 在 Linearizabiltiy 中必須 C 在前 B 在后, 而 Sequential Consistency 中 B 和 C 的順序可以互換.

這么看 Linearizability 和 Sequential Consistency 是不是很像? 過去絕大多數人會認為 Linearizability 的定義只是比 Sequential consistency 多了一個物理時間先后的約束, 所以認為他們很像, 甚至認為它們基本是一個東西, 性能也應該差不多. 但是后來以色列科學家 Hagit Attiya 和 Jennifer Welch 在 1994年 發表的論文讓大家意識到他們其實是完全不同的概念, 性能差別很大. (Sequential Consistency versus Linearizabiltiy, ACM Transactions on Computer Systems, Vol 12, No 2, May 1994, Pages 91-122) 過去人們在探討這兩種一致性模型的時候沒有真正分析過他們的理論上的性能差別, Attiya 第一次給出了具體的分析.

假設我們的網絡延遲有一個上限 d (盡管現實中不可能, 這里純粹做理論分析用), 那么最慢和最快的請求波動在 u 以內. 論文證明了下圖中上半部分綠色四邊形是 Linearizability 的性能根據讀寫比例從 u/4 到 u/2, 下面黃色三角形是 Sequential Consistency 的性能, 最糟糕不會超過 d * 2. 從性能角度來看, 二者的差別還是巨大的.

至于 Linearizability 的實現, 可以說是所有一致性模型里最豐富的了, 我們會在本系列下一篇文章中介紹.

如果你耐心看到這里了, 至此, 我們已經開了一個好頭, 你一定是對分布式系統的一致性問題很感興趣, 在本系列下一篇文章中我們將會提到 Linearizability 和 Sequential Consistency 的一些應用. 將來我們還會繼續介紹 Casual Consistency, PRAM, Eventual Consistency 這些性能更好但是一致性更弱的模型, 所以, stay tuned!