Tuần Bonus: Consensus — Raft & Paxos

“Trong một cluster 5 nodes, có 2 node nói ‘X = 1’, 1 node nói ‘X = 2’, và 2 node mất kết nối. Giá trị thật của X là gì? Câu trả lời không phải ‘biểu quyết majority’. Câu trả lời là một thuật toán dài 18 trang gọi là Raft — và nếu sai một bước, em sẽ split-brain, mất data, hoặc tệ hơn — phục vụ data sai cho khách hàng mà không hề biết.”

Tags: system-design consensus raft paxos distributed-systems bonus Student: Hieu (Backend Dev → Architect) Prerequisite: Tuan-07-Database-Sharding-Replication · Tuan-10-Consistent-Hashing Liên quan: Tuan-08-Message-Queue · Tuan-20-Design-Key-Value-Store · Case-Design-Distributed-Message-Queue · Case-Design-Stock-Exchange · Case-Design-Payment-System

1. Context & Why

Analogy đời thường — Ban hội đồng quản trị

Hieu, tưởng tượng em là chủ tịch một công ty 5 người sáng lập. Mỗi quyết định lớn (mua tài sản, thuê CEO, đổi tên công ty) phải được “thông qua” — nhưng:

Các thành viên ở 5 thành phố khác nhau (network partition khả thi)
Có người đang ngủ lúc bỏ phiếu (server crash)
Có người gửi thư bị thất lạc (message loss)
Có người gửi 2 lần (duplicate)
Có người gửi sai thứ tự (out of order)
Tệ nhất: có người gửi thư giả mạo nhân danh người khác (Byzantine)

Câu hỏi: làm sao em đảm bảo:

Mọi người cùng đồng ý một quyết định duy nhất (Agreement)
Không ai đồng ý hai quyết định khác nhau (No double vote)
Cuối cùng phải có quyết định (Termination — không treo mãi)
Quyết định đã thông qua không bị đảo ngược (Durability)

Đây chính là bài toán Consensus trong hệ thống phân tán. Nó là nền móng của:

Etcd (Kubernetes lưu state ở đây)
Consul (service discovery)
CockroachDB / TiKV / YugabyteDB (distributed SQL)
Kafka KRaft (thay ZooKeeper từ 2022)
MongoDB Replica Set (election)
Aurora, Spanner, Bigtable — tất cả

Tại sao Backend Dev cần hiểu Consensus?

Lý do	Giải thích
Mọi DB hiện đại đều dùng	PostgreSQL HA (Patroni + etcd), MongoDB replica set, Cassandra (gossip + paxos LWT), Kafka KRaft
Service discovery dùng	Consul, etcd, ZooKeeper — tất cả đều consensus
Distributed lock dùng	Redlock có lỗi, Chubby/etcd lock mới đúng
Leader election	Bất kỳ pattern leader-follower nào (e.g., write coordinator trong sharded DB)
Configuration management	Kubernetes etcd, secrets propagation
Khi sai = mất data hoặc split-brain	Stripe, GitHub, Kafka đã từng outage vì consensus bug

Key insight: Em không cần viết Raft từ đầu (đừng — sẽ có bug subtle). Nhưng em bắt buộc phải hiểu nó để: chọn đúng tool, debug khi cluster down, set timeout đúng, và biết khi nào tool đang lừa em (e.g., Redis Sentinel không phải consensus).

Tại sao Alex Xu không đi sâu vào Raft/Paxos?

Alex Xu vol 1+2 là sách interview-prep. Trong 45 phút interview, Raft chỉ là 1 dòng “use Raft for leader election”. Nhưng trong production, em cần hiểu:

Election timeout phải đặt bao nhiêu? (đáp án phụ thuộc network RTT)
Cluster size lẻ hay chẵn? (luôn lẻ — sẽ giải thích)
Split-brain xảy ra khi nào? (network partition + bug)
Thay node chết như nào? (joint consensus)
Snapshot vs log compaction? (khi WAL > 1GB)

Đây là khoảng cách giữa Senior và Architect.

Tham chiếu chính (đọc trước khi đào sâu)

Raft paper (2014) — Diego Ongaro & John Ousterhout — https://raft.github.io/raft.pdf — paper “In Search of an Understandable Consensus Algorithm” (USENIX ATC ‘14)
Paxos Made Simple (2001) — Leslie Lamport — https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
Raft visualization — https://raft.github.io/ — interactive simulation
Raft Refloated (2014) — formal Raft model với TLA+
etcd Raft implementation — https://github.com/etcd-io/raft — production-grade Go implementation

2. Deep Dive — Khái niệm cốt lõi

2.1 Bài toán Consensus chính thức

Định nghĩa formal: Cho N processes (nodes) trong network bất đồng bộ, mỗi process propose một giá trị $v_{i}$ . Một giao thức consensus phải đảm bảo:

Property	Mô tả
Validity	Giá trị được decide phải là một trong các giá trị propose (không phải số ngẫu nhiên)
Agreement	Không có 2 correct process decide 2 giá trị khác nhau
Termination	Mọi correct process cuối cùng phải decide một giá trị (không treo mãi)
Integrity	Mỗi process chỉ decide một lần

2.1.1 FLP Impossibility — Định lý không thể vượt qua

Fischer-Lynch-Paterson 1985: Trong hệ thống bất đồng bộ thuần túy (asynchronous — không có timeout), với dù chỉ 1 process có thể fail, KHÔNG TỒN TẠI giao thức consensus deterministic nào đảm bảo cả 3 property: Validity + Agreement + Termination.

Tiếng Việt: nếu network có thể delay vô hạn và 1 node có thể chết → không thể vừa đảm bảo “luôn ra quyết định” vừa đảm bảo “không bao giờ ra quyết định sai”.

Ý nghĩa thực tế:

Phải hi sinh 1 trong 3 properties hoặc dùng giả định khác
Raft/Paxos hi sinh Termination trong worst-case (nếu network split mãi mãi → không decide)
Trong thực tế, dùng timeout (partial synchrony) → đảm bảo termination với high probability
Dùng randomization (election timeout random) để tránh livelock

Bài học: Mọi consensus algorithm đều có trade-off giữa Safety và Liveness. Raft/Paxos chọn Safety > Liveness: thà không decide còn hơn decide sai.

2.1.2 Safety vs Liveness

Property	Định nghĩa	Ví dụ trong Raft
Safety (“Bad things never happen”)	Không bao giờ vi phạm invariant	Không có 2 leader cùng term, không commit log conflict
Liveness (“Good things eventually happen”)	Cuối cùng sẽ progress	Cluster cuối cùng sẽ elect leader, cuối cùng sẽ commit

Quy tắc vàng: Nếu phải chọn, Safety > Liveness. Một database treo 5 phút (mất liveness) còn hơn database trả wrong data (mất safety). Stripe sẵn sàng pause payment 10 phút khi etcd partition còn hơn double-charge khách.

2.2 Replicated State Machine Model

Consensus được dùng để xây Replicated State Machine (RSM):

┌───────────────────────────────────────────────────┐
│ Mỗi node có:                                       │
│   - State Machine (deterministic)                  │
│   - Log của các command                            │
│                                                    │
│ Nếu mọi node:                                      │
│   1. Bắt đầu cùng initial state                   │
│   2. Apply cùng chuỗi command theo cùng thứ tự    │
│   → Tất cả node sẽ có cùng state cuối cùng        │
│                                                    │
│ Consensus job: đảm bảo "cùng chuỗi command"       │
└───────────────────────────────────────────────────┘

Ví dụ: etcd dùng Raft để replicate log của KV operations:

Log entry 1: SET foo=1
Log entry 2: SET bar=2
Log entry 3: DEL foo

Mọi node apply theo thứ tự → kết thúc với {bar: 2}. Đó là RSM.

Tham chiếu: Lamport’s “Time, Clocks, and the Ordering of Events” (1978) — https://lamport.azurewebsites.net/pubs/time-clocks.pdf

2.3 Raft Overview — Decomposition

Raft (2014) được thiết kế với mục tiêu understandability (có thể dạy được). Nó decompose consensus thành 3 sub-problem độc lập:

Sub-problem	Giải quyết bởi
Leader Election	Bầu một node làm leader; chỉ leader nhận write
Log Replication	Leader replicate log entries sang follower; commit khi quorum
Safety	5 invariants đảm bảo không có conflicting decisions

Triết lý cốt lõi của Raft: Strong Leader.

Tất cả write đi qua leader
Log flow một chiều: Leader → Follower (không bao giờ ngược lại)
Đơn giản hoá tư duy → ít bug hơn Multi-Paxos

2.3.1 Server States (3 trạng thái)

                        Timeout, start election
        ┌───────────────────────────────────────────┐
        │                                            ▼
   ┌─────────┐  Step down  ┌─────────────┐  Win election ┌─────────┐
   │ Follower│◄────────────│  Candidate  │──────────────►│ Leader  │
   └─────────┘             └─────────────┘                └─────────┘
        ▲                         │                            │
        │                         │                            │
        │   Discover higher term  │   Discover higher term    │
        └─────────────────────────┴────────────────────────────┘

State	Vai trò
Follower	Trạng thái mặc định. Nhận RPC từ leader/candidate, không tự initiate. Reset timer khi nhận heartbeat.
Candidate	Khi follower timeout → trở thành candidate, request vote từ tất cả node.
Leader	Sau khi thắng election. Gửi heartbeat (AppendEntries trống) định kỳ, nhận client request.

Invariant: Tại bất kỳ thời điểm nào, tối đa 1 leader trong cùng 1 term. Đây là Election Safety property.

2.3.2 Term — Đơn vị thời gian logic

Raft chia thời gian thành các term (nhiệm kỳ), được đánh số liên tục: term 1, term 2, term 3, …

Term 1                Term 2          Term 3            Term 4
┌──────────┐         ┌──────┐         ┌────────────┐    ┌────────┐
│ Election │ Normal  │ Split│ No      │  Election  │ ...│        │
│          │ ops     │ vote │ leader  │            │    │        │
└──────────┘         └──────┘         └────────────┘    └────────┘
            ▲                ▲                       ▲
       Leader L1 dies    No winner           Leader L3 elected

Quy tắc về term:

Mỗi term bắt đầu bằng election
Mỗi term có tối đa 1 leader (hoặc không có nếu split vote)
Term là monotonically increasing number
Mỗi RPC chứa term của sender
Nếu node nhận RPC với term lớn hơn term của mình → cập nhật term + chuyển về Follower
Nếu node nhận RPC với term nhỏ hơn → reject

Key insight: Term hoạt động như logical clock — giúp phát hiện stale leader. Nếu old leader (đã bị isolate) gửi AppendEntries với term cũ, follower sẽ reject. Đây là cách Raft tránh split-brain.

2.4 Leader Election — Chi tiết

2.4.1 Election Trigger

Election được trigger khi follower không nhận heartbeat từ leader trong election timeout:

# Pseudo-code
def follower_loop():
    while True:
        msg = recv(timeout=election_timeout)
        if msg is None:
            # Timeout → start election
            become_candidate()
        elif msg is AppendEntries:
            reset_election_timeout()
            handle_append_entries(msg)

2.4.2 Election Timeout — Random hoá

Vấn đề: Nếu mọi node có cùng election timeout → tất cả timeout cùng lúc → tất cả thành candidate → tất cả vote cho mình → split vote (không ai đủ majority) → loop vô hạn.

Giải pháp Raft: Random hoá timeout trong khoảng [T, 2T]:

import random
 
ELECTION_TIMEOUT_MIN = 150  # ms
ELECTION_TIMEOUT_MAX = 300  # ms
 
election_timeout = random.uniform(ELECTION_TIMEOUT_MIN, ELECTION_TIMEOUT_MAX)

Phép tính: Với T=150ms, [T, 2T] = [150, 300]:

Probability 2 node timeout cách nhau < 5ms: ~3% (nhỏ → ít split vote)
Khoảng cách trung bình giữa 2 timeout: ~75ms (đủ để 1 node start election + nhận vote)

Heartbeat interval phải << election timeout:

heartbeat_interval \approx \frac{T}{10}

Ví dụ: T = 150ms → heartbeat = 15-50ms. Nếu heartbeat = T → quá muộn → mất leader.

2.4.3 Election Algorithm

1. Follower timeout → trở thành Candidate
2. Tăng currentTerm += 1
3. Vote cho chính mình (votedFor = self)
4. Reset election timer (random)
5. Gửi RequestVote RPC tới TẤT CẢ node khác (parallel)
6. Đợi response:
   - Nhận đủ majority votes → trở thành Leader
   - Nhận AppendEntries từ leader hợp lệ → trở thành Follower
   - Election timeout (no winner) → tăng term, election lại

RequestVote RPC:

Arguments:
  term         : term hiện tại của candidate
  candidateId  : ID candidate
  lastLogIndex : index của log entry cuối cùng
  lastLogTerm  : term của log entry cuối cùng

Reply:
  term        : currentTerm của receiver (để candidate update)
  voteGranted : true nếu vote

Receiver logic (cực kỳ quan trọng):

def handle_request_vote(req):
    if req.term < currentTerm:
        return RejectVote(currentTerm)
 
    if req.term > currentTerm:
        currentTerm = req.term
        votedFor = None
        state = FOLLOWER
 
    # Đã vote cho ai khác trong term này?
    if votedFor is not None and votedFor != req.candidateId:
        return RejectVote(currentTerm)
 
    # Candidate's log có "up-to-date" so với local log không?
    if not is_log_up_to_date(req.lastLogIndex, req.lastLogTerm):
        return RejectVote(currentTerm)
 
    votedFor = req.candidateId
    persist_state()  # IMPORTANT: phải persist trước khi response
    reset_election_timeout()
    return GrantVote(currentTerm)

2.4.4 “Up-to-date” Log — Election Restriction

Một trong những điểm khôn ngoan nhất của Raft: Voter chỉ vote cho candidate có log at least as up-to-date as voter’s log:

def is_log_up_to_date(candidate_last_index, candidate_last_term):
    my_last_index, my_last_term = log[-1].index, log[-1].term
 
    if candidate_last_term > my_last_term:
        return True
    if candidate_last_term < my_last_term:
        return False
    # Same term → so sánh index
    return candidate_last_index >= my_last_index

Tại sao quan trọng: Đảm bảo leader mới có TẤT CẢ committed entries từ term trước. Đây là cơ sở của Leader Completeness property (sẽ giải thích ở 2.6).

Aha moment: Nếu không có rule này, một node với log cũ có thể được elect làm leader → ghi đè committed entries → mất data đã commit. Đây là cách Raft đảm bảo không bao giờ mất committed data.

2.4.5 Quorum & Majority

Raft cần majority (đa số quá bán) để elect leader và commit log:

Quorum = ⌊ \frac{N}{2} ⌋ + 1

N (cluster size)	Quorum	Có thể chịu lỗi
1	1	0 (không HA)
2	2	0 (1 fail = lost quorum)
3	2	1
4	3	1 (như 3, không lợi gì!)
5	3	2
6	4	2 (như 5, không lợi gì!)
7	4	3

Kết luận quan trọng: Luôn dùng số lẻ node. 4 node và 3 node chịu được cùng số fail (1), nhưng 4 node tốn thêm 1 server, latency commit cao hơn (đợi 3 ack vs 2). Số node phổ biến nhất trong production: 3 (small cluster) hoặc 5 (medium-large).

Tại sao majority? Tại sao không 1 node thôi?

Để 2 quorum không thể tồn tại đồng thời. Bất kỳ 2 majority nào cũng phải giao nhau ở ít nhất 1 node — node đó “biết” cả 2 và sẽ reject một.
Đây là cách Raft tránh split-brain khi network partition.

2.5 Log Replication — Chi tiết

2.5.1 Log Structure

Mỗi log entry gồm:

Index: vị trí trong log (1, 2, 3, …)
Term: term mà entry được tạo
Command: lệnh để apply vào state machine

Index:    1     2     3     4     5     6     7
        ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
Leader  │ T=1 │ T=1 │ T=2 │ T=2 │ T=3 │ T=3 │ T=3 │
        │ x=1 │ y=2 │ x=3 │ y=4 │ z=5 │ x=6 │ y=7 │
        └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
                              ▲
                          commitIndex = 4

State machine chỉ apply entries có index ⇐ commitIndex.

2.5.2 AppendEntries RPC

Heartbeat và log replication dùng cùng RPC: AppendEntries (entries có thể rỗng = heartbeat).

Arguments:
  term         : leader's term
  leaderId     : để follower có thể redirect client
  prevLogIndex : index của entry trước entries[]
  prevLogTerm  : term của prevLogIndex (consistency check)
  entries[]    : log entries để store (rỗng = heartbeat)
  leaderCommit : leader's commitIndex

Reply:
  term         : currentTerm
  success      : true nếu follower có entry tại prevLogIndex matching prevLogTerm

2.5.3 Log Consistency Check (Log Matching Property)

Magic của Raft: Trước khi append entry mới, leader gửi (prevLogIndex, prevLogTerm). Follower chỉ accept nếu log của nó match tại đó.

def handle_append_entries(req):
    if req.term < currentTerm:
        return Failure(currentTerm)
 
    # Reset election timer (đây là heartbeat)
    reset_election_timeout()
 
    # Consistency check
    if req.prevLogIndex >= len(log):
        return Failure(currentTerm)  # Log của follower quá ngắn
    if log[req.prevLogIndex].term != req.prevLogTerm:
        return Failure(currentTerm)  # Conflict tại prevLogIndex
 
    # Truncate any conflicting entries, then append
    for i, new_entry in enumerate(req.entries):
        idx = req.prevLogIndex + 1 + i
        if idx < len(log) and log[idx].term != new_entry.term:
            log = log[:idx]  # Truncate
            break
 
    # Append new entries
    log.extend(req.entries[len(log) - req.prevLogIndex - 1:])
 
    # Advance commitIndex
    if req.leaderCommit > commitIndex:
        commitIndex = min(req.leaderCommit, len(log) - 1)
        apply_to_state_machine_up_to(commitIndex)
 
    return Success(currentTerm)

Log Matching Property (induction):

Nếu 2 entries có cùng index + cùng term → chúng có cùng command
Nếu 2 entries có cùng index + cùng term → tất cả entry trước đó cũng identical

Đây là invariant cực mạnh, cho phép Raft chỉ check 1 entry để biết toàn bộ prefix match.

2.5.4 Conflict Resolution — Backtracking

Khi follower reject AppendEntries (consistency check fail), leader decrement nextIndex và retry:

Leader log:    [1:T1, 2:T1, 3:T2, 4:T2, 5:T3]
Follower log:  [1:T1, 2:T1, 3:T1]              ← conflict tại index 3

Step 1: Leader gửi prevLogIndex=4, prevLogTerm=T2 → Follower reject
Step 2: Leader gửi prevLogIndex=3, prevLogTerm=T2 → Follower reject (T1 != T2)
Step 3: Leader gửi prevLogIndex=2, prevLogTerm=T1 → Follower accept
        → Follower truncate log[3:] và append entries từ leader

Optimization (paper Section 5.3): Follower có thể trả về conflictTerm và conflictIndex để leader skip nhanh hơn (không cần decrement từng index một).

2.5.5 Commit Rule — Khi nào entry “committed”?

Một entry được committed khi:

Leader replicate nó tới majority servers
VÀ entry đó nằm trong leader’s current term

Quy tắc thứ 2 (current term) là điểm tinh tế — nếu thiếu, có thể mất committed entry. Paper Section 5.4.2 mô tả case lỗi.

def update_commit_index():
    """Leader logic: cập nhật commitIndex."""
    for n in range(commitIndex + 1, len(log)):
        # Đếm số node đã replicate đến index n
        count = 1  # leader đã có
        for follower in followers:
            if follower.matchIndex >= n:
                count += 1
 
        # Phải ở current term (paper section 5.4.2)
        if count >= majority and log[n].term == currentTerm:
            commitIndex = n
        else:
            break
    apply_to_state_machine_up_to(commitIndex)

Aha moment: Tại sao “current term” matter? Vì entry từ term cũ có thể bị overwrite bởi leader mới. Chỉ khi leader của term hiện tại commit ít nhất 1 entry → tất cả entry trước đó cũng được committed (theo Log Matching).

2.6 Five Safety Properties — 5 Bất biến

Raft đảm bảo 5 properties (cumulative):

#	Property	Định nghĩa
1	Election Safety	Tối đa 1 leader trong 1 term
2	Leader Append-Only	Leader không bao giờ overwrite hay delete entry trong log của mình; chỉ append
3	Log Matching	Nếu 2 logs có entry cùng (index, term) → tất cả entry trước đó identical
4	Leader Completeness	Nếu entry committed ở term T → entry đó có trong log của tất cả leader của term > T
5	State Machine Safety	Nếu node đã apply entry tại index i → không node nào apply entry khác tại index i

Cách Raft đảm bảo:

(1) Quorum giao nhau → 1 candidate phải lấy vote từ majority → 2 candidate cùng term không thể cùng thắng
(2) Code constraint: leader chỉ log.append(), không bao giờ log[i] = ...
(3) Consistency check trong AppendEntries (prevLogIndex/prevLogTerm)
(4) Election restriction (up-to-date log) + commit rule (current term)
(5) Hệ quả của 1-4

Paper Section 5.4.3 chứng minh formally.

2.7 Membership Changes — Thêm/Bớt Node

Vấn đề: Khi add/remove node, không thể “atomic switch” config — vì với network delay, một số node có thể có config cũ, số khác có config mới → có thể tạo 2 majority cho 2 leader → split-brain.

2.7.1 Joint Consensus (Paper Section 6)

Giải pháp original của Raft: Joint Consensus — chuyển qua 2 phase:

Phase 1: C_old → C_old,new (joint config)
  - Decision cần majority trong CẢ C_old VÀ C_new
  - Tránh split-brain trong giai đoạn transition

Phase 2: C_old,new → C_new
  - Sau khi C_old,new committed, chuyển sang C_new thuần
  - Decision chỉ cần majority C_new

Visualisation:

Time →

Phase 1:  [Old: A,B,C]                          ← Cluster 3 nodes
          [Old: A,B,C] ∪ [New: A,B,C,D,E]      ← Joint config
Phase 2:                  [New: A,B,C,D,E]      ← Cluster 5 nodes

2.7.2 Single-Server Changes (Simpler)

Paper sau đó (Ongaro thesis 2014) giới thiệu single-server membership change — đơn giản hơn:

Chỉ thêm/bớt 1 node mỗi lần
Đảm bảo old majority + new majority luôn giao nhau (vì chỉ khác 1 node)

Etcd implementation: dùng single-server changes (đơn giản, dễ verify).

2.8 Snapshotting — Log Compaction

Vấn đề: Log càng dài, restart càng chậm (replay từ đầu) và tốn disk.

Giải pháp: Định kỳ snapshot toàn bộ state machine, rồi truncate log trước snapshot.

Before snapshot:
Log: [1:SET x=1, 2:SET y=2, ..., 100000:DEL z=99]

After snapshot at index 99000:
Snapshot: {x: ..., y: ..., ...} (state at index 99000)
Log: [99001:..., 99002:..., ..., 100000:DEL z=99]

InstallSnapshot RPC: Khi follower lag quá xa (log of leader đã truncate), leader gửi snapshot:

Arguments:
  term, leaderId
  lastIncludedIndex : last index trong snapshot
  lastIncludedTerm  : term của lastIncludedIndex
  data              : snapshot bytes (chunked)

Khi nào snapshot?

Log size > threshold (e.g., 100MB)
Số entries > threshold (e.g., 100K)
Định kỳ (e.g., mỗi giờ)

Etcd default: snapshot mỗi 100,000 entries; configurable bằng --snapshot-count.

2.9 Paxos — Người tiền nhiệm

Paxos (Lamport 1989, papers 1998 + 2001) là consensus algorithm “kinh điển” — base của Google Chubby, Megastore, Spanner.

2.9.1 Basic Paxos (single-decree)

Roles:

Proposer: đề xuất giá trị
Acceptor: vote
Learner: học giá trị đã chosen

2 phase:

Phase 1 (Prepare):
  Proposer chọn proposal number n, gửi PREPARE(n) tới majority acceptor
  Acceptor: nếu n > max_seen, promise không accept proposal < n
            return previously accepted (n', v') nếu có

Phase 2 (Accept):
  Proposer: nếu nhận majority promise:
    - Nếu có (n', v') trong response → propose v = v' (highest n')
    - Nếu không → propose v = own value
    Gửi ACCEPT(n, v)
  Acceptor: accept nếu chưa promise n'' > n

Single-decree Paxos chỉ chốt 1 giá trị. Để chốt nhiều (như log) → Multi-Paxos.

2.9.2 Multi-Paxos

Tối ưu Basic Paxos cho chuỗi quyết định:

Phase 1 chỉ làm 1 lần (elect “distinguished proposer” = leader)
Phase 2 lặp lại cho từng log entry

→ Tương đương Raft về mặt latency (1 round-trip per log entry).

2.9.3 Tại sao Paxos khó hiểu?

Paper original cực ngắn, dùng analogy Greek parliament
Leader election không tách bạch với log replication
Optimizations (Multi-Paxos, Cheap Paxos, Fast Paxos) khiến variant nở rộ
“Paxos Made Live” (Google 2007) thừa nhận: implementation Paxos thật ở Google Chubby tốn hàng năm engineer để debug

Quote nổi tiếng (Mike Burrows, tác giả Chubby): “There is only one consensus protocol, and that’s Paxos. All other approaches are just broken versions of Paxos.” — đây là lý do Raft phải chứng minh mình tương đương Paxos về safety.

2.10 Raft vs Paxos vs ZAB

Tiêu chí	Raft	Multi-Paxos	ZAB (ZooKeeper)
Đề xuất	Ongaro & Ousterhout 2014	Lamport 1989/1998	ZooKeeper (Yahoo) 2008
Mục tiêu thiết kế	Understandability	Generality	Primary-backup
Strong leader	✅	⚠️ (variant-dependent)	✅
Log flow	Leader → Follower	Bidirectional possible	Leader → Follower
Election	Tách bạch, tường minh	Coupled với consensus	Tách bạch (FLE)
Membership change	Joint consensus / single-server	Reconfiguration variant	Reconfig phiên bản 3.5+
Easy to implement	✅ Yes	❌ No	⚠️ Medium
Production usage	etcd, Consul, TiKV, CockroachDB, Kafka KRaft	Google Chubby, Spanner	ZooKeeper
Paper readability	18 pages, clear pseudo-code	Greek allegory (fun read)	Workshop paper

Tham chiếu:

Ongaro thesis (250+ pages, full proofs): https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pdf
Paxos Made Live (Google 2007): https://research.google/pubs/paxos-made-live-an-engineering-perspective/
ZAB paper: https://marcoserafini.github.io/papers/zab.pdf

2.11 Production Implementations

2.11.1 etcd

Language: Go
Repo: https://github.com/etcd-io/etcd (raft library: https://github.com/etcd-io/raft)
Use case: Kubernetes control plane, service discovery
Cluster size: Khuyến nghị 3 hoặc 5 nodes
Data model: Hierarchical key-value
Notable: etcd raft library được dùng lại bởi CockroachDB, TiKV, Dgraph

2.11.2 Consul

Language: Go
Use case: Service discovery, KV store, service mesh (Connect)
Notable: Dùng riêng raft protocol, có “WAN federation” giữa các datacenter

2.11.3 TiKV / CockroachDB

Language: Rust (TiKV) / Go (CockroachDB)
Use case: Distributed SQL với strong consistency
Notable:
- Mỗi region (range of keys) là một Raft group riêng
- 1 cluster có thể có hàng triệu Raft groups
- Multi-Raft architecture

2.11.4 Apache Kafka KRaft (KIP-500)

Language: Java/Scala
Use case: Replace ZooKeeper từ Kafka 3.3+ (2022)
Notable: Loại bỏ external dependency, đơn giản hoá ops
Tham chiếu: KIP-500 — https://cwiki.apache.org/confluence/display/KAFKA/KIP-500

2.11.5 MongoDB Replica Set

Election: dùng Raft-like algorithm từ MongoDB 3.2+
Notable: Trước đó dùng custom protocol; chuyển sang Raft để đơn giản

2.11.6 Tham khảo nhanh

Hệ thống	Consensus	Vai trò
Kubernetes	etcd (Raft)	Control plane state
Spanner	Paxos	Replication groups
Bigtable	Chubby (Paxos)	Master election
HBase	ZooKeeper (ZAB)	Master election
Cassandra	Không có consensus mặc định	Dùng eventual consistency; LWT dùng Paxos
Redis Sentinel	Không phải Raft	Quasi-leader election (có thể split-brain — tham chiếu Martin Kleppmann’s critique)
Redis Cluster	Không phải Raft	Gossip + epoch-based

Cảnh báo: Redis Sentinel không đảm bảo consensus chặt như Raft. Đọc Kleppmann “How to do distributed locking” (https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html) trước khi dùng Redlock.

3. Estimation — Ước lượng Consensus Cluster

3.1 Election Timeout Calibration

Quy tắc (paper Section 9.1):

broadcastTime ≪ electionTimeout ≪ MTBF

Trong đó:

broadcastTime = thời gian gửi RPC đến mọi server và nhận response (~0.5ms intra-DC, ~50ms cross-region)
electionTimeout = timeout để follower trở thành candidate (~150-300ms)
MTBF = Mean Time Between Failures (~tháng — năm)

Rule of thumb: electionTimeout >= 10 × broadcastTime.

Ví dụ:

Single-DC cluster: broadcastTime ~0.5ms → electionTimeout 150-300ms (etcd default)
Multi-region cluster: broadcastTime ~50ms (US-EU) → electionTimeout 1000-2000ms

3.2 Throughput của Raft Cluster

Setup: 5-node Raft cluster, intra-DC, NVMe SSD.

Operation	Latency typical	Throughput typical
Single write (commit)	2-10 ms	5K-50K ops/s
Single read (linearizable)	2-10 ms	5K-50K ops/s
Single read (stale)	< 1 ms	100K+ ops/s
Heartbeat	< 1 ms	N/A

Bottleneck: thường là fsync (WAL persistence). Mỗi commit cần fsync trên majority node.

Commit latency = round_trip_to_majority + fsync_time

Etcd benchmark (5-node cluster, AWS m4.2xlarge, NVMe):

Sequential write: ~16K writes/s, P99 ~10ms
Random read (stale): ~80K reads/s
Linearizable read: ~30K reads/s

3.3 Quorum Size & Fault Tolerance

Cluster size N	Quorum	Tolerate failures	Latency note
3	2	1	Đợi 2 ack (fast)
5	3	2	Đợi 3 ack (slower)
7	4	3	Đợi 4 ack (slowest)
9	5	4	Hiếm dùng — quá chậm

Trade-off: Cluster lớn = chịu lỗi tốt hơn, nhưng commit latency tăng (vì phải đợi nhiều ack hơn).

Best practice: 3 nodes cho dev/staging, 5 nodes cho production critical (DB, K8s control plane).

3.4 Storage Capacity

Etcd (default):

Default DB size limit: 2GB (configurable lên đến 8GB qua --quota-backend-bytes)
Khuyến nghị: giữ < 8GB; nếu lớn hơn → reshard hoặc dùng DB khác

**Mỗi key trung bình ~256 bytes (key + value + metadata):

Max keys = \frac{8 GB}{256 B} = 31 M keys

→ Etcd phù hợp cho metadata (config, service registry), không phù hợp làm primary data store.

3.5 Network Bandwidth

Heartbeat traffic: với N=5 nodes, heartbeat 50ms:

Leader gửi 4 heartbeat × 20/s = 80 RPC/s (vài KB/s — không đáng kể)

Log replication: với write rate W ops/s, average log entry size E bytes:

Bandwidth (leader \to followers) = (N - 1) \times W \times E

Ví dụ: 5 nodes, 10K writes/s, 256B/entry:

= 4 \times 10, 000 \times 256 = 10 MB/s = 80 Mbps

→ 1 Gbps NIC dư sức.

3.6 Recovery Time After Leader Crash

Sequence:

Followers detect leader timeout: ~150-300ms (election timeout)
Election: ~50-150ms (1-2 round trips)
New leader sends initial heartbeat: ~10-50ms

Total downtime \approx 200 ms + 100 ms + 30 ms \approx 300 - 500 ms

→ Sub-second failover. Đây là lý do Kubernetes đứng vững khi 1 master crash.

4. Security First — Bảo mật Consensus

4.1 Threat Model — Crash vs Byzantine

Failure type	Mô tả	Raft handle?
Crash failure	Node chết / restart, không gửi message	✅ Yes
Network partition	Node bị isolate	✅ Yes (minority partition không tiến hành được)
Slow node	Node chậm	✅ Yes (timeout)
Message loss/duplicate	RPC mất hoặc trùng	✅ Yes (idempotent + retry)
Byzantine	Node gửi message sai/giả	❌ NO — cần BFT (PBFT, HotStuff)

Quan trọng: Raft là CFT (Crash Fault Tolerant), không phải BFT (Byzantine Fault Tolerant). Nếu một node bị compromised và gửi RPC giả mạo → Raft có thể bị đánh lừa. Cho blockchain/financial → cần BFT (PBFT, Tendermint, HotStuff).

4.2 mTLS Authentication giữa các Node

Threat: Attacker giả mạo một node → gửi AppendEntries giả → corrupt log.

Mitigation: mTLS — mỗi node có cert riêng, verify cert đối phương.

Etcd config:

etcd \
  --name node1 \
  --listen-peer-urls https://10.0.0.1:2380 \
  --peer-cert-file=/etc/etcd/ssl/peer.crt \
  --peer-key-file=/etc/etcd/ssl/peer.key \
  --peer-trusted-ca-file=/etc/etcd/ssl/ca.crt \
  --peer-client-cert-auth \
  --client-cert-auth \
  --cert-file=/etc/etcd/ssl/server.crt \
  --key-file=/etc/etcd/ssl/server.key \
  --trusted-ca-file=/etc/etcd/ssl/ca.crt

Best practice:

Dùng cert authority riêng cho cluster (không dùng public CA)
Rotate cert định kỳ (90-365 ngày)
Lưu private key trong KMS (HashiCorp Vault, AWS KMS)

4.3 Client Authentication

Threat: Anonymous client read/write etcd → leak K8s secrets, modify cluster state.

Etcd RBAC:

# Tạo user
etcdctl user add admin
 
# Tạo role với permission
etcdctl role add k8s-reader
etcdctl role grant-permission k8s-reader read /registry/
 
# Gán role
etcdctl user grant-role admin k8s-reader
 
# Bật auth
etcdctl auth enable

4.4 Encryption at Rest

Etcd (3.5+) hỗ trợ encryption at rest cho secrets:

# k8s EncryptionConfiguration
apiVersion: apiserver.config.k8s.io/v1
kind: EncryptionConfiguration
resources:
  - resources:
      - secrets
    providers:
      - aescbc:
          keys:
            - name: key1
              secret: <base64-encoded 32-byte AES key>
      - identity: {}

→ K8s API server encrypt secrets bằng AES-256-CBC trước khi ghi vào etcd.

4.5 Audit Log

Mọi mutation phải được log:

etcd --logger=zap --log-outputs=/var/log/etcd/audit.log \
     --log-level=info

Forward log vào SIEM (Splunk, Datadog, Wazuh) để detect:

Failed auth attempts
Suspicious access patterns
Unauthorized config changes

4.6 Network Isolation

Best practice:

Etcd cluster nằm trong private subnet (không public IP)
Firewall chỉ allow:
- Port 2380 (peer-to-peer): chỉ between etcd nodes
- Port 2379 (client): chỉ từ K8s API server / admin bastion
Không expose etcd qua Internet — bao giờ

4.7 Reference: NIST & CIS

NIST SP 800-204C: Implementing Distributed Systems Security
CIS Kubernetes Benchmark Section 1.2: etcd hardening
Kubernetes Security Cheat Sheet: https://cheatsheetseries.owasp.org/cheatsheets/Kubernetes_Security_Cheat_Sheet.html

5. DevOps — Vận hành Etcd Cluster

5.1 Deploying 3-node Etcd Cluster (Docker Compose)

# docker-compose.yml
version: "3.8"
 
services:
  etcd1:
    image: quay.io/coreos/etcd:v3.5.12
    container_name: etcd1
    command:
      - /usr/local/bin/etcd
      - --name=etcd1
      - --initial-advertise-peer-urls=http://etcd1:2380
      - --listen-peer-urls=http://0.0.0.0:2380
      - --advertise-client-urls=http://etcd1:2379
      - --listen-client-urls=http://0.0.0.0:2379
      - --initial-cluster=etcd1=http://etcd1:2380,etcd2=http://etcd2:2380,etcd3=http://etcd3:2380
      - --initial-cluster-state=new
      - --initial-cluster-token=tkn-cluster
      - --data-dir=/etcd-data
      - --auto-compaction-retention=1
      - --auto-compaction-mode=periodic
      - --quota-backend-bytes=8589934592   # 8GB
      - --snapshot-count=100000
    volumes:
      - etcd1-data:/etcd-data
    ports:
      - "2379:2379"
      - "2380:2380"
    networks:
      - etcd-net
 
  etcd2:
    image: quay.io/coreos/etcd:v3.5.12
    container_name: etcd2
    command:
      - /usr/local/bin/etcd
      - --name=etcd2
      - --initial-advertise-peer-urls=http://etcd2:2380
      - --listen-peer-urls=http://0.0.0.0:2380
      - --advertise-client-urls=http://etcd2:2379
      - --listen-client-urls=http://0.0.0.0:2379
      - --initial-cluster=etcd1=http://etcd1:2380,etcd2=http://etcd2:2380,etcd3=http://etcd3:2380
      - --initial-cluster-state=new
      - --initial-cluster-token=tkn-cluster
      - --data-dir=/etcd-data
    volumes:
      - etcd2-data:/etcd-data
    networks:
      - etcd-net
 
  etcd3:
    image: quay.io/coreos/etcd:v3.5.12
    container_name: etcd3
    command:
      - /usr/local/bin/etcd
      - --name=etcd3
      - --initial-advertise-peer-urls=http://etcd3:2380
      - --listen-peer-urls=http://0.0.0.0:2380
      - --advertise-client-urls=http://etcd3:2379
      - --listen-client-urls=http://0.0.0.0:2379
      - --initial-cluster=etcd1=http://etcd1:2380,etcd2=http://etcd2:2380,etcd3=http://etcd3:2380
      - --initial-cluster-state=new
      - --initial-cluster-token=tkn-cluster
      - --data-dir=/etcd-data
    volumes:
      - etcd3-data:/etcd-data
    networks:
      - etcd-net
 
volumes:
  etcd1-data:
  etcd2-data:
  etcd3-data:
 
networks:
  etcd-net:

Verify cluster health:

# Sau khi start
docker exec etcd1 etcdctl member list
docker exec etcd1 etcdctl endpoint status --cluster -w table
docker exec etcd1 etcdctl endpoint health --cluster
 
# Output mẫu:
# +------------------+--------+-----------+----------+
# |    ENDPOINT      | HEALTH | TOOK      | ERROR    |
# +------------------+--------+-----------+----------+
# | http://etcd1:2379 |  true  | 2.5ms     |          |
# | http://etcd2:2379 |  true  | 3.1ms     |          |
# | http://etcd3:2379 |  true  | 2.8ms     |          |
# +------------------+--------+-----------+----------+

5.2 Prometheus Metrics & Alerts

Etcd expose Prometheus metrics ở /metrics.

Critical alerts:

# /etc/prometheus/etcd-alerts.yml
groups:
  - name: etcd_alerts
    rules:
      # Cluster mất leader = không serve request
      - alert: EtcdNoLeader
        expr: etcd_server_has_leader == 0
        for: 1m
        labels:
          severity: critical
        annotations:
          summary: "etcd node {{ $labels.instance }} has no leader"
          runbook: "https://etcd.io/docs/v3.5/op-guide/recovery/"
 
      # Leader election quá thường xuyên = cluster instability
      - alert: EtcdHighLeaderElections
        expr: rate(etcd_server_leader_changes_seen_total[5m]) > 0.1
        for: 10m
        labels:
          severity: warning
        annotations:
          summary: "etcd leader changing frequently ({{ $value }}/s)"
 
      # Commit duration cao = disk slow hoặc network slow
      - alert: EtcdHighCommitDuration
        expr: |
          histogram_quantile(0.99,
            rate(etcd_disk_backend_commit_duration_seconds_bucket[5m])
          ) > 0.25
        for: 10m
        labels:
          severity: warning
        annotations:
          summary: "etcd P99 commit duration is {{ $value }}s"
          description: "Likely disk I/O bottleneck. Check disk fsync latency."
 
      # Quá nhiều proposal failed = consensus có vấn đề
      - alert: EtcdHighProposalFailures
        expr: rate(etcd_server_proposals_failed_total[5m]) > 5
        for: 5m
        labels:
          severity: warning
 
      # DB size gần limit
      - alert: EtcdDbSizeNearQuota
        expr: |
          etcd_mvcc_db_total_size_in_use_in_bytes /
          etcd_server_quota_backend_bytes > 0.8
        for: 10m
        labels:
          severity: warning
        annotations:
          summary: "etcd DB at {{ $value | humanizePercentage }} of quota"
 
      # Network round trip cao giữa peer
      - alert: EtcdHighFsyncDuration
        expr: |
          histogram_quantile(0.99,
            rate(etcd_disk_wal_fsync_duration_seconds_bucket[5m])
          ) > 0.5
        for: 10m
        labels:
          severity: critical
        annotations:
          summary: "etcd WAL fsync P99 is {{ $value }}s — disk too slow"

5.3 Grafana Dashboard

Panel	PromQL	Mục đích
Has Leader	`etcd_server_has_leader`	Health: phải = 1 trên đa số node
Leader Changes	`rate(etcd_server_leader_changes_seen_total[5m])`	Stability: phải gần 0
WAL Fsync P99	`histogram_quantile(0.99, rate(etcd_disk_wal_fsync_duration_seconds_bucket[5m]))`	Disk health: < 10ms
DB Commit P99	`histogram_quantile(0.99, rate(etcd_disk_backend_commit_duration_seconds_bucket[5m]))`	DB health: < 25ms
Proposal Rate	`rate(etcd_server_proposals_committed_total[5m])`	Throughput
Watch Streams	`etcd_debugging_mvcc_watch_stream_total`	Khách hàng watch số lượng
Network RTT P99	`histogram_quantile(0.99, rate(etcd_network_peer_round_trip_time_seconds_bucket[5m]))`	Inter-peer health
DB Size	`etcd_mvcc_db_total_size_in_bytes`	Capacity

5.4 Defragmentation

Vấn đề: Etcd dùng MVCC → key cũ vẫn nằm trên disk dù đã delete. Lâu ngày DB size tăng (fragmentation).

Fix:

# Compact (xoá history cũ)
etcdctl compact $(etcdctl endpoint status -w json | jq -r '.[0].Status.header.revision')
 
# Defrag (giảm DB size thực)
etcdctl defrag --cluster

Khuyến nghị: chạy defrag off-peak hours, mỗi tuần. Khi defrag, node tạm time không serve request (~vài giây).

5.5 Backup & Restore

Snapshot backup:

# Backup
etcdctl snapshot save /backup/etcd-$(date +%Y%m%d-%H%M%S).db
 
# Restore (cần restart cluster)
etcdctl snapshot restore /backup/etcd-20260501.db \
  --name etcd1 \
  --initial-cluster etcd1=http://etcd1:2380,etcd2=http://etcd2:2380,etcd3=http://etcd3:2380 \
  --initial-advertise-peer-urls http://etcd1:2380 \
  --data-dir /etcd-data-restored

Best practice:

Snapshot mỗi 1 giờ → S3 với encryption
Giữ 30 ngày backup
Test restore monthly trên staging

5.6 Disaster Recovery — Lost Quorum

Scenario: 5-node cluster, 3 nodes chết → mất quorum → cluster không hoạt động.

Recovery procedure (etcd docs):

# Step 1: stop survivors
systemctl stop etcd
 
# Step 2: snapshot từ survivor mới nhất
etcdctl --endpoints=https://surviving-node:2379 snapshot save /tmp/snap.db
 
# Step 3: restore với --force-new-cluster trên 1 node
etcdctl snapshot restore /tmp/snap.db \
  --name new-etcd1 \
  --initial-cluster new-etcd1=https://new-host1:2380 \
  --initial-cluster-token new-cluster \
  --initial-advertise-peer-urls https://new-host1:2380
 
# Step 4: start node 1 với data restored
systemctl start etcd
 
# Step 5: thêm các node còn lại bằng `etcdctl member add`
etcdctl member add new-etcd2 --peer-urls=https://new-host2:2380
# Start new-etcd2 với --initial-cluster-state=existing

CẢNH BÁO: --force-new-cluster chỉ dùng khi đã mất quorum không thể recover bằng cách khác. Nó bypass safety checks → có thể mất data committed gần đây.

5.7 Rolling Upgrade

# Etcd hỗ trợ rolling upgrade chỉ giữa minor version kề (3.4 → 3.5)
# Không skip version (3.4 → 3.6 PHẢI qua 3.5)
 
# Quy trình:
# 1. Backup
etcdctl snapshot save /backup/before-upgrade.db
 
# 2. Upgrade từng node một (không bao giờ song song)
for node in etcd1 etcd2 etcd3; do
    ssh $node 'systemctl stop etcd'
    ssh $node 'docker pull quay.io/coreos/etcd:v3.5.12'
    ssh $node 'systemctl start etcd'
 
    # Đợi node join cluster lại
    until etcdctl endpoint health --endpoints=https://$node:2379; do
        sleep 5
    done
done
 
# 3. Verify
etcdctl version
etcdctl member list

6. Code Implementation — Mini Raft

Disclaimer: Đây là educational implementation. Đừng dùng trong production. Production phải dùng etcd/raft, hashicorp/raft, hoặc tikv/raft-rs — đã được battle-tested.

6.1 Python: Raft State Machine (Single-File)

"""
Mini Raft Implementation — Educational
Hỗ trợ: Leader election, Log replication, Heartbeat
KHÔNG hỗ trợ: snapshotting, membership change, persistent state to disk
"""
 
import asyncio
import random
import time
from dataclasses import dataclass, field
from enum import Enum
from typing import Optional
 
 
class State(Enum):
    FOLLOWER = "follower"
    CANDIDATE = "candidate"
    LEADER = "leader"
 
 
@dataclass
class LogEntry:
    term: int
    index: int
    command: str  # E.g., "SET x=1"
 
 
@dataclass
class RaftNode:
    node_id: str
    peers: list[str]  # IDs của các node khác
 
    # Persistent state (paper Figure 2)
    current_term: int = 0
    voted_for: Optional[str] = None
    log: list[LogEntry] = field(default_factory=list)
 
    # Volatile state on all servers
    commit_index: int = 0
    last_applied: int = 0
 
    # Volatile state on leaders
    next_index: dict[str, int] = field(default_factory=dict)
    match_index: dict[str, int] = field(default_factory=dict)
 
    # Internal state
    state: State = State.FOLLOWER
    last_heartbeat: float = 0
    election_timeout: float = 0
    votes_received: set[str] = field(default_factory=set)
 
    # Network mock (in real system: gRPC/HTTP)
    network: Optional["Network"] = None
 
    def __post_init__(self):
        self._reset_election_timeout()
 
    def _reset_election_timeout(self):
        """Random timeout 150-300ms để tránh split vote."""
        self.election_timeout = random.uniform(0.150, 0.300)
        self.last_heartbeat = time.monotonic()
 
    # === Election ===
 
    async def become_candidate(self):
        self.state = State.CANDIDATE
        self.current_term += 1
        self.voted_for = self.node_id
        self.votes_received = {self.node_id}  # Vote cho mình
        self._reset_election_timeout()
 
        print(f"[{self.node_id}] Term {self.current_term}: starting election")
 
        # Gửi RequestVote tới tất cả peer (parallel)
        last_log_index = len(self.log)
        last_log_term = self.log[-1].term if self.log else 0
 
        tasks = [
            self.network.send_request_vote(
                from_id=self.node_id,
                to_id=peer,
                term=self.current_term,
                candidate_id=self.node_id,
                last_log_index=last_log_index,
                last_log_term=last_log_term,
            )
            for peer in self.peers
        ]
        results = await asyncio.gather(*tasks, return_exceptions=True)
 
        for peer, result in zip(self.peers, results):
            if isinstance(result, Exception):
                continue
            term, vote_granted = result
 
            # Discover higher term
            if term > self.current_term:
                self.current_term = term
                self.voted_for = None
                self.state = State.FOLLOWER
                return
 
            if self.state != State.CANDIDATE:
                return  # Đã chuyển state
 
            if vote_granted:
                self.votes_received.add(peer)
 
                # Đủ majority?
                cluster_size = len(self.peers) + 1
                if len(self.votes_received) >= cluster_size // 2 + 1:
                    await self.become_leader()
                    return
 
    async def become_leader(self):
        if self.state != State.CANDIDATE:
            return
 
        self.state = State.LEADER
        print(f"[{self.node_id}] Won election for term {self.current_term}!")
 
        # Initialize leader state
        for peer in self.peers:
            self.next_index[peer] = len(self.log) + 1
            self.match_index[peer] = 0
 
        # Gửi heartbeat ngay lập tức
        await self.send_heartbeats()
 
    # === Vote handler (RPC receiver) ===
 
    def handle_request_vote(
        self,
        term: int,
        candidate_id: str,
        last_log_index: int,
        last_log_term: int,
    ) -> tuple[int, bool]:
        """
        Returns: (current_term, vote_granted)
        """
        # Reject if outdated term
        if term < self.current_term:
            return self.current_term, False
 
        # Step down if higher term
        if term > self.current_term:
            self.current_term = term
            self.voted_for = None
            self.state = State.FOLLOWER
 
        # Đã vote cho người khác?
        if self.voted_for is not None and self.voted_for != candidate_id:
            return self.current_term, False
 
        # Check log up-to-date
        my_last_term = self.log[-1].term if self.log else 0
        my_last_index = len(self.log)
 
        log_ok = (
            last_log_term > my_last_term
            or (last_log_term == my_last_term and last_log_index >= my_last_index)
        )
        if not log_ok:
            return self.current_term, False
 
        # Grant vote
        self.voted_for = candidate_id
        self._reset_election_timeout()
        return self.current_term, True
 
    # === Log replication ===
 
    async def send_heartbeats(self):
        """Leader gửi AppendEntries (có thể trống = heartbeat) tới mọi follower."""
        if self.state != State.LEADER:
            return
 
        tasks = []
        for peer in self.peers:
            next_idx = self.next_index[peer]
            prev_log_index = next_idx - 1
            prev_log_term = (
                self.log[prev_log_index - 1].term
                if prev_log_index > 0 and prev_log_index <= len(self.log)
                else 0
            )
            entries = self.log[next_idx - 1:] if next_idx <= len(self.log) else []
 
            tasks.append(
                self.network.send_append_entries(
                    from_id=self.node_id,
                    to_id=peer,
                    term=self.current_term,
                    leader_id=self.node_id,
                    prev_log_index=prev_log_index,
                    prev_log_term=prev_log_term,
                    entries=entries,
                    leader_commit=self.commit_index,
                )
            )
 
        results = await asyncio.gather(*tasks, return_exceptions=True)
 
        for peer, result in zip(self.peers, results):
            if isinstance(result, Exception):
                continue
            term, success = result
 
            if term > self.current_term:
                # Step down
                self.current_term = term
                self.voted_for = None
                self.state = State.FOLLOWER
                return
 
            if success:
                # Update match/next index
                if peer in self.next_index:
                    n = self.next_index[peer] - 1 + len(
                        [e for e in self.log[self.next_index[peer] - 1:]]
                    )
                    self.match_index[peer] = max(self.match_index[peer], n)
                    self.next_index[peer] = n + 1
            else:
                # Decrement next_index, retry
                self.next_index[peer] = max(1, self.next_index[peer] - 1)
 
        # Update commitIndex
        self._update_commit_index()
 
    def handle_append_entries(
        self,
        term: int,
        leader_id: str,
        prev_log_index: int,
        prev_log_term: int,
        entries: list[LogEntry],
        leader_commit: int,
    ) -> tuple[int, bool]:
        """
        Returns: (current_term, success)
        """
        # Reject outdated
        if term < self.current_term:
            return self.current_term, False
 
        # Step down if higher
        if term > self.current_term:
            self.current_term = term
            self.voted_for = None
 
        self.state = State.FOLLOWER
        self._reset_election_timeout()
 
        # Consistency check
        if prev_log_index > 0:
            if prev_log_index > len(self.log):
                return self.current_term, False
            if self.log[prev_log_index - 1].term != prev_log_term:
                return self.current_term, False
 
        # Truncate conflicting entries, then append
        for i, new_entry in enumerate(entries):
            log_idx = prev_log_index + i
            if log_idx < len(self.log):
                if self.log[log_idx].term != new_entry.term:
                    self.log = self.log[:log_idx]
                    self.log.append(new_entry)
            else:
                self.log.append(new_entry)
 
        # Update commit index
        if leader_commit > self.commit_index:
            self.commit_index = min(leader_commit, len(self.log))
            self._apply_committed()
 
        return self.current_term, True
 
    def _update_commit_index(self):
        """Leader: cập nhật commit_index dựa trên match_index."""
        for n in range(self.commit_index + 1, len(self.log) + 1):
            count = 1  # Leader đã có
            for peer in self.peers:
                if self.match_index.get(peer, 0) >= n:
                    count += 1
 
            cluster_size = len(self.peers) + 1
            if count >= cluster_size // 2 + 1 and self.log[n - 1].term == self.current_term:
                self.commit_index = n
            else:
                break
 
        self._apply_committed()
 
    def _apply_committed(self):
        """Apply newly committed entries to state machine."""
        while self.last_applied < self.commit_index:
            self.last_applied += 1
            entry = self.log[self.last_applied - 1]
            print(f"[{self.node_id}] Apply: {entry.command}")
 
    # === Client interface ===
 
    def append_command(self, command: str) -> bool:
        """Client gọi để propose command. Chỉ leader accept."""
        if self.state != State.LEADER:
            return False
 
        entry = LogEntry(
            term=self.current_term,
            index=len(self.log) + 1,
            command=command,
        )
        self.log.append(entry)
        # Trigger replication ở loop chính
        return True
 
    # === Main loop ===
 
    async def run(self):
        """Main event loop của Raft node."""
        while True:
            now = time.monotonic()
 
            if self.state == State.LEADER:
                # Heartbeat mỗi 50ms
                await self.send_heartbeats()
                await asyncio.sleep(0.050)
 
            elif self.state in (State.FOLLOWER, State.CANDIDATE):
                if now - self.last_heartbeat > self.election_timeout:
                    await self.become_candidate()
                else:
                    await asyncio.sleep(0.010)
 
 
# === Network Layer (mock) ===
 
class Network:
    """In-memory network để demo. Real implementation dùng gRPC/HTTP."""
    def __init__(self):
        self.nodes: dict[str, RaftNode] = {}
 
    def register(self, node: RaftNode):
        self.nodes[node.node_id] = node
        node.network = self
 
    async def send_request_vote(self, from_id, to_id, term, candidate_id,
                                  last_log_index, last_log_term):
        # Simulate network delay
        await asyncio.sleep(random.uniform(0.005, 0.020))
        peer = self.nodes.get(to_id)
        if not peer:
            raise ConnectionError(f"Peer {to_id} not found")
        return peer.handle_request_vote(term, candidate_id, last_log_index, last_log_term)
 
    async def send_append_entries(self, from_id, to_id, term, leader_id,
                                    prev_log_index, prev_log_term, entries, leader_commit):
        await asyncio.sleep(random.uniform(0.005, 0.020))
        peer = self.nodes.get(to_id)
        if not peer:
            raise ConnectionError(f"Peer {to_id} not found")
        return peer.handle_append_entries(
            term, leader_id, prev_log_index, prev_log_term, entries, leader_commit,
        )
 
 
# === Demo ===
 
async def demo():
    network = Network()
    nodes = []
 
    node_ids = ["A", "B", "C", "D", "E"]
    for nid in node_ids:
        peers = [p for p in node_ids if p != nid]
        node = RaftNode(node_id=nid, peers=peers)
        network.register(node)
        nodes.append(node)
 
    # Run all nodes concurrently
    tasks = [asyncio.create_task(n.run()) for n in nodes]
 
    # Wait for leader election
    await asyncio.sleep(1.0)
 
    leader = next((n for n in nodes if n.state == State.LEADER), None)
    if leader:
        print(f"\n=== Leader elected: {leader.node_id} (term {leader.current_term}) ===\n")
 
        # Submit commands
        for cmd in ["SET x=1", "SET y=2", "DEL x"]:
            leader.append_command(cmd)
            await asyncio.sleep(0.2)  # Đợi replication
 
    await asyncio.sleep(2)
 
    # Cancel
    for t in tasks:
        t.cancel()
 
 
if __name__ == "__main__":
    asyncio.run(demo())

6.2 Sử dụng `etcd/raft` (Go) — Production-grade

// Reference: https://github.com/etcd-io/raft
 
package main
 
import (
    "context"
    "go.etcd.io/raft/v3"
    "go.etcd.io/raft/v3/raftpb"
    "time"
)
 
// Đây là skeleton — etcd/raft cung cấp consensus,
// app phải implement: storage, transport, state machine
 
type RaftNode struct {
    node    raft.Node
    storage *raft.MemoryStorage  // Production: dùng disk-backed storage
    cfg     *raft.Config
}
 
func NewRaftNode(id uint64, peers []raft.Peer) *RaftNode {
    storage := raft.NewMemoryStorage()
    cfg := &raft.Config{
        ID:              id,
        ElectionTick:    10,                      // 10 × tick interval = election timeout
        HeartbeatTick:   1,                       // 1 × tick = heartbeat
        Storage:         storage,
        MaxSizePerMsg:   1024 * 1024,            // 1 MB per AppendEntries
        MaxInflightMsgs: 256,
    }
 
    n := raft.StartNode(cfg, peers)
    return &RaftNode{node: n, storage: storage, cfg: cfg}
}
 
func (rn *RaftNode) Run(ctx context.Context) {
    ticker := time.NewTicker(100 * time.Millisecond)
    defer ticker.Stop()
 
    for {
        select {
        case <-ticker.C:
            rn.node.Tick()
 
        case rd := <-rn.node.Ready():
            // 1. Persist hard state + entries to disk
            rn.storage.Append(rd.Entries)
            // ... save HardState to durable storage
 
            // 2. Send messages to peers
            for _, msg := range rd.Messages {
                go sendToPeer(msg)
            }
 
            // 3. Apply committed entries to state machine
            for _, entry := range rd.CommittedEntries {
                applyToStateMachine(entry)
            }
 
            // 4. Advance — báo cho Raft là đã xử lý xong
            rn.node.Advance()
 
        case <-ctx.Done():
            rn.node.Stop()
            return
        }
    }
}
 
func sendToPeer(msg raftpb.Message) {
    // gRPC/HTTP implementation
}
 
func applyToStateMachine(entry raftpb.Entry) {
    // Apply command to KV store, etc.
}

Production Go Raft libraries:

etcd/raft: most mature, used by etcd, CockroachDB, TiKV

hashicorp/raft: dùng trong Consul, simpler API

tikv/raft-rs: Rust port của etcd/raft

7. System Design Diagrams

7.1 Raft State Machine

stateDiagram-v2
    [*] --> Follower

    Follower --> Candidate: Election timeout<br/>(no heartbeat received)
    Candidate --> Candidate: Election timeout<br/>(split vote, retry)
    Candidate --> Leader: Receive majority votes
    Candidate --> Follower: Discover current leader<br/>or higher term

    Leader --> Follower: Discover higher term<br/>(network partition heal)

    note right of Follower
        - Reset timer on heartbeat
        - Vote at most once per term
        - Apply committed entries
    end note

    note right of Candidate
        - Increment term
        - Vote for self
        - Request votes from peers
    end note

    note right of Leader
        - Send heartbeats
        - Replicate log entries
        - Commit when majority
    end note

7.2 Leader Election Sequence

sequenceDiagram
    participant A as Node A (Follower)
    participant B as Node B (Follower → Candidate)
    participant C as Node C (Follower)
    participant D as Node D (Follower)
    participant E as Node E (Follower)

    Note over A,E: Term 1: Leader was A, but A crashed

    Note over B: Election timeout!<br/>Increment term to 2<br/>Vote for self
    B->>B: state = Candidate<br/>term = 2<br/>votedFor = B

    par Send RequestVote in parallel
        B->>A: RequestVote(term=2, lastLogIdx=10)
        B->>C: RequestVote(term=2, lastLogIdx=10)
        B->>D: RequestVote(term=2, lastLogIdx=10)
        B->>E: RequestVote(term=2, lastLogIdx=10)
    end

    Note over A: A is dead, timeout
    C->>B: VoteGranted=true (votedFor=B, log up-to-date)
    D->>B: VoteGranted=true
    E->>B: VoteGranted=false (already voted for someone else)

    Note over B: Got 3 votes (B,C,D) = majority of 5<br/>Become Leader!
    B->>B: state = Leader

    par Send initial heartbeats
        B->>A: AppendEntries(term=2, entries=[])
        B->>C: AppendEntries(term=2, entries=[])
        B->>D: AppendEntries(term=2, entries=[])
        B->>E: AppendEntries(term=2, entries=[])
    end

7.3 Log Replication Sequence

sequenceDiagram
    participant Client
    participant L as Leader (B)
    participant F1 as Follower (C)
    participant F2 as Follower (D)
    participant F3 as Follower (E)

    Client->>L: PUT /key=value
    L->>L: Append to log<br/>idx=11, term=2

    par Replicate to majority
        L->>F1: AppendEntries(prevIdx=10, entries=[idx=11])
        L->>F2: AppendEntries(prevIdx=10, entries=[idx=11])
        L->>F3: AppendEntries(prevIdx=10, entries=[idx=11])
    end

    F1->>F1: Append idx=11 to log
    F1-->>L: Success
    F2->>F2: Append idx=11 to log
    F2-->>L: Success
    F3-->>L: Failure (slow/partition)

    Note over L: 3/5 success (majority)<br/>Commit idx=11

    L->>L: commitIndex = 11<br/>Apply to state machine

    L-->>Client: 200 OK

    par Notify followers about commit (next heartbeat)
        L->>F1: AppendEntries(leaderCommit=11)
        L->>F2: AppendEntries(leaderCommit=11)
        L->>F3: AppendEntries(leaderCommit=11)
    end

    F1->>F1: Apply idx=11 to state machine
    F2->>F2: Apply idx=11 to state machine
    F3->>F3: Recovers, applies idx=11

7.4 Network Partition — Split-Brain Prevention

flowchart TB
    subgraph "Before Partition: 5-node cluster, Leader=A, Term=1"
        A1[A: Leader] -.heartbeat.-> B1[B: Follower]
        A1 -.heartbeat.-> C1[C: Follower]
        A1 -.heartbeat.-> D1[D: Follower]
        A1 -.heartbeat.-> E1[E: Follower]
    end

    subgraph "Partition: A,B isolated from C,D,E"
        subgraph Minority["Minority (2 nodes) - cannot elect"]
            A2[A: Leader<br/>Term=1]
            B2[B: Follower]
        end
        subgraph Majority["Majority (3 nodes) - elects new leader"]
            C2[C: New Leader<br/>Term=2]
            D2[D: Follower<br/>Term=2]
            E2[E: Follower<br/>Term=2]
        end
        A2 -.cannot reach.-> C2
    end

    subgraph "Heal: A discovers higher term"
        A3[A: → Follower<br/>Term=2]
        B3[B: Follower<br/>Term=2]
        C3[C: Leader<br/>Term=2]
        D3[D: Follower]
        E3[E: Follower]
        C3 -.heartbeat.-> A3
        C3 -.heartbeat.-> B3
    end

    style A2 fill:#ffcdd2
    style C2 fill:#c8e6c9
    style A3 fill:#fff9c4

Key insight: Trong giai đoạn partition, A vẫn nghĩ mình là leader nhưng không thể commit (không có majority). Khi partition heal, A nhận heartbeat từ C với term=2 > term=1 → step down. Không có split-brain commit data.

7.5 Membership Change — Joint Consensus

sequenceDiagram
    participant Admin
    participant L as Leader
    participant Old as Old Members<br/>(C_old)
    participant New as New Members<br/>(C_new)

    Note over Admin: Add new node D to cluster {A, B, C}

    Admin->>L: Propose config change
    L->>L: Append C_old,new entry to log<br/>(joint config: must satisfy<br/>majority of C_old AND C_new)

    par Replicate joint config
        L->>Old: AppendEntries(C_old,new)
        L->>New: AppendEntries(C_old,new)
    end

    Old-->>L: ack
    New-->>L: ack

    L->>L: Commit C_old,new<br/>(majority in BOTH old and new)

    L->>L: Append C_new entry to log
    par Replicate new config
        L->>Old: AppendEntries(C_new)
        L->>New: AppendEntries(C_new)
    end

    Old-->>L: ack (last action of old members)
    New-->>L: ack

    L->>L: Commit C_new<br/>(majority in C_new only)

    Note over L: Cluster transitioned from C_old to C_new<br/>WITHOUT any moment having 2 majorities

7.6 Snapshot & Log Compaction

flowchart LR
    subgraph BEFORE["Log: 100K entries — too long"]
        E1[Entry 1<br/>SET x=1]
        E2[Entry 2<br/>SET y=2]
        E3[...]
        E99[Entry 99000<br/>DEL z]
        E100[Entry 99001<br/>SET a=5]
        E101[Entry 100000<br/>...]
    end

    subgraph AFTER["After snapshot at index 99000"]
        SNAP["📷 Snapshot<br/>{x: ..., y: ...,<br/>last 99000 state}"]
        E102[Entry 99001<br/>SET a=5]
        E103[Entry 100000<br/>...]

        SNAP --> E102
        E102 --> E103
    end

    BEFORE -->|"Compact:<br/>save snapshot,<br/>truncate log[1..99000]"| AFTER

    style SNAP fill:#bbdefb

7.7 Production Architecture — Etcd in Kubernetes

flowchart TB
    subgraph K8s["Kubernetes Control Plane"]
        APIS[kube-apiserver]
        SCHED[kube-scheduler]
        CTRL[kube-controller-manager]
    end

    subgraph EtcdCluster["Etcd 3-node Cluster (Raft)"]
        E1[etcd-1<br/>Leader]
        E2[etcd-2<br/>Follower]
        E3[etcd-3<br/>Follower]

        E1 -.Raft heartbeat.-> E2
        E1 -.Raft heartbeat.-> E3
        E1 -.Log replication.-> E2
        E1 -.Log replication.-> E3
    end

    subgraph Storage["Per-node Storage"]
        WAL1[(WAL + Snapshot<br/>NVMe SSD)]
        WAL2[(WAL + Snapshot)]
        WAL3[(WAL + Snapshot)]
    end

    subgraph Monitoring["Observability"]
        PROM[Prometheus]
        GRAF[Grafana]
        ALERT[Alertmanager]
    end

    APIS -->|gRPC<br/>linearizable read/write| E1
    SCHED -->|watch /pods| E2
    CTRL -->|watch /deployments| E3

    E1 --> WAL1
    E2 --> WAL2
    E3 --> WAL3

    E1 -->|expose /metrics| PROM
    E2 -->|expose /metrics| PROM
    E3 -->|expose /metrics| PROM
    PROM --> GRAF
    PROM --> ALERT

    style E1 fill:#4caf50,color:#fff
    style E2 fill:#2196f3,color:#fff
    style E3 fill:#2196f3,color:#fff

8. Aha Moments & Pitfalls

Aha Moments

#1: Quorum giao nhau. Bất kỳ 2 majority nào trong cluster N node cũng phải giao nhau ở ít nhất 1 node. Đây là chìa khoá để tránh split-brain — vì node giao đó “biết” cả 2 quyết định và sẽ reject một.

#2: Term là logical clock. Term không phải “session” hay “epoch” thông thường — nó là cơ chế giúp Raft nhận ra stale leader khi network heal. Một old leader gửi RPC với term cũ → bị reject ngay.

#3: Random election timeout là kỹ thuật đơn giản nhưng cực hiệu quả. Không có nó, mọi node sẽ timeout cùng lúc → split vote vô tận.

#4: “Up-to-date log” rule đảm bảo leader mới luôn có TẤT CẢ committed entries. Nếu thiếu rule này, có thể lose committed data — đây là sự khác biệt giữa Raft và một số biến thể Paxos đơn giản.

#5: Số node luôn phải lẻ. 4-node cluster chịu được 1 fail (như 3-node) nhưng tốn thêm 1 server và commit chậm hơn (đợi 3 ack vs 2). 6-node cũng vậy. Chỉ dùng số chẵn khi đang rolling upgrade transient.

#6: Raft không Byzantine-tolerant. Nó chỉ chống crash failure. Nếu một node bị compromised và gửi RPC giả → Raft có thể bị lừa. Cho blockchain → cần PBFT/HotStuff.

#7: Etcd không phải primary database. Nó được tối ưu cho metadata (config, service registry) — DB size limit 8GB, throughput 10-50K ops/s. Đừng dùng làm transactional DB.

#8: Redis Sentinel ≠ Raft. Redis Sentinel là quasi-leader election có thể split-brain trong network partition. Cho distributed lock thật → dùng etcd/Consul/ZooKeeper.

Pitfalls — Sai lầm thường gặp

Pitfall 1: Cluster size = 2 hoặc 4 (chẵn)

Sai: Deploy 2-node etcd cluster để “tiết kiệm” → 1 node fail → mất quorum → cluster down. Đúng: Luôn dùng số lẻ ≥ 3. 3-node cho dev/staging, 5-node cho production critical.

Pitfall 2: Election timeout quá ngắn

Sai: Set election timeout = 50ms vì “muốn failover nhanh” → trên cluster cross-region (RTT 100ms) → leader chưa kịp gửi heartbeat đã timeout → loop election liên tục. Đúng: electionTimeout >= 10 × broadcastTime. Single-DC: 150-300ms. Cross-region: 1000-2000ms.

Pitfall 3: Disk fsync chậm

Sai: Deploy etcd trên HDD hoặc shared storage (network FS) → fsync latency 50-100ms → commit chậm → leader thrashing. Đúng: Dùng dedicated NVMe SSD với fsync < 10ms. Không bao giờ dùng EBS gp2/HDD/EFS cho etcd.

Pitfall 4: Không monitor leader changes

Sai: Setup etcd rồi quên. Sau 6 tháng, leader thay đổi 100 lần/giờ vì disk degrading → cluster vẫn “lên” nhưng latency cực cao. Đúng: Alert khi rate(etcd_server_leader_changes_seen_total[5m]) > 0.1.

Pitfall 5: Thử implement Raft cho production

Sai: Đọc paper Raft → tự code C++ → tin rằng “Raft đơn giản, mình code được”. Đúng: Dùng etcd/raft, hashicorp/raft, hoặc tikv/raft-rs. Có hàng chục edge cases (snapshot streaming, joint consensus, leader transfer, ReadIndex linearizable read) cực dễ sai. Ngay cả paper cũng có errata.

Pitfall 6: Confusing Raft với Replication

Sai: Tưởng PostgreSQL streaming replication = Raft → cluster Patroni “self-healing”. Đúng: Patroni dùng etcd (Raft) ở dưới để leader election, nhưng PostgreSQL replication tự nó không phải consensus. Nếu mất etcd → Patroni cluster không thể auto-failover.

Pitfall 7: Linearizable read tưởng là free

Sai: Mọi etcd get đều linearizable → throughput cao bằng stale read. Đúng: Linearizable read đắt hơn vì cần ReadIndex (round-trip với majority để confirm leader). Throughput có thể 10x thấp hơn stale read. Dùng --consistency=s cho stale read khi không cần linearizable.

Pitfall 8: Membership change song song

Sai: Cố thêm 2 node cùng lúc bằng 2 RPC parallel → có thể tạo 2 majority đồng thời → split-brain. Đúng: Single-server changes — chỉ thêm/bớt 1 node tại 1 thời điểm. Etcd enforce rule này.

Pitfall 9: Không backup

Sai: 3-node etcd “không thể fail” → không setup snapshot. Đúng: Mọi cluster đều cần snapshot. Disk corruption, software bug, operator error đều có thể xoá data ở majority. Snapshot mỗi giờ → S3 với encryption + retention 30 ngày.

Pitfall 10: Etcd làm primary DB

Sai: Lưu user profile (vài GB), order history, transaction log vào etcd vì “đã có sẵn”. Đúng: Etcd chỉ cho metadata (< 8GB, low throughput). Dùng PostgreSQL/Cassandra/DynamoDB cho primary data. Etcd workload điển hình: K8s state, service registry, distributed lock — không phải data plane.

9. Internal Links — Liên kết kiến thức

Consensus trong các tuần khác

Tuần	Chủ đề	Liên hệ với Consensus
Tuan-07-Database-Sharding-Replication	DB Sharding & Replication	Synchronous replication = quorum write; Patroni dùng etcd cho HA
Tuan-08-Message-Queue	Message Queue	Kafka KRaft thay ZooKeeper từ 2022; ISR replication có element của consensus
Tuan-10-Consistent-Hashing	Consistent Hashing	Cassandra dùng gossip + Paxos LWT cho linearizable update
Tuan-11-Microservices-Pattern	Microservices	Service mesh control plane (Istio, Linkerd) dùng etcd/raft
Tuan-13-Monitoring-Observability	Monitoring	Etcd metrics critical: leader changes, fsync, commit latency
Tuan-14-AuthN-AuthZ-Security	Security	mTLS giữa node, RBAC client, encryption at rest
Tuan-20-Design-Key-Value-Store	Key-Value Store	Dynamo dùng Sloppy quorum + hinted handoff (KHÁC consensus)
Case-Design-Distributed-Message-Queue	Distributed MQ	Kafka KRaft, ISR election
Case-Design-Stock-Exchange	Stock Exchange	Matching engine cần linearizable order; có thể dùng Raft
Case-Design-Payment-System	Payment System	Etcd cho distributed lock idempotency
Case-Design-Hotel-Reservation-System	Hotel Reservation	Booking concurrency control: dùng linearizable KV

Tham khảo bắt buộc đọc

Papers:

Diego Ongaro & John Ousterhout, In Search of an Understandable Consensus Algorithm (USENIX ATC ‘14) — https://raft.github.io/raft.pdf
Diego Ongaro, Consensus: Bridging Theory and Practice (PhD thesis, Stanford 2014) — https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pdf
Leslie Lamport, Paxos Made Simple (2001) — https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
Tushar Chandra et al., Paxos Made Live — An Engineering Perspective (Google, 2007) — https://research.google/pubs/paxos-made-live-an-engineering-perspective/
Flavio Junqueira et al., Zab: High-performance broadcast for primary-backup systems (DSN 2011) — https://marcoserafini.github.io/papers/zab.pdf
Fischer, Lynch, Paterson, Impossibility of Distributed Consensus with One Faulty Process (1985) — FLP impossibility theorem

Books:

Martin Kleppmann, Designing Data-Intensive Applications — Chapter 9 “Consistency and Consensus” — https://dataintensive.net/
Roberto Vitillo, Understanding Distributed Systems — Chapter on Replication & Consensus — https://understandingdistributed.systems/
Alex Petrov, Database Internals — Part II: Distributed Systems — https://www.databass.dev/

Implementations & Resources:

etcd raft library — https://github.com/etcd-io/raft
HashiCorp raft — https://github.com/hashicorp/raft
TiKV raft-rs — https://github.com/tikv/raft-rs
Raft visualization — https://raft.github.io/
Raft scope — http://thesecretlivesofdata.com/raft/
Distributed Consensus Reading List — https://github.com/heidihoward/distributed-consensus-reading-list

Engineering blogs:

Martin Kleppmann, How to do distributed locking (critique of Redlock) — https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
CockroachDB, Living without atomic clocks (about TrueTime alternatives) — https://www.cockroachlabs.com/blog/living-without-atomic-clocks/
Marc Brooker, On Quorums and Failover — https://brooker.co.za/blog/

Courses:

MIT 6.5840 Distributed Systems (formerly 6.824) — https://pdos.csail.mit.edu/6.824/ — Lab 2: Implement Raft trong Go
Tham khảo lab 2A (election), 2B (log replication), 2C (persistence), 2D (snapshot)

File tiếp theo (Batch A2): Tuan-Bonus-Consistency-Models-Isolation — Linearizability, Sequential Consistency, MVCC, Snapshot Isolation, Serializable Snapshot Isolation, Jepsen analyses.

File trước trong tuần: Tuan-10-Consistent-Hashing — Consensus thường được dùng song song với consistent hashing trong distributed systems (e.g., TiKV multi-Raft).

lthieu's notes

Explorer

Tuan-Bonus-Consensus-Raft-Paxos

Tuần Bonus: Consensus — Raft & Paxos

1. Context & Why

Analogy đời thường — Ban hội đồng quản trị

Tại sao Backend Dev cần hiểu Consensus?

Tại sao Alex Xu không đi sâu vào Raft/Paxos?

Tham chiếu chính (đọc trước khi đào sâu)

2. Deep Dive — Khái niệm cốt lõi

2.1 Bài toán Consensus chính thức

2.1.1 FLP Impossibility — Định lý không thể vượt qua

2.1.2 Safety vs Liveness

2.2 Replicated State Machine Model

2.3 Raft Overview — Decomposition

2.3.1 Server States (3 trạng thái)

2.3.2 Term — Đơn vị thời gian logic

2.4 Leader Election — Chi tiết

2.4.1 Election Trigger

2.4.2 Election Timeout — Random hoá

2.4.3 Election Algorithm

2.4.4 “Up-to-date” Log — Election Restriction

2.4.5 Quorum & Majority

2.5 Log Replication — Chi tiết

2.5.1 Log Structure

2.5.2 AppendEntries RPC

2.5.3 Log Consistency Check (Log Matching Property)

2.5.4 Conflict Resolution — Backtracking

2.5.5 Commit Rule — Khi nào entry “committed”?

2.6 Five Safety Properties — 5 Bất biến

2.7 Membership Changes — Thêm/Bớt Node

2.7.1 Joint Consensus (Paper Section 6)

2.7.2 Single-Server Changes (Simpler)

2.8 Snapshotting — Log Compaction

2.9 Paxos — Người tiền nhiệm

2.9.1 Basic Paxos (single-decree)

2.9.2 Multi-Paxos

2.9.3 Tại sao Paxos khó hiểu?

2.10 Raft vs Paxos vs ZAB

2.11 Production Implementations

2.11.1 etcd

2.11.2 Consul

2.11.3 TiKV / CockroachDB

2.11.4 Apache Kafka KRaft (KIP-500)

2.11.5 MongoDB Replica Set

2.11.6 Tham khảo nhanh

3. Estimation — Ước lượng Consensus Cluster

3.1 Election Timeout Calibration

3.2 Throughput của Raft Cluster

3.3 Quorum Size & Fault Tolerance

3.4 Storage Capacity

3.5 Network Bandwidth

3.6 Recovery Time After Leader Crash

4. Security First — Bảo mật Consensus

4.1 Threat Model — Crash vs Byzantine

4.2 mTLS Authentication giữa các Node

4.3 Client Authentication

4.4 Encryption at Rest

4.5 Audit Log

4.6 Network Isolation

4.7 Reference: NIST & CIS

5. DevOps — Vận hành Etcd Cluster

5.1 Deploying 3-node Etcd Cluster (Docker Compose)

5.2 Prometheus Metrics & Alerts

5.3 Grafana Dashboard

5.4 Defragmentation

5.5 Backup & Restore

5.6 Disaster Recovery — Lost Quorum

5.7 Rolling Upgrade

6. Code Implementation — Mini Raft

6.1 Python: Raft State Machine (Single-File)

6.2 Sử dụng etcd/raft (Go) — Production-grade

7. System Design Diagrams

7.1 Raft State Machine

7.2 Leader Election Sequence

7.3 Log Replication Sequence

7.4 Network Partition — Split-Brain Prevention

7.5 Membership Change — Joint Consensus

7.6 Snapshot & Log Compaction

7.7 Production Architecture — Etcd in Kubernetes

6.2 Sử dụng `etcd/raft` (Go) — Production-grade