6. 複製

出錯的事物與不可能出錯的事物之間的主要區別在於，當不可能出錯的事物出錯時，通常會發現它幾乎不可能查詢或修復。

Douglas Adams，《基本無害》（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

在較舊的文件中，你可能會看到術語 主從複製。它與基於主節點的複製含義相同，但應該避免使用該術語，因為它被廣泛認為是冒犯性的 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）。基於 ZDA 的系統將所有資料持久化到物件儲存，並嚴格將磁碟和記憶體用於快取。這允許節點沒有持久狀態，這大大簡化了運維。WarpStream、Confluent Freight、Buf 的 Bufstream 和 Redpanda Serverless 都是使用零磁碟架構構建的相容 Kafka 的系統。幾乎每個現代雲資料倉庫也採用這種架構，Turbopuffer（向量搜尋引擎）和 SlateDB（雲原生 LSM 儲存引擎）也是如此。

處理節點故障

系統中的任何節點都可能發生故障，可能是由於故障意外發生，但同樣可能是由於計劃維護（例如，重新啟動機器以安裝核心安全補丁）。能夠在不停機的情況下重新啟動單個節點對於操作和維護來說是一個很大的優勢。因此，我們的目標是儘管單個節點發生故障，但保持整個系統執行，並儘可能減小節點中斷的影響。

如何透過基於主節點的複製實現高可用性？

從節點故障：追趕恢復

在其本地磁碟上，每個從節點保留從主節點接收的資料變更日誌。如果從節點崩潰並重新啟動，或者如果主節點和從節點之間的網路暫時中斷，從節點可以很容易地恢復：從其日誌中，它知道在故障發生之前處理的最後一個事務。因此，從節點可以連線到主節點並請求在從節點斷開連線期間發生的所有資料變更。當它應用了這些變更後，它就趕上了主節點，可以像以前一樣繼續接收資料變更流。

儘管從節點恢復在概念上很簡單，但在效能方面可能具有挑戰性：如果資料庫具有高寫入吞吐量，或者如果從節點已離線很長時間，可能有很多寫入需要趕上。在進行這種追趕時，恢復的從節點和主節點（需要將寫入積壓傳送到從節點）都會有高負載。

一旦所有從節點都確認已處理了日誌，主節點就可以刪除其寫入日誌，但如果從節點長時間不可用，主節點面臨選擇：要麼保留日誌直到從節點恢復並趕上（冒著主節點磁碟空間耗盡的風險），要麼刪除不可用從節點尚未確認的日誌（在這種情況下，從節點無法從日誌中恢復，並且在它回來時必須從備份中恢復）。

領導者故障：故障轉移

處理主節點故障更加棘手：其中一個從節點需要被提升為新的主節點，客戶端需要重新配置以將其寫入傳送到新的主節點，其他從節點需要開始從新的主節點消費資料變更。這個過程稱為 故障轉移。

故障轉移可以手動發生（管理員收到主節點失敗的通知並採取必要步驟來建立新的主節點）或自動發生。自動故障轉移過程通常包括以下步驟：

  1. 確定主節點已失敗。 可能會出現許多問題：崩潰、停電、網路問題等。沒有萬無一失的方法來檢測出了什麼問題，所以大多數系統只是使用超時：節點經常相互反彈訊息，如果節點在一段時間內沒有響應——比如 30 秒——它被認為已死。（如果主節點被故意關閉以進行計劃維護，這不適用。）
  2. 選擇新的主節點。 這可以透過選舉過程完成（其中主節點由剩餘副本的多數選擇），或者新的主節點可以由先前建立的 控制器節點 任命 13。領導的最佳候選者通常是具有來自舊主節點的最新資料變更的副本（以最小化任何資料丟失）。讓所有節點就新主節點達成一致是一個共識問題，在 第 10 章 中詳細討論。
  3. 重新配置系統以使用新的主節點。 客戶端現在需要將其寫入請求傳送到新的主節點（我們在 “請求路由” 中討論這個問題）。如果舊的主節點恢復，它可能仍然認為自己是主節點，沒有意識到其他副本已經迫使它下臺。系統需要確保舊的主節點成為從節點並識別新的主節點。

故障轉移充滿了可能出錯的事情：

  • 如果使用非同步複製，新的主節點可能在失敗之前沒有收到來自舊主節點的所有寫入。如果前主節點在選擇了新主節點後重新加入叢集，那些寫入應該怎麼辦？新的主節點可能同時收到了衝突的寫入。最常見的解決方案是簡單地丟棄舊主節點未複製的寫入，這意味著你認為已提交的寫入實際上並不持久。
  • 如果資料庫之外的其他儲存系統需要與資料庫內容協調，丟棄寫入尤其危險。例如，在 GitHub 的一次事故中 14，一個過時的 MySQL 從節點被提升為主節點。資料庫使用自增計數器為新行分配主鍵，但由於新主節點的計數器落後於舊主節點，它重用了舊主節點先前分配的一些主鍵。這些主鍵也在 Redis 儲存中使用，因此主鍵的重用導致 MySQL 和 Redis 之間的不一致，這導致一些私人資料被錯誤地披露給錯誤的使用者。
  • 在某些故障場景中（見 第 9 章），可能會發生兩個節點都認為自己是主節點的情況。這種情況稱為 腦裂，這是危險的：如果兩個主節點都接受寫入，並且沒有解決衝突的過程（見 “多主複製”），資料很可能會丟失或損壞。作為安全措施，一些系統在檢測到兩個主節點時有一種機制來關閉一個節點。然而，如果這種機制設計不當，你最終可能會關閉兩個節點 15。此外，當檢測到腦裂並關閉舊節點時，可能為時已晚，資料已經損壞。
  • 在宣佈主節點死亡之前，正確的超時是什麼？更長的超時意味著在主節點失敗的情況下恢復時間更長。然而，如果超時太短，可能會有不必要的故障轉移。例如，臨時負載峰值可能導致節點的響應時間增加到超時以上，或者網路故障可能導致資料包延遲。如果系統已經在高負載或網路問題上掙扎，不必要的故障轉移可能會使情況變得更糟，而不是更好。

Note

透過限制或關閉舊主節點來防止腦裂被稱為 柵欄機制，或者更強調地說，向頭部開槍（STONITH）。我們將在 “分散式鎖和租約” 中更詳細地討論柵欄機制。

這些問題沒有簡單的解決方案。因此，一些運維團隊更喜歡手動執行故障轉移，即使軟體支援自動故障轉移。

故障轉移最重要的是選擇一個最新的從節點作為新的主節點——如果使用同步或半同步複製，這將是舊主節點在確認寫入之前等待的從節點。使用非同步複製，你可以選擇具有最大日誌序列號的從節點。這最小化了故障轉移期間丟失的資料量：丟失幾分之一秒的寫入可能是可以容忍的，但選擇落後幾天的從節點可能是災難性的。

這些問題——節點故障；不可靠的網路；以及圍繞副本一致性、永續性、可用性和延遲的權衡——實際上是分散式系統中的基本問題。在 第 9 章 和 第 10 章 中，我們將更深入地討論它們。

複製日誌的實現

基於主節點的複製在底層是如何工作的？讓我們簡要地看看實踐中使用的幾種不同的複製方法。

基於語句的複製

在最簡單的情況下，主節點記錄它執行的每個寫入請求（語句）並將該語句日誌傳送給其從節點。對於關係資料庫，這意味著每個 INSERT、UPDATE 或 DELETE 語句都被轉發到從節點，每個從節點解析並執行該 SQL 語句，就像它是從客戶端接收的一樣。

雖然這聽起來合理，但這種複製方法可能會出現各種問題：

  • 任何呼叫非確定性函式的語句，例如 NOW() 獲取當前日期和時間或 RAND() 獲取隨機數，可能會在每個副本上生成不同的值。
  • 如果語句使用自增列，或者如果它們依賴於資料庫中的現有資料（例如，UPDATE … WHERE <某條件>），它們必須在每個副本上以完全相同的順序執行，否則它們可能會產生不同的效果。當有多個併發執行的事務時，這可能會受到限制。
  • 具有副作用的語句（例如，觸發器、儲存過程、使用者定義的函式）可能會導致每個副本上發生不同的副作用，除非副作用是絕對確定的。

可以解決這些問題——例如，主節點可以在記錄語句時用固定的返回值替換任何非確定性函式呼叫，以便從節點都獲得相同的值。以固定順序執行確定性語句的想法類似於我們之前在 “事件溯源與 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，這方面很有用。這種技術稱為 變更資料捕獲，我們將在 [Link to Come] 中回到它。

複製延遲的問題

能夠容忍節點故障只是想要複製的一個原因。如 “分散式與單節點系統” 中所述，其他原因是可伸縮性（處理比單臺機器能夠處理的更多請求）和延遲（將副本在地理上放置得更接近使用者）。

基於主節點的複製要求所有寫入都透過單個節點，但只讀查詢可以轉到任何副本。對於主要由讀取和只有少量寫入組成的工作負載（這通常是線上服務的情況），有一個有吸引力的選擇：建立許多從節點，並將讀取請求分佈在這些從節點上。這減輕了主節點的負載，並允許附近的副本提供讀取請求。

在這種 讀擴充套件 架構中，你可以透過新增更多從節點來簡單地增加服務只讀請求的容量。然而，這種方法只有在使用非同步複製時才現實可行——如果你試圖同步複製到所有從節點，單個節點故障或網路中斷將使整個系統無法寫入。而且你擁有的節點越多，其中一個節點宕機的可能性就越大，因此完全同步的配置將非常不可靠。

不幸的是，如果應用程式從 非同步 從節點讀取，如果從節點已落後，它可能會看到過時的資訊。這導致資料庫中出現明顯的不一致：如果你同時在主節點和從節點上執行相同的查詢，你可能會得到不同的結果，因為並非所有寫入都已反映在從節點中。這種不一致只是一種臨時狀態——如果你停止向資料庫寫入並等待一段時間，從節點最終將趕上並與主節點保持一致。因此，這種效果被稱為 最終一致性 22。

Note

術語 最終一致性 由 Douglas Terry 等人創造 23，由 Werner Vogels 推廣 24，併成為許多 NoSQL 專案的戰鬥口號。然而，不僅 NoSQL 資料庫是最終一致的：非同步複製的關係資料庫中的從節點具有相同的特徵。

術語"最終"是故意模糊的：一般來說，副本可以落後多遠沒有限制。在正常操作中，寫入發生在主節點上並反映在從節點上之間的延遲——複製延遲——可能只是幾分之一秒，在實踐中不會被注意到。然而，如果系統在接近容量執行或網路中存在問題，延遲可以輕易增加到幾秒甚至幾分鐘。

當延遲如此之大時，它引入的不一致不僅僅是一個理論問題，而是應用程式的真正問題。在本節中，我們將重點介紹複製延遲時可能發生的三個問題示例。我們還將概述解決它們的一些方法。

讀己之寫

許多應用程式讓使用者提交一些資料，然後檢視他們提交的內容。這可能是客戶資料庫中的記錄，或討論執行緒上的評論，或其他類似的東西。提交新資料時，必須將其傳送到主節點，但當用戶檢視資料時，可以從從節點讀取。如果資料經常被檢視但只是偶爾被寫入，這尤其合適。

使用非同步複製，存在一個問題，如 圖 6-3 所示：如果使用者在寫入後不久檢視資料，新資料可能尚未到達副本。對使用者來說，看起來他們提交的資料丟失了，所以他們會理解地不高興。

圖 6-3. 使用者進行寫入，然後從陳舊副本讀取。為了防止這種異常，我們需要寫後讀一致性。

在這種情況下，我們需要 寫後讀一致性，也稱為 讀己之寫一致性 23。這是一種保證，如果使用者重新載入頁面，他們將始終看到他們自己提交的任何更新。它不對其他使用者做出承諾：其他使用者的更新可能直到稍後才可見。然而，它向用戶保證他們自己的輸入已正確儲存。

我們如何在基於主節點的複製系統中實現寫後讀一致性？有各種可能的技術。提及其中幾個：

  • 當讀取使用者可能已修改的內容時，從主節點或同步更新的從節點讀取；否則，從非同步更新的從節點讀取。這要求你有某種方法知道某物是否可能已被修改，而無需實際查詢它。例如，社交網路上的使用者個人資料資訊通常只能由個人資料的所有者編輯，而不能由其他任何人編輯。因此，一個簡單的規則是：始終從主節點讀取使用者自己的個人資料，從從節點讀取任何其他使用者的個人資料。
  • 如果應用程式中的大多數東西都可能被使用者編輯，那種方法將不會有效，因為大多數東西都必須從主節點讀取（否定了讀擴充套件的好處）。在這種情況下，可以使用其他標準來決定是否從主節點讀取。例如，你可以跟蹤上次更新的時間，並在上次更新後的一分鐘內，使所有讀取都來自主節點 25。你還可以監控從節點上的複製延遲，並防止在落後主節點超過一分鐘的任何從節點上進行查詢。
  • 客戶端可以記住其最近寫入的時間戳——然後系統可以確保為該使用者提供任何讀取的副本至少反映該時間戳之前的更新。如果副本不夠最新，則可以由另一個副本處理讀取，或者查詢可以等待直到副本趕上 26。時間戳可以是 邏輯時間戳（指示寫入順序的東西，例如日誌序列號）或實際系統時鐘（在這種情況下，時鐘同步變得至關重要；見 “不可靠的時鐘”）。
  • 如果你的副本分佈在各個地區（為了地理上接近使用者或為了可用性），還有額外的複雜性。任何需要由主節點提供的請求都必須路由到包含主節點的地區。

當同一使用者從多個裝置訪問你的服務時，會出現另一個複雜情況，例如桌面網路瀏覽器和移動應用程式。在這種情況下，你可能希望提供 跨裝置 寫後讀一致性：如果使用者在一個裝置上輸入一些資訊，然後在另一個裝置上檢視它，他們應該看到他們剛剛輸入的資訊。

在這種情況下，需要考慮一些額外的問題：

  • 需要記住使用者上次更新的時間戳的方法變得更加困難，因為在一個裝置上執行的程式碼不知道在另一個裝置上發生了什麼更新。此元資料將需要集中化。
  • 如果你的副本分佈在不同的地區，則無法保證來自不同裝置的連線將路由到同一地區。（例如，如果使用者的臺式計算機使用家庭寬頻連線，而他們的移動裝置使用蜂窩資料網路，則裝置的網路路由可能完全不同。）如果你的方法需要從主節點讀取，你可能首先需要將來自使用者所有裝置的請求路由到同一地區。

![TIP] 地區和可用區

我們使用術語 地區 來指代單個地理位置中的一個或多個數據中心。雲提供商在同一地理區域中定位多個數據中心。每個資料中心被稱為 可用區 或簡稱 區域。因此，單個雲區域由多個區域組成。每個區域是位於獨立物理設施中的獨立資料中心，具有自己的電源、冷卻等。

同一地區的區域透過非常高速的網路連線連線。延遲足夠低，以至於大多數分散式系統可以在同一地區的多個區域中執行節點，就好像它們在單個區域中一樣。多區域配置允許分散式系統在一個區域離線的區域中斷中倖存，但它們不能防止所有區域不可用的區域中斷。為了在區域中斷中倖存，分散式系統必須部署在多個地區，這可能導致更高的延遲、更低的吞吐量和增加的雲網絡賬單。我們將在 “多主複製拓撲” 中更多地討論這些權衡。現在，只要知道當我們說地區時，我們指的是單個地理位置中的區域/資料中心集合。

單調讀

從非同步從節點讀取時可能發生的第二個異常示例是，使用者可能會看到事物 在時間上倒退。

如果使用者從不同的副本進行多次讀取，就可能發生這種情況。例如，圖 6-4 顯示使用者 2345 進行相同的查詢兩次，首先到延遲很小的從節點，然後到延遲更大的從節點。（如果使用者重新整理網頁，並且每個請求都路由到隨機伺服器，這種情況很可能發生。）第一個查詢返回使用者 1234 最近新增的評論，但第二個查詢沒有返回任何內容，因為滯後的從節點尚未獲取該寫入。實際上，第二個查詢觀察到的系統狀態比第一個查詢更早的時間點。如果第一個查詢沒有返回任何內容，這不會那麼糟糕，因為使用者 2345 可能不知道使用者 1234 最近添加了評論。然而，如果使用者 2345 首先看到使用者 1234 的評論出現，然後又看到它消失，這對使用者 2345 來說非常令人困惑。

圖 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 運動推廣了這樣的觀點，即這些功能限制了可伸縮性，大規模系統必須接受最終一致性。

然而，從那時起，許多資料庫開始提供強一致性和事務，同時還提供分散式資料庫的容錯、高可用性和可伸縮性優勢。如 “關係模型與文件模型” 中所述，這種趨勢被稱為 NewSQL，以與 NoSQL 形成對比（儘管它不太關於 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。

這再次導致多主架構：每個開啟共享檔案的 Web 瀏覽器選項卡都是一個副本，你對檔案進行的任何更新都會非同步複製到開啟同一檔案的其他使用者的裝置。即使應用程式不允許你在離線時繼續編輯檔案，多個使用者可以進行編輯而無需等待伺服器的響應這一事實已經使其成為多主。

離線編輯和即時協作都需要類似的複製基礎設施：應用程式需要捕獲使用者對檔案所做的任何更改，並立即將它們傳送給協作者（如果線上），或本地儲存它們以供稍後傳送（如果離線）。此外，應用程式需要接收來自協作者的更改，將它們合併到使用者的檔案本地副本中，並更新使用者介面以反映最新版本。如果多個使用者同時更改了檔案，可能需要衝突解決邏輯來合併這些更改。

支援此過程的軟體庫稱為 同步引擎。儘管這個想法已經存在很長時間了，但這個術語最近才受到關注 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）。

多人影片遊戲有類似的需求，需要立即響應使用者的本地操作，並將它們與透過網路非同步接收的其他玩家的操作協調。在遊戲開發術語中，同步引擎的等效物稱為 網路程式碼。網路程式碼中使用的技術非常特定於遊戲的要求 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 的寫入。如果寫入巧合地具有相同的時間戳，可以透過比較值來選擇獲勝者（例如，在字串的情況下，取字母表中較早的那個）。

這種方法稱為 最後寫入者勝（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"可以按原樣應用，但如果在 3 處插入”!“應用於狀態"nice”，我們將得到"nic!e”，這是不正確的。因此，我們需要轉換每個操作的索引以考慮已經應用的併發操作；在這種情況下，"!“的插入被轉換為索引 4 以考慮在較早索引處插入"n”。
CRDT
大多數 CRDT 為每個字元提供唯一的、不可變的 ID，並使用這些 ID 來確定插入/刪除的位置，而不是索引。例如，在 圖 6-11 中，我們將 ID 1A 分配給"i"，ID 2A 分配給"c"等。插入感嘆號時，我們生成一個包含新字元的 ID（4B）和我們想要在其後插入的現有字元的 ID（3A）的操作。要在字串的開頭插入，我們將"nil"作為前面的字元 ID。在同一位置的併發插入按字元的 ID 排序。這確保副本收斂而不執行任何轉換。

有許多基於這些想法變體的演算法。列表/陣列可以類似地支援，使用列表元素而不是字元，其他資料型別（如鍵值對映）可以很容易地新增。OT 和 CRDT 之間存在一些效能和功能權衡，但可以在一個演算法中結合 CRDT 和 OT 的優點 48。

OT 最常用於文字的即時協作編輯，例如在 Google Docs 中 32，而 CRDT 可以在分散式資料庫中找到，例如 Redis Enterprise、Riak 和 Azure Cosmos DB 49。JSON 資料的同步引擎可以使用 CRDT（例如，Automerge 或 Yjs）和 OT（例如，ShareDB）實現。

什麼是衝突？

某些型別的衝突是顯而易見的。在 圖 6-9 的示例中，兩個寫入併發修改了同一記錄中的同一欄位，將其設定為兩個不同的值。毫無疑問，這是一個衝突。

其他型別的衝突可能更難以檢測。例如，考慮一個會議室預訂系統：它跟蹤哪個房間由哪組人在什麼時間預訂。此應用程式需要確保每個房間在任何時間只由一組人預訂（即，同一房間不得有任何重疊的預訂）。在這種情況下，如果為同一房間同時建立兩個不同的預訂，可能會出現衝突。即使應用程式在允許使用者進行預訂之前檢查可用性，如果兩個預訂是在兩個不同的主節點上進行的，也可能會發生衝突。

沒有快速現成的答案，但在以下章節中，我們將追蹤通向對這個問題的良好理解的路徑。我們將在 第 8 章 中看到更多衝突的例子，並在 [Link to Come] 中討論在複製系統中檢測和解決衝突的可伸縮方法。

無主複製

到目前為止，我們在本章中討論的複製方法——單主和多主複製——都基於這樣的想法：客戶端向一個節點（主節點）傳送寫入請求，資料庫系統負責將該寫入複製到其他副本。主節點確定寫入應該處理的順序，從節點以相同的順序應用主節點的寫入。

一些資料儲存系統採用不同的方法，放棄主節點的概念，並允許任何副本直接接受來自客戶端的寫入。一些最早的複製資料系統是無主的 1 50，但在關係資料庫主導的時代，這個想法基本上被遺忘了。在亞馬遜於 2007 年將其用於其內部 Dynamo 系統後，它再次成為資料庫的時尚架構 45。Riak、Cassandra 和 ScyllaDB 是受 Dynamo 啟發的具有無主複製模型的開源資料儲存，因此這種資料庫也被稱為 Dynamo 風格。

Note

原始的 Dynamo 系統僅在論文中描述 45，但從未在亞馬遜之外發布。AWS 的名稱相似的 DynamoDB 是一個更新的雲資料庫，但它具有完全不同的架構：它使用基於 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 使得 w + r > n，你通常可以期望每次讀取都返回為鍵寫入的最新值。這是因為你寫入的節點集和你讀取的節點集必須重疊。也就是說，在你讀取的節點中，必須至少有一個具有最新值的節點（如 圖 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（在 “CRDT 與操作變換” 中描述，並由 Riak 使用）。

最後寫入者勝很容易實現：每個寫入都標有時間戳，具有更高時間戳的值總是覆蓋具有較低時間戳的值。然而，時間戳不會告訴你兩個值是否實際上衝突（即，它們是併發寫入的）或不衝突（它們是一個接一個寫入的）。如果你想顯式解決衝突，系統需要更加小心地檢測併發寫入。

“先發生"關係與併發

我們如何決定兩個操作是否併發？為了培養直覺，讓我們看一些例子：

  • 在 圖 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 是併發的。我們需要的是一個演算法來告訴我們兩個操作是否併發。如果一個操作先發生於另一個，後面的操作應該覆蓋前面的操作，但如果操作是併發的，我們有一個需要解決的衝突。

![TIP] 併發、時間和相對論

似乎兩個操作如果"同時"發生，應該稱為併發——但實際上，它們是否真的在時間上重疊並不重要。由於分散式系統中的時鐘問題，實際上很難判斷兩件事是否恰好在同一時間發生——我們將在 第 9 章 中更詳細地討論這個問題。

為了定義併發，確切的時間並不重要：我們只是稱兩個操作併發，如果它們都不知道對方，無論它們發生的物理時間如何。人們有時將這一原則與物理學中的狹義相對論聯絡起來 57，它引入了資訊不能比光速傳播更快的想法。因此，如果兩個事件之間的時間短於光在它們之間傳播的時間，那麼相隔一定距離發生的兩個事件不可能相互影響。

在計算機系統中，即使光速原則上允許一個操作影響另一個，兩個操作也可能是併發的。例如，如果網路在當時很慢或中斷，兩個操作可以相隔一段時間發生，仍然是併發的，因為網路問題阻止了一個操作能夠知道另一個。

捕獲先發生關係

讓我們看一個確定兩個操作是否併發或一個先發生於另一個的演算法。為了簡單起見，讓我們從只有一個副本的資料庫開始。一旦我們弄清楚如何在單個副本上執行此操作，我們就可以將該方法推廣到具有多個副本的無主資料庫。

圖 6-15 顯示了兩個客戶端併發地向同一購物車新增專案。（如果這個例子讓你覺得太無聊，想象一下兩個空中交通管制員併發地向他們正在跟蹤的扇區新增飛機。）最初，購物車是空的。客戶端之間向資料庫進行了五次寫入：

  1. 客戶端 1 將 milk 新增到購物車。這是對該鍵的第一次寫入，因此伺服器成功儲存它併為其分配版本 1。伺服器還將值連同版本號一起回顯給客戶端。
  2. 客戶端 2 將 eggs 新增到購物車，不知道客戶端 1 併發地添加了 milk（客戶端 2 認為它的 eggs 是購物車中的唯一專案）。伺服器為此寫入分配版本 2，並將 eggs 和 milk 儲存為兩個單獨的值（兄弟節點）。然後，它將 兩個 值連同版本號 2 一起返回給客戶端。
  3. 客戶端 1，不知道客戶端 2 的寫入，想要將 flour 新增到購物車，因此它認為當前購物車內容應該是 [milk, flour]。它將此值連同伺服器之前給客戶端 1 的版本號 1 一起傳送到伺服器。伺服器可以從版本號判斷 [milk, flour] 的寫入取代了 [milk] 的先前值，但它與 [eggs] 併發。因此，伺服器將版本 3 分配給 [milk, flour]，覆蓋版本 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. 分片