本章涵蓋兩個系統設計模式：校驗和（Checksum） 與 向量時鐘（Vector Clocks）。

校驗和（Checksum）#

背景#

在分散式系統中，資料需要在各個元件之間傳輸。然而，從某個節點取得的資料可能在傳輸過程中損毀，損毀的原因可能來自於：

  • 儲存裝置故障
  • 網路傳輸錯誤
  • 軟體缺陷

當資料損毀發生時，系統如何確保資料的完整性，讓客戶端收到錯誤通知而非損毀的資料？

定義#

計算資料的校驗和（Checksum），並將校驗和與資料一同儲存。

解決方案#

校驗和機制的運作流程如下：

  1. 寫入時：當系統儲存資料時，計算該資料的校驗和，並將校驗和與資料一起儲存。
  2. 讀取時：當客戶端擷取資料時，驗證接收到的資料是否與已儲存的校驗和相符。
  3. 不一致時：若資料與校驗和不符，客戶端可選擇從另一個**副本（Replica）**重新取得資料。
flowchart TD
    Write([寫入資料]) --> Calc1[計算資料的校驗和\nCalculate Checksum]
    Calc1 --> Store[將資料與校驗和一同儲存\nStore Data + Checksum]

    Read([讀取資料]) --> Fetch[取出資料與儲存的校驗和]
    Fetch --> Calc2[重新計算資料的校驗和\nRecalculate Checksum]
    Calc2 --> Compare{比較校驗和\n是否一致？}
    Compare -->|一致| Intact([資料完整\nData Intact])
    Compare -->|不一致| Corrupt[偵測到資料損毀\nCorruption Detected]
    Corrupt --> Repair[從其他副本取得正確資料\nFetch from Replica]
    Repair --> Done([修復完成])

校驗和提供了一種簡單而有效的資料完整性驗證機制。在分散式系統中，由於資料會經過網路傳輸並儲存在多個節點上，校驗和能夠在每個環節確保資料未被意外修改或損毀。

實際應用#

  • HDFS 會將每個檔案的校驗和與資料一起儲存，確保資料在 DataNode 之間傳輸時的完整性。
  • Chubby 同樣會儲存每個檔案的校驗和，用於驗證資料的正確性。

向量時鐘（Vector Clocks）#

背景#

當分散式系統允許**並行寫入（Concurrent Writes）**時，可能會產生同一物件的多個版本。不同的副本最終可能持有不同版本的資料。

在單一機器上，我們可以依賴**實際時鐘時間（Wall Clock Time）**來判斷事件的先後順序：如果在時間 t1 對鍵 k 進行了一次寫入，接著在時間 t2 進行了另一次寫入，且 t2 > t1，那麼第二次寫入顯然比較新，資料庫可以安全地覆蓋原始值。

然而，在分散式系統中，這個假設並不成立。原因在於時鐘偏移（Clock Skew）：

  • 不同的時鐘往往以不同的速率運行
  • 我們無法假設節點 A 上的時間 t 一定發生在節點 B 上的時間 t+1 之前
  • **NTP（Network Time Protocol）**等時鐘同步技術無法保證完美同步
  • 除非使用 GPS 時鐘或原子鐘（Atomic Clocks），否則實際時鐘的時間戳並不足以作為事件排序的依據

在分散式環境中，單純依賴實際時鐘時間戳來判斷事件順序是不可靠的。時鐘偏移可能導致錯誤的因果關係判斷，進而造成資料不一致。

定義#

使用**向量時鐘（Vector Clocks）**來追蹤值的歷史記錄，並在讀取時調和分歧的歷史版本。

解決方案#

向量時鐘是一組**（節點, 計數器）**配對。系統為每個物件的每個版本關聯一個向量時鐘。

版本比較規則：

  • 如果第一個物件的向量時鐘中，所有節點的計數器都小於或等於第二個物件向量時鐘中對應節點的計數器，則第一個物件是第二個物件的祖先版本（Ancestor），可以被安全地丟棄。
  • 否則，兩個變更存在衝突（Conflict），需要進行調和。

衝突解決機制：

  • 衝突在**讀取時（Read-time）**解決
  • 如果系統本身無法自動調和衝突，則將所有衝突版本發送給客戶端應用程式，由應用程式決定如何合併
flowchart TD
    Start([讀取物件的多個版本]) --> Compare{比較向量時鐘\nVector Clocks}
    Compare --> Check{版本A 的所有計數器\n皆 ≤ 版本B？}
    Check -->|是| Dominant[版本A 為祖先版本\n保留版本B\nKeep Dominant Version]
    Dominant --> Done([完成])
    Check -->|否| Check2{版本B 的所有計數器\n皆 ≤ 版本A？}
    Check2 -->|是| Dominant2[版本B 為祖先版本\n保留版本A\nKeep Dominant Version]
    Dominant2 --> Done
    Check2 -->|否，兩者皆非| Concurrent[並行衝突偵測\nConcurrent Conflict]
    Concurrent --> Resolve{系統能否\n自動調和？}
    Resolve -->|是| Auto[自動合併版本\nAuto Merge]
    Auto --> Done
    Resolve -->|否| Client[回傳所有衝突版本\n給用戶端調和\nClient Reconciliation]
    Client --> Done

向量時鐘的衝突解決方式類似於 Git 處理合併衝突的模式：系統嘗試自動合併，當無法自動解決時，將衝突交由使用者（或應用程式）手動處理。

實際應用#

  • Amazon Dynamo 使用向量時鐘來調和並行更新所產生的衝突版本，確保最終一致性（Eventual Consistency）。
Backward Quorum Lease Forward