Thuật toán Raft là gì: Giải pháp đồng thuận dễ hiểu cho các hệ thống phi tập trung
Thuật toán Raft là gì? Đây là một giao thức đồng thuận được thiết kế để thay thế Paxos, nổi bật bằng cách tách biệt logic rõ ràng, dễ hiểu hơn nhưng vẫn đảm bảo tính an toàn và khả năng chịu lỗi. Raft cho phép một nhóm máy chủ duy trì một bản sao chung của trạng thái (state machine) và đồng ý về thứ tự các thao tác khi một số máy chủ bị lỗi.
Thuật toán được đặt tên dựa trên từ viết tắt của các từ Reliable, Replicated, Redundant, And Fault-Tolerant. Raft hiện đã được triển khai trong nhiều dự án biết đến như etcd, Consul và nhiều hệ thống lưu trữ phân tán khác.
Cách hoạt động của Raft
Raft chia thời gian thành các kỳ hạn (terms). Mỗi kỳ hạn bắt đầu với một cuộc bầu chọn lãnh đạo, trong đó các máy chủ tranh cử vai trò lãnh đạo. Khi một lãnh đạo được chọn, nó chịu trách nhiệm nhận yêu cầu từ khách hàng, sao chép nhật ký (log) đến các máy chủ khác và áp dụng các thay đổi vào trạng thái chung.
1. Bầu chọn lãnh đạo
- Mỗi máy chủ có một thời gian chờ ngẫu nhiên (election timeout) thường từ 150 tới 300 mili giây.
- Nếu không thấy tin nhắn từ lãnh đạo trong khoảng thời gian chờ, máy chủ trở thành ứng viên (candidate), tăng term và bỏ phiếu cho chính mình, sau đó gửi tin nhắn
RequestVoteđến tất cả các máy chủ khác. - Một máy chủ sẽ bỏ phiếu cho ứng viên đầu tiên mà nó thấy trong kỳ hạn hiện tại, miễn là ứng viên có term không nhỏ hơn term của mình và nhật ký của ứng viên đầy đủ và cập nhật.
- Nếu ứng viên nhận được hơn một nửa số phiếu, nó trở thành lãnh đạo mới trong kỳ hạn này.
- Ngược lại, nếu không đủ phiếu hoặc có máy chủ có term cao hơn, ứng viên hủy candidacy và trở thành người theo dõi (follower), chờ lãnh đạo mới xuất hiện.
2. Nhân bản log (log replication)
Khi lãnh đạo đã được chọn, nó thực hiện hai công việc chính:
- Nhận yêu cầu từ khách hàng và mỗi yêu cầu được thêm vào nhật ký của lãnh đạo như một mục log mới (entry).
- Gửi tin nhắn
AppendEntriesđến tất cả các follower để sao chép mục log này. Mỗi tin nhắn kèm theo chỉ số và thuật ngữ của mục log trước đó để follower có thể kiểm tra tính tương thích.
Sau khi hơn nửa số máy chủ phản hồi thành công, lãnh đạo xem mục log đã được ghi và áp dụng nó vào trạng thái của mình. Quy trình này cũng đồng thời ghi tất cả các mục log trước đó.
Nếu follower phát hiện nhật ký của mình không khớp (ví dụ do lỗi mạng), nó từ chối tin nhắn và lãnh đạo sẽ ghi đè các mục log xung đột từ vị trí không khớp bằng các mục log mới của mình.
An toàn và tính chính xác
Raft được chứng minh toán học là an toàn dưới mô hình lỗi máy chủ dừng (crash-stop), tức là giả định máy chủ không thể hành động bất thường khi lỗi mà không thể gửi tin nhắn sai (Byzantine). Các tính chất then chốt bao gồm:
- An toàn انتخاب lãnh đạo: mỗi kỳ hạn chỉ có tối đa một lãnh đạo được chọn.
- Thành viên log: nếu hai mục log có cùng chỉ số và cùng thuật ngữ, thì tất cả các mục log trước đó cũng giống nhau.
- Tính chất chỉ-đọc của lãnh đạo: lãnh đạo trong một kỳ hạn không bao giờ ghi đè hoặc xóa các mục log đã cam kết trong nhật ký của mình.
- An toàn thành viên log: nếu một mục log được áp dụng vào trạng thái của một máy chủ, thì cùng mục log sẽ cũng tồn tại ở cùng vị trí trong nhật ký của mọi máy chủ khác và sẽ cuối cùng được áp dụng vào trạng thái của chúng.
So sánh Raft với Paxos
| Tiêu chí | Paxos | Raft | |
|---|---|---|---|
| Khó hiểu | Cao – logic phức tạp | Thấp – được thiết kế để dạy và học dễ | |
| Bước quyết định | Hai giai đoạn (prepare/accept) | Một giai đoạn (AppendEntries) – đơn giản hơn | |
| Thời gian chờ ngẫu nhiên | Có (để tránh livelock) | Có (election timeout – tránh bầu chọn bị chia đôi) | |
| Triển khai thực tế | Ít | Nhiều (etcd, Consul, TiKV) |
Mặc dù Paxos còn được dùng trong một số hệ thống cũ, Raft ngày càng được ưu chọn vì độ đơn giản và tài liệu hướng dẫn rõ ràng, giúp đội ngũ phát triển triển khai và bảo trì dễ dàng hơn.
Ứng dụng thực tế
Raft được triển khai trong nhiều hệ thống quan trọng:
- etcd: khoá giá trị phân tán dùng làm nền tảng cho Kubernetes để lưu trạng thái cluster.
- Consul: dịch vụ tìm kiếm và cấu hình phân tán, bao gồm health check và service discovery.
- Cơ sở dữ liệu phân tán: nhiều DB NewSQL như TiKV dùng Raft để sao chép dữ liệu giữa các node.
Ngoài ra, Raft còn được dùng trong các hệ thống điều khiển công nghiệp, mạng lưới cảm biến và bất kỳ nơi nào cần đảm bảo tính nhất quán trong môi trường có thể xảy ra lỗi phần cứng.
Nguồn tham khảo
- Trang chủ chính thức của dự án Raft và bài báo gốc In Search of an Understandable Consensus Algorithm.
- Raft (algorithm) trên Wikipedia.
- Mã nguồn tham chiếu etcd-io/raft.
Kết luận
Thuật toán Raft giải quyết bài toán đồng thuận bằng cách đặt emphasis vào khả năng hiểu và triển khai thực tế. Thay vì logic trộn lẫn như Paxos, Raft chia vấn đề thành các bước rõ ràng: bầu chọn lãnh đạo, nhân bản log và an toàn thành viên. Nhờ vậy, dù là nhà phát triển mới cũng có thể nắm vững và áp dụng vào dự án của mình trong thời gian ngắn. Với sự phổ biến ngày càng tăng trong hạ tầng điện toán đám mây và vi xử lý, Raft tiếp tục là lựa chọn hàng đầu cho những ai cần một giải pháp đồng thuận đáng tin cậy, dễ hiểu và có thể mở rộng.
