Chào các bạn! Hôm nay chúng ta sẽ nói về một chủ đề rất quan trọng trong hệ thống phân tán - thuật toán đồng thuận. Cụ thể, chúng ta sẽ tìm hiểu về Paxos và Raft - hai cái tên nổi bật nhất trong lĩnh vực này. Tôi sẽ giải thích bằng cách kể chuyện để mọi người dễ hiểu nhất có thể.
Tại Sao Cần "Mọi Người Cùng Quyết Định"?
Hãy tưởng tượng bạn và hai người bạn cùng quản lý một cuốn sổ kế toán quan trọng. Cuốn sổ này chỉ có một bản duy nhất nhưng cả ba đều có thể sửa nội dung. Vấn đề đặt ra là: nếu cả ba cùng muốn sửa sổ cùng lúc (ví dụ chuyển tiền cho cùng một người), ai quyết định? Làm sao để cuối sổ có dữ liệu giống nhau?
Đây chính là thách thức lớn của hệ thống phân tán: tính nhất quán.
Trong lĩnh vực máy tính, giải pháp "sao" cho vấn đề này là thuật toán đồng thuận. Nhiệm vụ của nó là giúp các server node (có thể bị lỗi hoặc chậm mạng) có thể đồng ý về một giá trị nào đó.
Trong lĩnh vực này, có hai cái tên cực kỳ nổi tiếng: Paxos và Raft. Hôm nay chúng ta sẽ tìm hiểu về nguồn gốc và sự phát triển của chúng.
Paxos: "Tiền Bối" Thông Minh Nhưng Khó Hiểu
Thuật toán Paxos giống như một giáo sư toán học có trí tuệ cao nhưng cách diễn đạt rất trừu tượng. Nó đã được đề cập từ năm 1990 bởi Leslie Lamport, nhưng vì quá khó hiểu (ngay cả tác giả cũng dùng câu chuyện "quốc hội Hy Lạp" để giải thích, khiến nhiều người càng hoang mang), nên trong một thời gian dài nó chỉ tồn tại trong các bài báo khoa học, rất ít người có thể thực hiện nó.
Ý chính của Paxos (bản dịch đơn giản):
Trong một cụm Paxos, có ba vai trò (nhưng một node có thể kiêm nhiều vai trò):
- Người đề xuất (Proposer): Người đưa ra đề xuất
- Người chấp nhận (Acceptor): Người bỏ phiếu quyết định. Đề xuất được chấp nhận khi hơn một nửa người chấp nhận đồng ý.
- Người học (Learner): Không bỏ phiếu, chỉ học kết quả cuối cùng.
Quy trình chính của Paxos gồm hai bước:
Giai đoạn chuẩn bị (Prepare): Người đề xuất tạo một số duy nhất (ví dụ: 001), sau đó hỏi tất cả người chấp nhận: "Tôi muốn đề xuất số 001, các bạn đã phê duyệt đề xuất nào khác chưa?" Người chấp nhận sẽ trả lời: "Tôi chưa phê duyệt đề xuất nào khác. Nếu sau đó bạn đề xuất số 001, tôi sẽ chỉ xem xét của bạn."
Giai đoạn chấp nhận (Accept): Sau khi nhận được cam kết từ hơn một nửa người chấp nhận, người đề xuất gửi yêu cầu chính thức: "Vậy xin hãy chấp nhận đề xuất của tôi."
Ví dụ code cho giai đoạn chuẩn bị của Paxos:
class Acceptor:
def __init__(self, node_id):
self.node_id = node_id
self.promised_id = 0 # Số lớn nhất đã cam kết
self.accepted_id = 0 # Số lớn nhất đã chấp nhận
self.accepted_value = None
def process_prepare(self, proposal_id):
# Yêu cầu chuẩn bị: nếu số nhận được lớn hơn đã cam kết, thì cam kết
if proposal_id > self.promised_id:
self.promised_id = proposal_id
return True, self.accepted_id, self.accepted_value
else:
return False, None, None
# Ví dụ: Người đề xuất gửi yêu cầu chuẩn bị với số 5
acceptor_1 = Acceptor("NodeA")
result = acceptor_1.process_prepare(5)
print(f"Kết quả giai đoạn chuẩn bị: {result}")
Ưu điểm của Paxos: Cực kỳ cổ điển, tính đúng đắn được chứng minh toán học, rất đáng tin cậy.
Nhược điểm của Paxos: Quá khó triển khai! Quyết định một vòng có thể bị lặp vô tận, cần thêm cơ chế (ví dụ chọn một người đề xuất chính), khó hiểu và đường cong học tập cao.
Raft: "Người Mới" Được Thiết Kế Để Dễ Hiểu
Năm 2013 đến. Các giáo sư Diego Ongaro và John Ousterhout từ Đại học Stanford cũng không chịu nổi sự phức tạp của Paxos. Họ nói: "Chúng tôi nhất định phải thiết kế một thuật toán đồng thuận đúng như Paxos nhưng dễ hiểu hơn."
Và Raft ra đời.
Raft không phát minh lý thuyết mới, mà thực hiện một "đóng gói kỹ thuật" và "thiết kế module" cực kỳ xuất sắc. Nó chia vấn đề đồng thuận thành ba vấn đề con tương đối độc lập:
- Bầu chọn lãnh đạo (Leader Election): Chọn ra một "ôm đầu", bình thường mọi việc do "ôm đầu" quyết định.
- Sao chép nhật ký (Log Replication): "Ôm đầu" ghi lại quyết định và đồng bộ cho tất cả "em em".
- An toàn (Safety): Đảm bảo nếu "ôm đầu" gặp sự cố, "ôm đầu" mới nhất có đầy đủ dữ liệu nhất.
Quy Trình Cốt Lõi Của Raft: Đơn Giản Như Chọn Lớp Trưởng
Bầu Chọn Lãnh Đạo
Ban đầu, tất cả node đều là "theo dõi" (Follower).
Nếu một node theo dõi trong một khoảng thời gian không nhận được "nhịp tim" từ "ôm đầu" (yêu cầu sao chép nhật ký rỗng), nó sẽ nghĩ rằng "ôm đầu" đã ngã, tự biến thành "ứng viên" (Candidate).
Ứng viên tự bỏ phiếu cho mình,然后拉票:"请选我当新班长！"
Các node khác nhận được yêu cầu bỏ phiếu, nếu chưa bỏ phiếu cho ai khác, sẽ đồng ý. Node có hơn nửa số phiếu trở thành lãnh đạo mới.
Ví dụ code cho thời gian bầu cử trong Raft:
import random
import time
# Mỗi node theo dõi có thời gian bầu cử ngẫu nhiên (ví dụ 150-300 mili giây)
election_timeout = random.randint(150, 300) / 1000 # giây
print(f"Thời gian bầu cử của node hiện tại: {election_timeout} giây")
# Giả lập chờ nhịp tim
start_time = time.time()
# Giả sử không nhận được nhịp tim
if time.time() - start_time > election_timeout:
print("Hết thời gian mà không nhận được nhịp tim! Tôi sẽ trở thành ứng viên và bắt đầu bầu cử.")
Sao Chép Nhật Ký
Sau khi bầu cử xong, tất cả yêu cầu từ client đều gửi cho lãnh đạo.
Lãnh đạo ghi hoạt động của client (ví dụ "đặt X=5") vào nhật ký của mình, sau đó gửi yêu cầu "sao chép nhật ký" cho tất cả node theo dõi.
Khi hơn nửa node theo dõi trả lời "đã ghi", lãnh đạo sẽ đánh dấu nhật ký này là "đã cam kết", rồi áp dụng vào máy trạng thái (thực sự thay đổi giá trị X).
Cuối cùng, lãnh đạo thông báo cho node theo dõi: "Được rồi, nhật ký này đã cam kết, các bạn cũng áp dụng vào máy trạng thái của mình đi!"
Ví dụ code cho mục nhật ký trong Raft:
class LogEntry:
def __init__(self, term, command):
self.term = term # Số term khi tạo nhật ký này
self.command = command # Lệnh cụ thể, ví dụ {"key": "X", "value": 5}
# Tạo một mục nhật ký
entry1 = LogEntry(1, "set X=5")
print(f"Mục nhật ký: term={entry1.term}, lệnh={entry1.command}")
Ví dụ code cho cấu trúc đơn giản của AppendEntries RPC từ lãnh đạo đến một node theo dõi:
# Tham số của yêu cầu AppendEntries RPC
def append_entries_request(leader_term, leader_id, prev_log_index, prev_log_term, entries, leader_commit):
return {
"term": leader_term,
"leaderId": leader_id,
"prevLogIndex": prev_log_index, # Chỉ mục nhật trước đó, dùng cho kiểm tra nhất quán
"prevLogTerm": prev_log_term, # Term của nhật ký trước đó
"entries": entries, # Các mục nhật ký cần sao chép (có thể nhiều)
"leaderCommit": leader_commit # Chỉ mục nhật ký đã cam kết của lãnh đạo
}
# Giả lập yêu cầu
req = append_entries_request(term=2, leader_id="nodeA", prev_log_index=5, prev_log_term=1, entries=[entry1], leader_commit=5)
print("Cấu trúc yêu cầu sao chép nhật ký từ lãnh đạo:", req.keys())
Ví dụ code cho logic đơn giản xử lý AppendEntries của node theo dõi:
def follower_process_append_entries(follower_log, req):
# Kiểm tra nhất quán: kiểm tra term của nhật ký ở vị trí prev_log_index có khớp không
if len(follower_log) >= req["prevLogIndex"] and follower_log[req["prevLogIndex"]-1].term == req["prevLogTerm"]:
# Khớp thành công, thêm nhật ký mới
follower_log.extend(req["entries"])
# Cập nhật chỉ mục cam kết của mình dựa trên leaderCommit
return True, follower_log
else:
# Khớp thất bại, từ chối
return False, follower_log
# Giả lập nhật ký của node theo dõi
follower_log = []
success, new_log = follower_process_append_entries(follower_log, req)
print(f"Sao chép nhật ký có thành công không: {success}")
Ví dụ code cho chuyển đổi trạng thái của node Raft:
class RaftNode:
def __init__(self, node_id):
self.node_id = node_id
self.state = "Follower" # Ba trạng thái: Follower, Candidate, Leader
self.current_term = 0
self.voted_for = None
def become_candidate(self):
self.state = "Candidate"
self.current_term += 1
self.voted_for = self.node_id
print(f"Node {self.node_id} trở thành ứng viên trong term {self.current_term}")
def become_leader(self):
self.state = "Leader"
print(f"Node {self.node_id} trở thành lãnh đạo trong term {self.current_term}!")
# Giả lập chuyển đổi vai trò
node = RaftNode("Node1")
node.become_candidate()
node.become_leader()
Paxos vs Raft: So Sánh Tư Duy
| Đặc điểm | Paxos | Raft |
|---|---|---|
| Mục tiêu thiết kế | Tính đúng đắn tối ưu | Tính đúng đắn + Dễ hiểu |
| Phân chia vai trò | Người đề xuất, Người chấp nhận, Người học (vai trò trừu tượng) | Lãnh đạo, Người theo dõi, Ứng viên (vai trò rõ ràng) |
| Quy trình ra quyết định | Hai giai đoạn (chuẩn bị + chấp nhận), đề xuất có thể đồng thời | Lãnh đạo mạnh + sao chép nhật ký, thứ tự rõ ràng |
| Bầu chọn lãnh đạo | Không có cơ chế bầu chọn rõ ràng, cần thiết kế thêm | Cơ chế bầu chọn rõ ràng, dễ hiểu (nhịp tim + timeout + bỏ phiếu) |
| Điểm khó | Vấn đề sống lại, ngưỡng hiểu cao | Thay đổi thành viên, xử lý snapshot hơi phức tạp |
| Ứng dụng kỹ thuật | Nhiều hệ thống cổ điển (như Chubby) sử dụng nội bộ, nhưng bị đóng gói | Phổ biến hơn: etcd, Consul, TiKV |
Ví dụ code cho phán đoán "đa số" đơn giản:
# Tổng số node
total_nodes = 5
# Số phiếu hoặc phản hồi thành công cần có
majority = total_nodes // 2 + 1
print(f"Trong 5 node, cần ít nhất {majority} phiếu để đạt đồng thuận.")
# Giả lập kết quả bỏ phiếu
votes_received = 3
if votes_received >= majority:
print("Đã có hỗ trợ đa số, quyết định được thông qua!")
else:
print("Chưa đạt đa số, quyết định thất bại.")
Hỏi Đáp
Hỏi: Có người nói Raft là "Paxos dễ triển khai hơn", nói như vậy có đúng không?
Trả lời: Nói như vậy có phần đúng nhưng không hoàn toàn chính xác. Nói chính xác hơn là: Raft và Paxos giải quyết cùng một vấn đề nhưng cách tiếp cận khác nhau. Paxos giống như một công thức toán học, cho bạn sự linh hoạt tối đa, nhưng cũng dễ dùng sai. Còn Raft thì dựa trên tư tưởng của Paxos, thiết kế lại quy trình, thông qua "chọn một lãnh đạo mạnh" và "module hóa" để biến kịch bản đề xuất phức tạp thành có trật tự kiểm soát được. Vậy Raft không phải là phiên bản đơn giản hóa của Paxos, mà là "thuật toán đồng thuận được thiết kế lại cho sự dễ hiểu".
Thay Đổi Thành Viên và Nén Nhật Ký (Chủ Đề Nâng Cao Của Raft)
Tất nhiên, môi trường sản xuất thực tế phức tạp hơn lý thuyết. Ví dụ, cụm muốn thay đổi một máy (thay đổi thành viên), làm sao đảm bảo trong quá trình thay đổi không có vấn đề? Raft sử dụng cách "hai giai đoạn", thông qua "Liên minh chung" (Joint Consensus) để chuyển đổi trơn tru. Ngoài ra, nhật ký không thể tăng vô hạn, Raft sẽ định kỳ làm snapshot, lưu trạng thái hiện tại, rồi bỏ các nhật ký trước đó.
Ví dụ code cho snapshot của Raft (minh họa):
# Trạng thái hiện tại của máy trạng thái: một database dictionary đơn giản
state_machine = {
"user:1001": {"name": "Nguyen Van A", "balance": 100},
"user:1002": {"name": "Tran Thi B", "balance": 200}
}
# Tạo snapshot: lưu trạng thái hiện tại và index/term của nhật ký cuối cùng
def create_snapshot(state_machine, last_included_index, last_included_term):
snapshot = {
"data": state_machine.copy(),
"last_included_index": last_included_index,
"last_included_term": last_included_term
}
# Ở đây có thể ghi snapshot vào đĩa
return snapshot
snap = create_snapshot(state_machine, last_included_index=100, last_included_term=5)
print(f"Đã tạo snapshot, chứa {len(snap['data'])} dữ liệu user, index nhật ký cuối cùng là {snap['last_included_index']}")
Tóm Tắt: Chúng Ta Nên Chọn Gì?
Nếu bạn làm nghiên cứu học thuật, muốn đi sâu vào nền tảng lý thuyết, thì Paxos và các biến thể của nó (Multi-Paxos, Fast Paxos) là môn học bắt buộc.
Nếu bạn làm phát triển kỹ thuật, cần chọn một thư viện thuật toán đồng thuận cho hệ thống phân tán của mình (như trung tâm cấu hình, database phân tán), thì hãy chọn Raft. Vì triển khai của nó (như thư viện Raft của etcd) trưởng thành hơn, tài liệu tốt hơn, khi có vấn đề cũng dễ debug hơn.
Từ Paxos đến Raft, chúng ta thấy được ví dụ kinh điển về "lý thuyết đi vào thực tiễn" trong khoa học máy tính: một lý thuyết tối ưu (Paxos) đã truyền cảm hứng cho những người đi sau, và một thiết kế lấy con người làm trung tâm (Raft) cuối cùng đã giúp công nghệ phổ biến đến với mọi người.
Mẹo Ghi Nhớ
Điểm ghi nhớ Paxos: Hai giai đoạn (chuẩn bị + chấp nhận), một cốt lõi (đa số). Nếu không hiểu, không phải lỗi của bạn, vì nó quá "toán học".
Điểm ghi nhớ Raft: Trước chọn đầu, sau làm việc, sao chép nhật ký phải qua đa số; nhịp tim timeout tránh chia cắt, mọi quyết định do đầu chủ.
Nhớ vài câu này, bạn đã nắm được điểm cốt lõi rồi.