Skip to content

6. 複製

與可能出錯的東西比，“不可能”出錯的東西最顯著的特點就是：一旦真的出錯，通常就徹底玩完了。

—— 道格拉斯・亞當斯，《基本無害》（1992）

複製 意味著在透過網路連線的多臺機器上保留相同資料的副本。正如 “分散式與單節點系統” 中所討論的，我們希望複製資料，可能出於以下原因：

  • 使資料在地理上更接近使用者（從而降低訪問延遲）
  • 即使系統的一部分發生故障，系統仍能繼續工作（從而提高可用性）
  • 增加能夠處理讀查詢的機器數量（從而提高讀取吞吐量）

本章假設資料集足夠小，每臺機器都能儲存整個資料集的副本。在 第 7 章 中，我們將放寬這一假設，討論單臺機器無法容納的大型資料集如何進行 分片（分割槽）。再往後的章節會討論複製資料系統中可能出現的各種故障，以及應對這些故障的方法。

如果要複製的資料不隨時間變化，複製就很簡單：只需把資料複製到每個節點一次，便大功告成。複製的全部難點都在於處理被複制資料的 變更，這正是本章的主題。我們將討論三類在節點之間複製變更的演算法：單主複製、多主複製 和 無主複製。幾乎所有分散式資料庫都採用其中一種。三者各有利弊，本章將逐一詳述。

複製需要考慮許多權衡，例如採用同步複製還是非同步複製，以及如何處理失效的副本。這些往往都是資料庫的配置選項；具體細節因資料庫而異，但不同實現背後的基本原理大體相通。本章將討論這些選擇帶來的後果。

資料庫複製算得上是老生常談：自 20 世紀 70 年代有人開始研究以來，其基本原理並沒有太大變化 1，因為網路的根本約束也一直未變。即便如此，最終一致性 等概念仍常常引起困惑。在 “複製延遲的問題” 中，我們會更精確地說明最終一致性，並討論 讀己之寫、單調讀 等保證。

備份與複製

你可能會問：有了複製，是否還需要備份？答案是肯定的，因為二者目的不同。副本會迅速把一個節點上的寫入反映到其他節點，而備份儲存的是資料在過去某一時刻的快照，以便恢復到先前狀態。如果不慎刪除了某些資料，複製幫不上忙，因為刪除操作也會傳播到所有副本；要恢復這些資料，仍然需要備份。

事實上，複製與備份往往相輔相成。正如 “設定新的副本” 中將要看到的，備份有時是建立複製的一環；反過來，歸檔複製日誌也可以成為備份流程的一部分。

有些資料庫會在內部維護過去狀態的不可變快照，相當於一種內建備份。不過，這意味著舊版本和當前狀態要儲存在同一類儲存介質上。資料量很大時，把舊資料的備份放在針對低頻訪問最佳化的物件儲存中，往往比放在主儲存中便宜；主儲存只需保留資料庫的當前狀態。

單主複製

每個儲存資料庫複製的節點都稱為一個 副本。存在多個副本時，一個問題不可避免：如何確保所有資料最終都出現在所有副本上？

資料庫的每次寫入都必須由每個副本處理，否則各副本就會包含不同的資料。最常見的解決方案稱為 基於領導者的複製，也稱 主備複製 或 主動/被動複製。其工作原理如下（見 圖 6-1）：

  1. 其中一個副本被指定為 領導者（也稱 主庫 或 源 2）。客戶端要寫入資料庫時，必須把請求發給領導者；領導者首先將新資料寫入本地儲存。
  2. 其他副本稱為 追隨者（也稱 只讀副本、備庫 或 熱備）。領導者每次把新資料寫入本地儲存，也會把資料變更作為 複製日誌 或 變更流 傳送給所有追隨者。每個追隨者取得領導者的日誌，按照領導者處理寫入的相同順序應用所有寫入，從而更新本地的資料庫副本。
  3. 客戶端讀取資料庫時，可以查詢領導者，也可以查詢任意追隨者；但只有領導者接受寫入（從客戶端的角度看，追隨者是隻讀的）。
圖 6-1. 單主複製把所有寫入都發往指定的領導者，再由領導者將變更流傳送給各追隨者副本。

如果資料庫做了分片（見 第 7 章），每個分片都有一個領導者。不同分片的領導者可以位於不同節點，但每個分片仍必須有且只有一個領導者。在 “多主複製” 中，我們將討論另一種模型：同一分片可以同時有多個領導者。

單主複製應用極為廣泛。它是 PostgreSQL、MySQL、Oracle Data Guard 3 和 SQL Server Always On 可用性組 4 等許多關係資料庫的內建功能；MongoDB、DynamoDB 5 等文件資料庫，Kafka 等訊息代理，DRBD 等複製塊裝置，以及一些網路檔案系統也採用這種方式。Raft 等許多共識演算法同樣以單個領導者為基礎；CockroachDB 6、TiDB 7、etcd、RabbitMQ 法定人數佇列等系統用它來實現複製，並在原領導者失效時自動選舉新領導者（第 10 章 將更詳細地討論共識）。

Note

較早的資料中可能會出現 主從複製（master–slave replication）一詞。它與基於領導者的複製含義相同，但如今普遍認為這種說法具有冒犯性，應當避免使用 8。

同步複製與非同步複製

複製系統的一個重要細節是，複製究竟 同步 進行還是 非同步 進行。（在關係資料庫中，這通常是一個配置項；其他系統往往固定採用其中一種。）

設想 圖 6-1 中的情形：某網站使用者更新個人頭像。客戶端在某個時刻向領導者發出更新請求，不久後領導者收到請求；領導者隨後在某個時刻把資料變更轉發給追隨者，並最終通知客戶端更新成功。圖 6-2 展示了其中一種可能的時序。

圖 6-2. 基於領導者的複製，其中一個追隨者同步複製，另一個非同步複製。

在 圖 6-2 的例子中，發往追隨者 1 的複製是 同步 的：領導者必須等到追隨者 1 確認收到寫入，才能向用戶報告成功，也才能讓其他客戶端看到這次寫入。發往追隨者 2 的複製則是 非同步 的：領導者發出訊息，但不等待追隨者響應。

圖中追隨者 2 處理訊息前有一段明顯的延遲。通常複製相當快：大多數資料庫系統不到一秒便能把變更應用到追隨者，但它們並不保證複製一定能在多久內完成。有時追隨者可能落後領導者幾分鐘甚至更久，例如追隨者正從失效中恢復、系統在容量極限附近執行，或節點間網路出現問題。

同步複製的優點是，追隨者保證擁有與領導者一致的最新資料副本。領導者突然失效時，可以確信資料仍可從追隨者取得。缺點是，如果同步追隨者沒有響應——無論因為崩潰、網路故障還是其他原因——寫入就無法繼續。領導者必須阻塞所有寫入，直至同步副本重新可用。

因此，把所有追隨者都設為同步並不現實：任意一個節點停機都會拖垮整個系統。實踐中，資料庫所謂的同步複製，通常是指 一個 追隨者同步，其餘追隨者非同步。如果同步追隨者不可用或過慢，就把某個非同步追隨者切換為同步。這樣可以保證至少有兩個節點持有最新資料：領導者和一個同步追隨者。這種配置有時也稱為 半同步。

有些系統會同步更新 多數 副本（例如含領導者在內的 5 個副本中更新 3 個），其餘少數副本非同步更新。這就是 法定人數 的一個例子，我們會在 “讀寫仲裁” 中進一步討論。採用共識協議自動選舉領導者的系統經常使用多數法定人數，第 10 章 將再次談到這個問題。

有時，基於領導者的複製會配置為完全非同步。如果領導者失效且無法恢復，所有尚未複製到追隨者的寫入都會丟失。也就是說，即使已經向客戶端確認成功，寫入仍不保證持久。不過，完全非同步配置也有一個優點：即使所有追隨者都已落後，領導者仍可繼續處理寫入。

削弱永續性聽起來不像是划算的取捨，但非同步複製依然應用廣泛，尤其是在追隨者很多或分佈於不同地理位置時 9。我們會在 “複製延遲的問題” 中再談這一點。

設定新的副本

有時需要設定新的追隨者，也許是為了增加副本數量，也許是為了替換失效的節點。怎樣才能確保新追隨者拿到領導者資料的準確副本？

簡單地把資料檔案從一個節點複製到另一個節點通常並不夠：客戶端一直在向資料庫寫入，資料始終處於變化之中，普通的檔案複製會在不同時間點讀到資料庫的不同部分，所得結果可能毫無意義。

可以鎖住資料庫，讓磁碟上的檔案保持一致，但這樣資料庫將無法接受寫入，違背了高可用的目標。好在設定追隨者通常不需要停機。從概念上講，其過程如下：

  1. 取得領導者資料庫在某個時刻的一致快照；如果可能，不要鎖住整個資料庫。大多數資料庫都提供這一功能，因為備份同樣需要它。有些情況下需要藉助第三方工具，例如 MySQL 的 Percona XtraBackup。
  2. 把快照複製到新的追隨者節點。
  3. 追隨者連線領導者，請求從快照生成之後發生的所有資料變更。這要求快照與領導者複製日誌中的準確位置相關聯。不同系統對這個位置有不同稱呼：PostgreSQL 稱之為 日誌序列號；MySQL 則有 binlog 位點 和 全域性事務識別符號（GTID）兩套機制。
  4. 追隨者處理完快照之後積壓的資料變更時，就稱它已經 趕上進度。此後，它可以繼續隨時處理領導者產生的資料變更。

設定追隨者的實際步驟因資料庫而異。有些系統完全自動完成這一過程，另一些系統則需要管理員手工執行一套頗為晦澀的多步驟流程。

還可以把複製日誌歸檔到物件儲存；再定期把整個資料庫的快照儲存到物件儲存，就形成了一套很好的資料庫備份與災難恢復方案。建立新追隨者時，步驟 1 和 2 也可以透過從物件儲存下載這些檔案來完成。例如，WAL-G 為 PostgreSQL、MySQL 和 SQL Server 提供了這種功能，Litestream 則為 SQLite 提供了類似功能。

以物件儲存為後端的資料庫

物件儲存不只能用於歸檔。許多資料庫已經開始用 Amazon Web Services S3、Google Cloud Storage、Azure Blob Storage 等物件儲存為線上查詢提供資料。把資料庫資料存入物件儲存有很多好處：

  • 物件儲存比其他雲端儲存方案便宜。雲資料庫因而可以把查詢頻率較低的資料放到成本更低、延遲更高的儲存中，同時用記憶體、SSD 和 NVMe 儲存工作集。
  • 物件儲存還提供多可用區、雙地區或多地區複製，並給出很高的永續性保證；資料庫也由此可以避開跨可用區網路費用。
  • 資料庫可以利用物件儲存的 條件寫入 功能——本質上是一種 比較並設定（CAS）操作——來實現事務和領導者選舉 10 11。
  • 把多個數據庫的資料放在同一物件儲存中，可以簡化資料整合，尤其是在使用 Apache Parquet、Apache Iceberg 等開放格式時。

這些好處把事務、領導者選舉和複製的責任轉交給物件儲存，從而大幅簡化資料庫架構。

以物件儲存實現複製的系統也必須面對一些權衡。尤其是，物件儲存的讀寫延遲遠高於本地磁碟或 EBS 之類的虛擬塊裝置。許多雲服務商還按 API 呼叫次數收費，迫使系統把讀寫合併成批次以降低成本，而批處理又會進一步增加延遲。此外，許多物件儲存沒有標準的檔案系統介面，未整合物件儲存的系統便無法直接利用它。使用者空間檔案系統（FUSE）等介面允許運維人員把物件儲存桶掛載成檔案系統，應用程式不必知道資料實際位於物件儲存中。然而，許多物件導向儲存的 FUSE 介面並不支援非順序寫入、符號連結等 POSIX 功能，而系統可能依賴這些功能。

不同系統處理這些權衡的方式各不相同。有些採用 分層儲存 架構，把不常訪問的資料放到物件儲存，把新資料或常用資料放在 SSD、NVMe 乃至記憶體等更快的儲存介質上。另一些系統以物件儲存作為主儲存層，但另用 Amazon EBS、Neon Safekeepers 12 等低延遲儲存系統儲存 WAL。近來，一些系統走得更遠，採用 零磁碟架構（ZDA）：所有資料都持久化到物件儲存，磁碟和記憶體只用作快取。節點因此無需儲存持久狀態，運維也大為簡化。WarpStream、Confluent Freight、Buf 的 Bufstream 和 Redpanda Serverless 都是採用零磁碟架構構建的 Kafka 相容系統。幾乎所有現代雲資料倉庫也採用類似架構，向量搜尋引擎 Turbopuffer 和雲原生 LSM 儲存引擎 SlateDB 亦是如此。

處理節點故障

系統中的任何節點都可能停機，既可能是故障意外所致，也可能是計劃內維護，例如重啟機器以安裝核心安全補丁。能夠在服務不中斷的情況下逐個重啟節點，對運維和維護大有裨益。因此，我們的目標是：即使個別節點失效，整個系統仍能繼續執行，並儘可能減小節點停機的影響。

如何用基於領導者的複製實現高可用？

追隨者失效：追趕恢復

每個追隨者都會在本地磁碟上記錄從領導者收到的資料變更。如果追隨者崩潰後重啟，或領導者與追隨者之間的網路暫時中斷，恢復起來相對容易：追隨者可以從日誌中得知故障發生前處理的最後一個事務。它隨後連線領導者，請求自己斷開期間發生的所有資料變更。應用完這些變更後，它便趕上領導者，可以像以前一樣繼續接收資料變更流。

追隨者恢復在概念上很簡單，效能上卻可能很棘手。如果資料庫寫入吞吐量很高，或追隨者離線很久，需要追趕的寫入可能非常多。追趕期間，正在恢復的追隨者和領導者都會承受很高負載——領導者還要把積壓的寫入傳送給追隨者。

所有追隨者確認處理完某段寫入日誌後，領導者便可將其刪除。但如果某個追隨者長時間不可用，領導者必須作出選擇：要麼一直保留日誌，等追隨者恢復並趕上進度，但要冒領導者磁碟空間耗盡的風險；要麼刪除尚未得到該追隨者確認的日誌，這樣追隨者恢復上線後就無法靠日誌追趕，只能從備份恢復。

領導者失效：故障切換

領導者失效處理起來更加棘手：必須把一個追隨者提升為新領導者，重新配置客戶端以便把寫入發給新領導者，並讓其他追隨者開始消費新領導者的資料變更。這個過程稱為 故障切換。

故障切換可以手工完成——通知管理員領導者已經失效，再由管理員執行必要步驟選出新領導者；也可以自動完成。自動故障切換通常包括以下步驟：

  1. 確認領導者失效。 可能出問題的地方很多：崩潰、斷電、網路故障等等。沒有萬無一失的辦法判斷究竟出了什麼問題，因此大多數系統只是使用超時：節點之間頻繁往返傳遞訊息，如果某個節點在一段時間內（例如 30 秒）沒有響應，就認為它已經失效。（因計劃維護而主動下線領導者則不適用這一規則。）
  2. 選擇新的領導者。 可以透過選舉完成（由剩餘副本中的多數選出領導者），也可以由事先指定的 控制器節點 任命 13。最合適的候選者通常是從舊領導者收到資料變更最多、資料最新的副本，這樣可以儘量減少資料損失。讓所有節點就新領導者達成一致是一個共識問題，第 10 章 將詳細討論。
  3. 重新配置系統以使用新領導者。 客戶端現在必須把寫請求發給新領導者（參見 “請求路由”）。如果舊領導者恢復上線，它可能仍以為自己是領導者，沒有意識到其他副本已經迫使它退位。系統必須保證舊領導者轉為追隨者，並承認新領導者。

故障切換過程中有很多地方可能出錯：

  • 如果使用非同步複製，新領導者可能沒有收到舊領導者失效前的全部寫入。選出新領導者後，原領導者若重新加入叢集，那些未複製的寫入該怎麼辦？與此同時，新領導者可能已經收到與之衝突的寫入。最常見的辦法是直接丟棄舊領導者尚未複製的寫入，這意味著你原以為已經提交的寫入其實並未持久儲存。
  • 如果資料庫內容還需要與資料庫之外的儲存系統協調，丟棄寫入尤其危險。例如，GitHub 曾發生過一起事故 14：一個數據過時的 MySQL 追隨者被提升為領導者。資料庫用自增計數器為新行分配主鍵；新領導者的計數器落後於舊領導者，因而重複使用了舊領導者已經分配過的一些主鍵。這些主鍵同時用於 Redis 儲存，主鍵重用造成 MySQL 與 Redis 資料不一致，最終使一些私有資料洩露給了錯誤的使用者。
  • 在某些故障場景下（見 第 9 章），可能有兩個節點都認為自己是領導者。這種情況稱為 腦裂，非常危險：如果兩個領導者都接受寫入，而系統又沒有衝突解決流程（參見 “多主複製”），資料很可能丟失或損壞。有些系統設有保險機制，一旦發現兩個領導者便關閉其中一個節點；但機制設計不當時，也可能把兩個節點都關閉 15。而且，等系統發現腦裂並關閉舊節點時，可能已經為時過晚，資料早已損壞。
  • 宣佈領導者失效前，超時應該設為多長？超時越長，領導者確實失效時恢復所需的時間就越長；超時太短，又容易觸發不必要的故障切換。例如，短暫的負載尖峰可能使節點響應時間超過超時值，網路抖動也可能延遲資料包。如果系統已經飽受高負載或網路問題困擾，不必要的故障切換隻會讓情況更糟。

Note

透過限制或關閉舊領導者來防止腦裂，稱為 柵欄（fencing），更形象的說法是 爆彼之頭（Shoot The Other Node In The Head，STONITH）。“分散式鎖和租約” 將更詳細地討論柵欄機制。

這些問題沒有簡單的解決方案。因此，即使軟體支援自動故障切換，一些運維團隊還是更願意手工執行。

故障切換最重要的是選出一個數據最新的追隨者作為新領導者。採用同步或半同步複製時，應選擇舊領導者確認寫入前所等待的那個追隨者；採用非同步複製時，則可以選擇日誌序列號最大的追隨者。這樣能儘量減少故障切換時的資料損失：丟失幾分之一秒內的寫入或許尚可容忍，選中一個落後數天的追隨者卻可能是災難性的。

節點失效、不可靠的網路，以及圍繞副本一致性、永續性、可用性和延遲所作的權衡，都是分散式系統中的根本問題。第 9 章 和 第 10 章 將進一步深入討論。

複製日誌的實現

基於領導者的複製在底層究竟如何工作？實踐中採用了幾種不同的複製方式，下面逐一簡要介紹。

基於語句的複製

最簡單的情況下，領導者會記錄自己執行的每個寫入請求（即 語句），並把這份語句日誌傳送給追隨者。對於關係資料庫，這意味著每條 INSERT、UPDATE 或 DELETE 語句都會轉發給追隨者；每個追隨者解析並執行這條 SQL 語句，就像它直接來自客戶端一樣。

雖然聽起來很合理，但這種複製方式有許多可能出錯的地方：

  • 任何呼叫非確定性函式的語句，都可能在各副本上產生不同的值，例如用 NOW() 取得當前日期和時間，或用 RAND() 取得隨機數。
  • 如果語句使用自增列，或依賴資料庫中的現有資料（例如 UPDATE …​ WHERE <some condition>），就必須在每個副本上按完全相同的順序執行，否則可能產生不同結果。有多個事務併發執行時，這會成為限制。
  • 帶有副作用的語句（例如觸發器、儲存過程、使用者定義函式），可能在各副本上產生不同的副作用，除非這些副作用完全確定。

這些問題可以繞開。例如，領導者在記錄語句時，可以用固定的返回值替換非確定性函式呼叫，從而讓所有追隨者得到相同的值。按固定順序執行確定性語句，與 “事件溯源與 CQRS” 中介紹的事件溯源模型很相似。這種方法也稱為 狀態機複製；“使用共享日誌” 將討論其理論基礎。

MySQL 5.1 以前使用基於語句的複製。由於日誌相當緊湊，如今有時仍會採用這種方式；不過預設情況下，只要語句中存在任何非確定性，MySQL 就會切換到稍後介紹的基於行的複製。VoltDB 也採用基於語句的複製，並要求事務必須是確定性的，以保證安全 16。然而，實踐中很難確保確定性，因此許多資料庫更傾向於其他複製方式。

預寫日誌（WAL）傳輸

我們在 第 4 章 中看到，B 樹儲存引擎需要預寫日誌才能可靠工作：每次修改都先寫入 WAL，以便崩潰後把樹恢復到一致狀態。WAL 包含把索引和堆恢復到一致狀態所需的全部資訊，因此同一份日誌也能用來在另一個節點上建立副本：領導者除了把日誌寫入磁碟，還透過網路把它傳送給追隨者。追隨者處理日誌後，就會構建出與領導者完全相同的檔案副本。

PostgreSQL、Oracle 等資料庫採用這種複製方式 17 18。其主要缺點是，日誌在非常低的層次描述資料：WAL 記錄了哪個磁碟塊中的哪些位元組發生變化。因此，複製與儲存引擎緊密耦合。資料庫從一個版本升級到另一個版本、儲存格式隨之改變時，通常無法在領導者和追隨者上執行不同版本的資料庫軟體。

這看起來只是一個微不足道的實現細節，卻可能給運維帶來巨大影響。如果複製協議允許追隨者執行比領導者更新的軟體版本，就可以先升級追隨者，再執行故障切換，讓一個升級後的節點成為新領導者，從而實現資料庫軟體的零停機升級。如果複製協議不允許版本不一致——WAL 傳輸往往如此——這類升級就需要停機。

邏輯（基於行）日誌複製

另一種方法是讓複製和儲存引擎使用不同的日誌格式，從而使複製日誌與儲存引擎的內部實現解耦。這種複製日誌稱為 邏輯日誌，以區別於儲存引擎的（物理）資料表示。

關係資料庫的邏輯日誌通常由一系列記錄組成，以行的粒度描述對資料庫表的寫入：

  • 插入一行時，日誌包含所有列的新值。
  • 刪除一行時，日誌包含足以唯一標識被刪行的資訊，通常是主鍵；如果表沒有主鍵，則需要記錄所有列的舊值。
  • 更新一行時，日誌包含足以唯一標識被更新行的資訊，以及所有列的新值（或者至少包含所有發生變化的列的新值）。

修改多行的事務會生成多條這樣的日誌記錄，隨後再跟一條表示事務已經提交的記錄。MySQL 配置為基於行的複製時，除了 WAL 之外，還會維護一份稱為 binlog 的獨立邏輯複製日誌。PostgreSQL 則把物理 WAL 解碼成行插入、更新和刪除事件，以實現邏輯複製 19。

由於邏輯日誌與儲存引擎的內部實現解耦，更容易保持向後相容，因而領導者與追隨者可以執行不同版本的資料庫軟體，也就能以極少的停機時間升級到新版本 20。

邏輯日誌格式也更容易由外部應用程式解析。如果要把資料庫內容傳送到外部系統，例如送入資料倉庫做離線分析，或構建自定義索引和快取 21，這一點會很有用。這種技術稱為 變更資料捕獲，我們會在 “變更資料捕獲” 中再次談到它。

複製延遲的問題

容忍節點失效只是使用複製的一個原因。正如 “分散式與單節點系統” 中提到的，其他原因還包括可伸縮性（處理單臺機器無法承受的請求量）和延遲（把副本放在地理上更靠近使用者的位置）。

基於領導者的複製要求所有寫入經過一個節點，但只讀查詢可以發往任意副本。對於讀多寫少的工作負載——線上服務往往如此——有一種很有吸引力的方案：建立許多追隨者，把讀請求分散到這些追隨者上。這樣既能減輕領導者的負載，也能由附近的副本處理讀請求。

在這種 讀擴充套件 架構中，只需增加追隨者，便可提高只讀請求的處理能力。不過，這種辦法實際上只適用於非同步複製。如果嘗試同步複製到所有追隨者，任意一個節點失效或網路中斷都會讓整個系統無法寫入。節點越多，越可能有某個節點停機，因此完全同步的配置會極不可靠。

不幸的是，應用程式從 非同步 追隨者讀取時，如果追隨者落後，就可能看到過時的資訊。資料庫於是顯得不一致：同時在領導者和追隨者上執行同一查詢，結果可能不同，因為追隨者尚未反映所有寫入。這種不一致只是暫時的——如果停止寫入並等待一段時間，追隨者最終會趕上領導者，恢復一致。因此，這種現象稱為 最終一致性 22。

Note

最終一致性 一詞由 Douglas Terry 等人提出 23，經 Werner Vogels 推廣 24，後來成了許多 NoSQL 專案的口號。不過，最終一致性並非 NoSQL 資料庫獨有：關係資料庫採用非同步複製時，其追隨者也有相同特性。

“最終”一詞有意保持模糊：一般而言，副本能落後多久並沒有上限。正常執行時，從寫入發生在領導者上，到變更反映在追隨者上，兩者之間的延遲——即 複製延遲——可能只有幾分之一秒，在實踐中難以察覺。但當系統在容量極限附近執行或網路出現問題時，延遲很容易增至幾秒甚至幾分鐘。

延遲一旦大到這種程度，由此造成的不一致就不再只是理論問題，而會成為應用程式面臨的真實問題。本節將重點介紹複製延遲容易引發的三類問題，並概述一些解決辦法。

讀己之寫

許多應用程式允許使用者提交資料，隨後檢視自己提交的內容。它可能是客戶資料庫中的一條記錄、討論主題下的一條評論，或其他類似內容。新資料必須寫入領導者，但使用者檢視時可以從追隨者讀取。如果資料經常讀取、很少寫入，這種做法尤其合適。

非同步複製在這裡會產生問題，如 圖 6-3 所示：使用者剛寫入資料不久便檢視它時，新資料可能尚未到達該副本。在使用者看來，自己剛剛提交的資料彷彿丟失了，當然會感到不滿。

圖 6-3. 使用者寫入後，又從陳舊副本讀取。要防止這種異常，需要寫後讀一致性。

這種情況下需要 寫後讀一致性，也稱 讀己之寫一致性 23。它保證使用者重新載入頁面時，總能看到自己提交的更新。至於其他使用者則不作保證：他們的更新可能過一段時間才會出現。但至少使用者可以確信，自己的輸入已經正確儲存。

如何在基於領導者的複製系統中實現寫後讀一致性？有多種辦法，例如：

  • 讀取使用者可能修改過的內容時，從領導者或同步更新的追隨者讀取；其他內容則從非同步更新的追隨者讀取。這要求系統無需實際查詢，就能判斷某項內容是否可能被修改。例如，社交網路中的個人資料通常只能由本人編輯。因此可以制定一條簡單規則：使用者自己的資料總是從領導者讀取，其他使用者的資料則從追隨者讀取。
  • 如果應用程式中的大部分內容都可能由使用者編輯，上述辦法就沒有效果，因為幾乎所有內容都得從領導者讀取，讀擴充套件也就失去了意義。這時可以採用其他標準來決定是否從領導者讀取。例如，記錄最近一次更新時間，此後一分鐘內的所有讀取都發往領導者 25。也可以監控追隨者的複製延遲，不向落後領導者超過一分鐘的追隨者傳送查詢。
  • 客戶端可以記住自己最近一次寫入的時間戳，系統再確保為該使用者處理讀取的副本至少已經反映到這個時間戳。如果副本不夠新，就換一個副本處理讀取，或讓查詢等待該副本趕上進度 26。這個時間戳既可以是 邏輯時間戳（例如表示寫入順序的日誌序列號），也可以來自實際的系統時鐘；後一種情況下，時鐘必須準確同步，參見 “不可靠的時鐘”。
  • 如果副本分佈於多個地區（為了靠近使用者或提高可用性），還會增加一層複雜性：凡是必須由領導者處理的請求，都要路由到領導者所在的地區。

同一使用者透過多個裝置訪問服務時，例如同時使用桌面瀏覽器和移動應用，還會出現另一種複雜情況。這時可能需要提供 跨裝置 寫後讀一致性：使用者在一臺裝置上輸入資訊，隨後在另一臺裝置上檢視時，應當看到剛才輸入的內容。

還需要考慮以下問題：

  • 依賴“記住使用者最近一次更新時間戳”的方法會變得更難，因為一臺裝置上執行的程式碼不知道另一臺裝置做了哪些更新。這些元資料需要集中儲存。
  • 如果副本分佈在不同地區，來自不同裝置的連線不保證會路由到同一地區。例如，使用者的桌上型電腦使用家庭寬頻，手機使用蜂窩網路，兩臺裝置的網路路徑可能完全不同。如果方案要求從領導者讀取，可能首先要把該使用者所有裝置發出的請求都路由到同一地區。

地區與可用區

本書用 地區（region）表示同一地理位置上的一個或多個數據中心。雲服務商通常會在同一地理區域設定多個數據中心，每個資料中心稱為一個 可用區（availability zone），簡稱 區（zone）。因此，一個雲地區由多個可用區組成。每個可用區都是位於獨立物理設施中的資料中心，有自己的供電、製冷等基礎設施。

同一地區內的可用區之間由高速網路連線，延遲足夠低，因此大多數分散式系統可以把節點分散在多個可用區執行，就像它們位於同一個區一樣。多可用區配置可以抵禦某個可用區整體下線，卻無法抵禦一個地區內所有可用區均不可用的地區級中斷。要在地區級中斷時繼續執行，分散式系統必須跨多個地區部署，而這可能帶來更高延遲、更低吞吐量和更高的雲網絡費用。我們將在 “多主複製拓撲” 中進一步討論這些權衡。這裡暫且記住：本書所說的地區，是同一地理位置上的一組可用區或資料中心。

單調讀

從非同步追隨者讀取時可能發生的第二種異常，是使用者可能會看到 時光倒流。

使用者連續幾次從不同副本讀取時，就可能發生這種情況。例如，圖 6-4 中，使用者 2345 連續執行兩次相同查詢：第一次查詢複製延遲較小的追隨者，第二次查詢延遲更大的追隨者。（使用者重新整理網頁、而每個請求被隨機路由到不同伺服器時，這種場景很容易出現。）第一次查詢返回了使用者 1234 最近新增的評論，第二次卻什麼也沒返回，因為落後的追隨者還沒有收到這次寫入。實際上，第二次查詢觀察到的系統狀態比第一次更早。如果第一次查詢本就沒有結果，倒也問題不大，因為使用者 2345 多半不知道使用者 1234 剛剛新增過評論；但如果評論先出現又消失，就非常令人困惑。

圖 6-4. 使用者先從較新的副本讀取，隨後從陳舊副本讀取，時間彷彿倒退了。要防止這種異常，需要單調讀。

單調讀 22 保證這種異常不會發生。它弱於強一致性，卻強於最終一致性。讀取資料時仍可能看到舊值；單調讀只保證同一使用者順序執行多次讀取時，不會看到時間倒退——一旦讀到較新的資料，以後就不會再讀到更舊的資料。

實現單調讀的一種辦法，是確保每個使用者始終從同一個副本讀取（不同使用者可以選擇不同副本）。例如，可以根據使用者 ID 的雜湊選擇副本，而不是隨機選擇。如果該副本失效，則需要把使用者的查詢重新路由到其他副本。

一致字首讀

第三種複製延遲異常違反了因果關係。設想 Poons 先生和 Cake 夫人有下面這段簡短對話：

Poons 先生
Cake 夫人，你能看到多遠的未來？
Cake 夫人
通常大約十秒鐘，Poons 先生。

這兩句話之間存在因果依賴：Cake 夫人聽到 Poons 先生的問題，然後作出回答。

現在設想第三個人透過追隨者旁聽這段對話。Cake 夫人的話經過複製延遲較小的追隨者，Poons 先生的話經過延遲更大的追隨者（見 圖 6-5）。於是，這位旁聽者會聽到：

Cake 夫人
通常大約十秒鐘，Poons 先生。
Poons 先生
Cake 夫人，你能看到多遠的未來？

在旁聽者看來，Cake 夫人還沒聽到 Poons 先生提問，就已經回答了問題。這種通靈能力令人印象深刻，卻也十分費解 27。

圖 6-5. 如果某些分片的複製速度慢於其他分片，觀察者可能先看到答案，後看到問題。

防止這種異常需要另一種保證：一致字首讀 22。它保證，如果一系列寫入按某個順序發生，那麼任何人讀取這些寫入時，也會看到它們以相同順序出現。

這在分片（分割槽）資料庫中尤其容易成為問題，我們將在 第 7 章 討論這類資料庫。如果資料庫始終按相同順序應用寫入，讀取就總會看到一致字首，這種異常也不會發生。然而，在許多分散式資料庫中，不同分片彼此獨立執行，沒有全域性寫入順序。使用者讀取資料庫時，可能看到一部分處於較舊狀態，另一部分卻處於較新狀態。

一種解決辦法是確保存在因果關係的寫入落在同一個分片，但有些應用程式無法高效做到這一點。還有一些演算法會顯式跟蹤因果依賴，我們會在 “先發生”關係與併發 中再次討論。

複製延遲的解決方案

使用最終一致的系統時，值得認真考慮：如果複製延遲增加到幾分鐘甚至幾小時，應用程式會怎樣表現？如果答案是“沒有影響”，那當然很好；如果會給使用者帶來糟糕體驗，就必須把系統設計成能夠提供寫後讀之類的更強保證。複製本來是非同步的，卻假裝它是同步的，遲早會釀成問題。

如前所述，應用程式可以提供比底層資料庫更強的保證，例如把某些讀取發往領導者或同步更新的追隨者。不過，在應用程式程式碼中處理這些問題既複雜又容易出錯。

對應用程式開發者而言，最簡單的程式設計模型，是選擇一個能為副本提供強一致性保證（例如線性一致性，見 第 10 章）和 ACID 事務（見 第 8 章）的資料庫。這樣就可以基本忽略複製帶來的挑戰，把資料庫看作只有一個節點。2010 年代初興起的 NoSQL 運動曾宣揚一種觀點：這些特性會限制可伸縮性，大規模系統不得不接受最終一致性。

此後，許多資料庫開始在提供強一致性和事務的同時，保留分散式資料庫在容錯、高可用和可伸縮性方面的優勢。正如 “關係模型與文件模型” 中提到的，為與 NoSQL 區分，這一趨勢稱為 NewSQL（儘管重點並不在 SQL 本身，而在可伸縮事務管理的新方法）。

如今雖已有可伸縮的強一致分散式資料庫，一些應用程式仍有充分理由選擇一致性保證較弱的其他複製方式：面對網路中斷時，它們的韌性可能更強，開銷也低於事務型系統。本章餘下部分將繼續探討這些方法。

多主複製

到目前為止，本章只討論了使用單個領導者的複製架構。雖然這是常見做法，但還有一些值得關注的選擇。

單主複製有一個主要缺點：所有寫入都必須經過唯一的領導者。無論出於什麼原因，只要連線不上領導者——例如客戶端與領導者之間的網路中斷——就無法寫入資料庫。

單主複製模型可以自然地擴充套件為允許多個節點接受寫入。複製仍以同樣方式進行：每個處理寫入的節點都必須把資料變更轉發給其他所有節點。我們把這種配置稱為 多主複製，也稱 主動/主動複製 或 雙向複製。在這種配置中，每個領導者同時也是其他領導者的追隨者。

與單主複製一樣，多主複製也可以選擇同步或非同步。假設有兩個領導者 A 和 B，現在要向 A 寫入。如果寫入必須從 A 同步複製到 B，那麼兩者之間的網路一旦中斷，在網路恢復前就無法向 A 寫入。這種同步多主複製提供的模型與單主複製極為相似：也就是說，這等同於把 B 設為領導者，由 A 把所有寫請求轉發給 B 執行。

因此，本節不再深入討論同步多主複製，而把它視為等同於單主複製。以下討論集中於非同步多主複製：即使某個領導者與其他領導者之間的連線中斷，它仍可處理寫入。

跨地域執行

在單個地區內使用多主配置通常沒有多少意義，因為所得好處很少能抵消額外的複雜性。不過，在某些場景中，這種配置確實合理。

設想一個數據庫在多個地區都有副本，也許是為了在整個地區失效時仍能執行，也許是為了在地理上更接近使用者。這種部署稱為 地理分散式、跨地域分散式 或 跨地域複製。採用單主複製時，領導者必須位於其中 一個 地區，所有寫入都要經過該地區。

在多主配置中，每個 地區都可以有一個領導者。圖 6-6 展示了這種架構：每個地區內部使用常規的領導者—追隨者複製（追隨者可以位於與領導者不同的可用區）；地區之間，則由各地區的領導者把變更復制給其他地區的領導者。

圖 6-6. 跨多個地區的多主複製。

下面比較單主與多主配置在多地區部署中的表現：

效能
在單主配置中，每次寫入都必須透過網際網路發往領導者所在的地區。這可能顯著增加寫入延遲，甚至違背多地區部署的初衷。在多主配置中，每次寫入都能在本地地區處理，再非同步複製到其他地區。地區間的網路延遲因而對使用者不可見，感知到的效能可能更好。
容忍地區停機
在單主配置中，如果領導者所在的地區不可用，可以透過故障切換把另一個地區的追隨者提升為領導者。在多主配置中，各地區可以彼此獨立地繼續執行；離線地區恢復上線後，複製會趕上進度。
容忍網路問題
即使地區之間使用專用連線，其流量也可能不如同一地區內不同可用區之間、或同一可用區內部的流量可靠。單主配置對地區間鏈路的問題極為敏感：一個地區的客戶端要向另一個地區的領導者寫入，就必須透過這條鏈路發出請求，並等待響應後才能完成操作。

非同步複製的多主配置更能容忍網路問題：網路暫時中斷期間，每個地區的領導者仍可獨立處理寫入。

一致性
單主系統可以提供可序列化事務等強一致性保證，我們會在 第 8 章 討論。多主系統最大的缺點，是它所能提供的一致性要弱得多。例如，無法保證銀行賬戶餘額不會變成負數，也無法保證使用者名稱唯一：不同領導者完全可能分別處理單獨看來合法的寫入（從賬戶支付一筆錢、註冊某個使用者名稱），但把它們與另一個領導者上的寫入合在一起，就違反了約束。

這是分散式系統的一項根本限制 28。如果必須強制執行這類約束，最好採用單主系統。不過，正如 “處理寫入衝突” 中將要看到的，對於不需要這類約束的大量應用程式，多主系統仍能提供有用的一致性屬性。

多主複製不如單主複製常見，但 MySQL、Oracle、SQL Server、YugabyteDB 等許多資料庫仍提供支援。有時它以外部附加元件的形式出現，例如 Redis Enterprise、EDB Postgres Distributed 和 pglogical 29。

許多資料庫的多主複製都是後來加裝的功能，因而常有細微的配置陷阱，也會與其他資料庫功能產生出人意料的相互作用。例如，自增鍵、觸發器和完整性約束都可能帶來問題。因此，多主複製往往被視為應當儘量避開的危險領域 30。

多主複製拓撲

複製拓撲 描述寫入從一個節點傳播到另一個節點時所經過的通訊路徑。如果只有兩個領導者，如 圖 6-9 所示，那麼只有一種合理的拓撲：領導者 1 必須把所有寫入傳送給領導者 2，反之亦然。領導者超過兩個時，則有多種拓撲可供選擇。圖 6-7 給出了三個例子。

圖 6-7. 多主複製可以採用的三種拓撲示例。

最通用的是 圖 6-7(c) 所示的 全對全 拓撲，每個領導者都會把寫入傳送給其他所有領導者。不過，實際系統也會採用限制更多的拓撲。例如在 環形拓撲 中，每個節點從一個節點接收寫入，再把這些寫入連同自己的寫入轉發給另一個節點。另一種常見拓撲呈 星形：指定一個根節點，由它把寫入轉發給所有其他節點。星形拓撲還可以推廣成樹形。

Note

不要把星形網路拓撲與 星型模式 混為一談；後者描述的是資料模型結構，參見 “星型與雪花型：分析模式”。

在環形和星形拓撲中，一次寫入可能要經過多個節點才能到達所有副本。因此，節點必須轉發從其他節點收到的資料變更。為避免無限複製迴圈，每個節點都有唯一識別符號；複製日誌中的每次寫入都會標記自己經過的全部節點 31。節點收到帶有自身識別符號的資料變更時，會直接忽略它，因為這說明自己已經處理過該變更。

不同拓撲的問題

環形和星形拓撲有一個問題：只要一個節點失效，就可能中斷其他節點之間的複製訊息流；在該節點修復前，其他節點無法相互通訊。雖然可以重配拓撲以繞過失效節點，但大多數部署都需要手工完成這一操作。連線更密集的拓撲（例如全對全）容錯性更好，因為訊息可以沿不同路徑傳播，避開單點故障。

另一方面，全對全拓撲也有問題。尤其是，不同網路鏈路的速度可能不同（例如受到網路擁塞影響），導致某些複製訊息“超越”另一些訊息，如 圖 6-8 所示。

圖 6-8. 在多主複製中，寫入抵達某些副本的順序可能有誤。

在 圖 6-8 中，客戶端 A 在領導者 1 上向表中插入一行，客戶端 B 隨後在領導者 3 上更新該行。但領導者 2 可能以相反順序收到這兩次寫入：先收到更新（在它看來，這是要更新資料庫中並不存在的行），稍後才收到本應先發生的插入。

這也是一個因果關係問題，與 “一致字首讀” 中看到的情況相似。更新依賴先前的插入，因此必須保證所有節點先處理插入，再處理更新。僅僅給每次寫入附加時間戳並不夠，因為不能相信各節點的時鐘同步得足以讓領導者 2 正確排列這些事件（見 第 9 章）。

要正確排列這些事件，可以採用本章稍後介紹的 版本向量（見 “檢測併發寫入”）。不過，許多多主複製系統並未使用可靠的更新排序技術，因而容易遇到 圖 6-8 所示的問題。如果使用多主複製，應當瞭解這些風險，仔細閱讀文件，並充分測試資料庫，確認它確實提供了你以為它會提供的保證。

同步引擎與本地優先軟體

應用程式需要在斷網時繼續工作，是另一個適合多主複製的場景。

以手機、膝上型電腦和其他裝置上的日曆應用為例。無論裝置有沒有聯網，你都需要隨時檢視會議（發出讀請求）和新增會議（發出寫請求）。離線期間所作的變更，應在裝置下次上線時與伺服器及其他裝置同步。

這種情況下，每臺裝置都有一個充當領導者的本地資料庫副本，可以接受寫入；各裝置上的日曆副本之間則透過非同步多主複製過程進行同步。複製延遲可能長達數小時甚至數天，取決於裝置何時重新聯網。

從架構上看，這種配置相當於把地區間多主複製推到極致：每臺裝置都是一個“地區”，它們之間的網路連線極不可靠。

實時協作、離線優先和本地優先應用

此外，許多現代 Web 應用還提供 實時協作 功能，例如用於文件和電子表格的 Google Docs 與 Sheets、用於圖形設計的 Figma，以及用於專案管理的 Linear。這些應用之所以響應迅速，是因為使用者輸入會立即反映在介面上，無需等待與伺服器的一次網路往返；一位使用者所作的編輯也會以很低的延遲呈現給協作者 32 33 34。

這同樣形成了多主架構：每個開啟共享檔案的瀏覽器標籤頁都是一個副本，對檔案所作的更新會非同步複製到其他開啟該檔案的使用者裝置上。即使應用程式不支援離線編輯，只要多個使用者可以不等伺服器響應便各自編輯，它就已經是多主系統。

離線編輯與實時協作需要相似的複製基礎設施：應用程式必須捕獲使用者對檔案作出的所有變更，線上時立即發給協作者，離線時則先儲存在本地，稍後再發送。同時，應用程式還要接收協作者的變更，將其合併到使用者的本地檔案副本，並更新介面以顯示最新版本。多個使用者併發修改檔案時，還可能需要用衝突解決邏輯合併這些變更。

支援這一過程的軟體庫稱為 同步引擎。這個想法由來已久，但“同步引擎”一詞近來才受到關注 35 36 37。允許使用者離線時繼續編輯檔案的應用程式稱為 離線優先 應用 38，它可以用同步引擎來實現。本地優先軟體 則不僅要支援離線優先，還要保證即使軟體開發者關閉所有線上服務，協作應用仍能繼續工作 39。一種實現方式是採用開放標準的同步協議，並讓多個服務提供商都能支援這一協議 40。例如，Git 就是本地優先的協作系統（雖然它不支援實時協作），因為可以透過 GitHub、GitLab 或其他任意程式碼倉庫託管服務進行同步。

同步引擎的利弊

如今構建 Web 應用的主流方式，是讓客戶端只保留極少的持久狀態；每當需要顯示新資料或更新資料時，就向伺服器發出請求。使用同步引擎時則相反：客戶端持有持久狀態，與伺服器的通訊移到後臺進行。這種方式有多項優點：

  • 資料在本地，使用者介面的響應速度可以遠快於等待服務呼叫返回資料。有些應用追求在圖形系統的 下一幀 響應使用者輸入：對於重新整理率為 60 Hz 的顯示器，這意味著要在 16 毫秒內完成渲染。
  • 允許使用者離線工作很有價值，尤其是在連線時斷時續的移動裝置上。使用同步引擎後，應用程式無需另設離線模式：離線不過是網路延遲變得非常大。
  • 與在應用程式碼中顯式呼叫服務相比，同步引擎簡化了前端應用的程式設計模型。正如 “遠端過程呼叫（RPC）的問題” 中所述，每次服務呼叫都要處理錯誤。例如，更新伺服器資料的請求失敗後，使用者介面必須以某種方式反映錯誤。同步引擎讓應用直接讀寫幾乎不會失敗的本地資料，從而形成更具宣告性的程式設計風格 41。
  • 要實時顯示其他使用者所作的編輯，需要接收變更通知，並據此高效更新使用者介面。同步引擎與 響應式程式設計 模型結合，是實現這一功能的好辦法 42。

如果能事先下載使用者可能需要的全部資料，並持久儲存在客戶端，同步引擎的效果最好。這樣一來，需要時就能離線訪問；但也意味著，如果使用者可以訪問的資料量非常大，同步引擎便不適用。例如，下載使用者自己建立的全部檔案通常沒問題（單個使用者一般不會產生那麼多資料），下載一個電子商務網站的全部商品目錄則多半不合理。

Lotus Notes 在 20 世紀 80 年代率先採用了同步引擎的思想 43，儘管當時並未使用這個名稱；日曆等特定應用的同步功能也已存在多年。如今有不少通用同步引擎，其中一些依賴專有後端服務，例如 Google Firestore、Realm 或 Ditto；另一些提供開源後端，適合構建本地優先軟體，例如 PouchDB/CouchDB、Automerge 或 Yjs。

多人影片遊戲也需要立即響應玩家的本地操作，再與透過網路非同步收到的其他玩家操作協調。在遊戲開發術語中，與同步引擎對應的部分稱為 網路程式碼（netcode）。網路程式碼所用的技術針對遊戲需求高度定製 44，無法直接移植到其他軟體，因此本書不再展開。

處理寫入衝突

多主複製最大的難題——無論是地理分散式的服務端資料庫，還是終端使用者裝置上的本地優先同步引擎——都是不同領導者上的併發寫入可能彼此衝突，需要解決。

例如，圖 6-9 展示了兩個使用者同時編輯一個維基頁面。使用者 1 把頁面標題從 A 改為 B，使用者 2 則獨立地把標題從 A 改為 C。兩位使用者的變更都成功應用到各自的本地領導者，但非同步複製這些變更時，系統發現了衝突。單主資料庫不會遇到這個問題。

圖 6-9. 兩個領導者併發更新同一條記錄，造成寫入衝突。

Note

我們稱 圖 6-9 中的兩次寫入為 併發寫入，因為最初執行寫入時，兩者都不知道對方。它們在物理時間上是否真的同時發生並不重要；如果寫入發生在離線期間，兩者甚至可能相隔很久。真正重要的是，一次寫入發生時，另一次寫入是否已經生效。

我們會在 “檢測併發寫入” 中討論資料庫如何判斷兩次寫入是否併發。現在先假定衝突已經能夠檢測，接下來考慮怎樣解決才最合適。

衝突避免

一種策略是從一開始就避免衝突。例如，如果應用程式能確保某條記錄的所有寫入都經過同一個領導者，那麼即使整個資料庫採用多主複製，也不會產生衝突。同步引擎客戶端離線更新時無法使用這種辦法，但在跨地域複製的服務端系統中有時可行 30。

例如，在使用者只能編輯自己資料的應用程式中，可以保證某位使用者的請求總是路由到同一個地區，並使用該地區的領導者讀寫。不同使用者可以有不同的“主”地區（也許根據與使用者的地理距離來選擇），但從任一使用者的角度看，本質上仍是單主配置。

不過，有時需要改變某條記錄的指定領導者：可能是一個地區不可用，必須把流量改送另一個地區；也可能是使用者搬到了別處，現在離另一個地區更近。如果使用者恰好在指定領導者切換期間執行寫入，就可能發生衝突，必須用下面某種方法解決。因此，只要允許改變領導者，衝突避免就可能失效。

再舉一個衝突避免的例子。假設要插入新記錄，並用自增計數器生成唯一 ID。系統有兩個領導者時，可以讓一個只生成奇數，另一個只生成偶數。這樣兩個領導者便不會併發地把同一個 ID 分配給不同記錄。“ID 生成器和邏輯時鐘” 將討論其他 ID 分配方案。

最後寫入者勝（丟棄併發寫入）

如果無法避免衝突，最簡單的解決辦法是給每次寫入附加時間戳，並始終採用時間戳最大的值。例如在 圖 6-9 中，假設使用者 1 寫入的時間戳大於使用者 2。兩個領導者都會判定頁面的新標題應為 B，並丟棄把標題設為 C 的寫入。如果兩次寫入碰巧擁有相同時間戳，還可以比較值來決定勝者（例如字串可以選擇字母順序在前的值）。

這種方法稱為 最後寫入者勝（last write wins，LWW），因為時間戳最大的寫入被視為“最後”一次寫入。不過，這個名稱容易誤導：當兩次寫入像 圖 6-9 中那樣併發時，根本無從定義哪次較早、哪次較晚，因此併發寫入的時間戳順序實質上是隨機的。

所以，LWW 的真正含義是：同一條記錄在不同領導者上併發寫入時，隨機挑選其中一次作為勝者，其他寫入則靜默丟棄，即使它們都已在各自的領導者上成功處理。這樣固然能讓所有副本最終收斂到一致狀態，代價卻是資料丟失。

如果能夠避免衝突——例如只插入以 UUID 等唯一鍵標識的記錄，而且從不更新——LWW 就沒有問題。但如果要更新現有記錄，或不同領導者可能插入鍵相同的記錄，就必須判斷丟失更新對應用程式是否可以接受。不能接受時，應採用下面介紹的其他衝突解決方式。

LWW 還有一個問題：如果寫入時間戳來自實時時鐘（例如 Unix 時間戳），系統會對時鐘同步極為敏感。假如一個節點的時鐘快於其他節點，再嘗試覆蓋該節點寫入的值時，新寫入的時間戳可能反而更小，因而被忽略，儘管它顯然發生得更晚。使用 邏輯時鐘 可以解決這個問題，參見 “ID 生成器和邏輯時鐘”。

手動衝突解決

如果不願隨機丟棄某些寫入，下一個選擇是手工解決衝突。你可能熟悉 Git 等版本控制系統中的做法：兩個分支上的提交修改了同一檔案的同一行，合併分支時就會產生合併衝突，必須先解決衝突才能完成合並。

在資料庫中，讓一次衝突阻塞整個複製過程，直到有人解決，顯然並不現實。資料庫通常會儲存一條記錄的所有併發寫入值——例如 圖 6-9 中的 B 和 C。這些值有時稱為 兄弟值。下次查詢該記錄時，資料庫返回 全部 值，而不只是最新的一個。隨後可以任意選擇解決辦法：在應用程式碼中自動處理（例如把 B 與 C 拼成“B/C”），或詢問使用者；最後再向資料庫寫回一個新值，消解衝突。

CouchDB 等系統採用這種衝突解決方式，但它也有不少問題：

  • 資料庫 API 會發生變化。例如，維基頁面標題原本只是字串，現在卻變成一組字串；通常只有一個元素，發生衝突時卻可能有多個。應用程式碼處理這種資料會相當彆扭。
  • 讓使用者手工合併兄弟值，無論對應用開發者還是使用者都是沉重負擔：開發者必須製作衝突解決介面，使用者則可能不明白自己為什麼要做這件事、又該做什麼。很多情況下，自動合併比打擾使用者更合適。
  • 自動合併兄弟值如果不夠謹慎，也會產生意外結果。例如，亞馬遜購物車過去允許併發更新，再把任一兄弟值中出現的所有商品都保留下來，也就是取購物車的並集。如果顧客在一個兄弟值中刪除商品，而另一個兄弟值仍含有該商品，已經刪除的商品便會意外重現 45。圖 6-10 展示了這種情況：裝置 1 刪除 Book，裝置 2 同時刪除 DVD，合併衝突後兩件商品卻都回來了。
  • 如果多個節點同時觀察到衝突並各自解決，解決過程本身還可能引入新衝突，而且各節點給出的結果可能不一致。例如，如果沒有固定排列順序，一個節點可能把 B 和 C 合併成“B/C”，另一個卻合併成“C/B”；再合併“B/C”與“C/B”時，結果可能變成“B/C/C/B”之類的怪東西。
圖 6-10. 亞馬遜購物車異常示例：以並集方式合併購物車衝突時，已刪除的商品可能重新出現。

自動衝突解決

對許多應用程式而言，處理衝突的最佳方式，是用演算法自動把併發寫入合併成一致狀態。自動衝突解決可以保證所有副本 收斂 到同一狀態：只要處理過相同的一組寫入，各副本的狀態就相同，與寫入到達的順序無關。

LWW 是衝突解決演算法的一個簡單例子。針對不同資料型別，人們還開發了更複雜的合併演算法，目標是儘可能保留所有更新的預期效果，從而避免資料丟失：

  • 如果資料是文字（例如維基頁面的標題或正文），可以檢測相鄰版本之間插入或刪除了哪些字元。合併結果會保留任一兄弟值中的所有插入和刪除。如果使用者在同一位置併發插入文字，可以按確定性的順序排列，確保所有節點得到相同結果。
  • 如果資料是元素集合，無論像待辦事項列表一樣有序，還是像購物車一樣無序，都可以像合併文字那樣跟蹤插入和刪除。為避免 圖 6-10 中的購物車異常，演算法會記住 Book 和 DVD 已被刪除，因此合併結果為 Cart = {Soap}。
  • 如果資料是可以遞增或遞減的整數計數器（例如社交媒體帖子的點贊數），合併演算法可以計算各兄弟值上分別發生了多少次遞增和遞減，再正確相加，既不重複計數，也不丟失更新。
  • 如果資料是鍵值對映，可以對同一個鍵下的值採用其他某種衝突解決演算法；不同鍵上的更新則可以彼此獨立地處理。

衝突解決並非無所不能。例如，如果規定一個列表最多包含五個元素，而多位使用者併發新增元素，使總數超過五個，那麼唯一的選擇就是丟掉其中一些。即便如此，自動衝突解決仍足以構建許多實用應用。一旦決定構建可協作的離線優先或本地優先應用，衝突解決就不可避免，而自動化往往是最佳選擇。

CRDT 與操作變換

實現自動衝突解決時，通常使用兩類演算法：無衝突複製資料型別（CRDT）46 和 操作變換（OT）47。二者的設計理念與效能特徵不同，但都能自動合併前面提到的各種資料。

圖 6-11 展示了 OT 和 CRDT 分別如何合併文字的併發更新。假設兩個副本起初都儲存文字“ice”。一個副本在開頭插入字母“n”，得到“nice”；與此同時，另一個副本在末尾插入感嘆號，得到“ice!”。

圖 6-11. OT 與 CRDT 分別如何合併字串中的兩次併發插入。

兩類演算法用不同方式得到合併結果“nice!”：

OT
記錄字元插入或刪除位置的索引：“n”插入索引 0，“!”插入索引 3。然後兩個副本交換操作。在索引 0 插入“n”可以原樣應用；但如果直接在狀態“nice”的索引 3 插入“!”，結果會變成錯誤的“nic!e”。因此，必須根據已經應用的併發操作變換每個操作的索引。這裡，為了計入較小索引處插入的“n”，需要把“!”的插入位置變換為索引 4。
CRDT
大多數 CRDT 不使用索引，而是給每個字元分配唯一且不可變的 ID，再據此確定插入和刪除位置。例如在 圖 6-11 中，“i”的 ID 是 1A，“c”的 ID 是 2A，依此類推。插入感嘆號時，生成的操作既包含新字元的 ID（4B），也包含插入位置之前那個現有字元的 ID（3A）。要插在字串開頭，就把前驅字元 ID 設為“nil”。同一位置的併發插入按字元 ID 排列。這樣無需變換操作，也能保證各副本收斂。

許多演算法都建立在這些思路的不同變體上。列表和陣列可以採用類似方法，把字元換成列表元素；鍵值對映等其他資料型別也很容易加入。OT 與 CRDT 在效能和功能上各有取捨，但也可以把二者的優點結合到同一種演算法中 48。

OT 最常用於文字的實時協作編輯，例如 Google Docs 32；CRDT 則用於 Redis Enterprise、Riak、Azure Cosmos DB 等分散式資料庫 49。面向 JSON 資料的同步引擎既可以用 CRDT 實現（如 Automerge、Yjs），也可以用 OT 實現（如 ShareDB）。

什麼是衝突？

有些衝突顯而易見。在 圖 6-9 的例子中，兩次寫入併發修改同一條記錄的同一個欄位，把它設成兩個不同的值。毫無疑問，這就是衝突。

另一些衝突則更為微妙，不易發現。以會議室預訂系統為例，它記錄哪個房間在什麼時間由哪組人預訂。應用程式必須確保同一時刻每個房間只分配給一組人，也就是說，同一房間的預訂不能重疊。如果兩項不同預訂在同一時間佔用同一房間，就會產生衝突。即使應用程式在允許預訂前檢查空閒情況，只要兩次預訂分別在不同領導者上進行，仍可能發生衝突。

這個問題沒有現成的簡短答案，不過在接下來的章節中，我們會逐步加深理解。第 8 章 將給出更多衝突示例；“排序事件以捕獲因果關係” 則會討論在複製系統中可伸縮地檢測與解決衝突的方法。

無主複製

本章此前討論的單主複製與多主複製，都基於同一個思路：客戶端把寫請求發給某個節點（領導者），再由資料庫系統負責把寫入複製到其他副本。領導者決定處理寫入的順序，追隨者則按相同順序應用領導者的寫入。

另一些資料儲存系統採取了不同辦法：放棄領導者概念，允許任何副本直接接受客戶端寫入。最早的一些複製資料系統採用的就是無主模型 1 50，但在關係資料庫佔據主導地位的年代，這個思路幾乎被遺忘。2007 年，亞馬遜把它用於內部的 Dynamo 系統 45，無主架構由此再度流行。Riak、Cassandra 和 ScyllaDB 都是受 Dynamo 啟發、採用無主複製模型的開源資料儲存，因此這類資料庫也稱為 Dynamo 風格 資料庫。

Note

最初的 Dynamo 系統只在論文中有所描述 45，從未在亞馬遜之外發布。名稱相近的 DynamoDB 是 AWS 後來推出的雲資料庫，但架構完全不同：它採用基於 Multi-Paxos 共識演算法的單主複製 5。

在一些無主實現中，客戶端直接把寫入發給多個副本；另一些實現則由協調者節點代客戶端完成這件事。不過，與有領導者的資料庫不同，協調者不會強制規定寫入順序。我們將看到，這項設計差異會深刻影響資料庫的使用方式。

當節點故障時寫入資料庫

假設一個數據庫有三個副本，其中一個暫時不可用，也許正在重啟以安裝系統更新。在單主配置中，要繼續處理寫入，可能需要執行故障切換（參見 “處理節點故障”）。

無主配置則根本沒有故障切換。圖 6-12 展示了此時的情形：客戶端（使用者 1234）把寫入並行發給三個副本；兩個可用副本接受寫入，不可用副本則錯過了它。假設三個副本中有兩個確認就足以判定寫入成功：使用者 1234 收到兩個 ok 響應後，系統便認為寫入成功，客戶端直接忽略有一個副本漏掉寫入這一事實。

圖 6-12. 節點停機後的仲裁寫、仲裁讀和讀修復。

現在設想不可用的節點恢復上線，客戶端開始從它讀取。該節點停機期間發生的寫入都沒有儲存在這裡，因此從它讀取時，響應中可能包含 陳舊（過時）的值。

為解決這個問題，客戶端讀取資料庫時，不能只把請求發給一個副本：讀請求也要並行發往多個節點。不同節點可能給出不同響應，例如一個返回最新值，另一個返回陳舊值。

要分辨哪些響應是最新的、哪些已經過時，每個寫入的值都必須帶有版本號或時間戳，類似 “最後寫入者勝（丟棄併發寫入）” 中介紹的做法。客戶端收到多個讀取結果時，採用時間戳最大的值——即使只有一個副本返回該值，其他幾個副本都返回舊值。更多細節參見 “檢測併發寫入”。

追趕錯過的寫入

複製系統應當保證所有資料最終都會複製到每個副本。不可用節點恢復上線後，怎樣補上停機期間錯過的寫入？Dynamo 風格的資料儲存會使用以下幾種機制：

讀修復
客戶端並行讀取多個節點時，可以發現陳舊響應。例如在 圖 6-12 中，使用者 2345 從副本 3 得到版本 6 的值，從副本 1 和副本 2 得到版本 7 的值。客戶端發現副本 3 的值已經過時，於是把較新的值寫回這個副本。對於經常讀取的值，這種方法很有效。
提示移交
某個副本不可用時，另一個副本可以替它儲存寫入，並把這些寫入記錄為 提示。原本應接收這些寫入的副本恢復後，儲存提示的副本會將它們傳送過去，然後刪除提示。即使某些值從未被讀取、無法透過讀修復更新，這個 移交 過程也能讓副本趕上進度。
反熵
此外，還有一個後臺程序定期查詢副本之間的資料差異，把缺失的資料從一個副本複製到另一個。與基於領導者的複製日誌不同，這個 反熵過程 並不按特定順序複製寫入，資料得到複製之前可能有很長延遲。

讀寫仲裁

在 圖 6-12 的例子中，寫入只在三個副本中的兩個上完成，我們仍判定它成功。如果只有一個副本接受寫入呢？這個下限究竟能壓到多低？

如果能保證每次成功寫入至少儲存在三個副本中的兩個上，那麼最多隻有一個副本是陳舊的。因此，只要讀取至少兩個副本，就可以確信其中至少一個是最新的。即使第三個副本停機或響應緩慢，讀取仍能返回最新值。

更一般地說，假設有 n 個副本，每次寫入必須得到 w 個節點確認才算成功，每次讀取則至少查詢 r 個節點。（上述例子中，n = 3、w = 2、r = 2。）只要 w + r > n，讀取時就有望得到最新值，因為所查詢的 r 個節點中，至少有一個必然是最新的。遵守這些 r、w 取值的操作稱為 仲裁讀 和 仲裁寫 50。可以把 r 和 w 看作一次讀或寫要成立所需的最低票數。

在 Dynamo 風格的資料庫中，引數 n、w、r 通常都可以配置。常見做法是讓 n 取奇數（通常為 3 或 5），並令 w = r = (n + 1) / 2（向上取整）；不過也可以根據需要調整。例如，寫少讀多的工作負載可能適合設為 w = n、r = 1。這樣讀取更快，缺點是隻要一個節點失效，所有資料庫寫入都會失敗。

Note

叢集中的節點數可以多於 n，但任意給定值只儲存在 n 個節點上。這樣就能對資料集進行分片，支援單個節點無法容納的資料集。我們會在 第 7 章 繼續討論分片。

仲裁條件 w + r > n 使系統能夠按以下方式容忍節點不可用：

  • 如果 w < n，有一個節點不可用時仍可處理寫入。
  • 如果 r < n，有一個節點不可用時仍可處理讀取。
  • 當 n = 3、w = 2、r = 2 時，可以像 圖 6-12 那樣容忍一個節點不可用。
  • 當 n = 5、w = 3、r = 3 時，可以容忍兩個節點不可用，如 圖 6-13 所示。

通常，讀寫請求總會並行傳送到全部 n 個副本。引數 w 和 r 決定要等待多少個節點，也就是在判定讀或寫成功之前，n 個節點中必須有多少個報告成功。

圖 6-13. 如果 w + r > n，讀取的 r 個副本中至少有一個必然見過最近一次成功寫入。

如果可用節點少於所需的 w 或 r，寫入或讀取就會返回錯誤。節點不可用可能有許多原因：節點停機（崩潰或斷電）、執行操作時出錯（磁碟已滿，無法寫入）、客戶端與節點之間網路中斷，等等。我們只關心節點是否返回成功響應，無需區分故障的具體型別。

仲裁一致性的侷限

如果有 n 個副本，並選擇滿足 w + r > n 的 w 和 r，通常可以期望每次讀取都返回某個鍵最近寫入的值。這是因為寫入所涉及的節點集合與讀取所涉及的節點集合必然有交集；也就是說，讀取的節點中至少有一個儲存著最新值，如 圖 6-13 所示。

r 和 w 通常取節點的多數（多於 n/2），因為這樣既能保證 w + r > n，又能容忍最多 n/2（向下取整）個節點失效。不過，法定人數並不一定非得是多數；真正重要的是，讀操作與寫操作所用的節點集合至少有一個共同節點。法定人數還可以有其他安排，為分散式演算法的設計提供一定靈活性 51。

也可以把 w 和 r 設得更小，使 w + r ≤ n，即不滿足仲裁條件。此時讀寫請求仍會發往 n 個節點，只是操作成功所需的成功響應更少。

w 和 r 越小，越容易讀到陳舊值，因為讀操作更可能沒有覆蓋儲存最新值的節點。好處則是延遲更低、可用性更高：網路中斷導致許多副本不可達時，系統仍有更大機會繼續處理讀寫。只有可達副本數低於 w 或 r 時，資料庫才會分別變得不可寫或不可讀。

然而，即使 w + r > n，仍有一些邊緣情況會讓一致性屬性變得難以理解，例如：

  • 如果儲存新值的節點失效，又從儲存舊值的副本恢復資料，儲存新值的副本數可能降到 w 以下，破壞仲裁條件。
  • 再平衡期間，一部分資料會從一個節點遷移到另一個節點（見 第 7 章），各節點對“某個值的 n 個副本應由哪些節點儲存”可能看法不一，使讀仲裁與寫仲裁不再相交。
  • 如果讀操作與寫操作併發，讀取可能看見併發寫入的值，也可能看不見。尤其是，某次讀取可能看到新值，後續讀取卻看到舊值，參見 “線性一致性與仲裁”。
  • 如果一次寫入在部分副本上成功、在其餘副本上失敗（例如某些節點磁碟已滿），總成功數少於 w，那麼整體寫入會判定失敗，但成功副本上的寫入不會回滾。這意味著即使系統報告寫入失敗，後續讀取仍可能返回這次寫入的值 52。
  • 如果資料庫用實時時鐘的時間戳判斷寫入的新舊（例如 Cassandra 和 ScyllaDB），另一個時鐘較快的節點只要寫過同一個鍵，後續寫入就可能被靜默丟棄。我們在 “最後寫入者勝（丟棄併發寫入）” 中已經見過這個問題，還會在 “對同步時鐘的依賴” 中進一步討論。
  • 如果兩次寫入併發發生，一個副本可能先處理其中一次，另一個副本則先處理另一次，由此產生衝突，與多主複製中的情況相似（參見 “處理寫入衝突”）。我們會在 “檢測併發寫入” 中再談這個問題。

因此，仲裁看似保證讀取返回最近寫入的值，實際卻沒有那麼簡單。Dynamo 風格資料庫通常針對能夠容忍最終一致性的場景最佳化。引數 w 和 r 可以調節讀到陳舊值的機率 53，卻不宜被當作絕對保證。

監控陳舊性

從運維角度看，監控資料庫返回的結果是否最新非常重要。即使應用程式能夠容忍陳舊讀取，也必須瞭解複製是否健康。如果複製大幅落後，系統應發出告警，以便調查網路故障、節點過載等原因。

採用基於領導者的複製時，資料庫通常會暴露覆制延遲指標，供監控系統採集。這是因為寫入在領導者和追隨者上按相同順序應用，每個節點都有自己在複製日誌中的位置，也就是已經在本地應用了多少次寫入。用領導者當前位置減去追隨者當前位置，便可度量複製延遲。

無主複製系統沒有固定的寫入應用順序，監控起來更加困難。副本為了移交而儲存的提示數量可以作為一項健康指標，卻很難作出有意義的解釋 54。最終一致性有意給出了一項模糊保證，但為了可運維性，必須能夠量化“最終”究竟有多遠。

單主與無主複製的效能

基於單個領導者的複製系統能夠提供強一致性保證，而無主系統很難甚至不可能做到。不過，正如 “複製延遲的問題” 中所見，在基於領導者的複製系統裡，如果從非同步更新的追隨者讀取，同樣可能得到陳舊值。

從領導者讀取可以保證響應最新，卻存在效能問題：

  • 讀取吞吐量受領導者處理能力限制；相比之下，讀擴充套件可以把讀取分散到非同步更新的副本，但這些副本可能返回陳舊值。
  • 領導者失效後，必須等系統檢測到故障並完成故障切換，才能繼續處理請求。即使故障切換很快，響應時間的短暫上升也會被使用者察覺；如果耗時很長，系統就會在此期間不可用。
  • 系統對領導者的效能問題極其敏感。如果領導者因過載或資源爭用而響應緩慢，使用者的響應時間也會立即增加。

無主架構的一大優點，是面對這些問題時韌性更強。系統無需故障切換，而且請求原本就會並行發往多個副本，因此一個副本變慢或不可用，對響應時間的影響很小：客戶端只需採用響應較快的其他副本所返回的結果。採用最快響應的做法稱為 請求對沖，可以顯著降低尾延遲 55。

無主系統之所以有這種韌性，根本原因是它不區分正常情況和故障情況。這對於處理所謂的 灰色失效 尤其有利：節點並未徹底停機，卻處於降級狀態，處理請求異常緩慢 56；節點單純過載時也是如此（例如節點離線一段時間後，靠提示移交恢復可能產生大量額外負載）。基於領導者的系統必須判斷情況是否嚴重到需要故障切換，而故障切換本身又可能帶來進一步中斷；無主系統根本不需要作出這項判斷。

當然，無主系統也可能遇到效能問題：

  • 即使不需要執行故障切換，也必須由一個副本發現另一個副本不可用，才能替它儲存錯過寫入的提示。不可用副本恢復後，移交過程還要把這些提示發給它。在系統本已承壓時，這會給副本增加額外負載 54。
  • 副本越多，法定人數越大，請求完成前必須等待的響應也越多。即使只等待最快的 r 或 w 個副本，即使所有請求並行發出，更大的 r 或 w 仍會提高遇到慢副本的機率，從而增加總體響應時間（參見 “響應時間指標的應用”）。
  • 大範圍網路中斷使客戶端與大量副本斷開時，可能根本無法組成法定人數。有些無主資料庫允許任何可達副本接受寫入，即使它不屬於該鍵通常所在的副本集合（Riak 和 Dynamo 稱之為 寬鬆仲裁 45；Cassandra 和 ScyllaDB 稱之為 一致性級別 ANY）。後續讀取不保證能看到這次寫入，但對某些應用而言，這仍好過寫入直接失敗。

多主複製抵禦網路中斷的能力甚至可能強於無主複製，因為讀寫只需與一個領導者通訊，而領導者可以與客戶端位於同一地區。不過，一個領導者上的寫入會非同步傳播給其他領導者，讀取結果因而可能任意陳舊。仲裁讀寫提供了一種折中：既有良好的容錯能力，也有很高機率讀到最新資料。

多地區操作

我們此前把跨地區複製作為多主複製的一個用例（見 “多主複製”）。無主複製同樣適合多地區執行，因為它本來就是為了容忍相互衝突的併發寫入、網路中斷和延遲尖峰而設計的。

Cassandra 和 ScyllaDB 在常規無主模型中實現多地區支援：客戶端把寫入直接發往所有地區的副本，並可選擇多種一致性級別，規定請求至少得到多少響應才算成功。例如，可以要求所有地區的全部副本共同組成一個法定人數，也可以要求每個地區各自組成法定人數，或只要求客戶端所在地區達到法定人數。本地法定人數無需等待其他地區的慢請求，但也更容易返回陳舊結果。

Riak 則把客戶端與資料庫節點之間的所有通訊限制在本地地區，因此 n 表示一個地區內的副本數。資料庫叢集之間的跨地區複製在後臺非同步進行，方式與多主複製相似。

檢測併發寫入

與多主複製一樣，無主資料庫允許對同一個鍵併發寫入，由此產生需要解決的衝突。衝突可能在寫入發生時出現，但並非總是如此；它也可能到讀修復、提示移交或反熵階段才被發現。

問題在於，網路延遲會變化，系統還可能部分失效，所以事件抵達不同節點的順序可能不同。例如，圖 6-14 展示了客戶端 A 和 B 同時寫入三節點資料儲存中的鍵 X：

  • 節點 1 收到 A 的寫入，但由於短暫中斷，一直沒有收到 B 的寫入。
  • 節點 2 先收到 A 的寫入，再收到 B 的寫入。
  • 節點 3 先收到 B 的寫入，再收到 A 的寫入。
圖 6-14. Dynamo 風格資料儲存中的併發寫入沒有明確定義的順序。

如果每個節點一收到客戶端寫請求就直接覆蓋鍵的值，各節點將永久不一致，如 圖 6-14 最後的 get 請求所示：節點 2 認為 X 的最終值是 B，其他節點卻認為是 A。

為了達到最終一致，各副本必須收斂到同一個值。可以採用 “處理寫入衝突” 中討論過的任意衝突解決機制，例如 Cassandra 和 ScyllaDB 使用的最後寫入者勝、手工解決，或 “CRDT 與操作變換” 中介紹且 Riak 使用的 CRDT。

最後寫入者勝很容易實現：給每次寫入附加時間戳，時間戳較大的值總是覆蓋較小的值。但時間戳無法告訴你兩個值究竟是否衝突：它們可能是併發寫入的，也可能先後寫入。如果要顯式解決衝突，系統必須更仔細地檢測併發寫入。

“先發生”關係與併發

怎樣判斷兩個操作是否併發？先看幾個例子來建立直覺：

  • 在 圖 6-8 中，兩次寫入併不併發：A 的插入 先發生於 B 的遞增，因為 B 所遞增的值正是 A 插入的值。換句話說，B 的操作建立在 A 的操作之上，所以 B 必然發生得更晚。也可以說，B 因果依賴 於 A。
  • 圖 6-14 中的兩次寫入則是併發的：每個客戶端開始操作時，都不知道另一個客戶端也在操作同一個鍵。因此，兩次操作之間沒有因果依賴。

如果操作 B 知道 A、依賴 A，或以某種方式建立在 A 之上，就稱操作 A 先發生於 操作 B。一項操作是否先發生於另一項操作，是定義併發的關鍵。事實上，只要兩個操作誰也不先發生於另一個——也就是說，誰都不知道對方——就可以稱它們 併發 57。

因此，對於任意兩個操作 A 與 B，只有三種可能：A 先發生於 B；B 先發生於 A；或者 A 與 B 併發。我們需要一種演算法判斷兩次操作是否併發。如果一項操作先發生於另一項，後發生的操作就應覆蓋先前操作；如果兩者併發，則出現了需要解決的衝突。

併發、時間與相對論

兩項操作似乎只有在“同一時刻”發生時才應稱為併發，實際上它們在物理時間上是否重疊並不重要。由於分散式系統中的時鐘問題，判斷兩件事是否恰好同時發生相當困難，我們會在 第 9 章 進一步討論。

定義併發時，精確時間並不重要：只要兩項操作彼此都不知道對方，就稱它們併發，無論它們實際發生在什麼物理時刻。人們有時把這個原理與物理學中的狹義相對論聯絡起來 57。狹義相對論提出，資訊傳播不可能超過光速。因此，如果相隔一定距離的兩個事件之間，時間差短於光傳播這段距離所需的時間，它們就不可能相互影響。

在計算機系統中，即使按光速計算，一項操作原則上來得及影響另一項，兩者仍可能併發。例如，當時網路很慢或已經中斷，兩項操作即使相隔一段時間，仍會因網路問題而彼此無法知曉。

捕獲先發生關係

下面看一種演算法，它可以判斷兩項操作是併發的，還是一項先發生於另一項。為簡單起見，先從只有一個副本的資料庫開始。弄清單副本的做法後，再推廣到擁有多個副本的無主資料庫。

圖 6-15 展示了兩個客戶端併發地向同一個購物車新增商品。（如果這個例子太無聊，也可以設想兩名空中交通管制員併發地把飛機加入各自正在監視的空域。）購物車最初為空，兩個客戶端先後共向資料庫發出五次寫入：

  1. 客戶端 1 把 milk 加入購物車。這是該鍵的第一次寫入，伺服器成功儲存它並分配版本 1；然後把值和版本號一起返回給客戶端。
  2. 客戶端 2 把 eggs 加入購物車，卻不知道客戶端 1 同時加入了 milk（它以為 eggs 是購物車中唯一的商品）。伺服器為這次寫入分配版本 2，把 eggs 和 milk 儲存為兩個獨立的值（兄弟值），再把 兩個 值連同版本號 2 一起返回給客戶端。
  3. 客戶端 1 不知道客戶端 2 的寫入，又想加入 flour，因此它認為購物車內容應為 [milk, flour]。它把這個值連同伺服器此前給出的版本號 1 一起傳送。伺服器可以根據版本號判斷：[milk, flour] 取代了先前的 [milk]，卻與 [eggs] 併發。因此，伺服器為 [milk, flour] 分配版本 3，覆蓋版本 1 的 [milk]，保留版本 2 的 [eggs]，並把剩下的兩個值都返回給客戶端。
  4. 與此同時，客戶端 2 想加入 ham，並不知道客戶端 1 剛剛加入 flour。客戶端 2 在上一次響應中收到了 [milk] 和 [eggs]，於是將兩者合併，再加入 ham，形成新值 [eggs, milk, ham]。它把這個值連同先前的版本號 2 一起發給伺服器。伺服器判斷版本 2 可以覆蓋 [eggs]，但與 [milk, flour] 併發；剩下的兩個值便是版本 3 的 [milk, flour] 和版本 4 的 [eggs, milk, ham]。
  5. 最後，客戶端 1 想加入 bacon。它此前在版本 3 的響應中收到 [milk, flour] 和 [eggs]，於是合併二者，加入 bacon，把最終值 [milk, flour, eggs, bacon] 連同版本號 3 發給伺服器。這個值覆蓋 [milk, flour]（[eggs] 已在上一步被覆蓋），卻與 [eggs, milk, ham] 併發，因此伺服器保留這兩個併發值。
圖 6-15. 捕獲兩個客戶端併發編輯購物車時的因果依賴。

圖 6-15 中各操作之間的資料流，在 圖 6-16 中以圖形表示。箭頭指出哪項操作 先發生於 另一項，也就是說，後發生的操作 知道 或 依賴 先發生的操作。在這個例子裡，客戶端從未完全掌握伺服器上的最新資料，因為始終有另一項操作併發進行。但值的舊版本最終會被覆蓋，而且不會丟失任何寫入。

圖 6-16. 圖 6-15 中因果依賴關係的圖示。

請注意，伺服器僅憑版本號就能判斷兩項操作是否併發，無需解釋值本身，因此值可以是任意資料結構。演算法如下：

  • 伺服器為每個鍵維護一個版本號；每次寫入該鍵時遞增版本號，並把新版本號與寫入值一同儲存。
  • 客戶端讀取一個鍵時，伺服器返回所有兄弟值（即尚未被覆蓋的全部值）以及最新版本號。客戶端寫入前必須先讀取。
  • 客戶端寫入一個鍵時，必須帶上前一次讀取所得的版本號，還必須把上次讀取收到的所有值合併起來，例如使用 CRDT，或詢問使用者。寫請求的響應與讀取相似，也會返回所有兄弟值，因此可以像購物車例子那樣連續執行多次寫入。
  • 伺服器收到帶有特定版本號的寫入時，可以覆蓋版本號不高於它的所有值，因為這些值已被合併進新值；版本號更高的值則必須保留，因為它們與傳入寫入併發。

寫入帶上前一次讀取所得的版本號，就說明這次寫入基於哪個先前狀態。如果寫入不含版本號，它就與其他所有寫入併發，因而不會覆蓋任何內容，只會作為後續讀取返回的值之一。

版本向量

圖 6-15 的例子只有一個副本。如果沒有領導者，而且多個副本都能接受寫入，演算法需要怎樣改變？

圖 6-15 用一個版本號捕獲操作之間的依賴關係，但多個副本併發接受寫入時，一個版本號就不夠了。此時必須針對每個鍵，給 每個副本 分別維護版本號。副本處理寫入時遞增自己的版本號，同時記錄自己見過的其他副本版本號。這些資訊表明哪些值應當覆蓋，哪些值應作為兄弟值保留。

所有副本的版本號集合稱為 版本向量 58。這種思路有若干變體，其中最值得關注的也許是 點化版本向量 59 60，Riak 2.0 採用了這種變體 61 62。這裡不展開細節；它的工作方式與購物車例子非常相似。

與 圖 6-15 中的版本號一樣，讀取時資料庫副本會把版本向量發給客戶端，隨後寫入時客戶端必須再把它帶回資料庫。（Riak 把版本向量編碼成一個字串，稱為 因果上下文。）版本向量讓資料庫能夠區分覆蓋寫入和併發寫入。

版本向量還保證：先從一個副本讀取，再把寫入發給另一個副本，是安全的。這樣做可能產生兄弟值，但只要正確合併兄弟值，就不會丟失資料。

版本向量與向量時鐘

版本向量 有時也稱為 向量時鐘，儘管兩者並不完全相同。區別十分微妙，細節請參閱相關文獻 60 63 64。簡而言之，比較副本狀態時，應當使用版本向量。

總結

本章考察了複製問題。複製有多種用途：

高可用性
即使一臺或多臺機器、一個可用區乃至整個地區停機，系統仍能繼續執行
離線執行
網路中斷時，應用程式仍能繼續工作
延遲
把資料放在地理上靠近使用者的位置，讓使用者能夠更快地與之互動
可伸縮性
把讀取分散到多個副本，處理超出單臺機器能力的讀取量

複製的目標看似簡單——在多臺機器上保留相同資料的副本——實際卻極其棘手。它要求我們仔細考慮併發、所有可能出錯的環節，以及怎樣應對故障造成的後果。至少要處理節點不可用和網路中斷，而且這還沒有算上軟體缺陷或硬體錯誤引起的靜默資料損壞等更隱蔽的故障。

我們討論了三種主要的複製方式：

單主複製
客戶端把所有寫入發給一個節點（領導者），領導者再把資料變更事件流傳送給其他副本（追隨者）。讀取可以在任意副本上執行，但追隨者返回的結果可能陳舊。
多主複製
客戶端把每次寫入發給多個領導者中的一個，任意領導者都能接受寫入。各領導者相互發送資料變更事件流，也會將其傳送給追隨者。
無主複製
客戶端把每次寫入發給多個節點，並行讀取多個節點，從而發現並修復持有陳舊資料的節點。

每種方式都有優缺點。單主複製很流行，因為它相對容易理解，又能提供強一致性。多主複製和無主複製面對節點故障、網路中斷和延遲尖峰時韌性更強，代價是必須解決衝突，而且只能提供較弱的一致性保證。

複製可以同步，也可以非同步；發生故障時，這項選擇會深刻影響系統行為。系統平穩執行時，非同步複製可能很快，但仍必須弄清複製延遲增大或伺服器失效時會發生什麼。如果領導者失效，而你把一個非同步更新的追隨者提升為新領導者，最近提交的資料可能丟失。

我們考察了複製延遲可能造成的幾種反常現象，並討論了幾種一致性模型，以便判斷應用程式在複製延遲下應有怎樣的行為：

寫後讀一致性
使用者應當總能看到自己提交的資料。
單調讀
使用者看到某一時刻的資料後，不應在稍後又看到更早時刻的資料。
一致字首讀
使用者看到的資料狀態應符合因果關係，例如以正確順序看到問題及其回答。

最後，我們討論了多主複製和無主複製如何讓所有副本最終收斂到一致狀態：用版本向量或類似演算法檢測哪些寫入併發，再用 CRDT 等衝突解決演算法合併併發寫入的值。最後寫入者勝和手工解決衝突也是可選方案。

本章一直假設每個副本都儲存整個資料庫的完整複製，但對大型資料集而言，這並不現實。下一章將介紹 分片，使每臺機器只需儲存一部分資料。

參考文獻

  1. B. G. Lindsay, P. G. Selinger, C. Galtieri, J. N. Gray, R. A. Lorie, T. G. Price, F. Putzolu, I. L. Traiger, and B. W. Wade. Notes on Distributed Databases. IBM Research, Research Report RJ2571(33471), July 1979. Archived at perma.cc/EPZ3-MHDD ↩︎ ↩︎

  2. Kenny Gryp. MySQL Terminology Updates. dev.mysql.com, July 2020. Archived at perma.cc/S62G-6RJ2 ↩︎

  3. Oracle Corporation. Oracle (Active) Data Guard 19c: Real-Time Data Protection and Availability. White Paper, oracle.com, March 2019. Archived at perma.cc/P5ST-RPKE ↩︎

  4. Microsoft. What is an Always On availability group? learn.microsoft.com, September 2024. Archived at perma.cc/ABH6-3MXF ↩︎

  5. Mostafa Elhemali, Niall Gallagher, Nicholas Gordon, Joseph Idziorek, Richard Krog, Colin Lazier, Erben Mo, Akhilesh Mritunjai, Somu Perianayagam, Tim Rath, Swami Sivasubramanian, James Christopher Sorenson III, Sroaj Sosothikul, Doug Terry, and Akshat Vig. Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service. At USENIX Annual Technical Conference (ATC), July 2022. ↩︎ ↩︎

  6. Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, Bram Gruneir, Justin Jaffray, Lucy Zhang, and Peter Mattis. CockroachDB: The Resilient Geo-Distributed SQL Database. At ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 1493–1509, June 2020. doi:10.1145/3318464.3386134 ↩︎

  7. Dongxu Huang, Qi Liu, Qiu Cui, Zhuhe Fang, Xiaoyu Ma, Fei Xu, Li Shen, Liu Tang, Yuxing Zhou, Menglong Huang, Wan Wei, Cong Liu, Jian Zhang, Jianjun Li, Xuelian Wu, Lingyu Song, Ruoxi Sun, Shuaipeng Yu, Lei Zhao, Nicholas Cameron, Liquan Pei, and Xin Tang. TiDB: a Raft-based HTAP database. Proceedings of the VLDB Endowment, volume 13, issue 12, pages 3072–3084. doi:10.14778/3415478.3415535 ↩︎

  8. Mallory Knodel and Niels ten Oever. Terminology, Power, and Inclusive Language in Internet-Drafts and RFCs. IETF Internet-Draft, August 2023. Archived at perma.cc/5ZY9-725E ↩︎

  9. Buck Hodges. Postmortem: VSTS 4 September 2018. devblogs.microsoft.com, September 2018. Archived at perma.cc/ZF5R-DYZS ↩︎

  10. Gunnar Morling. Leader Election With S3 Conditional Writes. www.morling.dev, August 2024. Archived at perma.cc/7V2N-J78Y ↩︎

  11. Vignesh Chandramohan, Rohan Desai, and Chris Riccomini. SlateDB Manifest Design. github.com, May 2024. Archived at perma.cc/8EUY-P32Z ↩︎

  12. Stas Kelvich. Why does Neon use Paxos instead of Raft, and what’s the difference? neon.tech, August 2022. Archived at perma.cc/SEZ4-2GXU ↩︎

  13. Dimitri Fontaine. An introduction to the pg_auto_failover project. tapoueh.org, November 2021. Archived at perma.cc/3WH5-6BAF ↩︎

  14. Jesse Newland. GitHub availability this week. github.blog, September 2012. Archived at perma.cc/3YRF-FTFJ ↩︎

  15. Mark Imbriaco. Downtime last Saturday. github.blog, December 2012. Archived at perma.cc/M7X5-E8SQ ↩︎

  16. John Hugg. ‘All In’ with Determinism for Performance and Testing in Distributed Systems. At Strange Loop, September 2015. ↩︎

  17. Hironobu Suzuki. The Internals of PostgreSQL. interdb.jp, 2017. ↩︎

  18. Amit Kapila. WAL Internals of PostgreSQL. At PostgreSQL Conference (PGCon), May 2012. Archived at perma.cc/6225-3SUX ↩︎

  19. Amit Kapila. Evolution of Logical Replication. amitkapila16.blogspot.com, September 2023. Archived at perma.cc/F9VX-JLER ↩︎

  20. Aru Petchimuthu. Upgrade your Amazon RDS for PostgreSQL or Amazon Aurora PostgreSQL database, Part 2: Using the pglogical extension. aws.amazon.com, August 2021. Archived at perma.cc/RXT8-FS2T ↩︎

  21. Yogeshwer Sharma, Philippe Ajoux, Petchean Ang, David Callies, Abhishek Choudhary, Laurent Demailly, Thomas Fersch, Liat Atsmon Guz, Andrzej Kotulski, Sachin Kulkarni, Sanjeev Kumar, Harry Li, Jun Li, Evgeniy Makeev, Kowshik Prakasam, Robbert van Renesse, Sabyasachi Roy, Pratyush Seth, Yee Jiun Song, Benjamin Wester, Kaushik Veeraraghavan, and Peter Xie. Wormhole: Reliable Pub-Sub to Support Geo-Replicated Internet Services. At 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), May 2015. ↩︎

  22. Douglas B. Terry. Replicated Data Consistency Explained Through Baseball. Microsoft Research, Technical Report MSR-TR-2011-137, October 2011. Archived at perma.cc/F4KZ-AR38 ↩︎ ↩︎ ↩︎

  23. Douglas B. Terry, Alan J. Demers, Karin Petersen, Mike J. Spreitzer, Marvin M. Theher, and Brent B. Welch. Session Guarantees for Weakly Consistent Replicated Data. At 3rd International Conference on Parallel and Distributed Information Systems (PDIS), September 1994. doi:10.1109/PDIS.1994.331722 ↩︎ ↩︎

  24. Werner Vogels. Eventually Consistent. ACM Queue, volume 6, issue 6, pages 14–19, October 2008. doi:10.1145/1466443.1466448 ↩︎

  25. Simon Willison. Reply to: “My thoughts about Fly.io (so far) and other newish technology I’m getting into”. news.ycombinator.com, May 2022. Archived at perma.cc/ZRV4-WWV8 ↩︎

  26. Nithin Tharakan. Scaling Bitbucket’s Database. atlassian.com, October 2020. Archived at perma.cc/JAB7-9FGX ↩︎

  27. Terry Pratchett. Reaper Man: A Discworld Novel. Victor Gollancz, 1991. ISBN: 978-0-575-04979-6 ↩︎

  28. Peter Bailis, Alan Fekete, Michael J. Franklin, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. Coordination Avoidance in Database Systems. Proceedings of the VLDB Endowment, volume 8, issue 3, pages 185–196, November 2014. doi:10.14778/2735508.2735509 ↩︎

  29. Yaser Raja and Peter Celentano. PostgreSQL bi-directional replication using pglogical. aws.amazon.com, January 2022. Archived at https://perma.cc/BUQ2-5QWN ↩︎

  30. Robert Hodges. If You *Must* Deploy Multi-Master Replication, Read This First. scale-out-blog.blogspot.com, April 2012. Archived at perma.cc/C2JN-F6Y8 ↩︎ ↩︎

  31. Lars Hofhansl. HBASE-7709: Infinite Loop Possible in Master/Master Replication. issues.apache.org, January 2013. Archived at perma.cc/24G2-8NLC ↩︎

  32. John Day-Richter. What’s Different About the New Google Docs: Making Collaboration Fast. drive.googleblog.com, September 2010. Archived at perma.cc/5TL8-TSJ2 ↩︎ ↩︎

  33. Evan Wallace. How Figma’s multiplayer technology works. figma.com, October 2019. Archived at perma.cc/L49H-LY4D ↩︎

  34. Tuomas Artman. Scaling the Linear Sync Engine. linear.app, June 2023. ↩︎

  35. Amr Saafan. Why Sync Engines Might Be the Future of Web Applications. nilebits.com, September 2024. Archived at perma.cc/5N73-5M3V ↩︎

  36. Isaac Hagoel. Are Sync Engines The Future of Web Applications? dev.to, July 2024. Archived at perma.cc/R9HF-BKKL ↩︎

  37. Sujay Jayakar. A Map of Sync. stack.convex.dev, October 2024. Archived at perma.cc/82R3-H42A ↩︎

  38. Alex Feyerke. Designing Offline-First Web Apps. alistapart.com, December 2013. Archived at perma.cc/WH7R-S2DS ↩︎

  39. Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, and Mark McGranaghan. Local-first software: You own your data, in spite of the cloud. At ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!), October 2019, pages 154–178. doi:10.1145/3359591.3359737 ↩︎

  40. Martin Kleppmann. The past, present, and future of local-first. At Local-First Conference, May 2024. ↩︎

  41. Conrad Hofmeyr. API Calling is to Sync Engines as jQuery is to React. powersync.com, November 2024. Archived at perma.cc/2FP9-7WJJ ↩︎

  42. Peter van Hardenberg and Martin Kleppmann. PushPin: Towards Production-Quality Peer-to-Peer Collaboration. At 7th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC), April 2020. doi:10.1145/3380787.3393683 ↩︎

  43. Leonard Kawell, Jr., Steven Beckhardt, Timothy Halvorsen, Raymond Ozzie, and Irene Greif. Replicated document management in a group communication system. At ACM Conference on Computer-Supported Cooperative Work (CSCW), September 1988. doi:10.1145/62266.1024798 ↩︎

  44. Ricky Pusch. Explaining how fighting games use delay-based and rollback netcode. words.infil.net and arstechnica.com, October 2019. Archived at perma.cc/DE7W-RDJ8 ↩︎

  45. Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon’s Highly Available Key-Value Store. At 21st ACM Symposium on Operating Systems Principles (SOSP), October 2007. doi:10.1145/1323293.1294281 ↩︎ ↩︎ ↩︎ ↩︎

  46. Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. A Comprehensive Study of Convergent and Commutative Replicated Data Types. INRIA Research Report no. 7506, January 2011. ↩︎

  47. Chengzheng Sun and Clarence Ellis. Operational Transformation in Real-Time Group Editors: Issues, Algorithms, and Achievements. At ACM Conference on Computer Supported Cooperative Work (CSCW), November 1998. doi:10.1145/289444.289469 ↩︎

  48. Joseph Gentle and Martin Kleppmann. Collaborative Text Editing with Eg-walker: Better, Faster, Smaller. At 20th European Conference on Computer Systems (EuroSys), March 2025. doi:10.1145/3689031.3696076 ↩︎

  49. Dharma Shukla. Azure Cosmos DB: Pushing the frontier of globally distributed databases. azure.microsoft.com, September 2018. Archived at perma.cc/UT3B-HH6R ↩︎

  50. David K. Gifford. Weighted Voting for Replicated Data. At 7th ACM Symposium on Operating Systems Principles (SOSP), December 1979. doi:10.1145/800215.806583 ↩︎ ↩︎

  51. Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. Flexible Paxos: Quorum Intersection Revisited. At 20th International Conference on Principles of Distributed Systems (OPODIS), December 2016. doi:10.4230/LIPIcs.OPODIS.2016.25 ↩︎

  52. Joseph Blomstedt. Bringing Consistency to Riak. At RICON West, October 2012. ↩︎

  53. Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, Joseph M. Hellerstein, and Ion Stoica. Quantifying eventual consistency with PBS. The VLDB Journal, volume 23, pages 279–302, April 2014. doi:10.1007/s00778-013-0330-1 ↩︎

  54. Colin Breck. Shared-Nothing Architectures for Server Replication and Synchronization. blog.colinbreck.com, December 2019. Archived at perma.cc/48P3-J6CJ ↩︎ ↩︎

  55. Jeffrey Dean and Luiz André Barroso. The Tail at Scale. Communications of the ACM, volume 56, issue 2, pages 74–80, February 2013. doi:10.1145/2408776.2408794 ↩︎

  56. Peng Huang, Chuanxiong Guo, Lidong Zhou, Jacob R. Lorch, Yingnong Dang, Murali Chintalapati, and Randolph Yao. Gray Failure: The Achilles’ Heel of Cloud-Scale Systems. At 16th Workshop on Hot Topics in Operating Systems (HotOS), May 2017. doi:10.1145/3102980.3103005 ↩︎

  57. Leslie Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM, volume 21, issue 7, pages 558–565, July 1978. doi:10.1145/359545.359563 ↩︎ ↩︎

  58. D. Stott Parker Jr., Gerald J. Popek, Gerard Rudisin, Allen Stoughton, Bruce J. Walker, Evelyn Walton, Johanna M. Chow, David Edwards, Stephen Kiser, and Charles Kline. Detection of Mutual Inconsistency in Distributed Systems. IEEE Transactions on Software Engineering, volume SE-9, issue 3, pages 240–247, May 1983. doi:10.1109/TSE.1983.236733 ↩︎

  59. Nuno Preguiça, Carlos Baquero, Paulo Sérgio Almeida, Victor Fonte, and Ricardo Gonçalves. Dotted Version Vectors: Logical Clocks for Optimistic Replication. arXiv:1011.5808, November 2010. ↩︎

  60. Giridhar Manepalli. Clocks and Causality - Ordering Events in Distributed Systems. exhypothesi.com, November 2022. Archived at perma.cc/8REU-KVLQ ↩︎ ↩︎

  61. Sean Cribbs. A Brief History of Time in Riak. At RICON, October 2014. Archived at perma.cc/7U9P-6JFX ↩︎

  62. Russell Brown. Vector Clocks Revisited Part 2: Dotted Version Vectors. riak.com, November 2015. Archived at perma.cc/96QP-W98R ↩︎

  63. Carlos Baquero. Version Vectors Are Not Vector Clocks. haslab.wordpress.com, July 2011. Archived at perma.cc/7PNU-4AMG ↩︎

  64. Reinhard Schwarz and Friedemann Mattern. Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail. Distributed Computing, volume 7, issue 3, pages 149–174, March 1994. doi:10.1007/BF02277859 ↩︎

最後更新於
第二部分：分散式資料7. 分片