Giải thuật phân tán: Giải thích thuật toán đồng thuận Raft một cách dễ hiểu qua ví dụ trực quan

Bài toán đồng thuận (Consensus) trong hệ thống phân tán#

Làm thế nào để 5 máy chủ độc lập (nằm ở các trung tâm dữ liệu khác nhau) cùng thống nhất được một trạng thái dữ liệu duy nhất, ngay cả khi 2 trong số 5 máy bị sập nguồn hoặc đường truyền cáp quang biển bị đứt?

Trước đây, thuật toán Paxos được coi là tiêu chuẩn nhưng quá khó hiểu và cực kỳ phức tạp để hiện thực hóa bằng code.

Vào năm 2014, Raft Consensus Algorithm ra đời với mục tiêu tối thượng: Dễ hiểu và dễ áp dụng thực tế. Ngày nay, Raft đứng sau các hệ thống phân tán khổng lồ như etcd (trái tim của Kubernetes), Kafka KRaft, TiDB, và CockroachDB.

3 Trạng thái của một Node trong Raft#

Mỗi máy chủ trong cụm Raft luôn ở 1 trong 3 trạng thái:

1. Follower (Người theo dõi): Lắng nghe lệnh từ Leader. Nếu quá thời gian (Election Timeout) không nghe thấy tín hiệu sống (Heartbeat) từ Leader $\rightarrow$ Tự ứng cử làm Candidate.
2. Candidate (Ứng cử viên): Gửi yêu cầu bầu cử (RequestVote) tới các node khác. Nếu giành được đa số phiếu ($\ge 3/5$ phiếu) $\rightarrow$ Đắc cử làm Leader.
3. Leader (Thủ lĩnh): Node duy nhất tiếp nhận mọi yêu cầu ghi từ client, ghi vào log của mình và phát tán (AppendEntries) tới các Follower.

Cơ chế Bầu cử Leader (Leader Election) bằng Randomized Timeout#

Điểm thông minh nhất của Raft là: Thời gian chờ bầu cử của mỗi node được chọn ngẫu nhiên từ 150ms đến 300ms. Nhờ có sự chênh lệch ngẫu nhiên này, hầu như luôn luôn có một node tỉnh dậy trước, gửi phiếu xin bầu cử và đắc cử ngay lập tức, loại bỏ nguy cơ bị chia rẽ phiếu bầu (Split Vote)!

Nhật ký phân tán (Log Replication)#

Khi Leader nhận được lệnh SET name = "TopDev":

1. Leader ghi tạm lệnh vào log cục bộ (chưa commit).
2. Leader gửi lệnh sang tất cả Follower qua RPC AppendEntries.
3. Khi đa số Follower (Quorum) xác nhận đã ghi log $\rightarrow$ Leader chính thức Commit lệnh và áp dụng vào máy trạng thái (State Machine).
4. Leader trả lời client: "Ghi thành công!".

Góc thảo luận#

Anh em đã từng tìm hiểu qua Raft hay Paxos chưa? Đã từng gặp hiện tượng Split-Brain (Não phân đôi) trong các cụm cluster chưa?

Xem thêm nội dung liên quan:

• Học Kiến trúc Phân tán Chuyên sâu
• Bộ đề trắc nghiệm Hệ thống Phân tán