Giao diện
🤝 DISTRIBUTED CONSENSUS
Sự Đồng thuận của Bầy đàn: Khi Máy tính Cần "Bầu cử"
Mục tiêu Học tập
Sau khi hoàn thành module này, bạn sẽ có khả năng:
- Hiểu tại sao sự đồng thuận là bài toán cốt lõi của distributed systems
- Giải thích Two Generals' Problem và ý nghĩa của nó
- Mô tả cơ chế Leader Election và Log Replication trong Raft
- Xử lý Split-brain Scenario với Quorum
1. The Problem: Tại sao Đồng ý một Con số lại Khó?
NOTE
🎓 Giáo sư Tom: Hãy tưởng tượng 3 database servers cần đồng ý rằng "Account Balance = 1000$". Nghe đơn giản? Nhưng nếu network lag, nếu một server crash giữa chừng, nếu message bị mất... đây là bài toán đã làm đau đầu các nhà khoa học máy tính suốt 40 năm.
1.1 Two Generals' Problem (Bài toán Hai Vị Tướng)
┌─────────────────────────────────────────────────────────────────────────┐
│ TWO GENERALS' PROBLEM │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 🏰 ENEMY CITY 🏰 │
│ ════════════════ │
│ │
│ ⚔️ Army A ⚔️ Army B │
│ (General Alice) (General Bob) │
│ │ │ │
│ │ │ │
│ └──────────── VALLEY ─────────────────┘ │
│ (Unreliable) │
│ │
│ Mục tiêu: CẢ HAI đồng loạt tấn công lúc 6:00 AM │
│ Vấn đề: Messenger qua valley có thể bị bắt/giết bất cứ lúc nào │
│ │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Alice ─────► "Attack at 6 AM" ──────► Bob │
│ ❓ │
│ (Delivered?) │
│ │
│ Alice ◄───── "ACK, I'll attack" ◄───── Bob │
│ ❓ │
│ (Delivered?) │
│ │
│ Alice ─────► "ACK of ACK" ──────────► Bob │
│ ❓ │
│ (Infinite loop of ACKs!) │
│ │
│ ⚠️ THEOREM: Không có protocol nào đảm bảo 100% đồng thuận │
│ trong mạng không đáng tin cậy với khả năng mất message. │
│ │
└─────────────────────────────────────────────────────────────────────────┘Kết luận quan trọng:
IMPORTANT
Định lý Two Generals: Trong một mạng không đáng tin cậy (messages có thể mất), không tồn tại protocol nào đảm bảo đồng thuận 100%. TCP "giải quyết" điều này bằng cách chấp nhận timeout và retry - không phải đảm bảo tuyệt đối.
1.2 FLP Impossibility Theorem
NOTE
🎓 Giáo sư Tom: Năm 1985, Fischer, Lynch và Paterson chứng minh một định lý chấn động: Trong hệ thống bất đồng bộ (async) với khả năng chỉ MỘT node fail, không có thuật toán đồng thuận nào vừa đảm bảo Safety (không có kết quả sai), vừa đảm bảo Liveness (luôn có kết quả), vừa đảm bảo Fault Tolerance.
┌─────────────────────────────────────────────────────────────────────────┐
│ FLP IMPOSSIBILITY │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Bạn chỉ có thể chọn 2 trong 3: │
│ │
│ ┌─────────────────┐ │
│ │ SAFETY │ │
│ │ (No wrong │ │
│ │ answers) │ │
│ └────────┬────────┘ │
│ │ │
│ ┌────────────┴────────────┐ │
│ │ │ │
│ ▼ ▼ │
│ ┌─────────┐ ┌─────────────┐ │
│ │LIVENESS │ │ FAULT │ │
│ │(Always │◄───────────►│ TOLERANCE │ │
│ │ decide) │ │(Handle fail)│ │
│ └─────────┘ └─────────────┘ │
│ │
│ Real-world solution: Chấp nhận "eventually" thay vì "always" │
│ │
└─────────────────────────────────────────────────────────────────────────┘2. Paxos: Nền tảng Lịch sử
TIP
🔧 Kỹ sư Raizo: Paxos là thuật toán được Leslie Lamport phát minh năm 1989. Dù là nền tảng lý thuyết quan trọng, nó cực kỳ khó hiểu và khó implement đúng. Google Chubby, Apache ZooKeeper đều dựa trên Paxos nhưng với vô số modifications. Tôi sẽ giới thiệu ngắn gọn - đủ để bạn hiểu tại sao Raft ra đời.
2.1 Paxos Roles
┌─────────────────────────────────────────────────────────────────────────┐
│ PAXOS ROLES │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ PROPOSER │ │ ACCEPTOR │ │ LEARNER │ │
│ │─────────────│ │─────────────│ │─────────────│ │
│ │ Đề xuất │───►│ Bỏ phiếu │───►│ Học kết quả │ │
│ │ giá trị │ │ chấp nhận │ │ cuối cùng │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ │
│ │
│ Trong thực tế, một node thường đóng cả 3 vai trò │
│ │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ TWO-PHASE PROTOCOL: │
│ │
│ Phase 1: PREPARE │
│ ───────────────── │
│ Proposer ──► "Prepare(n)" ──► Acceptors │
│ Acceptors ─► "Promise(n, accepted_value)" ─► Proposer │
│ │
│ Phase 2: ACCEPT │
│ ─────────────── │
│ Proposer ──► "Accept(n, value)" ──► Acceptors │
│ Acceptors ─► "Accepted" ─► Learners │
│ │
│ ⚠️ Vấn đề: Nếu 2 Proposers liên tục "đua nhau" prepare │
│ với proposal number tăng dần → LIVELOCK (không bao giờ xong) │
│ │
└─────────────────────────────────────────────────────────────────────────┘2.2 Tại sao Paxos "Khó hiểu"?
| Issue | Mô tả |
|---|---|
| No Leader | Mọi node có thể là Proposer → conflict resolution phức tạp |
| Livelock | Hai proposers có thể block nhau vô hạn |
| Multi-Paxos | Paper gốc chỉ đồng thuận 1 giá trị, log replication cần Multi-Paxos |
| Implementation Gap | Từ paper đến production code là khoảng cách rất lớn |
CAUTION
🎓 Giáo sư Tom: Lamport từng nói: "Paxos paper was written for an audience of Greek philosophers, not for engineers." Đây là lý do Diego Ongaro và John Ousterhout tạo ra Raft năm 2014 - một thuật toán được thiết kế để dễ hiểu.
3. Raft: The Understandable One
3.1 Raft Core Concept
┌─────────────────────────────────────────────────────────────────────────┐
│ RAFT NODE STATES │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────┐ │
│ │ FOLLOWER │ │
│ │ (Default) │ │
│ └──────┬──────┘ │
│ │ │
│ Election Timeout │
│ (no heartbeat) │
│ │ │
│ ▼ │
│ ┌─────────────┐ │
│ ┌──────────►│ CANDIDATE │◄──────────┐ │
│ │ └──────┬──────┘ │ │
│ │ │ │ │
│ Election Wins Election Split Vote │
│ Timeout (majority) (retry) │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌─────────────┐ │ │
│ └───────────│ LEADER │───────────┘ │
│ │ (Only ONE) │ │
│ └─────────────┘ │
│ │ │
│ Discovers higher term │
│ │ │
│ ▼ │
│ ┌─────────────┐ │
│ │ FOLLOWER │ │
│ └─────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘Ba thành phần chính của Raft:
| Component | Chức năng |
|---|---|
| Leader Election | Bầu chọn một Leader duy nhất trong cluster |
| Log Replication | Leader sao chép log entries đến Followers |
| Safety | Đảm bảo State Machine Safety (cùng log → cùng state) |
3.2 Leader Election (Bầu chọn Lãnh đạo)
┌─────────────────────────────────────────────────────────────────────────┐
│ LEADER ELECTION FLOW │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ TERM 1: Normal Operation │
│ ════════════════════════ │
│ │
│ ┌──────────┐ Heartbeat ┌──────────┐ ┌──────────┐ │
│ │ LEADER │◄────────────────────►│ FOLLOWER │ │ FOLLOWER │ │
│ │ Node A │ (AppendRPC) │ Node B │ │ Node C │ │
│ │ Term: 1 │ │ Term: 1 │ │ Term: 1 │ │
│ └──────────┘ └──────────┘ └──────────┘ │
│ │ │ │ │
│ ╳ (CRASH!) │ │ │
│ │ │ │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ TERM 2: Election Triggered │
│ ══════════════════════════ │
│ │
│ Node B: "No heartbeat for 300ms... Starting election!" │
│ │
│ ┌──────────┐ RequestVote ┌──────────┐ │
│ │ (dead) │ │CANDIDATE │────────────────┐ │
│ │ Node A │ │ Node B │ RequestVote │ │
│ │ │ │ Term: 2 │ │ │
│ └──────────┘ └────┬─────┘ │ │
│ │ │ │
│ │ ▼ │
│ │ ┌──────────┐│
│ │ │ FOLLOWER ││
│ │ │ Node C ││
│ │ │ Term: 2 ││
│ │ └────┬─────┘│
│ │ Vote for B │ │
│ ◄───────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ Node B becomes │ │
│ │ LEADER! │ │
│ │ (2/3 = Majority)│ │
│ └─────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘Election Rules:
- Election Timeout: Random 150-300ms để tránh split vote
- Term Number: Monotonically increasing, giống "nhiệm kỳ tổng thống"
- Vote Once Per Term: Mỗi node chỉ vote 1 lần trong 1 term
- Majority Wins: Cần
(N/2) + 1votes để thắng
3.3 Log Replication (Sao chép Nhật ký)
┌─────────────────────────────────────────────────────────────────────────┐
│ LOG REPLICATION │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Client Request: SET x = 5 │
│ │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ LEADER │ │
│ │ Log: [T1:SET a=1] [T1:SET b=2] [T2:SET x=5] │ │
│ │ ▲ │ │
│ │ (Uncommitted) │ │
│ └───────────────────────────────────┬─────────────────────────┘ │
│ │ │
│ AppendEntries RPC │ │
│ ┌─────────────────────────┼─────────────────────────┐ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌─────────────────┐ ┌─────────────────┐ ┌────────────┐│
│ │ FOLLOWER 1 │ │ FOLLOWER 2 │ │ FOLLOWER 3 ││
│ │ [T1:a=1][T1:b=2]│ │ [T1:a=1][T1:b=2]│ │ (slow) ││
│ │ [T2:x=5] ✓ │ │ [T2:x=5] ✓ │ │ [T1:a=1] ││
│ └────────┬────────┘ └────────┬────────┘ └────────────┘│
│ │ │ │
│ └─────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌───────────────────┐ │
│ │ 3/4 Acknowledged │ │
│ │ (Majority = 3) │ │
│ │ │ │
│ │ COMMIT: x = 5 ✓ │ │
│ └───────────────────┘ │
│ │
│ ⚠️ Entry chỉ được COMMIT khi majority của cluster ACK │
│ Follower 3 sẽ "catch up" khi kết nối lại │
│ │
└─────────────────────────────────────────────────────────────────────────┘3.4 Split-Brain Scenario: Địa ngục của Distributed Systems
WARNING
Split-Brain xảy ra khi network partition chia cluster thành 2+ phần, mỗi phần "nghĩ" mình là đa số và bầu Leader riêng. Kết quả: Data inconsistency.
┌─────────────────────────────────────────────────────────────────────────┐
│ SPLIT-BRAIN SCENARIO │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ BEFORE PARTITION (Normal: 5 nodes, 1 Leader) │
│ ═══════════════════════════════════════════ │
│ │
│ Node 1 Node 2 Node 3 Node 4 Node 5 │
│ [LEADER] [FOLLOWER] [FOLLOWER] [FOLLOWER] [FOLLOWER]
│ ▲ ▲ ▲ ▲ ▲ │
│ └───────────────┴──────────────┴──────────────┴──────────────┘ │
│ Network OK │
│ │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ DURING PARTITION │
│ ════════════════ │
│ │
│ ┌─────────────────────┐ ╳╳╳╳╳╳╳ ┌──────────────────────────────────┐ │
│ │ PARTITION A │ NETWORK │ PARTITION B │ │
│ │ │ CUT │ │ │
│ │ Node 1 Node 2 │ │ Node 3 Node 4 Node 5 │ │
│ │ [LEADER] [FOLLOWER] │ │ [FOLLOWER][FOLLOWER][FOLLOWER] │ │
│ │ │ │ │ │
│ │ Minority (2/5) │ │ Majority (3/5) │ │
│ │ ❌ Cannot commit │ │ ✅ Can elect new Leader │ │
│ │ │ │ │ │
│ └─────────────────────┘ └──────────────────────────────────┘ │
│ │
│ Partition A: Node 1 vẫn là Leader nhưng KHÔNG THỂ commit │
│ (chỉ có 2/5 nodes, không đủ majority) │
│ │
│ Partition B: Node 3 timeout, start election, wins với 3/5 votes │
│ Node 3 becomes new Leader với HIGHER TERM │
│ │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ AFTER PARTITION HEALS │
│ ═════════════════════ │
│ │
│ Node 1 nhận heartbeat từ Node 3 với higher term │
│ → Node 1 STEP DOWN, trở thành Follower │
│ → Node 1 rollback uncommitted entries (nếu có) │
│ → Cluster hội tụ về một Leader duy nhất (Node 3) │
│ │
│ ✅ SAFETY PRESERVED: Nhờ Quorum, không có data loss │
│ │
└─────────────────────────────────────────────────────────────────────────┘Quorum (Đa số) - Chìa khóa của Safety:
| Cluster Size | Quorum | Tolerate Failures |
|---|---|---|
| 3 nodes | 2 | 1 node |
| 5 nodes | 3 | 2 nodes |
| 7 nodes | 4 | 3 nodes |
TIP
🔧 Kỹ sư Raizo: Luôn dùng số lẻ nodes (3, 5, 7). Với 4 nodes, quorum vẫn là 3, nên bạn chỉ tolerate 1 failure - không khác gì 3 nodes, nhưng tốn thêm resource. Với 3 nodes bạn đã có high availability cho hầu hết production workloads.
4. Raizo's Production Advice
CAUTION
🔧 Kỹ sư Raizo - Golden Rule:
"Đừng bao giờ tự implement thuật toán Consensus cho Production. KHÔNG BAO GIỜ. Hãy dùng các implementation đã được battle-tested:
- etcd (Kubernetes, CoreOS) - Raft
- ZooKeeper (Kafka, Hadoop) - ZAB (Zookeeper Atomic Broadcast, tương tự Paxos)
- Consul (HashiCorp) - Raft
Tôi đã thấy những team giỏi nhất mất 2 năm chỉ để viết Raft implementation đúng. Và họ VẪN có bugs."
4.1 When Leader Dies: The Nightmare Scenario
Key Takeaway: Client phải implement retry with idempotency - Leader có thể chết SAU KHI replicate nhưng TRƯỚC KHI respond.
5. Scenario Quiz
Câu hỏi 1: Network Partition
Bạn có cluster 5 nodes Raft. Network partition chia thành 2 phần: Partition A (2 nodes, bao gồm Leader cũ) và Partition B (3 nodes).
Điều gì xảy ra?
👁️ Xem đáp án
Đáp án:
Partition A (2 nodes với Leader cũ):
- Leader vẫn nhận client requests
- Nhưng KHÔNG THỂ COMMIT vì chỉ có 2/5 nodes (không đủ quorum 3)
- Client requests sẽ timeout hoặc block
Partition B (3 nodes):
- Election timeout triggered
- Một node trở thành Candidate, gửi RequestVote
- Nhận 3/5 votes → Trở thành new Leader
- CÓ THỂ COMMIT vì có đủ quorum
Sau khi partition heals:
- Leader cũ (Partition A) nhận heartbeat với higher term
- Step down, trở thành Follower
- Rollback uncommitted entries (nếu có)
- Cluster hội tụ về new Leader
Safety Guarantee: Không có data loss vì chỉ có committed entries mới được applied.
Câu hỏi 2: Leader Crash Timing
Client gửi write request
SET balance = 1000đến Leader. Leader đã replicate đến 2/3 followers và nhận ACK từ họ, nhưng crash TRƯỚC KHI commit.Entry này có bị mất không?
👁️ Xem đáp án
Đáp án: KHÔNG, entry sẽ được bảo toàn!
Lý do:
- Entry đã được replicate đến majority (Leader + 2 followers = 3/3)
- Khi new Leader được bầu, entry này đã có trong log của new Leader
- New Leader sẽ commit entry này vì nó thuộc majority
Tuy nhiên:
- Client không nhận response → phải retry
- Retry phải idempotent (kiểm tra xem operation đã thực hiện chưa)
Ví dụ idempotent design:
Request: { id: "uuid-123", operation: "SET balance = 1000" }
Server check: if request_id "uuid-123" already processed
→ return cached result
else → execute and cache result6. Tiếp theo
Bây giờ bạn đã hiểu về Consensus, hãy khám phá:
Chúng ta sẽ tìm hiểu sự khác biệt giữa Strong Consistency và Eventual Consistency - và tại sao Facebook/TikTok sẵn sàng chấp nhận view counts không chính xác.