本章摘要： 探討單主、多主與無主三種複製策略的寫入衝突處理與一致性保證，深入複製延遲帶來的 read-after-write、monotonic reads 等一致性問題，以及 version vectors 在並行寫入偵測中的應用。

為什麼需要複製#

複製（Replication） 是指將相同的資料保存在多台透過網路連接的機器上。複製的主要目的有三個：

• 降低延遲：讓資料在地理上靠近使用者
• 提高可用性：即使部分節點故障，系統仍能繼續運作
• 擴展讀取吞吐量：讓更多機器能處理讀取請求

如果資料不會改變，複製很簡單——複製一次就好。所有困難都在於處理資料的變更。本章討論三種主要的複製演算法：single-leader、multi-leader 與 leaderless 複製。

Leaders 與 Followers#

最常見的複製方式是 leader-based replication（又稱 active/passive 或 master-slave 複製）。運作方式如下：

• 其中一個副本被指定為 leader（master/primary），所有寫入請求都必須送往 leader
• 其他副本稱為 followers（read replicas/slaves/secondaries/hot standbys），leader 將資料變更以 replication log 或 change stream 的形式傳送給 followers
• 讀取可以從 leader 或任何 follower 執行，但寫入只能由 leader 處理

許多關聯式資料庫（PostgreSQL、MySQL、Oracle Data Guard、SQL Server AlwaysOn）和非關聯式資料庫（MongoDB、RethinkDB、Espresso）都內建這種複製機制。分散式訊息佇列如 Kafka 和 RabbitMQ 也使用類似架構。

同步與非同步複製#

複製可以是同步（synchronous） 或非同步（asynchronous） 的，這個選擇對系統行為有深遠的影響。

同步複製的優點是 follower 保證擁有與 leader 一致的最新資料副本。如果 leader 故障，資料仍可從 follower 取得。缺點是如果同步 follower 沒有回應（可能因為當機、網路問題或其他原因），寫入就無法完成，leader 必須阻塞等待。

實務上，通常採用 semi-synchronous 的配置：一個 follower 為同步，其餘為非同步。若同步 follower 變慢或不可用，就將另一個非同步 follower 改為同步。這確保至少兩個節點（leader 加上一個同步 follower）擁有最新資料。

在實務中，完全同步複製很少使用，因為任何一個節點的故障都會導致整個系統停擺。通常所謂的「同步複製」其實是 semi-synchronous。

完全非同步複製則是最常見的配置。即使所有 follower 都落後了，leader 仍可繼續處理寫入。缺點是如果 leader 故障且無法恢復，尚未複製到 follower 的寫入就會永久遺失——即使客戶端已收到寫入成功的確認。

設定新的 Follower#

當需要增加新的 follower 時（無論是為了增加副本數量還是替換故障節點），必須確保新 follower 擁有 leader 的精確資料副本。簡單地複製檔案是不可行的，因為資料隨時在變化。鎖定資料庫也不符合高可用的目標。流程如下：

1. 在某個時間點對 leader 的資料庫取得一致性快照（snapshot），且不需要鎖定整個資料庫（大多數資料庫都支援此功能）
2. 將快照複製到新的 follower 節點
3. Follower 連接到 leader，請求快照時間點之後的所有資料變更（快照需關聯到 leader replication log 中的精確位置，如 PostgreSQL 的 log sequence number 或 MySQL 的 binlog coordinates）
4. Follower 處理完積壓的資料變更後，即追上 leader，可以正常處理後續變更

處理節點故障#

系統中的任何節點都可能故障（可能是意外，也可能是計畫性維護）。能夠在不停機的情況下重啟個別節點是運維上的重大優勢。

Follower 故障：追趕復原（Catch-up Recovery）

每個 follower 都在本地保存了從 leader 收到的資料變更日誌。如果 follower 當機後重啟，它可以從日誌中得知故障前最後處理的交易，然後向 leader 請求之後的所有變更，逐一套用直到追上 leader。

Leader 故障：故障轉移（Failover）

Leader 故障的處理更加複雜，需要執行 failover：某個 follower 需要被提升為新的 leader，客戶端需要重新配置以將寫入送往新 leader，其他 follower 也需要開始從新 leader 消費資料。Failover 可以手動或自動進行。

自動 failover 的步驟：

1. 判定 leader 已故障：通常使用 timeout——如果節點在一定時間內（如 30 秒）未回應，就認定它已失效
2. 選擇新 leader：可透過選舉流程或由事先指定的 controller 節點指派。最佳候選人通常是擁有最新資料的 follower
3. 重新配置系統：客戶端將寫入導向新 leader，其他 follower 從新 leader 取得資料。如果舊 leader 恢復，系統需確保它成為 follower

Failover 充滿潛在風險：

• 非同步複製中，新 leader 可能未收到舊 leader 的所有寫入。若舊 leader 恢復，這些未複製的寫入通常被直接丟棄，可能違反客戶端對持久性的期望
• 丟棄寫入特別危險的情況：若其他儲存系統與資料庫內容有協調關係（例如 GitHub 事件中，MySQL 自增主鍵與 Redis 快取不一致，導致私人資料外洩）
• 在某些故障場景下，兩個節點可能都自認為 leader（split brain），如果沒有衝突解決機制，可能導致資料遺失或損壞
• 設定多長的 timeout 才能判定 leader 已故障？太長會增加恢復時間，太短可能造成不必要的 failover（例如暫時性負載尖峰或網路問題）

這些問題沒有簡單的解決方案，因此有些運維團隊寧願選擇手動 failover。

複製日誌的實作方式#

Leader-based 複製底層有多種實作方式：

Statement-based replication：Leader 將每個寫入語句（INSERT、UPDATE、DELETE）記錄並轉發給 followers。但有許多問題：非確定性函式（如 NOW() 或 RAND()）會在不同副本產生不同值、語句依賴既有資料的順序可能不同、有副作用的語句（觸發器、預存程序、使用者自訂函式）可能在不同副本產生不同結果。

Write-ahead log（WAL）shipping：Leader 將 WAL（append-only 的位元組序列）傳送給 followers。PostgreSQL 和 Oracle 都使用此方法。缺點是 WAL 的格式非常底層——描述的是哪些磁碟區塊的哪些位元組發生了變更，因此與儲存引擎緊密耦合。如果 leader 與 follower 的資料庫版本不同，WAL 格式可能不相容，使得零停機升級變得困難。

Logical（row-based）log replication：使用與儲存引擎不同的日誌格式。對於關聯式資料庫，通常是以列（row）為粒度的變更記錄。這種格式與儲存引擎解耦，因此更容易保持向後相容，也更容易讓外部系統解析（如 change data capture，將資料送至資料倉儲或建立自訂索引）。MySQL 的 binlog 就使用這種方式。

Trigger-based replication：若需要更大的彈性（如只複製部分資料、在不同資料庫之間複製、或套用衝突解決邏輯），可使用應用層的觸發器與預存程序（如 Oracle GoldenGate、Bucardo for PostgreSQL）。這種方式開銷更大、更容易出錯，但提供最大的彈性。

複製延遲問題#

Leader-based 複製在讀多寫少的工作負載中表現良好——只有一個 leader 處理寫入，但多個 follower 可以分散讀取。這種讀取擴展（read-scaling） 架構在非同步複製中效果最好，但非同步代表 follower 的資料可能不是最新的。

如果應用程式從非同步 follower 讀取，可能會看到過時資料。這種不一致是暫時的——最終所有 follower 都會追上，稱為 eventual consistency。「最終」一詞刻意模糊——正常情況下延遲可能只有幾分之一秒，但在系統接近容量上限或有網路問題時，延遲可能增加到數秒甚至數分鐘。

以下介紹三種因複製延遲導致的具體問題，以及對應的一致性保證。

讀取自己的寫入（Read-after-write Consistency）#

使用者寫入資料後，如果立即讀取，可能從尚未反映該寫入的 follower 讀取，看起來就像資料遺失了。Read-after-write consistency（也稱 read-your-writes consistency）保證使用者能看到自己提交的資料。

實作 read-after-write consistency 的幾種技巧：

• 對於使用者可能修改過的資料（如自己的個人檔案），從 leader 讀取；其他資料從 follower 讀取
• 如果大部分資料都可能被使用者修改，上述方法就不實用。可以追蹤最近更新時間，若距上次更新不到一分鐘，就從 leader 讀取
• 客戶端可以記住最近一次寫入的時間戳記，系統確保提供讀取的副本至少包含該時間戳記之前的所有更新。時間戳記可以是邏輯時間戳記（如 log sequence number）或實際系統時鐘
• 如果副本分布在多個資料中心，需要將請求路由到包含 leader 的資料中心

跨裝置的 read-after-write consistency 更加複雜。使用者可能在一個裝置上寫入，在另一個裝置上讀取。此時需要集中化的元資料來追蹤更新時間戳記，且若副本分布在多個資料中心，不同裝置的請求路由也需要協調。

單調讀取（Monotonic Reads）#

使用者多次讀取時，可能碰巧先從較新的 follower 讀取，再從較舊的 follower 讀取，導致看到「時間倒流」——先看到較新的資料，之後卻看到較舊的資料。

Monotonic reads 保證一旦使用者看到某個時間點的資料，後續的讀取不會看到更早時間點的資料。這比 strong consistency 弱，但比 eventual consistency 強。

實作方式之一是確保每個使用者的讀取始終從同一個副本取得（例如根據使用者 ID 的 hash 選擇副本）。如果該副本故障，則需要重新路由。

一致前綴讀取（Consistent Prefix Reads）#

這種異常涉及因果關係的違反。例如觀察者看到一段對話中的回答出現在問題之前，因為問題和回答被寫入不同的分區，而這些分區的複製延遲不同。

Consistent prefix reads 保證如果一系列寫入按照特定順序發生，任何讀取者都會以相同順序看到這些寫入。這在分片（partitioned）資料庫中是特別棘手的問題，因為不同分區獨立運作，沒有全域的寫入順序。

一種可能的解決方案是確保具有因果關係的寫入都被寫入同一個分區。

複製延遲的解決方案#

應用程式可以透過在應用層提供比底層資料庫更強的保證來解決上述問題，但這會增加應用程式的複雜度，而且容易出錯。更好的方式是由資料庫系統提供 transaction 來處理，讓應用程式開發者不必擔心這些微妙的複製問題。但在分散式資料庫中，許多系統放棄了 transaction，宣稱在分散式系統中 transaction 代價太高。後續章節將進一步討論這個問題。

Multi-Leader 複製#

Leader-based 複製有個明顯缺點：只有一個 leader，所有寫入都必須經過它。Multi-leader replication（也稱 master-master 或 active/active 複製）允許多個節點接受寫入。每個 leader 同時也是其他 leader 的 follower。

使用場景#

在單一資料中心內使用 multi-leader 通常不值得，因為增加的複雜度超過了好處。但以下場景有意義：

多資料中心運作

每個資料中心有一個 leader。在資料中心內部，使用一般的 leader-follower 複製；資料中心之間，每個 leader 將變更複製到其他資料中心的 leader。

與 single-leader 跨資料中心配置相比，multi-leader 的優勢：

離線運作的客戶端：每個裝置上有本地資料庫作為 leader，裝置間透過多資料中心式的非同步 multi-leader 複製同步。例如手機行事曆 app——CouchDB 就是為這種使用場景設計的。

協作編輯：如 Google Docs、Etherpad 等即時協作編輯工具，本質上也類似 multi-leader 複製問題——每個使用者的編輯即時套用到本地副本，然後非同步複製到其他使用者。

處理寫入衝突#

Multi-leader 複製最大的問題是寫入衝突。

例如兩個使用者同時編輯同一個 wiki 頁面的標題，分別在不同 leader 成功寫入，但在非同步複製時才偵測到衝突。相比之下，single-leader 系統中第二個寫入者會被阻塞或要求重試。

同步與非同步的衝突偵測：可以讓衝突偵測變成同步的——寫入時等待所有副本確認，但這就失去了 multi-leader 的主要優勢（允許每個 leader 獨立接受寫入）。

避免衝突：最簡單的策略是避免衝突——確保特定記錄的所有寫入都經過同一個 leader。例如讓使用者的資料永遠路由到同一個資料中心的 leader。但如果使用者移動位置或資料中心故障需要重新路由，衝突避免就會失效。

收斂至一致狀態（Convergent Conflict Resolution）：Multi-leader 複製中沒有固定的寫入順序，各副本必須最終收斂（converge） 至相同狀態。常見策略：

• 給每個寫入一個唯一 ID（如時間戳記、UUID），取最大 ID 的寫入為贏家。若使用時間戳記就是 Last Write Wins（LWW）。這很常見但容易導致資料遺失
• 給每個副本一個唯一 ID，較高 ID 的副本永遠優先。也會造成資料遺失
• 自動合併值（如將衝突的字串排序後串接）
• 保留衝突的所有資訊，由應用程式碼在事後處理（如提示使用者解決）

自訂衝突解決邏輯：大多數 multi-leader 工具允許用應用程式碼處理衝突。可以在寫入時執行（如 Bucardo 允許寫入一段 Perl snippet），或在讀取時執行（如 CouchDB 在讀取時偵測到衝突時將所有版本回傳，由應用程式或使用者解決）。

自動衝突解決是活躍的研究領域。相關技術包括：

• CRDTs（Conflict-free Replicated Data Types）：可由多使用者同時編輯並自動合理合併的資料結構，如 Riak 2.0 的資料型別
• Mergeable persistent data structures：類似 Git 版本控制，追蹤歷史並執行三方合併
• Operational transformation：Google Docs 等協作編輯使用的演算法，專為有序列表（如文字）的並行編輯設計

Multi-Leader 複製拓撲#

複製拓撲（replication topology） 描述寫入從一個 leader 傳播到其他 leader 的路徑。

三種常見拓撲：

環形與星形拓撲的問題是：單一節點故障可能中斷其他節點間的訊息流。全連接拓撲的容錯性較好，但也有自己的問題。

在全連接拓撲中，不同 leader 間的網路速度不同，可能導致某些寫入以錯誤的順序到達——「超車」了其他依賴它們的寫入。簡單的時間戳記排序不足以解決，因為時鐘無法充分同步。需要像 version vectors 這類技術來正確排序事件，但許多 multi-leader 複製系統對此的實作並不完善。

Leaderless 複製#

前面討論的 single-leader 和 multi-leader 都基於一個概念：客戶端將寫入送往一個 leader，由資料庫系統負責複製。Leaderless replication 則放棄 leader 的概念，允許任何副本直接接受客戶端的寫入。

Amazon 的內部系統 Dynamo 推廣了這種架構（注意與 DynamoDB 不同），因此也稱為 Dynamo-style 資料庫。Riak、Cassandra 和 Voldemort 都採用這種模型。

當節點不可用時的寫入#

在 leaderless 系統中，failover 不存在。客戶端直接將寫入送往多個副本。假設三個副本中有一個不可用——客戶端只要收到兩個副本的確認，就認為寫入成功，忽略不可用的那個。

當不可用的節點恢復後，它的資料是過時的。解決方式是客戶端不是從一個副本讀取，而是平行從多個副本讀取。透過版本號判斷哪個值較新。

有兩種機制確保最終所有副本的資料一致：

• Read repair：客戶端讀取時偵測到過時的值，就將新值寫回過時的副本。適合經常被讀取的資料
• Anti-entropy process：背景程式持續檢查副本間的資料差異，將缺少的資料從一個副本複製到另一個。與 leader-based 複製不同，此程式不保證特定的複製順序，可能有顯著延遲

Quorum 讀取與寫入#

若有 n 個副本，寫入需要 w 個節點確認成功，讀取需要查詢 r 個節點。只要 w + r > n，就能保證讀取時至少能取得一個包含最新值的節點。

常見設定為 n = 3, w = 2, r = 2。可以根據需求調整 w 和 r 的比例：

• 寫少讀多的工作負載：設定 w = n, r = 1，讀取更快但寫入只要一個節點故障就會失敗
• 一般而言，只要 w + r > n 就能容忍一定數量的不可用節點

即使滿足 w + r > n，仍有邊界情況可能回傳過時值：

• 使用 sloppy quorum 時，w 個寫入和 r 個讀取可能落在完全不同的節點上
• 兩個寫入同時發生，無法確定先後順序。若使用 LWW 合併，時鐘偏差可能導致寫入遺失
• 寫入與讀取同時發生，寫入可能只反映在部分副本上
• 寫入在部分副本成功但其他副本失敗（例如磁碟已滿），成功的副本不會回滾。後續讀取可能拿到或拿不到這次寫入的值
• 攜帶新值的節點故障，從攜帶舊值的副本恢復，使得擁有新值的副本數低於 w

因此 Dynamo-style 資料庫通常針對最終一致性而非 strong consistency 進行最佳化。

Sloppy Quorum 與 Hinted Handoff#

在大型叢集中（節點數遠大於 n），客戶端在遇到網路問題時可能無法連接到任何指定的 n 個節點。此時有兩個選擇：

• 對所有無法達成 quorum 的請求回傳錯誤
• 接受寫入，並暫時將其寫入不在指定 n 個節點之中的其他可達節點——這就是 sloppy quorum

Hinted handoff：當網路問題解決後，暫時接受寫入的節點會將資料傳回「正確」的節點。

Sloppy quorum 有助於提高寫入可用性——只要有任何 w 個節點可用就能寫入，不必一定是原本指定的那些節點。但這意味著即使 w + r > n，也不能保證讀取到最新值，因為最新值可能暫時存在於 n 以外的節點上。

多資料中心的 Leaderless 複製#

Cassandra 和 Voldemort 在 leaderless 模型中實作了多資料中心支援。n 個副本分布在多個資料中心，客戶端的寫入送往所有副本，但只等待本地資料中心的 quorum 確認。跨資料中心的複製在背景非同步進行。

偵測並行寫入#

在 Dynamo-style 資料庫中，多個客戶端可能同時寫入同一個 key，造成衝突。即使使用 strict quorum，也可能因為事件的不同到達順序而發生衝突。

Last Write Wins（LWW）#

一種衝突解決方法是給每個寫入加上時間戳記，取最新的為準——Last Write Wins。Cassandra 是唯一推薦使用此策略的資料庫，Riak 則作為可選設定。

LWW 的代價是持久性——若同一個 key 有多個並行寫入，即使都回報成功，最終只有一個會被保留，其他都會被默默丟棄。若資料遺失不可接受，LWW 不適合。安全使用 LWW 的方式是確保 key 只會被寫入一次然後視為不可變（如 Cassandra 建議使用 UUID 作為 key）。

Happens-before 關係與並行#

如何判斷兩個操作是「並行」的？關鍵不在於它們是否在物理時間上同時發生（由於分散式系統中的時鐘問題，這很難精確判定），而在於它們是否互相知道對方的存在。

• 若操作 A 發生在操作 B 之前（B 知道 A、或依賴 A、或以某種方式建立在 A 之上），則 A happens before B
• 若兩個操作都不 happen before 對方，則它們是並行的（concurrent）

此處的「並行」並非指嚴格的物理時間重疊。在分散式系統中，由於時鐘問題和網路延遲，不可能精確判斷兩個事件是否「同時」發生。我們使用的定義是：若兩個操作都不知道對方的存在，則它們是並行的，無論物理時間上的先後。

捕捉 Happens-before 關係#

以一個購物車為例，伺服器透過版本號追蹤因果依賴關係。演算法如下：

• 伺服器為每個 key 維護版本號，每次寫入時遞增，並與寫入值一起儲存
• 客戶端讀取時，伺服器回傳所有未被覆寫的值及最新版本號。客戶端讀取後才能寫入
• 客戶端寫入時，必須附帶前次讀取的版本號，並將前次讀取取得的所有值合併後一起送回
• 伺服器收到寫入時，可以覆寫該版本號及更低版本的值（因為它們已被合併到新值中），但必須保留更高版本號的值（因為那些值與這次寫入是並行的）

合併並行寫入的值#

上述演算法確保不會默默丟棄資料，但客戶端需要負責合併並行值（siblings）。這與 multi-leader 複製中的衝突解決本質上相同。

簡單的方法是取其中一個值（LWW），但這會遺失資料。以購物車為例，較合理的合併策略是取聯集（union）。但如果要支援刪除操作，就不能簡單地從資料庫刪除——必須使用 tombstone（刪除標記）來標示項目已被移除，以便在合併 siblings 時正確處理。

由於在應用程式碼中合併 siblings 複雜且容易出錯，有些系統使用專門的資料結構自動合併，例如 Riak 的 CRDTs（Conflict-free Replicated Data Types）。

Version Vectors#

上述範例假設只有一個副本。當有多個副本且沒有 leader 時，單一版本號不足以追蹤依賴關係。需要為每個副本和每個 key 維護版本號。

每個副本在處理寫入時遞增自己的版本號，同時追蹤它從其他副本看到的版本號。所有副本的版本號集合稱為 version vector（Riak 2.0 使用的是其變體 dotted version vector）。

Version vector 會隨著值在讀取時從資料庫傳給客戶端，寫入時再從客戶端傳回資料庫（Riak 稱之為 causal context）。這讓資料庫能區分覆寫與並行寫入，確保從一個副本讀取後寫回另一個副本是安全的。

Version vector 有時被稱為 vector clock，但兩者並不完全相同。簡單來說，在比較副本狀態時，version vector 是正確的資料結構。

本章總結#

複製可以服務於多個目的：高可用性、離線運作、降低延遲、擴展性。儘管目標簡單——在多台機器上保存相同資料的副本——複製在實務上卻非常複雜，需要仔細思考並行性與各種故障情境。

三種主要複製方式的比較：

複製延遲帶來的一致性問題可透過以下模型來思考：

最後，multi-leader 和 leaderless 複製中的並行寫入衝突，可以透過 happens-before 關係判斷操作的因果性，並使用 version vectors 在多副本環境中正確追蹤這些關係。