Thuật toán đồng thuận Raft, từng bước một

Ba node database cùng nhận một lệnh. Một node mất điện khi đang ghi, một node khác mất kết nối mạng, còn node thứ ba tiếp tục phục vụ traffic. Giá trị nào lúc này mới là sự thật? Quan trọng hơn, làm sao các node còn sống cuối cùng đi đến cùng một quyết định khi không có trọng tài nào biết chính xác chuyện gì đã xảy ra?

Đó là bài toán consensus. Raft đưa bài toán về một replicated log với leader rõ ràng. Client gửi command cho leader; leader sắp thứ tự command trong log; đa số node xác nhận từng quyết định bền vững; mọi node apply các entry đã commit vào cùng một state machine tất định. Kết quả không phải là availability vô điều kiện, mà là một giao thức chính xác để bảo vệ một lịch sử duy nhất trong lúc máy dừng, khởi động lại, message bị lặp và đồng hồ không thống nhất.

Raft được thiết kế để dễ hiểu, nhưng “dễ hơn Paxos” không đồng nghĩa với đơn giản. Safety đến từ nhiều quy tắc phối hợp; bỏ log freshness check hay current-term commit rule có thể phá vỡ lịch sử thống nhất.

Bắt đầu bằng mô hình tư duy đúng #

Một server Raft luôn ở một trong ba vai trò: follower, candidate hoặc leader. Khi hệ thống ổn định, có một leader và các node còn lại là follower. Follower không nghe thấy leader trong khoảng election timeout ngẫu nhiên sẽ thành candidate. Candidate giành được đa số phiếu sẽ thành leader. Mỗi server phải persist ba phần consensus state trước khi trả lời thành công:

• currentTerm: kỷ nguyên logic chỉ tăng, không giảm;
• votedFor: candidate đã nhận phiếu của server trong term hiện tại, nếu có;
• log: chuỗi entry có dạng (index, term, command).

Term là logical clock. Message có term cao hơn buộc receiver cập nhật term và về follower; message từ term cũ bị từ chối. Volatile state gồm commitIndex, entry cao nhất đã committed, và lastApplied, entry cao nhất đã chạy. Leader còn giữ nextIndex và matchIndex cho từng follower.

Consensus cần quorum, không cần toàn bộ node. Với cluster có $N$ voting member, kích thước majority là

Hai majority bất kỳ luôn giao nhau ở ít nhất một server. Điểm giao đó mang tri thức từ quyết định trước sang quyết định sau. Cluster ba node chịu được một node unavailable; cluster năm node chịu được hai. Thêm một voter để thành số chẵn thường làm tăng chi phí phối hợp mà không tăng khả năng chịu lỗi.

Bầu một leader mà không tin đồng hồ tuyệt đối #

Follower reset election timer khi nhận AppendEntries hợp lệ hoặc grant vote. Timeout được random, ví dụ 150–300 ms trong bài báo ban đầu, để các follower ít tranh cử cùng lúc. Giá trị production phải phản ánh network và storage latency thực tế; con số phòng lab không phù hợp hệ thống liên vùng.

Khi timeout xảy ra, follower tăng currentTerm, chuyển thành candidate, tự bỏ phiếu, persist các thay đổi rồi gửi RequestVote cho peer. Receiver chỉ cấp một phiếu nếu term của candidate không cũ và log của candidate ít nhất mới bằng log cục bộ. Cách đánh giá “mới” là so term của entry cuối trước, rồi mới so index. Chỉ so độ dài là sai vì entry từ leader term mới hơn mang bằng chứng mạnh hơn.

Log freshness check là cầu nối giữa election safety và data safety. Candidate bị thiếu một committed entry không thể có log mới hơn mọi thành viên trong majority đã commit entry đó, nên không thể thu đủ đa số phiếu. Đây là nền tảng của tính chất leader completeness: mọi entry đã commit ở term trước đều xuất hiện trong log của các leader về sau.

Split vote không làm hỏng safety. Candidate lại timeout, tăng term và thử với độ trễ mới. Partition có thể làm hệ thống ngừng tiến triển, nhưng không tạo hai leader cùng term. Leader cũ bị cô lập vẫn có thể tưởng mình là leader; message term thấp của nó sẽ bị từ chối.

Replicate và commit log #

Sau election, leader append từng client command vào log cục bộ rồi gửi AppendEntries cho follower. Mỗi request nêu prevLogIndex và prevLogTerm, tương đương câu hỏi: “Lịch sử của bạn có khớp với tôi ngay trước các entry mới không?” Follower chỉ chấp nhận khi cặp giá trị đó khớp. Nếu gặp entry xung đột ở cùng index, follower xóa entry ấy cùng toàn bộ phần phía sau rồi append entry của leader. Leader lùi nextIndex và retry cho tới khi tìm được điểm chung giữa hai lịch sử.

Mô hình TypeScript dưới đây lược bỏ transport, batching, snapshot và chi tiết persistence, nhưng giữ các state transition quan trọng. Implementation thực tế phải ghi bền vững currentTerm, votedFor và log entry mới trước khi acknowledge.

import { randomElectionTimeout } from './timers.js';

type Role = 'follower' | 'candidate' | 'leader';

interface Entry<Command> {
  term: number;
  command: Command;
}

interface AppendEntries<Command> {
  term: number;
  leaderId: string;
  prevLogIndex: number;
  prevLogTerm: number;
  entries: ReadonlyArray<Entry<Command>>;
  leaderCommit: number;
}

interface AppendResult {
  term: number;
  success: boolean;
  matchIndex: number;
}

class RaftNode<Command> {
  role: Role = 'follower';
  currentTerm = 0;
  votedFor: string | undefined;
  log: Array<Entry<Command>> = [];
  commitIndex = -1;
  lastApplied = -1;
  electionDeadline = randomElectionTimeout();

  receiveAppend(request: AppendEntries<Command>): AppendResult {
    if (request.term < this.currentTerm) {
      return { term: this.currentTerm, success: false, matchIndex: -1 };
    }

    if (request.term > this.currentTerm) {
      this.currentTerm = request.term;
      this.votedFor = undefined;
    }
    this.role = 'follower';
    this.electionDeadline = randomElectionTimeout();

    if (request.prevLogIndex >= 0) {
      const previous = this.log[request.prevLogIndex];
      if (!previous || previous.term !== request.prevLogTerm) {
        return { term: this.currentTerm, success: false, matchIndex: -1 };
      }
    }

    let targetIndex = request.prevLogIndex + 1;
    for (const incoming of request.entries) {
      const local = this.log[targetIndex];
      if (local && local.term !== incoming.term) {
        this.log.splice(targetIndex);
      }
      if (!this.log[targetIndex]) {
        this.log.push(incoming);
      }
      targetIndex += 1;
    }

    const lastNewIndex = request.prevLogIndex + request.entries.length;
    this.commitIndex = Math.min(
      request.leaderCommit,
      Math.max(request.prevLogIndex, lastNewIndex),
    );

    return {
      term: this.currentTerm,
      success: true,
      matchIndex: lastNewIndex,
    };
  }

  applyCommitted(apply: (command: Command) => void): void {
    while (this.lastApplied < this.commitIndex) {
      this.lastApplied += 1;
      const entry = this.log[this.lastApplied];
      if (!entry) throw new Error('committed entry is missing');
      apply(entry.command);
    }
  }
}

Replication và commitment là hai chuyện khác nhau. Một entry có thể tồn tại trên nhiều server nhưng vẫn chưa committed. Leader chỉ tăng commitIndex tới index $k$ khi majority đã replicate qua $k$ và log[k].term === currentTerm. Khi một entry của term hiện tại được commit, mọi entry đứng trước cũng gián tiếp thành committed, kể cả entry leader kế thừa từ term cũ.

Điều kiện current-term ngăn một kịch bản overwrite tinh vi sau nhiều lần đổi leader. Nếu chỉ đếm replica cho entry term cũ, leader có thể công bố commit dù một candidate tương lai, được bầu hoàn toàn hợp lệ theo quy tắc log freshness, vẫn có khả năng thay entry ấy. Quy tắc bảo thủ này đóng lỗ hổng đó.

Giữ safety khi hệ thống gặp lỗi #

Raft chủ động chọn safety thay vì availability khi không có majority liên lạc được. Trong partition chia cluster năm node thành nhóm hai và ba, phía ba node có thể bầu leader và commit write; phía hai node thì không. Stale leader ở phía thiểu số có thể tạm nhận request nhưng không thể commit. Khi network hồi phục, AppendEntries từ leader hợp lệ có term cao hơn sẽ ghi đè suffix cũ chưa commit.

Một số failure scenario cần được lần theo cụ thể:

• Leader crash trước khi replicate: entry chưa commit ở máy đó có thể biến mất sau khi leader mới được bầu. Client phải retry.
• Leader crash sau commit nhưng trước khi reply: command vẫn tồn tại, nhưng client không biết điều đó. Deduplication giúp retry an toàn.
• Follower restart: nó nạp term, vote và log đã persist rồi catch up từ leader. Có thể dựng lại tiến độ commit và apply, nhưng metadata của snapshot cũng phải bền vững.
• RPC đến trễ hoặc bị lặp: check term và index vô hiệu hóa message stale; handler nên idempotent.
• Đồng hồ nhảy: correctness không phụ thuộc wall clock đồng bộ. Timing chỉ ảnh hưởng liveness, nên node bị pause lâu có thể kích hoạt election nhưng không làm thay đổi lịch sử đã commit.

Linearizable write đến từ quy tắc leader và commit khi client retry đúng cách. Read cần thêm một lớp bảo vệ: former leader đang bị partition không được phép trả state stale như dữ liệu hiện tại. Implementation thường dùng ReadIndex đã được quorum xác nhận, hoặc leader lease có giới hạn và dựa trên giả định rõ ràng về clock, trước khi phục vụ linearizable read. Đọc từ follower chỉ phù hợp nếu API công khai cho phép stale data.

State machine cũng phải deterministic. Nếu apply một entry mà đọc local clock, sinh số random không có seed hoặc phụ thuộc dữ liệu riêng của process, cùng một log vẫn có thể tạo ra state khác nhau. Hãy đặt timestamp, identifier hay kết quả bất định đã chọn vào replicated command.

Đổi membership và nén lịch sử #

Log của hệ thống chạy lâu không thể tăng vô hạn. Server định kỳ serialize state machine tại một included index và term, sau đó loại bỏ log entry cũ. Nếu follower tụt quá xa, leader gửi InstallSnapshot thay vì replay toàn bộ lịch sử. Cài snapshot phải atomic: crash chỉ được để lại state cũ hợp lệ hoặc state mới hợp lệ, không phải nửa nọ nửa kia. Checksum và format có version giúp phát hiện corruption cũng như xử lý upgrade.

Đổi voter nguy hiểm hơn thêm một địa chỉ. Chuyển thẳng từ $C_{old}$ sang $C_{new}$ có thể tạo hai majority không giao nhau. Joint consensus trước hết commit cấu hình yêu cầu majority của cả tập cũ lẫn mới, rồi mới commit cấu hình mới. Biến thể đổi từng server cũng phải bảo đảm quorum luôn giao nhau khi chuyển tiếp.

Trong vận hành, membership change nên được serialize, có observability và đủ chậm để voter mới catch up trước khi ảnh hưởng availability. Node thường xuyên lỗi cần được sửa hoặc thay thế; tự động loại member khi network partition có thể biến outage tạm thời thành split-brain cấu hình vĩnh viễn.

Kiểm thử giao thức và hiểu giới hạn #

Unit test happy path gần như chưa chạm vào bài toán consensus. Test có giá trị phải điều khiển time và transport: pause node, đảo thứ tự RPC, duplicate response, làm mất acknowledgement, crash ngay trước hoặc sau durable write, rồi restart từ bytes đã persist. Deterministic simulator có thể sinh hàng nghìn schedule và kiểm tra invariant sau từng event:

• mỗi term có nhiều nhất một leader;
• committed entry tại một index không bao giờ đổi term hoặc command;
• server apply entry đúng thứ tự index và không bao giờ apply hai lần;
• commitIndex và lastApplied không bao giờ giảm;
• mọi applied prefix giữa các server đều giống nhau;
• khi thiếu quorum, không entry mới nào trở thành committed.

Property-based generation và model checking hiệu quả vì bug nặng thường cần một thứ tự event khó hình dung. Test kiểu Jepsen bổ sung bằng history quan sát bên ngoài khi process bị pause, disk fault và partition. Metric nên có term change, election duration, replication lag, commit latency, snapshot progress và quorum health; log cần chứa term, index, peer và kết quả RPC.

Raft vẫn có giới hạn. Leader là bottleneck sắp thứ tự write. Cluster lớn hoặc trải rộng địa lý phải trả quorum latency và dễ đổi leader. Raft chuẩn không chịu được member độc hại, không sửa được state machine bất định và không cung cấp exactly-once cho side effect bên ngoài replicated state. Disk chậm có thể làm election mất ổn định vì persistence nằm trên critical path. Implementation trưởng thành thường batch entry, pipeline replication, áp dụng backpressure, pre-vote trước khi làm gián đoạn term đang khỏe và transfer leadership trước bảo trì.

Tổng kết #

Raft hoạt động vì các mảnh ghép củng cố lẫn nhau. Term loại bỏ authority cũ. Election timeout ngẫu nhiên thường tạo ra một candidate, còn log freshness rule ngăn candidate thiếu dữ liệu chiến thắng. AppendEntries sửa divergent suffix. Majority replication kết hợp current-term commit rule biến entry tạm thời thành quyết định bền vững. Cuối cùng, deterministic application làm mọi state machine hội tụ.

Khi implement hoặc vận hành Raft, hãy tách safety khỏi liveness. Safety nghĩa là lịch sử đã commit không bao giờ đổi bất kể message trễ bao lâu. Liveness nghĩa là cluster cuối cùng tiếp tục tiến triển khi một majority ổn định có thể liên lạc. Timeout, pre-vote, batching và tuning cải thiện liveness; durable state, quorum intersection, log matching và commit rule bảo vệ safety. Giao thức trở nên dễ suy luận hơn nhiều khi mọi optimization đều phải giữ các invariant đó, thay vì chỉ chạy qua được demo trong điều kiện bình thường.