"Đồng hồ sinh học" của blockchain trông như thế nào?

“Thời gian” là đề tài muôn thuở trong thời thế đổi thay. Các cuộc thảo luận về thời gian đã diễn ra trong chuỗi khối và các hệ thống phân tán khác. Thời gian kết nối các quy trình và nút, đồng thời chúng tôi cũng sử dụng "độ chi tiết" của thời gian để đo lường mạng phi tập trung kết nối các khối thành chuỗi.

Khó khăn về thời gian trong một hệ thống phân tán là rất khó để "đồng hồ vật lý" của những người tham gia khác nhau thống nhất hoàn toàn. Bậc thầy hệ thống phân tán Lamport cung cấp một phương pháp phi tập trung, biến vấn đề thành mối quan hệ giữa thời gian và trật tự, đồng thời đưa ra khái niệm đồng hồ logic, giống như giới thiệu "đồng hồ sinh học" cho các hệ thống phân tán bao gồm cả chuỗi khối.

stakefish biên soạn một bài viết của nhà phân tích Vac và nhà phát triển ENS Dean Eigenmann, giới thiệu cuộc thảo luận của Lamport về thời gian, đồng hồ và trật tự, đồng thời nhắc nhở mọi người hiểu về chuỗi khối và thời gian của hệ thống phân tán từ một góc độ khác.

Chủ đề nào thích hợp hơn để bắt đầu loạt bài viết về hệ thống phân tán? Giao thức giao dịch riêng tư của Ethereum AZTEC? Thuật toán Paxos nổi tiếng là khó thành thạo? Những chủ đề này được để lại để viết sau. Hôm nay, tôi chọn một chủ đề cơ bản để bắt đầu: chủ đề về thời gian trong các hệ thống phân tán.

Bài viết này giải thích bài báo nổi tiếng "Thời gian, đồng hồ và thứ tự các sự kiện trong một hệ thống phân tán" của người đoạt giải Turing và chuyên gia máy tính Leslie Lamport. Thật thú vị khi đọc lại bài đăng này một thời gian dài sau đó và chắt lọc các khái niệm chính.

Những người bạn không quen thuộc với Leslie Lamport có thể có một ý tưởng chung, anh ấy nổi tiếng vì đã tạo ra LaTeX, TLA +, Paxos và cũng thảo luận về vấn đề chung của Byzantine. Tất nhiên còn có đồng hồ Lamport (đồng hồ logic đầu tiên), và trong bài viết này chúng tôi cũng sẽ giới thiệu các khái niệm cơ bản của nó.

Trước tiên chúng ta hãy xem định nghĩa của một hệ thống phân tán. Định nghĩa do Lamport đưa ra là:

"Một hệ thống được gọi là hệ thống phân tán nếu độ trễ trong việc cung cấp thông tin trong hệ thống không đáng kể so với thời gian giữa các sự kiện trong một quy trình."

Tôi thích định nghĩa này vì nó tập trung vào độ trễ giữa gửi và nhận tin nhắn.

Với định nghĩa được xác định rõ ràng, chúng tôi bắt đầu giới thiệu chính thức.

tiêu đề phụ

Sắp xếp các sự kiện cục bộ không thể dễ dàng hơn. Bạn chỉ cần gán cho mỗi sự kiện một dấu thời gian khi nó xảy ra. Chúng ta có thể thu được thứ tự tổng thể của tất cả các sự kiện, nghĩa là tất cả các sự kiện có thể được sắp xếp theo một thứ tự cụ thể.

Nhưng vấn đề này khó khăn hơn nhiều trong bối cảnh của các hệ thống phân tán. Tại sao?

Tất cả chỉ vì bản chất rất đơn giản của một hệ thống phân tán: sau khi một tin nhắn được gửi giữa các nút, nó có thể đến 0, 1 hoặc nhiều lần tại bất kỳ thời điểm nào trong tương lai. Trong trường hợp này, các nút khác nhau trong hệ thống phân tán không thể thống nhất về thời gian. Ví dụ:

Một nút có thể gửi tin nhắn đến một nút khác để đánh dấu thời gian hiện tại là 12:00:00, nhưng người nhận không biết mất bao lâu để gửi tin nhắn, vì vậy không có cách nào để xác nhận xem nó có còn là 12:00 hay không: 00 khi nó đến. Nếu vậy, không có cách nào để xác định xem thông tin có được đồng bộ hóa hay không ngay cả khi các tin nhắn được gửi qua lại trong cả ngày giữa các nút. Nếu chúng ta không thể đồng ý về thời gian, chúng ta không thể đồng ý về trình tự các sự kiện.

Vậy làm thế nào để giải quyết vấn đề này?

Trong một hệ thống phân tán, nhiều nút giao tiếp bằng cách gửi tin nhắn cho nhau. Khi nút nhận được thông tin, trước tiên nút sẽ xác nhận thông tin và sau đó thực hiện sự kiện tiếp theo của nó. Thứ tự như vậy ban đầu cho thấy một "mối quan hệ nhân quả": thông tin phải được gửi trước khi có thể nhận được.

Chú thích: Mối quan hệ nhân quả này là mối quan hệ tuần tự, không phải là mối quan hệ logic giữa nguyên nhân và kết quả.

Sau đó, thứ tự có thể được rút ra dựa trên mối quan hệ nhân quả: tin nhắn phải được gửi trước khi anh ta nhận được. Chỉ cần nhìn vào hai sự kiện A và B, chúng ta có thể diễn tả thứ tự bằng cách đưa ra mối quan hệ “xảy ra trước”.

Bây giờ, mối quan hệ này có thể được xác định mà không cần một khái niệm hệ thống về thời gian vật lý: sự kiện A phải xảy ra trước sự kiện B nếu A có tác động nhân quả lên B. Quan hệ nhân quả cho phép chúng ta xác định thứ tự của các sự kiện liên quan trong một hệ thống, thứ tự từng phần.

Thứ tự một phần cũng có một hạn chế: không thể xác định các phụ thuộc, chúng tôi có thể không biết thứ tự chính xác của mọi sự kiện trong hệ thống. Vì có thể có nhiều sự kiện xảy ra đồng thời trên toàn hệ thống nên không phải tất cả các nút đều biết về sự xuất hiện của những sự kiện này.

tiêu đề phụ

Nhưng bây giờ chúng ta có một phần thứ tự, chúng ta có thể thêm đồng hồ vào hệ thống để có được thứ tự tổng thể của tất cả các sự kiện trong hệ thống.

Vừa rồi chúng ta đã biết rằng việc sử dụng đồng hồ vật lý trong các hệ thống phân tán là không khả thi, khi đó chúng ta cần sử dụng đồng hồ logic. Đồng hồ logic về cơ bản là một chức năng có khả năng gán một số cho một sự kiện. Con số này biểu thị thời điểm sự kiện xảy ra (từ bây giờ chúng ta sẽ gọi con số này là thời gian) và không liên quan đến thời gian vật lý.

chữ

∀a,b a → b ⟹ C(a) < C(b)

Biểu thức trên có nghĩa là gì?

Mũi tên "→" có nghĩa là "xảy ra trước (xảy ra trước)", và C đại diện cho chức năng đồng hồ, có thể hiểu đơn giản là thời gian. Vậy để diễn đạt ý là: với mỗi biến cố a, b, nếu a xảy ra trước b thì thời gian của a nhỏ hơn thời gian của b.

Nhưng suy diễn ngược lại không đúng, chỉ vì thời gian của biến cố này nhỏ hơn thời gian của biến cố kia, không thể nói biến cố này xảy ra trước, chúng có thể đồng quy.

Trong hình trên, chúng ta có thể thấy rằng trên nút α, một sự kiện xảy ra lần lượt tại thời điểm 1 và thời điểm 2; nút β có một sự kiện xảy ra tại chính thời điểm 1 của nó. Các sự kiện tại thời điểm 1 và thời điểm 2 tại nút α đồng thời với các sự kiện tại thời điểm 1 tại nút β và không có mối liên hệ nhân quả nào.

• Nếu a và b là hai sự kiện trên một nút và a xảy ra trước b, thì thời gian của a phải nhỏ hơn thời gian của b.

• Nếu a là nút gửi tin nhắn và b là nút khác nhận tin nhắn, thì thời gian của a vẫn phải nhỏ hơn thời gian của b.

Các nút cần để đồng hồ tích tắc giữa các sự kiện. Nếu không, đồng hồ phải được nâng cao đến thời gian muộn hơn thời gian có trong bất kỳ thông báo nào nhận được từ các nút khác. b có thể xảy ra sau khi đồng hồ được điều chỉnh nhanh.

Ví dụ

Ví dụ

Cuối cùng, chúng tôi thiết lập một máy trạng thái để xem việc sử dụng đồng hồ logic. Ví dụ: chúng tôi có một hệ thống phân tán trong đó nhiều nút muốn truy cập tài nguyên được chia sẻ và mỗi lần chỉ có thể truy cập một nút. Máy trạng thái cần đáp ứng các điều kiện sau:

• Điều kiện 1: Một nút có thể truy cập tài nguyên trước tiên phải giải phóng tài nguyên đó trước khi các nút khác có thể truy cập.

• Điều kiện 2: Yêu cầu tài nguyên phải được cấp quyền truy cập theo thứ tự yêu cầu được thực hiện.

• Điều kiện 3: Nếu mọi nút được cấp quyền truy cập cuối cùng sẽ giải phóng tài nguyên, thì mọi yêu cầu cuối cùng sẽ được cấp.

Tại sao không giới thiệu một điều phối viên trung gian? Bởi vì trong trường hợp này, nếu một yêu cầu xảy ra sớm hơn nhưng lại đến sau thì điều kiện 2 không thể được thỏa mãn, một lý do khác là chúng tôi muốn áp dụng giải pháp phi tập trung.

Vì vậy, chúng ta vẫn phải xây dựng các điều kiện để đáp ứng đồng hồ logic này. Làm thế nào để đáp ứng các điều kiện?

Lamport cung cấp cho chúng tôi một giải pháp phi tập trung. Đầu tiên, chúng tôi muốn tất cả các nút lưu trữ hàng đợi yêu cầu. Thứ hai, một số giả định đơn giản phải được thỏa mãn:

• Giả định 1: Tất cả các tin nhắn được nhận theo thứ tự chúng được gửi.

• Giả định 2: Cuối cùng tất cả các tin nhắn đều được nhận.

• Giả định 3: Mỗi nút có thể gửi tin nhắn trực tiếp đến tất cả các nút khác trong hệ thống.

Nếu có các thuật toán và giao thức phức tạp hơn, các giả định trên có thể được bỏ qua.

Bây giờ chúng ta có thể định nghĩa một thuật toán thỏa mãn 3 điều kiện này và chỉ ra chức năng của đồng hồ trong thực tế:

1. Nếu một nút muốn yêu cầu một tài nguyên, nó sẽ tạo một yêu cầu với thời gian hiện tại, thêm nó vào hàng đợi của nó và gửi nó đến mọi nút khác.

2. Tất cả các nút khác đặt yêu cầu này vào hàng đợi của chúng và gửi lại thông báo phản hồi.

3. Nút giải phóng tài nguyên gửi thông báo giải phóng với thời gian hiện tại và xóa yêu cầu ban đầu khỏi hàng đợi của nó.

4. Khi nút nhận được thông báo giải phóng, nó sẽ xóa yêu cầu liên quan khỏi hàng đợi của chính nó.

5. Khi một nút có yêu cầu riêng trong hàng đợi của nó trước bất kỳ yêu cầu nào khác (theo tổng số thứ tự thời gian), anh ta có thể tự do truy cập tài nguyên đó và anh ta nhận được tin nhắn từ tất cả các nút khác sau thời gian đó.

Thuật toán trên là một thuật toán phi tập trung được thực hiện hoàn toàn độc lập bởi mỗi nút, sử dụng đồng hồ để sắp xếp các yêu cầu theo một thứ tự chung, nhằm đạt được quyền truy cập vào tài nguyên và sự phối hợp giữa các nút.

Chà, thông qua bài viết, chúng ta đã tìm hiểu sơ bộ về cách sử dụng các đồng hồ logic này để sắp xếp các sự kiện trong hệ thống phân tán và phân tích ứng dụng thực tế của việc xác định thứ tự khi hệ thống phân tán truy cập tài nguyên. Phản hồi rất được hoan nghênh và tôi sẽ tiếp tục cập nhật thêm các bài viết về hệ thống phân tán.

Tiêu đề gốc: Thời gian, đồng hồ và trật tự

Bởi Dean Eigenmann

chữ