Giải thích cách Raft replicate log từ node leader qua các node follower.

Phần 2: Log Replication

Sau khi trở thành leader, node bắt đầu replicate log qua các node follower trong mạng thông qua request AppendEntries


1
2
3
4
5
6
Arguments
term: leader’s term
leaderID: follower dùng để redirect client
prevLogIndex: index của log entry nằm ngay phía trước những log entry mới được tạo
prevLogTerm: term của entry tại vị trí prevLogIndex
entries[]: log entry từ leader (và để rỗng cho giao thức Heartbeat)
leaderCommit: leader commited Index

7
8
Result
term: trả về term hiện tại, cho phép leader cập nhật lại term mới hơn
success: trả về true nếu follower chứa log entry khớp với prevLogIndex và prevLogTerm

9
10
11
12
13
Implementation
1.Trả về false nếu term < currentTerm ($5.1)
2.Trả về false nếu log không chứa entry tại vị trí prevLogIndex mà term khớp với prevLogTerm
3. Nếu tồn tại entry nhưng xung đột với các log entry mới (cùng index nhưng khác term): xóa hết toàn bộ log entry từ vị trí hiện tại và tất cả nằm sau đó ($5.3)
4. Nối tiếp toàn bộ các entry mới mà chưa tồn tại trong log.
5. Nếu leaderCommit > commitIndex, gán commitIndex=min(leaderCommit, index của entry cuối cùng được thêm vào)

Ta nhận thấy:

  • Dòng (1) (7) (9): Giao thức hoạt động theo từng vòng. Do vậy, những request đến trễ sau khi follower chấp nhận leader từ một node khác cao hơn sẽ không được đồng ý. Đồng thời, trả về term mới hơn để candidate có thể cập nhật term
  • Dòng (6): Follower sẽ dựa vào leaderCommit ID để quyết định có những log entry nào mới chưa được commit so với leader và update vào FSM
  • Dòng (3) (4) (10): để kiểm tra và giải quyết log bất đồng bộ giữa follower và leader

Sau đây là minh họa cụ thể cách leader đồng bộ log với node follower.

Minh họa: trạng thái khởi đầu của leader và follower

Khởi đầu là trạng thái giữa follower và leader:

  • màu xanh xương: là các log entry đã được đồng bộ giữa follower và leader. (mỗi cặp tương ứng sẽ giống nhau về index; data và term)
  • màu xanh lá cây: là các log entry ở leader (và chắc chắn đã được replicate qua quá bán các node trong mạng) nhưng chưa được replicate qua follower.
  • màu đỏ: là các log entry được replicate từ các leader trước đó, nhưng chưa được replicate qua quá bán, do vậy có thể được xóa đi.
  • màu trắng: log entry mới gửi từ phía người dùng sau khi node này trở thành leader (chưa được replicate qua bất cứ node nào khác)

(Minh họa 0)

Giải thích minh hoạ 0:

Như giải thích ở phần bầu chọn leader, một node muốn trở thành leader thì trước hết phải thoả mãn điều kiện có các log entry “up-to-date”. Hay nói cách khác, log trên leader phải là mới nhất và hoàn toàn có thể replicate qua tất cả các node khác.

Ta có thể replicate log theo phương pháp brute-force bằng cách gửi toàn bộ log entry của leader qua các follower. Follower sẽ xoá đi tất cả log hiện tại và thay vào đó sử dụng log từ leader. Tuy nhiên, nhược điểm phương pháp này là khối lượng dữ liệu phải gửi trên đường truyền rất lớn (có thể tới hàng triệu bản ghi), nên không phù hợp với bài toán thực tế.

Do vậy, thuật toán Raft phải tối ưu quá trình này, với một giả định là khả năng log bất đồng bộ giữa follower và leader là rất hiếm khi xảy ra (như trong hình vẽ là chỉ bất đồng bộ ở 2 log entry tại index số 4 và số 5).

(Minh họa 1)

Giải thích hình minh họa 1:

  • Leader: với Request AppendEntries đầu tiên sẽ chứa 2 log entry: log entry mới nhất và log entry ngay trước đó. Ở đây là trắng 6 và xanh lá 5.
  • Follower: Follower so sánh tại index 5 và thấy bất đồng bộ (xanh lá != đỏ), do vậy follower sẽ xóa đi log entry tại index là 5 và trả về false.

(Minh họa 2)

Giải thích hình minh họa 2:

  • Leader: nhận được kết quả là false trả về, leader biết rằng follower vẫn chưa cập nhật được log sang trạng thái mới nhất, và vẫn có thể còn một số log entry ở trạng thái bất đồng bộ. Do vậy, leader tiếp tục gửi lại request AppendEntries nhưng tăng kích thước lên 1. Như ở đây là xanh lá 4-5 và trắng 6.
  • Follower: Follower so sánh tại index 4 và thấy bất đồng bộ (xanh lá != đỏ), do vậy follower sẽ xóa đi log entry tại index là 5 và trả về false.

(Minh họa 3)

Giải thích minh họa 3:

  • Leader: tương tự, leader mở rộng tiếp đoạn log cần được gửi: xanh dương 3 ; xanh lá 4-5; trắng 6.
  • Follower: lúc này, leader so sánh tại vị trí index = 3 thấy 2 log entry giống nhau. Theo định lí Log Matching Property, chắc chắn tất cả các log entry từ đầu đến index thứ 3 là đồng nhất, không cần phải đồng bộ nữa.
  • Follower sau đó đồng bộ tất cả các log entry đang bị thiếu: xanh lá 4-5 và trắng 6 vào local và trả về true.

(Minh họa 4)

Giải thích minh họa 4:

Sau khi leader và follower đã đồng bộ về log, người dùng tiếp tục gửi một request mới số 7 vào leader.

  • Leader: leader ghi nhận follower đã cập nhật hoàn toàn tới vị trí 6. Do vậy, lần này chỉ cần gửi log entry ở vị trí 7 và log entry trước đó là 6.
  • Follower: Follower so sánh log entry tại vị trí thứ 6 và thấy đã khớp. Tương tự như minh họa 3, follower sẽ ghi vào local log màu cam thứ 7 và trả về true.

Trong phần tiếp theo, chúng ta sẽ đi qua các vấn đề khác về Raft như một số trường hợp đặc biệt khi thực thi; tương tác giữa client và raft server …