Lần đầu mình mở Raft paper ra, thấy hình state machine với mũi tên tứ tung là đóng tab ngay. Mấy tuần sau deadline ép, mình mới ngồi lại đọc từng trang — core idea chỉ gói gọn trong vài câu. Phần còn lại là edge cases.
Mình sẽ build một simplified Raft bằng Go: leader election và log replication, đối chiếu với Raft paper gốc (Ongaro & Ousterhout). Không dùng library, không abstract gì cả. Mục tiêu là anh em hiểu consensus hoạt động như thế nào — không phải thuộc lòng specification.
Lưu ý trước khi đọc tiếp: code trong bài này là bản giản lược để dạy invariant, không phải Raft production-ready. Không có persistence (ghi disk), không có snapshot/log compaction, không có membership change, và sendRequestVote/sendAppendEntries là placeholder cho transport layer thật — tự implement RPC/network là việc riêng, không nằm trong scope bài này. Đừng copy thẳng vào production.
Vấn đề consensus trông như thế nào khi mọi thứ vỡ
Có N nodes trong một cluster. Anh em muốn chúng agree on một sequence of values — “transaction này đã committed”, “config đã thay đổi”. Nhưng network drop messages, nodes crash bất cứ lúc nào.
Không có consensus protocol thì:
- Node A xử lý request X, node B không nhận được message → hai node có state khác nhau
- Node A crash giữa chừng → ai là source of truth?
- Network partition → hai nhóm nodes tự ra quyết định riêng, reconnect với conflicting history
Raft giải quyết bằng một rule đơn giản: chỉ có một leader được phép quyết định, và mọi quyết định phải được majority (quorum) xác nhận trước khi coi là committed.
State machine của một Raft node
Ba states, chuyển qua lại theo term:
type State int
const (
Follower State = iota
Candidate
Leader
)
type LogEntry struct {
Term int
Command interface{}
}
type RaftNode struct {
mu sync.Mutex
id int
peers []int
state State
currentTerm int
votedFor int // -1 nếu chưa vote trong term này
log []LogEntry
// Cả hai phải được initialize = -1 khi log còn rỗng.
commitIndex int // index cao nhất đã được commit
lastApplied int // index cao nhất đã apply vào state machine
// Leader-only — key là peer ID thật, KHÔNG phải index trong slice n.peers.
// Dùng map thay vì []int vì peer ID không đảm bảo là 0..N-1 liên tục —
// index thẳng vào slice bằng peer ID là một trong những lỗi phổ biến
// nhất khi tự viết Raft, dễ panic (index out of range) hoặc sai âm thầm.
nextIndex map[int]int // peer ID → index tiếp theo cần gửi
matchIndex map[int]int // peer ID → index cao nhất đã replicate thành công
resetTimerCh chan struct{} // báo cho election timer loop restart đếm giờ
stopCh chan struct{}
}Transitions:
- Follower → Candidate: election timeout hết mà không nhận heartbeat từ leader
- Candidate → Leader: nhận đủ votes từ majority
- Candidate / Leader → Follower: nhận message với term cao hơn
Election timeout và cách trigger election
Follower chờ heartbeat từ leader. Timeout mà không có gì → assume leader đã chết, bắt đầu election.
Timeout phải randomized. Nếu tất cả cùng timeout một lúc thì ai cũng self-vote, không ai thắng — split vote mãi mãi.
func randomTimeout() time.Duration {
// 150-300ms là range trong Raft paper
ms := 150 + rand.Intn(150)
return time.Duration(ms) * time.Millisecond
}
func (n *RaftNode) runElectionTimer() {
timer := time.NewTimer(randomTimeout())
defer timer.Stop()
for {
select {
case <-timer.C:
n.mu.Lock()
state := n.state
n.mu.Unlock()
if state != Leader {
// Timeout mà vẫn là Follower hoặc Candidate
// → bắt đầu election mới
go n.startElection()
}
timer.Reset(randomTimeout())
case <-n.resetTimerCh:
// Nhận heartbeat hợp lệ, hoặc vừa vote cho ai đó → restart đếm giờ
if !timer.Stop() {
// Non-blocking drain: Stop có thể báo false trong race window
// khi timer đã fire nhưng value chưa quan sát được trên channel.
select {
case <-timer.C:
default:
}
}
timer.Reset(randomTimeout())
case <-n.stopCh:
return
}
}
}
func (n *RaftNode) resetElectionTimer() {
select {
case n.resetTimerCh <- struct{}{}:
default: // đã có một reset đang chờ xử lý, không cần xếp hàng thêm
}
}Bug hay gặp nhất khi tự viết phần này: tạo timer local trong runElectionTimer, nhưng resetElectionTimer lại Reset một *time.Timer field khác lưu trên struct. Hai timer không liên quan gì tới nhau — gọi resetElectionTimer() không có tác dụng gì lên vòng lặp thật, nên timeout vẫn hết ngay cả khi vừa nhận heartbeat, và Follower dead-loop bắt đầu election liên tục. Pattern đúng là dùng một channel để loop tự Reset chính timer của nó, như trên.
RequestVote: nodes vote cho nhau như thế nào
Node bắt đầu election: increment term, chuyển thành Candidate, tự vote cho mình, gửi RequestVote tới tất cả peers.
type RequestVoteArgs struct {
Term int
CandidateID int
LastLogIndex int // để kiểm tra log up-to-date
LastLogTerm int
}
type RequestVoteReply struct {
Term int
VoteGranted bool
}
func (n *RaftNode) startElection() {
n.mu.Lock()
n.state = Candidate
n.currentTerm++
n.votedFor = n.id
term := n.currentTerm
n.resetElectionTimer() // tự vote cho mình cũng tính là "hoạt động", reset luôn
lastLogIndex := len(n.log) - 1
lastLogTerm := -1
if lastLogIndex >= 0 {
lastLogTerm = n.log[lastLogIndex].Term
}
n.mu.Unlock()
votes := 1 // tự vote cho mình
total := len(n.peers) + 1 // + chính mình
quorum := total/2 + 1
// Cluster một node đã có quorum ngay từ self-vote; không có peer reply
// nào để trigger nhánh becomeLeader bên dưới.
if votes >= quorum {
n.mu.Lock()
if n.currentTerm == term && n.state == Candidate {
n.becomeLeaderLocked()
}
n.mu.Unlock()
return
}
var wg sync.WaitGroup
for _, peer := range n.peers {
wg.Add(1)
go func(peerID int) {
defer wg.Done()
args := RequestVoteArgs{
Term: term,
CandidateID: n.id,
LastLogIndex: lastLogIndex,
LastLogTerm: lastLogTerm,
}
var reply RequestVoteReply
if !n.sendRequestVote(peerID, args, &reply) {
return
}
n.mu.Lock()
defer n.mu.Unlock()
if reply.Term > n.currentTerm {
// Có term cao hơn → mình outdated, step down
n.currentTerm = reply.Term
n.state = Follower
n.votedFor = -1
return
}
// Reply có còn liên quan không? Giữa lúc gửi RequestVote và lúc
// reply về, mình có thể đã step down, hoặc đã bắt đầu một
// election khác (term khác) — vote cho election cũ không còn
// ý nghĩa gì với election hiện tại.
if n.currentTerm != term || n.state != Candidate {
return
}
if reply.VoteGranted {
votes++
if votes >= quorum {
n.becomeLeaderLocked()
}
}
}(peer)
}
wg.Wait()
}
// becomeLeaderLocked chuyển node sang Leader. Caller phải đang giữ n.mu.
// Guard n.state != Candidate ở nơi gọi (trong startElection) đã đảm bảo
// hàm này không bị gọi lại khi đã step down hoặc đã là Leader.
func (n *RaftNode) becomeLeaderLocked() {
n.state = Leader
lastIndex := len(n.log)
n.nextIndex = make(map[int]int, len(n.peers))
n.matchIndex = make(map[int]int, len(n.peers))
for _, peerID := range n.peers {
n.nextIndex[peerID] = lastIndex
n.matchIndex[peerID] = -1
}
go n.runHeartbeat()
}Quorum tính trên tổng số node trong cluster (len(n.peers) + 1, cộng chính mình), không phải trên len(n.peers). Với cluster lẻ số node hai công thức trùng nhau nên bug này dễ lọt qua test, nhưng với cluster chẵn thì sai — len(n.peers)/2 + 1 cho cluster 4 node ra quorum 2, trong khi quorum đúng phải là 3. Quorum sai thì hai quorum có thể không overlap, mất luôn safety guarantee.
Phía nhận vote:
func (n *RaftNode) handleRequestVote(args RequestVoteArgs) RequestVoteReply {
n.mu.Lock()
defer n.mu.Unlock()
if args.Term < n.currentTerm {
// Candidate bị outdated → từ chối, báo lại term hiện tại của mình
return RequestVoteReply{Term: n.currentTerm, VoteGranted: false}
}
if args.Term > n.currentTerm {
// Nhận term mới hơn → step down và cập nhật TRƯỚC khi build reply,
// để reply.Term phản ánh đúng term mới, không phải term cũ
n.currentTerm = args.Term
n.state = Follower
n.votedFor = -1
}
alreadyVoted := n.votedFor != -1 && n.votedFor != args.CandidateID
if alreadyVoted {
return RequestVoteReply{Term: n.currentTerm, VoteGranted: false}
}
// Kiểm tra log up-to-date: candidate's log phải ít nhất bằng mình
myLastIndex := len(n.log) - 1
myLastTerm := -1
if myLastIndex >= 0 {
myLastTerm = n.log[myLastIndex].Term
}
logOK := args.LastLogTerm > myLastTerm ||
(args.LastLogTerm == myLastTerm && args.LastLogIndex >= myLastIndex)
if !logOK {
return RequestVoteReply{Term: n.currentTerm, VoteGranted: false}
}
n.votedFor = args.CandidateID
n.resetElectionTimer()
return RequestVoteReply{Term: n.currentTerm, VoteGranted: true}
}Bug hay bị miss ở đây: bản đầu tiên gán reply.Term = n.currentTerm trước khi kiểm tra args.Term > n.currentTerm — nên nếu nhánh đó chạy và update n.currentTerm, reply vẫn mang giá trị term cũ. Candidate nhận reply với term cũ thì không step down đúng lúc. Cách an toàn là build reply sau khi mọi update đã xong, như trên.
Điều kiện logOK là chỗ anh em hay miss: mình chỉ vote cho candidate nếu log của nó “at least as up-to-date” như log của mình. Đây là cách đảm bảo leader mới không bị thiếu thông tin về những gì đã committed.
Một điều paper yêu cầu mà code ở đây không có: currentTerm, votedFor, và log đều phải được ghi xuống disk (persist) trước khi trả reply cho RPC tương ứng. Nếu node crash rồi restart, nó phải nhớ đã vote cho ai ở term nào — quên mất thì có thể vote hai lần trong cùng một term sau khi restart, phá vỡ chính safety guarantee mà alreadyVoted đang cố bảo vệ. Tương tự, log entries phải persist trước khi ack lại leader — mất log đã ack rồi thì matchIndex leader đang giữ không còn đúng sự thật. Code ở đây chỉ giữ state trong memory, nên chỉ dùng để học, không dùng để chạy node có thể crash-restart.
Tại sao quorum là N/2 + 1
Đây là cái mình thấy elegant nhất trong toàn bộ Raft.
Với 5 nodes, quorum là 3. Bất kỳ hai quorums nào cũng overlap ít nhất 1 node:
Quorum A: {1, 2, 3}
Quorum B: {3, 4, 5}
Overlap: {3} ← node 3 biết cả hai sidesNếu một entry đã committed (ack bởi quorum A), thì bất kỳ leader mới nào được bầu lên (cần quorum B để win) cũng sẽ có ít nhất một node biết về entry đó. Node đó sẽ không vote cho candidate nào mà log thiếu entry đó.
Nếu quorum là N/2 thay vì N/2 + 1 thì hai quorums có thể không overlap → conflicting commits → split brain.
AppendEntries: heartbeat và log replication
AppendEntries là RPC làm hai việc:
- Gửi heartbeat định kỳ để followers biết leader còn sống
- Replicate log entries từ leader xuống followers
type AppendEntriesArgs struct {
Term int
LeaderID int
PrevLogIndex int // index của entry ngay trước entries mới
PrevLogTerm int // term của entry đó
Entries []LogEntry
LeaderCommit int // commitIndex của leader
}
type AppendEntriesReply struct {
Term int
Success bool
}
func (n *RaftNode) handleAppendEntries(args AppendEntriesArgs) AppendEntriesReply {
n.mu.Lock()
defer n.mu.Unlock()
if args.Term < n.currentTerm {
// reply.Term ở đây phải là n.currentTerm của MÌNH, không phải
// args.Term — leader gửi request nhận reply này sẽ thấy term
// cao hơn của mình và biết nó đã outdated
return AppendEntriesReply{Term: n.currentTerm, Success: false}
}
// Nhận message từ current/newer leader → step down nếu cần, reset timer.
// Update currentTerm TRƯỚC khi build reply, để reply.Term không bao giờ
// là giá trị cũ (bug hay gặp: gán reply.Term ngay đầu hàm trước khi
// nhánh này chạy, khiến reply mang term stale).
if args.Term > n.currentTerm {
n.currentTerm = args.Term
n.votedFor = -1
}
n.state = Follower
n.resetElectionTimer()
// Kiểm tra consistency: entry tại PrevLogIndex phải match PrevLogTerm
if args.PrevLogIndex >= 0 {
if args.PrevLogIndex >= len(n.log) {
// Log của mình ngắn hơn → thiếu entries
return AppendEntriesReply{Term: n.currentTerm, Success: false}
}
if n.log[args.PrevLogIndex].Term != args.PrevLogTerm {
// Conflict tại PrevLogIndex → truncate và retry
return AppendEntriesReply{Term: n.currentTerm, Success: false}
}
}
// Append entries mới, overwrite nếu có conflict
for i, entry := range args.Entries {
idx := args.PrevLogIndex + 1 + i
if idx < len(n.log) {
if n.log[idx].Term != entry.Term {
// Conflict → truncate từ đây
n.log = n.log[:idx]
}
}
if idx >= len(n.log) {
n.log = append(n.log, entry)
}
}
// Cập nhật commitIndex theo leader
if args.LeaderCommit > n.commitIndex {
n.commitIndex = min(args.LeaderCommit, len(n.log)-1)
}
return AppendEntriesReply{Term: n.currentTerm, Success: true}
}Leader gửi heartbeat định kỳ:
func (n *RaftNode) runHeartbeat() {
ticker := time.NewTicker(50 * time.Millisecond)
defer ticker.Stop()
for {
select {
case <-ticker.C:
n.mu.Lock()
if n.state != Leader {
n.mu.Unlock()
return
}
n.mu.Unlock()
n.broadcastAppendEntries()
case <-n.stopCh:
return
}
}
}
func (n *RaftNode) broadcastAppendEntries() {
for _, peer := range n.peers {
go n.sendAppendEntriesToPeer(peer)
}
}Commit index: khi nào entry được coi là committed
Leader chỉ advance commitIndex khi majority đã ack:
func (n *RaftNode) sendAppendEntriesToPeer(peerID int) {
n.mu.Lock()
if n.state != Leader {
n.mu.Unlock()
return
}
term := n.currentTerm
nextIdx := n.nextIndex[peerID]
prevLogIndex := nextIdx - 1
prevLogTerm := -1
if prevLogIndex >= 0 && prevLogIndex < len(n.log) {
prevLogTerm = n.log[prevLogIndex].Term
}
entries := n.log[nextIdx:]
args := AppendEntriesArgs{
Term: term,
LeaderID: n.id,
PrevLogIndex: prevLogIndex,
PrevLogTerm: prevLogTerm,
Entries: append([]LogEntry{}, entries...), // copy để tránh race
LeaderCommit: n.commitIndex,
}
n.mu.Unlock()
var reply AppendEntriesReply
if !n.sendAppendEntries(peerID, args, &reply) {
return
}
n.mu.Lock()
defer n.mu.Unlock()
if reply.Term > n.currentTerm {
n.currentTerm = reply.Term
n.state = Follower
n.votedFor = -1
return
}
// Reply có thể đến rất trễ, sau khi mình đã mất rồi giành lại
// leadership (term đã đổi), hoặc không còn là Leader nữa — áp dụng
// một reply stale vào nextIndex/matchIndex sẽ làm hỏng state hiện tại.
if term != n.currentTerm || n.state != Leader {
return
}
if reply.Success {
// Nhiều AppendEntries trong cùng term có thể về lệch thứ tự.
// Chỉ advance, không để reply cũ kéo progress lùi lại.
newMatch := prevLogIndex + len(entries)
if newMatch <= n.matchIndex[peerID] {
return
}
n.matchIndex[peerID] = newMatch
n.nextIndex[peerID] = newMatch + 1
// Check nếu có entry mới có thể commit
n.maybeAdvanceCommitIndex()
} else {
// Chỉ áp dụng failure nếu nextIndex vẫn đúng bằng snapshot dùng để
// gửi request này. Nếu request mới hơn đã advance nó, reply này stale.
if n.nextIndex[peerID] == nextIdx && n.nextIndex[peerID] > 0 {
n.nextIndex[peerID]--
}
}
}
func (n *RaftNode) maybeAdvanceCommitIndex() {
// Tìm N lớn nhất mà majority matchIndex[i] >= N
// và log[N].Term == currentTerm
total := len(n.peers) + 1 // + chính leader
quorum := total/2 + 1
for N := len(n.log) - 1; N > n.commitIndex; N-- {
if n.log[N].Term != n.currentTerm {
// Chỉ commit entries của current term
// (safety property của Raft)
continue
}
count := 1 // leader tự tính
for _, peer := range n.peers {
if n.matchIndex[peer] >= N {
count++
}
}
if count >= quorum {
n.commitIndex = N
break
}
}
}Chú ý n.log[N].Term != n.currentTerm: leader chỉ commit entries của current term. Đây là subtlety hay bị miss — không thể commit entry từ previous term trực tiếp. Phải commit một entry của current term, và entry đó kéo theo tất cả entries trước đó theo Log Matching Property.
Kết
- Đọc Raft paper song song với việc build, đừng bỏ qua nó. Code giúp cụ thể hóa concept và bắt mình xử lý từng edge case, nhưng phần chứng minh “vì sao nó an toàn” nằm trong paper — tự đoán từ code không thay được.
- Quorum overlap là điều kiện cần, không phải đủ. Nó đảm bảo hai quorum bất kỳ luôn gặp nhau ở ít nhất một node, nhưng safety của Raft còn phụ thuộc vào election restriction (chỉ vote cho log up-to-date), Log Matching Property, và rule chỉ commit entry của current term. Thiếu một trong số này, quorum overlap không cứu được anh em.
- Implementation ở bài này là bản giản lược để học invariant, không phải Raft production. Không có persistence, snapshot, membership change, hay network layer thật. Muốn production-grade thì xem
etcd/raft: pure Go, không có network layer sẵn (anh em tự plug transport), nhưng đầy đủ những phần bài này chưa làm, và code có comment đối chiếu từng bước với paper.