不理解Zookeeper一致性原理，談何異地多活改造

在2017年餓了麼做異地多活建設之時，我的團隊承擔了Zookeeper的異地多活改造。在此期間，我聽到了關於Zookeeper一致性的兩種不同說法：

• 一種說法是Zookeeper是最終一致性，由於多副本，以及保證大多數成功的Zab協議，當一個客戶端進程寫入一個新值，另一個客戶端進程不能保證馬上就會讀到，但能保證最終會讀到這個值；

• 另一種說法是Zookeeper的Zab協議類似於Paxos協議，並且提供了強一致性。

每當聽到這兩種說法，我都想糾正一下——不對，Zookeeper是順序一致性（sequential consistency）。但解釋起來比較複雜，需要一篇長文來說明，於是就有了本文，下面就和大家一起討論下我的看法。

什麼是sequetial consistency

從Zookeeper的文檔中我們可以看到，裡面明確寫出它的一致性是sequential consistency。（詳細參見Zookeeper官方文檔[1]）

那麼，什麼是sequential consistency呢？

sequential consistency是Lamport在1979年首次提出的。（詳細參見他的這篇論文：How to make a multiprocessor computer that correctly executes multiprocess programs）

論文中定義，當滿足下面這個條件時就是sequential consistency：

“

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.

這段英文定義很晦澀（這是Lamport大神的一貫風格，嚴謹但晦澀，Paxos協議也是如此），我第一次看到時的感覺是：“這是什麼鬼？”為啥每個英文單詞我都認識，但就是不知道他在說什麼？第一次看到這句話和我有同感的小夥伴留個言吧~

後文我再把這段英文定義翻譯成中文，現在我們先看看這篇論文的標題和定義中出現的一個關鍵詞，來說明一下sequential consistency的應用範圍。

論文的標題和定義中包含“multiprocessor”這個詞，multiprocessor是多核處理器的意思。從這個關鍵字來看，sequential consistency是用來定義多核處理器和跑在多核處理器上的程序的一個特性。Lamport這篇論文的標題可以翻譯成：“如何讓具有多核處理器的計算機正確執行多進程程序”，也就是說如果一個多核處理器具有sequential consistency的特性，這個多核處理器就可以正確運行，後面我會解釋這個正確運行是什麼意思（也就是本文後面講到的sequential consistency的作用）。

從這個標題我們還可以看出，sequential consistency應該是個併發編程（concurrent programming）領域的概念

接下來我們嘗試翻譯一下上文那段晦澀的定義。做這段翻譯讓我找到了上學時做閱讀理解的感覺，我先不直接翻譯，因為就算我把它翻譯成中文，估計很多人還是會有“為啥每個中文字我都懂，還是不知道在說什麼”的感覺。

首先，我來解釋一下個別的詞。首先，“any execution”是什麼意思？你有多個程序（program）在多核處理器上運行，例如你有兩個程序，第一個程序叫P1，它的代碼如下：

P1_write(x);

P1_read(y);

第二個程序叫P2，代碼如下：

P2_write(u);

P2_read(v);

從理論上來講，兩個程序運行在兩個獨立處理器的核上，有多少種執行的可能？我列舉其中幾種來舉例說明。

第一種：

P1---write(x)--------read(y)--------

P2-----------write(u)-------read(v)-

第二種：

P1----------write(x)-read(y)--------

P2--write(u)----------------read(v)-

第三種：

P1---read(y)----------write(x)------

P2-----------write(u)---------read(v)-

我們有24種可能的執行順序，也就是這四個操作任意的排列組合，也就是4!=24。類似第一種和第二種這樣的可能性很好理解。為什麼會出現像第三種這樣的可能的執行呢？那是因為就算在同一個程序中，由於處理會有多級的緩存，以及處理器中coherence的存在，雖然你的程序中是先write後read，在內存中真正生效的順序，也有可能是先read後write。

其實還會出現類似下面這樣的執行，兩個操作在兩個處理器上同時執行。

P1--write(x)-read(y)--------

P2--write(u)--------read(v)-

如果加上同時運行的這種情況，那就有更多種可能性。我的算數不太好，這裡就不繼續算下去了，因為到底有多少個不重要，重要的是要知道有很多種可能性。那麼定義中的“any execution”，就是指任意一種可能的執行，在定義中也可以理解為所有的這些可能的執行。

接著我們再來解釋一個詞——“sequential order”。什麼叫sequential order？我們來翻一下英語詞典（感覺更像在做閱讀理解了）。

“

sequential：連續的；相繼的；有順序的

order：命令；順序；規則；[貿易] 定單

sequential order——有順序的順序，這又是什麼鬼？

其實sequential是有一個接一個的意思，在處理器的這種上下文中，sequential就是指操作（operartion）一個接一個地執行，也就是順序執行，並且沒有重疊。order是指經過一定的調整，讓某樣東西按照一定的規則變得有序。比如，在算法中的排序算法就是ordering，就是讓數組這個東西按照從大到小或從小到大的規則變得有序。

再說回上文的例子，如果把四個操作，按一個接一個的規則排列，這時就可以得到4！的排列組合個可能的排列（order），同樣的，有多少個不重要。

比如：

P1_write(x);P1_read(y);P2_write(u);P2_read(v);

P1_read(y);P1_write(x);P2_write(u);P2:read(v);

P2_write(u);P2_read(v);P1_read(y);P1:write(x);

我這裡只列舉其中三個，其他的大家可以自己排一下。

重點來了，其實sequential order就是讓這四個操作按照一個接一個的順序執行，並且沒有重疊。注意這個排列不是真實的執行，真實的執行是any execution，這裡說的是邏輯上的假設，也就是為什麼定義有一個as if。

做了這麼多的鋪墊，下面我們開始翻譯定義中的第一句話：

“

任意一種可能的執行效果，與所有的處理器上的某一種操作按照順序排列執行的效果是一樣的。

注意，some在這裡是指“某一種”的意思，不是一些，因為order是單數（真的是在做閱讀理解）。

這句話的意思就是說，一個處理器要滿足這個條件，就只能允許滿足這個條件的那些可能的執行存在，其他不滿足的可能的執行都不會出現。

從第一句話中我們可以看出，一種多核處理器要想滿足sequential consistency，那麼多個程序在多個核運行效果“等同”於在一個核上順序執行所有操作的效果是差不多的。如果這樣的話，其實多核的威力基本就消失了。所以無論是從Lamport寫這篇論文的1979年，還是現在，沒有任何一個現實的多核處理器實現了sequential consistency。

那麼，為什麼Lamport大神提出這樣一個不現實的概念呢？（要注意Lamport寫這篇論文時，並沒有把它引申到分佈式系統領域，就是針對多核處理器、併發編程領域提出的）我們稍後再論述。

這裡還要注意的一點是，在我的翻譯裡用了“效果”一詞，但實際上英文原文中用的是“result（結果）”一詞。那效果和結果有什麼區別嗎？我們解釋一下什麼叫執行結果。

不管是任何真實的執行，還是某種經過順序排序後的假設執行，程序會產生一定的結果，比如print出來的結果（result）。實際上定義中說的是結果一樣。如果定義中用“效果”的話，那這個定義就只是一個定性的定義，如果用“結果”的話，那這個定義就是一個定量的定義。定量的，也就是說可以通過數學證明的。從這點我們可以看出，大神就是不一樣，任何理論都是可以通過數學證明為正確的。本文後面還會提到證明的事情，我們這裡再賣個關子。

到這裡，關於定義的第一句，更準確的翻譯就是：

“

任意一種可能的執行的結果，與某一種所有的處理器上的操作按照順序排列執行的結果是一樣的。

這裡我們還要注意一點，結果一樣就意味著，如果有人真的要實現一種sequential consistency的多核處理器的話，因為要保證結果一樣，所以他是有一定的空間來優化，而不會完全是一個核順序執行的效果。但是估計這種優化也是非常有限的。

好了，終於把最難的第一句話解釋完了，大家可以鬆口氣，第二句就非常簡單了。我們還是先解釋第二句種出現的一個詞——“sequence”。剛剛解釋過的sequential order是順序排序（就是按一個接一個排序），其實這是一個動作，動作會產生結果，它的結果產生了一個操作（operation）的隊列。第二句中出現的sequence就是指這個操作（operation）的隊列。

好，那第二句的翻譯就是：

“

並且每個獨立的處理器的操作，都會按照程序指定的順序出現在操作隊列中。

也就是說如果程序裡是先write(x);後read(y);，那麼只有滿足這個順序的操作隊列是符合條件的。這樣，我們剛剛說的很多可能的執行就少了很多，這裡我也就不計算少了多少，還是那句話，數量不重要，反正是有，而且變少了。

那麼第二句話意味著什麼？意味著如果一個多核處理器實現了sequential consistency，那這種多核處理器基本上就告別自（緩）行（存）車了。這裡我還要繼續賣關子，連緩存這種最有效提高處理器性能的優化都沒了，大神為什麼要提出這個概念？

好了，到這裡我們可以把兩句翻譯合起來，完整看一下：

“

任意一種可能的執行的結果，與某一種所有的處理器上的操作按照順序排列執行的結果是一樣的，並且每個獨立的處理器的操作，都會按照程序指定的順序出現在操作隊列中。

從這個定義中，我們可以看出，此概念的核心就是sequential order，這也就是為什麼Lamport老爺子把這種一致性模型稱之為sequential consistency。可以說這個命名是非常貼切的，不知道這種貼切對於以英語為母語的人來說是不是更好理解一些，應該不會出現“順序的順序是什麼鬼”這種情況。如果你看完本文，也覺得sequential很貼切的話，那就說明我講清楚了。

接下來我們舉個具體的例子，再來說明一下：

execution A

P0 writex=1-------------------------------

P1 -------write x=2----------------------

P2 -----------------read x==1--read x==2

P3 -----------------read x==1--read x==2

sequetial order: P0_write x=1,P3_read x==1,P4_read x==1,P1_write x=2,P3_read x==2,P4_read x==2

execution B

P0 write=1-------------------------------

P1 -------write x=2----------------------

P2 -----------------read x==2--read x==1

P3 -----------------read x==2--read x==1

sequetial order: P1_write x=2,P3_read x==2,P4_read x==2,P0_write x=1,P3_read x==1,P4_read x==1

execution C

P0 write=1-------------------------------

P1 -------write x=2----------------------

P2 -----------------read x==1--read x==2

P3 -----------------read x==2--read x==1

sequetial order: 你找不出一個符合定義中2個條件的一種order。

所以說如果一個多核處理器只允許execution A和B出現，不允許C出現，那麼這個多核處理器就是sequetial consistency的。如果它允許C出現，那它就不是sequetial consistency。

到這裡，我們已經完整地解釋完什麼是sequetial consistency。但是，細心的朋友可能會問，如果你的program是多線程的程序怎麼辦？那我們再把定義中最後的一個細節解釋一下：program這個詞。

program是指可以直接運行在處理器上的指令序列。這個並不是program的嚴格定義，但是我要指出的是這個program是在操作系統都沒有的遠古時代就存在的概念，在上文的定義中prgram就是指那個時代的program。

這個program裡沒有進程、線程的概念，這些概念都是在有了操作系統之後才出現的。因為沒有操作系統，也沒有內存空間的概念。不像我們現在所說的程序（program），不同的程序有自己獨立的內存地址空間。我們這裡，內存（memory）對於不同的program來說是shared。另外，需要注意的是program可以用來說明各種程序，不管你是操作系統內核，還是應用程序，都適用。

sequential consistency

是分佈式領域的概念

剛剛我們說了，sequential consistency雖然是針對併發編程領域提出的，但實際上它是分佈式領域的概念，特別是分佈式存儲系統。在 Distributed system: Principles and Paradigms（作者Andrew S.Tanenbaum, Maarten Van Steen），作者稍微修改了一下Lamport的定義，讓這個定義更貼近分佈式領域中的概念，我們來看一下作者是怎麼改的：

“

The result of any execution is the same as if the (read and write) operations by all processes on the data store were executed in some sequential order and the operations of-each individual process appear in this sequence in the order specified by its program.

作者把processor換成了process，並且加了on the data store這個限定，在Lamport的定義裡沒有這個限定，其實默認指的是memory（內存）。process就是指進程，以Zookeeper為例，就是指訪問Zookeeper的應用進程。program也不是那麼底層概念，也是基於操作系統的應用程序了。

sequential consistency的作用

好了，下面該揭曉我上面賣的兩個關子了。在Lamport的論文中，給出了一個小例子，如下：

process 1

a := 1;

if b = 0 then critical section:

a := 0

else ... fi

process 2

b := 1;

if a = 0 then critical section:

b := 0

else ... fi

Lamport在論文中說，如果一種多核處理滿足sequential consistency的條件，那麼最多隻有一個程序能夠進入critical section

Lamport老爺子應該是認為這個證明太簡單了，不需要花費筆墨來證明它。sequential consistency這篇論文只有不到兩頁A4紙，是我見過的最短的論文。這是Lamport一貫的做事風格，他的Paxos論文中，有很多細節都是一筆帶過的，給讀者留下無盡的遐想（瞎想）。

假設現在我們已經證明這個是正確的（雖然我也沒去證明，論文給出了兩個參考文獻用於證明），那這個例子說明了什麼呢？

大家也許注意到了，這個例子沒有用到任何鎖，但它實現了critical section，critical section是一種多線程synchronization 機制。如果多核處理器是sequential consistency的，那麼你寫的併發程序“天然就是正確的”。

但是處理器的設計者為了追求性能，將保證程序正確的任務丟給程序開發者。只在硬件級別提供了一些fence、cas等指令，基於這些指令操作內核和語言基礎庫實現了各種synchronization機制，用來保證操作系統的正確性和應用程序的正確性。程序員必須小心謹慎地使用線程和這些synchronization機制，否則就會出各種意想不到的問題。如果你沒有debug一個多線程bug連續加班兩天，那說明你是大神。

這些指令都是具有更高一致性級別，也就是linearizability，（關於linearizability可以參見我的另外一篇文章《線性一致性（Linearizability）是併發控制的基礎》[2]），雖然一致性級別高，但只是個別指令的，處理器整體只是實現了比sequential consistency低很多的一致性級別。所以實現難度大大降低了。

雖然Lamport老爺子的sequential consistency概念在concurrent programming領域中還沒有實際意義，但卻給我們指出了程序員的天堂在哪裡。在程序員的天堂裡，沒有多（車）線（來）程（車）編（往）程，只要寫程序就行。你面試的時候不會再有人問你多線程編程，不會再問你各種鎖。

在分佈式領域中，sequential consistency更實際一些。Zookeeper就實現了sequential consistency。同理，這應該也是可以證明的，但目前還沒發現有Zookeeper社區有任何論文來證明這個。如果你已經明白上面解釋的定義，就可以想清楚Zookeeper是sequential consistency。歡迎大家一起來探討。

為何Zookeeper要實現

sequential consistency

實際上，Zookeeper的一致性更復雜一些，Zookeeper的讀操作是sequential consistency的，Zookeeper的寫操作是linearizability的。關於這個說法，Zookeeper的官方文檔中沒有寫出來，但在社區的郵件組有詳細的討論（郵件組的討論參見[3]）。

另外，在 Modular Composition of Coordination Services 這篇關於Zookeeper的論文中也有提到這個觀點（這篇論文不是Zookeeper的主流論文，但全面分析了Zookeeper的特性，以及Zookeeper跨機房方案，餓了麼的Zookeeper異地多活改造也參考了這篇論文中的一些觀點），我們可以這麼理解Zookeeper，從整體（read操作+write操作）上來說是sequential consistency，寫操作實現了linearizability。

通過簡單的推理，我們可以得出Lamport論文中的小例子，在Zookeeper中也是成立的。我們可以這樣實現分佈式鎖。但Zookeeper官方推薦的分佈式實現方法並沒有採用這個方式，而是利用了Zookeeper的linearizability特性實現了分佈式鎖（關於Zookeeper官方是如何實現分佈式鎖的，請參見我這篇文章《Zookeeper實現分佈式鎖和選主》[4]）。

為什麼Zookeeper要實現sequential consistency？Zookeeper最核心的功能是用來做coordination service，也就是用來做分佈式鎖服務，在分佈式的環境下，Zookeeper本身怎麼做到“天然正確”？沒有其他的synchronization機制保證Zookeeper是正確的，所以只要Zookeeper實現了sequential consistency，那它自身就可以保證正確性，從而對外提供鎖服務。

參考文章：

[1]http://zookeeper.apache.org/doc/r3.4.9/zookeeperProgrammers.html#ch_zkGuarantees

[2]https://blog.csdn.net/cadem/article/details/79932574

[3]http://comments.gmane.org/gmane.comp.java.hadoop.zookeeper.user/5221

[4]https://blog.csdn.net/cadem/article/details/56289825

閱讀更多 DBAplus社群 的文章

關鍵字: 客戶端 進程 程序員