Logical clock: sắp thứ tự nhân quả khi đồng hồ giữa các service lệch nhau Trung cấp

Thời gian đọc ước tính: 4 phút

Cần đọc trước

Tám ngộ nhận về hệ phân tán: nhìn từ một request timeout

Vấn đề

Orders ghi event “đơn 42 đã tạo” lúc đồng hồ máy nó hiển thị 10:00:05. Payments nhận event và ghi log “đã xử lý” lúc đồng hồ máy nó hiển thị 10:00:03.

Sắp log theo timestamp vật lý thì “đã xử lý” đứng trước “đã tạo”. Đó không phải lỗi Kafka: hai máy lệch đồng hồ, hoặc NTP vừa chỉnh giờ.

Hai câu hỏi khác nhau:

Câu hỏi	Công cụ
Bao nhiêu thời gian đã trôi qua?	Wall clock (và monotonic clock cho deadline)
Event nào có thể gây ra event nào?	Logical clock

Happens-before và quy tắc Lamport

Happens-before (a → b):

Cùng một process, a chạy trước b: a → b.
a là gửi message, b là nhận chính message đó: a → b.
Bắc cầu: a → b và b → c thì a → c.

Hai event không có đường nhân quả nào nối nhau là concurrent; nghĩa là không thể xếp cái nào trước, không phải CPU chạy cùng một nanosecond.

Lamport clock: trước mỗi event local hoặc send, L = L + 1; send mang L trong message; khi nhận message mang m, L = max(L, m) + 1. Bảo đảm: a → b thì L(a) < L(b). Chiều ngược lại không đúng.

class Lamport {
  private l = 0;
  tick()           { return ++this.l; }                          // local hoặc send
  receive(m: number) { this.l = Math.max(this.l, m) + 1; return this.l; }
}

Bỏ Math.max thì process nhận có thể có L thấp hơn lúc gửi, và vi phạm a → b ⇒ L(a) < L(b).

Message chuyển thông tin nhân quả, không chuyển đồng hồ vật lý

Orders → MessageL=1

Bước 1/4

Orders tăng logical clock lên 1 và gửi message mang timestamp 1.

Output demo thực tế (chạy examples/src/lamport-clock/clock-demo.ts):

Orders sends event: 1 wall-clock: 10:00:05
Payments local event: 1 wall-clock: 10:00:02
Payments receives event: 2 wall-clock: 10:00:03
Orders next local event: 2 wall-clock: 10:00:06

Wall clock của Payments (10:00:03) nhỏ hơn Orders (10:00:05), nhưng Lamport vẫn đúng: L(send) = 1 < L(receive) = 2. Các chuỗi giờ được gán cố ý để mô phỏng skew; script không sửa đồng hồ hệ điều hành.

Ba process, một cặp concurrent

Ba process: Lamport clock và vector clock cho từng event

Bước 1/4

P1 gửi m1 (a) và P3 có một event nội bộ (d). Hai event này không có đường message nối nhau, nên a và d là concurrent dù cùng L = 1.

Cặp	`L`	Vector clock	Kết luận
a, b	`1 < 2`	`[1,0,0]` nhỏ hơn `[1,1,0]`	`a → b` (có message m1)
d, c	`1 < 3`	`[0,0,1]` và `[1,2,0]` không so sánh được	Concurrent, dù `L(d) < L(c)`
f, e	`2 < 4`	`[2,0,0]` và `[1,2,2]` không so sánh được	Concurrent, dù `L(f) < L(e)`

Lamport clock cho L(d) < L(c) nhưng d không gây ra c.

Vector clock giữ một thành phần cho mỗi process nên bắt được cả hai chiều: V(a) < V(b) khi và chỉ khi a → b. Đổi lại metadata lớn theo số process.

Nếu chỉ cần thứ tự tổng để tie-break, sắp theo (L, processId); thứ tự đó không biến hai event concurrent thành có nhân quả.

Vì sao điều này quan trọng: last-write-wins

Một số store giải quyết ghi xung đột bằng last-write-wins (LWW) theo timestamp, ví dụ Cassandra (theo từng cell, timestamp từ client hoặc coordinator) và DynamoDB global tables giữa các region. (Bài báo Dynamo gốc của Amazon thì dùng vector clock và để ứng dụng hoà giải.) Giả sử đồng hồ của A nhanh 5 giây:

Thời điểm thật	Writer	Giá trị	Timestamp ghi
10:00:00	A (đồng hồ nhanh 5 s)	`x = 1`	10:00:05
10:00:02	B (đồng hồ đúng)	`x = 2`	10:00:02

LWW giữ x = 1 vì timestamp lớn hơn, dù B ghi sau, và không có lỗi nào được báo. Đây là lý do thật để quan tâm tới đồng hồ: mất dữ liệu im lặng. Với dữ liệu quan trọng, dùng version/vector clock và quy tắc merge, hoặc đồng hồ có sai số chặn như dưới đây.

HLC và TrueTime trong một dòng

Kỹ thuật	Ý tưởng	Dùng ở
Hybrid Logical Clock (HLC)	Timestamp = wall clock cộng bộ đếm logic, bám thời gian thật nhưng vẫn giữ quan hệ nhân quả	CockroachDB, MongoDB (cluster time)
TrueTime	API trả khoảng `[earliest, latest]` có sai số chặn; Spanner chờ hết khoảng không chắc chắn (commit wait) trước khi commit	Google Spanner

Lưu ý khi dùng đồng hồ: dùng monotonic clock cho deadline và đo khoảng thời gian (wall clock có thể nhảy lùi khi NTP step hoặc leap second); wall clock chỉ để hiển thị và log.

Ví dụ thực tế

Đưa logical clock vào hệ thật cần quyết định: lưu trong header hay envelope, khôi phục sau restart (demo giữ trong RAM nên mất khi process chết), và bảo đảm proxy không bỏ header.

Trade-offs

Logical clock giúp gì

Giữ quan hệ send → receive mà không cần đồng hồ đồng bộ tuyệt đối
Metadata nhỏ, quy tắc đơn giản
Tách thứ tự nhân quả khỏi thứ tự hiển thị wall clock

Điều nó không giải quyết

Không đo thời gian thật; không dùng làm TTL hoặc deadline
L(a) < L(b) không chứng minh a → b (cần vector clock)
Không tự giải quyết ghi đồng thời, idempotency hay transaction giữa service

Sai lầm thường gặp

Tóm tắt

Tự kiểm tra: (1) Vì sao Payments ghi 10:00:03 dù nhận message có log 10:00:05? (2) Hai event L = 2 có concurrent không? (3) Trong ba process trên, vector clock cho biết điều gì mà L không cho?

Tham khảo

#distributed-systems #logical-clock #clock-skew #causality