Quần Cam

Lamport timestamp

Photo by Eduardo Olszewski on Unsplash

Câu chuyện đôi bạn

Gần đây mục Hư Cấu của vnexpress xuất hiện một câu chuyện cảm động về tình bạn, với các tình tiết được diễn ra theo tốc độ ánh sáng:

Cam và Sọt là đôi bạn thân. Một ngày đẹp trời, sét đánh trúng đầu Cam. Lúc choáng váng Cam thấy Thor báo mộng một dãy số xổ số Quanlott. Thor đã báo thì chớ có sai nên Cam không lưỡng lự mà mua ngay.

Thương bạn nghèo thất học, Cam khoe Sọt giấc mơ của mình và hứa nếu trúng sẽ chia bốn chấm không % giúp bạn xóa đói giảm nghèo. Nhưng Sọt lòng lang dạ sói, len lén tự mua cho mình một vé. Té ra từ “úp sọt” có nguồn gốc như thế.

Đến lúc xổ số, cả Cam và Sọt đều trúng nhưng Quanlott thì chỉ có một cái. Người ta đành phải trao giải cho vé được mua sớm hơn. Lúc này timestamp mua vé được dùng làm cơ sở để xác định thứ tự trước sau. Bất ngờ vé của Sọt hiển thị timestamp nhỏ hơn, thế là Sọt là người chiến thắng.

Thế là tình bạn tan vỡ. Cam thề trước ánh đèn con cháu nhà họ Cam mãi ghi sâu mối thù này.

Vấn đề của việc sắp xếp bằng thời gian vật lý

Ta hãy thử vẽ lại câu chuyện này bằng lược đồ space-time, với chiều ngang thể hiện không gian (với các tiến trình) và chiều dọc là thời gian (chiều từ dưới lên). Dấu chấm tròn dùng để chỉ event và dấu mũi tên dùng để chỉ sự trao đổi một gói tin.

Nếu bạn có đọc bài Trứng lòng đào và các vấn đề đồng hồ trong lập trình, đồng hồ vật lý có thể bị trượt, bị lệch và không đáng tin. Do đó cách giải thích cho hiện tượng này có thể là:

  1. Server Quanlott dùng timestamp trên máy người dùng — đồng hồ của Sọt trượt về quá khứ hay đồng hồ của Cam trượt về tương lai.
  2. Cam xài mạng dial-up, gói tin bị drop/retry liên tục nên rốt cuộc request tới chậm hơn.
  3. Tác giả thích thế, nếu hoàng tử lúc nào cũng lấy Bạch Tuyết thì làm gì có PRIDE.

Trong đời sống thường ngày chúng ta vẫn dùng thời gian vật lý để sắp xếp event xung quanh. Tui thức dậy vào lúc 7:01 và bạn ăn sáng vào lúc 7:02. Theo lẽ tự nhiên, bạn có thể nói rằng tui thức dậy trước khi bạn ăn sáng. Mặc dù có khả năng đồng hồ của bạn chạy nhanh hơn đồng hồ của tui.

Đồng hồ vật lý là không đáng tin khi ta nói về việc xây dựng hệ thống phân tán. Ta không thể dùng nó cho việc sắp xếp các event, hay chi tiết hơn là xác định sự kiện này xảy ra trước sự kiện kia. Vậy ta nên dùng tiêu chí gì?

Bài viết này giới thiệu về Lamport Timestamp, một paper được viết năm 1978 bởi Leslie Lamport, và cách mà Lamport Timestamp có thể được sử dụng để giải quyết bài toán éo le này.

Lamport timestamp

Thứ tự từng phần

Trước tiên ta hãy định nghĩa lại quan hệ “xảy ra trước”.

Cho a, b là hai events trong một hệ thống phân tán (bao gồm nhiều process liên kết với nhau), và -> là quan hệ “xảy ra trước”.

  1. Nếu a và b xảy ra trên cùng một process, và a đến trước b, thì a -> b.
  2. Nếu a là việc gửi gói tin từ một process, và b là việc nhận gói tin đó ở một process khác, thì a -> b.
  3. Nếu a -> b và b -> c thì a -> c.

Ta có thể giải thích từng điểm như sau. Điểm 1 khá đơn giản, trong một tiến trình tuần tự thì event nào đến trước sẽ là event xảy ra trước. Điểm 2 và 3 có thể hiểu là quan hệ nhân quả (causal effect): nếu một event b xảy ra bởi vì event a, thì a -> b.

Ta thử vẽ lại lược đồ space-time theo định nghĩa trên.

Lamport 1

Từ lược đồ, ta biết Cam mua vé (c2) và việc Sọt mua vé là một mối quan hệ nhân quả (s2) (causality effect). Bởi c1 -> c2, c2 -> s1, s1 -> s2.

Với những event nằm trên những tiến trình không trao đổi với nhau (ví dụ như c3 và s2), ta nói rằng chúng là những concurrent event, mặc dù trên lược đồ space-time trông có vẻ c3 diễn ra trước (theo đồng hồ vật lý).

Như vậy bằng cách này, ta có thể xây dựng một hệ thống vận hành chính xác chỉ bằng việc biết những event đã xảy ra, mà không cần phải biết những sự việc có thể đã xảy ra.

Đồng hồ logic

Bây giờ ta giới thiệu đồng hồ logic, tuân theo định nghĩa quan hệ “xảy ra trước” ta đã mô tả.

Giả sử mỗi tiến trình đều có một đồng hồ C, với C là một hàm số sinh ra timestamp. Đồng hồ này không nhất thiết phải liên quan đến đồng hồ vật lý (vì như vậy đòi hỏi đồng hồ vật lý phải tuyệt đối chính xác).

Mỗi event x trên tiến trình đều được C gán cho một con số timestamp tương đương C(x). Ta có thể hiện thực C dễ dàng với một con counter luôn tăng.

Ta có Clock Condition của đồng hồ logic là:

Clock Condition. For any events a, b: if a -> b then C(a) < C(b).

Ta có thể định nghĩa lại Clock Condition dựa trên quan hệ “xảy ra trước”, bao gồm 2 điều kiện sau:

C1. Nếu a và b là events trong process Pi, thì Ci(a) < Ci(b).
C2. Nếu a là event gửi gói tin từ process Pi và b là event nhận gói tin đó của process Pj, thì Ci(a) < Ci(b).

Code thì thường dễ hiểu hơn công thức, nên tui đã chuẩn bị sẵn cho bạn một vài dòng mã giả.

class Process
  def initialize()
    @clock = 0
  end

  def tick()
    @clock += 1
  end

  def send(receiver)
    send_to(receiver, tick())
  end

  def receive(sender_timestamp)
    @clock = max(sender_timestamp + 1, tick())
  end
end

Bạn có thể thấy có hai implementation rule ở đây (với hàm đồng hồ logic C là tick()).

IR1. tick() luôn tăng, đảm bảo trên cùng một process, timestamp của event sau luôn lớn hơn event trước. => điều này làm thỏa C1.
IR2. (a) khi gửi gói tin, process luôn tăng/tick clock của mình. (b) khi nhận tin, process luôn chọn timestamp lớn hơn hoặc bằng đồng hồ của mình và lớn hơn timestamp của sender.

Sắp xếp toàn cục

Sau khi xong phần hiện thực, ta hãy đến với bước quan trọng nhất, một hệ thống phân tán sử dụng Lamport timestamp và đồng hồ logic sẽ sắp xếp toàn cục các event như thế nào.

Bạn đoán đúng rồi. Chúng ta chỉ cần sắp xếp các event theo timestamp của chúng. Với các event có timestamp bằng nhau, ta sắp xếp chúng theo một tiêu chí bất kì nào đó.

Ta định nghĩa quan hệ => như sau: Nếu a là một event trong process Pi và b là một event trong process Pj, và là tiêu chí của chúng ta, ta có a => b nếu:

  1. Ci(a) < Ci(b).
  2. Ci(a) = Ci(b) và Pi ≺ Pj.

≺ sẽ đóng vai trò như một tie-breaker khi bạn lâm vào tình huống timestamp bằng nhau.

Giải bài toán với Lamport Timestamp

Ta sẽ áp dụng những gì đã học nãy giờ để xác định Cam mới là người xứng đáng trúng cái Quanlott.

Với Cam, Sọt là hai process trong một hệ thống phân tán. Cả hai đều có một đồng hồ logic của riêng mình: CC, và CS. Tất cả đồng hồ đều bắt đầu từ 0 và tự tick.

  • c1. Cam mua vé Quanlott, CC(c1) = 3.
  • c2. Cam gửi tin nhắn khoe với Sọt. Event này xảy ra sau c1, ta có CC(c2) = 4.
  • c3. Sau khi gửi tin, Cam thấy mình ngu nên tự vả vào mồm một cái. CC(c3) = 5.
  • s1. Sọt nhận được tin nhắn của Cam có timestamp CC(c2) = 4 và giả sử CS = 2, như đã nói ở phần trước, ta chọn số lớn hơn timestamp của cả sender và receiver. Vì vậy ta gán timestamp 5 cho CS(s1), để đảm bảo cho những event sau s1, CS luôn lớn hơn 5.
  • s2. Sọt mua vé Quanlott, event này có timestamp CS(s2) = 6.

Như vậy khi sắp xếp toàn cục các event trong hệ thống này, ta thấy event mua vé của Cam có timestamp nhỏ hơn event mua vé của Sọt. Nhờ Lamport timestamp mà Cam đã tránh được một pha úp sọt trông thấy.

Tuy nhiên một câu hỏi cũng được đặt ra: Vậy thì Sọt nhận được tin nhắn trước hay Cam tự vả vào mồm trước?.

Hai event này là hai concurrent events có timestamp bằng nhau (5).

Câu trả lời là tùy bạn. Chính xác là phụ thuộc vào điều kiện ≺ như thế nào (ví dụ như quần đứa nào ngắn hơn thì được xếp trước, hay là tên nào đẹp trai hơn thì bị xếp sau) mà ta sẽ có những thứ tự khác nhau cho những concurrent events này.

Bài viết này sẽ giúp tui tăng lương như thế nào?

Như thường lệ, bài viết này không giúp bạn tăng lương cũng như tăng xông.

Ngoài những gì được đề cập trong bài viết, paper này còn một phần giới thiệu cách dùng đồng hồ vật lý để xử lý các even ngoài luồng. Giả sử trong ví dụ của chúng ta, nếu ta không track được sự kiện Cam báo cho Sọt trong hệ thống (ví dụ Cam nói với Sọt về dãy số bằng miệng), thì đồng hồ vật lý có thể được sử dụng cho những trường hợp này.

Lamport timestamp được ứng dụng trong nhiều phần mềm phân tán, ví dụ như Vector Clock trong Riak. Vector Clock lưu lại đồng hồ logic của các process dưới dạng vector/array, và mỗi tin nhắn khi được gửi đều gởi kèm với vector clock của sender.

wiki vector clock

Tham khảo

  1. https://lamport.azurewebsites.net/pubs/time-clocks.pdf
  2. http://basho.com/posts/technical/why-vector-clocks-are-easy/
  3. http://basho.com/posts/technical/why-vector-clocks-are-hard/

NGUY HIỂM! KHU VỰC NHIỀU GIÓ!
Khuyến cáo giữ chặt bàn phím và lướt thật nhanh khi đi qua khu vực này.
Chức năng này hỗ trợ markdown và các thứ liên quan.
nvmnghia chém vào lúc

Bài hay như này mà không ai đọc. Đang cày cuyển của kleppman phần riak và leaderless (lần thứ 3 lol), thử tìm gg xem có ông việt nam nào viết, thì tìm đc chỗ này. Hình như mấy cha elixir ở VN đều bá đạo cả :o

nvmnghia chém vào lúc

Chúc anh thớt có thêm nhiều bài viết kĩ thuật bá đạo như này. Nhưng anh thớt cho em hỏi tí, mấy cái biểu đồ anh vẽ bằng gì mà địep thế ạ?

qcam chém vào lúc

hình như bài này viết xong quên publish LOL.

Mình vẽ bằng draw.io bạn ạ.

Goose97 chém vào lúc

Bài hay quá anh ơi. Mà ảo thật sáng em vô tình thế nào chui vào repo ruby-vietnam/hardcore-rule, lòng vòng thì thấy bài về chủ đề này của anh cơ mà commit từ 2 năm trước. Giờ vào nhìn title bài này đúng là giật mình

Bài viết cùng chủ đề

Trứng lòng đào và các vấn đề đồng hồ trong lập trình

Vì sao đồng hồ lại không đáng tin cậy? Dùng đồng hồ trong máy tính như thế nào thì hợp lý?

Vài ghi chép về Elixir Compiler (phần 1)

Bài viết mà thằng chả chém gió về Elixir compiler.

Viết cho tuổi 20

Bài viết mà thằng chả chém gió về tri túc các kiểu…