設計鍵值儲存系統

字數總計：0 個 | 閱讀時長：0 分鐘 |閱讀次數：次

以 C# /.NET 8 與 MSSQL 為主要範例語言／平台，分 2 – 3 次（每次 40‑50 分鐘）循序漸進講解本章重點，並輔以可執行的程式碼片段與示意圖。

整體章節重點 (Bird‑Eye View)

Key‑Value Store 基礎：資料模型、操作介面 (put / get)。
擴充挑戰：從單機記憶體雜湊表 → 分散式雜湊表 (DHT)。
CAP 與一致性：AP / CP 系統選擇、N / W / R 仲裁參數。
資料分區與複本：一致性雜湊、跨資料中心複寫。
衝突處理：Vector Clock、最終一致性。
容錯機制：Gossip 偵錯、Sloppy Quorum、Hinted Handoff、Anti‑Entropy & Merkle Tree。
讀寫流程：Commit Log → MemTable → SSTable；MemTable / Bloom Filter 多層快取。

本章要求

設計出一個可支援以下操作的鍵值儲存系統：

  - put(key, value) // 插入一組與「key」鍵相關聯的「vlaue」值
  - get(key) // 取出與「key」鍵相關聯的「vlaue」值

瞭解問題並確立設計的範圍
天底下沒有完美的設計。
每一種設計都必須在記憶體讀取、寫入與使用方面進行取捨，以達到某種特定的平衡。
在一致性與可用性之間，也需要進行權衡取捨。
- 設計的範圍設定：
  - 鍵值對的尺寸很小，小於 10 KB。
  - 有能力儲存大數據資料。
  - 高可用性：即使發生故障，系統也可以快速回應。
  - 高擴展性：系統可進行擴展，以支援大型資料集。
  - 自動擴展：應該可以根據流量，自動添加/移除伺服器。
  - 可調整系統一致性的程度。
  - 低延遲。

Session 1 ：從零開始認識 Key‑Value Store

鍵值資料庫（Key-Value Store，也稱鍵值存儲）是一種非關聯式資料庫，以 「鍵-值對」 形式儲存資料。
每筆資料由 唯一的鍵（key） 識別並對應一個 值（value），類似 Dictionary 或 Hash Table 的概念。
鍵：通常為短字串或其雜湊，須具唯一性以快速索引；
值：可以是任意類型的二進位資料，系統通常將值視為不透明的blob（例如 Redis、Memcached 即採用此模型）。
主流產品 (Redis、DynamoDB…)

alt text

Session 2 ：單機設計 v.s. 分散式挑戰

雜湊表 + 壓縮 + 冷資料落盤
何時需要走向分散式 → 大容量、高可用

單一伺服器的鍵值儲存系統：

簡單實作：
- 最直接的做法就是把「鍵值對」全部放到記憶體。
- 雜湊表（Hash Table）在記憶體中保存所有鍵值對。
- 基本操作包括 put(key, value)（寫入/更新鍵的值）與 get(key)（讀取鍵的值）。
資料結構：
- 使用如 C# 的 Dictionary<string, string> 即可達成 O(1) 的鍵查詢時間。
記憶體 vs 磁碟：
- 若資料量可能超過記憶體，可透過LRU快取策略將常用資料留在記憶體，不常用資料寫入磁碟檔案；
- 也可採用資料壓縮減少空間。
容量侷限：
- 即使有上述優化，單台伺服器的記憶體與磁碟總有上限，大規模資料最終會超出單機容量。
- 此時需要水平擴充（scale out）至分散式鍵值存儲架構。

分散式鍵值儲存系統：

分散式鍵值存儲（Distributed Key-Value Store）又稱分散式雜湊表（DHT），透過多部伺服器共同存放整體資料集。
設計分散式系統時，理解 CAP 定理極其重要。

CAP 定理簡介

CAP 定理，又稱 Brewer 定理，由 Eric Brewer 於 2000 年提出，2002 年經 Seth Gilbert 與 Nancy Lynch 形式化證明。
定理指出：在一個分散式資料存儲系統中，只能在以下三者中最多同時滿足兩項，無法兼得三者。 (腾讯云)
- 一致性 ( Consistency )、
- 可用性 ( Availability )、
- 分區容錯性 ( Partition Tolerance )

三大屬性定義

一致性 ( Consistency, C )：
- 保證每次讀取都能拿到最新的寫入值，或者返回錯誤，
- 也就是「所有節點在同一時間看到相同資料」的強一致性承諾。(腾讯云)
可用性 ( Availability, A )：
- 系統對每次請求都能在有限時間內做出響應（非錯誤或超時）。
- 即便部分節點失效，健康節點依然對外提供服務。(腾讯云)
分區容錯性 ( Partition Tolerance, P )：
- 當系統節點間發生網路分區（訊息丟失或延遲）時，仍能繼續對外提供服務。
- 由於大規模分散式系統中網路分區幾乎不可避免，P 通常被視為必須保障的屬性。(腾讯云)

屬性兩兩組合與典型示例

alt text

CA（一致性 + 可用性，放棄 P）
- 適用於無須考慮網路分區容錯的場景，
- 例如：單機或單資料中心部署的關係型資料庫系統（如 SQL Server 等）。(維基百科)
CP（一致性 + 分區容錯，放棄 A）
- 在發生分區容錯時優先保證強一致性，犧牲可用性。
- 例如：MongoDB，在分區容錯期間會拒絕服務以確保一致性。(Stack Overflow)
AP（可用性 + 分區容錯，放棄 C）
- 在發生分區容錯時優先保證可用性
- 允許短暫不一致，並透過最終一致性（Reconciliation）進行修復。
- 例如：Apache Cassandra，即使分區容錯期間也繼續響應請求，可能讀到舊值。 (Stack Overflow)

理想情況

alt text 在理想情況下，永遠不會發生網路分區容錯的問題：

寫入 n1 的資料自動就會複製到 n2、n3。
如此可達到一致性與可用性。

現實世界的分散式系統

alt text 在真實環境中，網路分區容錯的發生是不可避免的：

節點 n3 因故離線，無法與 n1、n2 溝通；
若客戶端將資料寫入 n1／n2，則資料無法傳遞到 n3；
若寫入 n3 卻未傳至 n1／n2，則後者只能保有舊版資料。

CP 系統（強一致性優先）
- 發生分區時，拒絕或延後對 n1、n2 的寫入，確保所有可用節點資料一致，犧牲可用性──
  銀行系統即屬此類，必須保證餘額一定為最新狀態。
AP 系統（可用性優先）
- 分區期間仍接受讀寫，可能返回舊資料；待網路恢復後再同步至 n3，最終達成一致。

設計取捨與面試要點 - CAP

為何必須取捨？
- 分散式系統中網路分區（P）不可避免，
- 當發生分區時，系統無法同時保證既讀取最新值(C)、又對所有請求都做出響應(A)。
- 必須在一致性與可用性間做出取捨。(ruanyifeng.com)
如何依場景選擇？
- 金融支付：對資料一致性要求極高，常選 CP ，確保交易正確無誤。(IBM)
- 社交推薦、日誌收集：對可用性和吞吐量要求優先，常選 AP 。(IBM)
- 內部管理系統：網路分區風險較低，可選 CA 以簡化設計。
面試常見考察點
1. 正確認識 C/A/P 三者含義及差異。
2. 針對不同業務場景，說明為何在 C/A/P 間做出具體取捨。
3. 以具體系統（如 Key-Value 儲存）為例，闡述如何實現 CAP（Quorum、Hinted Handoff、Anti-Entropy 等機制）。

透過以上整理，您可在系統設計面試中清晰闡述 CAP 定理，並結合業務需求給出合理架構選擇。

Session 3 ：鍵值儲存系統的構成元素

我們打算在本節討論以下這些核心元素與技術，與建構出相應的鍵值儲存系統。
以下內容主要是以三個很受歡迎的鍵值儲存系統為基礎： Dynamo、Cassandra 與 BigTable

資料分區 ( data partition )
資料複製 ( data replication )
一致性
不一致問題的解決方式
故障的處理方式
系統架構圖
寫入途徑
讀取途徑

資料分區：一致性雜湊與水平擴充

當資料規模龐大時，將全部鍵值對存於單一節點(伺服器)，是一種不可行的做法。

資料分區（data partition）： 將資料拆分到多個節點(伺服器)存放。
資料分區面臨兩大挑戰：
1. 資料均勻分布： 確保各節點負載均衡，避免有的節點存了過多資料、成為瓶頸。
2. 動態伸縮： 節點數量增加或減少時，儘量減少資料在節點間搬移的成本。

為解決上述問題
一致性雜湊（Consistent Hashing）是一種經典技術。
一致性雜湊：將整個雜湊值空間組織成一個雜湊環（Hash Ring）然後將節點和資料鍵都映射到此環上。

alt text

首先，伺服器會被放到雜湊環上。在圖 6-4 中， s0、s1、....、s7 所代表的8部伺服器全都被放到雜湊環上。
接著，有一個鍵也進行了雜湊運算，而被放到了同一個雜湊環上。
存放規則：
- 從資料鍵映射點 順時針 遇到的第一個節點，即為此鍵的負責節點。
- key0 運用存放規則的邏輯，最後保存到 s1 之中。

一致性雜湊的優點：

自動水平擴充：
- 可平滑地新增/移除節點而無需重新分配全部鍵。
- 加入節點，只需重新分配鄰近區域的一部分鍵；
- 移除節點，其負載自動攤分給鄰近節點。這滿足動態擴縮需求。
最小資料搬移：
- 新增或移除節點時，只需移動環上極少量鍵，不影響其它區段的資料。
負載均衡 ( 可因應不均勻性/異質性的問題 )：
- 結合虛擬節點機制，能讓節點根據性能配置不同數量的虛擬節點，避免因節點性能差異導致負載不均（容量越大的節點可在環上放置更多虛擬節點，獲取較大區間的鍵）。
- 例：如果某個伺服器的容量比較大，只要指定比較多的虛擬節點給它就可以了。

資料複製：高可用性的基石

為了達到高可用性與可靠性 ( relibility )

為提升系統容錯性與高可用性，分散式鍵值存儲通常將資料 複製（Replication） 至多個節點。

也就是對每個鍵值對保存多份拷貝，放置於不同節點，當部分節點故障時仍能由其他副本提供服務。

常用的複製策略如下： key0 會被複製到 s1 、 s2 、 s3 ( N=3 )

alt text

複製因子 N：就是儲存 N 份
- 每筆資料儲存 N 份（包含原始1份+ N-1份副本）
- 例如： N=3，此時系統至少需有 N 個節點才能容納所有副本。
副本選擇：必須確保節點不重複
- Key0 先按上述一致性雜湊的方式找到主存節點
- 再沿雜湊環順時針方向選擇接續的 N-1 個獨立節點作為副本存放處。
  - 例如 N=3 時，
  - key0 可存於 s1（主）以及後續的 s2、s3 節點上，共三副本。
  - 若遇到虛擬節點映射同一實體節點的情況，則跳過重複實體以確保副本分散在不同實體節點。
跨機房分佈：提高可靠性
- 為防同機房故障導致副本同時損失，通常會將 N 個副本分布在多個資料中心。
- 例如：3個副本可放在三個不同機房，透過高速網路互聯同步。

透過適當的複製策略，可以實現讀取的高可用：

即使一兩個節點故障，資料的其他副本仍可提供服務。同時多副本也提高了資料耐久性（不易因單點損毀而永久丟失）。

註：複製帶來一致性維護的挑戰 —— 當多個副本存在時，如何確保各副本的值一致，是後續「一致性」與「衝突解決」部分要解決的問題。

一致性：Quorum 機制與最終一致性

如果沒有額外措施，不同副本可能出現數據不一致（如有的收到更新，有的因網路問題未收到）。

如前所述，將資料複製到多個節點可以提高可用性，但也帶來副本間數據同步的難題。

為管理一致性，可採用 Quorum 共識機制調節讀寫操作：

定義：
- N：副本的數量 ( 如下圖 6-6，N=3 )。
- W：寫入的最低門檻，寫入操作必須至少有 W 個副本回應確認，才視為寫入成功。
- R：讀取的最低門檻，讀取操作必須等待至少有 R 個副本回應，才視為讀取成功。
運作： 以圖 6-6 為例 N=3 資料被製到 s0、s1、s2。
- 協調者 ( coordinator ) ： 代表客戶端與節點之間代理者 ( proxy ) 的角色。
- W=1： 每次寫入，協調者必須至少收到一個 ACK 確認，才能回覆客戶端成功。
  - 不代表資料只寫入1個節點
  - 如果從 s1 收到了確認，就不需要再等待 s0 與 s2 的確認了。
- W=2： 每次寫入，協調者必須至少收到二個 ACK 確認，才能回覆客戶端成功。
  - 如果從 s1 收到了確認，要再等待 s0 或 s2 的確認。
- R=2： 每次讀取，協調者會並行查詢至少2個副本，並等待回應，最後取其中最新版本後再返回，才能回覆客戶端成功。

alt text

延遲 vs 一致性：
- W、R 的選擇代表延遲與一致性的權衡。
- W或R越小：操作響應越快，但返回舊數據的風險增大。
- W或R越大：數據一致性越好，但需等待更多節點，延遲提高。
強一致性保證的條件：
- W=N + R=1 ： 就表示系統針對快速讀取進行最佳化。
- W=1 + R=N ： 就表示系統針對快速寫入進行最佳化。
- W + R > N ： 就可以具有強一致性。因為任意一筆資料的讀寫集合會在至少一個共同副本相交，確保讀一定能讀到最新寫入。(例如 N=3，W=R=2)
- W + R <= N ： 則不能保證具有強一致性。

設計取捨與面試要點 - 一致性模型

在設計鍵值儲存系統時，一致性模型確實是一個需要考慮的重要因素。

一致性模型定義的是資料一致性程度，而實際上確實存在各式各樣不同的一致性模型：

強一致性： 任何讀取操作所送回的值，都對應到最新寫入資料項的結果。客戶端絕不會看到過時的資料。
弱一致性： 後續的讀取操作有可能看到的並不是最新的值。客戶端可能不是最新的資料。
最終一致性 ( eventual consistency )： 弱一致性的殊殊形式，只要給定足夠的時間，所有資料更新終究都會被傳遞，且所有副本都會是一致的。客戶端會現是等待最新資料的過程。

在我們設計的系統中，

為了高可用性，預設採用 最終一致性 ( eventual consistency ) 模型，

即 AP 模式： 允許在短暫時間內副本之間數據不一致，但保證最終（在沒有新的更新後經過足夠時間）所有副本趨於一致。

這意味：

系統在寫入時不強制所有副本立即同步成功即可返回成功（如採用 W < N），因此短期內不同節點可能讀到舊值。
系統在背景持續同步副本，或透過讀取修復機制，確保最終各副本一致。
最終一致性容忍暫時不一致，換取故障情況下仍可接受讀/寫請求（提高可用性）。例如 Dynamo、Cassandra 即採此模型。

然而，最終一致性模型下，不可避免會出現更新衝突的問題：

當網路分區或並發寫入發生時，不同節點可能各自接受了對同一鍵的不同更新，導致系統存在多個版本的值。接下來我們將介紹如何檢測與解決這些衝突。

不一致問題的解決方式：版本控制 ( Versioning ) 與向量時鐘 ( Vector Clock )

複製：提高可用性，同時也導致副本間產生不一致的問題。
因此，我們需要一個能夠偵測衝突與協調衝突的版本控制系統。

版本控制： 把每次的資料修改，全都視為資料的一個全新不可變版本。
向量時鐘： 解決兩個版本衝突此類問題的常用技術。

版本衝突問題舉例： 圖6-7 －＞圖6-8

有 2 個副本 n1 與 n2 具有相同 key="name" 並且值相同為 "john" ，我們稱為原始值。 ( 圖 6-7 )

某刻 Client A 通過節點 n1 將 name 更新為值 "johnSanFrancisco"
同時 Client B 通過節點 n2 將 name 更新為值 "johnNewYork"
由於 A、B 幾乎同時寫入，且寫入不同節點。 2個副本各自被更新為不同值。( 圖 6-8 )

產生衝突版本：

key="name" 產生兩個衝突值： v1（值="johnSanFrancisco"）與 v2（值="johnNewYork"）。
這種情況下，單靠時間戳無法明確判斷哪個版本為「最新」或「正確」，因為兩次寫入發生在不同節點且近乎同時。

解決衝突版本：

版本控制：
- 定義： 把每次的資料修改，全都視為資料的一個全新不可變版本。
向量時鐘：
- 為了解決誰覆蓋誰的問題。
- 為每個資料項維護一個多維版本向量，用來判定版本間的先後或並行關係。
- 定義：
  - 向量時鐘是與資料相關聯的一對資料，其形式為 節點(伺服器), 版本。
  - 可用來檢查某個版本是否為最新版本、是否為成功的版本、或是否與其他版本衝突。
  - 如 D 的向量時鐘可能為 D([S1, v1], [S2, v2], ... [Sn, vn]) 。
  - S1...Sn 是參與此資料項更新的節點ID
  - v1...vn 是該節點對此資料的更新次數。
- 更新規則：
  - 每當資料 D 在某節點 Si 發生寫入
    - 如果向量時鐘中已存在 [Si, vi] ，則將 vi 加一（該節點對此資料的版本號+1）。
    - 如果不存在 [Si, vi]，則新增 [Si, 1] 條目，表示該節點首次創建此資料版本。
- 版本比較：
  - 將兩個版本的向量時鐘逐分量比較
  - 如果 版本X 的每個節點計數都 <= 版本Y 的對應計數
    - 版本X D(［S0, 1］, [S1, 1])
    - 版本Y D(［S0, 1］, [S1, 2])
    - 則 X 是 Y 的祖先版本（即 X 的所有更新都被 Y 包含，無衝突）。
  - 如果 版本X 的某幾個節點計數比 版本Y 的對應計數或大或小
    - 版本X D(［S0, 1］, [S1, 2])
    - 版本Y D(［S0, 2］, [S1, 1])
    - 則 版本X 與 版本Y 發生並行衝突（即各有部分更新彼此不包含）。
  - 目前的應用結論
    - Amazon Dynamo 就成功在生產環境使用向量時鐘並未遇到不可控的時鐘膨脹問題。
    - 向量時鐘仍是實用解決方案。

向量時鐘的缺點
透過以上機制，向量時鐘可以避免隨意覆蓋並發寫入造成的數據丟失，保留所有衝突版本供合併。值得注意的是，向量時鐘也有缺點：
- 增加客戶端複雜度：
  - 需要客戶端（或應用層）實現衝突合併邏輯，對開發者提出更高要求。
  - 一些系統（如 Cassandra）乾脆選擇更簡單的 最後寫入優先 (Last Write Wins) 策略，以縮減實現複雜度，但代價是可能捨棄較新的並發更新。
- 開銷隨節點數增加：
  - 向量時鐘裡 server:version 這樣成對資料，其數量可能會快速成長。
  - 在大規模系統中，維護數十上百的節點版本向量會增加存儲和傳輸負擔。
  - 針對長度設定了一個門檻值。超過限制長度，就會刪除掉最舊的成對資料。
  - 導致，無法正正確判斷前後代關系，造成重新協調效果不佳。

舉例： 向量時鐘是用 D([S1, v1], [S2, v2], ... [Sn, vn]) 來表式。 D ：是資料項 Sn ：是伺服器編號
vn ：是版本計數器如果把資料項 D 寫入伺服器 Si , 則系統就必須執行以下其中一個任務。
- 如果 [Si,vi] 存在， vi 就加 1。
- 否則的話，就建立一個新的項目 [Si,1] 。
- 透過向量時鐘，我們能檢測衝突版本並進一步合併。
- 以下用實際例子 ( 圖 6-9 ) 說明其工作流程：假設 N=3 節點 Sx, Sy, Sz

初始寫入： （ Sx 第1次寫入此鍵）
- 客戶端把資料項 D1 寫入系統，且這個寫入是由伺服器 Sx 來處理。
- 因此，就有了向量時鐘為 D1([Sx, 1])。
後續覆寫： （ Sx 第2次更新此鍵，取代了舊版本）
- 另一客戶端讀取了最新的 D1 ，並把它改為 D2 ，仍然是由同一部伺服器 Sx 進行寫入處理把資料寫回伺服器。
- 因此，D2 繼承自 D1，視為同一演進鏈，故 Sx 將其版本遞增為 D2([Sx, 2])。
並行更新1： （繼承了之前 Sx:2 的版本，並加入 Sy:1 ）
- 第三個客戶端讀取最新 D2，更新為 D3，
- 透過不同節點 Sy 寫入。
- Sy 不曾寫過該鍵，於是 D3 的時鐘為 ([Sx,2], [Sy,1])。
並行更新2：
- 第四個客戶端也讀取 D2（與步驟3並行），更新為 D4，
- 透過另一節點 Sz 寫入。得到 D4 的時鐘 ([Sx,2], [Sz,1])。
衝突產生：
- 現在系統內存在 D3 和 D4 兩條平行分支（皆從 D2 演化而來）。
- D3 的時鐘 [Sx:2, Sy:1] 與
- D4 的時鐘 [Sx:2, Sz:1] 互相無法比較誰包含誰（各自有對方沒有的分量），判斷為衝突版本。
- 此時若有讀取請求，
  - 系統會同時返回 D3 和 D4 兩個版本給客戶端。
  - 要求客戶端執行應用層合併（例如將兩個購物車列表合併）後提交一個最終版本 D5([Sx,3], [Sy,1], [Sz,1])。
衝突合併：
- 客戶端解析衝突得到最終結果，再寫入系統（假設透過 Sx ）。
- Sx 將合併版本 D5 的時鐘更新為 ([Sx,3], [Sy,1], [Sz,1])。
- 因為 D5 包含了之前 D3、D4 的所有分量（ Sx:3 ≥2, Sy:1 ≥1, Sz:1 ≥1 ），
- 因此 D5 被視為後繼版本，舊的 D3、D4 可被標記為過時並最終刪除。

在GitHub上在編輯此頁面

Sdi Aig設計網路限速器