Tôi đã triển khai thuật toán đồng thuận Raft (đại diện tiêu biểu cho các thuật toán phân tán) bằng Python. Bản triển khai này khá tệ! Nhưng cũng (phần nào) đúng.
Dưới đây là vài ghi chép tôi muốn chia sẻ với những ai muốn thử sức với một thử thách tương tự.
Nhìn lại, đây là những tài liệu hữu ích nhất để tìm hiểu về Raft và triển khai nó cho đúng.
- Bài báo về Raft (đọc đến mục 5 và thường xuyên đối chiếu hình 2)
- Hướng dẫn về Raft dành cho sinh viên
- một trong những bản triển khai Raft được sử dụng rộng rãi nhất
- clone kho mã nguồn, đọc lướt
raft.go, rồi trao đổi qua lại với một LLM để hiểu mã nguồn và các quyết định thiết kế
- clone kho mã nguồn, đọc lướt
- Loạt bài trên blog của Eli Bendersky
Tôi khuyên bạn nên dành khoảng một giờ để đọc bài báo trước, rồi viết mã khung cho một máy chủ UDP hoặc TCP đọc các byte nhận được và thêm chúng vào một mảng. Sau đó, tôi làm theo bản triển khai của Eli, thêm các tính năng vào bản triển khai Raft của mình theo cùng thứ tự.
Sau khi có được một cơ chế bầu chọn có vẻ hoạt động, tôi bắt đầu tìm lỗi và những chỗ mình hiểu sai về thuật toán. Tôi đối chiếu qua lại giữa hướng dẫn dành cho sinh viên, Hình 2 trong bài báo về Raft và bản triển khai của mình, suy xét kỹ những điểm bản triển khai giống (hoặc khác) với mô tả trong tài liệu. Tôi cũng dùng LLM rất nhiều để rà soát mã này, đưa nội dung từ các tài liệu trên vào ngữ cảnh.
Lặp lại quy trình trên cho việc sao chép nhật ký, lưu trữ bền vững, v.v.
về phần triển khai
Tôi đưa ra một số lựa chọn thiết kế để đơn giản hóa bản triển khai của mình. Không theo thứ tự cụ thể nào:
- mỗi nút chạy và xử lý thông điệp trên một luồng duy nhất
- dùng một "đồng hồ logic" để theo dõi "thời gian" cục bộ trong hệ thống (ví dụ: gọi
tick()và tăng một bộ đếm cục bộ tại mỗi nút thay vì dùng thời gian hệ thống) - làm bản triển khai trở nên "lộn xộn" bằng cách đặt mọi thứ trong một tệp, chẳng hạn như phân tích cú pháp dữ liệu mạng, lưu trữ/lưu trữ bền vững, thuật toán Raft cốt lõi và các tiện ích/lệnh để điều khiển chính nút đó
Lựa chọn 2 có vẻ hợp lý và đúng đắn (bản triển khai của etcd cũng dùng đồng hồ logic). Có thể nói lựa chọn 3 tốt hơn cho việc học/giảng dạy. Đặt mọi thứ trong một tệp khá tiện vì bạn có thể xem tất cả cùng lúc, đồng thời có một bản triển khai dễ tháo tung ra để xem những cách trừu tượng hóa nào phù hợp nhất với thuật toán.
Theo tôi, lựa chọn 1 có phần khó chấp nhận. Đúng là nó giúp việc triển khai đơn giản hơn nhiều (bạn bớt phải lo về deadlock và việc cập nhật trạng thái nội bộ của nút một cách nguyên tử), nhưng kết quả thu được cũng không hoàn toàn là Raft. Với bản triển khai đầu tiên, điều này có vẻ chấp nhận được. Bản thân thuật toán đã đủ phức tạp, và tôi nghĩ bạn sẽ muốn dành thời gian gỡ các lỗi logic trong thuật toán Raft cốt lõi hơn là loay hoay với mutex.
Tôi cho rằng triển khai Raft theo cách này là một dự án mất ~30 giờ. Việc đọc bài báo về Raft lần đầu và xem các tài liệu liên quan sẽ mất vài giờ. Tôi viết phần lớn mã trong ~3 ngày vào kỳ nghỉ lễ, mỗi ngày mày mò viết mã khoảng 6-8 giờ. Tôi vẫn còn vài chỗ cần trau chuốt và cải thiện (ví dụ: sửa một số lỗi khó nhận ra) trong bản triển khai hiện tại, có thể cần thêm nửa ngày làm việc nữa.
Nhìn chung, như vậy cũng không tệ để hiểu được một trong những thuật toán cốt lõi làm nền tảng cho rất nhiều hệ thống hạ tầng.