A query does not become fast merely because it has more machines. In a distributed database, the scarce resource often changes from disk I/O to network movement, coordination, or the slowest partition. Good design begins by deciding where data lives and which operations can remain local.
Parallel and distributed are related, not identical
- Parallel execution divides one operation across workers to reduce elapsed time.
- Distributed storage places data across independently failing nodes, often to scale capacity or improve availability.
- Replication keeps multiple copies for read scale or fault tolerance.
A system may run parallel queries on one shared cluster, distribute data without parallelizing a small query, or do both.
In plain terms: more workers help only when the work splits evenly and the cost of coordinating them is smaller than the time saved.
Partitioning decides what stays local
| Strategy | Good at | Main risk |
|---|---|---|
| Hash partitioning | Even distribution, equality by key | Range scans touch many partitions |
| Range partitioning | Time/range pruning | Hot recent range and skew |
| List/geographic partitioning | Administrative locality | Uneven growth |
| Random/round-robin | Bulk balance | Almost every keyed query scatters |
Choose a partition key from the dominant access path, join path, and write distribution—not from the column that merely looks unique. A tenant identifier can colocate tenant-local transactions; a timestamp can prune archival queries but concentrate current writes.
Distributed join choices
Suppose orders is partitioned and must join countries.
- Colocated join: both tables share compatible partitioning. Each worker joins locally.
- Broadcast join: send the small table to every worker.
- Repartition join: shuffle both inputs by the join key.
- Semijoin reduction: send keys first, then move only matching rows.
The optimizer needs row count, byte size, selectivity, and distribution. Average partition size is insufficient: one hot key can make a single worker dominate wall-clock time.
elapsed time ≈ max(worker time) + shuffle + coordinationThis is why a plan with excellent total CPU can still have poor latency.
Replication changes the correctness problem
Replication asks how copies agree and what happens during failure. Synchronous replication can reduce acknowledged data loss but adds write latency and may reduce availability during a partition. Asynchronous replication returns earlier but permits lag and stale reads.
The CAP result is often oversimplified. It matters specifically when the network is partitioned: the system cannot guarantee both that every response reflects a single up-to-date copy and that every request receives a successful response. Outside a partition, latency and consistency choices still matter, but “pick two” is not a complete design method.
2PC and consensus solve different problems
Two-phase commit (2PC) coordinates one atomic transaction across participants:
- Prepare: each participant promises it can commit and records that promise durably.
- Commit/abort: the coordinator announces the final outcome.
If the coordinator disappears after participants prepare, they may remain blocked until the decision is recovered.
Consensus protocols instead let a group agree on an ordered value despite some failures. A system may use consensus to replicate each shard and still use 2PC for a transaction spanning several shards. One does not automatically replace the other.
A practical design sequence
- Define the unit that must update atomically.
- Pick a partition key that keeps that unit local when possible.
- Measure data and request skew, including the hottest key.
- Price network bytes and tail latency, not only average CPU.
- State the read-consistency and data-loss contract.
- Test node loss, coordinator loss, retries, and duplicate delivery.
Review card
- Partitioning is primarily a locality decision.
- A distributed join chooses between colocation, broadcast, shuffle, and reduction.
- Tail latency follows the slowest worker, so skew matters.
- Replication adds a consistency and failure contract.
- 2PC coordinates atomic commit; consensus agrees on replicated state.
- Distribution pays off only after network and coordination costs are counted.
Query 不會因為機器變多就自然變快。在 distributed database 裡，瓶頸常從 disk I/O 轉成 network movement、coordination，或最慢的那個 partition。設計的起點是決定資料放哪裡，以及哪些 operation 能留在 local 完成。
Parallel 與 distributed 有關，但不是同一件事
- Parallel execution 把單一 operation 分給多個 worker，目的是縮短 elapsed time。
- Distributed storage 把資料放到會獨立故障的 node，通常為了 capacity 或 availability。
- Replication 保存多份 copy，用於 read scale 或 fault tolerance。
系統可以在單一 shared cluster 平行執行 query，也可以分散存放資料但不平行處理小 query，或同時做兩者。
白話來說： 只有工作切得平均，而且協調成本小於省下的時間時，多 worker 才真的有幫助。
Partitioning 決定哪些工作能留在 local
| 策略 | 適合 | 主要風險 |
|---|---|---|
| Hash partitioning | 平均分布、key equality | Range scan 會碰很多 partition |
| Range partitioning | Time/range pruning | 最新區間變 hot spot |
| List／geographic | 行政或地理 locality | 成長不均 |
| Random／round-robin | Bulk balance | 多數 keyed query 都要 scatter |
Partition key 應從主要 access path、join path 與 write distribution 選，不是挑一個「看起來很 unique」的欄位。Tenant ID 可以讓 tenant-local transaction 共置；timestamp 有助 archival pruning，卻可能把最新寫入集中在一處。
Distributed join 的選擇
假設已 partition 的 orders 要 join countries：
- Colocated join： 兩表使用相容 partitioning，各 worker 本地 join。
- Broadcast join： 把小表送到每個 worker。
- Repartition join： 兩邊依 join key shuffle。
- Semijoin reduction： 先送 key，再搬真正 match 的 row。
Optimizer 需要 row count、byte size、selectivity 與 distribution。只看平均 partition size 不夠；一個 hot key 就可能讓單一 worker 決定整體時間。
elapsed time ≈ max(worker time) + shuffle + coordination所以 total CPU 很漂亮的 plan，latency 仍可能很差。
Replication 改變的是正確性問題
Replication 要回答 copy 如何一致，以及 failure 時怎麼辦。Synchronous replication 能降低 acknowledged data loss，但增加 write latency，network partition 時也可能降低 availability。Asynchronous replication 回覆較快，代價是 lag 與 stale read。
CAP 經常被濃縮得太過頭。它特別描述 network partition 發生時：系統不能同時保證每個 response 都像來自同一份最新 copy，又保證每個 request 都成功得到 response。平時仍要處理 latency 與 consistency 選擇，「三選二」不是完整設計方法。
2PC 與 consensus 解決不同問題
Two-phase commit（2PC）協調跨 participant 的單一 atomic transaction：
- Prepare： 每個 participant durable 記錄自己能 commit 的承諾。
- Commit／abort： coordinator 宣布最後結果。
若 coordinator 在 prepare 後消失，participant 可能必須等 decision 被恢復。
Consensus protocol 則讓一組 node 在部分故障下仍能對 ordered value 達成一致。系統可以用 consensus 複寫每個 shard，再用 2PC 處理跨 shard transaction；兩者不能直接互相替代。
實務設計順序
- 定義必須 atomic update 的單位。
- 選能讓這個單位盡量 local 的 partition key。
- 量 data 與 request skew，包含最 hot 的 key。
- 計算 network bytes 與 tail latency，不只 average CPU。
- 寫清楚 read consistency 與 data-loss contract。
- 測 node loss、coordinator loss、retry 與 duplicate delivery。
複習卡
- Partitioning 首先是 locality 決策。
- Distributed join 在 colocation、broadcast、shuffle、reduction 間選擇。
- Tail latency 由最慢 worker 決定，因此 skew 很重要。
- Replication 會新增 consistency 與 failure contract。
- 2PC 協調 atomic commit；consensus 對 replicated state 達成一致。
- 把 network 與 coordination 成本算進去後，distribution 才可能真的划算。