Giải thích bài viết của người đoạt giải Turing: “Đồng hồ sinh học” của blockchain trông như thế nào?

Tiêu đề gốc: ""Đồng hồ sinh học" của blockchain trông như thế nào? 》
Nguồn gốc: stakefish

"Thời gian" là chủ đề muôn thuở trong những năm tháng đổi thay. Các cuộc thảo luận đã và đang diễn ra trong blockchain 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.

Vấn đề về thời gian trong các 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 tiếp cận được thỏa thuận đầy đủ. . Lamport, bậc thầy về hệ thống phân tán, cung cấp cách tiếp cận phi tập trung, chuyển các vấn đề thành mối quan hệ giữa thời gian và trình tự, đồng thời đề xuất khái niệm về đồ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 Dean Eigenmann, nhà phân tích Vac và nhà phát triển ENS, giới thiệu về Lamport về thời gian, đồng hồ và tuần tự cuộc thảo luận sẽ cung cấp cho bạn một góc nhìn khác về việc hiểu blockchain và thời gian của hệ thống phân tán.

Chủ đề nào thích hợp hơn để bắt đầu chuỗi 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? Tôi sẽ để lại những chủ đề này để viết sau. Hôm nay, tôi chọn một chủ đề cơ bản làm đầu: chủ đề về thời gian trong các hệ thống phân tán.

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

Những người bạn chưa quen với Leslie Lamport có thể giới thiệu ngắn gọn. Anh ấy nổi tiếng với việc tạo ra LaTeX, TLA+, Paxos, và cũng Thảo luận về vấn đề của các tướng lĩnh Byzantine. Và tất nhiên còn có đồng hồ Lamport (đồng hồ logic đầu tiên), những khái niệm cơ bản về loại đồng hồ này cũng sẽ được giới thiệu trong bài viết này.

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

"Nếu độ trễ truyền thông tin trong một hệ thống khác với độ trễ trong một quy trình duy nhất Nếu khoảng thời gian giữa các sự kiện không thể bỏ qua thì nó được gọi là hệ thống phân tán."

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

Với định nghĩa rõ ràng, chúng ta bắt đầu phần giới thiệu chính thức.

Đặt hàng

Việc sắp xếp các sự kiện ở địa phương không thể dễ dàng hơn được. Bạn chỉ cần cung cấp cho mỗi sự kiện một dấu thời gian khi nó xảy ra. Chúng ta có thể có được thứ tự chung 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 hệ thống phân tán. Tại sao?

Mọi thứ đều do một đặc tính rất đơn giản của hệ thống phân tán: các tin nhắn được truyền giữa các nút sẽ được gửi đi sau , có thể đến 0 lần, 1 lần 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 tin nhắn đã được gửi đi trong bao lâu và cũng không có cách nào để xác nhận liệu khi đến nơi có còn là 12:00:00 hay không. Nếu đúng như vậy, các nút sẽ gửi tin nhắn qua lại trong cả ngày mà không thể xác định liệu thông tin có được đồng bộ hóa hay không. Nếu chúng ta không thể đồng ý về thời gian thì chúng ta không thể đồng ý về trình tự các sự kiện.

Làm cách nào để giải quyết vấn đề này?

Trong hệ thống phân tán, nhiều nút giao tiếp bằng cách gửi thông tin cho nhau. Khi một nút nhận được một tin nhắn, đầu tiên nó sẽ xác nhận tin nhắn đó và sau đó thực hiện sự kiện tiếp theo. Trình tự này vốn thể hiện 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.

Bản dịch: Mối quan hệ nhân quả này là mối quan hệ thời gian, 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 nó . Chỉ cần nhìn vào hai sự kiện A và B, ta có thể đưa ra mối quan hệ “xảy ra trước” để mô tả trình tự.

Bây giờ, mối quan hệ này có thể được xác định mà không cần khái niệm vật lý về thời gian hệ thống: nếu A gây ra nguyên nhân tác động lên B, Sự kiện A phải xảy ra trước sự kiện B. Tính 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, đó là thứ tự một phần.

Việc sắp xếp từng phần cũng có một hạn chế: nếu không xác định được mối tương quan, chúng ta có thể không biết ý nghĩa của mọi sự kiện trong hệ thống. Thứ tự chính xác. Bởi vì có thể có nhiều sự kiện diễn ra đồng thời trong 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.

Đồng hồ

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

Chúng ta vừa 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, vì vậy chúng ta cần sử dụng đồng hồ logic cái đồng hồ. Đồng hồ logic về cơ bản là một hàm gán số cho một sự kiện. Con số này biểu thị thời gian xảy ra sự kiện (từ bây giờ chúng ta sẽ gọi con số này là thời gian) và không liên quan gì đến thời gian vật lý.

Chúng tôi giả định rằng mỗi nút trong hệ thống phân tán này có một đồng hồ. Đồng hồ này tích tắc khi các sự kiện được thực thi, nhưng tiến trình của đồng hồ không được coi là một sự kiện trong hệ thống. Đối với mỗi sự kiện xảy ra trên một nút trong hệ thống, đồng hồ logic sẽ gán một số cho sự kiện đó. Theo giả định này, chúng ta có thể thỏa mãn điều kiện đồng hồ sau:

∀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 đó", còn C tượng trưng cho chức năng đồng hồ, Có thể hiểu đơn giản là như thời gian. Vậy ý nghĩa 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 ngắn hơn thời gian của b.

Nhưng suy luận này không có giá trị, chỉ vì thời gian của sự kiện này nhỏ hơn thời gian của sự kiện khác nên nó đúng không có nghĩa là sự kiện này đã xảy ra trước đây, chúng có thể xảy ra đồng thời.

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

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ì a là Thời gian sẽ 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 là ít hơn thời gian b.

Các nút cần duy trì đồng hồ chạy giữa các sự kiện. Nếu không, đồng hồ phải được chuyển sang thời điểm muộn hơn thời gian có trong bất kỳ tin nhắn 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 tiến lên.

Bây giờ, chúng ta có thể sử dụng đồng hồ đáp ứng các điều kiện này để thiết lập trình tự tổng thể của toàn bộ hệ thống phân tán. Ở đây, chúng ta chỉ cần sử dụng những đồng hồ đáp ứng các điều kiện này .Đồng hồ cho thời gian để sắp xếp.

Trường hợp sử dụng

Cuối cùng, chúng tôi thiết lập một máy trạng thái để xem cách 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ẻ nhưng chỉ có thể truy cập một nút tại một thời điểm. Máy trạng thái cần đáp ứng các điều kiện sau:

Điều kiện 1: 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 và sau đó các nút khác sẽ đến thăm anh ta.

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

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

Tại sao không giới thiệu điều phối viên trung gian? Bởi vì trong trường hợp này, nếu yêu cầu xảy ra sớm hơn nhưng đến muộn hơn thì điều kiện 2 không thể được đáp ứng; 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 để thỏa mãn đồ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 giải pháp phi tập trung. Đầu tiên, chúng ta cần tất cả các nút để lưu trữ hàng đợi yêu cầu. Thứ hai, phải đáp ứng một số giả định đơn giản:

Giả định 1: Tất cả tin nhắn đều được nhận theo thứ tự gửi.

Giả định 2: Cuối cùng thì tất 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 thì có thể bỏ qua các giả định trên.

Bây giờ chúng ta có thể xác định một thuật toán thỏa mãn 3 điều kiện này và thể hiện 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 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ó cho các nút khác nút.

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

3. Nút giải phóng tài nguyên sẽ gửi một thông báo phát hành kèm theo thời gian hiện tại và xóa bản gốc khỏi tài nguyên đó xếp hàng. hỏi.

4. Khi nút nhận được thông báo phát hành, nó sẽ xóa các 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 thứ tự thời gian) , anh ta có thể tự do truy cập tài nguyên và 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 thi hoàn toàn độc lập bởi mỗi nút. Nó sử dụng đồng hồ để xử lý các yêu cầu theo tổng số yêu cầu. Sắp xếp để đạt được quyền truy cập vào tài nguyên và phối hợp giữa các nút.

Được rồi, qua bài viết chúng ta đã hiểu đại khái 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 các bài toán ứng dụng thực tế trong việc xác định thứ tự khi truy cập tài nguyên trong hệ thống phân tán. Hoan nghênh những ý kiến đóng góp của mọi người, mình sẽ tiếp tục cập nhật thêm nhiều 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ự
Tác giả: Dean Eigenmann
Biên soạn bởi: stakefish

Nguồn gốc: weixin.qq.com

Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia