• 說明分散的三個動機（規模、可用性、延遲）與它帶來的根本困難（部分失效、不可靠網路、沒有全域時鐘）。

  • 比較單領導者、多領導者、無領導者三種複寫架構，以及同步／非同步複寫的取捨與複寫延遲造成的異常。

  • 設定並理解 PostgreSQL 的串流複寫與邏輯複寫（slot、hot standby、synchronous_standby_names、publication/subscription）。

  • 解釋範圍分割、雜湊分割與一致性雜湊，以及次級索引、再平衡與熱點問題。

  • 精確陳述 CAP 定理（Gilbert–Lynch 版本）、它常被誤解之處，以及 PACELC 的補充。

  • 在 Jepsen 的一致性模型地圖上定位 linearizability、sequential、causal、eventual consistency 與 serializability。

為什麼要分散，以及為什麼困難

單機資料庫在三個方向上會碰到天花板：規模（資料量或吞吐超過一台機器）、可用性（一台機器當機就全停）、 延遲（使用者分佈全球，光速往返 150 ms）。分散到多台機器解決這些問題，代價是必須面對分散式系統的三個根本事實：

  1. 部分失效：某些節點掛了、某些還活著，而你往往無法分辨「掛了」和「很慢」。

  2. 不可靠的網路：訊息可能延遲、遺失、重複、亂序；分割（partition）會發生。

  3. 沒有全域時鐘：各節點的時鐘有偏差（NTP 下常見數毫秒到數百毫秒），「先後」需要另外定義。

本章處理資料的擺放（複寫與分割）與一致性語意；第 15 章處理共識、第 16 章處理跨節點交易、第 17 章處理網路與儲存層。

複寫

複寫（replication）把同一份資料放在多個節點，目的為可用性、讀取擴展與地理延遲。難的是寫入如何在複本間同步。

單領導者（primary / standby）

所有寫入送到一個 leader，它把變更（WAL 或邏輯變更）串流給 followers；讀取可以分散到 followers。

  • 同步複寫：leader 等至少一個 follower 確認後才回報 commit——不會遺失已確認的資料，但 follower 慢或斷線會卡住寫入。 實務上用「一個同步 + 其餘非同步」（semi-synchronous）或 quorum 式的同步（PostgreSQL 的 ）。

  • 非同步複寫：leader 不等。吞吐與延遲最好，但 leader 當機時最後幾筆已確認的交易可能遺失（RPO \(> 0\)）。

  • Failover：偵測 leader 失效（timeout）\(\to\) 選出新 leader（最新的 follower）\(\to\) 重新導向客戶端。危險：腦裂（split brain）——舊 leader 其實沒死，兩個 leader 同時接受寫入。 需要 fencing（STONITH、fencing token、租約）與第 15 章的共識來安全地選主。

複寫延遲的異常（讀 follower 時）：

  • 寫完馬上讀卻看不到（需 read-your-writes：寫後一段時間內讀 leader，或帶 LSN 等待 follower 追上）。

  • 連續兩次讀結果「倒退」（需 monotonic reads：同一使用者固定讀同一個 follower）。

  • 看到回答卻看不到問題（需 consistent prefix reads：因果相關的寫入保持順序）。

多領導者

多個資料中心各有 leader，彼此非同步互相複寫；或離線裝置（手機行事曆）各自是 leader。寫入延遲低、容忍資料中心斷線， 但寫入衝突無可避免：同一列在兩地被同時修改。解法：避免衝突（依使用者固定路由到某個 leader）、 Last-Writer-Wins（以時間戳決勝，會靜默丟資料）、保留所有版本交給應用程式合併、或使用 CRDT（可交換合併的資料型別）。 PostgreSQL 16 的邏輯複寫加入 選項，讓雙向複寫不會把收到的變更再傳回去（但衝突處理仍是使用者的責任；BDR/pgEdge 等產品補上這一塊）。

無領導者（Dynamo 風格）

Amazon Dynamo（2007）、Cassandra、Riak、DynamoDB：沒有 leader，客戶端（或協調節點）把寫入同時送到 \(N\) 個複本， \(W\) 個確認即成功；讀取送到 \(N\) 個，\(R\) 個回應即可。若 \(W + R > N\)，讀寫集合必定有交集，讀到的至少有一個最新版本（以版本號或向量時鐘判斷）。 典型設定 \(N = 3, W = 2, R = 2\)。配套機制：sloppy quorum 與 hinted handoff（節點暫時不可達時先寫到別的節點，之後補回）、 read repair（讀到舊版本時順手更新）、anti-entropy（背景以 Merkle tree 比對修復）。 代價是一致性弱（即使 \(W + R > N\) 也不是 linearizable，見 Kleppmann DDIA 第 5 章的反例）、衝突需要解決。

lP3.6cmP3.6cmP3.6cm & 單領導者 & 多領導者 & 無領導者
寫入衝突 & 無 & 有，需解決 & 有，需解決
寫入延遲 & 到 leader 的往返 & 本地 leader，低 & 到 \(W\) 個複本
一致性 & 可達 linearizable（同步 + 讀 leader） & 最終一致 & 可調（\(R\)、\(W\)），通常最終一致
失效處理 & failover 複雜、腦裂風險 & 容忍資料中心斷線 & 天然容忍節點失效
代表 & PostgreSQL、MySQL、MongoDB、Kafka & 多區 PostgreSQL（BDR）、CouchDB、行事曆同步 & Dynamo、Cassandra、Riak、ScyllaDB

串流複寫（physical）：standby 以 建立，透過 walreceiver 從 primary 的 walsender 持續接收 WAL 並重播（永不結束的復原，第 11 章）。

  • Replication slot（）：primary 保留 standby 尚未取走的 WAL——standby 斷線太久會塞爆 （ 設上限）。

  • Hot standby：standby 可服務唯讀查詢；長查詢與 WAL 重播（如 VACUUM 清掉查詢仍需要的版本）衝突時，依 取消查詢，或以 讓 primary 延後清理。

  • 同步： 或 ，搭配 的等級（第 8 章）。

  • Failover 工具：Patroni（以 etcd/Consul/ZooKeeper 做領導者選舉與 fencing）、repmgr、pg_auto_failover； 讓舊 primary 不必重建就能回頭當 standby；PostgreSQL 17 的 failover slot 讓邏輯複寫在切換後延續。

  • 監控：（、）。

邏輯複寫（PostgreSQL 10+）： / ，透過邏輯解碼（）傳送列層級的變更，可跨大版本、選擇性複寫部分表或列（row filter、column list）， 用於升級、資料整合、CDC（Debezium 使用 或 ）。限制：不複寫 DDL、序列、大物件；初始同步大表耗時；衝突（如唯一鍵）會讓 subscription 停下來。

分割（sharding / partitioning）

當資料或寫入量超過單一節點，就必須把資料切分到多個節點（每個分片通常再複寫）。

  • 範圍分割：依鍵的區間（, …）。範圍查詢高效；但循序鍵（時間戳、自增 id）會把所有寫入打到同一分片——熱點。 HBase、Bigtable、CockroachDB、TiDB、Spanner 採用（自動分裂過大的 range）。

  • 雜湊分割：對鍵取雜湊再分配。負載均勻；但範圍查詢要散播到所有分片。Cassandra、DynamoDB、Citus 預設採用。 可以用複合鍵（雜湊第一部分、第二部分範圍）兼得：。

  • 一致性雜湊（Karger et al. 1997）：把雜湊空間視為環，節點與鍵都雜湊到環上，鍵歸屬順時針第一個節點；增減節點只需搬動 \(1/N\) 的資料。 搭配虛擬節點（每個實體節點在環上有數百個點）讓負載均勻。Dynamo、Cassandra、分散式快取採用。

  • 固定分區數：預先切成遠多於節點數的分區（如 Citus 預設 32 個 shard、Elasticsearch 的 shard），再平衡時整個分區搬移，不需重新雜湊。

分割後的難題：

  • 次級索引：本地索引（每個分片索引自己的資料；查詢要 scatter-gather 所有分片）vs 全域索引（依索引鍵分割；寫入要跨分片更新，需要分散式交易）。

  • 跨分片查詢與 join：盡量共置（co-locate）——以 tenant id 分割所有表，讓同租戶的 join 落在同一分片（Citus 的 distribution column）。

  • 再平衡：線上搬移分區而不中斷服務；避免「加一台機器就要重雜湊全部資料」。

  • 路由：客戶端、代理層或節點自己知道「鍵在哪」——元資料存在 etcd/ZooKeeper 之類的共識儲存。

CAP 定理

Brewer 2000 年的猜想、Gilbert 與 Lynch 2002 年的證明：在一個非同步網路中，分散式系統不可能同時保證

  • Consistency：linearizability（每個操作看起來像在某個瞬間原子地發生在單一副本上），

  • Availability：每個送到未失效節點的請求最終都得到（非錯誤的）回應，

  • Partition tolerance：網路可以任意丟訊息。

證明極簡單：分割成兩半後，一半收到寫入，另一半收到讀取；要「可用」就得回答，要「一致」就得回答新值，但訊息過不去——二選一。

  • P 不是選項：網路分割一定會發生，真正的選擇只在分割發生時的 C 或 A。「CA 系統」在分散式語境下沒有意義。

  • CAP 的 C 是 linearizability（很強），A 是「每個非失效節點都要回應」（很特殊）。ACID 的 C、一般說的「高可用（99.99%）」都不是 CAP 的定義。

  • 它只談一個暫存器的一種一致性與一種失效。Kleppmann（2015）的 Please stop calling databases CP or AP 指出：多數真實系統既不是 CAP 意義的 CP 也不是 AP。

  • PACELC（Abadi 2012）更實用：Partition 時選 A 或 C；Else（正常運作時）選 Latency 或 Consistency。 Dynamo/Cassandra 是 PA/EL；Spanner、CockroachDB 是 PC/EC；PostgreSQL 非同步複寫是 PA/EL、同步複寫偏 PC/EC。

一致性模型

「一致性」一詞在不同脈絡下有不同意思。Jepsen 的地圖把單物件／多物件的順序保證（分散式系統傳統）與交易隔離等級（資料庫傳統）放在同一張圖：

  • Linearizability：所有操作有一個與真實時間一致的全序；一旦某個讀看到新值，之後的讀都看到。單物件、單操作的最強保證。實作需要共識或同步複寫；CAP 的 C。

  • Sequential：有全序，且符合每個客戶端自己的程式順序，但不必符合真實時間。

  • Causal：只對有因果關係的操作保序；可在分割下保持可用（是「可用系統能提供的最強模型」之一）。

  • Eventual：停止寫入後，所有複本終將收斂。沒有任何關於「何時」與「中間看到什麼」的保證。

  • Serializability 談的是多物件交易的等價序列順序，不談真實時間——PostgreSQL 的 SERIALIZABLE 允許「先 commit 的交易在序列化順序中排後面」。 Strict serializability = serializability + linearizability，Spanner 的「external consistency」即此（CockroachDB 預設略弱，為 serializable 加上單鍵 linearizable）。

時間與順序

沒有全域時鐘，分散式系統以邏輯手段定義「先後」：

  • Lamport 時鐘（1978）：每個節點一個計數器，送訊息時附上、收到時取 \(\max\) 加一；若 \(a \to b\)（因果先於）則 \(L(a) < L(b)\)，反之不成立。

  • 向量時鐘：每個節點一個分量；能判定兩事件是因果相關還是並行（Dynamo 用來偵測衝突版本）。

  • 混合邏輯時鐘（HLC）：實體時間 + 邏輯計數器，接近牆上時鐘又保持因果；CockroachDB、YugabyteDB 以 HLC 做 MVCC 時間戳。

  • TrueTime：Spanner 用 GPS + 原子鐘把時鐘誤差界定在 \(\epsilon\)（約 7 ms）內，commit 時等待 \(\epsilon\)（commit wait）換取 external consistency（第 16 章）。

現代分散式資料庫的架構分類

P2.6cmP5.2cmP5.4cm 架構 & 做法 & 代表
Shared-nothing 分片 + 每分片共識 & 資料切成 range／hash 分片，每個分片一個 Raft/Paxos 群組，分散式交易跨分片 & Spanner、CockroachDB、TiDB、YugabyteDB（NewSQL）
協調者 + worker 分片 & 在既有單機資料庫上加一層路由與分散式查詢規劃 & Citus（PostgreSQL）、Vitess（MySQL）、ShardingSphere
Shared-storage / 計算儲存分離 & 單一寫入節點，WAL 送到分散式儲存層；儲存層負責複寫與頁面物化（「the log is the database」） & Aurora、Neon、AlloyDB、PolarDB
Dynamo 風格 & 無領導者、一致性雜湊、可調 quorum & Cassandra、ScyllaDB、DynamoDB、Riak
主從複寫 + 外部協調 & 傳統資料庫加 failover 管理器 & PostgreSQL + Patroni、MySQL Group Replication / Orchestrator

v7 第一步是單領導者串流複寫：leader 的 多一個 把 WAL 記錄透過 TCP 送給 follower， follower 的 寫入本地 WAL 並由 redo 程序套用（重用 v4 的復原程式碼），並開放唯讀查詢。 提供 兩種模式，量測吞吐差異；再寫一個客戶端測試「寫入後立刻讀 follower」觀察 read-your-writes 問題， 並用「附帶 LSN、等待 follower 追上」修好它。第 15 章會把選主交給 Raft。

  1. \(N = 3\)。列出 \((W, R)\) 的所有組合，指出哪些滿足 \(W + R > N\)、各自的寫入／讀取可用性（可容忍幾個節點失效）與延遲特性。

  2. 給一個 \(W + R > N\) 但讀到舊值的具體交錯（提示：寫入只在部分節點成功後失敗、或讀寫並行）。

  3. 一個以自增 id 為主鍵的訂單表要分成 16 個分片。比較範圍分割、雜湊分割、 三種設計在「寫入熱點」「查某客戶最近訂單」「查某時間區間所有訂單」上的表現。

  4. 用 CAP 的精確定義分析：PostgreSQL 單 primary + 一個同步 standby，在 primary 與 standby 之間網路分割時，系統是 C 還是 A？若改為非同步呢？若 standby 自動升級為 primary 呢？

  5. 「我們的系統是最終一致的，所以可能會讀到舊資料」與「我們的系統是 causal consistent」對一個聊天應用的差別是什麼？舉出使用者可觀察到的現象。

  6. 解釋為何 PostgreSQL 的 SERIALIZABLE 不是 strict serializable，並構造一個例子：交易 \(T_2\) 在真實時間上於 \(T_1\) commit 之後才開始，卻在序列化順序中排在 \(T_1\) 之前。

  7. （動手）用 Docker 建一個 primary + hot standby，在 standby 上執行長查詢同時於 primary 大量更新並 VACUUM，觀察 的取消行為；開啟 後再觀察 primary 的膨脹。