Causal order — happened-before và vector clock

TL;DR: Bài trước đóng lối "so timestamp vật lý để biết thứ tự". Bài này mở lối khác: suy luận thứ tự không cần đồng hồ vật lý, chỉ dựa vào quan hệ nhân quả. Leslie Lamport định nghĩa happened-before (a → b: a có thể ảnh hưởng b) — cùng node theo thứ tự thực thi, hoặc gửi rồi nhận một message. Nhiều cặp sự kiện không có quan hệ này — chúng song song (concurrent), nên nhân quả là thứ tự bộ phận, không toàn phần. Lamport clock (một số đếm) cho thứ tự tổng nhưng không phân biệt được song song; vector clock (một vector đếm mỗi node) thì phát hiện được.

Ở bài 01 mạng che mất thứ tự; ở bài 02 đồng hồ cũng không cứu được. Giải pháp không phải tìm một đồng hồ tốt hơn mà đổi câu hỏi: thay vì "cái nào xảy ra sau theo thời gian tuyệt đối?" (bất khả tín), hỏi "cái nào có thể ảnh hưởng tới cái nào?" — một câu hỏi trả lời được chỉ bằng thông tin trao đổi giữa các node, không cần đồng hồ.

1. Analogy — chuỗi email trả lời vs hai email độc lập

Trong hộp thư, bạn phân biệt được hai tình huống mà không cần nhìn giờ gửi. Một email B là trả lời (reply) email A: chắc chắn A đến trước, vì người gửi B đã đọc A rồi mới viết — B phụ thuộc nhân quả vào A. Ngược lại, hai người ở hai nơi cùng viết cho bạn hai email hoàn toàn khác chủ đề, không ai biết email của người kia: đó là hai email độc lập — không cái nào ảnh hưởng cái nào, dù một cái có thể tình cờ gửi trước vài giây. Với cặp reply, thứ tự là xác định (A trước B). Với cặp độc lập, hỏi "cái nào trước" là vô nghĩa về nhân quả — chúng song song.

2. Happened-before: vì sao nhân quả là thứ tự bộ phận?

Leslie Lamport (1978) định nghĩa quan hệ happened-before, ký hiệu a → b, đọc là "a xảy ra trước b" theo nghĩa a có thể ảnh hưởng tới b. Quan hệ này đúng trong ba trường hợp:

1. Cùng một node: nếu a và b xảy ra trên cùng một node và a chạy trước b theo thứ tự thực thi → a → b.
2. Gửi và nhận: nếu a là sự kiện gửi một message và b là sự kiện nhận chính message đó (ở node khác) → a → b.
3. Bắc cầu (transitive): nếu a → b và b → c thì a → c.

Điểm mấu chốt: không phải cặp sự kiện nào cũng có quan hệ này. Nếu a và b xảy ra trên hai node khác nhau và không có chuỗi message nào nối chúng, thì không có a → b lẫn b → a. Ta nói a và b song song (concurrent), ký hiệu a ∥ b.

flowchart LR
  A1["a1: node A ghi x"] --> A2["a2: node A gui msg"]
  A2 -->|"message"| B2["b2: node B nhan msg"]
  B2 --> B3["b3: node B ghi y"]
  B1["b1: node B ghi z<br/>(truoc khi nhan)"] --> B2

Trong sơ đồ: a1 → a2 → b2 → b3 (chuỗi nhân quả qua message). Nhưng a1 và b1 song song — chúng xảy ra độc lập, không node nào thấy sự kiện của node kia trước khi hành động. Vì tồn tại các cặp song song không so được, nhân quả là một partial order (thứ tự bộ phận): một số cặp có thứ tự rõ, một số cặp thì không. Điều này khác total order (thứ tự toàn phần) — nơi mọi cặp đều so được (như số nguyên: hai số bất kỳ luôn có cái lớn hơn).

Sự phân biệt này không phải hình thức: hai ghi song song cho cùng một key chính là xung đột thật cần gộp (như bài multi-leader ở Module 2), còn hai ghi có quan hệ nhân quả thì cái sau đè cái trước một cách hợp lệ. Muốn giải xung đột đúng, hệ phải phân biệt được hai loại đó.

3. Lamport clock — một số đếm, và giới hạn của nó

Cách đơn giản nhất để đánh dấu nhân quả: mỗi node giữ một bộ đếm (một số nguyên). Quy tắc Lamport clock:

- Moi node co bien counter, khoi tao 0.
- Truoc moi su kien noi bo: counter <- counter + 1.
- Khi GUI message: counter <- counter + 1; dinh kem counter vao message.
- Khi NHAN message co timestamp t: counter <- max(counter, t) + 1.

Quy tắc max khi nhận là mấu chốt: nó đảm bảo bên nhận luôn có counter lớn hơn bên gửi tại thời điểm gửi. Kết quả: nếu a → b thì LC(a) < LC(b) — số Lamport tôn trọng nhân quả. Gán thêm một quy tắc phá hoà (ví dụ kèm node-id) là có một total order nhất quán với nhân quả.

Nhưng Lamport clock có một giới hạn nền tảng: chiều ngược lại không đúng. LC(a) < LC(b) không chứng minh a → b — hai sự kiện song song vẫn có hai số khác nhau, và bạn không cách nào biết số đó đến từ "sau thật" hay chỉ "song song mà tình cờ đếm nhiều hơn". Nói cách khác, Lamport clock nén một partial order thành một total order, và trong lúc nén nó xoá mất thông tin "cặp này song song". Với việc cần phát hiện xung đột (biết hai ghi có song song không), Lamport clock không đủ.

4. Vector clock — phân biệt được nhân quả với song song

Vector clock khắc phục đúng giới hạn của Lamport clock. Thay vì một số, mỗi node giữ một vector V có một ô cho mỗi node. V[i] là "số sự kiện của node i mà node này đã biết". Quy tắc:

- Node i co vector V, khoi tao [0, 0, ..., 0].
- Truoc moi su kien noi bo cua node i: V[i] <- V[i] + 1.
- Khi GUI message: V[i] <- V[i] + 1; dinh kem CA vector V.
- Khi NHAN vector W: voi moi j: V[j] <- max(V[j], W[j]); roi V[i] <- V[i] + 1.

So sánh hai vector V và W:

• V → W (V xảy ra trước) nếu V[k] <= W[k] với mọi k, và có ít nhất một k mà V[k] < W[k].
• V ∥ W (song song) nếu không cái nào trội hết cái kia — tồn tại k mà V[k] > W[k] và m mà V[m] < W[m].

Nhờ giữ nguyên "ai đã thấy gì của ai", vector clock không nén mất thông tin song song như Lamport clock. Trước khi đọc phần giải, hãy tự áp quy tắc so sánh vào một cặp cụ thể.

Lần theo quy tắc:

• P [2,1,0] vs Q [2,3,1]: so từng ô — 2<=2 (ô A), 1<=3 (ô B), 0<=1 (ô C): mọi ô của P nhỏ hơn hoặc bằng Q, và có ô lớn thật sự (B: 1 vượt lên 3). Vậy P → Q — P xảy ra trước Q (Q đã "thấy" P). Trực giác khớp: Q biết nhiều sự kiện của B và C hơn, còn của A thì bằng.
• R [1,2,0] vs S [2,1,0]: ô A có R=1 < S=2 (S trội ở A) nhưng ô B có R=2 > S=1 (R trội ở B). Không cái nào trội hết → R ∥ S, song song. Đây chính là dấu hiệu xung đột: R và S là hai ghi độc lập, không cái nào thấy cái kia — nếu chúng ghi cùng một key thì hệ phải gộp chứ không được vứt một cái.

Đó là sức mạnh vector clock so với Lamport clock: nó không chỉ sắp thứ tự mà còn chỉ mặt cặp nào song song. Cái giá là bộ nhớ — vector dài bằng số node, và với hệ nhiều node biến động, việc quản lý các ô trở nên tốn kém (một vấn đề thực tế mà các hệ dùng nhiều biến thể để giảm nhẹ).

5. Pitfall — tưởng "số lớn hơn = xảy ra sau"

❌ if (LC(writeA) > LC(writeB)) keep(writeA);   // nhu LWW nhung dung so Lamport
   // -> hai ghi SONG SONG van co hai so khac nhau
   // -> van vut nham mot ghi hop le (xung dot bi bo qua)

✅ Dung VECTOR clock: neu writeA || writeB (song song) -> GOP, dung vut
✅ Chi khi mot vector troi hoan toan vector kia moi coi la de hop le

Hướng đúng: chọn công cụ theo câu hỏi. Cần một total order để, ví dụ, sắp log toàn hệ → Lamport clock đủ và rẻ. Cần phát hiện ghi xung đột để gộp đúng → phải vector clock (hoặc biến thể), chấp nhận cái giá bộ nhớ. Và trong mọi trường hợp, đừng quay lại tin timestamp vật lý — đó là bài học của bài 02.

6. 📚 Đào sâu — nguồn gốc & tài liệu

7. Liên hệ các bài khác

• Bài 02 — Đồng hồ không tin cậy: bài này là câu trả lời cho bế tắc của bài 02 — suy thứ tự bằng nhân quả (logic), không bằng đồng hồ vật lý.
• Module 2 — Multi-leader replication: "hai ghi song song cần gộp, hai ghi nhân quả thì đè" chính là bài toán giải xung đột ở đó; vector clock là công cụ phân biệt hai loại — không mất dữ liệu như LWW.
• Module 6 — Causal consistency: causal order của bài này được nâng thành một mô hình nhất quán — hệ đảm bảo mọi node thấy các sự kiện theo đúng thứ tự nhân quả.
• Bài 01 — Mạng không tin cậy: vì message là thứ duy nhất nối các node (mạng không tin cậy nhưng vẫn là kênh truyền), quan hệ gửi→nhận trở thành nền để định nghĩa nhân quả mà không cần đồng hồ.

8. Tóm tắt

• Happened-before (a → b): a có thể ảnh hưởng b — cùng node theo thứ tự, hoặc gửi→nhận cùng message, hoặc bắc cầu.
• Cặp không có a → b lẫn b → a là song song (concurrent) → nhân quả là partial order, không phải total order.
• Lamport clock (một số, quy tắc max khi nhận): a → b ⇒ LC(a) < LC(b), cho total order nhất quán với nhân quả — nhưng không phát hiện được song song (chiều ngược không đúng).
• Vector clock (một ô đếm mỗi node): so từng ô → xác định rõ a→b, b→a, hay song song; đủ để phát hiện ghi xung đột cần gộp. Cái giá: bộ nhớ tỉ lệ số node.
• Chọn theo câu hỏi: cần total order rẻ → Lamport; cần phát hiện xung đột → vector clock. Tuyệt đối không quay lại timestamp vật lý.

9. Tự kiểm tra

Bài tiếp theo: Partial failure & fencing token — chống split-brain