en
new
0
Avatar
Huy Hoàng @hhoang
14.1K 205 1.6K
Published Tuesday, 12:33 a.m. 8 min read
17

Cấu trúc dữ liệu và Giải thuật Bài 91: Thuật toán Đồng thuận trên Hệ thống phân tán (Raft / Paxos) - Khi hàng ngàn máy chủ cùng giải một bài toán.

Trong suốt 90 bài học qua, chúng ta đã xây dựng các thuật toán chạy trên một máy tính duy nhất (Single-node). Tuy nhiên, các hệ thống công nghệ hiện đại không thể sống sót nếu chỉ dựa vào một máy chủ. Khi máy chủ đó bị rút điện, đứt cáp, hoặc cháy ổ cứng, toàn bộ hệ thống sẽ sụp đổ (Single Point of Failure).

Để giải quyết vấn đề này, cơ sở dữ liệu và các hệ thống backend được nhân bản (Replication) ra hàng chục, hàng trăm máy chủ chạy song song. Nhưng một cơn ác mộng mới xuất hiện: Split-Brain (Tâm thần phân liệt).

Nếu Client A gửi lệnh "Mua hàng" đến Server 1, và Client B gửi lệnh "Hủy hàng" đến Server 2 cùng một lúc, hệ thống sẽ lưu trạng thái nào? Làm sao để 5 máy chủ hoàn toàn độc lập, giao tiếp qua một mạng lưới nội bộ chập chờn, có thể thống nhất 100% về một trạng thái duy nhất?

Đó là bài toán Đồng thuận Phân tán (Distributed Consensus). Để giải quyết bài toán này, Leslie Lamport đã tạo ra thuật toán Paxos (nhưng nó quá phức tạp để cài đặt thực tế). Năm 2013, Diego Ongaro và John Ousterhout ra mắt Raft — một thuật toán đồng thuận dễ hiểu hơn, mạnh mẽ tương đương, và nhanh chóng trở thành tiêu chuẩn vàng của thế giới Cloud Native.

1. Raft: Triết lý của sự độc tài hợp pháp

Khác với các hệ thống ngang hàng (Peer-to-peer), Raft giải quyết sự đồng thuận bằng cách thiết lập một chế độ "độc tài" có thời hạn. Tại bất kỳ thời điểm nào, một cụm máy chủ (Cluster) chạy Raft chỉ có thể ở một trong 3 trạng thái:

  1. Leader (Người lãnh đạo): Có quyền lực tối cao. Mọi yêu cầu Ghi (Write) từ Client đều phải đi qua Leader.

  2. Follower (Người theo đuôi): Nhận lệnh từ Leader, lưu dữ liệu vào ổ cứng của mình, và không bao giờ tự ý trả lời Client.

  3. Candidate (Ứng cử viên): Trạng thái trung gian khi Follower nghi ngờ Leader đã chết và đứng lên tranh cử.

Thuật toán Raft chia bài toán đồng thuận thành 2 giai đoạn độc lập: Bầu cử (Leader Election) và Sao chép Nhật ký (Log Replication).

2. Giai đoạn 1: Bầu cử Leader (Leader Election)

Raft sử dụng một cơ chế gọi là Nhịp tim (Heartbeat) và Đồng hồ đếm ngược (Election Timeout).

  • Khi hệ thống khởi động, tất cả máy chủ đều là Follower.

  • Mỗi Follower có một đồng hồ đếm ngược (được set ngẫu nhiên từ 150ms150ms đến 300ms300ms).

  • Nếu đồng hồ này đếm về 00 mà Follower không nhận được "nhịp tim" (ping) từ Leader, nó kết luận Leader đã chết. Nó tự phong mình làm Candidate, tăng bộ đếm Nhiệm kỳ (Term) lên 1, tự bỏ 1 phiếu cho chính mình, và gửi yêu cầu xin phiếu (RequestVote) đến các máy khác.

  • Máy nào có đồng hồ đếm ngược chạy xong sớm nhất sẽ tung ra lời kêu gọi trước. Các máy khác khi nhận được yêu cầu hợp lệ sẽ bỏ phiếu cho ứng viên đó và reset đồng hồ của mình.

  • Nếu Candidate nhận được quá bán số phiếu (Majority - ví dụ 3/5 máy), nó chính thức trở thành Leader và bắt đầu phát Heartbeat dồn dập (ví dụ 50ms50ms/lần) để đè bẹp các ứng viên khác, yêu cầu họ quay lại làm Follower.

Tại sao lại là Timeout ngẫu nhiên? Nếu tất cả timeout đều bằng 150ms150ms, mọi máy sẽ cùng ứng cử một lúc, phiếu bầu sẽ bị chia đều (Split Vote) và không ai đắc cử. Sự ngẫu nhiên giúp luôn có một máy chủ nhanh chân hơn hẳn.

3. Giai đoạn 2: Sao chép Nhật ký (Log Replication)

Khi đã có Leader, làm sao để dữ liệu được đồng bộ an toàn? Raft sử dụng cơ chế Ghi nhận 2 pha (Two-phase Commit) trên các bản ghi nhật ký (Log Entries).

Giả sử Client gửi lệnh SET X = 5 tới Leader:

  1. Append (Ghi nháp): Leader ghi lệnh này vào Log của chính nó (trạng thái Uncommitted). Lúc này, XX vẫn chưa chính thức bằng 5.

  2. Replicate (Phân phát): Leader đóng gói lệnh này gửi đến tất cả các Follower.

  3. Acknowledge (Xác nhận): Các Follower nhận được lệnh, ghi nháp vào Log của mình, và gửi phản hồi "OK" về cho Leader.

  4. Commit (Chốt hạ): Khi Leader nhận được chữ ký "OK" từ quá bán (Majority) số Follower (ví dụ 3/5), nó chính thức áp dụng lệnh SET X = 5 vào cơ sở dữ liệu (Commit), trả lời Client "Thành công".

  5. Notify (Thông báo): Trong nhịp tim tiếp theo, Leader báo cho các Follower biết: "Lệnh đó đã được chốt, các anh cũng chốt (Commit) đi".

Sức mạnh của Majority (Quá bán): Nếu cụm có 5 máy, bạn chỉ cần 3 máy sống là hệ thống vẫn hoạt động bình thường. Nếu 2 máy bị đứt mạng (Network Partition), chúng sẽ không bao giờ gom đủ số phiếu 3/5 để bầu Leader mới hay Commit dữ liệu mới, tránh hoàn toàn được lỗi Split-Brain.

4. Trực quan hóa Cỗ máy Trạng thái Raft

Dưới đây là mô phỏng luồng hoạt động của Raft. Bạn có thể quan sát cách cơ chế Timeout ngẫu nhiên giúp bầu ra Leader, và cách dòng dữ liệu từ Client phải chờ xác nhận quá bán mới được Commit.

5. Hiện thực logic cốt lõi bằng Golang

Go là ngôn ngữ khai sinh ra nhiều hệ thống Raft lừng danh (như etcd, Consul). Dưới đây là mô phỏng vòng lặp sự kiện (Event Loop) cốt lõi của một Node trong hệ thống Raft, quản lý sự chuyển đổi giữa 3 trạng thái:

Go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

// Các trạng thái của một Node
type State int

const (
	Follower State = iota
	Candidate
	Leader
)

type RaftNode struct {
	ID          int
	CurrentTerm int
	State       State
	VotedFor    int
	// Kênh (Channel) để nhận tín hiệu Heartbeat từ Leader
	HeartbeatC  chan bool
}

func NewRaftNode(id int) *RaftNode {
	return &RaftNode{
		ID:          id,
		CurrentTerm: 0,
		State:       Follower,
		VotedFor:    -1,
		HeartbeatC:  make(chan bool),
	}
}

// Chạy vòng lặp sự kiện (Event Loop) của máy chủ
func (n *RaftNode) Run() {
	for {
		switch n.State {
		case Follower:
			n.runFollower()
		case Candidate:
			n.runCandidate()
		case Leader:
			n.runLeader()
		}
	}
}

func (n *RaftNode) runFollower() {
	// Random timeout từ 150ms - 300ms
	timeoutDuration := time.Duration(150+rand.Intn(150)) * time.Millisecond
	timeout := time.After(timeoutDuration)

	fmt.Printf("[Node %d] Đang ở trạng thái FOLLOWER (Term: %d). Chờ Heartbeat...\n", n.ID, n.CurrentTerm)

	select {
	case <-n.HeartbeatC:
		// Nhận được Heartbeat từ Leader -> Khôi phục lại trạng thái Follower và đếm ngược lại
		fmt.Printf("[Node %d] Nhận được Heartbeat. Đặt lại đồng hồ.\n", n.ID)
		return
	case <-timeout:
		// Hết giờ mà không có Heartbeat -> Leader đã chết -> Đứng lên ứng cử
		fmt.Printf("[Node %d] Đứt kết nối Leader! Chuyển sang CANDIDATE.\n", n.ID)
		n.State = Candidate
	}
}

func (n *RaftNode) runCandidate() {
	n.CurrentTerm++
	n.VotedFor = n.ID
	votesReceived := 1 // Tự bầu cho mình 1 phiếu

	fmt.Printf("[Node %d] Trở thành CANDIDATE. Kêu gọi bầu cử cho Term %d...\n", n.ID, n.CurrentTerm)

	// Mô phỏng quá trình xin phiếu (RequestVote RPC) từ các Node khác
	// Giả lập nhận được quá bán số phiếu (Majority = 3/5)
	time.Sleep(50 * time.Millisecond) // Độ trễ mạng
	votesReceived = 3 

	if votesReceived >= 3 {
		fmt.Printf("[Node %d] Nhận được %d phiếu. Trở thành LEADER!\n", n.ID, votesReceived)
		n.State = Leader
	} else {
		// Nếu không đủ phiếu (do Split Vote), quay lại làm Follower và chờ Timeout mới
		n.State = Follower
	}
}

func (n *RaftNode) runLeader() {
	fmt.Printf("[Node %d] Đang làm LEADER. Gửi Heartbeat cho toàn cụm...\n", n.ID)
	
	// Leader liên tục gửi Heartbeat (Ví dụ: 50ms một lần)
	for i := 0; i < 3; i++ {
		time.Sleep(50 * time.Millisecond)
		fmt.Printf("[Node %d] Ping Heartbeat (Term: %d)\n", n.ID, n.CurrentTerm)
		// Thực tế: Gửi RPC AppendEntries qua mạng tới các máy khác
	}
	
	// Giả lập Leader bị sập nguồn
	fmt.Printf("[Node %d] Sập nguồn! Rớt chức Leader.\n", n.ID)
	time.Sleep(1 * time.Second) // Hệ thống ngưng trệ 1 giây trước khi reboot
	n.State = Follower
}

func main() {
	rand.Seed(time.Now().UnixNano())
	
	// Khởi tạo một Node và chạy thử State Machine
	node := NewRaftNode(1)
	
	// Bọc vào Goroutine để chạy vô tận
	go node.Run()

	// Chờ xem log 3 giây
	time.Sleep(3 * time.Second)
}

6. Tầm ảnh hưởng của Raft trong Hệ thống Hiện đại

Raft không phải là một thuật toán lý thuyết suông; nó là nền tảng quản lý trạng thái của hàng loạt công nghệ cốt lõi trong ngành công nghiệp phần mềm:

  • etcd (Trái tim của Kubernetes): K8s sử dụng etcd — một key-value store chạy bằng thuật toán Raft — để lưu trữ cấu hình mạng, danh sách các container đang chạy, và trạng thái của toàn bộ cluster. Nếu Leader của etcd sập, K8s tự động bầu Leader mới mà không làm rớt dịch vụ.

  • Kafka (KRaft Mode): Trước đây Kafka phụ thuộc vào ZooKeeper (chạy thuật toán Zab - anh em của Paxos) để quản lý cụm. Từ phiên bản 2.8, Kafka tự xây dựng cơ chế KRaft dựa trên Raft để nhúng thẳng hệ thống đồng thuận vào các Broker, loại bỏ sự cồng kềnh của ZooKeeper.

  • MongoDB & TiDB: Các cơ sở dữ liệu phân tán (NoSQL và NewSQL) đều cài đặt biến thể của Raft trong cơ chế Replica Set để đảm bảo dữ liệu luôn được ghi nhất quán ra nhiều server khác nhau.

Chúng ta đã bước từ việc giải quyết bài toán trên một CPU đơn lẻ sang một cụm Cluster gồm hàng ngàn máy chủ. Để hoàn thiện kiến trúc hệ thống, bước cuối cùng là học cách chia nhỏ dữ liệu ra để nhét vừa vào hàng ngàn máy chủ đó một cách công bằng và có thể mở rộng tự do.

cấu trúc dữ liệu

All Rights Reserved

Table of contents


Viblo
Let's register a Viblo Account to get more interesting posts.
Register