2017 年在餓了么做異地多活建設(shè)之時(shí)，我的團(tuán)隊(duì)承擔(dān)了 Zookeeper 的異地多活改造。

[[230262]]

在此期間，我聽到了關(guān)于 Zookeeper 一致性的兩種不同說法：

Zookeeper 是最終一致性的，由于多副本，以及保證大多數(shù)成功的 Zab 協(xié)議，當(dāng)一個(gè)客戶端進(jìn)程寫入一個(gè)新值，另一個(gè)客戶端進(jìn)程不能保證馬上就會(huì)讀到，但能保證最終會(huì)讀到這個(gè)值。

Zookeeper 的 Zab 協(xié)議類似于 Paxos 協(xié)議，并且提供了強(qiáng)一致性。

每當(dāng)聽到這兩種說法，我都想糾正一下。Zookeeper 是順序一致性（Sequential Consistency）的，但解釋起來比較復(fù)雜，下面和大家一起討論下我的看法。

什么是 Sequetial Consistency

從 Zookeeper 的文檔中我們可以看到，里面明確寫出它的一致性是 Sequential Consistency。

那么，什么是 Sequential Consistency 呢？

Sequential Consistency 是 Lamport 在 1979 年***提出的。論文中定義，當(dāng)滿足下面這個(gè)條件時(shí)就是 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 大神的一貫風(fēng)格，嚴(yán)謹(jǐn)?shù)逎琍axos 協(xié)議也是如此。

我***次看到時(shí)的感覺是：“這是什么鬼？”為啥每個(gè)英文單詞我都認(rèn)識(shí)，但就是不知道他在說什么？

我們先看看這篇論文的標(biāo)題和定義中出現(xiàn)的一個(gè)關(guān)鍵詞，來說明一下 Sequential Consistency 的應(yīng)用范圍。

論文的標(biāo)題和定義中包含“multiprocessor”這個(gè)詞，multiprocessor 是多核處理器的意思。

從這個(gè)關(guān)鍵字來看，Sequential Consistency 是用來定義多核處理器和跑在多核處理器上的程序的一個(gè)特性。

Lamport 這篇論文的標(biāo)題可以翻譯成：“如何讓具有多核處理器的計(jì)算機(jī)正確執(zhí)行多進(jìn)程程序”。

也就是說如果一個(gè)多核處理器具有 Sequential Consistency 的特性，這個(gè)多核處理器就可以正確運(yùn)行，后面我會(huì)解釋這個(gè)正確運(yùn)行是什么意思（也就是本文后面講到的 Sequential Consistency 的作用）。

從這個(gè)標(biāo)題我們還可以看出，Sequential Consistency 應(yīng)該是個(gè)并發(fā)編程（Concurrent Programming）領(lǐng)域的概念。

但我們現(xiàn)在常常在分布式系統(tǒng)領(lǐng)域討論 Sequential Consistency，比如本文主要討論的 Zookeeper（Zookeeper 很明顯是一個(gè)分布式系統(tǒng)）的一致性。

實(shí)際上，多核處理器上運(yùn)行的多個(gè)程序，其實(shí)也是一種分布式系統(tǒng)（Lamport在他的這篇 Time，Clocks，and the Ordering of Events in a Distributed System 分布式系統(tǒng)的開山之作中也闡述了這個(gè)觀點(diǎn)）。

所以雖然 Sequential Consistency 最早在并發(fā)編程中提出，但是它可以應(yīng)用在分布式系統(tǒng)中，比如本文討論的 Zookeeper 這種分布式存儲(chǔ)系統(tǒng)。

另外一個(gè)比較重要的 Linearizability（線性一致性），也是在并發(fā)編程中最早提出的，目前也被廣泛應(yīng)用在分布式系統(tǒng)領(lǐng)域中。

接下來我們嘗試翻譯一下上文那段晦澀的定義，做這段翻譯讓我找到了上學(xué)時(shí)做閱讀理解的感覺。

我先不直接翻譯，因?yàn)榫退阄野阉g成中文，估計(jì)很多人還是會(huì)有“為啥每個(gè)中文字我都懂，還是不知道在說什么”的感覺。

首先，我來解釋一下個(gè)別的詞。首先，“any execution”是什么意思？你有多個(gè)程序（Program）在多核處理器上運(yùn)行，例如你有兩個(gè)程序。

***個(gè)程序叫 P1，它的代碼如下： 

P1_write(x); 
P1_read(y); 

第二個(gè)程序叫 P2，代碼如下：

P2_write(u); 
P2_read(v); 

從理論上來講，兩個(gè)程序運(yùn)行在兩個(gè)獨(dú)立處理器的核上，有多少種執(zhí)行的可能？我列舉其中幾種來舉例說明。

***種：

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 種可能的執(zhí)行順序，也就是這四個(gè)操作任意的排列組合，也就是4!=24。

類似***種和第二種這樣的可能性很好理解。為什么會(huì)出現(xiàn)像第三種這樣的可能的執(zhí)行呢？

那是因?yàn)榫退阍谕粋€(gè)程序中，由于處理會(huì)有多級(jí)的緩存，以及處理器中 coherence 的存在，雖然你的程序中是先 write 后 read，在內(nèi)存中真正生效的順序，也有可能是先 read 后 write。

其實(shí)還會(huì)出現(xiàn)類似下面這樣的執(zhí)行，兩個(gè)操作在兩個(gè)處理器上同時(shí)執(zhí)行。

P1--write(x)-read(y)-------- 
P2--write(u)--------read(v)- 

如果加上同時(shí)運(yùn)行的這種情況，那就有更多種可能性。我的算術(shù)不太好，這里就不繼續(xù)算下去了，因?yàn)榈降子卸嗌賯€(gè)不重要，重要的是要知道有很多種可能性。

那么定義中的“any execution”，就是指任意一種可能的執(zhí)行，在定義中也可以理解為所有的這些可能的執(zhí)行。

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

sequential：連續(xù)的；相繼的；有順序的

order：命令；順序；規(guī)則；[貿(mào)易] 定單

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

其實(shí) sequential 是有一個(gè)接一個(gè)的意思，在處理器的這種上下文中，sequential 就是指操作（operartion）一個(gè)接一個(gè)地執(zhí)行，也就是順序執(zhí)行，并且沒有重疊。

order 是指經(jīng)過一定的調(diào)整，讓某樣?xùn)|西按照一定的規(guī)則變得有序。比如，在算法中的排序算法就是 ordering，就是讓數(shù)組這個(gè)東西按照從大到小或從小到大的規(guī)則變得有序。

那么 sequential order 就是指讓操作（operation）按照一個(gè)接一個(gè)這樣的規(guī)則排列，并且沒有重疊。

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

比如：

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); 

我這里只列舉其中三個(gè)，其他的大家可以自己排一下。

重點(diǎn)來了，其實(shí) sequential order 就是讓這四個(gè)操作按照一個(gè)接一個(gè)的順序執(zhí)行，并且沒有重疊。

注意這個(gè)排列不是真實(shí)的執(zhí)行，真實(shí)的執(zhí)行是 any execution，這里說的是邏輯上的假設(shè)，也就是為什么定義有一個(gè) as if。

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

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

注意，some 在這里是指“某一種”的意思，不是一些，因?yàn)?order 是單數(shù)（真的是在做閱讀理解）。

這句話的意思就是說，一個(gè)處理器要滿足這個(gè)條件，就只能允許滿足這個(gè)條件的那些可能的執(zhí)行存在，其他不滿足的可能的執(zhí)行都不會(huì)出現(xiàn)。

從***句話中我們可以看出，一種多核處理器要想滿足 Sequential Consistency，那么多個(gè)程序在多個(gè)核運(yùn)行效果“等同”于在一個(gè)核上順序執(zhí)行所有操作的效果是差不多的。

如果這樣的話，其實(shí)多核的威力基本就消失了。所以無論是從 Lamport 寫這篇論文的 1979 年，還是現(xiàn)在，沒有任何一個(gè)現(xiàn)實(shí)的多核處理器實(shí)現(xiàn)了 Sequential Consistency。

那么，為什么 Lamport 大神提出這樣一個(gè)不現(xiàn)實(shí)的概念呢？（要注意 Lamport 寫這篇論文時(shí)，并沒有把它引申到分布式系統(tǒng)領(lǐng)域，就是針對多核處理器、并發(fā)編程領(lǐng)域提出的）我們稍后再論述。

這里還要注意的一點(diǎn)是，在我的翻譯里用了“效果”一詞，但實(shí)際上英文原文中用的是“result（結(jié)果）”一詞。那效果和結(jié)果有什么區(qū)別嗎？我們解釋一下什么叫執(zhí)行結(jié)果。

不管是任何真實(shí)的執(zhí)行，還是某種經(jīng)過順序排序后的假設(shè)執(zhí)行，程序會(huì)產(chǎn)生一定的結(jié)果，比如 print 出來的結(jié)果（result）。實(shí)際上定義中說的是結(jié)果一樣。

如果定義中用“效果”的話，那這個(gè)定義就只是一個(gè)定性的定義，如果用“結(jié)果”的話，那這個(gè)定義就是一個(gè)定量的定義。定量的，也就是說可以通過數(shù)學(xué)證明的。

從這點(diǎn)我們可以看出，大神就是不一樣，任何理論都是可以通過數(shù)學(xué)證明為正確的。本文后面還會(huì)提到證明的事情，我們這里再賣個(gè)關(guān)子。

到這里，關(guān)于定義的***句，更準(zhǔn)確的翻譯就是： 

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

這里我們還要注意一點(diǎn)，結(jié)果一樣就意味著，如果有人真的要實(shí)現(xiàn)一種 Sequential Consistency 的多核處理器的話，因?yàn)橐ＷC結(jié)果一樣，所以他是有一定的空間來優(yōu)化，而不會(huì)完全是一個(gè)按順序執(zhí)行的效果。

但是估計(jì)這種優(yōu)化也是非常有限的。好了，終于把最難的***句話解釋完了，大家可以松口氣，第二句就非常簡單了。

我們還是先解釋第二句中出現(xiàn)的一個(gè)詞——“sequence”。剛剛解釋過的 sequential order 是順序排序（就是按一個(gè)接一個(gè)排序）。

其實(shí)這是一個(gè)動(dòng)作，動(dòng)作會(huì)產(chǎn)生結(jié)果，它的結(jié)果產(chǎn)生了一個(gè)操作（operation）的隊(duì)列。第二句中出現(xiàn)的 sequence 就是指這個(gè)操作（operation）的隊(duì)列。

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

并且每個(gè)獨(dú)立的處理器的操作，都會(huì)按照程序指定的順序出現(xiàn)在操作隊(duì)列中。

也就是說如果程序里是先write(x)；后read(y)；，那么只有滿足這個(gè)順序的操作隊(duì)列是符合條件的。

這樣，我們剛剛說的很多可能的執(zhí)行就少了很多，這里我也就不計(jì)算少了多少，還是那句話，數(shù)量不重要，反正是有，而且變少了。

那么第二句話意味著什么？意味著如果一個(gè)多核處理器實(shí)現(xiàn)了 Sequential Consistency，那這種多核處理器基本上就告別自（緩）行（存）車了。

這里我還要繼續(xù)賣關(guān)子，連緩存這種最有效提高處理器性能的優(yōu)化都沒了，大神為什么要提出這個(gè)概念？

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

任意一種可能的執(zhí)行的結(jié)果，與某一種所有的處理器上的操作按照順序排列執(zhí)行的結(jié)果是一樣的，并且每個(gè)獨(dú)立的處理器的操作，都會(huì)按照程序指定的順序出現(xiàn)在操作隊(duì)列中。  

從這個(gè)定義中，我們可以看出，此概念的核心就是 sequential order，這也就是為什么 Lamport 老爺子把這種一致性模型稱之為 Sequential Consistency。

可以說這個(gè)命名是非常貼切的，不知道這種貼切對于以英語為母語的人來說是不是更好理解一些，應(yīng)該不會(huì)出現(xiàn)“順序的順序是什么鬼”這種情況。如果你看完本文，也覺得 sequential 很貼切的話，那就說明我講清楚了。

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

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: 你找不出一個(gè)符合定義中2個(gè)條件的一種order。 

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

所以說如果一個(gè)多核處理器只允許 execution A 和 B 出現(xiàn)，不允許 C 出現(xiàn)，那么這個(gè)多核處理器就是 Sequetial Consistency 的；如果它允許 C 出現(xiàn)，那它就不是 Sequetial Consistency。

到這里，我們已經(jīng)完整地解釋完什么是 Sequetial Consistency。但是，細(xì)心的朋友可能會(huì)問，如果你的 program 是多線程的程序怎么辦？那我們再把定義中***的一個(gè)細(xì)節(jié)解釋一下：program 這個(gè)詞。

program 是指可以直接運(yùn)行在處理器上的指令序列。這個(gè)并不是 program 的嚴(yán)格定義，但是我要指出的是這個(gè) program 是在操作系統(tǒng)都沒有的遠(yuǎn)古時(shí)代就存在的概念，在上文的定義中 prgram 就是指那個(gè)時(shí)代的 program。

這個(gè) program 里沒有進(jìn)程、線程的概念，這些概念都是在有了操作系統(tǒng)之后才出現(xiàn)的。因?yàn)闆]有操作系統(tǒng)，也沒有內(nèi)存空間的概念。

不像我們現(xiàn)在所說的程序（program），不同的程序有自己獨(dú)立的內(nèi)存地址空間。我們這里，內(nèi)存（memory）對于不同的 program 來說是 shared。

另外，需要注意的是 program 可以用來說明各種程序，不管你是操作系統(tǒng)內(nèi)核，還是應(yīng)用程序，都適用。

Sequential Consistency 是分布式領(lǐng)域的概念

剛剛我們說了，Sequential Consistency 雖然是針對并發(fā)編程領(lǐng)域提出的，但實(shí)際上它是分布式領(lǐng)域的概念，特別是分布式存儲(chǔ)系統(tǒng)。

在 Distributed system：Principles and Paradigms （作者Andrew S.Tanenbaum, Maarten Van Steen），作者稍微修改了一下 Lamport 的定義，讓這個(gè)定義更貼近分布式領(lǐng)域中的概念。

我們來看一下作者是怎么改的： 

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 這個(gè)限定，在 Lamport 的定義里沒有這個(gè)限定，其實(shí)默認(rèn)指的是 memory（內(nèi)存）。

process 就是指進(jìn)程，以 Zookeeper 為例，就是指訪問 Zookeeper 的應(yīng)用進(jìn)程。program 也不是那么底層的概念，也是基于操作系統(tǒng)的應(yīng)用程序了。

Sequential Consistency 的作用

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

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 的條件，那么最多只有一個(gè)程序能夠進(jìn)入 critical section。

在論文中，Lamport 老爺子并沒有解釋為什么最多只有一個(gè)程序能夠進(jìn)入 critical section。

而是把這個(gè)證明留給了論文的讀者，就像我們常見的教科書中的課后習(xí)題一樣。

Lamport 老爺子應(yīng)該是認(rèn)為這個(gè)證明太簡單了，不需要花費(fèi)筆墨來證明它。Sequential Consistency 這篇論文只有不到兩頁 A4 紙，是我見過的最短的論文。

這是 Lamport 一貫的做事風(fēng)格，他的 Paxos 論文中，有很多細(xì)節(jié)都是一筆帶過的，給讀者留下無盡的遐想（瞎想）。

假設(shè)現(xiàn)在我們已經(jīng)證明這個(gè)是正確的（雖然我也沒去證明，論文給出了兩個(gè)參考文獻(xiàn)用于證明），那這個(gè)例子說明了什么呢？

大家也許注意到了，這個(gè)例子沒有用到任何鎖，但它實(shí)現(xiàn)了 critical section，critical section 是一種多線程 synchronization 機(jī)制。

如果多核處理器是 Sequential Consistency 的，那么你寫的并發(fā)程序“天然就是正確的”。

但是處理器的設(shè)計(jì)者為了追求性能，將保證程序正確的任務(wù)丟給程序開發(fā)者。

只在硬件級(jí)別提供了一些 fence、cas 等指令，基于這些指令操作內(nèi)核和語言基礎(chǔ)庫實(shí)現(xiàn)了各種 synchronization 機(jī)制，用來保證操作系統(tǒng)的正確性和應(yīng)用程序的正確性。

程序員必須小心謹(jǐn)慎地使用線程和這些 synchronization 機(jī)制，否則就會(huì)出各種意想不到的問題。如果你沒有 debug 一個(gè)多線程 Bug 連續(xù)加班兩天，那說明你是大神。

這些指令都是具有更高一致性級(jí)別，也就是 linearizability，雖然一致性級(jí)別高，但只是個(gè)別指令的，處理器整體只是實(shí)現(xiàn)了比 Sequential Consistency 低很多的一致性級(jí)別。所以實(shí)現(xiàn)難度大大降低了。

雖然 Lamport 老爺子的 Sequential Consistency 概念在 Concurrent Programming 領(lǐng)域中還沒有實(shí)際意義，但卻給我們指出了程序員的天堂在哪里。

在程序員的天堂里，沒有多（車）線（來）程（車）編（往）程，只要寫程序就行。你面試的時(shí)候不會(huì)再有人問你多線程編程，不會(huì)再問你各種鎖。

在分布式領(lǐng)域中，Sequential Consistency 更實(shí)際一些。Zookeeper 就實(shí)現(xiàn)了 Sequential Consistency。

同理，這應(yīng)該也是可以證明的，但目前還沒發(fā)現(xiàn)有 Zookeeper 社區(qū)有任何論文來證明這個(gè)。

如果你已經(jīng)明白上面解釋的定義，就可以想清楚 Zookeeper 是 Sequential Consistency，歡迎大家一起來探討。

為何 Zookeeper 要實(shí)現(xiàn) Sequential Consistency

實(shí)際上，Zookeeper 的一致性更復(fù)雜一些，Zookeeper 的讀操作是 Sequential Consistency 的，Zookeeper 的寫操作是 linearizability 的。

關(guān)于這個(gè)說法，Zookeeper 的官方文檔中沒有寫出來，但在社區(qū)的郵件組有詳細(xì)的討論。

另外，在 Modular Composition of Coordination Services 這篇關(guān)于 Zookeeper 的論文中也有提到這個(gè)觀點(diǎn)（這篇論文不是 Zookeeper 的主流論文，但全面分析了 Zookeeper 的特性，以及 Zookeeper 跨機(jī)房方案，餓了么的 Zookeeper 異地多活改造也參考了這篇論文中的一些觀點(diǎn)）。

我們可以這么理解 Zookeeper，從整體（read 操作+write 操作）上來說是 Sequential Consistency，寫操作實(shí)現(xiàn)了 linearizability。

通過簡單的推理，我們可以得出 Lamport 論文中的小例子，在 Zookeeper 中也是成立的。我們可以這樣實(shí)現(xiàn)分布式鎖。

但 Zookeeper 官方推薦的分布式實(shí)現(xiàn)方法并沒有采用這個(gè)方式，而是利用了 Zookeeper 的 linearizability 特性實(shí)現(xiàn)了分布式鎖。

為什么 Zookeeper 要實(shí)現(xiàn) Sequential Consistency？Zookeeper 最核心的功能是用來做 coordination service，也就是用來做分布式鎖服務(wù)，在分布式的環(huán)境下，Zookeeper 本身怎么做到“天然正確”？

沒有其他的 synchronization 機(jī)制保證 Zookeeper 是正確的，所以只要 Zookeeper 實(shí)現(xiàn)了 Sequential Consistency，那它自身就可以保證正確性，從而對外提供鎖服務(wù)。 

作者：陳東明

簡介：餓了么北京技術(shù)中心架構(gòu)組負(fù)責(zé)人，負(fù)責(zé)餓了么的產(chǎn)品線架構(gòu)設(shè)計(jì)及基礎(chǔ)架構(gòu)研發(fā)工作。曾任百度架構(gòu)師，負(fù)責(zé)百度即時(shí)通訊產(chǎn)品的架構(gòu)設(shè)計(jì)。具有豐富的大規(guī)模系統(tǒng)構(gòu)建和基礎(chǔ)架構(gòu)的研發(fā)經(jīng)驗(yàn)，善于復(fù)雜業(yè)務(wù)需求下的大并發(fā)、分布式系統(tǒng)設(shè)計(jì)和持續(xù)優(yōu)化。