2.1　概述

數據庫管理系統（DataBase Management System，DBMS，以下簡稱“數據庫”），是位于用戶與操作系統之間的一層數據管理軟件，功能主要包括數據定義、數據操縱、數據庫的運行管理、數據庫的建立和維護等（見參考文獻[19]）。

分布式數據庫系統由分布于多個計算機節點上的若干個數據庫系統組成，它提供有效的存取手段來操縱這些節點上的子數據庫。分布式數據庫在使用上可視為一個完整的數據庫，而實際上它分散在處于不同物理位置的各個節點上。當然，分布在各個節點上的子數據庫在邏輯上是相關的[1]。

分布式事務型數據庫系統用于實現分布式事務處理功能。分布式事務處理技術與單機事務處理技術的不同之處是，面向的數據庫系統是否為分布式的，是否引入了分布式系統的一致性問題。這類一致性問題需要與事務一致性問題一起考慮。分布式事務的重點在于ACID特性。所以，分布式事務的一致性是事務的一致性而非外部一致性，但需要考慮外部一致性的需求。

外部一致性的需求表現在這幾個方面：分布式系統受多節點分布、每份數據存在多個副本、各節點間存在時延、所有節點間存在分區等問題的影響。在一個分布式系統中，讀、寫操作對于外部的客戶端而言，需要實現外部一致性以滿足客戶端操作的邏輯一致性。

因為要結合數據庫的事務處理模型、數據的事務一致性要求、分布式的外部一致性要求，所以分布式數據庫的事務處理模型會變得更復雜，需要探索在外部一致性和事務一致性這兩個需求下讀、寫操作之間的關系。為了在系統層面滿足應用對數據庫提出的高可用、高可靠的需求，分布式數據庫的事務處理系統會變得更為復雜，需要探索不同層次的高可用性和分布式事務處理之間的關系，并解決各種故障，如節點上的事務故障、節點故障、分區/通信故障等。為了在系統層面滿足用戶對分布式數據庫提出的高性能的需求，分布式數據庫的事務模型需要拋棄集中式的全局事務處理機制，考慮去中心化的分布式事務模型。

對于分布式一致性來說，可簡單分為如下3種類型（如果細分的話，可分為很多一致性，如順序一致性、FIFO一致性、會話一致性、單讀一致性、單寫一致性等）。

• 弱一致性（weak consistency）：當寫入一個新值后，讀操作在數據副本上可能讀出來，也可能讀不出來。比如搜索引擎，不能實時反映外界信息的真實情況。
• 最終一致性（eventually consistency，見參考文獻[27]）：當寫入一個新值后，有可能讀不出來，但在某個時間窗口之后要保證最終能讀出來（“最終”的含義是所有相關的操作都完成后）。比如電子郵件系統，要保證收件人最終能夠收到相關的郵件。
• 強一致性（strong consistency，見參考文獻[286]）：新的數據一旦寫入，在任意副本中，在任意時刻都能讀到新值。比如文件系統就是強一致性的。

這3種一致性都是分布式架構帶來的一致性，這里的分類方式并不十分科學，但比較形象。這3種不同的一致性，也存在共性的地方，即對數據進行操作，都涉及修改數據，修改后的數據被存儲，然后再被讀取這3個關鍵節點。但是，在最后讀取這個關鍵節點上，3種一致性下讀取數據的效果是不同的。強一致性確保寫過的數據一定能被讀到；弱一致不能確保寫過的數據一定能被讀到；最終一致性在達到“最終”之前可歸入弱一致性，但比弱一致性略強一點，在歷經一定時間并到“最終”時，得到了應得到的結果，這時又可等效于強一致性。從這3種一致性的歸類來看，不同的一致性可以達到的目標或效果是不同的。

下面先簡略討論常見的一致性，然后對各種一致性的細節進行深入分析。

2.1.1　常見的分布式一致性

維基百科[2]討論了幾種常見的一致性，并對不同的一致性進行了定義（注意是在允許并發存在的情況下對一致性進行定義，即允許一定程度的并發事件發生）。

1. 嚴格一致性

嚴格一致性（strict consistency）是最強的一致性。在此類一致性下，任何處理器對變量的寫入都需要所有處理器立即看到。這可以理解為存在一個全局時鐘，在該時鐘周期結束時，每個寫操作都應反映在所有處理器緩存中，下一個操作只能在下一個時鐘周期內發生。

這是一種理想的一致性，對于多個要讀寫同一個數據項的個體（此處假設為處理器）來說，一個個體修改了數據項則其他所有個體（這是并發的場景）在既定的時間內必須獲知修改事件發生。而計算機的硬件體系結構中，一個時鐘周期內處理器只能完成一個最基本的動作，一個時鐘周期是一個最小的讀寫操作發生的時長，如果跨了兩個時鐘周期，則其他處理器（多處理器、多核體系結構）可能讀到此數據項的不同值（寫操作前、寫操作后讀到此數據項的不同的值），從而造成“不同個體讀到不同的數據值”這樣的不一致。

在上面的場景中，對比Spanner等分布式系統，會發現過程非常相似。Spanner中的個體是用戶，用戶要讀寫數據；時鐘周期是在時間軸上的不同時間段；時鐘周期的長度對應著多節點間的網絡時延。所以此處的一致性問題在本質上是對所有操作做全序排序的問題。

2. 順序一致性

順序一致性（sequential consistency）是一種比嚴格一致性更弱的一致性。在順序一致性下，某一處理器對變量的寫入，其他處理器不一定要立即看到，但是，不同處理器對變量的寫入必須以相同的順序被所有處理器看到（一個寫操作的結果不能立刻被其他個體感知，但是對于其他個體來說，這個寫操作的結果總是能確保被其他的個體以同樣的順序“知曉”，這樣就確保了對同一個會話的結果的感知是一致的，即確保保持會話內的因果關系）。就如1979年Lamport所說：若任何執行的結果都與所有處理器的操作以某種順序執行的結果相同，并且每個單獨的處理器的操作以其程序指定的順序出現在該順序中，那么就可以說這個過程滿足順序一致性。

嚴格一致性強調的是寫事件的結果應該被其他個體立刻知曉（似乎沒有時延，但是處于分布式結構中，沒有不耗時的消息傳遞），而順序一致性強調的是“會話寫事件”發生后，需要避免多個觀察者觀察到不同的結果。因此，順序一致性是指“會話內的寫是有序的且會按該序被有序讀到”，因而在順序一致性下，其他多個觀察者看到的結果是一致的。

如圖2-1a所示，P1和P2都寫數據項X，若P3和P4觀察X的過程（兩次讀X）和結果都是一致的（先讀到b后讀到a），則說明該過程符合順序一致性要求。如圖2-1b所示，P1和P2都寫數據項X，若P3和P4觀察X的過程（兩次讀X）和結果是不一致的（P3先讀到b后讀到a，P4先讀到a后讀到b），則說明該過程不符合順序一致性要求。

對于圖2-1所示情況，若個體都是先讀到b后讀到a，則認為該過程具備順序一致性。由此可見，在順序一致性下，只關心所有個體（進程或者節點）的歷史事件是否存在唯一的偏序關系，不關心P1和P2寫數據項X的偏序關系（盡管P1寫X的值a在前）。在順序一致性中，絕對時間無關緊要，事件的順序是最重要的，即要保持一個會話內的因果序而不需要全系統遵守實時（Real-time）限制。

順序一致性首先在參考文獻[84，26]中被定義，其中參考文獻[26]給出了形式化的定義。

3. 線性一致性

線性一致性（linearizability，又稱原子一致性）是Herlihy和Wing在1987年提出的，他們對線性一致性的描述是“can be defined as sequential consistency with the real-time constraint”（可以定義為具有實時約束的序列一致性）。這句話很重要，說明線性一致在考慮了時間的特性后還能夠保證順序一致性，所以線性一致性比順序一致性更為嚴格。

對于線性一致性，大家可以參見參考文獻[183，193，26]。

線性一致強調操作是原子的，在一個原子操作發生時數據項被修改，之后（帶有時間語義）的讀操作都能夠獲取最新的被寫過的數據項的數據值。

在分布式系統中，線性一致性強調的是在涉及多個節點且有多個事件發生時，不管是從哪個節點（副本）執行讀操作，都能讀到按實時順序被修改后的值。

如圖2-1a所示，W(x) a先于W(x) b發生，則P3和P4只有讀到的順序為“R(x)a R(x)b”才符合線性一致性。所以，線性一致性強調了實時排序（Real-time序）的因素。

線性一致的精確定義見參考文獻[183，193，194，26]。

4. 因果一致性

因果一致性（causal consistency）是順序一致性的弱化，它將事件分為因果相關和非因果相關兩類。它定義了只有因果相關的寫操作才需要被所有進程以相同的順序看到。

因果一致性的特別之處在于，需要保持相關的事件的邏輯順序以便保證一致性。遵從會話內的因果一致性為順序一致性。因果一致性，可參考文獻[178]中定義的happened-before關系。

如圖2-2所示，P3和P4采用了同樣的順序（過程一致），卻沒有讀到同樣的值（結果不一致），這不符合順序一致性，但是符合因果一致性。因為P2讀取到a值后才寫x為b值，而P3和P4都先期讀到了a值。

在分布式環境內，一個典型的例子是：創建一個用戶，然后用此用戶登錄系統。這兩個動作前后帶有邏輯關系。如果從一個節點先進行登錄，而該節點不知道用戶被創建這個事實，則登錄必然因用戶不存在而失敗，但事實上確實用戶已經在另外一個節點上創建完畢，只是在這個節點上暫時沒有獲取到這個用戶存在的事實（數據）。

5. 可串行化一致性

如果事務調度的結果（例如，生成的數據庫狀態）等于其串行執行的事務的結果，則事務調度是可串行化的，也就是其具有可串行化的一致性（Serializability），或者說事務具有一致性。

可串行化一致性是數據庫范圍內的事務一致性，其和分布式環境、并發環境下的一致性不同，它們也不可簡單放在一起比較。但是，事務一致性和分布式一致性可以高度融合，成為新的一致性體系，對于這種一致性的研究目前尚在推進中。注意，在分布式數據庫中，事務一致性常和分布式環境中的一致性交叉，對此需要仔細甄別（初步討論參見2.4節）。

6. 強一致性

所謂強一致性（strong consistency）是指所有訪問被所有并行進程（或節點、處理器等）以相同順序（順序）看到。

從并發的角度看，強一致性會使所有參與者觀察到的結果相同。這是通過線性一致性和順序一致性來保證的。

強一致性，更多是從一個系統外部的角度看并發系統的數據是否處于一致的狀態。所以對于一個分布式數據庫系統而言，強一致性需要保證：系統既要滿足事務的可串行化一致性又要滿足分布式系統的一致性（線性一致性或順序一致性）。

7. 最終一致性

最終一致性（eventual consistency）是分布式計算中用于實現高可用性的一致性，它非正式地保證：如果對給定數據項沒有新的更新，那么最終對該項的所有訪問都將返回上次更新的值。

最終一致性服務通常被歸類為提供BASE（基本可用、軟狀態、最終一致性），即基本語義的服務，而不是提供傳統的ACID保證。

強一致性與最終一致性都是從一個系統外部的角度看并發系統的數據是否處于一致的狀態。但在最終一致性條件下，在某些時間點上，可能存在不一致，隨著時間的推移，最終會達成一致（比如多副本之間要達成一致，先讓半數以上達成一致，余者逐步達成一致）。

2.1.2　科研情況一覽

分布式系統的一致性主要包括線性一致性、順序一致性、因果一致性等，更多精確定義見參考文獻[21，26，27，28，29]等。

參考文獻[26]中對非事務存儲系統中的一致性進行了詳細介紹，突出了非事務存儲系統中多種一致性模型中微妙但有意義的差異。這有助于更好地理解非事務存儲系統中一致性之間的聯系與差異。詳情可參見2.3節。

參考文獻[22]中把非事務相關的一致性統一歸為操作一致性，其中包含因果一致性、線性一致性等，并把操作一致性定義為“在多副本的分布式系統下，單次讀寫操作訪問單個數據項時所能夠滿足的語義”，還把“操作一致性”分為兩級——強一致性和弱一致性。強一致性通常被等同于線性一致性和順序一致性，弱一致性則放松了線性一致性對讀寫操作“保持操作發生時的時間順序的邏輯”的要求。

參考文獻[22]中還分析了操作一致性和事務一致性之間的關系：

• 操作一致性是事務一致性實現的基礎。
• 即使操作一致性得到了全面保障，也不能說明事務一致性會得到保障。
• 操作一致性是事務一致性的必要條件。

對于操作一致性的定義，存在的可討論之處如下。

• 操作順序：單次讀寫操作，是讀在前還是寫在前？如果是讀在前，先讀后寫為什么會在多副本的分布式系統中在同一個數據項上發生不一致？之所以會發生不一致，是因為一部分副本先進行寫操作，其他的副本雖然在這之后進行讀操作，但寫入的數據沒有同步到其他副本，致使其他副本提供了舊值，進而造成最新的寫結果不能被后發生的讀操作讀取。所以“單次讀寫操作”應該是“單次先寫后讀操作”。
• 單次的概念：“單次”的含義是什么？在參考文獻[22]中把非事務相關的一致性統一稱為“操作一致性”，故“單次”必然不是針對一個事務的，即對于單次來說沒有事務的概念。沒有事務的概念意味著每個操作都是獨立的，所以先發生的寫操作和后發生的讀操作是兩個操作，不是單次操作。由上可知，“單次”不是指操作的個數。

對于操作一致性的合理理解應當是，“單個會話”內發生的先寫后讀兩個作用在同一個數據對象上的操作，后面發生的讀操作一定能夠讀取到前面的寫操作寫入的數據，所以對于多副本的分布式系統而言，要么區分主備副本且只在主副本上提供讀服務，要么副本間必須強同步后才可以從任何副本上讀取數據。但是，后者顯然需要有事務功能的支持才能確保寫多個副本時“要么成功要么失敗”（至少是寫多個副本時操作是滿足ACID中的“原子性”的）。

參考文獻[29]把分布式系統中的“單調讀”“單調寫”“因果一致性”等一致性歸于“session guarantees”（會話保證），這意味著分布式系統下的一部分一致性問題是與會話（session）相關的。

對于操作一致性的另外一種理解是，“多個會話”發生了先寫后讀事件，此時需有機制確定不同會話間發生的事件的先后順序，比如Spanner利用Truetime機制排序任何會話上發生的操作。

以上情況，均不是“單次”之意所能表達的。因此，本章將分布式系統涉及的一致性，統一稱為分布式一致性，其中包括了強一致性的外部一致性，弱一致性的最終一致性。而分布式一致性有一部分一致性，如單調讀、單調寫、因果一致性等，更強調讀和寫操作，或者說讀和寫事件之間發生的順序，這是一種邏輯關系。而表示順序的邏輯關系的天然方式就是時間，因此一些系統利用時間對讀和寫事件的前后邏輯關系進行標識。另外，強一致性中諸如外部一致性，對于一系列的操作（如事務內的多個寫操作）更多強調其操作序列的原子性，也強調在多副本下同步數據的原子性，只有原子性得到保障，才能進一步考慮分布式系統下的帶有“前后關系的邏輯特性”。

對于分布式數據庫系統（非NoSQL系統），根據CAP分布式原理，可以把因分布式系統對數據庫的影響限制在較強的一致性上（順序一致性、線性一致性等）。

參考文獻[261]統一定義了多種一致性，并試圖把分布式一致性和事務一致性進行結合（見圖2-3），但是這種結合還是著力在分布式一致性上，使得分布式一致性和事務一致性的結合只落腳在嚴格可串行化（strict serializability）上，參考文獻中沒有更深入探索如何把二者緊密結合，這類似參考文獻[29]給出的關系，如圖2-4所示（結合點只有一個，即嚴格可串行化）。

在分布式架構中，物理節點是分離的，每個節點相對獨立，節點間通過網絡相連，全部獨立的節點和網絡構成一個完整的系統。

分布式架構中，實體對象有兩類——物理節點和網絡。物理節點存在失效（故障）的可能，網絡也存在失效的可能。這兩類對象的失效為分布式系統帶來了可靠性、可用性方面的問題。即使不失效，網絡上也存在時延的問題，時延為分布式系統帶來了可用性方面的問題（參見1.2.2節）。

另外，分布式系統中并發事件間的順序會引發一致性問題，這涉及不同的讀、寫操作對存儲的數據項進行的并發操作，以及并發操作事件在數據項上體現出的對結果是否可讀、何時可讀的問題，這樣的問題就是分布式架構為分布式系統帶來的復雜的一致性——分布式一致性。本章開篇曾介紹過，分布式一致性又可分為結果一致性（consensus，共識，一致的意見）[6]和次序一致性（consistency，一致的順序），后者是本書討論的重點。

另外，對于分布式事務型數據庫，還有事務的一致性問題，這將在2.4節討論。

接下來的兩節將分別對結果一致性和次序一致性進行討論。

---

[1]參見https://baike.baidu.com/item/分布式系統/4905336?fr=aladdin。

[2]https://en.wikipedia.org/wiki/Consistency_model。

[3]參見http://regal.csep.umflint.edu/~swturner/Classes/csc577/Online/Chapter06/img06.html。

[4]http://regal.csep.umflint.edu/~swturner/Classes/csc577/Online/Chapter06/img10.html。

[5]圖中使用結果可見性來定義一系列共識和一致性。選中標記表示在一致性中被強制執行的約束。這里我們假設程序、會話和事務是等價的。注意，因為結果可見性是一個不變量，所以約束是可加的，不需要提前執行。因此，我們可以僅使用結果可見性來構造此表的列，從而簡潔地表示各種排序保證。

[6]結果一致性，可用consensus一詞表達其含義，即為“共識”。所謂共識就是對某種行為、結果實現共同認可。