Ordering Guarantees & Consensus — Total Order, 2PC, Raft và ZooKeeper (DDIA) | Blog

Mở đầu

Ảnh: Brett Sayles — Pexels

Trong distributed systems, có một câu hỏi tưởng chừng đơn giản nhưng lại vô cùng khó trả lời: sự kiện nào xảy ra trước?

Khi bạn có nhiều máy chủ, nhiều request, và nhiều dữ liệu được ghi đồng thời, việc xác định thứ tự giữa các sự kiện trở nên cực kỳ phức tạp. Không giống như chương trình chạy trên một máy đơn — nơi mọi thứ có một thứ tự rõ ràng — trong distributed systems, mỗi node đều có đồng hồ riêng, network có thể trễ bất kỳ lúc nào, và các node có thể crash.

Đây là lúc ordering guarantees và consensus xuất hiện. Hai khái niệm này là nền tảng cho hầu hết các cơ chế đồng bộ trong distributed systems — từ database replication cho tới distributed coordination (ZooKeeper, etcd).

Total Order vs Partial Order — Thứ tự toàn phần và thứ tự bộ phận

Ảnh: Ketut Subiyanto — Pexels

Trước khi nói về consensus, cần hiểu hai khái niệm cơ bản về thứ tự:

Total order (thứ tự toàn phần): Mọi phần tử đều có thể so sánh được với nhau. Ví dụ: các số nguyên — bạn luôn nói được 5 < 7 hay 10 > 3. Trong distributed systems, nếu mọi operation đều có thể xác định operation nào xảy ra trước, operation nào xảy ra sau — đó là total order.
Partial order (thứ tự bộ phận): Một số cặp phần tử có thể so sánh, một số cặp thì không. Ví dụ: các tập hợp — {a, b} và {b, c} có thể so sánh một phần, nhưng {a, b} và {c, d} thì không (không tập nào là tập con của tập nào). Trong distributed systems, nếu hai operation không liên quan với nhau (concurrent), ta không thể nói cái nào xảy ra trước.

DDIA giải thích rằng các hệ thống khác nhau chọn mức độ ordering khác nhau. Hệ thống linearizable đòi hỏi total order: mọi operation đều có một thứ tự tuyến tính rõ ràng. Trong khi đó, các hệ thống với causal consistency chỉ cần partial order — những operation có quan hệ nhân quả với nhau mới cần thứ tự, còn những operation concurrent thì không.

Total Order Broadcast — Cơ chế cốt lõi cho consensus

Khi một hệ thống quyết định dùng total order, nó cần một cơ chế để đảm bảo mọi node nhận được các message theo cùng một thứ tự. Đây gọi là total order broadcast (còn gọi là atomic broadcast).

Total order broadcast có hai tính chất quan trọng:

Reliable delivery: Mọi node đều nhận được message — nếu một node nhận được message, tất cả node khác cuối cùng cũng nhận được.
Totally ordered delivery: Mọi node đều nhận các message theo cùng một thứ tự.

Tại sao total order broadcast lại quan trọng? Bởi vì nó là nền tảng cho consensus — một trong những bài toán khó nhất trong distributed systems. Nếu bạn có thể đảm bảo mọi node thấy cùng một dãy thứ tự, bạn có thể xây dựng consensus trên nó.

Cụ thể: total order broadcast tương đương với consensus theo hướng hai chiều. Nếu bạn có total order broadcast, bạn có thể giải bài toán consensus. Và nếu bạn có consensus, bạn có thể xây dựng total order broadcast. Đây là một kết quả quan trọng trong lý thuyết distributed systems.

2PC (Two-Phase Commit) — Consensus với giới hạn

Two-Phase Commit (2PC) là thuật toán cổ điển nhất để đạt được sự đồng thuận giữa nhiều node. Như tên gọi, nó có hai phase:

Phase 1 — Prepare: Coordinator gửi request "prepare" đến tất cả participants. Mỗi participant trả lời "yes" (sẵn sàng commit) hoặc "no" (từ chối). Nếu participant nói "yes", nó cam kết sẽ commit — dù có chuyện gì xảy ra — trừ khi coordinator bảo abort.
Phase 2 — Commit/Abort: Nếu tất cả đều nói "yes", coordinator gửi "commit" cho tất cả. Nếu có bất kỳ "no" nào, coordinator gửi "abort".

Tuy nhiên, 2PC có một vấn đề lớn: nó là một blocking protocol. Nếu coordinator bị crash sau khi nhận "yes" từ participants nhưng trước khi gửi "commit", các participants sẽ bị kẹt — không biết nên commit hay abort. Họ phải chờ coordinator recover. Đây gọi là vấn đề "in doubt" hay "uncertain" transaction.

DDIA so sánh 2PC với một cuộc hẹn mà người tổ chức đã xác nhận với từng người tham gia nhưng rồi biến mất — mọi người đều chờ, không ai dám đi đâu vì sợ cuộc hẹn vẫn diễn ra.

Raft — Consensus Algorithm hiện đại

Ảnh: panumas nikhomkhai — Pexels

Raft là một consensus algorithm được thiết kế với mục tiêu dễ hiểu (so với Paxos — thuật toán consensus nổi tiếng nhưng cực kỳ khó hiểu và implement đúng).

Raft hoạt động dựa trên ý tưởng về leader: một node được bầu làm leader, và leader chịu trách nhiệm quản lý replicated log. Các bước cơ bản:

Leader election: Các node bầu ra một leader thông qua cơ chế bầu cử. Mỗi node có một election timeout ngẫu nhiên. Nếu không nhận được heartbeat từ leader trong timeout đó, nó tự ứng cử làm leader cho term mới.
Log replication: Leader nhận request từ client, append nó vào log, rồi gửi tới tất cả followers. Chỉ khi majority nodes xác nhận ghi thành công, leader mới commit entry đó.
Safety: Raft đảm bảo rằng nếu một entry đã được commit ở một term, nó sẽ xuất hiện trong mọi log của leader ở các term sau. Điều này được đảm bảo thông qua quy tắc: chỉ leader có log đầy đủ nhất mới có thể thắng cử.

Raft sử dụng majority (đa số) để đưa ra quyết định. Điều này có nghĩa: để tồn tại được N node crash trong cluster, bạn cần 2N + 1 node. Ví dụ: cluster 3 node chịu được 1 node crash, cluster 5 node chịu được 2 node crash.

ZooKeeper và Distributed Coordination Services

ZooKeeper là một distributed coordination service — một hệ thống được xây dựng dựa trên consensus (cụ thể là Zab — ZooKeeper Atomic Broadcast, một giao thức tương tự Raft nhưng ra đời sớm hơn).

ZooKeeper cung cấp cho developers một số building blocks hữu ích:

Linearizable writes qua một ZooKeeper ensemble — đảm bảo total order trên write operations
Ephemeral nodes — tự động biến mất khi client mất kết nối, dùng để phát hiện failure
Sequential znodes — tự động tạo tên duy nhất có thứ tự, dùng để implement distributed lock, leader election, membership service
Watch — cơ chế notification cho phép client biết khi dữ liệu thay đổi

DDIA chỉ ra rằng ZooKether không phải là cơ sở dữ liệu — bạn không nên lưu dữ liệu ứng dụng vào ZooKeeper. Nó là công cụ để phối hợp giữa các node: biết ai là leader, node nào còn sống, lock distributed ở đâu.

Các hệ thống như Kafka (dùng ZooKeeper/etcd để quản lý metadata và leader election), HBase, và nhiều distributed database khác đều dựa vào các coordination service kiểu này.

Comparison: 2PC vs Raft vs ZooKeeper

Bảng sau giúp so sánh ba approach:

2PC: Blocking protocol, coordinator là single point of failure, không chịu được crash. Dùng trong distributed transactions (XA transactions).
Raft: Non-blocking, chịu được minority failures. Cung cấp total order broadcast + consensus. Dùng trong etcd, Consul, MongoDB replica sets.
ZooKeeper (Zab): Non-blocking, tương tự Raft. Cung cấp coordination primitives (lock, election, membership). Dùng trong Kafka, HBase, Apache Curator.

Key Takeaways

Total order ≠ Partial order. Hệ thống linearizable cần total order; causal consistency chỉ cần partial order. Sự khác biệt này ảnh hưởng lớn đến performance và khả năng chịu lỗi.
Total order broadcast ≈ Consensus. Hai bài toán này tương đương nhau — giải được bài này là giải được bài kia.
2PC bị blocking. Khi coordinator crash, participants bị kẹt không biết commit hay abort. Đây là lý do 2PC không phù hợp cho hệ thống cần high availability.
Raft dùng leader + majority. Majority-based approach cho phép hệ thống tiếp tục hoạt động khi minority nodes bị lỗi.
ZooKeeper không phải database. Dùng để coordination — lưu metadata, không lưu dữ liệu ứng dụng.

Glossary

Total order — thứ tự toàn phần: mọi cặp phần tử đều có thể so sánh
Partial order — thứ tự bộ phận: chỉ một số cặp phần tử có thể so sánh
Total order broadcast — cơ chế đảm bảo mọi node nhận message theo cùng thứ tự
Consensus — các node thống nhất một giá trị/decision dù có failure
2PC (Two-Phase Commit) — thuật toán commit 2 pha, blocking coordinator
Raft — consensus algorithm dùng leader election + log replication
ZooKeeper — distributed coordination service (lock, election, membership)
Zab — ZooKeeper Atomic Broadcast, giao thức consensus của ZooKeeper
Leader election — cơ chế bầu leader trong cluster
Majority (quorum) — hơn 50% nodes, cần thiết cho quyết định consensus

Kết

Ordering guarantees và consensus là hai trong số những khái niệm nền tảng nhất của distributed systems. Từ những hệ thống database đơn giản đến các distributed coordination service phức tạp, tất cả đều xoay quanh câu hỏi: làm sao để các node thống nhất với nhau?

DDIA trình bày vấn đề này một cách có hệ thống: bắt đầu từ total order broadcast, qua 2PC, đến Raft và ZooKeeper. Mỗi approach đều có trade-off riêng — không có giải pháp nào hoàn hảo. Hiểu được những trade-off này giúp chọn đúng công cụ cho từng bài toán.

Bài tiếp theo sẽ nói về Distributed Transactions & Exactly-Once Processing — một chủ đề liên quan mật thiết với consensus và ordering.