老規(guī)矩，枯燥乏味的論文，需要精神支持，先給兄弟們上圖，緩解疲勞。

這個問題不僅僅是單主復(fù)制和多主復(fù)制的后果：任何線性一致的數(shù)據(jù)庫都有這個問題，不管它是如何實現(xiàn)的。這個問題也不僅僅局限于多數(shù)據(jù)中心部署，而可能發(fā)生在任何不可靠的網(wǎng)絡(luò)上，即使在同一個數(shù)據(jù)中心內(nèi)也是如此。問題面臨的權(quán)衡如下：5

• 如果應(yīng)用需要線性一致性，且某些副本因為網(wǎng)絡(luò)問題與其他副本斷開連接，那么這些副本掉線時不能處理請求。請求必須等到網(wǎng)絡(luò)問題解決，或直接返回錯誤。（無論哪種方式，服務(wù)都 不可用）。

• 如果應(yīng)用不需要線性一致性，那么某個副本即使與其他副本斷開連接，也可以獨立處理請求（例如多主復(fù)制）。在這種情況下，應(yīng)用可以在網(wǎng)絡(luò)問題解決前保持可用，但其行為不是線性一致的。

因此，不需要線性一致性的應(yīng)用對網(wǎng)絡(luò)問題有更強的容錯能力。這種見解通常被稱為 CAP 定理【29,30,31,32】，由 Eric Brewer 于 2000 年命名，盡管 70 年代的分布式數(shù)據(jù)庫設(shè)計者早就知道了這種權(quán)衡【33,34,35,36】。

CAP 最初是作為一個經(jīng)驗法則提出的，沒有準確的定義，目的是開始討論數(shù)據(jù)庫的權(quán)衡。那時候許多分布式數(shù)據(jù)庫側(cè)重于在共享存儲的集群上提供線性一致性的語義【18】，CAP 定理鼓勵數(shù)據(jù)庫工程師向分布式無共享系統(tǒng)的設(shè)計領(lǐng)域深入探索，這類架構(gòu)更適合實現(xiàn)大規(guī)模的網(wǎng)絡(luò)服務(wù)【37】。對于這種文化上的轉(zhuǎn)變，CAP 值得贊揚 —— 它見證了自 00 年代中期以來新數(shù)據(jù)庫的技術(shù)爆炸（即 NoSQL）。

順序保證

之前說過，線性一致寄存器的行為就好像只有單個數(shù)據(jù)副本一樣，且每個操作似乎都是在某個時間點以原子性的方式生效的。這個定義意味著操作是按照某種良好定義的順序執(zhí)行的。我們將操作以看上去被執(zhí)行的順序連接起來，以此說明了 圖 9-4 中的順序。

順序（ordering） 這一主題在本書中反復(fù)出現(xiàn)，這表明它可能是一個重要的基礎(chǔ)性概念。讓我們簡要回顧一下其它曾經(jīng)出現(xiàn)過 順序 的上下文：

• 在 第五章 中我們看到，領(lǐng)導(dǎo)者在單主復(fù)制中的主要目的就是，在復(fù)制日志中確定 寫入順序（order of write）—— 也就是從庫應(yīng)用這些寫入的順序。如果不存在一個領(lǐng)導(dǎo)者，則并發(fā)操作可能導(dǎo)致沖突（請參閱 “處理寫入沖突”）。

• 在 第七章 中討論的 可串行化，是關(guān)于事務(wù)表現(xiàn)的像按 某種先后順序（some sequential order） 執(zhí)行的保證。它可以字面意義上地以 串行順序（serial order） 執(zhí)行事務(wù)來實現(xiàn)，或者允許并行執(zhí)行，但同時防止序列化沖突來實現(xiàn)（通過鎖或中止事務(wù)）。

• 在 第八章 討論過的在分布式系統(tǒng)中使用時間戳和時鐘（請參閱 “依賴同步時鐘”）是另一種將順序引入無序世界的嘗試，例如，確定兩個寫入操作哪一個更晚發(fā)生。

事實證明，順序、線性一致性和共識之間有著深刻的聯(lián)系。盡管這個概念比本書其他部分更加理論化和抽象，但對于明確系統(tǒng)的能力范圍（可以做什么和不可以做什么）而言是非常有幫助的。我們將在接下來的幾節(jié)中探討這個話題。

順序與因果關(guān)系

順序 反復(fù)出現(xiàn)有幾個原因，其中一個原因是，它有助于保持 因果關(guān)系（causality）。在本書中我們已經(jīng)看到了幾個例子，其中因果關(guān)系是很重要的：

• 在 “一致前綴讀”（圖 5-5）中，我們看到一個例子：一個對話的觀察者首先看到問題的答案，然后才看到被回答的問題。這是令人困惑的，因為它違背了我們對 因（cause） 與 果（effect） 的直覺：如果一個問題被回答，顯然問題本身得先在那里，因為給出答案的人必須先看到這個問題（假如他們并沒有預(yù)見未來的超能力）。我們認為在問題和答案之間存在 因果依賴（causal dependency）。

• 圖 5-9 中出現(xiàn)了類似的模式，我們看到三位領(lǐng)導(dǎo)者之間的復(fù)制，并注意到由于網(wǎng)絡(luò)延遲，一些寫入可能會 “壓倒” 其他寫入。從其中一個副本的角度來看，好像有一個對尚不存在的記錄的更新操作。這里的因果意味著，一條記錄必須先被創(chuàng)建，然后才能被更新。

• 在 “檢測并發(fā)寫入” 中我們觀察到，如果有兩個操作 A 和 B，則存在三種可能性：A 發(fā)生在 B 之前，或 B 發(fā)生在 A 之前，或者 A 和 B并發(fā)。這種 此前發(fā)生（happened before） 關(guān)系是因果關(guān)系的另一種表述：如果 A 在 B 前發(fā)生，那么意味著 B 可能已經(jīng)知道了 A，或者建立在 A 的基礎(chǔ)上，或者依賴于 A。如果 A 和 B 是 并發(fā) 的，那么它們之間并沒有因果聯(lián)系；換句話說，我們確信 A 和 B 不知道彼此。

• 在事務(wù)快照隔離的上下文中（“快照隔離和可重復(fù)讀”），我們說事務(wù)是從一致性快照中讀取的。但此語境中 “一致” 到底又是什么意思？這意味著 與因果關(guān)系保持一致（consistent with causality）：如果快照包含答案，它也必須包含被回答的問題【48】。在某個時間點觀察整個數(shù)據(jù)庫，與因果關(guān)系保持一致意味著：因果上在該時間點之前發(fā)生的所有操作，其影響都是可見的，但因果上在該時間點之后發(fā)生的操作，其影響對觀察者不可見。讀偏差（read skew） 意味著讀取的數(shù)據(jù)處于違反因果關(guān)系的狀態(tài)（不可重復(fù)讀，如 圖 7-6 所示）。

• 事務(wù)之間 寫偏差（write skew） 的例子（請參閱 “寫入偏差與幻讀”）也說明了因果依賴：在 圖 7-8 中，愛麗絲被允許離班，因為事務(wù)認為鮑勃仍在值班，反之亦然。在這種情況下，離班的動作因果依賴于對當(dāng)前值班情況的觀察?？纱谢煺崭綦x 通過跟蹤事務(wù)之間的因果依賴來檢測寫偏差。

• 在愛麗絲和鮑勃看球的例子中（圖 9-1），在聽到愛麗絲驚呼比賽結(jié)果后，鮑勃從服務(wù)器得到陳舊結(jié)果的事實違背了因果關(guān)系：愛麗絲的驚呼因果依賴于得分宣告，所以鮑勃應(yīng)該也能在聽到愛麗斯驚呼后查詢到比分。相同的模式在 “跨信道的時序依賴” 一節(jié)中，以 “圖像大小調(diào)整服務(wù)” 的偽裝再次出現(xiàn)。

因果關(guān)系對事件施加了一種 順序：因在果之前；消息發(fā)送在消息收取之前。而且就像現(xiàn)實生活中一樣，一件事會導(dǎo)致另一件事：某個節(jié)點讀取了一些數(shù)據(jù)然后寫入一些結(jié)果，另一個節(jié)點讀取其寫入的內(nèi)容，并依次寫入一些其他內(nèi)容，等等。這些因果依賴的操作鏈定義了系統(tǒng)中的因果順序，即，什么在什么之前發(fā)生。

如果一個系統(tǒng)服從因果關(guān)系所規(guī)定的順序，我們說它是 因果一致（causally consistent） 的。例如，快照隔離提供了因果一致性：當(dāng)你從數(shù)據(jù)庫中讀取到一些數(shù)據(jù)時，你一定還能夠看到其因果前驅(qū)（假設(shè)在此期間這些數(shù)據(jù)還沒有被刪除）。

因果順序不是全序的

全序（total order） 允許任意兩個元素進行比較，所以如果有兩個元素，你總是可以說出哪個更大，哪個更小。例如，自然數(shù)集是全序的：給定兩個自然數(shù)，比如說 5 和 13，那么你可以告訴我，13 大于 5。

然而數(shù)學(xué)集合并不完全是全序的：{a, b} 比 {b, c} 更大嗎？好吧，你沒法真正比較它們，因為二者都不是對方的子集。我們說它們是 無法比較（incomparable） 的，因此數(shù)學(xué)集合是 偏序的（partially ordered） ：在某些情況下，可以說一個集合大于另一個（如果一個集合包含另一個集合的所有元素），但在其他情況下它們是無法比較的 7。

全序和偏序之間的差異反映在不同的數(shù)據(jù)庫一致性模型中：

• 線性一致性

  在線性一致的系統(tǒng)中，操作是全序的：如果系統(tǒng)表現(xiàn)的就好像只有一個數(shù)據(jù)副本，并且所有操作都是原子性的，這意味著對任何兩個操作，我們總是能判定哪個操作先發(fā)生。這個全序在 圖 9-4 中以時間線表示。

• 因果性

  我們說過，如果兩個操作都沒有在彼此 之前發(fā)生，那么這兩個操作是并發(fā)的（請參閱 “此前發(fā)生” 的關(guān)系和并發(fā)）。換句話說，如果兩個事件是因果相關(guān)的（一個發(fā)生在另一個事件之前），則它們之間是有序的，但如果它們是并發(fā)的，則它們之間的順序是無法比較的。這意味著因果關(guān)系定義了一個偏序，而不是一個全序：一些操作相互之間是有順序的，但有些則是無法比較的。

因此，根據(jù)這個定義，在線性一致的數(shù)據(jù)存儲中是不存在并發(fā)操作的：必須有且僅有一條時間線，所有的操作都在這條時間線上，構(gòu)成一個全序關(guān)系?？赡苡袔讉€請求在等待處理，但是數(shù)據(jù)存儲確保了每個請求都是在唯一時間線上的某個時間點自動處理的，不存在任何并發(fā)。

并發(fā)意味著時間線會分岔然后合并 —— 在這種情況下，不同分支上的操作是無法比較的（即并發(fā)操作）。在 第五章 中我們看到了這種現(xiàn)象：例如，圖 5-14 并不是一條直線的全序關(guān)系，而是一堆不同的操作并發(fā)進行。圖中的箭頭指明了因果依賴 —— 操作的偏序。

如果你熟悉像 Git 這樣的分布式版本控制系統(tǒng)，那么其版本歷史與因果關(guān)系圖極其相似。通常，一個 提交（Commit） 發(fā)生在另一個提交之后，在一條直線上。但是有時你會遇到分支（當(dāng)多個人同時在一個項目上工作時），合并（Merge） 會在這些并發(fā)創(chuàng)建的提交相融合時創(chuàng)建。

線性一致性強于因果一致性

那么因果順序和線性一致性之間的關(guān)系是什么？答案是線性一致性 隱含著（implies） 因果關(guān)系：任何線性一致的系統(tǒng)都能正確保持因果性【7】。特別是，如果系統(tǒng)中有多個通信通道（如 圖 9-5 中的消息隊列和文件存儲服務(wù)），線性一致性可以自動保證因果性，系統(tǒng)無需任何特殊操作（如在不同組件間傳遞時間戳）。

線性一致性確保因果性的事實使線性一致系統(tǒng)變得簡單易懂，更有吸引力。然而，正如 “線性一致性的代價” 中所討論的，使系統(tǒng)線性一致可能會損害其性能和可用性，尤其是在系統(tǒng)具有嚴重的網(wǎng)絡(luò)延遲的情況下（例如，如果系統(tǒng)在地理上散布）。出于這個原因，一些分布式數(shù)據(jù)系統(tǒng)已經(jīng)放棄了線性一致性，從而獲得更好的性能，但它們用起來也更為困難。

好消息是存在折衷的可能性。線性一致性并不是保持因果性的唯一途徑 —— 還有其他方法。一個系統(tǒng)可以是因果一致的，而無需承擔(dān)線性一致帶來的性能折損（尤其對于 CAP 定理不適用的情況）。實際上在所有的不會被網(wǎng)絡(luò)延遲拖慢的一致性模型中，因果一致性是可行的最強的一致性模型。而且在網(wǎng)絡(luò)故障時仍能保持可用【2,42】。

在許多情況下，看上去需要線性一致性的系統(tǒng)，實際上需要的只是因果一致性，因果一致性可以更高效地實現(xiàn)。基于這種觀察結(jié)果，研究人員正在探索新型的數(shù)據(jù)庫，既能保證因果一致性，且性能與可用性與最終一致的系統(tǒng)類似【49,50,51】。

這方面的研究相當(dāng)新鮮，其中很多尚未應(yīng)用到生產(chǎn)系統(tǒng)，仍然有不少挑戰(zhàn)需要克服【52,53】。但對于未來的系統(tǒng)而言，這是一個有前景的方向。

捕獲因果關(guān)系

我們不會在這里討論非線性一致的系統(tǒng)如何保證因果性的細節(jié)，而只是簡要地探討一些關(guān)鍵的思想。

為了維持因果性，你需要知道哪個操作發(fā)生在哪個其他操作之前（happened before）。這是一個偏序：并發(fā)操作可以以任意順序進行，但如果一個操作發(fā)生在另一個操作之前，那它們必須在所有副本上以那個順序被處理。因此，當(dāng)一個副本處理一個操作時，它必須確保所有因果前驅(qū)的操作（之前發(fā)生的所有操作）已經(jīng)被處理；如果前面的某個操作丟失了，后面的操作必須等待，直到前面的操作被處理完畢。

為了確定因果依賴，我們需要一些方法來描述系統(tǒng)中節(jié)點的 “知識”。如果節(jié)點在發(fā)出寫入 Y 的請求時已經(jīng)看到了 X 的值，則 X 和 Y 可能存在因果關(guān)系。這個分析使用了那些在欺詐指控刑事調(diào)查中常見的問題：CEO 在做出決定 Y 時是否 知道 X ？

用于確定 哪些操作發(fā)生在其他操作之前 的技術(shù)，與我們在 “檢測并發(fā)寫入” 中所討論的內(nèi)容類似。那一節(jié)討論了無領(lǐng)導(dǎo)者數(shù)據(jù)存儲中的因果性：為了防止丟失更新，我們需要檢測到對同一個鍵的并發(fā)寫入。因果一致性則更進一步：它需要跟蹤整個數(shù)據(jù)庫中的因果依賴，而不僅僅是一個鍵?？梢酝茝V版本向量以解決此類問題【54】。

為了確定因果順序，數(shù)據(jù)庫需要知道應(yīng)用讀取了哪個版本的數(shù)據(jù)。這就是為什么在 圖 5-13 中，來自先前操作的版本號在寫入時被傳回到數(shù)據(jù)庫的原因。在 SSI 的沖突檢測中會出現(xiàn)類似的想法，如 “可串行化快照隔離” 中所述：當(dāng)事務(wù)要提交時，數(shù)據(jù)庫將檢查它所讀取的數(shù)據(jù)版本是否仍然是最新的。為此，數(shù)據(jù)庫跟蹤哪些數(shù)據(jù)被哪些事務(wù)所讀取。

序列號順序

雖然因果是一個重要的理論概念，但實際上跟蹤所有的因果關(guān)系是不切實際的。在許多應(yīng)用中，客戶端在寫入內(nèi)容之前會先讀取大量數(shù)據(jù)，我們無法弄清寫入因果依賴于先前全部的讀取內(nèi)容，還是僅包括其中一部分。顯式跟蹤所有已讀數(shù)據(jù)意味著巨大的額外開銷。

但還有一個更好的方法：我們可以使用 序列號（sequence number） 或 時間戳（timestamp） 來排序事件。時間戳不一定來自日歷時鐘（或物理時鐘，它們存在許多問題，如 “不可靠的時鐘” 中所述）。它可以來自一個 邏輯時鐘（logical clock），這是一個用來生成標識操作的數(shù)字序列的算法，典型實現(xiàn)是使用一個每次操作自增的計數(shù)器。

這樣的序列號或時間戳是緊湊的（只有幾個字節(jié)大?。峁┝艘粋€全序關(guān)系：也就是說每個操作都有一個唯一的序列號，而且總是可以比較兩個序列號，確定哪一個更大（即哪些操作后發(fā)生）。

特別是，我們可以使用 與因果一致（consistent with causality） 的全序來生成序列號 8：我們保證，如果操作 A 因果地發(fā)生在操作 B 前，那么在這個全序中 A 在 B 前（ A 具有比 B 更小的序列號）。并行操作之間可以任意排序。這樣一個全序關(guān)系捕獲了所有關(guān)于因果的信息，但也施加了一個比因果性要求更為嚴格的順序。

在單主復(fù)制的數(shù)據(jù)庫中（請參閱 “領(lǐng)導(dǎo)者與追隨者”），復(fù)制日志定義了與因果一致的寫操作。主庫可以簡單地為每個操作自增一個計數(shù)器，從而為復(fù)制日志中的每個操作分配一個單調(diào)遞增的序列號。如果一個從庫按照它們在復(fù)制日志中出現(xiàn)的順序來應(yīng)用寫操作，那么從庫的狀態(tài)始終是因果一致的（即使它落后于領(lǐng)導(dǎo)者）。

非因果序列號生成器

如果主庫不存在（可能因為使用了多主數(shù)據(jù)庫或無主數(shù)據(jù)庫，或者因為使用了分區(qū)的數(shù)據(jù)庫），如何為操作生成序列號就沒有那么明顯了。在實踐中有各種各樣的方法：

• 每個節(jié)點都可以生成自己獨立的一組序列號。例如有兩個節(jié)點，一個節(jié)點只能生成奇數(shù)，而另一個節(jié)點只能生成偶數(shù)。通常，可以在序列號的二進制表示中預(yù)留一些位，用于唯一的節(jié)點標識符，這樣可以確保兩個不同的節(jié)點永遠不會生成相同的序列號。可以將日歷時鐘（物理時鐘）的時間戳附加到每個操作上【55】。這種時間戳并不連續(xù)，但是如果它具有足夠高的分辨率，那也許足以提供一個操作的全序關(guān)系。這一事實應(yīng)用于 最后寫入勝利 * 的沖突解決方法中（請參閱 “有序事件的時間戳”）。

• 可以預(yù)先分配序列號區(qū)塊。例如，節(jié)點 A 可能要求從序列號 1 到 1,000 區(qū)塊的所有權(quán)，而節(jié)點 B 可能要求序列號 1,001 到 2,000 區(qū)塊的所有權(quán)。然后每個節(jié)點可以獨立分配所屬區(qū)塊中的序列號，并在序列號告急時請求分配一個新的區(qū)塊。

這三個選項都比單一主庫的自增計數(shù)器表現(xiàn)要好，并且更具可伸縮性。它們?yōu)槊總€操作生成一個唯一的，近似自增的序列號。然而它們都有同一個問題：生成的序列號與因果不一致。

因為這些序列號生成器不能正確地捕獲跨節(jié)點的操作順序，所以會出現(xiàn)因果關(guān)系的問題：

• 每個節(jié)點每秒可以處理不同數(shù)量的操作。因此，如果一個節(jié)點產(chǎn)生偶數(shù)序列號而另一個產(chǎn)生奇數(shù)序列號，則偶數(shù)計數(shù)器可能落后于奇數(shù)計數(shù)器，反之亦然。如果你有一個奇數(shù)編號的操作和一個偶數(shù)編號的操作，你無法準確地說出哪一個操作在因果上先發(fā)生。

• 來自物理時鐘的時間戳?xí)艿綍r鐘偏移的影響，這可能會使其與因果不一致。例如 圖 8-3 展示了一個例子，其中因果上晚發(fā)生的操作，卻被分配了一個更早的時間戳。8

• 在分配區(qū)塊的情況下，某個操作可能會被賦予一個范圍在 1,001 到 2,000 內(nèi)的序列號，然而一個因果上更晚的操作可能被賦予一個范圍在 1 到 1,000 之間的數(shù)字。這里序列號與因果關(guān)系也是不一致的。

蘭伯特時間戳

盡管剛才描述的三個序列號生成器與因果不一致，但實際上有一個簡單的方法來產(chǎn)生與因果關(guān)系一致的序列號。它被稱為蘭伯特時間戳，萊斯利?蘭伯特（Leslie Lamport）于 1978 年提出【56】，現(xiàn)在是分布式系統(tǒng)領(lǐng)域中被引用最多的論文之一。

圖 9-8 說明了蘭伯特時間戳的應(yīng)用。每個節(jié)點都有一個唯一標識符，和一個保存自己執(zhí)行操作數(shù)量的計數(shù)器。蘭伯特時間戳就是兩者的簡單組合：（計數(shù)器，節(jié)點 ID）$(counter, node ID)$。兩個節(jié)點有時可能具有相同的計數(shù)器值，但通過在時間戳中包含節(jié)點 ID，每個時間戳都是唯一的。