傳統上，一致性是在「對共享資料的讀寫操作」脈絡下討論的——共享資料可能透過（分散式）共享記憶體、共享資料庫或檔案系統提供。本節使用更廣義的詞：資料儲存（data store）。資料儲存可能實體分散在多台機器上；每個能存取資料的行程，都假設手邊有一份整個儲存的本地（或鄰近）拷貝，寫入操作會被傳播到其他拷貝。凡是改變資料的操作歸類為寫入（write），否則為讀取（read）。

一致性模型（consistency model）本質上是行程與資料儲存之間的一份契約：只要行程遵守某些規則，儲存就承諾正確運作。正常情況下，行程讀取某資料項時期待拿到「最後一次寫入」的結果；但在沒有全域時鐘的情況下，「最後一次」很難精確定義，因此需要其他定義方式，於是產生了一系列一致性模型。每個模型實際上都在限制「讀取一個資料項可以回傳哪些值」。

限制越強的模型越容易使用（例如開發應用程式時），限制越弱的越難用；代價則是：好用的模型效能遠不如難用的。天下沒有白吃的午餐。

連續一致性#

複製資料沒有「最佳解」：只有放鬆一致性才有可能得到有效率的解法，而能容忍什麼樣的不一致高度取決於應用。余（Haifeng Yu）與瓦達特（Amin Vahdat）（2002）提出一個通用做法，以三個獨立的軸定義不一致性，稱為連續一致性範圍（continuous consistency ranges）：

• 數值偏差（numerical deviation）：適用於資料具有數值語意的應用。例如複製股價紀錄時，可規定兩份拷貝相差不得超過 $0.02（絕對數值偏差），或不得超過 0.5%（相對數值偏差）。數值偏差也可以理解為「已施加於某副本、但其他副本尚未看到的更新數量」，此時相應的值偏差也稱為其權重（weight）。
• 過時偏差（staleness deviation）：關乎副本最後一次更新的時間。有些應用可以容忍舊資料，只要不要太舊——例如天氣預報在數小時內大致仍準確，主伺服器可以收到即時更新，但只偶爾傳播給副本。
• 排序偏差（ordering deviation）：有些應用允許各副本上更新的順序不同，只要差異有界。可以把這些更新看成先**暫定（tentatively）**施加在本地拷貝上、等待所有副本的全域共識；因此某些更新可能得回滾（roll back）、換個順序重新施加後才成為永久。

Conit：一致性的度量單位#

為了定義不一致性，Yu 與 Vahdat 引入一致性單位（consistency unit, conit）：指定「以哪個單位來度量一致性」。例如在股市例子中，conit 可以是代表單一股票的紀錄；也可以是一則天氣預報。

延伸案例：以向量時鐘追蹤 conit 的偏差

考慮兩個副本 A、B 操作同一個 conit，其中含資料項 x 與 y（皆初始化為 0），各副本維護一個二維向量時鐘：

• A 已從 B 收到操作 <5,B>: x ← x+2 並使其已提交（committed，不可回滾）；A 另有三個暫定更新操作 <8,A>、<12,A>、<14,A>，故其排序偏差為 3；因最後一個操作 <14,A>，A 的向量時鐘成為 (15,5)。
• A 唯一沒看到的 B 端操作是 <10,B>，故其（操作數量上的）數值偏差為 1；此偏差的權重可表示為「A 的已提交值」與「A 未見的 B 端操作結果」的最大差。A 的已提交值為 (x,y) = (2,0)，而 A 未見的 B 端操作造成 y = 5 的差。
• 同理，B 有兩個暫定更新 <5,B> 與 <10,B>，排序偏差為 2；B 完全沒看過 A 的操作，向量時鐘為 (0,11)，數值偏差為 3、總權重為 6（B 的已提交值是 (0,0)，而 A 端的暫定操作已會把 x 推到 6）。

conit 的粒度存在取捨：

• conit 太大（例如整個資料庫）：所有資料的更新被合併計算，副本更快被判定為不一致。若規定兩副本間未同步更新不得超過一筆，兩個不相干的資料項各更新一次就得觸發傳播；若 conit 較小則還不用。當 conit 內的資料項被完全獨立地使用時，這種情況稱為**假性共享（falsely share）**該 conit。
• conit 太小：需要管理的 conit 總數變多，管理負擔（overhead）本身也會傷害整體效能。

conit 在概念上很有吸引力，但要實用還有兩道關卡：其一，需要有實際執行一致性的協定（本章稍後討論）；其二，開發者必須為應用指定一致性需求，而實務顯示這極其困難——程式設計者通常不熟悉複製，更遑論給出精細的一致性參數，因此簡單易懂的程式介面是必要條件。

連續一致性可以實作成一個工具箱（toolkit），對程式設計者來說就是一個連結進應用程式的程式庫。conit 直接在資料項更新處宣告：

AffectsConit(ConitQ, 1, 1);
append message m to queue Q;

表示「把訊息附加到佇列 Q」屬於名為 ConitQ 的 conit。操作也可以宣告為依賴某個 conit：

DependsOnConit(ConitQ, 4, 0, 60);
read message m from head of queue Q;

這裡指定數值偏差、排序偏差、過時上限分別為 4、0、60（秒）：其他副本上未見的更新至多 4 個、本地不得有暫定更新、且本地拷貝在 60 秒內檢查過新鮮度。若條件不滿足，底層中介軟體（middleware）會先把 Q 的本地拷貝帶到可執行該讀取的狀態。

操作的一致排序#

除了連續一致性之外，過去數十年還累積了大量資料為中心的一致性模型研究，其中重要的一支來自並行程式設計（concurrent programming）領域：當共享資源被複製時，如何表達並行存取的語意。這些模型都在處理「對共享複製資料的操作如何取得一致排序」；它們可視為對連續一致性的補充——當副本上的暫定更新需要提交時，各副本必須就這些更新的全域順序達成共識。

以下使用一種特殊記法：把行程的操作畫在一條由左至右的時間軸上。W_i(x)a 表示行程 P_i 把值 a 寫入資料項 x；R_i(x)b 表示行程 P_i 讀取 x 得到 b。每個資料項初始值皆為 NIL；不會混淆時省略行程下標。

例如：P1 執行 W(x)a——這個操作先施加在 P1 的本地拷貝、再傳播到其他拷貝；P2 稍後先讀到 NIL、又過一會兒才讀到 a。這表示更新傳播到 P2 花了一些時間，完全可以接受。

循序一致性#

**循序一致性（sequential consistency）**是重要的資料為中心一致性模型，最早由藍波特（Leslie Lamport）（1979）在多處理器共享記憶體的脈絡下定義。資料儲存滿足以下條件時稱為循序一致：

任何執行的結果，都等同於所有行程對資料儲存的（讀寫）操作被以某個循序順序執行，且每個行程自己的操作在此序列中保持其程式指定的順序。

• 意思是：行程在（可能）不同機器上並行執行時，任何合法的操作交錯（interleaving）都是可接受的行為，但所有行程必須看到同一種交錯。
• 定義中完全沒有提到時間——沒有「最近一次寫入」的概念。
• 此脈絡下，行程「看得到」所有行程的寫入，但只看得到自己的讀取。

時間不起作用的例子：P1 先（就絕對時間而言）執行 W(x)a，P2 後執行 W(x)b；若 P3 與 P4 都先讀到 b、後讀到 a，這仍是循序一致的——P2 的寫入「看起來」發生在 P1 之前，沒有問題。反之，若 P3 讀到的順序是先 b 後 a、P4 卻是先 a 後 b（最後認定值不同），就違反循序一致性，因為並非所有行程看到相同的交錯。

延伸案例：三個行程的 90 種合法交錯與簽章

考慮三個並行行程 P1、P2、P3，操作初始為 0 的整數變數 x、y、z（Dubois 等人，1988）。每個行程各有一個賦值（寫入）與一個 print（同時讀取兩個變數），所有敘述皆不可分割：

• P1: x ← 1; print(y,z)
• P2: y ← 1; print(x,z)
• P3: z ← 1; print(x,y)

六個獨立敘述理論上有 720（6!）種執行序列，但需扣除違反程式順序者：以 x ← 1 開頭的 120（5!）種序列中，一半讓 print(y,z) 跑在 y ← 1 之前、一半讓 print(x,y) 跑在 z ← 1 之前不合法，僅 30 種合法；三種開頭各 30 種，共 90 種合法執行序列。

把 P1、P2、P3 的輸出（各為 2 位元）串接成 6 位元的簽章（signature），64 種簽章模式並非全部合法：

• 000000 不合法——這意味著 print 全跑在賦值之前，違反程式順序。
• 001001 也不合法：前兩位 00 表示 P1 印出時 y、z 皆為 0，即 P1 兩個敘述都先於 P2、P3；中兩位 10 表示 P2 在 P1 開始後、P3 開始前執行；末兩位 01 卻要求 P3 在 P1 開始前完成——矛盾。

90 種合法排序產生多種（少於 64 種）程式結果。行程與資料儲存的契約是：行程必須接受所有這些合法結果。只對其中部分結果正確運作的程式，就違反了契約，是不正確的程式。

因果一致性#

因果一致性（causal consistency）（Hutto 與 Ahamad，1990）是循序一致性的弱化：它區分「潛在有因果關係」與「沒有因果關係」的事件。因果的概念在前一章討論向量時間戳時已出現過——若事件 b 由較早的事件 a 引起或影響，因果性要求所有人都先看到 a、再看到 b。

• 例：P1 寫入 x，接著 P2 讀取 x 後寫入 y——讀 x 與寫 y 潛在有因果關係，因為 y 的計算可能依賴讀到的 x 值。
• 反之，兩個行程自發且同時寫入不同資料項，則無因果關係。無因果關係的操作稱為並行的（concurrent）。

資料儲存為因果一致的條件：

潛在有因果關係的寫入，必須被所有行程以相同順序看見；並行的寫入則允許在不同機器上以不同順序被看見。

• 例一：W2(x)b 與 W1(x)c 為並行寫入時，各行程以不同順序看到它們是允許的——這種序列因果一致，但循序一致（或嚴格一致）的儲存則禁止。

• 例二：若 P2 先執行 R(x)a 再寫 W(x)b，則 W1(x)a 與 W2(x)b 有因果關係，所有行程必須以相同順序看到兩者；把那個讀取拿掉後，兩個寫入變成並行，不同順序就合法了（但這對循序一致儲存仍不可接受）。

實作因果一致性需要追蹤「哪些行程看過哪些寫入」，實際上是要建構並維護一張操作依賴圖（dependency graph），可用向量時間戳（vector timestamps）達成，本章稍後會再回到這個主題。

操作分組與進入一致性#

循序與因果一致性都定義在個別讀寫操作的層級，這是歷史因素：這些模型最初為共享記憶體多處理器系統而生，且實作在硬體層。但這種細粒度往往與應用程式的粒度不匹配——程式層級的並行通常透過互斥（mutual exclusion）與交易等同步機制控制，讀寫操作實際上被 ENTER_CS 與 LEAVE_CS（CS 即臨界區段，critical section）成對框住：

• 成功執行 ENTER_CS 的行程可以確定本地儲存的資料是最新的，接著可以放心執行一連串讀寫，最後以 LEAVE_CS 收尾。
• 這種「框住」把一串讀寫變成一個不可分割執行的單位，拉高了粒度：受保護的資料不會被並行存取干擾。

其語意以共享同步變數（synchronization variables）表述。這裡採一般化做法：每個同步變數關聯某些資料（可能是全部共享資料）；行程進入臨界區段時取得（acquire）相關同步變數，離開時釋放（release）。每個同步變數有一個目前擁有者（owner）——最後取得它的行程；擁有者可反覆進出臨界區段而不需送出任何網路訊息。未擁有變數的行程要向目前擁有者發訊息索取擁有權與相關資料的目前值；多個行程也可以**非排他模式（nonexclusive mode）**同時擁有一個同步變數——可讀但不可寫相關資料。

必須滿足以下準則（Bershad 等人，1993）：

1. 行程的 acquire 在「受保護共享資料的所有更新都已對該行程生效」之前不得完成——亦即 acquire 時，所有遠端修改必須變得可見。
2. 行程要以排他模式存取同步變數之前，不得有其他行程持有該變數（連非排他模式也不行）——確保更新共享資料前沒有別人同時在更新。
3. 排他模式存取結束後，其他行程的下一次非排他模式存取，必須先向該變數的擁有者查核（取得最新拷貝）後才可進行。

滿足這些準則的模型即進入一致性（entry consistency）。舉例：不對整份共享資料、而是對每個資料項各關聯一把鎖。P1 對 x 做 acquire 並修改 x，之後再對 y 做 acquire；P2 只對 x 做 acquire，因此讀 x 得到 a，但讀 y 可能得到 NIL；P3 先對 y 做 acquire，故在 P1 釋放 y 後會讀到 b。

進入一致性的程式設計難題是如何正確地把資料關聯到同步變數。直接的做法是明確告訴中介軟體要存取哪些資料（如同宣告交易會影響哪些資料表）；物件式做法則可為每個宣告的物件隱含關聯一個唯一同步變數，等效於把對該物件的所有呼叫序列化。

一致性與同調的區別#

最後釐清兩個近義概念：

• 一致性（consistency）模型針對的是一組資料項：多個行程並行操作這組資料時可以期待什麼；遵守模型規則的資料集合稱為一致。
• 同調（coherence）模型針對的是單一資料項（Cantin 等人，2005）：假設某資料項被複製到多處，各拷貝遵守其同調模型規則時稱為同調。

常見的同調模型就是「只施用於單一資料項的循序一致性」：發生並行寫入時，所有行程最終會看到相同的更新順序。