Raft — đồng thuận leader & log replication

TL;DR: Raft giúp nhiều node thống nhất một chuỗi lệnh (replicated log) dù có node chết hay mạng đứt. Ba phần tách biệt: bầu leader (một node làm trưởng nhóm, mỗi nhiệm kỳ gọi là term chỉ có một) bằng timeout ngẫu nhiên, nhân bản log (leader chép lệnh sang các node, quá nửa ghi xong thì chốt, gọi là commit), và safety (chỉ bỏ phiếu cho node có log mới ít nhất bằng mình, chỉ commit entry của term hiện tại bằng cách đếm replica). Đọc từ leader cũng cần xác nhận quyền, không thì có thể trả dữ liệu cũ. Raft là nền của etcd, Consul, TiKV, CockroachDB.

Bài này dạy Raft ở cấp thuật toán: pseudocode, trace, bất biến. Phần hệ thống (failover, khoá phân tán) nằm ở Consensus qua Raft trong Data phân tán.

Hình dung: nhóm họp bầu trưởng nhóm

Năm người cùng giữ một cuốn sổ chung, ai cũng phải ghi đúng nội dung theo đúng thứ tự.

• Mỗi nhiệm kỳ có đúng một trưởng nhóm; chỉ người đó đọc lệnh cho cả nhóm ghi.
• Khi quá nửa nhóm (ít nhất 3 trên 5) đã ghi, trưởng nhóm tuyên bố "chốt" và không ai rút lại được.
• Trưởng nhóm im lặng quá lâu thì ai sốt ruột trước đứng lên xin bầu nhiệm kỳ mới.
• Tin mang số nhiệm kỳ cũ là tin của trưởng nhóm hết hạn, nên bị bỏ qua.

Đối chiếu sang Raft: nhiệm kỳ là term, cuộc bầu là leader election, "quá nửa" là quorum, cuốn sổ là replicated log, "chốt" là commit. Một luật phép hình dung chưa nói: mỗi người chỉ bỏ phiếu cho ứng viên có sổ đầy đủ ít nhất bằng sổ của mình (mục 3).

1. Bài toán consensus: vì sao cần

Cùng một database chạy trên 5 node thì mọi lệnh ghi phải áp theo cùng thứ tự ở cả 5, không thì node 1 áp A rồi B còn node 2 áp B rồi A, trạng thái lệch nhau. Consensus là cơ chế thống nhất chuỗi lệnh đó. Yêu cầu: safety (không bao giờ trả kết quả sai) và liveness (cuối cùng vẫn tiến được khi đa số node sống).