ref: CHAPTER 06：DESIGN A KEY-VALUE STORE.md

ref: https://tw.annas-archive.org/md5/e89be9442169fe8f89a2fda597797668

ref: https://www.youtube.com/watch?v=8TE2DvpKxvA

ref: https://youtu.be/o6q8zPmfVLU?si=M7Y-FWqM-tuORxn7

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

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

1. Key‑Value Store 基礎：資料模型、操作介面 (put / get)。
2. 擴充挑戰：從單機記憶體雜湊表 → 分散式雜湊表 (DHT)。
3. CAP 與一致性：AP / CP 系統選擇、N / W / R 仲裁參數。
4. 資料分區與複本：一致性雜湊、跨資料中心複寫。
5. 衝突處理：Vector Clock、最終一致性。
6. 容錯機制：Gossip 偵錯、Sloppy Quorum、Hinted Handoff、Anti‑Entropy & Merkle Tree。
7. 讀寫流程：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…)

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

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

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

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

(2) 分散式鍵值儲存系統：

分散式鍵值存儲（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 通常被視為必須保障的屬性。(腾讯云)

屬性兩兩組合與典型示例

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

理想情況

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

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

現實世界的分散式系統

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

1. 節點 n3 因故離線，無法與 n1、n2 溝通；
2. 若客戶端將資料寫入 n1／n2，則資料無法傳遞到 n3；
3. 若寫入 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）然後將節點和資料鍵都映射到此環上。

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

一致性雜湊的優點：

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

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

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

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

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

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

• 複製因子 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個副本，並等待回應，最後取其中最新版本後再返回，才能回覆客戶端成功。

• 延遲 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"）。
• 這種情況下，單靠時間戳無法明確判斷哪個版本為「最新」或「正確」，因為兩次寫入發生在不同節點且近乎同時。

解決衝突版本：

1. 版本控制：
   • 定義： 把每次的資料修改，全都視為資料的一個全新不可變版本。
2. 向量時鐘：
   • 為了解決誰覆蓋誰的問題。
   • 為每個資料項維護一個多維版本向量，用來判定版本間的先後或並行關係。
   • 定義：
     • 向量時鐘是與資料相關聯的一對資料，其形式為 節點(伺服器), 版本。
     • 可用來檢查某個版本是否為最新版本、是否為成功的版本、或是否與其他版本衝突。
     • 如 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

這張流程圖示範整個向量時鐘（Vector Clock）在多節點環境下，如何追蹤版本、偵測衝突並最終合併的機制。*

具體來看：

1. D1 → D2： 都是透過 Sx 來寫入， Sx 的版本計數器從 1 增到 2。
2. D3： 有一客戶端在 Sy 寫入，繼承了 Sx:2，並在 Sy 新增 Sy:1 ( 因為 Sy 第一次處理 ) ，時鐘變成 (Sx:2, Sy:1) 。
3. D4： 另一個客戶端同時在 Sz 上寫入，同樣繼承 Sx:2，並新增 Sz:1 ( 因為 Sz 第一次處理 )，時鐘變成 (Sx:2, Sz:1) 。
4. 衝突偵測： 因為 (Sx:2, Sy:1) 跟 (Sx:2, Sz:1) 彼此各有對方沒有的分量，無法互相包含，所以被判定為衝突版本。
5. D5 合併： 在 應用層 把 D3、D4 合併後，由 Sx 再寫入一次，Sx 的計數器再 +1（從 2 → 3）， 、合併後的時鐘為 (Sx:3, Sy:1, Sz:1) ，它就 包含了之前所有分量，因此成為唯一合法的後繼版本 。

「分量」這個詞在這裡其實是從數學或向量概念延伸而來，指的是向量中每個維度上的值，在向量時鐘（Vector Clock）中，這些「分量」就是每個節點的版本號。

---

🔍 為什麼叫「分量」？

數學背景：

• 向量（Vector）是一組有方向和大小的數字集合，例如 。
• 向量的每個數字（例如 1、2、3）就是這個向量在各個軸上的「分量」（components）。
• 中文中「分量」是 vector component 的翻譯。

在向量時鐘中的意義：

向量時鐘用一組 key-value 組來記錄每個節點的版本：

{
 "Sx": 2,
 "Sy": 1,
 "Sz": 0
}

Copy to clipboard

這其實就是一個多維的向量，每個節點（如 Sx, Sy, Sz）對應一個「分量」：

• Sx 的分量是 2
• Sy 的分量是 1
• Sz 的分量是 0

---

✅ 用「分量」的好處：

• 可以用來比較兩個向量時鐘是否發生衝突
• 易於理解為「每個節點對這筆資料的貢獻度（或修改次數）」

---

📘 總結：

向量時鐘中的「分量」就是： 每個節點在向量中對應的版本值。

叫它「分量」是因為這種結構本身就是一個向量，這個詞也承襲了數學中向量各個維度的稱呼。這在資料庫、分散式系統、版> 本控制等領域中是常見的術語。

---

詳細步驟說明：

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

節點故障與容錯機制：Gossip 協議、Sloppy Quorum 與 Hinted Handoff

在大型分散式系統中，節點故障是常態而非例外。 因此，我們需要機制來偵測故障以及在故障發生時維持系統的可用性。 本節介紹兩類機制：

• 故障偵測：
  • 如何讓所有節點感知彼此的存活狀態，迅速發現節點宕機或網路隔離。
    • 在分散式系統中，如果某個伺服器說另一伺服器已故障，實際上這樣並不足以認為該伺服器確實已故障。
    • 原則：至少需要有兩個獨立來源提供相同資訊，我們才能把該伺服器標記為故障。
• 故障應對：
  • 當部分節點無法服務時，如何暫時接管其職責以及在其恢復後進行數據補償。

（1）故障偵測 – Gossip 協議：

• 傳統做法： 是一個節點向全體其它節點定期發送心跳 （ all-to-all 心跳 ），但在節點很多時網絡開銷巨大。
• 改進方案是 Gossip（八卦）協議，其特點類似社交場合的流言傳播：
  • 每個節點維護一份成員列表 ( 去中心化 )
    • 記錄集群中其他節點的 ID 及其心跳計數器等資訊。
  • 時鐘1：定時（例如每隔 w 秒），表示「我還活著」。
    • 各節點獨立地每隔固定時間增加自己的心跳計數。
  • 時鐘2：定時（例如每隔 𝑡 秒），表示「刷存在感」。
    • 每個節點從成員列表中隨機選擇幾個節點，
    • 將自己的心跳資訊發送給接收者。
      • 接收者：更新對應節點的心跳值，
      • 接收者：繼續隨機節點轉發，類似病毒傳播地散播心跳消息。
  • 節點收到某成員的信息： 會更新本地成員列表，確保彼此盡量最終收斂到一致的最新成員狀態。
  • 判定失效： 若成員列表中某節點的心跳值在超過一定時間沒有增長（ 例如超過 5 個 heartbeat 週期 ），則認定該節點離線。
  • 好處：
    • 透過 Gossip 機制，整個集群能在較小網絡開銷下達成對故障節點的共識。
    • 由於採隨機對等傳播，Gossip 在大規模節點時的消息數量只線性增加且具高度冗餘，不易有單點瓶頸。
  
  圖 6-11 示範：節點 s0 偵測到節點 s2 長時間沒心跳，s0 將此資訊隨 Gossip 傳給其他節點，最終全網標記 s2 故障。

（2）臨時故障應對 – Sloppy Quorum & Hinted Handoff：

• 發現節點故障後，系統應繼續提供服務而不強制等待故障節點恢復。
• 這涉及兩個機制：
  • Sloppy Quorum（草率仲裁）：
    • 為了提高可用性，暫時放寬 Quorum 的嚴格一致性要求。 在原本需要與特定 N 個副本交互的基礎上，改為：
    • 寫入：
      • 繞過故障節點
      • 在雜湊環上選擇前 W 個運行狀良好的伺服器進行寫入，即算成功。
    • 讀取：
      • 繞過故障節點
      • 在雜湊環上選擇前 R 個運行狀良好的伺服器進行讀取，即算成功。
    • 只要存活節點數量尚 >= W 或 R，讀寫操作就不會因單節點故障而被阻斷，提高了可用性。
  • Hinted Handoff（提示換手）： 寫入因 Sloppy Quorum 被臨時寫到代管節點，如何在故障節點恢復後補回缺失的更新？
    答案是提示換手：
    • 代管寫入的節點會將針對故障節點的更新保存下來（附上「給節點 X 的資料變更」提示）。
    • 等偵測到原故障節點重新上線後，代管者再將這些更新“轉交”回原設置應儲存該資料的節點，完成補寫。
  
  圖 6-12 所示，s2 故障期間 s3 代管了本屬於 s2 的更新，當 s2 恢復時，s3 將相關資料交還給 s2。
  上述兩者的結合增強可用性
  • 在短暫節點故障期間，系統仍能對外提供近乎正常的服務。
  • 當節點恢復後又能將資料漸進糾正，實現最終一致。
  
  犧牲了一定程度的一致性保證
  • Sloppy Quorum 犧牲了一定一致性保證，可能讀不到最新寫入（ 因寫到臨時節點 ），但換來的是更高的故障容忍和持續服務能力。

（3）永久故障應對 – 防止資料長期不一致： Merkle Tree

• 如果某節點永久失效（ 例如硬碟損毀無法恢復數據 ），則使用上述提示換手也無法把它「喚醒」。
• 此時通常透過 反熵（Anti-Entropy）機制在存活節點間進行資料修復同步。
• 典型手段是使用 Merkle Tree（梅克爾樹，又稱雜湊樹） 來高效比較大範圍資料：
  • 透過對資料集合計算出層次化的雜湊， 以快速定位哪個區段資料不一致， 並能最小化資料傳輸。
  • Amazon Dynamo 實作基於 Merkle 樹的反熵協議，確保副本間數據一致性。

  將整個 key 空間分塊，
  (1) 各節點對每塊計算雜湊，構建一棵樹並從根比對，若根相同則所有子樹都相同；
  (2) 若根不同，則只需下探有差異的子樹分支，迅速找出不一致的鍵集合。
  (3) 找到差異後，再進行資料補償同步。
  (4) 透過定期運行 Merkle 樹比較，各副本可在後台修復長期分歧，最終達成一致。
  

  Copy to clipboard
• 維基百科 Merkle Tree

  雜湊樹（hash tree；Merkle tree），
  在密碼學及電腦科學中是一種樹形資料結構，
  每個葉節點均以資料塊的雜湊作為標籤，
  而除了葉節點以外的節點則以其子節點標籤的加密雜湊作為標籤。
  
  雜湊樹能夠高效、安全地驗證大型資料結構的內容，是雜湊鏈的推廣形式。
  

  Copy to clipboard
  
  二元雜湊樹範例。 雜湊 0-0 和 0-1 分別是資料塊 L1 和 L2 的雜湊值。 雜湊 0 是將雜湊 0-0 和 0-1 連接後所取得的雜湊值。
  https://www.youtube.com/watch?v=pRwvZzxcH2w

  ---

  🔍 Merkle 樹建構流程（舉例：鍵空間 1～12）

  🎯 說明：

  假設我們的鍵值範圍是 1 到 12，以下是如何建構出對應的 Merkle 樹。 過程中若有異常（如資料不一致），會以特別標記的方塊來呈現。

  ---

  🧩 Step 1：鍵值劃分桶子（圖 6-13）

  • 將鍵的空間平均劃分為多個「桶子（bucket）」，本例中共 4 個桶子。
  • 每個桶子會對應一棵子樹的根節點（root level node），後續用來維護這個桶內的資料結構。
  • 📌 目的： 降低單一 Merkle 樹過大，提升定位異常的效率。

  ---

  🔐 Step 2：鍵值雜湊（圖 6-14）

  • 對每個桶子內的所有鍵值進行統一的 hash 處理。
  • 這些 hash 結果將作為 Merkle Tree 的葉節點（leaf nodes）。

  ---

  🌿 Step 3：建立桶子層級的雜湊節點（圖 6-15）

  • 每個桶子產生一個對應的 hash node，代表該桶整體資料狀態。
  • 這些節點會作為上層 Merkle Tree 的中繼節點（intermediate nodes）。

  ---

  🌳 Step 4：建構最終的 Merkle 樹（圖 6-16）

  • 從每個桶子的 hash node 開始，兩兩組合並進行 hash，逐層向上建構。
  • 最終會得到一個全域的 Merkle Root，可用來表示整體系統資料的一致性狀態。

  ---

  ✅ Merkle Tree 優點整理

  特性	說明
  區域性更新	只需更新變更桶子對應的子樹及相關 hash，其他部分保持不變
  快速偵測異常	比對 root hash，若不一致即可快速縮小範圍至異常桶子
  易於擴充	桶子數可依據資料規模動態調整，適合大規模分散式系統
  應用場景	區塊鏈、分散式檔案系統（如 IPFS）、資料一致性檢查與同步機制等

  ---

只要使用 Merkle Tree 的做法，
需要同步的資料量就會與兩個副本之間的差異(而不是所包含資料量)成正比。

在實際的系統中，
桶子的尺寸有可能相當大。
舉例來說，我們可能會設定每十億個鍵對應一百萬個桶子，如此一來，每個桶子就包含 1000 個鍵。

（4）資料中心服務中斷的問題： 跨多個資料中心複製資料的做法非常重要。

📌 回顧一下

Session 3 階段內容，至此我們聚焦在分散式鍵值存儲系統中一致性與容錯挑戰

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

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

(3) 一致性：Quorum 機制與最終一致性

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

(5) 節點故障與容錯機制：Gossip 協議、Sloppy Quorum 與 Hinted Handoff

我們已構建起一個分散式鍵值存儲的完整藍圖，

涵蓋從資料分區、複製到一致性維護、故障處理的各方面。

主要收穫包括：

• 一致性模型選擇： 綜上，本系統採用最終一致性模型，強調高可用性與容錯。但我們也提供參數使其一致性可調（Consistency Tunable），例如客戶端可根據需求選擇不同 R、W 配置來實現從弱一致到強一致的切換。
• 調節一致性的策略： Quorum 機制允許我們通過調整 W、R 在一致性與延遲間找到平衡點。對追求最終一致性的系統，可選較小 W、R 以降低延遲；如需強一致，可設定 W+R > N。
• 衝突偵測與解決： 透過向量時鐘為每個鍵值跟蹤多副本的版本演進史，偵測並行更新造成的衝突。在需要時將多版本交由客戶端合併，確保沒有寫入被無故覆蓋或遺失。儘管增加實現複雜度，但對於高度可用系統而言，這是達成最終一致性的關鍵。
• 故障容錯機制： Gossip 協議提供去中心化且高容錯的故障偵測方案，讓集群快速達成對節點存活狀態的共識。Sloppy Quorum 和 Hinted Handoff 則在節點臨時故障時維持服務不中斷，並在其恢復後自動補齊資料，提升整體可用性。永久性故障下，借助 Merkle 樹等反熵演算法，系統能找出並同步遺失的資料片段。

📌 最後關注系統的實際架構實作

包括資料存儲引擎（寫入/讀取路徑）以及一個使用 C# + MSSQL 的簡易鍵值存儲 API 範例，並探討幾個現代鍵值存儲系統作比較。

• 系統架構圖
• 寫入途徑
• 讀取途徑

系統架構圖：整體架構與資料存儲引擎

綜合前述設計， 我們的鍵值存儲系統架構可以描述如下：

• 無中心架構（Decentralized）： 集群中無主從之分，每個節點職責相當（均可作為請求協調者、均存儲部分資料）。這避免單點瓶頸，提升可靠性。
• 請求路由： 客戶端發出的請求（讀或寫），可透過一致性雜湊機制路由到對應的節點處理。實務中通常由客戶端或中介負責計算鍵的雜湊並選擇節點，或者設置每個節點都能轉發請求到正確節點。
• 協調者： 處理請求的節點扮演協調者角色（Coordinator），充當客戶端與存儲節點之間的代理。協調者負責與副本節點通信以完成讀寫 Quorum。
• 資料存儲層： 每個節點本地維護存儲引擎，包括記憶體快取（memtable）與磁碟資料檔（如 SSTable）等，用以快速存取和持久化資料。為性能，經常採用基於日誌的結構存儲（LSM Tree） 模型。
• 組件回顧：
  • 分區：一致性雜湊確定資料歸屬節點，支撐水平擴展。
  • 複製：多副本存放與跨機房配置保證高可用。
  • 一致性：Quorum 共識 + 調整 R/W 保證讀寫一致性。
  • 衝突解決：向量時鐘 & 客戶端合併應對並發更新。
  • 故障處理：Gossip 偵測 + Sloppy Quorum / Hinted Handoff 保證系統容錯與最終一致。

圖 6-17 為系統架構示意，展示了沒有中央控制節點下，各節點如何透過雜湊環、複製和協調機制協同工作：

圖 6-18 為分散式鍵值存儲系統的每個節點，去中心化的示意圖。

接下來重點說明 資料寫入與讀取路徑在節點內的處理流程，這對性能和可靠性至關重要。

寫入途徑：資料寫入路徑（Write Path）

對於來自客戶端發出的每一次寫入請求， 經路由到正確節點後， 主要執行以下步驟（借鑑 Apache Cassandra 的實作）：

1. 提交日誌 (Commit Log)： 協調節點首先將寫操作記錄追加到提交日誌文件中。這是一個有序寫入的預寫日誌，確保即使隨後節點崩潰，重啟時也能從日誌重放恢復未刷入的資料。有序寫磁碟相對快速，確保每次寫入先落盤，提高資料耐久性。
2. 寫入記憶體表 (MemTable)： 同時，將此鍵值對寫入節點的記憶體快取 (memtable)。MemTable可理解為存於記憶體的排序Map結構，累積近期寫入（尚未刷盤）。
3. 確認 & 複製： 協調者等待本地（及可能其他副本）的MemTable寫入操作成功返回（達到 W 個ACK）後，即可向客戶端回覆寫入成功。這時數據已經在記憶體中，以及至少 W 個副本的提交日誌中持久化。
4. MemTable 刷盤 (Flush to SSTable)： 隨著寫入不斷進行，MemTable 佔用內存越來越大。當其大小達到預設閾值或時間週期，就觸發刷盤：把 MemTable 內容排序後寫出到磁碟上的 SSTable（Sorted String Table） 檔案。SSTable 是有序的不變（immutable）鍵值集合檔，每次刷盤生成一個新的檔案。刷盤過程同時清空該 MemTable，並打上一個新的 MemTable 寫入後續資料。
5. 檔案合併 (Compaction)：（可選）為避免 SSTable 檔過多或存在過時版本碎片，後台定期對多個 SSTable 檔案進行壓實（Compaction），合併同一鍵的多版本記錄，棄掉被覆蓋或刪除的舊版本，減少查詢開銷。

以上流程確保了寫入既快速（記憶體操作+有序日誌）又安全（日誌在先，防故障丟失）。Cassandra 寫路徑的設計容許高吞吐的隨機寫操作，並通過後續順序刷盤優化磁碟訪問。

實現提示： 寫路徑強調先寫日誌再寫內存，這與傳統關係資料庫 WAL + Buffer Pool 機制類似，稱為「先寫日誌」策略。這樣在crash時，可重播日誌保障資料不丟。Cassandra也採此法確保即使節點故障重啟，提交日誌能恢復自上次flush後失去的資料。

讀取途徑：資料讀取路徑（Read Path）

讀取請求的流程相對直觀， 但需處理資料可能分散在記憶體和多個磁碟檔的情況。節點接到讀取某鍵的請求後：

1. 查詢 MemTable： 優先在記憶體快取中查找該鍵。如果命中（資料尚未刷盤，存在於最新 MemTable），直接返回值，讀取結束。這是最快的情況（O(1)雜湊查找，無磁碟IO）。
2. 查詢 Cache 未命中： 若鍵不在記憶體中（MemTable miss），說明資料要麼在舊的 SSTable 檔，要麼此鍵根本不存在。此時進入磁碟查找流程。

3. Bloom Filter 篩選： 為了避免遍歷所有 SSTable 檔案查找，可以使用Bloom Filter為每個 SSTable 加一層索引。Bloom Filter 是一種空間高效的機率型資料結構，可快速測試「某鍵是否不在某檔案」。每個 SSTable 存有對應的 Bloom Filter，當查找鍵K時，先讓 Bloom Filter 判斷該 SSTable 是否可能包含 K。
   • 如果 Bloom Filter 判定「不可能在此 SSTable」，則可直接跳過該檔案。
   • 若判定「可能存在」，才去該 SSTable 中透過檔內索引（二分搜尋等）實際查找。
   • 透過Bloom Filter，可以大幅減少不必要的磁碟IO。例如某鍵可能僅存在最新幾個檔案，Bloom Filter 將排除大部分與該鍵無關的檔案。
4. SSTable 查找： 對於Bloom Filter結果為可能包含的那些 SSTable，打開檔案（典型為有序IO），利用其內部稽核（如稀疏索引或B樹索引）定位鍵的位置，讀出對應的值。由於SSTable內記錄有序，可以較快速地找到鍵。
5. 數據返回與合併： 如果從多個副本節點讀取（R>1情況），協調者會收到多份值，需比較其版本（例如 vector clock 或時間戳）選擇最新的結果返回給客戶端。如果偵測到版本衝突（如之前所述出現多版本），則返回所有版本讓客戶端處理。
6. 讀取快取： 讀取完成後，可將該鍵結果存入頁面快取或鍵值快取，下次相同鍵訪問時直接命中，提高熱點讀性能。

總結來說， 讀路徑的優化重點在於記憶體命中優先， 其次透過Bloom Filter減少磁碟掃描範圍。

經過這些步驟， 大部分讀請求可在 O(1) 時間返回（記憶體命中）或以少量有序 IO 完成。 Bloom Filter 雖有極小機率誤判（回傳“可能存在”實際沒有），但不影響正確性，只是多一次空查找，而且誤判率可透過調整位元數控制。

Session 3 各個組件環環相扣關係的架構圖：

1. 起點：分散式需求

• 從單機無法滿足的需求出發（大容量、高可用、可擴展）

2. 基礎設計：資料分區與複製

• 資料分區：使用一致性雜湊將資料均勻分散到多個節點
• 資料複製：每份資料保存 N 個副本，確保可用性
• 兩者相輔相成：分區決定資料位置，複製保證容錯

3. 衍生挑戰：一致性問題

• 多副本帶來一致性挑戰
• CAP 定理迫使我們在 AP 和 CP 之間選擇
• 選擇 AP 系統（最終一致性）以保證高可用

4. 解決方案：一致性與衝突處理

• Quorum 機制：通過 N/W/R 參數調節一致性級別
• 向量時鐘：檢測並解決並發更新造成的版本衝突

5. 進階挑戰：節點故障

• 故障偵測：Gossip 協議去中心化地發現故障節點
• 臨時故障：Sloppy Quorum + Hinted Handoff 維持服務
• 永久故障：Merkle Tree 進行資料修復

6. 最終實現：完整系統架構

• 系統架構：去中心化設計，協調者模式
• 寫入路徑：Commit Log → MemTable → SSTable
• 讀取路徑：MemTable 優先，Bloom Filter 優化
• 節點內部：LSM Tree 結構，後台 Compaction

環環相扣的特點：

1. 因果關係明確：每一層的設計都是為了解決上一層帶來的問題
2. 相互依賴：各組件不是獨立存在，而是共同構成完整系統
3. 持續優化：系統運行中的經驗會反饋到各層設計的改進

這個架構展示了分散式鍵值儲存系統設計的完整思路，從需求出發，逐步解決各種挑戰，最終形成一個高可用、可擴展的系統。

第六章 總結

經過三個階段的講解，我們完整覆蓋了分散式鍵值存儲系統從原理到實作的方方面面：

• Session 1： 理解了鍵值資料庫的基本定義。
• Session 2： 單機實現方式，以及擴展到分散式系統時需要面臨的 CAP 抉擇。
• Session 3： 從資料分區/複製方法，到深入探討了為實現高可用而採取最終一致性的系統中，如何利用 quorum 共識調節一致性、用向量時鐘來侦測和解決衝突版本、用 Gossip 和 Hinted Handoff 等機制來實現故障容忍與自癒。並闡述了實際系統架構下資料讀寫的具體流程（MemTable+SSTable 和 Bloom Filter 等實作細節）。此外，我們將該系統與當今主流方案進行了對比，理解不同系統在 CAP 取捨和架構設計上的演進。

整章核心要點回顧： (對照下表)

• 為處理海量資料：採用分區/一致性雜湊分散鍵到多節點。
• 提供高可用讀取：透過多副本複製，甚至跨機房部署。
• 支撐高可用寫入：允許最終一致，使用向量時鐘進行版本控制與衝突解決。
• 可線性擴展：增加節點透過一致性雜湊自動攤平負載，虛擬節點支持異構性。
• 容忍臨時故障：採用 Sloppy Quorum + Hinted Handoff 技術保證服務不中斷。
• 應對永久故障：利用 Merkle Tree 進行反熵同步。
• 跨域高可用：多資料中心複製與故障轉移策略，保障局部機房宕機時系統整體仍存活。

C# 最小鍵值存儲 API 實作範例

下面我們將實作一個簡化的鍵值存儲服務，使用 C# (.NET 8 Minimal API) 提供 HTTP 接口，並以 MSSQL 資料庫作為持久層。此範例展示鍵值存儲的核心功能，包括資料的寫入、讀取和版本管理對應我們前述章節的概念。

資料表設計： 在 MSSQL 中建立一張 KeyValueStore 表：

CREATE TABLE KeyValueStore (
    [Key]   NVARCHAR(256) NOT NULL PRIMARY KEY,
    [Value] NVARCHAR(MAX) NULL,
    [Version] INT NOT NULL DEFAULT 0
);

• Key 欄位作為主鍵存放鍵名稱。
• Value 欄位存放字串類型的值（實務中可用 VARBINARY(MAX) 存放二進位資料)。
• Version 欄位記錄此鍵的版本號，用於簡單實現版本控制（每次更新遞增版本）。這對應前述向量時鐘的概念縮減版：我們僅用單一整數表示版本，雖無法處理多副本並發，但可用於樂觀鎖防止寫入覆蓋較新更新。

接著，我們使用 .NET 8 Minimal API 建立 HTTP 介面，包含 PUT（寫入/更新鍵）與 GET（讀取鍵）兩種操作：

using Microsoft.Data.SqlClient;
using Dapper;

var builder = WebApplication.CreateBuilder(args);
var app = builder.Build();

// Database connection string (modify as appropriate for your environment)
string connString = builder.Configuration.GetConnectionString("KeyValueDb");

// 1. GET endpoint: retrieve value by key
app.MapGet("/kv/{key}", async (string key) =>
{
    const string sql = "SELECT [Value], [Version] FROM KeyValueStore WHERE [Key] = @Key";
    await using var conn = new SqlConnection(connString);
    var result = await conn.QueryFirstOrDefaultAsync<(string Value, int Version)>(sql, new { Key = key });
    if (result.Value == null)
    {
        return Results.NotFound($"Key '{key}' not found");
    }
    // Return the value and version (as ETag header for concurrency control, e.g.)
    return Results.Ok(new { Key = key, Value = result.Value, Version = result.Version });
});

// 2. PUT endpoint: insert or update a key-value
app.MapPut("/kv/{key}", async (string key, string value) =>
{
    await using var conn = new SqlConnection(connString);
    // Try update first
    const string updateSql = @"
        UPDATE KeyValueStore
        SET [Value] = @Value, [Version] = [Version] + 1
        WHERE [Key] = @Key;
        SELECT @@ROWCOUNT;";
    var rows = await conn.ExecuteScalarAsync<int>(updateSql, new { Key = key, Value = value });
    if (rows == 0)
    {
        // If key not exists, insert new record
        const string insertSql = "INSERT INTO KeyValueStore([Key],[Value],[Version]) VALUES(@Key, @Value, 0);";
        try
        {
            await conn.ExecuteAsync(insertSql, new { Key = key, Value = value });
        }
        catch (SqlException ex) when (ex.Number == 2627) // PK violation
        {
            // Handle race condition: key was inserted by another request in the meantime
            return Results.Conflict($"Key '{key}' was inserted by another client.");
        }
    }
    return Results.NoContent();
});

app.Run();

上述程式碼說明：

• 我們使用 Dapper 輕量ORM來執行 SQL 查詢，方便地將結果映射為 C# 型別。
• 查詢 (GET)：透過主鍵查詢資料庫，若找到則返回 JSON，包括鍵和值以及版本號。版本號可以透過 HTTP ETag 頭返回，供客戶端做併發控制（比如更新時帶回去作條件比對）。
• 更新/插入 (PUT)：先嘗試執行 SQL UPDATE 語句（利用 @@ROWCOUNT 判斷是否有行受影響）更新現有記錄的值，並將版本 Version = Version + 1。若 UPDATE 返回影響行數為0，表示該鍵不存在，進而嘗試執行 INSERT 新記錄。考慮到可能出現併發（兩請求幾乎同時插入同一鍵導致一方PK衝突），捕獲 PK 違規錯誤號2627並返回衝突結果，提醒客戶端該鍵已被其他請求寫入。
• 整個 PUT 操作未使用顯式交易（Transaction），但由於我們先嘗試 UPDATE 再 INSERT，兩步間依然有極小窗口可能導致重複插入。因此以 try-catch 捕捉 PK 衝突視為最終一致性下的衝突解決之一種：這裡簡單地告知客戶端衝突，由客戶端決定後續（類似 Dynamo 讀合併寫回模式）。

對應章節概念： 這段程式碼體現了數個我們在前面討論的概念：

• Hash Table 存儲：我們以資料庫表的 PK 索引模擬鍵值對的 O(1) 查找，類似單機 HashTable。
• 持久化與 WAL：SQL 資料庫本身在執行 UPDATE/INSERT 時已使用WAL日志確保原子性，我們不需另寫文件日誌。但原理類似我們在寫路徑中強調的先寫提交日誌。
• 版本號/衝突控制：我們透過 Version 欄位實現版本控制，每次更新+1。這與向量時鐘理念類似但簡化為單一節點序號，用於檢測並發更新：若多客戶端同時讀取同一版本並各自修改，我們可以藉由版本是否匹配來檢測衝突（在此例中，可在 PUT 加入 WHERE Version = X 條件保護，若版本不符則UPDATE無效，提示客戶端重試）。
• 最終一致性與衝突：我們示範了簡單的衝突處理邏輯（PK衝突時返回 409），這映射到 Session 2 談的併發寫入衝突需要協調解決的場景。
• 高可用與容錯：本範例為簡化單節點服務，未實現 Gossip 等機制。但若擴展為多節點，我們可令每個節點部署此API服務並指向各自後端（如各自的資料庫分片），客戶端透過一致性哈希選節點請求，即可形成一個去中心的分散集群。再搭配資料庫層的同步機制或上層協調，可實現我們設計的 AP 模型。
• 讀寫流程：GET 端點優先查主鍵索引、PUT 端點先寫資料庫（相當於我們設計中寫MemTable和CommitLog），兩者都體現先快取/內存再磁碟的思路。雖然我們這裡讓SQL處理細節，但對應Cassandra架構中就是遵循「內存->磁碟、先log再flush」的流程。

附註： 實務中，可用 Entity Framework Core 或其他 ORM 簡化資料訪問，這裡用 Dapper 為直觀展現 SQL 操作。另外，為專注重點，程式碼省略了一些如日誌、更多錯誤處理，以及向量時鐘多節點部分（因單資料庫難以模擬多副本場景）。但其結構已足以作為Minimal Key-Value Store服務的雛形。

現代鍵值存儲框架演進與比較 (2023–2025)

如今市面上有眾多鍵值存儲解決方案，各具不同的架構與特性。我們選取其中具代表性的 DynamoDB、TiKV、FoundationDB、etcd、Redis Cluster，結合近年演進，做一番概覽與比較：

指出：Redis/MySQL 僅本地存單副本，而 TiKV/etcd 在三個節點上存三副本（通過 Raft 協議）。這直接反映了它們在 CAP 上的取捨差異——Redis/傳統資料庫多為 CA/單機擴展模式，追求可用性但透過主從複製仍可能有不一致；而 TiKV、etcd 堅持 CP 模式，每次寫都經過多節點一致同意。

總體而言，近年鍵值存儲領域趨勢可以概括為：

• 強一致性的崛起： 在雲原生環境下，像 FoundationDB、TiKV、etcd 等強一致KV廣受關注，因為它們簡化了上層應用的邏輯（不用擔心讀到舊數據）。這些系統大都基於共識演算法（Raft/Paxos）實現，隨著網路和算法優化，其性能也逐步提高，可支持越來越大的集群和資料量。
• 最終一致性的堅守： 傳統 Dynamo 風格的 AP 系統依然在大規模場景佔有一席，例如 DynamoDB、Cassandra、Riak 等。它們在全球部署、高流量容忍方面具備獨特優勢，並且透過引入輔助功能（如 DynamoDB 提供可選強一致讀），在CAP平衡上提供更多彈性。
• 內存與持久化融合： Redis 從純內存Cache演進出 Redis Cluster、再到支援持久化AOF/快照，以及近期的Redis on Flash方案等，說明高速內存KV和持久存儲結合是需求所在。許多系統（如 TiKV 使用 RocksDB LSM 引擎）也著重壓榨硬體性能，包含NVMe、optane等新介質的應用。
• 多模與易用性： 新一代KV如 FoundationDB 主打「一個核心，多種模型」，TiKV + TiDB 則展示了將鍵值存儲升級到分散式SQL的可能。這些演進都圍繞讓開發者更容易使用鍵值存儲，同時享受分散式帶來的伸縮與可靠性優勢。

以下額外參考

資料分區：一致性雜湊

• Virtual Node、負載平均、動態擴縮
• 程式範例：ConsistentHashRing (C# /.NET 8)

public sealed class ConsistentHashRing<T>
{
    private readonly SortedDictionary<int, T> _ring = new();
    private readonly int _replicas;
    private readonly MD5 _md5 = MD5.Create();

    public ConsistentHashRing(IEnumerable<T> nodes, int replicas = 160)
    {
        _replicas = replicas;
        foreach (var node in nodes) AddNode(node);
    }

    public void AddNode(T node)
    {
        for (int i = 0; i < _replicas; i++)
        {
            var hash = Hash($"{node}-{i}");
            _ring[hash] = node;
        }
    }

    public void RemoveNode(T node)
    {
        for (int i = 0; i < _replicas; i++)
        {
            var hash = Hash($"{node}-{i}");
            _ring.Remove(hash);
        }
    }

    public T GetNode(string key)
    {
        if (!_ring.Any()) throw new InvalidOperationException("Ring is empty");
        var hash = Hash(key);
        var kv = _ring.FirstOrDefault(p => p.Key >= hash);
        return kv.Equals(default(KeyValuePair<int, T>)) ? _ring.First().Value : kv.Value;
    }

    private int Hash(string input)
    {
        var bytes = _md5.ComputeHash(Encoding.UTF8.GetBytes(input));
        return BitConverter.ToInt32(bytes, 0) & 0x7FFFFFFF; // positive int
    }
}