向量時鐘算法深度解析：分散式系統版本控制與衝突檢測核心機制

一、應用場景與背景

在分散式資料庫（如 Dynamo、Riak、Cassandra）中，為了高可用與分區容錯，常採用**多主複製**架構：多個節點同時接受寫入，資料最終一致性透過背景同步實現。但並發寫入會導致版本衝突，例如：

• Client A 寫入 Node 1：price = 5888
• Client B 幾乎同時寫入 Node 2：price = 6888
• 同步時兩節點版本不一致，系統需判斷哪個更新更新、是否衝突

向量時鐘是解決此類問題的經典算法，提供**因果關係追蹤**與**衝突檢測**能力。

二、核心概念：向量時鐘結構

假設叢集有 N 個副本節點，每個資料項攜帶一個 N 維向量：

VC = [Node_A: v_A, Node_B: v_B, Node_C: v_C, ...]

• 每個維度對應一個節點的**邏輯時鐘**（單調遞增計數器）
• 初始狀態：[A:0, B:0, C:0]

三、版本演進完整演示

四、向量時鐘比較規則

給定兩向量 VC1、VC2，逐維度比較：

• VC1 先於 VC2（VC1 < VC2）：∀i, VC1[i] ≤ VC2[i] 且 ∃j, VC1[j] < VC2[j]
• VC2 先於 VC1：∀i, VC2[i] ≤ VC1[i] 且 ∃j, VC2[j] < VC1[j]
• 並發/衝突：∃i,j 使 VC1[i] < VC2[i] 且 VC1[j] > VC2[j]（如步驟 9：B 維度 2>1，C 維度 0<1）
• 相等：所有維度相等

五、同步合併規則

節點收到遠端版本 VC_remote，本地版本 VC_local：

1. 本地落後（VC_local < VC_remote）：採用遠端值，VC 取各維度最大值
2. 本地領先（VC_local > VC_remote）：拒絕遠端版本，保持本地
3. 衝突：無法自動判斷，需上層業務或衝突解決策略介入

六、衝突解決策略

向量時鐘**僅檢測衝突，不解決衝突**。常見解決方案：

1. Last Write Wins (LWW)：引入物理時間戳 timestamp，取時間較新者。向量擴展為 [A:1,B:2,C:0, ts:123456789]。缺點：時鐘不同步可能導致資料丟失
2. 應用層語義合併：如購物車合併、集合合併（CRDT）
3. 用戶介入：呈現衝突版本讓用戶選擇
4. 讀修復 / 寫修復：讀取時發現衰減版本觸發修復；同步時檢測衝突觸發修復

七、工程實踐考量

• 向量維度 = 副本數，通常 3-5 維，不會過長
• 節點變更：新增節點需擴展向量；節點下線可保留維度或壓縮
• 儲存開銷：每個 Key-Value 額外儲存向量，可接受
• 修復時機：讀修復延遲低但可能讀到舊值；寫修復一致性強但延遲高

八、總結

向量時鐘以**每節點一個計數器**精確捕捉分散式系統中的因果關係，是最終一致性系統實現版本控制、衝突檢測的基石。理解其比較規則、合併邏輯與衝突解決策略，是設計高可用分散式存儲系統的必修課。