[[413697]]

最近看到的一篇超棒的關(guān)于分布式系統(tǒng)中強(qiáng)一致性模型的blog，實(shí)在沒(méi)有不分享的道理。最近比較閑，所以干脆把它翻譯了，一是為了精讀，二是為了更友好地分享。其中會(huì)插入一些亂七八糟的個(gè)人補(bǔ)充，評(píng)論區(qū)的精彩討論也會(huì)有選擇性的翻譯。原文在這： https://aphyr.com/posts/313-st ... odels

網(wǎng)絡(luò)分區(qū)是大概率會(huì) 發(fā)生 的。交換機(jī)，網(wǎng)絡(luò)接口控制器（NIC，Network Interface Controller），主機(jī)硬件，操作系統(tǒng)，硬盤(pán)，虛擬機(jī)，語(yǔ)言運(yùn)行時(shí)，更不用說(shuō)程序語(yǔ)義本身，所有的這些將導(dǎo)致我們的消息可能會(huì)延遲，被丟棄，重復(fù)或被重新排序。在一個(gè)充滿不確定的世界里，我們希望程序保持一種 直觀的正確性 。

是的，我們想要直觀的正確性。那就做正確的事吧！但什么是正確的事？我們?nèi)绾蚊枋鏊吭谶@篇文章里，我們會(huì)見(jiàn)到一些“強(qiáng)”一致性模型，并且看到他們是如何互相適應(yīng)的。

正確性（Correctness）

其實(shí)有很多種描述一個(gè)算法抽象行為的方式——但為了統(tǒng)一，我們說(shuō)一個(gè)系統(tǒng)是由 狀態(tài) 和一些 導(dǎo)致?tīng)顟B(tài)轉(zhuǎn)移的操作 組成的。在系統(tǒng)運(yùn)行期間，它將隨著操作的演進(jìn)從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)。

uniprocessor history

舉個(gè)例子，我們的狀態(tài)可以是個(gè)變量， 操作 可以是對(duì)這個(gè)變量的讀和寫(xiě)。在這個(gè)簡(jiǎn)單的Ruby程序里，我們會(huì)對(duì)一個(gè)變量進(jìn)行幾次讀寫(xiě)，以輸出的方式表示寫(xiě)。

x = "a"; puts x; puts x 
 
x = "b"; puts x 
 
x = "c" 
 
x = "d"; puts x 

我們對(duì)程序的正確性已經(jīng)有了一個(gè)直觀的概念：以上這段程序應(yīng)該輸出 “aabd” 。為什么呢？因?yàn)樗鼈兪怯行虬l(fā)生的。首先我們 寫(xiě)入值a ，然后 讀到值a ，接著 讀到值a ， 寫(xiě)入值b ，如此進(jìn)行。

一旦我們把變量寫(xiě)為某個(gè)值，比如 a ，那么讀操作就應(yīng)該返回 a ，直到我們?cè)俅胃淖冏兞?。讀到的值應(yīng)該總是返回最近寫(xiě)入的值。我們把這種系統(tǒng)稱為——單值變量——單一 寄存器 （并不單指硬件層次的寄存器，而是 act like a register ）。

從編程的第一天開(kāi)始，我們就把這種模型奉為圭臬，像習(xí)慣一樣自然——但這并不是變量運(yùn)作的唯一方式。一個(gè)變量可能被讀到任何值： a ， d ，甚至是 the moon 。這樣的話，我們說(shuō)系統(tǒng)是 不正確 的，因?yàn)檫@些操作沒(méi)有與我們模型期望的運(yùn)作方式對(duì)應(yīng)上。

這引出了對(duì)系統(tǒng) 正確性 的定義：給定一些涉及操作與狀態(tài)的 規(guī)則 ，隨著操作的演進(jìn)，系統(tǒng)將一直 遵循這些規(guī)則 。我們把這樣的規(guī)則稱為 一致性模型 。

我們把對(duì)寄存器的規(guī)則用簡(jiǎn)單的英語(yǔ)來(lái)陳述，但它們也可以是任意復(fù)雜的數(shù)學(xué)結(jié)構(gòu)。“讀取兩次寫(xiě)入之前的值，對(duì)值加三，如果結(jié)果為4，讀操作可能返回cat或dog”，這也可以是一種一致性模型（作者只是為了表名一致性模型的闡述原則，后同）。也可以是“每次讀操作都會(huì)返回0”。我們甚至可以說(shuō)“根本沒(méi)有什么規(guī)則，所有操作都是允許的”。這就是 最簡(jiǎn)單 的一致性模型，任何系統(tǒng)都能輕易滿足。

更加正式地說(shuō)，一致性模型是 所有被允許的操作記錄 的集合。當(dāng)我們運(yùn)行一個(gè)程序，經(jīng)過(guò)一系列集合中允許的操作，特定的執(zhí)行結(jié)果總是 一致 的。如果程序意外地執(zhí)行了 非 集合中的操作，我們就稱執(zhí)行記錄是 非一致 的。如果 任意 可能的執(zhí)行操作都在這個(gè)被允許的操作集合內(nèi)，那么系統(tǒng)就 滿足 一致性模型。我們希望實(shí)際的系統(tǒng)是滿足這樣“直觀正確”的一致性模型的，這樣我們才能寫(xiě)出可預(yù)測(cè)的程序。

并發(fā)記錄（Concurrent histories）

假設(shè)有一個(gè)用Node.js或Erlang寫(xiě)的并發(fā)程序?，F(xiàn)有多個(gè)邏輯線程，我們稱之為“多進(jìn)程”。如果我們用2個(gè)進(jìn)程運(yùn)行這個(gè)并發(fā)程序，每個(gè)進(jìn)程都對(duì)同一個(gè)寄存器進(jìn)行訪問(wèn)（讀和寫(xiě)），那么我們之前認(rèn)為的寄存器系統(tǒng)的不變性（指順序不變性）就會(huì)被 改寫(xiě) 。

multiprocessor history

兩個(gè)工作進(jìn)程分別稱為“top”和“bottom”。Top進(jìn)程嘗試執(zhí)行 寫(xiě)a ， 讀 ， 讀 。Bottom進(jìn)程同時(shí)嘗試執(zhí)行 讀 ， 寫(xiě)b ， 讀 。因?yàn)槌绦蚴遣l(fā)的，所以兩個(gè)進(jìn)程之間互相交錯(cuò)的操作將導(dǎo)致 多個(gè)執(zhí)行順序 ——而在單核場(chǎng)景下，執(zhí)行順序總是程序里指定的那一個(gè)邏輯順序。圖例中，top寫(xiě)入 a ，bottom讀 a ，top讀 a ，bottom寫(xiě) b ，top讀 b ，bottom讀 b 。

但是并發(fā)會(huì)讓一切表現(xiàn)的不同。我們可以 默認(rèn) 地認(rèn)為每個(gè) 并發(fā) 的程序——一旦執(zhí)行，操作能以任意順序發(fā)生。一個(gè) 線程 ，或者說(shuō)是一個(gè) 邏輯進(jìn)程 ，在執(zhí)行記錄層面的做了一個(gè) 約束 ：屬于同一個(gè)線程的操作 一定 會(huì)按順序發(fā)生。邏輯線程對(duì)允許操作集合中的操作強(qiáng)加了部分順序保證。（一個(gè)邏輯線程即一個(gè)執(zhí)行實(shí)體，即使編譯器重排了指令，單個(gè)線程中的同步workflow順序是不會(huì)顛倒的。但是不同線程之間的事件順序無(wú)法保證。）

即使有了以上的保證，從獨(dú)立進(jìn)程的角度來(lái)看，我們的寄存器不變性也被破壞了。Top寫(xiě)入 a ，讀到 a ，接著讀到 b ——這 不再 是它寫(xiě)入的值。 我們必須使一致性模型更 寬松 來(lái)有效描述并發(fā)?，F(xiàn)在，進(jìn)程可以從其他任意進(jìn)程讀到最近寫(xiě)入的值。寄存器變成了兩個(gè)進(jìn)程之間的 協(xié)調(diào)地 ：它們共享了狀態(tài)。

光錐（Light cones）

> 讀寫(xiě)不再是一個(gè)瞬時(shí)的過(guò)程，而是一個(gè)類似光傳播->反射面->反向傳播的過(guò)程。

light cone history

現(xiàn)實(shí)往往沒(méi)有那么理想化：在幾乎每個(gè)實(shí)際的系統(tǒng)中，進(jìn)程之間都有一定的 距離 。一個(gè)沒(méi)有被緩存的值（指沒(méi)有被CPU的local cache緩存），通常在距離CPU 30厘米 的DIMM內(nèi)存條上。光需要整整一個(gè)納秒來(lái)傳播這么長(zhǎng)的距離，實(shí)際的內(nèi)存訪問(wèn)會(huì)比光速慢得多。位于不同數(shù)據(jù)中心某臺(tái)計(jì)算機(jī)上的值可以相距幾千公里——意味著需要幾百毫秒的傳播時(shí)間。我們沒(méi)有更快傳播數(shù)據(jù)的方法，否則就違反了物理定律。（物理定律都違反了，就更別談什么現(xiàn)代計(jì)算機(jī)體系了。）

這意味著我們的操作 不再是瞬時(shí)的 。某些操作也許快到可以被近乎認(rèn)為是瞬時(shí)的，但是通常來(lái)說(shuō)，操作是 耗時(shí) 的。我們 調(diào)用 對(duì)一個(gè)變量的寫(xiě)操作；寫(xiě)操作傳播到內(nèi)存，或其他計(jì)算機(jī)，或月球；內(nèi)存改變狀態(tài)；一個(gè)確認(rèn)信息回傳；這樣我們才 知道 這個(gè)操作真實(shí)的發(fā)生了。

concurrent read

不同地點(diǎn)之間傳送消息的延遲會(huì)在操作記錄中造成 歧義 。消息傳播的快慢會(huì)導(dǎo)致預(yù)期外的事件順序發(fā)生。上圖中，bottom發(fā)起一個(gè)讀請(qǐng)求的時(shí)候，值為 a ，但在讀請(qǐng)求的傳播過(guò)程中，top將值寫(xiě)為 b ——寫(xiě)操作偶然地比讀請(qǐng)求 先 到達(dá)寄存器。 Bottom最終讀到了 b 而不是 a 。

這一記錄破壞了我們的寄存器并發(fā)一致性模型。Bottom并沒(méi)有讀到它在發(fā)起讀請(qǐng)求時(shí)的值。有人會(huì)考慮使用 完成時(shí)間 而不是 調(diào)用時(shí)間 作為操作的 真實(shí)時(shí)間 ，但反過(guò)來(lái)想想，這同樣行不通：當(dāng)讀請(qǐng)求比寫(xiě)操作先到達(dá)時(shí)，進(jìn)程會(huì)在當(dāng)前值為 b 時(shí)讀到 a 。

在分布式系統(tǒng)中，操作的耗時(shí)被放大了，我們必須使一致性模型 更寬松 ：允許這些有歧義的順序發(fā)生。

我們?cè)撊绾未_定寬松的程度？我們必須允許 所有 可能的順序嗎？或許我們還是應(yīng)該強(qiáng)加一些合理性約束？

線性一致性（Linearizability）

finite concurrency bounds

通過(guò)仔細(xì)的檢查，我們發(fā)現(xiàn)事件的順序是有邊界的。在時(shí)間維度上，消息不能被逆向發(fā)送，因此 最先到達(dá) 的消息會(huì)即刻接觸到數(shù)據(jù)源。一個(gè)操作不能在它 被調(diào)用之前 生效。

同樣的，通知完成的消息也不能回傳，這意味著一個(gè)操作 不能 在它 完成之后 生效。

如果我們假設(shè)有一個(gè)全局的狀態(tài)與每個(gè)進(jìn)程通信；繼續(xù)假設(shè)與這個(gè)全局狀態(tài)交互的操作都是 原子的 ；那我們可以排除很多可能發(fā)生的記錄。 每個(gè)操作會(huì)在它調(diào)用和完成之間的某個(gè)時(shí)間點(diǎn)原子地生效 。

我們把這樣的一致性模型稱為 線性一致性模型 。盡管操作都是并發(fā)且耗時(shí)的，但每一個(gè)操作都會(huì)在某地以嚴(yán)格的線性順序發(fā)生。

linearizability complete visibility

“全局單點(diǎn)狀態(tài)”并不一定是一個(gè)單獨(dú)的節(jié)點(diǎn)，同樣的，操作也并不一定全是原子的，狀態(tài)也可以被分片成橫跨多臺(tái)機(jī)器，或者分多步完成——只要從進(jìn)程的角度看來(lái)，外部記錄的表現(xiàn)與 一個(gè)原子的單點(diǎn)狀態(tài)等效 。通常一個(gè)可線性化的系統(tǒng)由一些更小的協(xié)調(diào)進(jìn)程組成，這些進(jìn)程本身就是線性的，并且這些進(jìn)程又是由更細(xì)粒度的協(xié)調(diào)進(jìn)程組成，直到 硬件提供可線性化的操作 。

線性化是強(qiáng)大的武器。一旦一個(gè)操作完成，它或它之后的某一狀態(tài)將對(duì) 所有參與者 可見(jiàn)。因?yàn)槊總€(gè)操作 一定 發(fā)生在它的 完成時(shí)間 之前，且任何之后被調(diào)用的操作 一定 發(fā)生在 調(diào)用時(shí)間 之后，也就是在原操作本身之后。 一旦我們成功寫(xiě)入 b ，每個(gè)之后調(diào)用的讀請(qǐng)求都可以讀到 b ，如果有更多的寫(xiě)操作發(fā)生的話，也可以是 b 之后的某個(gè)值。

我們可以利用線性一致性的原子性約束來(lái) 安全地修改狀態(tài) 。我們定義一個(gè)類似 CAS（compare-and-set） 的操作，當(dāng)且僅當(dāng)寄存器持有某個(gè)值的時(shí)候，我們可以往它寫(xiě)入新值。 CAS 操作可以作為互斥量，信號(hào)量，通道，計(jì)數(shù)器，列表，集合，映射，樹(shù)等等的實(shí)現(xiàn)基礎(chǔ)，使得這些共享數(shù)據(jù)結(jié)構(gòu)變得可用。線性一致性保證了變更的 安全交錯(cuò) 。

此外，線性一致性的時(shí)間界限保證了操作完成后，所有變更都對(duì)其他參與者可見(jiàn)。于是線性一致性禁止了過(guò)時(shí)的讀。每次讀都會(huì)讀到某一介于 調(diào)用時(shí)間 與 完成時(shí)間 的狀態(tài)，但永遠(yuǎn)不會(huì)讀到讀請(qǐng)求調(diào)用之前的狀態(tài)。線性一致性同樣禁止了 非單調(diào) 的讀，比如一個(gè)讀請(qǐng)求先讀到了一個(gè)新值，后讀到一個(gè)舊值。

由于這些強(qiáng)約束條件的存在，可線性化的系統(tǒng)變得更容易推理，這也是很多并發(fā)編程模型構(gòu)建的時(shí)候選擇它作為基礎(chǔ)的原因。Javascript中的所有變量都是（獨(dú)立地）可線性化的，其他的還有Java中的volatile變量，Clojure中的atoms，Erlang中獨(dú)立的process。大多數(shù)編程語(yǔ)言都實(shí)現(xiàn)了互斥量和信號(hào)量，它們也是可線性化的。強(qiáng)約束的假設(shè)通常會(huì)產(chǎn)生強(qiáng)約束的保證。

但如果我們無(wú)法滿足這些假設(shè)會(huì)怎么辦？

（線性一致性模型提供了這樣的保證：1.對(duì)于觀察者來(lái)說(shuō)，所有的讀和寫(xiě)都在一個(gè)單調(diào)遞增的時(shí)間線上串行地向前推進(jìn)。 2.所有的讀總能返回最近的寫(xiě)操作的值。）

順序一致性（Sequential consistency）

sequencial history

如果我們?cè)试S進(jìn)程在時(shí)間維度發(fā)生偏移，從而它們的操作可能會(huì)在調(diào)用之前或是完成之后生效，但仍然保證一個(gè)約束——任意進(jìn)程中的操作必須按照進(jìn)程中定義的順序（即編程的定義的邏輯順序）發(fā)生。這樣我們就得到了一個(gè)稍弱的一致性模型： 順序一致性 。

順序一致性允許比線性一致性產(chǎn)生更多的記錄，但它仍然是一個(gè)很有用的模型：我們每天都在使用它。舉個(gè)例子，當(dāng)一個(gè)用戶上傳一段視頻到Y(jié)outube，Youtube把視頻放入一個(gè)處理隊(duì)列，并立刻返回一個(gè)此視頻的網(wǎng)頁(yè)。我們并不能立刻看到視頻，上傳的視頻會(huì)在被充分處理后的幾分鐘內(nèi)生效。隊(duì)列會(huì)以入隊(duì)的順序 同步 地（取決于隊(duì)列的具體實(shí)現(xiàn)）刪除隊(duì)列中的項(xiàng)。

很多緩存的行為和順序一致性系統(tǒng)一直。如果我在Twitter上寫(xiě)了一條推文，或是在Facebook發(fā)布了一篇帖子，都會(huì)耗費(fèi)一定的時(shí)間滲透進(jìn)一層層的緩存系統(tǒng)。不同的用戶將在不同的時(shí)間看到我的信息，但每個(gè)用戶都以 同一個(gè)順序 看到我的操作。一旦看到，這篇帖子便不會(huì)消失。如果我寫(xiě)了多條評(píng)論，其他人也會(huì)按順序的看見(jiàn)，而非亂序。

（順序一致性放松了對(duì)一致性的要求：1. 不要求操作按照真實(shí)的時(shí)間序發(fā)生。2. 不同進(jìn)程間的操作執(zhí)行先后順序也沒(méi)有強(qiáng)制要求，但必須是原子的。3. 單個(gè)進(jìn)程內(nèi)的操作順序必須和編碼時(shí)的順序一直。）

因果一致性（Casual consistency）

我們不必對(duì)一個(gè)進(jìn)程中的 每個(gè) 操作都施加順序約束。只有 因果相關(guān) 的操作必須按順序發(fā)生。同樣拿帖子舉例子：一篇帖子下的所有評(píng)論必須以同樣的順序展示給所有人，并且只有帖子可見(jiàn) 后 ，帖子下的回復(fù)才可見(jiàn)（也就是說(shuō)帖子和帖子下的評(píng)論有因果關(guān)系）。如果我們將這些因果關(guān)系編碼成類似“我依賴于操作X”的形式，作為每個(gè)操作明確的一部分，數(shù)據(jù)庫(kù)就可以將這些操作延遲直到它們的依賴都就緒后才可見(jiàn)。

因果一致性比同一進(jìn)程下對(duì)每個(gè)操作嚴(yán)格排序的一致性（即順序一致性）來(lái)的更寬松——屬于同一進(jìn)程但不同因果關(guān)系鏈的操作能以相對(duì)的順序執(zhí)行（也就是說(shuō)按因果關(guān)系隔離，無(wú)因果關(guān)系的操作可以并發(fā)執(zhí)行），這能防止許多不直觀的行為發(fā)生。

串行一致性（Serializable consistency）

serializable history

如果我們說(shuō)操作記錄的發(fā)生等效于某些單一的原子序，但和調(diào)用時(shí)間與完成時(shí)間無(wú)關(guān)，那么我們就得到了名為 串行一致性 的一致性模型。這一模型比你想象的更強(qiáng)大同時(shí)也更脆弱。

串行一致性是 弱約束 的，因?yàn)樗茉试S多種類型的記錄發(fā)生，且對(duì)時(shí)間或順序不設(shè)邊界。在上面的示意圖中，消息看似可以被任意地發(fā)送至過(guò)去和未來(lái)，因果關(guān)系也可以交錯(cuò)。在一個(gè)串行數(shù)據(jù)庫(kù)中，即使在0時(shí)刻， x 還沒(méi)被初始化，一個(gè)類似 read x 的讀事務(wù)也是允許執(zhí)行的。 或者它也會(huì)被延遲到無(wú)限遠(yuǎn)的未來(lái)執(zhí)行。類似 write 2 to x 的寫(xiě)事務(wù)可以立即執(zhí)行，也可能永遠(yuǎn)都不會(huì)執(zhí)行。

舉個(gè)例子，在一個(gè)串行系統(tǒng)中，有這么一段程序：

x = 1 
 
x = x + 1 
 
puts x 

這段程序可以輸出 nil ， 1 或 2 ，因?yàn)椴僮髂芤匀我忭樞虬l(fā)生。 這是十分弱的約束！這里可以把每一行代碼看作是單個(gè)操作，所有操作都成功執(zhí)行了。

另一方面，串行一致性也是 強(qiáng)約束 的，當(dāng)它要求一個(gè)線性順序時(shí)，它能攔截很大一部分操作記錄?？匆韵鲁绦颍?/p>

print x if x = 3 
 
x = 1 if x = nil 
 
x = 2 if x = 1 
 
x = 3 if x = 2 

這段程序只有一種輸出可能。它并不按我們 編寫(xiě) 的順序輸出，但 x 會(huì)從 nil 開(kāi)始變化： nil -> 1 -> 2 -> 3 ，最終輸出 3 。

因?yàn)榇幸恢滦栽试S對(duì)操作順序執(zhí)行任意的重排（只要操作順序是原子序的）， 它在實(shí)際的場(chǎng)景中并不是十分有用。大多數(shù)宣稱提供了串行一致性的數(shù)據(jù)庫(kù)實(shí)際上提供的是 強(qiáng)串行一致性 ，它有著和線性一致性一樣的時(shí)間邊界。讓事情更復(fù)雜的是，大多數(shù)SQL數(shù)據(jù)庫(kù)宣稱的串行一致性等級(jí)比 實(shí)際的更弱 ，比如可重復(fù)讀，游標(biāo)穩(wěn)定性，或是快照隔離性。

（關(guān)于線性一致性和串行一致性，看似十分相似，其實(shí)不然。串行一致性是數(shù)據(jù)庫(kù)領(lǐng)域的概念，是針對(duì)事務(wù)而言的，描述對(duì)一組事務(wù)的執(zhí)行效果等同于某種串行的執(zhí)行，沒(méi)有ordering的概念，而線性一致性來(lái)自并行計(jì)算領(lǐng)域，描述了針對(duì)某種數(shù)據(jù)結(jié)構(gòu)的操作所表現(xiàn)出的順序特征。 串行一致性是對(duì)多操作，多對(duì)象的保證，對(duì)總體的操作順序無(wú)要求；線性一致性是對(duì)單操作，單對(duì)象的保證，所有操作遵循真實(shí)時(shí)間序 。詳見(jiàn)： http://www.bailis.org/blog/lin ... lity/ ）

一致性的代價(jià)（Consistency comes with costs）

之前說(shuō)了“弱”一致性模型比“強(qiáng)”一致性模型 允許 更多的操作記錄發(fā)生（這里的強(qiáng)與弱是相對(duì)的）。比如線性一致性保證操作在調(diào)用時(shí)間與完成時(shí)間之間發(fā)生。不管怎樣， 需要協(xié)調(diào)來(lái)達(dá)成對(duì)順序的強(qiáng)制約束 。不嚴(yán)格地說(shuō)，執(zhí)行越多的記錄，系統(tǒng)中的參與者就必須越謹(jǐn)慎且通信頻繁。

也許你聽(tīng)說(shuō)過(guò) CAP理論 ，CAP理論聲明給定一致性（ C onsistency），可用性（ A vailability）和分區(qū)容錯(cuò)性（ P artition tolerance），任何系統(tǒng) 至多 能保證以上三項(xiàng)中的 兩項(xiàng) 而不可能滿足全部三項(xiàng)。這是Eric Brewer的CAP猜想的非正式說(shuō)法，以下是準(zhǔn)確的定義：

• 一致性（Consistency）意味著線性化，具體說(shuō)，可以是一個(gè)可線性化的寄存器。寄存器可以等效為集合，列表，映射，關(guān)系型數(shù)據(jù)庫(kù)等等，因此該理論可以被拓展到各種可線性化的系統(tǒng)。
• 可用性（Availability）意味著向非故障節(jié)點(diǎn)發(fā)出的每個(gè)請(qǐng)求都將成功完成。因?yàn)榫W(wǎng)絡(luò)分區(qū)可以持續(xù) 任意長(zhǎng)的時(shí)間 ，因此節(jié)點(diǎn)不能簡(jiǎn)單地把響應(yīng)推遲到分區(qū)結(jié)束。
• 分區(qū)容錯(cuò)性（Partition tolerance）意味著分區(qū)很可能發(fā)生。當(dāng)網(wǎng)絡(luò) 可靠 的時(shí)候，提供一致性和可用性將變得十分 簡(jiǎn)單 ，但當(dāng)網(wǎng)絡(luò) 不可靠 時(shí)，同時(shí)提供一致性和可用性將變得 幾乎不可能 。然而網(wǎng)絡(luò)總不是完美可靠的，所以我們不能選擇CA。所有實(shí)際可用的商用分布式系統(tǒng)至多能提供AP或CP的保證。

family tree

也許你會(huì)說(shuō)：“等等！線性化并不是一致性模型的終極解決方案！我能圍繞著CAP理論提供順序一致性，串行一致性或是快照隔離性！”

沒(méi)錯(cuò)，CAP理論只聲稱 我們不能構(gòu)建一個(gè)完全可用的線性化系統(tǒng) 。但問(wèn)題是我們又有了其他證據(jù)表明我們同樣不能利用順序化，串行化，可重復(fù)讀，快照隔離，游標(biāo)穩(wěn)定或是其它任意一個(gè)比這些強(qiáng)的約束來(lái)構(gòu)建完全可用的系統(tǒng)。在Peter Bailis的Highly Available Transactions這篇論文中，紅色陰影標(biāo)注的模型就不能是 完全 可用的。

如果我們 放松 對(duì)可用性的定義，只要求client節(jié)點(diǎn)能夠一直與同一server保持通信，某種一致性就被達(dá)成了。我們能以此為基礎(chǔ)提供因果一致性，PRAM（pipelined random access memory）一致性和“讀你所寫(xiě)”一致性。

如果我們要求 完全可用 ，那就能提供單調(diào)讀，單調(diào)寫(xiě)，讀的提交，單調(diào)且原子的視角等等。這些一致性模型是由如Riak和Cassandra這樣的分布式存儲(chǔ)系統(tǒng)，低隔離性設(shè)置的ANSI SQL數(shù)據(jù)庫(kù)提供的。這些一致性模型并沒(méi)有保證線性順序，而是在批處理任務(wù)或網(wǎng)絡(luò)場(chǎng)景下提供 部分 順序保證。只能保證部分順序是因?yàn)樗鼈儨?zhǔn)許更豐富的記錄。

一種混合方法（A hybrid approach）

weak not unsafe

一些算法依賴于線性化提供安全性。例如當(dāng)我們想構(gòu)建分布式鎖的服務(wù)時(shí)，我們就需要線性化，如果沒(méi)有硬性的時(shí)間邊界的話，我們就可以持有一把將來(lái)的鎖或是過(guò)去的鎖。而另一方面，很多算法根本 不需要 線性化。即使僅提供“弱”一致性模型，比如有 最終一致性 保證的集合，列表，樹(shù)，映射等結(jié)構(gòu)也能被安全地表示為 CRDTs （Commutative Replicated Data Types）

更強(qiáng)約束的一致性模型需要更多的協(xié)調(diào)——需要更多的消息交互，確保操作在正確的順序發(fā)生。這不僅意味著更低的可用性，還會(huì)被 導(dǎo)致更高的延遲 。這也是為什么現(xiàn)代CPU內(nèi)存模型默認(rèn)不是線性化的，除非顯示指定。（x86-64架構(gòu)的CPU通常以Sequential consistency作為默認(rèn)的memory order），現(xiàn)代CPU會(huì)在核之間重排內(nèi)存操作，甚至更糟糕。雖然（程序的行為）更難以推理，但帶來(lái)的性能提升是驚人的。在地理位置上零落的分布式系統(tǒng)，數(shù)據(jù)中心通常有幾百毫秒的延遲，通常和CPU的場(chǎng)景類似，代價(jià)也相似。

因此在實(shí)踐中，通常會(huì)用 混合 數(shù)據(jù)存儲(chǔ)，在數(shù)據(jù)庫(kù)之間混用不同的一致性模型來(lái)權(quán)衡冗余度，可用性，性能和安全性等目標(biāo)?？赡艿脑捑蜑榱丝捎眯院托阅苓x擇“弱”一致性模型。必要的話就選擇“強(qiáng)”一致性模型，因?yàn)槟承┧惴▽?duì)操作順序有嚴(yán)格要求。我們可以向S3，Riak，Cassandra等數(shù)據(jù)庫(kù)寫(xiě)入大量數(shù)據(jù)，然后線性地向Postgres，ZooKeeper或etcd寫(xiě)入指向數(shù)據(jù)的 指針 。一些數(shù)據(jù)庫(kù)準(zhǔn)許多種一致性模型共存，比如關(guān)系數(shù)據(jù)庫(kù)中的可調(diào)節(jié)隔離等級(jí)，Cassandra和Riak中的線性化事務(wù)，減少了使用的系統(tǒng)數(shù)量。但底線是： 任何人宣稱它的一致性模型是最優(yōu)解，那么他一定是個(gè)大豬蹄子 。

接下來(lái)是精彩評(píng)論時(shí)間

Colin Scott：當(dāng)你提到“屬于同一進(jìn)程但不同因果關(guān)系鏈的操作”的時(shí)候，是否對(duì)潛在的因果關(guān)系（happens before）作了更保守的假設(shè)？我在苦想一個(gè)case，當(dāng)來(lái)自同一臺(tái)機(jī)器上的兩個(gè)存在潛在因果關(guān)系（A必須先于B發(fā)生）的操作并發(fā)時(shí)，會(huì)發(fā)生什么？

Aphyr（作者）：盡管來(lái)自同一個(gè)進(jìn)程的操作在某一節(jié)點(diǎn)上按順序發(fā)生，但它們并不需要在 任何地方都 按序發(fā)生。順序一致性（Sequential consistency）作了這樣的約束，但因果一致性（Casual consistency）并沒(méi)有。只有 顯式 的因果關(guān)系在因果一致性系統(tǒng)中才是順序不變的，而 隱式 的因果關(guān)系在順序一致性系統(tǒng)中作了保證。（因?yàn)槎紒?lái)自同一進(jìn)程，通過(guò)pid區(qū)分）

Aurojit Panda：實(shí)際上你對(duì) Colin Scott 的回復(fù)和你在文章中的 一致性層級(jí)示意圖 是自相矛盾的。 PRAM一致性模型約定：所有節(jié)點(diǎn)都能按同一順序從一個(gè)給定節(jié)點(diǎn)觀測(cè)到它的寫(xiě)操作（Lipton，Sandberg 1988）。而你描述的因果一致性是某一比PRAM一致性更弱的一致性模型，并不是經(jīng)典的因果一致性模型。并且你描述中出現(xiàn)的隱式因果關(guān)系也是PRAM一致性模型約束中的一部分。如果因果一致性比PRAM一致性更強(qiáng)，PRAM一致性就應(yīng)該用任何因果一致性系統(tǒng)來(lái)實(shí)現(xiàn)，利用因果一致性對(duì)單節(jié)點(diǎn)的寫(xiě)操作進(jìn)行正確排序，使得其他節(jié)點(diǎn)的觀測(cè)結(jié)果一致。

Aphyr（作者）：請(qǐng)參考： https://projects.ics.forth.gr/ ... s.pdf ，獲得為什么因果一致性比PRAM更強(qiáng)的詳細(xì)解釋。具體地說(shuō)，有因果關(guān)系的操作可以在中間節(jié)點(diǎn)之間 傳遞 ，但是PRAM并沒(méi)有對(duì)因果一致性的傳遞性作任何定義。

Prakash：關(guān)于問(wèn)題“在你串行一致性的示例中，各種 if 假設(shè)是如何對(duì)順序進(jìn)行約束的？”你的回答中提到“這些操作發(fā)生的順序有且只有一種可能。”而我的問(wèn)題是，當(dāng)我們考慮在并發(fā)環(huán)境下執(zhí)行某種操作時(shí)，是怎么做到“串行有且只有一種可能”的？舉個(gè)例子，我們有不同的線程，其中一個(gè)檢查 x 值是否為3并把它打印，另一個(gè)將 x 的值設(shè)為2。你能解釋一下在這種場(chǎng)景中是如何維護(hù)順序的？

Aphyr（作者）：串行的操作記錄實(shí)際上會(huì)轉(zhuǎn)化為單道線程下的操作記錄，單道線程下的操作記錄就是我們之前的討論中發(fā)揮作用的 狀態(tài)轉(zhuǎn)移方程 。如果以 恒等函數(shù) 作為你的模型，操作記錄中 任何 可能的路徑都是有效的，它們并不會(huì)改變狀態(tài)。為了讓某些操作記錄永遠(yuǎn)不可串行化（限制那些非法的可能造成狀態(tài)轉(zhuǎn)移的操作發(fā)生），不得不聲明一些等效于單線程執(zhí)行的操作無(wú)效，這就是條件語(yǔ)句（ if ）強(qiáng)制部分操作有序的原因。