Phần trước đo mạng. Phần này đo thứ nghe còn vô lý hơn khi nói là "không tin được": đồng hồ. Mỗi máy có một đồng hồ, NTP giữ chúng gần nhau — nhưng gần là bao nhiêu, và bao nhiêu thì đủ để "sự kiện A xảy ra trước B" trở thành câu sai? Bài này dựng ba tiến trình thật, cho chúng gửi thông điệp qua mạng, gắn ba loại đồng hồ vào từng sự kiện, rồi đếm xem đồng hồ nào nói dối và khi nào.
Ba đồng hồ cho một sự kiện
Hình 1: Mỗi sự kiện mang cả ba đồng hồ. Lamport là một số; vector là một số cho mỗi node; cả hai chỉ tăng theo quy tắc gửi/nhận, không nhìn đồng hồ máy.
- Đồng hồ tường là
time.Now(), cộng một độ lệch giả lập theo cờ-lechđể mô phỏng máy có đồng hồ chạy nhanh hoặc chậm. Ba tiến trình ở đây chạy trên cùng một kernel nên không có lệch thật; độ lệch là thứ duy nhất được giả lập trong bài, và nó được ghi rõ trong mọi bảng. - Lamport clock (1978): một bộ đếm. Mỗi sự kiện tăng nó lên; khi nhận thông điệp, lấy max của mình và của người gửi rồi tăng. Nếu a xảy ra trước b thì Lamport(a) < Lamport(b) — chiều ngược lại thì không.
- Vector clock: một bộ đếm cho mỗi node. Khi nhận, lấy max từng phần rồi tăng phần của mình. "a trước b" khi mọi phần của a ≤ b và ít nhất một phần nhỏ hơn thật; không bên nào trước bên nào thì a và b đồng thời — nghĩa là không bên nào biết về bên kia lúc xảy ra.
Đo thật: 1 ms là đủ
Ba tiến trình, mỗi tiến trình gửi 300 thông điệp tới một node ngẫu nhiên khác, tổng 900. Mỗi cặp gửi → nhận là quan hệ nhân quả chắc chắn: không thể nhận trước khi gửi. Đếm xem mỗi đồng hồ xếp ngược bao nhiêu cặp:
Hình 2: Kết quả thật. Mục 1 là nhân quả chắc chắn, mục 2 là đồng thời, mục 3 là hậu quả thực tế của việc tin đồng hồ tường.
| lệch (node0, node1, node2) | tường xếp ngược | Lamport ngược | vector ngược |
|---|---|---|---|
| 0, 0, 0 ms | 0 | 0 | 0 |
| 0, +1, 0 ms | 300 (33,3%) | 0 | 0 |
| 0, +50, 0 ms | 300 (33,3%) | 0 | 0 |
| 0, −50, 0 ms | 297 (33,0%) | 0 | 0 |
| −30, 0, +30 ms | 431 (47,9%) | 0 | 0 |
Lệch 1 ms là đủ, vì mạng nhanh hơn 1 ms. RTT giữa ba tiến trình là 0,3 ms. Khi đồng hồ node 1 chạy nhanh 1 ms, mọi thông điệp node 1 gửi được đóng dấu "muộn" hơn thời điểm người nhận đóng dấu "đã nhận" — vì 1 ms lệch lớn hơn 0,3 ms đường truyền. Đúng 300 cặp, tức 100% thông điệp node 1 gửi đi, bị xếp ngược. Lệch 5 hay 50 ms cho cùng con số, vì ngưỡng đã bị vượt từ 1 ms. Lệch −50 ms đảo chiều: 297 cặp ngược là mọi thông điệp node 1 nhận. Ba node lệch nhau theo ba hướng: gần một nửa số cặp sai.
Đặt con số đó cạnh NTP: trong điều kiện tốt, NTP giữ lệch ở mức vài mili-giây; qua Internet công cộng là hàng chục; một máy ảo bị tạm dừng rồi tiếp tục có thể lệch hàng giây cho tới lần đồng bộ sau. Tất cả đều lớn hơn 0,3 ms. Trong mạng nội bộ, đồng hồ tường không đủ tốt để xếp thứ tự hai sự kiện ở hai máy khác nhau — không phải vì NTP kém, mà vì mạng nhanh hơn độ chính xác của bất kỳ đồng hồ nào.
Lamport và vector sai 0 lần ở mọi độ lệch, vì chúng không nhìn đồng hồ máy. Thứ tự của chúng đến từ chính thông điệp: nhận bao giờ cũng lấy max rồi tăng, nên nhận luôn lớn hơn gửi, bất kể máy nào nghĩ mấy giờ.
Mục 2: thứ Lamport không nói được
Lamport đảm bảo "a trước b ⇒ L(a) < L(b)" nhưng chiều ngược lại thì không: L(a) < L(b) không có nghĩa a xảy ra trước b. Trong 270.000 cặp sự kiện gửi ở hai node khác nhau, vector clock nhận ra 1.269 cặp đồng thời — hai sự kiện mà lúc xảy ra, không bên nào đã nghe gì về bên kia. Lamport gán số khác nhau cho 1.109 trong số đó, tức là xếp một cái trước một cái sau, và thứ tự đó không mang nghĩa nhân quả — nó chỉ là kết quả của việc ép mọi thứ lên một trục số.
Chuyện này quan trọng khi nào? Khi hai sự kiện đồng thời là hai lần ghi vào cùng một khoá. Lamport sẽ chọn một bên thắng mà không ai hay biết có xung đột; vector clock nói "đây là xung đột, cần hợp nhất" — và đó chính là cơ chế đằng sau sibling trong Dynamo/Riak và CRDT ở phần 9. Cái giá: vector lớn theo số node (ba số ở đây, hàng trăm số với hàng trăm node), còn Lamport luôn là một số.
Mục 3: Last-Writer-Wins với đồng hồ chạy nhanh
Nhiều hệ thống giải quyết xung đột bằng last-writer-wins: bản có timestamp lớn hơn thắng. Mục 3 đo đúng chuyện đó với hai node ghi cùng một khoá: node 1 ghi trước, node 0 ghi sau 5 ms theo thời gian thật.
- Lệch 0 hoặc +1 ms: node 0 thắng 200/200 — đúng, vì nó ghi sau.
- Lệch node 1 +20 ms: node 1 thắng 200/200 — sai, vì nó ghi trước; đồng hồ nhanh 20 ms khiến bản cũ có timestamp lớn hơn bản mới 5 ms.
Hệ quả thực tế: trong một cụm dùng LWW theo đồng hồ tường, máy có đồng hồ chạy nhanh nhất luôn thắng, bất kể nó ghi trước hay sau. Và nó thắng một cách im lặng — không log, không lỗi, chỉ có cập nhật của máy khác biến mất. Cassandra có ghi rõ điều này trong tài liệu; nhiều người đọc nó lần đầu sau khi mất dữ liệu.
Đánh đổi cần cân nhắc
Lệch đồng hồ ở đây là giả lập, và đó là điểm cần nói rõ. Ba tiến trình chạy chung một kernel, không thể lệch thật. Cờ -lech cộng một hằng vào time.Now() — nó mô phỏng offset chứ không mô phỏng drift (đồng hồ chạy nhanh dần) hay bước nhảy (NTP chỉnh lùi giờ). Hai thứ sau còn tệ hơn offset: bước nhảy lùi làm một máy tự xếp ngược sự kiện của chính nó. Go dùng đồng hồ đơn điệu cho time.Since đúng vì vậy — nhưng timestamp gửi qua mạng thì vẫn là đồng hồ tường.
Đồng hồ tường vẫn có chỗ: khi cần so với thế giới thật. "Đơn này tạo lúc 10:03" cho người đọc, "token hết hạn sau 15 phút", "xoá log cũ hơn 30 ngày" — những thứ này không phải nhân quả giữa hai máy, và Lamport vô dụng ở đó. Vấn đề chỉ xuất hiện khi lấy timestamp tường để quyết định cái nào xảy ra trước giữa hai máy.
Hybrid Logical Clock là cách lai thực dụng. HLC ghép đồng hồ tường với bộ đếm logic: gần với giờ thật để người đọc được, nhưng tuân thủ nhân quả như Lamport. CockroachDB và nhiều hệ mới dùng nó. Cái giá là phải giới hạn lệch tối đa và từ chối node vượt ngưỡng.
Spanner làm ngược lại: biến độ lệch thành khoảng. TrueTime trả về [sớm nhất, muộn nhất] thay vì một con số, và commit chờ cho tới khi khoảng đó trôi qua. Nó cần đồng hồ nguyên tử và GPS trong từng trung tâm dữ liệu — tức là trả tiền để thu hẹp cái khoảng mà bài này đo bằng mili-giây xuống micro-giây, chứ không xoá nó.
Số đo của ba node, 900 thông điệp. Tỉ lệ 33% là của mô hình "một node lệch, gửi đều cho hai node kia"; tỉ lệ thật phụ thuộc đồ thị trao đổi. Kết luận không phụ thuộc: ngưỡng để đồng hồ tường sai bằng độ trễ mạng, và độ trễ mạng nội bộ nhỏ hơn mọi độ lệch đồng hồ thực tế.
Ba ý mang về
- Đồng hồ tường sai nhân quả ngay khi lệch vượt độ trễ mạng — 1 ms trong mạng 0,3 ms là đủ để 100% thông điệp của node lệch bị xếp ngược (300/900); ba node lệch ba hướng là gần một nửa. NTP không hứa được dưới mức đó.
- Lamport và vector clock không bao giờ sai nhân quả (0/900 ở mọi độ lệch) vì thứ tự đến từ thông điệp, không từ đồng hồ. Lamport là một số nhưng không phân biệt được đồng thời (gán trước/sau cho 1.109 cặp vốn không liên quan); vector phân biệt được, với giá một bộ đếm mỗi node.
- LWW theo đồng hồ tường cho máy có đồng hồ nhanh thắng vô điều kiện: lệch 20 ms là bản cũ đè bản mới 200/200, không log, không lỗi. Dùng đồng hồ tường để hiển thị và hết hạn; dùng đồng hồ logic để xếp thứ tự giữa các máy.
Nguồn
- Leslie Lamport — Time, Clocks, and the Ordering of Events in a Distributed System (1978): https://lamport.azurewebsites.net/pubs/time-clocks.pdf
- Colin Fidge — Timestamps in Message-Passing Systems That Preserve the Partial Ordering (1988), vector clocks
- Martin Kleppmann — Designing Data-Intensive Applications, chương 8, mục Unreliable Clocks
- Kulkarni et al. — Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (HLC): https://cse.buffalo.edu/tech-reports/2014-04.pdf
- Google — Spanner: Google's Globally-Distributed Database (TrueTime): https://research.google/pubs/spanner-googles-globally-distributed-database-2/
- Go docs — package time, phần Monotonic Clocks: https://pkg.go.dev/time#hdr-Monotonic_Clocks
Phần sau dùng đúng thứ vừa đo để đập vỡ một công cụ ai cũng từng viết: khoá phân tán bằng SET NX kèm TTL. Tiến trình giữ khoá bị treo quá TTL, khoá hết hạn, tiến trình khác lấy khoá — rồi tiến trình đầu tỉnh dậy và ghi tiếp. Đo thật số lần ghi sai, và fencing token chặn nó ra sao.
