Thuật toán đồng thuận phân tán (Distributed Consensus) — Paxos và Raft

1. Tổng quan

A. Định nghĩa

Đồng thuận phân tán (Distributed Consensus) là thủ tục mang tính thuật toán bảo đảm rằng nhiều nút kết nối qua mạng, ngay cả trong môi trường có sự cố·độ trễ·mất thông điệp ở một số nút, vẫn đạt tới cùng một quyết định về một giá trị (hoặc thứ tự các lệnh). Paxos và Raft là các thuật toán tiêu biểu đạt được đồng thuận này dựa trên đa số (Quorum).

Thuật toán đồng thuận là công nghệ nền tảng cốt lõi giúp hệ thống phân tán hoạt động "như thể nhiều máy tính là một máy tính đáng tin cậy". Trong máy trạng thái được sao chép (Replicated State Machine), nếu mỗi nút áp dụng cùng các lệnh theo cùng một thứ tự thì trạng thái kết quả luôn khớp nhau, và chính "cùng một thứ tự" đó được xác lập bằng đồng thuận ngay cả trong tình huống sự cố. Độ tin cậy của hạ tầng dữ liệu phân tán hiện đại như etcd của Kubernetes, Chubby/Spanner của Google, Apache ZooKeeper, CockroachDB·TiDB đều đứng trên thuật toán đồng thuận.

B. Bối cảnh ra đời và sự cần thiết

Một máy chủ đơn khi gặp sự cố thì dịch vụ bị gián đoạn, nên để tăng tính sẵn sàng, dữ liệu được sao chép (replication) sang nhiều nút. Nhưng khi có nhiều bản sao, lập tức nảy sinh vấn đề "giá trị của bản sao nào là đúng", "phản ánh các yêu cầu ghi theo thứ tự nào". Mạng làm trễ·đảo thứ tự·mất thông điệp, nút chết rồi sống lại vào thời điểm bất kỳ, và quản trị viên có thể chọn sai leader mới. Trong môi trường mà lỗi cục bộ (partial failure) luôn hiện diện như vậy, để giữ tính nhất quán dữ liệu cần một giao thức chặt chẽ hơn đa số đơn thuần.

Về lý thuyết, định lý bất khả FLP (Fischer-Lynch-Paterson, 1985) đã chứng minh rằng "trong mạng hoàn toàn bất đồng bộ, nếu chỉ cần một nút có thể chết, thì đồng thuận tất định vừa luôn kết thúc (termination) vừa an toàn (safety) là không thể". Các thuật toán đồng thuận thực tế đưa vào timeout (giả định đồng bộ một phần) và tính ngẫu nhiên/bầu chọn leader để vòng qua giới hạn này và bảo đảm tính sẵn sàng thực dụng. Nói cách khác, mục tiêu thiết kế của thuật toán đồng thuận không phải "sự hoàn hảo lý thuyết" mà là tìm điểm cân bằng tuyệt đối không vi phạm tính an toàn (never wrong) đồng thời bảo đảm tiến triển khi mạng ổn định (eventually makes progress).

Paxos (Leslie Lamport, 1998) là thuật toán đầu tiên giải chặt chẽ bài toán này nhưng mang tiếng xấu là "khó hiểu (notoriously difficult)". Raft (Diego Ongaro·John Ousterhout, 2014) giữ nguyên tính an toàn tương đương nhưng lấy khả năng dễ hiểu (understandability) làm mục tiêu thiết kế hàng đầu, tách rõ bầu chọn leader·sao chép log·tính an toàn, và ngày nay đã trở thành tiêu chuẩn của ngành.

2. Các thuộc tính đồng thuận phải bảo đảm và cấu trúc tổng thể

Thuật toán đồng thuận phải thỏa mãn bốn thuộc tính sau. Đồng thuận (Agreement): mọi nút bình thường quyết định cùng một giá trị. Tính hợp lệ (Validity): giá trị được quyết định phải là giá trị mà một nút nào đó thực sự đã đề xuất. Tính toàn vẹn (Integrity): mỗi nút chỉ quyết định tối đa một lần. Tính kết thúc (Termination): nút bình thường cuối cùng nhất định sẽ quyết định một giá trị. Ba thuộc tính đầu thuộc về tính an toàn (Safety), thuộc tính cuối thuộc về tính sống/tiến triển (Liveness); các thuật toán thực tế đặt tính an toàn làm nguyên tắc tuyệt đối và cung cấp tính sống theo kiểu nỗ lực tốt nhất.

Cơ chế cốt lõi là nguyên lý quorum (túc số). Gọi tổng số nút là N, phải có sự đồng ý của đa số ⌊N/2⌋+1 nút thì quyết định mới được xác lập. Để hai quyết định khác nhau mỗi cái đều đạt đa số thì ít nhất một nút phải thuộc cả hai (tồn tại giao), và nút chồng lấn này ghi nhớ "quyết định trước" và buộc quyết định mới phải tôn trọng nó, qua đó chặn tận gốc chia rẽ não (split-brain). Vì thế N=5 thì chịu được tới 2 nút sự cố (vẫn còn đa số 3), và nói chung để chịu F sự cố cần N=2F+1 nút.

flowchart TB
    subgraph Client["Client"]
      REQ["Yêu cầu ghi (lệnh)"]
    end
    REQ --> L["Nút leader (Leader)"]
    subgraph Cluster["Cluster đồng thuận (N=5, đa số=3)"]
      L -->|"Sao chép log (AppendEntries)"| F1["Follower 1"]
      L -->|"Sao chép log"| F2["Follower 2"]
      L -->|"Sao chép log"| F3["Follower 3"]
      L -->|"Sao chép log"| F4["Follower 4"]
    end
    F1 -. "ACK" .-> L
    F2 -. "ACK" .-> L
    L -->|"Commit khi đủ ACK đa số"| SM["Áp dụng vào máy trạng thái sao chép"]
    SM --> RESP["Phản hồi client"]

Trong cấu trúc trên, leader biến lệnh của client thành mục log rồi sao chép cho các follower, và ngay khi thu đủ ACK của đa số, mục đó được xác lập là đã commit rồi áp dụng vào máy trạng thái. Mục đã commit không bao giờ bị đảo ngược, nên sau này dù leader nào được bầu mới cũng nhất định chứa các lệnh đã commit. Đây chính là thực chất của tính an toàn "một khi đã quyết thì giữ mãi mãi".

3. Paxos — Nguyên mẫu của đồng thuận

Paxos chia vai trò thành bên đề xuất (Proposer), bên chấp nhận (Acceptor), bên học (Learner). Bên đề xuất đề xuất giá trị, bên chấp nhận tạo thành quorum đa số để chấp nhận giá trị, còn bên học được lan truyền giá trị đã xác lập. Basic Paxos, quyết định một giá trị duy nhất, hoạt động theo 2 pha (Two-Phase).

Ở pha 1 Prepare/Promise, bên đề xuất chọn số đề xuất n tăng đơn điệu toàn cục và gửi Prepare(n) cho đa số bên chấp nhận. Bên chấp nhận, nếu n lớn hơn số mình đã thấy, sẽ hồi đáp lời hứa (Promise) "từ nay sẽ bỏ qua các đề xuất nhỏ hơn n", kèm theo giá trị đã chấp nhận nếu có. Ở pha 2 Accept/Accepted, khi nhận được lời hứa của đa số, bên đề xuất chọn giá trị có số hiệu cao nhất trong các giá trị được hồi đáp (nếu không có thì dùng giá trị của mình) và gửi Accept(n, v); khi đa số bên chấp nhận chấp nhận thì v được xác lập. Quy tắc tôn trọng giá trị cũ được hồi đáp này là cơ chế cốt lõi của tính an toàn, bảo đảm "không ghi đè lên giá trị có thể đã được quyết định".

Basic Paxos chỉ quyết định một giá trị, nên để lấp đầy log các lệnh liên tiếp thì mở rộng thành Multi-Paxos, chạy một instance Paxos cho mỗi slot log. Multi-Paxos bầu một leader ổn định để bỏ qua pha 1 và chỉ lặp lại pha 2, nhờ đó trong giai đoạn bình thường xác lập lệnh với 1 vòng thông điệp (1 RTT) và nâng cao hiệu năng. Tuy nhiên, bài báo Paxos không đặc tả các yếu tố thực tiễn như bầu chọn leader·thay đổi thành viên·nén log, để lại khó khăn thực tiễn là mỗi bản triển khai diễn giải khác nhau và khó kiểm chứng.

4. Raft — Đồng thuận dễ hiểu

Raft phân rã bài toán đồng thuận thành ba bài toán con ① bầu chọn leader (Leader Election) ② sao chép log (Log Replication) ③ tính an toàn (Safety) để có thể hiểu từng phần một cách độc lập. Mọi nút mang một trong các trạng thái Follower·Candidate·Leader, và thời gian được phân đoạn logic bằng số nhiệm kỳ (Term) tăng đơn điệu. Nhiệm kỳ là một dạng đồng hồ logic, được dùng để nhận diện·bác bỏ ngay các lệnh của leader cũ.

Bầu chọn leader được kích hoạt bởi timeout heartbeat. Nếu follower không nhận được heartbeat của leader trong một khoảng thời gian (election timeout, thường ngẫu nhiên 150~300ms), nó chuyển thành candidate, tăng nhiệm kỳ của mình và phát RequestVote. Mỗi nút chỉ bỏ một phiếu mỗi nhiệm kỳ, nên chỉ candidate đạt đa số phiếu mới trở thành leader. Bí quyết tiến triển của Raft là ngẫu nhiên hóa timeout để né tránh theo xác suất việc chia phiếu (split vote) khi nhiều candidate cùng ra ứng cử.

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate : "Timeout bầu cử (không nhận heartbeat)"
    Candidate --> Candidate : "Bầu lại khi chia phiếu (không đạt đa số)"
    Candidate --> Leader : "Đạt đa số phiếu"
    Candidate --> Follower : "Phát hiện nhiệm kỳ (Term) cao hơn"
    Leader --> Follower : "Xác nhận leader có nhiệm kỳ cao hơn"
    Leader --> Leader : "Gửi heartbeat định kỳ"

Sao chép log là cách leader thêm lệnh của client vào log rồi lan truyền cho follower qua RPC AppendEntries, và commit khi đa số đã lưu. Raft cưỡng chế thuộc tính khớp log (Log Matching), bảo đảm các mục có cùng chỉ số·nhiệm kỳ thì nội dung giống nhau và toàn bộ log trước đó cũng giống nhau. Nếu log của follower không khớp với leader, leader cưỡng chế ghi đè bằng log của mình để khôi phục tính nhất quán. Hơn nữa, bằng ràng buộc bầu chọn (Election Restriction), chỉ candidate có log commit mới nhất mới có thể trở thành leader, bảo đảm tính an toàn để lệnh đã commit không bao giờ bị mất. Thay đổi thành viên được xử lý không gián đoạn bằng đồng thuận chung (Joint Consensus) hoặc cách thay đổi từng nút một.

5. So sánh Paxos và Raft, và ứng dụng thực tiễn

Hai thuật toán cung cấp tính an toàn như nhau (quorum đa số·bất biến commit), nhưng có khác biệt rõ rệt về triết lý thiết kế và mức độ dễ dùng trong thực tế. Paxos có tính tổng quát hoạt động được cả khi không có leader và sự thanh lịch lý thuyết nhưng thiếu đặc tả thực tiễn, còn Raft đơn giản hóa luồng xoay quanh leader mạnh (Strong Leader) nên dễ triển khai·gỡ lỗi·giảng dạy. "Vì sao có khác biệt đó" bắt nguồn từ khác biệt về mục tiêu thiết kế — Paxos ưu tiên chứng minh tính đúng đắn dưới giả định tối thiểu, còn Raft ưu tiên sự rõ ràng để kỹ sư có thể thực sự triển khai·vận hành.

Ví dụ ứng dụng cụ thể, Kubernetes lưu mọi trạng thái của cluster (đối tượng·cấu hình) vào etcd, và etcd sao chép dữ liệu sang 3~5 nút bằng Raft. Với cấu hình 5 nút, dù 2 nút sự cố, nếu đa số 3 nút còn sống thì API server vẫn tiếp tục đọc·ghi bình thường. Đây cũng là lý do khuyến nghị thực tiễn là số nút lẻ (3·5·7) — số nút chẵn không tăng được số sự cố chịu đựng mà chỉ nâng ngưỡng đa số nên lại kém hiệu quả (ví dụ: 4 nút cũng chỉ chịu được tới 2 nút như 5 nút). Ngoài ra, bố trí nút trải qua các vùng (AZ) làm tăng tính sẵn sàng nhưng độ trễ vòng đồng thuận (latency) lớn lên, nên thiết kế bố trí cân nhắc tính nhất quán·tính sẵn sàng·độ trễ trở thành bài toán cốt lõi.

Mặt khác, họ PBFT·Tendermint của blockchain là đồng thuận BFT chịu được cả lỗi Byzantine, khi nút không chỉ hỏng đơn thuần mà gửi thông điệp giả một cách ác ý, và cần 3F+1 nút để chịu được F nút phản bội. Khác với Paxos·Raft giả định bên trong miền tin cậy (Crash Fault Tolerant), trong môi trường mở·không tin cậy cần đồng thuận BFT đắt đỏ hơn — đây là ranh giới phân định quan trọng.

6. Các điểm cần lưu ý và hàm ý

Từ góc nhìn Kỹ sư chuyên nghiệp (Professional Engineer), đồng thuận phân tán vượt ra ngoài kiến thức thuật toán đơn thuần để trở thành nền móng của kiến trúc độ tin cậy hệ thống, nên cần xem xét tổng hợp các điểm sau.

• Đánh đổi giữa tính nhất quán và độ trễ: Đồng thuận cần một vòng đi về với đa số cho mỗi lần ghi nên độ trễ tăng. Nên thiết kế tách cấp độ nhất quán: áp dụng đồng thuận cho metadata·cấu hình·thông tin leader cần nhất quán mạnh, và nhất quán cuối cùng (kiểu Dynamo) cho dữ liệu dung lượng lớn·tần suất cao. Điều này liên kết với việc ra quyết định theo góc nhìn PACELC.
• Chiến lược số nút·bố trí: Dùng số nút lẻ (3·5·7) để cân đối khả năng chịu lỗi và hiệu quả quorum, và khi bố trí đa AZ/region thì xem xét định lượng sự cân bằng giữa độ trễ đồng thuận và tính sẵn sàng. Càng nhiều nút thì khả năng chịu lỗi càng tăng nhưng độ trễ ghi·chi phí mạng cũng tăng.
• Kỹ thuật tối ưu hiệu năng: Bù đắp chi phí đồng thuận thông qua gom lô log (batching)·pipelining, đọc cục bộ dựa trên lease của leader, snapshot·nén log (log compaction), đọc từ follower để phân tán tải đọc v.v.
• Yêu cầu vận hành·quan sát: Để đối phó với bầu chọn leader dao động liên tục (flapping), lệch đồng hồ (clock skew), phân vùng mạng, cần quan sát (Observability) nhiệm kỳ·chỉ số commit·trạng thái quorum, và nhất định duy trì cấu hình dựa trên đa số để ngăn split-brain.
• Chọn mô hình mối đe dọa: Nếu bên trong miền tin cậy thì Crash-Fault (Paxos/Raft), nếu không tin cậy·mở thì Byzantine-Fault (PBFT/PoS) — phân biệt rõ mô hình mối đe dọa để tránh cơ chế an toàn thừa hoặc thiếu.
• Triển vọng công nghệ: Các biến thể giảm độ trễ như EPaxos·Flexible Paxos, đa leader·đọc dựa trên lease tận dụng tính cục bộ, và BFT mở rộng dựa trên bằng chứng cổ phần (PoS) đang phát triển, nên năng lực chọn phương thức đồng thuận phù hợp với tính nhất quán yêu cầu·quy mô·giả định tin cậy ngày càng quan trọng.

Tóm tắt một câu: Đồng thuận phân tán (Paxos·Raft) là kỹ thuật giúp nhiều nút đạt cùng một thứ tự lệnh bằng quorum đa số và sao chép log trong môi trường lỗi cục bộ, là nền tảng giữ tính an toàn làm nguyên tắc tuyệt đối và cân nhắc tính sẵn sàng·độ trễ để hệ thống phân tán hoạt động như một hệ thống tin cậy duy nhất.