Paxos và Raft

Paxos và Raft là hai giao thức đồng thuận thực tế có ảnh hưởng nhất, cung cấp sự đồng thuận chịu lỗi sự cố trên một nhật ký sao chép, làm nền tảng cho các hệ thống phối hợp trong thế giới thực.

Definition

Paxos và Raft là các giao thức dựa trên số lượng tối thiểu cho phép một tập hợp các bản sao đồng ý về một chuỗi lệnh có thứ tự (một nhật ký sao chép) bất chấp các lỗi sự cố, đảm bảo rằng các mục đã cam kết không bao giờ bị mất hoặc sắp xếp lại miễn là đa số các bản sao vẫn khả dụng.

Scope

Chủ đề này bao gồm họ Paxos—Paxos một quyết định (single-decree Paxos), Multi-Paxos và các cải tiến kỹ thuật của nó—và giao thức Raft, tổ chức lại các đảm bảo tương tự xung quanh một người lãnh đạo rõ ràng, sao chép nhật ký và thay đổi thành viên để dễ hiểu hơn. Nó bao gồm vai trò của người đề xuất/người chấp nhận và người lãnh đạo/người theo dõi, giao cắt số lượng tối thiểu (quorum intersection), bầu chọn và nhiệm kỳ của người lãnh đạo, khớp nhật ký (log matching), và các vấn đề thực tế về ảnh chụp nhanh (snapshots) và cấu hình lại (reconfiguration).

Core questions

• Giao cắt số lượng tối thiểu (quorum intersection) và đánh số đề xuất (proposal numbering) giữ cho Paxos an toàn qua các vòng và thay đổi người lãnh đạo như thế nào?
• Raft phân tách sự đồng thuận thành bầu chọn người lãnh đạo, sao chép nhật ký và an toàn như thế nào?
• Những thách thức kỹ thuật nào phát sinh khi biến các giao thức này thành hệ thống sản xuất?

Key theories

Paxos một quyết định và Multi-Paxos

Paxos đạt được sự đồng thuận về một giá trị thông qua các giai đoạn chuẩn bị và chấp nhận được điều chỉnh bởi các số đề xuất đơn điệu và số lượng tối thiểu đa số; Multi-Paxos phân bổ giai đoạn chuẩn bị trên một luồng quyết định do một người lãnh đạo ổn định dẫn dắt để xây dựng một nhật ký sao chép.

Sự phân tách của Raft

Raft đạt được sự an toàn tương tự như Paxos bằng cách bầu một người lãnh đạo duy nhất cho mỗi nhiệm kỳ, để người lãnh đạo thêm các mục mà người theo dõi sao chép, và thực thi một thuộc tính khớp nhật ký, cố tình đánh đổi tính tối giản để dễ hiểu và dễ triển khai.

Từ đặc tả đến hệ thống đang chạy

Việc triển khai Paxos trong thực tế đòi hỏi phải xử lý các lỗi đĩa, thuê người lãnh đạo (leader leases), nén nhật ký (log compaction) và cấu hình lại, những chi tiết thường bị bỏ qua trong thuật toán gốc nhưng cần thiết cho tính đúng đắn và hiệu suất.

Clinical relevance

Paxos và Raft chạy bên trong các dịch vụ phối hợp, cơ sở dữ liệu phân tán và kho lưu trữ cấu hình được sử dụng rộng rãi; việc hiểu chúng là điều cần thiết để xây dựng hoặc vận hành bất kỳ hệ thống nào phải giữ cho các bản sao nhất quán mạnh mẽ thông qua các lỗi.

History

Lamport đã mô tả Paxos trong bài báo 'nghị viện bán thời gian' năm 1998 của mình và làm rõ nó trong 'Paxos made simple' (2001); Chandra và các đồng nghiệp đã báo cáo thực tế về việc triển khai nó ở quy mô lớn vào năm 2007; và Ongaro cùng Ousterhout đã giới thiệu Raft vào năm 2014 để làm cho các đảm bảo tương đương dễ dạy và triển khai hơn nhiều.

Debates

Tính dễ hiểu so với tính tối giản trong các giao thức đồng thuận

Raft được thiết kế rõ ràng để dễ hiểu hơn Paxos, gây ra tranh luận về việc liệu cấu trúc bổ sung của nó (một người lãnh đạo mạnh mẽ) có hy sinh tính linh hoạt hay không; những người ủng hộ cho rằng tính dễ hiểu làm giảm lỗi triển khai, trong khi những người khác lưu ý rằng các biến thể Paxos có thể tổng quát hơn.

Key figures

• Leslie Lamport
• Diego Ongaro
• John Ousterhout
• Tushar Chandra

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

Paxos và Raft có phải là các thuật toán khác biệt cơ bản không?

Không—chúng giải quyết cùng một vấn đề với cùng một lõi số lượng tối thiểu đa số và các đảm bảo an toàn tương đương. Raft chủ yếu tổ chức lại Paxos xung quanh một người lãnh đạo mạnh mẽ và một nhật ký rõ ràng để làm cho giao thức dễ hiểu và dễ triển khai hơn.