分散式鍵值儲存系統#
鍵值儲存 (Key-Value Store) 對外只提供 get(key) 與 put(key, value) 兩個操作，但要做成跨資料中心、永不停機的分散式系統，背後串接了本章前幾節的所有元件：一致性雜湊 做分片、複製做冗餘、Quorum 做一致性調節、向量時鐘解衝突、Gossip 偵測故障。本節以 Dynamo 風格的設計，把這些零件組成一個端到端的系統。
CAP / BASE / 一致性模型的理論細節見 分散式系統基礎，本節聚焦「怎麼把理論落成可運作的儲存」。
特性與單機限制#
- 介面：
get(key)/put(key, value)；key 唯一，value 可為任意 blob。 - 效能取捨：短 key 較快；典型設計限制 value < 10 KB。
- 單機限制：受記憶體與磁碟容量上限約束，大資料集必須分散到多台——這就是引入分散式設計的起點（呼應 方法論與容量估算 中「30 TB/天 ➡️ 必須分片」的推導）。
CAP 取捨：CP 還是 AP#
在網路分區發生時，鍵值儲存必須在一致性與可用性間二擇一：
| 選擇 | 犧牲 | 行為 | 範例 |
|---|---|---|---|
| CP | 可用性 | 分區期間阻擋寫入以保證一致（如金融） | ZooKeeper 類 |
| AP | 一致性 | 持續接受讀寫，可能回傳舊資料，分區復原後同步 | Dynamo / Cassandra |
CA 系統在實務上不存在——網路分區無法避免，P 是必選項。Dynamo 風格的 KV 多半選 AP，再用 Quorum 與向量時鐘把一致性「調回來」。CAP 完整定義見 分散式系統基礎 — CAP 定理。
整體架構#
flowchart TB
Client(["Client"]) --> Coord["協調者節點<br/>Coordinator"]
Coord --> Ring["一致性雜湊環<br/>(分片路由)"]
Ring --> N1[("副本 1")]
Ring --> N2[("副本 2")]
Ring --> N3[("副本 3")]
Gossip["Gossip<br/>成員與故障偵測"] -.-> N1 & N2 & N3分區與複製#
- 分區 (Partitioning)：用 一致性雜湊 把 key 映射到環上，順時針找到負責節點。好處是自動擴展與異質性（容量大的節點分更多虛擬節點）。
- 複製 (Replication)：每個 key 複製到 N 個節點——從 key 的雜湊位置順時針取前 N 個不同實體節點（略過同一台的虛擬節點）。
- 為容忍整個資料中心斷電，副本應跨資料中心放置。
一致性：Quorum#
設 N 為副本數、W 為寫入仲裁數、R 為讀取仲裁數。協調者寫入時等 W 個副本確認、讀取時等 R 個副本回應。
$$ W + R > N ;\Rightarrow; \text{強一致性} $$
因為讀寫集合必然至少有一個節點重疊，該節點持有最新資料。
| 配置 (N=3) | 特性 |
|---|---|
| W=1, R=N | 寫快、讀慢 |
| W=N, R=1 | 讀快、寫慢 |
| W=2, R=2 | 平衡，且 2+2>3 ➡️ 強一致 |
| W+R ≤ N | 無法保證強一致，可能讀到舊值 |
Quorum 讓一致性變成可調參數：同一套儲存能依業務需求在「讀優化」「寫優化」「強一致」間切換，不必重寫系統。這正是 BASE / 最終一致性的工程體現，見 分散式系統基礎 — BASE 理論。
衝突解決：向量時鐘#
AP 系統允許併發寫入不同副本，會產生衝突版本。向量時鐘 (Vector Clock) 用 [server, counter] 序對追蹤因果關係：
- 寫到節點 Si 時，若已有
[Si, vi]就遞增 vi，否則新增[Si, 1]。 - 版本 X 是 Y 的祖先（無衝突）：Y 在所有節點的 counter 都 ≥ X。
- 兩版本衝突（互為 sibling）：彼此在某節點的 counter 互有大小。
向量時鐘衝突範例
1. 寫 D1 (節點 Sx) -> D1([Sx,1])
2. 讀 D1 改寫 D2 (Sx) -> D2([Sx,2]) # D2 是 D1 後代
3. 讀 D2 改寫 D3 (Sy) -> D3([Sx,2],[Sy,1])
4. 另一 client 讀 D2 改寫 D4 (Sz) -> D4([Sx,2],[Sz,1])
5. 讀到 D3 與 D4 -> 衝突! (Sy vs Sz 分歧)
6. client 解決後寫 D5 (Sx) -> D5([Sx,3],[Sy,1],[Sz,1])缺點：客戶端要實作衝突解決邏輯；序對可能膨脹，可設上限淘汰最舊項。向量時鐘屬分散式時間/因果序的應用，理論見 分散式系統基礎 — 一致性模型。
故障處理#
| 故障類型 | 機制 |
|---|---|
| 成員/失效偵測 | Gossip 協定：節點間互傳成員清單與心跳，去中心化偵測 |
| 暫時性故障 | 寬鬆仲裁 (Sloppy Quorum) + 暗示移交 (Hinted Handoff)：跳過離線節點選健康節點，恢復後把資料補回 |
| 永久性故障 | 反熵 (Anti-entropy) + Merkle 樹：比對副本，只同步差異桶，同步量正比於差異而非總資料量 |
| 資料中心故障 | 跨資料中心複製，容忍整個機房離線 |
讀寫路徑#
寫入路徑（LSM-tree 風格）：
flowchart LR
W["寫入請求"] --> CL["1. Commit Log<br/>(持久化)"]
CL --> MT["2. Memtable<br/>(記憶體)"]
MT -->|滿了 flush| SS["3. SSTable<br/>(磁碟, 有序)"]讀取路徑：
- 先查記憶體快取（命中即回）。
- 未命中 ➡️ 用 Bloom filter 判斷 key 可能在哪些 SSTable，避免無謂的磁碟讀。
- 從候選 SSTable 取出，回傳結果。
Bloom filter 與 SSTable 的延遲假設來自 方法論 — 延遲數字：SSD 隨機讀約 150 µs、磁碟尋道約 10 ms，所以「先用 Bloom filter 過濾、再讀磁碟」能省下大量無效尋道。
小結#
| 目標 | 採用技術 |
|---|---|
| 分散大資料集 | 一致性雜湊 |
| 高可用 | 多副本 + 跨資料中心複製 |
| 可調一致性 | Quorum (W + R > N) |
| 衝突解決 | 向量時鐘 |
| 增量擴展/異質 | 一致性雜湊 + 虛擬節點 |
| 暫時故障 | 寬鬆仲裁 + 暗示移交 |
| 永久故障 | Merkle 樹反熵 |
| 故障偵測 | Gossip 協定 |
| 快速讀寫 | Commit log + Memtable + SSTable + Bloom filter |
鍵值儲存是本章的集大成案例：把 一致性雜湊、複製、Quorum、向量時鐘、Gossip 組裝起來，就得到一個可水平擴展、容錯、一致性可調的儲存系統——這也是理解 Dynamo、Cassandra 等實際產品的最短路徑。