Consensus qua Raft — leader election, log replication, commit

TL;DR: Consensus là bài toán để nhiều node thống nhất một giá trị/thứ tự duy nhất dù có lỗi — nền của failover an toàn, khoá phân tán, bầu leader, uniqueness. Raft chia ba mảnh: leader election (mỗi term, đa số phiếu bầu một leader), log replication (leader ghi log rồi sao chép sang follower), commit (một mục committed — chốt, không đảo — khi nhân bản tới đa số node). Hai đa số bất kỳ luôn giao nhau, nên Raft không bao giờ có hai leader hợp lệ cùng term hay hai giá trị committed mâu thuẫn — cách nó chặn split-brain. Đổi lại cần đa số node sống (2f+1 chịu f lỗi); mỗi commit tốn một vòng phối hợp — công cụ CP cho số ít quyết định thật sự cần đảm bảo tuyệt đối.

Một database có 1 primary + 2 replica. Primary chết. Hệ tự "thăng" một replica lên primary mới. Nhưng nếu primary cũ chưa chết hẳn — chỉ bị nghẽn mạng — nó tỉnh lại và tưởng mình vẫn là primary: giờ có hai primary cùng nhận ghi (split-brain), dữ liệu rẽ đôi và hỏng. Câu hỏi "ai là primary?" nghe đơn giản nhưng là một bài toán consensus, và làm sai nó là nguồn của những sự cố mất dữ liệu tồi tệ nhất.

Bài này định nghĩa consensus, rồi mổ Raft theo đúng ba mảnh của nó, và làm rõ vì sao "đa số" là chìa khoá chống split-brain. Đây là mảnh ghép cuối: consensus chính là cỗ máy tạo ra linearizability (bài 01) và một failover an toàn trong thế giới CAP (bài 03).

1. Analogy — bầu lớp trưởng cần quá bán

Một lớp bầu lớp trưởng. Quy tắc: ai được quá nửa số phiếu thì trúng. Vì sao "quá nửa" mà không phải "nhiều phiếu nhất"? Vì quá nửa đảm bảo không thể có hai người cùng trúng trong một lần bầu — hai nhóm "quá nửa" chắc chắn chồng lấn ít nhất một người, mà một người chỉ bỏ một phiếu, nên không thể tồn tại hai người mỗi người đều được quá nửa. Nếu lần bầu này bất phân thắng bại (không ai quá nửa), lớp bầu lại vòng mới — mỗi vòng là một "nhiệm kỳ" đánh số tăng dần.

Raft hoạt động y hệt: leader là "lớp trưởng", term là "nhiệm kỳ", đa số phiếu là quy tắc trúng cử chống hai-leader.

2. Định nghĩa chính xác — consensus và các tính chất

Consensus: một tập node cùng đề xuất các giá trị, và giao thức bảo đảm chúng cùng quyết một giá trị, thoả bốn tính chất:

• Agreement: không hai node quyết hai giá trị khác nhau.
• Integrity: mỗi node quyết tối đa một lần (không đảo).
• Validity: giá trị được quyết phải là một trong các giá trị được đề xuất (không bịa).
• Termination: mọi node không lỗi cuối cùng quyết được (không treo mãi) — với điều kiện đa số node còn sống.

Trong thực tế, consensus thường được đóng gói thành total order broadcast (hay replicated log): thay vì quyết một giá trị, các node quyết một thứ tự cho một chuỗi thao tác — ai cũng thấy cùng một log theo cùng thứ tự. Đó chính xác là thứ tạo ra linearizability: có một điểm sắp thứ tự duy nhất cho mọi thao tác.

3. Cơ chế Raft — ba mảnh

3.1 Leader election — bầu đúng một leader mỗi term

Thời gian chia thành các term (nhiệm kỳ) đánh số tăng. Mỗi follower có một election timeout ngẫu nhiên; nếu hết timeout mà không nghe heartbeat từ leader, nó tự tăng term, chuyển thành candidate và xin phiếu (RequestVote). Mỗi node chỉ bỏ một phiếu mỗi term. Ai gom được đa số phiếu → thành leader của term đó và bắt đầu phát heartbeat. Timeout ngẫu nhiên làm hai candidate hiếm khi khởi động cùng lúc → tránh split vote kéo dài.

follower het election timeout (khong nghe heartbeat):
  term <- term + 1
  chuyen thanh candidate, tu bo phieu cho minh
  gui RequestVote toi moi node
  if nhan duoc phieu tu DA SO node:
    tro thanh LEADER cua term nay
  else if nghe heartbeat term >= term cua minh:
    lui ve follower
  else:
    timeout -> bau lai vong moi (term+1)

3.2 Log replication — leader sao chép, follower theo

Chỉ leader nhận lệnh ghi từ client. Nó append lệnh vào log của mình rồi gửi AppendEntries sao chép sang các follower. Mỗi mục log mang term và index. Follower nhận thì ghi vào log của mình và báo lại. Leader theo dõi mỗi follower đã sao chép tới đâu (matchIndex). Nếu log follower lệch (do leader cũ crash để lại mục thừa), leader ép follower khớp với log của mình — leader là nguồn sự thật của thứ tự.

3.3 Commit — chốt khi đạt đa số

Một mục log chỉ chuyển sang committed (đã chốt, an toàn để áp dụng vào state machine và trả lời client) khi leader thấy nó đã được nhân bản tới đa số node. Trước ngưỡng đa số, mục vẫn "treo" và có thể bị ghi đè nếu leader đổi. Sau khi committed, nó không bao giờ bị đảo — vì mọi leader tương lai đều phải được đa số bầu, mà đa số đó chắc chắn chứa ít nhất một node đã có mục committed này (xem mục 4), nên leader mới buộc phải giữ nó.

Có một ràng buộc tinh vi (Raft §5.4.2, Figure 8): leader chỉ trực tiếp commit một mục log của term hiện tại khi mục đó đạt đa số. Một mục của term cũ hơn (do leader trước để lại, chưa kịp commit) không được coi là committed chỉ vì bản thân nó đã nhân bản tới đa số — nó chỉ committed gián tiếp, khi một mục của term hiện tại nằm sau nó cũng đạt đa số. Bỏ qua caveat này (commit thẳng một mục term cũ chỉ vì đủ đa số) là kẽ hở kinh điển dẫn tới mất dữ liệu đã committed khi đổi leader.

sequenceDiagram
  participant C as Client
  participant L as Leader
  participant F1 as Follower 1
  participant F2 as Follower 2
  C->>L: ghi x=5
  L->>L: append (term,idx) vao log
  L->>F1: AppendEntries x=5
  L->>F2: AppendEntries x=5
  F1-->>L: OK
  Note over L: da dat DA SO (L + F1) -> COMMIT
  L-->>C: ghi thanh cong
  L->>F2: (F2 bat kip sau)

4. Vì sao "đa số" chặn được split-brain?

Đây là trái tim của Raft, và câu trả lời gói trong một tính chất tập hợp: hai tập con đa số (majority) bất kỳ của cùng một cụm luôn giao nhau ít nhất một phần tử. Với cụm n node, một majority là ⌊n/2⌋ + 1 node; hai majority cộng lại vượt n, nên theo nguyên lý chuồng bồ câu chúng phải chồng lấn.

Hai hệ quả chống split-brain rơi ra từ đây:

• Không hai leader hợp lệ cùng term: thành leader cần đa số phiếu; mỗi node chỉ một phiếu/term. Nếu có hai leader cùng term, cần hai đa số phiếu rời nhau — bất khả vì hai đa số phải giao nhau, mà node giao đó đã bỏ hết một phiếu cho một bên.
• Không hai giá trị committed mâu thuẫn: committed cần đa số bản sao. Một leader mới phải được đa số bầu; đa số đó giao với đa số đã lưu mục committed cũ → leader mới chắc chắn thấy mục đó và phải giữ. Vì vậy lịch sử committed chỉ nối dài, không rẽ nhánh.

flowchart LR
  A["Cum 5 node<br/>majority = 3"] --> B["Partition: nhom X (3)<br/>| nhom Y (2)"]
  B --> X["Nhom X: du 3 -> bau leader,<br/>commit duoc"]
  B --> Y["Nhom Y: chi 2 -> KHONG du da so<br/>-> khong co leader, khong commit"]
  X --> S["Chi MOT phia tien -> khong split-brain"]
  Y --> S

Lần theo cơ chế: majority của cụm 5 là 3. Nhóm X (3 node) vừa đủ một majority → giữ/bầu được leader và commit được (mỗi mục đạt 3 bản sao trong nội bộ X). Nhóm Y (2 node) không thể gom nổi 3 → nếu leader cũ nằm ở Y, nó mất quyền commit (không đạt đa số) và các follower ở Y hết timeout sẽ đòi bầu nhưng cũng không đủ phiếu → không có leader hợp lệ, không commit gì. Client bên Y bị treo/lỗi (đây là mặt CP của Raft — hy sinh availability phía thiểu số). Khi partition lành, bên Y thấy term của X cao hơn (X đã tiến), nên các node Y lùi về follower và Raft ép log của chúng khớp với leader X: mọi mục "treo" mà Y lỡ nhận nhưng chưa committed bị cắt bỏ và ghi đè bằng log đã committed của X. Kết quả: đúng một dòng lịch sử committed sống sót — không split-brain, không hai sự thật. Đây chính là lý do một mục chỉ an toàn khi đã đạt đa số: dưới ngưỡng đó nó luôn có thể bị một leader hợp lệ hơn ghi đè.

5. Pitfall — tưởng election là đủ, hoặc consensus chịu được mọi lỗi

❌ "Bau duoc leader la xong (co leader = an toan)"
   -> Election chi la 1/3. Chua co log replication + commit theo DA SO thi
   mot ghi "co leader nhan" van co the mat khi leader do crash truoc khi
   nhan ban du da so. An toan = da COMMIT (dat da so), khong phai "leader da nhan".

❌ "Consensus chiu duoc bao nhieu node chet cung duoc"
   -> SAI: can DA SO song. Cum 2f+1 chi chiu f loi. Cum 5 chet 3 -> phan con
   lai (2) khong dat da so -> KHONG bau/commit duoc -> he dung (khong sai,
   nhung khong tien). Mat da so la mat kha nang tien, khong phai mat an toan.

6. 📚 Đào sâu — nguồn gốc & tài liệu

7. Liên hệ các bài khác

• Bài 01 — Linearizability: consensus (total order broadcast) chính là cỗ máy hiện thực linearizability — một điểm sắp thứ tự duy nhất cho mọi thao tác.
• Bài 03 — CAP: Raft là hệ CP điển hình — hy sinh availability ở phía thiểu số (không đủ đa số) để không bao giờ split-brain.
• Bài 05 — Case study: etcd/ZooKeeper là consensus service đóng gói Raft/ZAB thành khoá, config, bầu leader dùng được ngay.
• Module 5 — Fencing token: fencing token chống "leader cũ tỉnh lại" — bổ trợ cho an toàn mà consensus cung cấp khi failover.

8. Tóm tắt

• Consensus = nhiều node thống nhất một giá trị/thứ tự duy nhất dù có lỗi (agreement, integrity, validity, termination); thường đóng gói thành total order broadcast (replicated log).
• Raft = ba mảnh: leader election (theo term, cần đa số phiếu), log replication (leader sao chép sang follower), commit (khi đạt majority quorum).
• Committed = đã nhân bản tới đa số → chốt, không thể đảo; đây là điểm sắp thứ tự tạo ra linearizability.
• Đa số luôn giao nhau → không hai leader hợp lệ cùng term, không hai giá trị committed mâu thuẫn → chống split-brain.
• Giá: cần đa số node sống (2f+1 chịu f lỗi); mất đa số → hệ dừng tiến (an toàn nhưng không khả dụng — mặt CP).
• Pitfall: "có leader là an toàn" (chưa — phải committed); "chịu được mọi lỗi" (không — cần đa số).

9. Tự kiểm tra

Bài tiếp theo: Case study — etcd/ZooKeeper vs Cassandra