Vector clock — thứ tự nhân quả sự kiện

TL;DR: Đồng hồ vật lý (wall-clock) của các máy có thể lệch nhau từ vài chục tới vài trăm millisecond, nên không thể dùng nó để 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 max từng phần tử (element-wise max: ở mỗi ô giữ số lớn hơn trong hai vector) 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 (hai phiên bản của cùng một key cùng được giữ vì không bản nào đè được bản kia) khi có concurrent write.

Giả sử một hệ 3 node kiểu Amazon, mỗi node ở một datacenter khác nhau: đồng hồ lệch nhau hàng chục tới vài trăm ms là chuyện có thể xảy ra. 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, biết đâu đồng hồ B chạy nhanh hơn.

Nói đời thường: mỗi máy giữ một cuốn sổ ghi "tôi đã biết tới việc thứ mấy của từng máy". Hai máy gặp nhau (gửi tin) thì so và chép lại cho đủ. Nhìn hai cuốn sổ là biết việc nào chắc chắn có trước, hay hai việc xảy ra mà không máy nào hay máy nào (concurrent).

Lamport (1978) phát biểu quan hệ happens-before (ký hiệu →): a → b nếu a có thể nhân quả ảnh hưởng tới b. Lamport scalar clock (một con số) chỉ đúng một chiều: A → B thì clock(A) < clock(B), nhưng không phân biệt được 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

Mỗi máy dùng thạch anh riêng nên đồng hồ lệch dần; NTP (Network Time Protocol, giao thức đồng bộ giờ qua mạng) đồng bộ định kỳ nhưng không đảm bảo thứ tự giữa hai máy. Vì sao wall-clock lệch và khác gì monotonic clock: xem Đồng hồ không tin cậy. Hệ quả cho thuật toán: hai client ghi đồng thời vào database kiểu Dynamo (ghi node nào cũng được, không có lock trung tâm) thì không có mốc giờ nào cho biết ghi nào "cuối cùng".

Vector clock hỏi một câu khác: thay vì "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ì?". Thông tin này ta thật sự có: node A gửi message cho B thì A chắc chắn xảy ra trước thời điểm B nhận. Phần lý thuyết happened-before và Lamport clock nằm ở Causal order trong Data phân tán.