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
sequenceDiagram
participant A as "Node A"
participant B as "Node B"
participant C as "Node C"
Note over A: "sự kiện a1: VC=[1,0,0]"
A->>B: "msg m1, VC=[1,0,0]"
Note over B: "b1 = nhận m1: VC=[1,1,0]"
Note over B: "sự kiện b2: VC=[1,2,0]"
B->>C: "msg m2, VC=[1,2,0]"
Note over C: "nhận m2: VC=[1,2,1]"
Note over A: "sự kiện a2: VC=[2,0,0]"
A->>C: "msg m3, VC=[2,0,0]"
Note over C: "nhận m3: VC=[2,2,2]"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.
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.
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ể.▸
Đồng hồ vật lý mỗi máy dùng thạch anh riêng và drift theo nhiệt độ, tải, phần cứng. NTP đồng bộ định kỳ nhưng vẫn để lại sai lệch 10–300 ms tùy điều kiện mạng. Nếu node A timestamp sự kiện lúc 10:00:00.200 và node B lúc 10:00:00.100, không thể kết luận B xảy ra trước — có thể đồng hồ B đang chạy nhanh hơn 150 ms.
Hệ quả: với drift 100 ms, hai write đến trong cùng 100 ms window đảo thứ tự tùy thuộc đồng hồ nào drift theo hướng nào. Wall-clock timestamp không phản ánh quan hệ nhân quả — chỉ phản ánh thời điểm mỗi máy tự đo, không có giá trị so sánh cross-machine tin cậy.
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?▸
Khi node A nhận message từ node B kèm VC_B, nghĩa là B đã "biết" tất cả sự kiện mà VC_B[j] ghi nhận — bao gồm cả những sự kiện B nghe từ các node khác trước đó. Lấy VC[j] = max(VC[j], VC_msg[j]) đảm bảo A hấp thụ toàn bộ kiến thức nhân quả tích lũy của B.
Nếu chỉ lấy giá trị sender, A sẽ xóa kiến thức mà A đã tự thu thập từ các source khác — mất thông tin. Ví dụ: A đã nhận message từ C trước đó nên VC_A[3]=5, trong khi B chưa biết về C nên VC_B[3]=2. Lấy max giữ lại VC_A[3]=5 đúng; copy sang sẽ làm mất 3 sự kiện C mà A đã biết.
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ì?▸
So sánh element-wise: VC1[1]=2 < VC2[1]=3 (VC1 nhỏ hơn ở chiều 1), nhưng VC1[2]=3 > VC2[2]=1 (VC1 lớn hơn ở chiều 2). Vì không có chiều nào nhỏ hơn toàn phần, kết quả là concurrent.
Ý nghĩa thực tế: hai sự kiện tương ứng không có quan hệ nhân quả với nhau. Node 1 đã làm thêm sự kiện nhưng chưa truyền sang node 2, trong khi node 2 đã làm thêm sự kiện nhưng chưa truyền sang node 1. Nếu đây là hai write vào cùng key, cả hai write đều hợp lệ và hệ thống phải giữ cả hai như sibling versions rồi để application quyết định merge.
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?▸
Lamport scalar clock đảm bảo: nếu A → B thì clock(A) < clock(B). Nhưng chiều ngược lại không đúng — clock(A) < clock(B) không suy ra A → B. Khi hai sự kiện concurrent, scalar clock vẫn cho một thứ tự (ai nhỏ hơn đứng trước) nhưng thứ tự đó không có ý nghĩa nhân quả. Không thể biết "A thật sự xảy ra trước B" hay "A và B concurrent".
Vector clock suy luận cả hai chiều: A → B (strict happens-before) khi và chỉ khi VC_A ≤ VC_B và VC_A ≠ VC_B (tức tồn tại ít nhất một chiều mà VC_A strictly nhỏ hơn VC_B). Điều kiện VC_A ≤ VC_B đơn thuần không đủ vì khi VC_A = VC_B, hai event là cùng một event — không phải happens-before. Chọn Lamport khi chỉ cần total order đơn giản (distributed log ordering, Lamport mutex) với chi phí O(1). Chọn vector clock khi cần phân biệt happens-before và concurrent để phát hiện conflict — điển hình là eventual-consistency database như Dynamo/Riak.
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?▸
Vector clock trong Dynamo được gắn vào mỗi version của data để theo dõi lịch sử nhân quả. Khi client đọc version v (kèm VC_v), rồi tính toán và ghi lại version mới v', server cần biết v' kế thừa nhân quả từ v. Client gửi kèm VC_v làm "context" để server biết v → v'.
Nếu client gửi VC rỗng (hoặc không gửi context), server nhìn thấy write không có lịch sử nhân quả — trông như một write độc lập hoàn toàn. Khi hệ thống so sánh write này với version hiện tại, kết quả sẽ là "concurrent" dù thực tế không phải. Điều này tạo sibling giả: hai version được giữ lại trong khi chỉ cần một, làm tăng overhead ứng dụng phải xử lý merge cho những conflict không có thật.
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?▸
Với 1000 node, mỗi message phải đính kèm vector 1000 phần tử integer — overhead đáng kể. Trong thực tế Dynamo, số coordinator node tham gia vào một write thường nhỏ (3–5 node theo consistent hashing), nên vector chỉ cần theo dõi các node thật sự tham gia, không phải toàn cụm.
Giải pháp thực tế: (1) Pruning — Dynamo paper đề xuất xóa entry cũ nhất khi vector vượt ngưỡng kích thước, chấp nhận mất chút độ chính xác. (2) Dotted Version Vectors (Riak 2.0) — tách riêng vector của replica node với vector của client, giảm kích thước. (3) Interval Tree Clocks — không cần biết n cố định trước, hỗ trợ node join/leave động mà không cần resize vector.
Q7Tại sao Cassandra không dùng vector clock mà dùng last-write-wins (LWW) với timestamp? Đánh đổi là gì?▸
Cassandra chọn last-write-wins: khi có conflict, giữ version có timestamp lớn hơn (theo đồng hồ vật lý), bỏ version kia. Quyết định thiết kế này đơn giản hóa triệt để — không cần lưu vector, không cần application merge logic, conflict resolution O(1).
Đánh đổi: LWW bỏ thông tin nhân quả. Nếu đồng hồ hai node lệch nhau, write "mới hơn về nhân quả" có thể có timestamp nhỏ hơn và bị ghi đè bởi write cũ hơn — silent data loss. Đây là lý do Cassandra khuyến cáo dùng tính năng như lightweight transactions (Paxos) hoặc application-level idempotency khi cần strong consistency. Vector clock an toàn hơn nhưng đòi hỏi ứng dụng tự xử lý sibling — Cassandra đánh đổi correctness để lấy simplicity và throughput cao hơn.
Bài tiếp theo: Gossip protocol — lan truyền trạng thái
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