Tối ưu hóa thuật toán Raft: Đạt đồng thuận với số lượng nút thiểu

Raft là một giao thức đồng thuận (consensus protocol) phổ biến được sử dụng để quản lý nhật ký sao chép (replicated log) trên một cụm các nút (nodes). Mục tiêu chính của Raft là duy trì tính nhất quán của dữ liệu, chịu đựng sự cố của các nút và đảm bảo có một lãnh đạo (leader) duy nhất điều phối mọi thay đổi. Trong trạng thái hoạt động bình thường, Raft yêu cầu sự đồng thuận của đa số các nút (ví dụ: 3 trên 5 nút) trước khi cam kết (commit) một thay đổi. Điều này đảm bảo an toàn nhưng cũng đồng nghĩa với việc hệ thống cần nhiều tài nguyên hoạt động.

Tuy nhiên, một bài viết kỹ thuật mới đây đã đề xuất một cách tiếp cận thú vị: liệu chúng ta có thể đạt được đồng thuận với một số lượng nút ít hơn đa số không? Câu trả lời nằm trong việc áp dụng các cấu trúc toán học đẹp mắt từ lý thuyết tổ hợp, cụ thể là các mặt phẳng chiếu hữu hạn (finite projective planes).

Ví dụ về trò chơi Spot It!

Cảm hứng cho giải pháp này đến từ một trò chơi bài nổi tiếng tên là Spot It! (hay Dobble). Trong trò chơi này, bất kỳ hai lá bài nào cũng chia sẻ chính xác một hình ảnh chung. Thuộc tính toán học này được gọi là mặt phẳng chiếu hữu hạn. Nếu chúng ta coi mỗi lá bài là một nhóm các nút (gọi là "bloc") và mỗi hình ảnh là một nút, thì bất kỳ hai nhóm nào cũng sẽ có ít nhất một nút giao nhau.

Trong thuật toán Raft truyền thống, tính đúng đắn (safety) được đảm bảo bởi nguyên tắc: bất kỳ hai đa số (majorities) phải có giao điểm. Điều này đảm bảo rằng không có hai lãnh đạo nào được bầu lên cùng một lúc với các lịch sử mâu thuẫn. Bằng cách thay thế khái niệm "đa số" bằng các "bloc" được thiết kế toán học, chúng ta có thể giảm số lượng nút cần thiết để hình thành một quorum hợp lệ.

Ví dụ đơn giản nhất là mặt phẳng Fano với 7 nút. Thay vì cần 4 nút (đa số) để đạt đồng thuận, chúng ta chỉ cần 3 nút, miễn là chúng tạo thành một "bloc" hợp lệ.

Sơ đồ mặt phẳng Fano

Hãy xem xét các kịch bản với hệ thống 7 nút sử dụng cấu trúc Fano:

1. Hoạt động với thiểu số: Nếu 4 nút gặp sự cố và chỉ còn 3 nút hoạt động, Raft truyền thống sẽ bị tắc nghẽn. Tuy nhiên, nếu 3 nút còn lại này恰好 tạo thành một "bloc" hợp lệ, hệ thống sửa đổi vẫn có thể tiếp tục hoạt động và cam kết các thay đổi.
2. Bầu cử lãnh đạo: Khi một lãnh đạo gặp sự cố, một nút mới có thể được bầu lên nếu nó nhận được phiếu bầu từ một "bloc" hợp lệ. Do tính chất giao nhau của các bloc, lãnh đạo mới được đảm bảo sẽ có thông tin về các cam kết trước đó.
3. Đánh đổi hiệu suất: Mặc dù có thể hoạt động với ít nút hơn, phương pháp này không đảm bảo tiến bộ (progress) trong mọi trường hợp. Có những tình huống đa số các nút vẫn hoạt động nhưng không tạo thành bất kỳ "bloc" hoàn chỉnh nào, khiến hệ thống bị đình trệ.

Đây là một đánh đổi quan trọng. Phương pháp này đánh đổi khả năng hoạt động liên tục khi có đa số nút sống để đổi lấy khả năng hoạt động với số nút cực ít trong các trường hợp cụ thể. Phân tích xác suất cho thấy với 7 nút, cơ hội hoạt động thành công với 3 nút ngẫu nhiên là khoảng 20%, nhưng tăng lên 80% với 4 nút.

Trong thực tế, các lỗi hệ thống thường không ngẫu nhiên mà có tính tương quan (ví dụ: cả một rack máy chủ hoặc một vùng sẵn sàng (availability zone) cùng bị lỗi). Do đó, thay vì dựa vào toán học thuần túy, các kỹ sư có thể thiết kế các "bloc" dựa trên topology mạng thực tế để tối ưu hóa khả năng chịu lỗi tốt hơn.

Việc áp dụng các cấu trúc toán học vào thiết kế hệ thống phân tán mở ra những hướng đi mới thú vị, cho phép chúng ta tái định nghĩa lại sự cân bằng giữa hiệu suất, độ tin cậy và chi phí trong kỷ nguyên điện toán đám mây.