Vector clock — thứ tự nhân quả sự kiện
Mỗi node giữ vector đếm; so sánh vector xác định quan hệ happens-before hay concurrent. Phát hiện conflict trong hệ phân tán.
TL;DR: Đồng hồ vật lý các máy lệch nhau vài trăm millisecond — không thể dùng wall-clock để xác định thứ tự sự kiện trong hệ phân tán. Vector clock giải quyết điều này: mỗi node i giữ một vector VC[1..n], tăng VC[i] khi có sự kiện nội bộ, đính kèm VC khi gửi message, lấy element-wise max khi nhận. So sánh hai vector cho biết quan hệ happens-before (A xảy ra trước B) hay concurrent (không có thứ tự nhân quả, có thể conflict). Dynamo và Riak dùng vector clock để phát hiện sibling versions khi có concurrent write.
Trong một hệ 3 node Amazon mỗi node ở một datacenter khác nhau, đồng hồ vật lý lệch nhau 50–300 ms là bình thường. Nếu node A ghi giá trị lúc 10:00:00.200 và node B ghi lúc 10:00:00.100 theo đồng hồ mỗi máy, không thể kết luận B xảy ra trước A — đồng hồ B chạy nhanh hơn thôi. Leslie Lamport (1978) phát biểu quan hệ happens-before (ký hiệu →) để thay thế wall-clock: a → b nếu a có thể nhân quả ảnh hưởng tới b. Lamport scalar clock giải quyết một phần, nhưng khi A → B thì clock(A) < clock(B), chiều ngược lại không đúng — ta không thể phân biệt A → B với A ∥ B (concurrent). Vector clock (Fidge 1988, Mattern 1988) lấp lỗ hổng này.
1. Vấn đề: đồng hồ vật lý không đáng tin
Wall-clock drift là hiện tượng tất yếu: mỗi máy dùng thạch anh riêng, nhiệt độ và tải làm drift tích lũy. NTP đồng bộ định kỳ nhưng không đảm bảo "node A thấy timestamp 100ms trước node B là đúng thứ tự". Google Spanner dùng GPS + atomic clock (TrueTime) để giới hạn drift dưới 7ms, nhưng đó là ngoại lệ đắt tiền.
Hệ quả: nếu hai client ghi đồng thời vào Dynamo-style database (write-anywhere, no central lock), ta không biết ghi nào "cuối cùng" mà không có thêm thông tin nhân quả.
Vector clock đặt câu hỏi khác: thay vì hỏi "cái gì xảy ra lúc mấy giờ?", hỏi "cái gì có thể nhân quả ảnh hưởng cái gì?". Đây là thông tin ta thật sự có: khi node A gửi message cho node B, A chắc chắn xảy ra trước thời điểm B nhận.
2. Vector clock — cấu trúc và cập nhật
Với cụm n node, mỗi node i duy trì một vector VC kích thước n:
VC[i]= số sự kiện đã xảy ra tại nodeitheo quan sát của node này.VC[j](j ≠ i) = số sự kiện tại nodejmà nodeiđã "biết tới" (thông qua message).
Quy tắc cập nhật
-- Khởi tạo
VC[1..n] <- [0, 0, ..., 0]
-- Sự kiện nội bộ tại node i (read/write/compute)
function onLocalEvent(i):
VC[i] <- VC[i] + 1
-- Gửi message tại node i
function onSend(i, msg):
VC[i] <- VC[i] + 1 -- tăng trước khi gửi
đính kèm bản sao VC vào msg
gửi msg
-- Nhận message tại node i (nhận VC_msg từ sender)
function onReceive(i, msg, VC_msg):
for j <- 1 to n:
VC[j] <- max(VC[j], VC_msg[j]) -- element-wise max
VC[i] <- VC[i] + 1 -- tăng VC[i] sau khi hợp nhất
// Time: O(n) per event Space: O(n) per node
Trực giác element-wise max: khi node A nhận message từ B kèm VC_B, nghĩa là B đã "thấy" tất cả sự kiện mà VC_B[j] ghi nhận. Lấy max đảm bảo A hấp thụ toàn bộ kiến thức nhân quả đó.
Trace 3 node, trao đổi message
Ba làn tách riêng có chủ đích: sơ đồ xếp theo một trục dọc chung sẽ ngầm gợi ý có dòng thời gian chung — đúng thứ mà cả bài đang nói là không tồn tại. C chỉ biết tới a2 sau khi nhận được m3, không phải vì thời gian trôi qua.
Sau khi C nhận cả m2 lẫn m3, VC_C = [2,2,2] — C "biết" cả sự kiện a1, a2 của A lẫn b1, b2 của B.
Thử ngẫmnode C nhận m2 trước m3 hay m3 trước m2 không làm thay đổi kết luận VC_C cuối cùng. Điều gì trong quy tắc element-wise max khiến thứ tự nhận message không quan trọng?
3. So sánh hai vector clock — phát hiện concurrent
Cho hai sự kiện e và f với vector clock VC_e và VC_f:
function compare(VC1, VC2):
-- kiểm tra VC1 <= VC2 (mọi phần tử)
leq12 <- true
leq21 <- true
for j <- 1 to n:
if VC1[j] > VC2[j]: leq12 <- false
if VC2[j] > VC1[j]: leq21 <- false
if leq12 and not leq21: return "before" -- e → f
if leq21 and not leq12: return "after" -- f → e
if leq12 and leq21: return "equal" -- cùng sự kiện
return "concurrent" -- e ∥ f, không có thứ tự
// Time: O(n) Space: O(1)
Ví dụ:
| VC_A | VC_B | Kết quả | Ý nghĩa |
|---|---|---|---|
[2, 1, 0] | [3, 2, 1] | before | A xảy ra trước B nhân quả |
[3, 2, 1] | [2, 1, 0] | after | B xảy ra trước A |
[2, 1, 0] | [1, 2, 0] | concurrent | Không có thứ tự — có thể conflict |
[1, 2, 3] | [1, 2, 3] | equal | Cùng trạng thái |
Trường hợp concurrent là quan trọng nhất: A và B không có quan hệ nhân quả — A không "biết" về B lúc xảy ra và ngược lại. Trong database phân tán, hai concurrent write lên cùng key tạo sibling versions (conflict thật sự, không phải vấn đề clock drift).
4. Ứng dụng: phát hiện conflict trong Dynamo/Riak
Amazon Dynamo (DynamoDB predecessor, 2007) gặp vấn đề: write-anywhere + eventual consistency → hai client có thể ghi cùng key đồng thời tại hai node khác nhau, rồi khi node gossip với nhau thì có hai version.
Với vector clock:
- Mỗi version của một key được gắn VC của node đã ghi.
- Khi hợp nhất hai version: nếu
VC_A before VC_B→ giữ B (A cũ hơn). Nếu concurrent → giữ cả hai như sibling versions, trả về client để client chọn (ứng dụng-specific merge). - Riak (database dựa trên Dynamo) gọi đây là "sib resolution" — vector clock giúp biết khi nào cần hỏi application.
So sánh với Lamport scalar clock:
| Thuộc tính | Lamport scalar | Vector clock |
|---|---|---|
A → B ⟹ clock(A) < clock(B) | Có | Có |
clock(A) < clock(B) ⟹ A → B | KHÔNG | Có |
| Phát hiện concurrent | Không thể | Có (compare trả "concurrent") |
| Chi phí | O(1) per event | O(n) per event |
Lưu ý ký hiệu: với vector clock,
clock(A) < clock(B)KHÔNG phải so sánh số học. Nó là thứ tự bộ phận (partial order):VC_A[j] <= VC_B[j]với mọijvà tồn tại ít nhất mộtjmàVC_A[j] < VC_B[j]. Hai vector không so được theo quan hệ này (mỗi cái lớn hơn ở một chiều) chính là concurrent — khác hẳn<toàn phần của Lamport scalar.
Lamport clock đủ cho định thứ tự toàn phần (total order) khi cần, nhưng không phân biệt được "A xảy ra trước B nhân quả" với "A và B concurrent". Vector clock trả lời câu hỏi thứ hai.
Thử ngẫmmột node mới join cluster sau khi node khác đã có hàng nghìn sự kiện. Vector clock của node mới bắt đầu từ đâu, và nó có "biết" được các sự kiện cũ trước khi join không?
5. Pitfall
Pitfall 1 — Quên tăng VC[i] khi nhận message
-- SAI: chi lay element-wise max, khong tang VC[i]
function onReceive_wrong(i, msg, VC_msg):
for j <- 1 to n:
VC[j] <- max(VC[j], VC_msg[j])
-- DUNG: tang VC[i] sau khi hop nhat de danh dau su kien "nhan message"
function onReceive_correct(i, msg, VC_msg):
for j <- 1 to n:
VC[j] <- max(VC[j], VC_msg[j])
VC[i] <- VC[i] + 1
Bỏ VC[i] <- VC[i] + 1 sau merge khiến sự kiện "nhận message" không được ghi nhận, phá vỡ bất biến: mọi sự kiện phải làm tăng ít nhất một phần tử của vector.
Pitfall 2 — So sánh sai: dùng tổng thay vì element-wise
-- SAI: so tong cac phan tu
if sum(VC1) < sum(VC2): return "before"
-- Vi du: VC1=[3,0,0], VC2=[1,1,1] -- tong bang nhau (3=3) nhung VC1 concurrent VC2
-- DUNG: element-wise comparison (xem ham compare o tren)
Dùng tổng có thể cho kết quả sai: [3,0,0] và [1,1,1] có tổng bằng nhau nhưng thực tế concurrent — node đầu tiên có 3 sự kiện chưa truyền sang hai node kia.
Pitfall 3 — Gắn VC của lúc đọc thay vì lúc ghi
Trong Dynamo-style: VC đính kèm vào version của data, không phải session đọc hiện tại. Khi client đọc version v rồi ghi v', nó phải đính kèm VC của v để server biết v' kế thừa v. Đính kèm VC rỗng → mọi write trông như concurrent, sinh sibling vô tội vạ.
6. Liên hệ các bài khác
- Quorum — đọc/ghi đa số: Quorum đảm bảo overlap giữa read-set và write-set, nhưng khi có concurrent write trượt qua quorum, vector clock là công cụ phát hiện và gắn nhãn conflict để application xử lý sau.
- Merkle tree — kiểm tra nhất quán: Merkle tree nhanh chóng tìm node nào có data khác nhau; vector clock sau đó được dùng để xác định phiên bản nào "mới hơn" hay "concurrent".
- Consistent hashing: Quy định key thuộc node nào; vector clock giải quyết conflict khi cùng key được ghi bởi hai node coordinator khác nhau.
- Gossip protocol: Gossip là cơ chế truyền tải vector clock và version data giữa các node — hai kỹ thuật bổ trợ nhau trong kiến trúc Dynamo/Riak.
- Case study Cassandra & etcd: Thấy vector clock (và biến thể dotted version vector) được áp dụng thực tế trong Riak, cùng chiến lược last-write-wins của Cassandra (đánh đổi: mất khả năng phát hiện concurrent).
📚 Deep Dive
Bài báo gốc:
- Lamport, L. (1978) — "Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM 21(7). Định nghĩa happens-before và Lamport scalar clock — nền tảng lý thuyết cho mọi clock phân tán.
- Fidge, C. (1988) — "Timestamps in Message-Passing Systems That Preserve the Partial Ordering". Phát minh vector timestamp độc lập với Mattern.
- Mattern, F. (1988) — "Virtual Time and Global States of Distributed Systems". Song song với Fidge, công bố cùng năm.
Ứng dụng thực tế:
- DeCandia et al. (2007) — "Dynamo: Amazon's Highly Available Key-value Store", SOSP. Section 4.4 mô tả vector clock + sibling resolution. Đây là bài báo làm vector clock nổi tiếng rộng rãi ngoài giới học thuật.
Biến thể:
- Dotted Version Vectors (Preguiça et al. 2012) — giải quyết false sibling khi client không trả VC đúng; Riak 2.0 dùng. Interval Tree Clocks (Almeida et al. 2008) — không cần biết số node cố định trước.
Tóm tắt
- Wall-clock không đáng tin trong hệ phân tán — drift 50–300 ms làm mất thứ tự tuyệt đối.
- Happens-before (
→) của Lamport: quan hệ nhân quả thay cho thứ tự thời gian vật lý. - Vector clock
VC[1..n]: tăngVC[i]khi có sự kiện nội bộ hoặc nhận message; gửi kèm VC; lấy element-wise max khi nhận. - So sánh hai VC bằng element-wise: "before/after" nếu một chiều nhỏ hơn toàn phần; "concurrent" nếu mỗi chiều có ít nhất một phần tử lớn hơn.
- Concurrent = conflict thật sự (không phải vấn đề clock) → giữ cả hai sibling, để application merge.
- Lamport scalar clock rẻ hơn O(1) nhưng không phân biệt happens-before và concurrent.
Tự kiểm tra
- Q1Vì sao không thể dùng wall-clock để xác định thứ tự sự kiện giữa hai node trong hệ phân tán? Cho ví dụ cụ thể.
- Q2Giải thích quy tắc element-wise max khi nhận message. Tại sao lấy max chứ không lấy giá trị của sender?
- Q3Cho hai vector clock: VC1 = [2, 3, 1] và VC2 = [3, 1, 2]. Quan hệ của chúng là gì? Ý nghĩa thực tế là gì?
- Q4Vector clock phát hiện concurrent khác gì so với Lamport scalar clock? Khi nào chọn Lamport, khi nào chọn vector clock?
- Q5Trong Dynamo, tại sao client khi ghi phải gửi kèm VC của version đã đọc trước đó? Điều gì xảy ra nếu bỏ qua bước này?
- Q6Vector clock có n node, mỗi sự kiện tốn O(n) để cập nhật và truyền. Với cụm 1000 node thì sao? Có giải pháp nào không?
- Q7Tại sao Cassandra không dùng vector clock mà dùng last-write-wins (LWW) với timestamp? Đánh đổi là gì?
Bài tiếp theo: Gossip protocol — lan truyền trạng thái
Bài này đáng gửi cho bạn học cùng?
Copy link đã gắn nguồn — dán group, chat, hoặc LinkedIn.
Bài này có giúp bạn hiểu bản chất không?
Hỏi đáp về bài này
Chưa có câu hỏi
Có gì chưa rõ trong bài? Đặt câu hỏi đầu tiên — câu trả lời từ cộng đồng giúp bạn (và người sau).
Đặt câu hỏi đầu tiên