1. Mục tiêu lý tưởng của hệ thống phân tán

• Hệ thống phân tán mà chuỗi khối thuộc về còn được gọi là "Máy trạng thái nhân bản". Mục tiêu của nó rất đơn giản: tất cả các máy tính trong hệ thống đều đồng ý về một giá trị đầu ra nhất định, có nghĩa là: tất cả các máy tính trong hệ thống Nút/máy tính đều có cùng trạng thái ban đầu và sau khi thực hiện giao dịch, tất cả các nút có cùng trạng thái cuối cùng.

• Điều này không khó để đạt được nếu tất cả các máy tính đều hoạt động tốt và giao tiếp giữa chúng được đồng bộ hóa hoàn hảo. Nhưng thực tế không phải như vậy, chủ yếu có hai loại vấn đề:

Một số/một số máy tính bị hỏng, có thể không tính được kết quả hoặc không kết nối được với hệ thống.

Những sự cố này là phổ biến và không thể tránh khỏi, và một khi sự cố xảy ra, tất cả các máy tính sẽ không thể đồng ý về một kết quả đầu ra nhất định. Hệ thống phân tán nổi tiếng "Nguyên tắc bất khả thi FLP" được mô tả như sau: Trong một hệ thống có mạng đáng tin cậy nhưng mô hình không đồng bộ tối thiểu cho phép lỗi nút, không có thuật toán đồng thuận xác định nào có thể giải quyết vấn đề nhất quán. Theo thuật ngữ của giáo dân: miễn là một máy tính trong hệ thống bị lỗi, hệ thống không thể đạt được sự đồng thuận về giá trị đầu ra.

Nguyên tắc Bất khả thi của FLP cho chúng ta biết: đừng lãng phí thời gian để thiết kế các thuật toán đồng thuận cho các hệ thống phân tán đối mặt với mọi tình huống, điều đó là không thể.

tiêu đề phụ

2. Thuật toán đồng thuận cho hệ thống phân tán

Mặc dù nguyên tắc bất khả thi của FLP là tàn nhẫn, nhưng những lợi ích mà các hệ thống phân tán có thể mang lại rất đáng để đối mặt với khó khăn. Vì không có thuật toán đồng thuận cho tất cả các kịch bản nên có thể tìm thấy một số thuật toán đồng thuận có hiệu quả trong các kịch bản cụ thể. Thuật toán đồng thuận đề cập đến một phương pháp để một hệ thống phân tán đạt được sự đồng thuận.

Hãy xem cách các nhà khoa học từng bước giới hạn kịch bản và hiện thực hóa thuật toán đồng thuận trong kịch bản này.

Đầu tiên, nếu mỗi máy tính trong hệ thống có thể đưa ra kết quả của riêng mình, tình hình chắc chắn sẽ phức tạp, bởi vì chúng tôi thậm chí không biết nên đạt được sự đồng thuận về kết quả nào. Do đó, bước đầu tiên trong việc giải quyết vấn đề đồng thuận là xác định sự đồng thuận là gì.Phương pháp đơn giản nhất là một máy tính nhất định có tiếng nói cuối cùng, nó đề xuất một kết quả và các máy tính khác đồng ý với kết quả đó.

Máy tính có tiếng nói cuối cùng được gọi là người đề xuất hoặc người lãnh đạo. Mặc dù đạt được sự đồng thuận thông qua người lãnh đạo không phải là cách duy nhất để giải quyết vấn đề, nhưng hầu hết các giao thức đều được thực hiện trên cơ sở này, bao gồm cả thuật toán đồng thuận được sử dụng trong hệ thống chuỗi khối.

Như vậy bạn thấy đấy, không có sự phân quyền tuyệt đối Bước đầu tiên để đạt được sự đồng thuận là xác định một trung tâm.

• Lạc đề: Khi biết được điều này, chúng ta mới có thể thiết lập một cuộc thảo luận hiệu quả hơn về phân quyền, chẳng hạn ở đây không thể nói chung chung về phân quyền mà là: phương thức tuyển chọn lãnh đạo này có nên đi đến tập trung hay không.

• Quay lại chủ đề. Các bước hoạt động của thuật toán đồng thuận yêu cầu người lãnh đạo đại khái như sau:

• bầu người lãnh đạo;

• Người lãnh đạo đề xuất một kết quả;

Nếu mọi người thống nhất về kết quả, hệ thống sẽ đưa ra kết quả cuối cùng, nếu mọi người không thống nhất thì quay lại bước 1 và bắt đầu lại.

Dòng suy nghĩ này cung cấp một cách để đạt được sự đồng thuận, nhưng nó còn lâu mới thực sự đạt được sự đồng thuận. Vì nếu máy tính không kết nối được với hệ thống thì không thể biểu quyết có đồng ý với kết quả của người đứng đầu hay không, nếu máy tính gặp sự cố lại là người đứng đầu thì tình hình sẽ còn tồi tệ hơn, và toàn bộ hệ thống sẽ điêu đứng. đến bế tắc.

tiêu đề phụ

3. Giả thuyết đồng bộ hóa thuật toán đồng thuận

Làm thế nào để giải quyết vấn đề thời gian chết ở trên? Phương pháp nói rất đơn giản: nếu một máy tính không thể kết nối với hệ thống, hãy bỏ qua nó và không tham gia vào vòng đồng thuận này.

Khi đó một câu hỏi mới lại đặt ra, làm sao biết nó không kết nối được với hệ thống, hay đang tham gia đồng thuận nhưng tốc độ chậm hơn các máy khác?

Kết quả là, các nhà khoa học đã phát triển một trong những giả định quan trọng nhất để giải quyết vấn đề đồng thuận: giả định về tính đồng bộ. Giả định về tính đồng bộ đưa ra khái niệm "thời gian chờ", có nghĩa là khung thời gian được đặt trước và nếu người lãnh đạo không đưa ra đề xuất trong khung thời gian đó, đề xuất đó sẽ bị loại bỏ và người lãnh đạo mới sẽ được bầu. Theo cách này, lỗi của nút dẫn đầu có thể được chấp nhận. (Lưu ý: giả định đồng bộ không bằng giả định đồng bộ)

Cả thuật toán Paxos và thuật toán Raft đều được đề xuất dựa trên giả định về tính đồng bộ. Nhưng hai thuật toán này cũng cần đưa ra một giả định khác về hệ thống, đó là tất cả các máy tính trong hệ thống đều là "người tốt", chúng hoặc phản hồi đúng theo đề xuất của người lãnh đạo, hoặc không phản hồi do bị lỗi.

Vì vậy, cuối cùng chúng ta có một hệ thống phân tán có thể đạt được sự đồng thuận, mặc dù nó có những điều kiện nghiêm ngặt.

Thuật toán đồng thuận Paxos là thuật toán đồng thuận dựa trên thông báo và có khả năng chịu lỗi cao do Leslie Lamport đề xuất vào năm 1990. Nó có vị trí quan trọng trong lĩnh vực ứng dụng hệ thống phân tán, bao gồm cả Google. Thuật toán này được sử dụng trong các hệ thống phân tán lớn của nhiều công ty, bao gồm . Và giai đoạn khám phá đầu tiên của chúng ta cũng có thể kết thúc tại đây, tiếp theo là giai đoạn thứ hai.

tiêu đề phụ

4. Loại bỏ những “kẻ xấu” trong hệ thống

Mặc dù Paxos có thể đạt được sự đồng thuận, nhưng thuật toán của nó dựa trên tiền đề rằng tất cả các máy tính đều là "người tốt". Và nếu có "kẻ xấu" trong máy tính, giọng nói của kẻ xấu và giọng nói của người tốt sẽ xuất hiện trong hệ thống và thuật toán Paxos không thể xử lý tình huống này.

Chúng ta cần một thuật toán có thể đạt được sự đồng thuận ngay cả khi có sự hiện diện của những kẻ xấu, điều đó có khả thi không? Leslie Lambert đã phát triển một mô hình để thảo luận về khả năng này, được gọi là Vấn đề chung của Byzantine, trong đó các nút Byzantine là các nút của kẻ xấu truyền các thông báo gây rối khiến toàn bộ hệ thống không đạt được sự đồng thuận.

Trong bài báo "The Byzantine Generals Problem", Lambert đã đề xuất một số giải pháp, một trong số đó có thể đạt được sự đồng thuận của hệ thống khi các nút Byzantine nhỏ hơn 1/3. Nói cách khác, nếu số lượng kẻ xấu trong hệ thống ít hơn 1/3, thì có thể đạt được sự đồng thuận thông qua các thuật toán.

• Thuật toán DLS và thuật toán PBFT (Practical Byzantine Fault Tolerant Algorithm) xuất hiện sau đó đều được phát triển trên cơ sở này.

• PBFT là một thuật toán chịu lỗi Byzantine tiêu biểu và quy trình triển khai của nó đại khái như sau. Sẽ không sao nếu bạn không hiểu quy trình, miễn là bạn biết rằng bạn có thể đạt được sự đồng thuận thông qua phương thức giao tiếp này.

• giai đoạn chuẩn bị trước: người lãnh đạo gửi kết quả cho tất cả những người theo dõi. Người dẫn đầu là nút 0 trong biểu đồ này và nó sẽ gửi kết quả cho những người theo dõi 1, 2 và 3.

• Giai đoạn chuẩn bị: Nếu người theo dõi cho rằng kết quả là chính xác, hãy nói với tất cả các nút khác để phê duyệt kết quả. Ví dụ: nút 1 sẽ gửi thông báo phê duyệt của nó tới các nút 0, 2 và 3.

Giai đoạn cam kết: Nếu người theo dõi thấy rằng hơn 2/3 số nút đồng ý với kết quả của người dẫn đầu, họ sẽ yêu cầu tất cả các nút khác chấp nhận kết quả này là kết quả cuối cùng.

Cho đến nay, chúng tôi đã giải quyết vấn đề đồng thuận của các hệ thống phân tán với các nút Byzantine. Tuy nhiên, nếu số lượng kẻ xấu trong hệ thống bằng hoặc hơn 1/3 thì vẫn không thể đi đến thống nhất. Những gì chúng ta có thể làm là làm cho những kẻ xấu ít hơn 1/3 thông qua các điều kiện hoặc ưu đãi truy cập của hệ thống.

Việc khám phá giai đoạn thứ hai của hệ thống phân tán kết thúc tại đây, và sau đó bước vào giai đoạn thứ ba.

tiêu đề phụ

5. Thuật toán đồng thuận Nakamoto

Cả Paxos và PBFT đều sử dụng giả định về tính đồng bộ Trên thực tế, hầu hết tất cả các nghiên cứu về thuật toán đồng thuận đều theo hướng này cho đến khi sự xuất hiện của thuật toán đồng thuận Nakamoto. Sự đồng thuận của Nakamoto sử dụng một cơ chế không xác định.

Nó có nghĩa là gì? Chúng ta có thể nghĩ về một hệ thống phân tán bao gồm 12 máy tính như một ban giám khảo gồm 12 bồi thẩm viên. Chúng tôi nhốt 12 người này trong phòng họp, phát biên bản giải thích vụ án rồi ngồi ở cửa phòng họp chờ họ đưa ra kết quả phiên tòa.

12 người này sẽ có những ý kiến ​​​​khác nhau về cách đánh giá và có thể thay đổi vị trí của họ khi cuộc thảo luận diễn ra, và một số người có thể ngủ gật và không thể bày tỏ ý kiến ​​​​của mình (tham khảo "Twelve Angry Men"). Khi đó người ngồi đợi ở cửa có hai lựa chọn. Lựa chọn đầu tiên là để bạn thảo luận và tôi có thể đợi bao lâu tùy ý, nhưng cuối cùng bạn phải cho tôi kết quả thử nghiệm xác định duy nhất; lựa chọn thứ hai là tôi không thể chờ đợi, và trước tiên bạn đưa ra kết quả mà hầu hết mọi người đồng ý Tôi, nếu có một kết quả mà nhiều người đồng ý, tôi sẽ chuyển sang kết quả đó.

Rõ ràng, chúng ta chỉ có thể chọn một trong hai, nếu bắt buộc phải xác nhận kết quả thì không có gì đảm bảo sẽ có kết quả, nếu bắt buộc phải có kết quả thì không có gì đảm bảo kết quả đó phải là kết quả cuối cùng.

• Đây là trường hợp của các hệ thống phân tán. Chỉ có hai tùy chọn. Tùy chọn đầu tiên được gọi là Finality, có nghĩa là "sự chắc chắn của kết quả" hoặc bảo mật; tùy chọn thứ hai được gọi là Liveness, có nghĩa là hoạt động hoặc tính khả dụng của mạng.

• Hai lựa chọn này xác định hai ý tưởng thiết kế khác nhau cho sự đồng thuận phân tán:

Việc theo đuổi Finality là kết quả ưu tiên, vì vậy cần phải đưa ra các yêu cầu trên mạng. PBFT và Tendermint đều là các thuật toán thuộc loại này, tuân theo giả định đồng bộ hóa mạng và các hệ thống sử dụng các thuật toán như vậy sẽ không phân nhánh.

Bên cạnh đó, việc chọn một trong Finality và Liveness cũng là một biểu hiện của định lý CAP (tam giác bất khả thi) của các hệ thống phân tán. Định lý cho biết: Đối với một hệ thống phân tán, không thể đồng thời thỏa mãn tính nhất quán, tính sẵn sàng và dung sai phân vùng. Bởi vì khả năng chịu lỗi phân vùng có nghĩa là hệ thống phải có khả năng chịu đựng được các phân vùng mạng và mạng thực chắc chắn sẽ được phân vùng, vì vậy điều kiện này phải được đáp ứng. tính nhất quán và tính khả dụng, trong số đó, tính nhất quán của CAP phản ánh tính chính xác và tính khả dụng của CAP phản ánh tính sống động.

Cho dù đó là Nguyên lý Bất khả thi của FLP hay Định lý Bất khả thi của CAP, họ không nói với chúng ta rằng: con đường này rất khó đi qua, và nếu bạn đột phá, đó sẽ là một phát kiến ​​vĩ đại; điều họ nói với chúng ta là: con đường này sẽ không làm việc, bạn phải làm Việc phải đánh đổi và lựa chọn theo nhu cầu.

Các thuật toán đồng thuận sử dụng các giả định về tính đồng bộ đã được giới thiệu chi tiết ở trên và chúng đạt được sự đồng thuận bằng cách đưa ra khái niệm về thời gian chờ và bỏ qua các máy tính gặp sự cố.

Sự đồng thuận của Nakamoto sử dụng cơ chế không xác định cũng được mô tả đơn giản: nếu bạn thấy một khối được đề xuất có nhiều bằng chứng công việc nhất, hãy chấp nhận khối đó, còn được gọi là quy tắc chuỗi dài nhất. Quy trình thực hiện cụ thể của nó thì mọi người đã quen thuộc nên mình sẽ không nhắc lại trong bài viết này.

Bây giờ, hãy xem các hệ thống sử dụng các giả định đồng bộ (Finality, được sử dụng nhiều hơn trong PoS) khác với các hệ thống sử dụng các cơ chế không xác định (Liveness, được sử dụng nhiều hơn trong PoW) khác nhau như thế nào. Nhưng cần phải nhắc lại rằng không phải tất cả PoS đều là lộ trình cuối cùng, chẳng hạn như Casper FFG; và PoW không giới hạn ở lộ trình Liveness, mặc dù không ai thiết kế sự đồng thuận cuối cùng về PoW.

Sự khác biệt giữa PoW và PoS là một cái là Công việc và cái kia là Cổ phần. Lý do tại sao điểm này cần được nhấn mạnh là trong các cuộc thảo luận về PoW và PoS, chúng ta thường không thảo luận về sự khác biệt giữa cơ chế Work và cơ chế Stake, mà là so sánh sự khác biệt giữa hệ thống Finality và hệ thống Liveness. Ví dụ: "không có quyền" về cơ bản là một chủ đề giữa hệ thống Finality và hệ thống Liveness, không phải là cuộc tranh luận giữa Công việc và Cổ phần.

Hãy quay trở lại căn phòng với 12 người đánh giá. Để theo đuổi Finality, mỗi người đánh giá cần biết ý tưởng của mọi người khác và cũng cần nói cho những người khác biết ý tưởng của họ, do đó, độ phức tạp trong giao tiếp sẽ tăng nhanh khi số lượng người đánh giá tăng lên và do đó toàn bộ hệ thống sẽ không khả dụng, nên phải khống chế số lượng Hội thẩm.

Khi đó đối với hệ thống phân tán, chỉ một số nút được chọn để vào phòng họp và họ quyết định sự đồng thuận, trong khi các nút khác chỉ chấp nhận sự đồng thuận. Vì vậy, trong hệ thống này có ba vai trò là người lãnh đạo, người theo dõi và người học hỏi Người lãnh đạo và người theo dõi là những người phản biện trong phòng họp, họ cần phải làm việc tốt, nếu không hệ thống có thể không đạt được sự thống nhất.

Đồng thuận Nakamoto theo đuổi sự sống động Các nút/người đánh giá không cần giao tiếp với mọi nút khác, họ chỉ cần giao tiếp với các nút xung quanh mình, do đó độ phức tạp giao tiếp sẽ không tăng do số lượng nút tăng lên. Nếu bạn muốn trở thành thẩm phán, bạn có thể bước vào phòng họp và trở thành thẩm phán mà không cần xin phép, và điều đó sẽ không gây khó khăn cho ban giám khảo để đạt được sự đồng thuận, đồng thời, bạn không thể làm việc hoặc rời đi bất cứ lúc nào thời gian. Chỉ có hai vai trò trong hệ thống, người lãnh đạo và người theo dõi, và mọi người đều tham gia vào sự đồng thuận trong phòng họp đó.

Có vẻ như sự đồng thuận của Nakamoto dường như phù hợp hơn với mong đợi của mọi người về tính mở của các hệ thống phân tán, nhưng đừng quên rằng nó có thể được thiết kế theo cách này vì nó hy sinh tính cuối cùng và đầu ra của nó là kết quả cuối cùng mang tính xác suất.

Hãy thử tưởng tượng, bạn nhận được 100% một ly cà phê tại Starbucks, nhưng Starbucks không nhận được 100% số tiền, điều này không phù hợp với quy tắc của thế giới mà hầu hết mọi người đều hiểu. Vì vậy, cơ chế không tất định có những thiếu sót và kịch bản không phù hợp.

Mặt khác, sau khi hệ thống hoàn thiện đảm bảo tính chắc chắn của kết quả, thiết kế hệ thống phải theo đuổi tính Sống động; và sau khi hệ thống Sống động đảm bảo tính mở của mạng, thiết kế hệ thống phải theo đuổi tính chất cuối cùng ngược lại. Để cải thiện tính chắc chắn hoặc bảo mật của kết quả, Đồng thuận Nakamoto cần thực hiện các nhượng bộ khác, chẳng hạn như TPS.

Vì vậy, bạn thấy đấy, thiết kế một hệ thống phân tán giống như thỏa thuận với Satan, bạn nhận được một số và bạn phải cho đi một số. Không có hệ thống tốt nhất, chỉ có hệ thống phù hợp để giải quyết một số loại vấn đề nhất định; không có so sánh chỉ số đơn giản, chỉ có cài đặt nào để đạt được chỉ số này.

Nếu bạn hiểu điều này thì mục đích của bài viết này đã đạt được và việc khám phá các hệ thống phân tán của chúng ta đã kết thúc ở đây.

Sáu, đi xa hơn

Liên Văn Lưu ý:

- How Does Distributed Consensus Work?

https://medium.com/

Bài viết này được lấy cảm hứng từ bài viết "Sự đồng thuận phân tán hoạt động như thế nào?" Nếu bạn muốn tìm hiểu thêm về các hệ thống phân tán, tôi khuyên bạn nên viết bài viết này, bài viết này giới thiệu sự đồng thuận phân tán từ góc độ chuyên môn; cũng đề xuất "CHÚNG TÔI NÓI GÌ KHI CHÚNG TA NÓI VỀ HỆ THỐNG PHÂN PHỐI", liệt kê một cách có hệ thống các bài báo cổ điển về các hệ thống phân tán.

https://ethfans.org/

- WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS

http://alvaro-videla.com/

Liên Văn Lưu ý:

- Bản dịch tiếng Trung của "Cách thức hoạt động của sự đồng thuận phân tán", bởi EthFans

Một vấn đề quan trọng khác trong các hệ thống phân tán là thời gian. Tất cả các thuật toán đồng thuận cần phải giải quyết nó, nhưng vì nó là một đầu mối khác nên bài viết này không đề cập đến nó. Nếu bạn muốn biết, bạn có thể học hỏi từ Tiến sĩ Leslie Lambert (bạn bao nhiêu tuổi ): "Thời gian, Đồng hồ và Thứ tự Sự kiện trong Hệ thống Phân tán".

• Nếu bạn quan tâm đến việc tìm kiếm sự cân bằng giữa Finality và Liveness, bạn có thể nghiên cứu sự đồng thuận của Casper FFG, trong đó có một phần của Liveness và một phần của Finality. Đồng thời, bạn cũng sẽ tìm thấy sự khác biệt giữa PoS của Casper FFG và PoS của Tendermint.

• Cuối cùng, làm một bản tóm tắt của bài viết này, trong đó chủ yếu bao gồm các nội dung sau:

• Hai định lý: Nguyên lý bất khả FLP; Định lý bất khả CAP.

• Hai loại khả năng chịu lỗi: khả năng chịu lỗi thời gian chết; khả năng chịu lỗi Byzantine.

• Hai ý tưởng thiết kế thuật toán đồng thuận: Finality; Liveness.

Ba thuật toán đồng thuận: đồng thuận Paxos, PBFT và Satoshi Nakamoto.

Người giới thiệu:

Sẽ có những điểm không chính xác và không đầy đủ do đơn giản hóa và loại suy trong bài viết, mong bạn thông cảm, cảm ơn bạn đã sửa.

2.《WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS》，Alvaro Videla

3.《Time, Clocks and the Ordering of Events in a Distributed System》，Leslie Lamport

4.《The Byzantine Generals Problem》，LESLIE LAMPORT、ROBERT SHOSTAK、MARSHALL PEASE

5.《Paxos Made Simple》，Leslie Lamport

6.《Bitcoin: A Peer-to-Peer Electronic Cash System》，Satoshi Nakamoto