向量時鐘 (Vector Clocks)

引言：「時間」的問題

在單台計算機上，我們只有一個時鐘。如果事件 A 發生在 10:00:01，事件 B 發生在 10:00:02，我們知道 A 先於 B。

但在 分散式系統 中，伺服器的時鐘 永遠無法完全同步。如果伺服器 1 認為現在是 10:00，而伺服器 2 認為是 09:59，時間感就錯亂了。如果兩個人在不同的伺服器上編輯同一個文件，我們怎麼知道誰先誰後？還是她們是同時編輯的？

向量時鐘 提供了一種在不需要中央時鐘的情況下，追蹤 因果關係 (Causality) 的方法。

演算法要解決什麼問題？

• 輸入： 發生在不同節點上的事件。
• 輸出： 一個邏輯時間戳，用於確定一個事件是否「先於」另一個，或者她們是否是「併發」的（存在衝突）。
• 承諾： 在分散式資料庫中實現可靠的衝突檢測。

核心思想 (工作原理)

1. 向量： 每個節點都維護一個計數器列表（向量），系統中的每個節點對應一個位置：[節點A: 0, 節點B: 0, 節點C: 0]。
2. 更新： 每當一個節點執行操作時，她會增加向量中屬於她 自己 的那個計數器。
3. 同步： 當節點 A 向節點 B 發送數據時，她會帶上自己的整個向量。節點 B 接收後，會將對應的計數器都取 最大值 進行合併。

比較兩個時鐘：

• 先於 (Happened Before)： 如果向量 A 的每一項都 $\le$ 向量 B，則 A 先於 B 發生。
• 衝突 (Conflict)： 如果 A 的某些項比 B 大，而另一些項比 B 小，說明這兩個事件是 併發 發生的。我們發現了一個衝突！

典型業務場景

• ✅ 協作編輯： 確定兩個使用者是否同時編輯了同一個段落（如 Figma 或 Google Docs 的底層邏輯）。

• ✅ DynamoDB / Riak： 這些追求高可用性的資料庫使用向量時鐘來檢測同一條紀錄是否存在兩個競爭版本，並要求使用者解決衝突（讀時修復）。

• ✅ 分散式版本控制： Git 使用類似的 DAG（有向無環圖）概念來追蹤歷史紀錄。

• ❌ 超大規模集群： 如果你有 10,000 個節點，向量就會變成 10,000 維，傳輸代價太重。此時通常改用 點式版本向量 (Dotted Version Vectors)。

性能與複雜度總結

• 空間： $O(N)$，其中 $N$ 是節點數量。
• 比較： $O(N)$。

小結：一句話記住它

「向量時鐘是雲端的『邏輯計時器』。她允許我們在沒有共享時鐘的情況下，重建數據的故事，並準確識別出兩個事件是在何時發生碰撞的。」