Lamport Clock và Vector Clock: Biểu diễn thứ tự trong hệ phân tán

Trong hệ phân tán, timestamp vật lý không đủ để kết luận chắc chắn sự kiện nào gây ra sự kiện nào. Clock giữa các máy có sai số, packet bị trễ và hai node có thể xử lý độc lập. Hai log ghi 10:00:00.100 và 10:00:00.101 không tự động tạo ra quan hệ nhân quả. Logical clock tập trung vào thứ tự có thể suy ra từ execution và message, không cố đo thời gian thực.

Lamport clock gán một số tăng dần để bảo toàn chiều của quan hệ “happened-before”. Vector clock dùng nhiều counter để biểu diễn chính xác hơn: một event có thể nằm sau event khác hoặc concurrent với nó. Hai cơ chế giải quyết bài toán khác nhau và đều không thay thế clock vật lý, transaction, consensus hay conflict-resolution policy.

1. Quan hệ happened-before

Lamport định nghĩa quan hệ a → b theo ba quy tắc:

1. Nếu a và b ở cùng process và a xảy ra trước b, thì a → b.
2. Nếu a là gửi một message và b là nhận message đó, thì a → b.
3. Nếu a → b và b → c, thì a → c.

Nếu không có a → b và cũng không có b → a, hai event là concurrent theo thông tin hệ thống quan sát được. “Concurrent” không nhất thiết có cùng wall-clock timestamp; nó có nghĩa không tồn tại chuỗi local-order/message chứng minh causal order.

Logical time trả lời câu hỏi về quan hệ nhân quả có thể quan sát, không trả lời event xảy ra lúc mấy giờ theo UTC.

2. Thuật toán Lamport clock

Mỗi process giữ counter số nguyên L. Trước mỗi local event hoặc send, tăng counter. Message mang timestamp hiện tại. Khi receive message có timestamp T, process đặt clock thành max(L, T) + 1 trước khi ghi nhận receive event.

onLocalEvent():
  L = L + 1
  return L

onSend(message):
  L = L + 1
  send(message, timestamp=L)

onReceive(message, T):
  L = max(L, T) + 1
  deliver(message)

Tính chất quan trọng: nếu a → b thì L(a) < L(b). Chiều ngược lại không đúng. Hai event độc lập vẫn có thể nhận 5 và 9; con số lớn hơn không chứng minh event 5 ảnh hưởng event 9. Đây là giới hạn thường bị bỏ qua khi dùng Lamport timestamp như bằng chứng causality.

3. Tạo total order mà không bịa thêm causality

Một số thuật toán cần sắp mọi event theo một thứ tự xác định. Có thể sort bằng cặp (lamport_timestamp, process_id), trong đó process ID phá hòa. Thứ tự này nhất quán với happened-before nếu implementation đúng, nhưng phần tie-break là quy ước, không phải causal fact.

Đừng dùng total order nhân tạo để silently ghi đè concurrent update nếu nghiệp vụ cần giữ cả hai phiên bản. Quy tắc “timestamp lớn thắng” có thể làm mất dữ liệu hợp lệ.

4. Vector clock mở rộng logical time

Với N process có identity ổn định, mỗi process giữ vector V[0..N-1]. Process i tăng thành phần V[i] cho event local/send. Message mang vector. Khi receive, process lấy maximum theo từng thành phần giữa local và message, rồi tăng thành phần của chính nó. Một số mô tả đặt increment ở vị trí hơi khác; protocol phải cố định convention.

onLocalOrSend(i):
  V[i] = V[i] + 1

onReceive(i, remote):
  for k in 0..N-1:
    V[k] = max(V[k], remote[k])
  V[i] = V[i] + 1

Mỗi thành phần tóm tắt process hiện tại đã biết bao nhiêu event từ process tương ứng. Merge bằng maximum tạo knowledge union: receive event biết tất cả điều receiver từng biết và điều sender truyền tới.

5. So sánh vector để phát hiện concurrency

Cho hai vector A và B:

• A ≤ B nếu mọi thành phần của A không lớn hơn B.
• A < B nếu A ≤ B và ít nhất một thành phần nhỏ hơn.
• Nếu A < B, event A happened-before event B.
• Nếu A không ≤ B và B cũng không ≤ A, chúng concurrent.

Ví dụ [2,1,0] < [3,1,2]. Nhưng [2,3,0] và [3,1,2] không so sánh được: vector đầu biết nhiều hơn về process 2, vector sau biết nhiều hơn về process 1 và 3. Không có bằng chứng một bên causally sau bên kia.

6. Ví dụ ba node

A, B và C bắt đầu tại [0,0,0]. A tạo update: [1,0,0]. A gửi message sang B. B merge rồi tăng thành [1,1,0]. Trong lúc đó C tạo update độc lập [0,0,1]. So sánh cho thấy update của B và C concurrent vì mỗi vector có một thành phần lớn hơn bên kia.

Nếu B sau đó gửi sang C, C merge và tăng thành [1,1,2]. Vector mới nằm sau update của A và B, đồng thời sau event cũ của C. Causality được truyền qua message mà không cần clock vật lý đồng bộ.

7. Ứng dụng thực tế

• Versioned key-value store: phát hiện hai replica tạo sibling version concurrent thay vì ghi đè.
• Multi-master replication: xác định version dominated có thể bỏ và version concurrent cần merge.
• CRDT/runtime: theo dõi causal context để áp dụng operation an toàn.
• Debugging/trace analysis: suy luận quan hệ event khi wall clock không đáng tin tuyệt đối.
• Optimistic workflow: phát hiện client ghi dựa trên state chưa bao gồm update khác.

Vector clock chỉ phát hiện conflict. Nó không quyết định merge text, chọn trạng thái đơn hàng hay hoàn tiền. Conflict resolution là chính sách domain: giữ sibling, merge tự động, yêu cầu người dùng, hoặc dùng CRDT phù hợp.

8. Chi phí và bài toán membership

Vector dài theo số participant. Với fleet thay đổi động hoặc mỗi client có identity riêng, metadata có thể lớn và process identity tái sử dụng gây sai causality. Cần policy về join, leave, epoch và garbage collection. Không xóa một thành phần chỉ vì node offline; knowledge cũ có thể quay lại qua replica khác.

Các biến thể như version vector, dotted version vector, interval tree clock hoặc hybrid logical clock giải quyết các trade-off khác nhau. Không nên tự “nén” vector bằng cách bỏ entry nhỏ mà chưa chứng minh an toàn. Nếu topology có server replica cố định, vector theo replica có thể đủ; nếu actor tùy ý, cần thiết kế khác.

9. Persistence, retry và identity

Logical clock mất sau restart có thể phát timestamp nhỏ hơn lịch sử. Persist counter/vector cùng state hoặc gắn process incarnation/epoch mới. Update state và causal metadata nên nằm trong cùng transaction; nếu data commit nhưng vector không commit, hệ thống có thể diễn giải sai version.

• Message retry phải giữ event/message ID để deduplicate; clock mới không biến duplicate thành event mới hợp lệ.
• Process ID phải duy nhất trong scope và lifetime đã định nghĩa.
• Restore backup cần xử lý epoch để không “quay ngược” logical time.
• Input từ client không tin cậy cần validate kích thước, counter overflow và identity.
• Logical timestamp không phải credential; không dùng nó thay authorization.

10. Logical clock không giải quyết mọi bài toán thời gian

Nếu cần TTL, certificate expiry, billing window hoặc lịch chạy job, hệ thống vẫn cần physical time được đồng bộ và policy cho clock uncertainty. Nếu cần mọi node đồng ý một log duy nhất khi có failure, cần consensus hoặc cơ chế serialization phù hợp. Nếu cần causal order và timestamp gần wall time, hybrid approach có thể phù hợp nhưng vẫn phải hiểu semantics.

Không gắn nhãn “exactly once” chỉ vì event có clock. Retry, deduplication, atomic commit và idempotent effect vẫn là vấn đề riêng. Cũng không suy latency bằng cách trừ Lamport timestamp; đơn vị logical tick không phải millisecond.

11. Kiểm thử implementation

• Local event luôn tăng thành phần đúng.
• Receive lấy maximum theo component rồi increment đúng convention.
• Mọi message edge thỏa send vector < receive vector.
• Event không có đường causal tạo vector incomparable trong scenario kiểm thử.
• Duplicate message không lặp business effect.
• Restart/restore không tái sử dụng identity và counter sai epoch.
• Serialization ổn định giữa ngôn ngữ, version và endianness.

Property test có thể sinh đồ thị event/message nhỏ, tính transitive closure của happened-before và so với vector comparison. Với Lamport clock, chỉ assert a → b ⇒ L(a) < L(b); không viết test converse vì đó không phải tính chất thuật toán.

Checklist lựa chọn

• Chỉ cần total order quyết định được: Lamport clock cộng tie-breaker có thể đủ.
• Cần phát hiện concurrent versions: cân nhắc vector/version vector.
• Membership lớn/dynamic: đánh giá metadata và variant khác.
• Cần thời gian thực: dùng physical clock với uncertainty, không dùng logical tick.
• Cần agreement: dùng consensus/serialization, không chỉ timestamp.
• Đã định nghĩa identity, persistence, retry, merge và garbage collection.

Tài liệu tham khảo

• Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System
• Microsoft Research publication page
• Friedemann Mattern: Virtual Time and Global States of Distributed Systems

Kết luận

Lamport clock cung cấp scalar order tôn trọng causal direction nhưng không phát hiện concurrency. Vector clock giữ causal knowledge theo participant, cho phép phân biệt event happened-before và event concurrent với chi phí metadata và membership cao hơn. Chọn cơ chế dựa trên câu hỏi hệ thống cần trả lời; đừng biến logical timestamp thành wall time, conflict resolver hay consensus. Khi semantics, identity và persistence được đặc tả rõ, logical clock là công cụ mạnh để suy luận về hệ phân tán.