DDIA · Martin Kleppmann · Chương 9DDIA · Martin Kleppmann · Chương 9DDIA · Martin Kleppmann · Chapter 9
DDIA · Chương 9 · Nhất quán & đồng thuậnDDIA · Chương 9 · Nhất quán & đồng thuậnDDIA · Chapter 9 · Consistency and Consensus

Làm sao nhiều máy cùng chốt một sự thậtNhiều máy mà nói cùng một chuyệnHow many machines agree on one truth

Chương 8 để lại một bãi đổ nát: mạng trễ và mất gói, đồng hồ nói dối, tiến trình bị treo giữa chừng, và không nút nào biết chắc nút khác còn sống hay đã chết. Chương 9 hỏi câu tiếp theo — với nền móng bất định như thế, ta vẫn dựng được những trừu tượng có bảo đảm mạnh hay không?1 Câu trả lời của Kleppmann là có, nhưng phải trả giá; và đỉnh của các trừu tượng ấy mang một cái tên: consensus — làm cho mọi nút cùng quyết định một điều, và không nút nào rút lại được1.

Ở chương trước, ta đã thấy máy móc trong hệ phân tán hay "nói dối": thư đi lạc, đồng hồ chạy sai, có máy im lặng mà chẳng biết nó ngủ hay chết. Vậy nhiều máy như thế có thể cùng đồng ý một chuyện không? Chương này trả lời: được, nhưng phải chịu chậm hơn và phức tạp hơn. Nhớ nhé: muốn chắc chắn thì phải chờ nhau.

Chapter 8 left behind a wreck: networks that delay and drop packets, clocks that lie, processes paused mid-step, and no node ever certain whether another is alive or dead. Chapter 9 asks the next question — on foundations that unreliable, can we still build abstractions with strong guarantees?1 Kleppmann's answer is yes, but at a price; and the summit of those abstractions has a name: consensus — getting all nodes to decide one thing, irrevocably1.

∴
Luận đề của chương Điều quan trọng nhất The thesis of the chapter

Có cả một phổ bảo đảm nhất quán, và ta nên chọn đúng nấc thay vì mặc định lấy nấc mạnh nhất. Ở đầu mạnh là linearizability — hệ trông như chỉ có một bản sao duy nhất — thứ mà một số ít việc (bầu leader, khóa, ràng buộc duy nhất) thật sự cần, còn phần lớn việc thì không, vì nó tốn đồng bộ và bị giới hạn bởi độ trễ mạng13. Ở giữa là các bảo đảm về thứ tự: nhân quả cho ta một thứ tự bộ phận, còn total order broadcast cho ta một thứ tự toàn phần — và thứ tự toàn phần ấy, hóa ra, tương đương với bài toán đồng thuận23.

Không phải hệ nào cũng cần "chắc chắn tuyệt đối". Có nhiều mức "đúng" khác nhau, và mức mạnh nhất thì chậm và đắt. Vài việc buộc phải dùng mức mạnh: chọn ra một người chỉ huy, giữ một cái khóa, hay bảo đảm hai người không cùng lấy một tên. Nhớ nhé: chọn mức vừa đủ cho việc của mình, đừng lúc nào cũng chọn mức đắt nhất.

There is a whole spectrum of consistency guarantees, and we should pick the right rung rather than default to the strongest. At the strong end sits linearizability — making a system look as if there were only a single copy of the data — which a few jobs (leader election, locks, uniqueness constraints) genuinely need and most do not, because it costs coordination and is bounded by network delay13. In between are ordering guarantees: causality gives a partial order, while total order broadcast gives a total one — and that total order turns out to be equivalent to the consensus problem23.

Trục 1 · LinearizabilityAxis 1 · Linearizability

Ảo giác “chỉ có một bản sao”The illusion of a single copy

Khi dữ liệu được nhân bản, người dùng có thể thấy những phiên bản khác nhau tùy họ hỏi bản sao nào. Linearizability — khả tuyến tính hóa, còn gọi là atomic consistency — xóa bỏ điều đó bằng một lời hứa duy nhất: làm cho hệ trông như thể chỉ tồn tại một bản sao dữ liệu duy nhất, và mọi thao tác trên nó là tức thời5. Kleppmann phát biểu ý đó một cách trực giác: nếu thao tác B bắt đầu sau khi thao tác A đã hoàn tất, thì B phải thấy hệ ở đúng trạng thái A để lại, hoặc mới hơn9. Vì thế nó là một bảo đảm về tính mới (recency guarantee), không phải một bảo đảm về giao dịch.

Tưởng tượng cả lớp cùng ghi điểm vào nhiều cuốn sổ đặt ở nhiều phòng. Hỏi phòng này ra một con số, hỏi phòng kia ra con số khác — vì có sổ chưa kịp chép. "Khả tuyến tính hóa" nghĩa là: dù thật ra có nhiều cuốn sổ, ai hỏi ở đâu cũng thấy y như chỉ có một cuốn sổ duy nhất, và cuốn đó luôn mới nhất. Nhớ nhé: nhiều sổ mà xem như một sổ.

When data is replicated, users may see different versions depending on which replica they ask. Linearizability — also called atomic consistency — abolishes that with a single promise: make the system look as though only one copy of the data exists, and every operation on it is instantaneous5. Kleppmann states it intuitively: if operation B starts after operation A has completed, then B must see the system in the state A left it in, or a newer one9. It is therefore a recency guarantee, not a guarantee about transactions.

Linearizability — a recency guarantee on a single object

Định nghĩa hình thức thuộc về Herlihy & Wing (1990): mỗi thao tác đồng thời tỏ ra như diễn ra tức thời tại một thời điểm nào đó nằm giữa lúc nó được gọi và lúc nó trả về5. Hệ quả rất thực dụng: một khi giá trị mới đã được đọc thấy, mọi lần đọc sau đó không được quay lại giá trị cũ — không có chuyện "lùi thời gian".

Nói gọn: mỗi việc coi như xảy ra trong một khoảnh khắc, và một khi ai đó đã thấy giá trị mới thì không ai được thấy lại giá trị cũ nữa. Nhớ nhé: đã mới rồi thì không lùi về cũ.

The formal definition belongs to Herlihy & Wing (1990): each concurrent operation appears to take effect instantaneously at some point between its invocation and its response5. The practical consequence: once a newer value has been read, no later read may go back to the older one — no time travel.

Điểm tinh tế mà Kleppmann nhấn: khả tuyến tính hóa là một tính chất có thể ghép (composable, hay "local") — nếu từng đối tượng trong hệ đều khả tuyến tính hóa thì toàn hệ cũng vậy6. Đây chính là chỗ nó khác hẳn khả tuần tự hóa, vốn không ghép được. Tính ghép được là lý do khả tuyến tính hóa là bảo đảm tự nhiên cho những "nguyên thủy" nhỏ như thanh ghi, khóa, bộ đếm — và cũng là lý do nó đắt: mỗi đối tượng đều phải trả phí đồng bộ riêng của nó.

Một bản sao Dù có bao nhiêu bản sao vật lý, hệ phải trông như chỉ có một bản duy nhất.
Tính mới, không phải cô lập Nó nói về việc đọc được giá trị mới nhất, không nói gì về gộp nhiều thao tác thành giao dịch.
Thời gian thực Thứ tự phải khớp với thời gian tường: xong trước thì phải được thấy trước.
Như một cuốn sổ Nhiều sổ nhưng ai xem cũng thấy giống hệt nhau.
Luôn mới nhất Đã thấy số mới thì không được thấy lại số cũ.
Theo đồng hồ thật Việc xong trước thì phải được nhìn thấy trước.
A single copy However many physical replicas exist, the system must look like just one.
Recency, not isolation It is about reading the latest value, and says nothing about grouping operations into transactions.
Real time The order must match wall-clock order: finished earlier must be visible earlier.
  1. The recency guarantee, precisely

    Không lùi về giá trị cũNo going back to a stale value

    Khả tuyến tính hóa ràng buộc thứ tự thực chứ không chỉ thứ tự logic. Tài liệu của etcd diễn đạt hệ quả này rất gọn: nếu một client hoàn tất một lần ghi tại thời điểm t1, thì một lần đọc khởi phát tại t2 > t1 phải trả về giá trị ít nhất mới bằng lần ghi đó31. Điều này buộc mọi bản sao phải phối hợp với nhau: không bản sao nào được phép trả lời bằng dữ liệu tụt hậu.

    Bạn vừa nộp bài lúc 9 giờ. Bạn của bạn hỏi lúc 9 giờ 01 thì phải nghe "đã nộp rồi", chứ không được nghe "chưa nộp". Nhớ nhé: chuyện đã xong rồi thì không ai được nói là chưa.

    Linearizability constrains real-time order, not merely logical order. etcd's documentation puts the consequence crisply: if a client completes a write at t1, a read issued at t2 > t1 must return a value at least as recent as that write31. That forces every replica to coordinate: no replica may answer from stale data.

    Nhận ra ở đâuBất cứ khi nào bạn nói "đọc-sau-khi-ghi phải thấy được", bạn đang đòi một mẩu khả tuyến tính hóa — và đang đòi một khoản đồng bộ đi kèm.
    Thấy ở đâuMỗi khi bạn muốn "vừa lưu là phải thấy ngay", bạn đang đòi điều này.
    Where you see itWhenever you say "a read after a write must see it," you are asking for a slice of linearizability — and for the coordination that comes with it.

    Cơ chế

    Vì thứ tự phải khớp thời gian thực, một hiện thực khả tuyến tính hóa không thể chỉ dựa vào bộ nhớ đệm cục bộ. Mọi lần đọc hoặc phải đi qua một điểm tuần tự hóa duy nhất (leader), hoặc phải hỏi đủ một quorum rồi sửa lại các bản tụt hậu trước khi trả lời14.

    Kiểm chứng khó

    Kiểm tra một hệ có khả tuyến tính hóa hay không là việc tốn kém: phải ghi lại dấu thời gian gọi/trả của mọi thao tác rồi tìm xem có tồn tại một thứ tự hợp lệ nào không9. Đó là bài toán tìm kiếm, không phải phép kiểm tra cục bộ — nên vi phạm thường chỉ lộ ra dưới tải nặng và lỗi mạng.

  2. Linearizability ≠ Serializability

    Hai chữ “nhất quán” không cùng nghĩaTwo different words that both sound like “consistency”

    Đây là cặp bị trộn lẫn nhiều nhất trong ngành, và Kleppmann tách bạch rất rõ1. Khả tuyến tính hóa là bảo đảm về tính mới cho một thao tác trên một đối tượng, có ràng buộc thời gian thực. Khả tuần tự hóa (Chương 7) là bảo đảm về cô lập giao dịch cho nhóm thao tác trên nhiều đối tượng, chỉ đòi kết quả tương đương một thứ tự tuần tự nào đó — và không ràng buộc thứ tự ấy phải khớp thời gian thực6. Ghép cả hai lại mới ra strict serializability7.

    Hai điều nghe giống nhau nhưng khác hẳn. Điều thứ nhất: "ai hỏi cũng thấy con số mới nhất" — nói về một ô dữ liệu. Điều thứ hai: "nhiều việc làm cùng lúc mà kết quả giống như làm lần lượt" — nói về cả nhóm việc. Nhớ nhé: một cái lo dữ liệu có mới không, cái kia lo các việc có giẫm chân nhau không.

    This is the industry's most-confused pair, and Kleppmann keeps them apart1. Linearizability is a recency guarantee for a single operation on a single object, with a real-time constraint. Serializability (Chapter 7) is a transaction isolation guarantee for groups of operations over many objects, requiring only that the result be equivalent to some serial order — and not requiring that order to match real time6. Combining the two yields strict serializability7.

    Bằng chứng chúng tách rờiPostgreSQL với Serializable Snapshot Isolation cho khả tuần tự hóa nhưng không cho khả tuyến tính hóa — nhãn “ACID” không hề kéo theo nghĩa “nhất quán” của CAP9.
    Bằng chứngCó cơ sở dữ liệu làm tốt việc "không giẫm chân nhau" mà vẫn cho đọc ra số cũ. Hai điều đó độc lập với nhau.
    Proof they come apartPostgreSQL under Serializable Snapshot Isolation provides serializability but not linearizability — the “ACID” label does not imply CAP's sense of “consistency”9.

    Quan hệ hình thức

    Herlihy & Wing nhận xét rằng khả tuyến tính hóa có thể xem là trường hợp riêng của strict serializability, khi mỗi giao dịch bị thu lại thành đúng một thao tác trên đúng một đối tượng6. Vì vậy nói "linearizable nên serializable" là sai chiều: nó chỉ đúng cho giao dịch một-thao-tác.

    Ghép được hay không

    Khả tuyến tính hóa ghép được: ghép các đối tượng khả tuyến tính hóa lại vẫn được một hệ khả tuyến tính hóa. Khả tuần tự hóa thì không — hai hệ con cùng khả tuần tự hóa vẫn có thể sinh ra một lịch sử chung không khả tuần tự hóa6. Đây là khác biệt kỹ thuật, không phải chuyện chữ nghĩa.

  3. “Eventual consistency” is a very weak promise

    “Rồi sẽ nhất quán” — nhưng bao giờ?“Eventually consistent” — but when?

    Ở đầu kia của phổ là eventual consistency: nếu ngừng ghi một lúc, cuối cùng mọi bản sao sẽ hội tụ về cùng giá trị. Kleppmann gọi đây là một bảo đảm rất yếu, vì nó không nói gì về bao giờ — và "cuối cùng" là một mệnh đề không có giới hạn thời gian. Bailis & Ghodsi cũng lập luận rằng cái tên dễ gây hiểu lầm và một tên chính xác hơn sẽ là convergence, sự hội tụ8.

    "Rồi sẽ giống nhau" nghe thì yên tâm, nhưng không ai hứa là bao lâu: một giây, một phút, hay tới khi bạn đã đi ngủ? Nhớ nhé: một lời hứa không kèm thời hạn thì gần như không phải lời hứa.

    At the other end of the spectrum sits eventual consistency: stop writing for a while and all replicas will converge on the same value. Kleppmann calls this a very weak guarantee, because it says nothing about when — and "eventually" carries no time bound. Bailis & Ghodsi likewise argue the name misleads, and that a more accurate one would be convergence8.

    Hệ quả khi lập trìnhVới nhất quán cuối, mọi lần đọc đều có thể là dữ liệu cũ. Lỗi sinh ra từ đó thường chỉ lộ ra khi mạng trục trặc hoặc tải cao — đúng lúc bạn ít muốn gặp nó nhất.
    Hệ quảBạn phải luôn chuẩn bị cho việc đọc ra số cũ, và chỉ khi hệ "bận" bạn mới thấy vấn đề.
    What it means for your codeUnder eventual consistency any read may be stale. The bugs that follow tend to surface only under network trouble or heavy load — exactly when you least want them.

    Phổ, không phải công tắc

    Giữa hai đầu còn nhiều nấc: đọc-thấy-cái-mình-ghi, đọc đơn điệu, tiền tố nhất quán, nhất quán nhân quả. Kleppmann dựng cả chương quanh ý niệm phổ này thay vì một công tắc bật/tắt1 — và mục tiêu kỹ thuật là chọn nấc rẻ nhất còn đủ cho bài toán.

    Vì sao vẫn phổ biến

    Vì nó cho phép mỗi bản sao trả lời ngay mà không hỏi ai, nên chịu được phân vùng mạng và có độ trễ thấp. Cái giá nằm ở chỗ gánh nặng xử lý xung đột và dữ liệu cũ bị đẩy sang tầng ứng dụng8.

Trục 2 · Where it's needed & what it costsAxis 2 · Where it's needed & what it costs

Vài việc thật sự cần nó — và hóa đơn đi kèmA few jobs genuinely need it — and the bill that follows

Kleppmann không khuyên dùng khả tuyến tính hóa ở khắp nơi; ông khoanh lại một danh sách ngắn những chỗ mà thiếu nó là hệ sai, chứ không chỉ là chậm cập nhật: bầu leader và khóa phân tán, ràng buộc duy nhất, và phụ thuộc thời gian xuyên kênh1. Ở mọi chỗ còn lại, cái giá — đồng bộ, độ trễ, và khả năng phục vụ khi mạng đứt — thường không đáng.

Không phải chỗ nào cũng cần mức chắc chắn nhất. Nhưng có vài việc mà thiếu nó là sai hẳn, không phải chỉ chậm: chọn ra đúng một người chỉ huy, giữ đúng một cái khóa, và bảo đảm hai người không cùng lấy một cái tên hay một chỗ ngồi. Nhớ nhé: chỉ vài việc mới đáng trả giá đắt.

Kleppmann does not recommend linearizability everywhere; he fences off a short list of places where its absence makes a system wrong, not merely slow to update: leader election and distributed locks, uniqueness constraints, and cross-channel timing dependencies1. Everywhere else the bill — coordination, latency and the ability to serve while the network is broken — is usually not worth paying.

The cost is not optional — it is a theorem

Hai kết quả hình thức đóng khung cái giá. Thứ nhất, định lý CAP: khi có phân vùng mạng, một hệ không thể vừa khả tuyến tính hóa vừa khả dụng theo nghĩa hình thức11. Thứ hai, và ít được nhắc hơn: ngay cả khi mạng hoàn toàn lành, thời gian phản hồi của các thao tác đọc/ghi khả tuyến tính hóa vẫn tỉ lệ với độ bất định của độ trễ mạng13.

Có hai điều đã được chứng minh chắc chắn. Một: khi đường dây bị đứt, không thể vừa "luôn đúng nhất" vừa "luôn trả lời được". Hai: kể cả lúc đường dây tốt, muốn "luôn đúng nhất" thì vẫn phải chờ — càng chờ lâu nếu đường truyền càng thất thường. Nhớ nhé: cái giá này không né được.

Two formal results frame the cost. First, the CAP theorem: under a network partition a system cannot be both linearizable and available in the formal sense11. Second, and less often quoted: even on a perfectly healthy network, the response time of linearizable reads and writes is necessarily proportional to the uncertainty of delays in the network13.

Kết quả thứ hai đáng chú ý vì nó bác bỏ cách đọc CAP quen thuộc: người ta hay nghĩ đánh đổi chỉ xuất hiện khi có sự cố. Attiya & Welch chỉ ra đánh đổi tồn tại mọi lúc, dưới dạng độ trễ13. Kleppmann còn dẫn một minh họa gần gũi hơn: ngay cả CPU trong máy của bạn cũng không cho truy cập RAM một cách khả tuyến tính hóa — mỗi lõi có bộ nhớ đệm riêng, và muốn có bảo đảm mạnh thì phải chèn chỉ thị memory barrier9. Nói cách khác, việc từ bỏ khả tuyến tính hóa vì hiệu năng là quyết định mà cả phần cứng lẫn phần mềm đều đã chọn từ lâu.

Khóa & leader Phải có đúng một người giữ khóa; hai người cùng tin mình giữ khóa là split brain.
Ràng buộc duy nhất Tên đăng nhập, số ghế, số dư không âm — đều cần một điểm quyết định duy nhất.
Xuyên kênh Khi hai bên còn liên lạc qua kênh khác (lời nói, hàng đợi), dữ liệu cũ trở thành mâu thuẫn thấy được.
Một chỉ huy Không được có hai người cùng tưởng mình chỉ huy.
Một chỗ ngồi Không được bán cùng một ghế cho hai người.
Có người mách Khi bạn nghe tin từ người khác rồi mới đi xem, xem ra số cũ là lộ ngay.
Locks & leaders Exactly one holder; two nodes each believing they hold the lock is split brain.
Uniqueness Usernames, seat numbers, non-negative balances — all need a single point of decision.
Cross-channel When two parties also talk over another channel, staleness becomes a visible contradiction.
  1. Locking and leader election

    Đúng một leader, đúng một người giữ khóaExactly one leader, exactly one lock holder

    Sao chép một-leader đòi hỏi đúng một nút là leader; nếu hai nút cùng tin mình là leader, dữ liệu sẽ phân nhánh và mất mát. Vì thế bầu leader thường được giao cho một dịch vụ điều phối như ZooKeeper hay etcd, và cái khóa mà các ứng viên tranh nhau phải là một khóa khả tuyến tính hóa: mọi nút phải đồng ý ai đang giữ28.

    Trong một trò chơi, chỉ được có một đội trưởng. Nếu hai bạn cùng tưởng mình là đội trưởng thì cả đội sẽ nhận hai mệnh lệnh trái nhau. Nhớ nhé: cái "gậy chỉ huy" phải là thứ mà ai nhìn vào cũng thấy đang ở trong tay đúng một người.

    Single-leader replication requires exactly one leader; if two nodes each believe they are leader, data forks and is lost. So leader election is usually delegated to a coordination service such as ZooKeeper or etcd, and the lock the candidates contend for must be a linearizable one: every node must agree on who holds it28.

    Nhận ra ở đâuMọi khóa phân tán, mọi hàng rào "chỉ một tiến trình được chạy tác vụ này", mọi cơ chế chống split brain đều là khả tuyến tính hóa đội lốt.
    Thấy ở đâuBất cứ chỗ nào cần "chỉ một người được làm việc này tại một lúc".
    Where you see itEvery distributed lock, every "only one process may run this job" fence, every anti-split-brain mechanism is linearizability in disguise.

    Khóa thôi chưa đủ

    Kleppmann lập luận riêng ở một bài khác rằng ngay cả khóa khả tuyến tính hóa cũng chưa đủ nếu tài nguyên được bảo vệ không kiểm tra gì: một tiến trình bị treo dài (GC pause) có thể tỉnh dậy sau khi khóa đã hết hạn và vẫn ghi đè. Lời giải là fencing token — một số tăng đơn điệu cấp kèm khóa, và kho lưu trữ từ chối mọi ghi mang số cũ hơn15.

    Vì sao là dịch vụ riêng

    Bầu leader là bài toán đồng thuận thu nhỏ. Thay vì mỗi hệ tự cài một thuật toán đồng thuận (dễ sai), thực tiễn phổ biến là "thuê ngoài": đẩy phần khó sang một cụm ZooKeeper/etcd nhỏ và để ứng dụng chỉ gọi API28.

  2. Uniqueness & cross-channel timing dependencies

    Khi người dùng có một “kênh phụ”When users have a side channel

    Ràng buộc duy nhất — một tên đăng nhập, một ghế, một số dư không âm — bản chất là một quyết định phải được chốt tại một điểm duy nhất, tức là một dạng đồng thuận. Tinh vi hơn là phụ thuộc thời gian xuyên kênh: Kleppmann kể chuyện Alice và Bob cùng xem kết quả chung kết World Cup 2014; Alice tải lại trang, thấy kết quả và reo lên; Bob nghe thấy rồi mới bấm tải lại, nhưng request của anh rơi vào một bản sao đang tụt hậu và màn hình báo trận đấu vẫn đang diễn ra9. Cái làm cho dữ liệu cũ trở thành sai chính là kênh liên lạc thứ hai — tiếng nói giữa hai người.

    Bạn và bạn cùng bàn xem cùng một trận bóng trên hai điện thoại. Bạn ấy thấy kết quả và hét lên; bạn bấm xem ngay sau đó nhưng máy bạn vẫn báo "đang đá". Nếu bạn ấy im lặng thì bạn chẳng thấy gì lạ. Nhớ nhé: dữ liệu cũ chỉ thành chuyện lớn khi có một đường tin khác chạy nhanh hơn.

    A uniqueness constraint — one username, one seat, one non-negative balance — is at bottom a decision that must be settled at a single point, which is a form of consensus. Subtler is the cross-channel timing dependency: Kleppmann tells of Alice and Bob watching the 2014 World Cup final; Alice reloads, sees the result and exclaims; Bob only then hits reload, but his request lands on a lagging replica and his screen says the match is still in progress9. What turns staleness into wrongness is that second channel — the two of them talking.

    Hệ quả thiết kếKhi xây một kho dữ liệu, bạn không biết client của mình có những kênh phụ nào. Muốn an toàn trước mọi kênh phụ, bạn buộc phải làm hệ trông như chỉ có một bản sao9.
    Bài họcBạn không đoán được người dùng còn nói chuyện với nhau bằng cách nào — nên hoặc chấp nhận rủi ro, hoặc làm cho mọi nơi luôn giống nhau.
    Design consequenceWhen you build a datastore you cannot know what back channels your clients have. To be safe against all of them you must make the system look as though there were a single copy9.

    Chính tài liệu ZooKeeper cũng cảnh báo

    Tài liệu ZooKeeper nêu đúng tình huống này như một ngộ nhận thường gặp: ZooKeeper không hứa rằng hai client bất kỳ luôn thấy cùng một ảnh chụp tại cùng một khoảnh khắc. Nếu client A ghi /a từ 0 thành 1 rồi bảo client B đọc, B vẫn có thể đọc ra 0 tùy nó đang nối tới máy chủ nào; muốn chắc, B phải gọi sync() trước khi đọc30.

    Cùng một hình dạng

    Ví dụ Alice/Bob và ví dụ A/B của ZooKeeper là một bài toán: thông tin đi vòng qua một kênh nhanh hơn đường sao chép dữ liệu. Nhận ra hình dạng này trong hệ của mình (hàng đợi tin nhắn, webhook, một người dùng gọi điện cho người kia) thường quan trọng hơn là thuộc lòng định nghĩa.

  3. How linearizable systems are actually built

    Ba cách hiện thực, hai cái có bẫyThree implementations, two with traps

    Cách chắc chắn nhất là đồng thuận: mọi thao tác đi qua một nhật ký được sắp thứ tự toàn phần, như ZooKeeper hay etcd làm31. Sao chép một-leader có tiềm năng khả tuyến tính hóa nếu mọi lần đọc đều đi qua leader — nhưng chỉ khi leader biết chắc mình vẫn là leader, điều mà Chương 8 đã cho thấy là không hiển nhiên. Quorum (đọc và ghi đều hỏi đa số) có thể khả tuyến tính hóa nếu kèm read repair đồng bộ14; nhưng với các hệ kiểu Dynamo dùng sloppy quorum, Kleppmann khuyên đừng trông cậy vào điều đó9.

    Có ba cách làm cho "nhiều cuốn sổ giống như một cuốn". Một: mọi người chỉ được ghi vào một cuốn chính. Hai: hỏi ý quá nửa số cuốn rồi mới trả lời. Ba: dùng một dịch vụ chuyên làm việc này. Nhớ nhé: cách nào cũng phải hỏi người khác trước khi trả lời — nên chậm hơn.

    The surest route is consensus: every operation passes through a totally-ordered log, as ZooKeeper and etcd do31. Single-leader replication is potentially linearizable if all reads go through the leader — but only if the leader truly knows it is still the leader, which Chapter 8 showed is not obvious. Quorums (majority reads and writes) can be linearizable with synchronous read repair14; but for Dynamo-style stores with sloppy quorums Kleppmann advises not to rely on it9.

    Đọc kỹ cấu hìnhCùng một sản phẩm có thể khả tuyến tính hóa ở chế độ này và không ở chế độ kia. Câu hỏi đúng không phải "cơ sở dữ liệu X có nhất quán không" mà "thao tác này, ở cấu hình này, bảo đảm gì".
    Nhớ hỏiĐừng hỏi "phần mềm này có chắc không", hãy hỏi "việc cụ thể này, cài đặt như thế này, chắc tới đâu".
    Read the configurationThe same product can be linearizable in one mode and not another. The right question is not "is database X consistent?" but "what does this operation, in this configuration, guarantee?"

    Vì sao quorum vẫn có thể hỏng

    Kleppmann liệt kê những tổ hợp tính năng khiến quorum mất tính khả tuyến tính hóa: sloppy quorum ghi tạm sang nút khác, read repair làm sống lại dữ liệu đã xóa, hoặc số bản sao trôi lệch khỏi N ban đầu khiến điều kiện w + r > n không còn đúng9.

    Bản sao bất đồng bộ thì chắc chắn không

    Sao chép đa-leader và sao chép không đồng bộ không thể khả tuyến tính hóa: mỗi bên chấp nhận ghi mà không hỏi bên kia, nên tồn tại những lịch sử không thể xếp vào một trật tự thời gian thực duy nhất9.

  4. The CAP theorem, stated precisely

    CAP: một định lý hẹp bị dùng quá rộngCAP: a narrow theorem used far too broadly

    Phát biểu hình thức của CAP — do Gilbert & Lynch chứng minh năm 2002 từ phỏng đoán của Brewer — rất hẹp11. Kleppmann liệt kê từng ràng buộc1: “nhất quán” ở đây chỉ có nghĩa là khả tuyến tính hóa, không phải chữ C trong ACID; “khả dụng” nghĩa là mọi nút còn sống phải trả lời không-lỗi cho mọi yêu cầu; mô hình hệ chỉ là một thanh ghi đọc-ghi duy nhất; lỗi duy nhất được xét là phân vùng mạng; và định lý không nói gì về độ trễ9.

    Có một câu nói nổi tiếng: "chọn 2 trong 3". Nhưng câu gốc của các nhà toán học chặt chẽ hơn nhiều, và chỉ áp dụng cho một tình huống rất hẹp: khi đường dây giữa các máy bị đứt. Lúc bình thường thì chẳng phải chọn gì cả. Nhớ nhé: nghe một câu khẩu hiệu ngắn gọn thì hãy hỏi câu gốc nói gì.

    CAP's formal statement — proved by Gilbert & Lynch in 2002 from Brewer's conjecture — is very narrow11. Kleppmann enumerates each constraint1: "consistency" here means only linearizability, not the C in ACID; "availability" means every non-failing node must return a non-error response to every request; the system model is a single read-write register; the only fault considered is a network partition; and the theorem says nothing about latency9.

    Đọc cho đúng“Chọn 2 trong 3” là cách diễn đạt gây hiểu lầm. Phân vùng mạng không phải thứ ta chọn — nó xảy ra. Lựa chọn thật chỉ xuất hiện khi đang có phân vùng, và khi mạng lành thì không phải chọn gì9.
    Nói cho đúngKhông ai "chọn" chuyện đường dây bị đứt. Chỉ khi nó đứt thì mới phải chọn: trả lời có thể sai, hay không trả lời.
    How to read it"Pick 2 of 3" is a misleading formulation. Partitions are not something you choose — they happen. The real choice appears only while a partition is in progress; when the network is healthy there is nothing to choose9.

    Vì sao gán nhãn “CP”/“AP” là sai

    Kleppmann chỉ ra rằng rất nhiều hệ thực tế không thuộc nhóm nào: sao chép một-leader với follower bất đồng bộ vừa không khả dụng theo nghĩa CAP (client bị ngăn khỏi leader thì không ghi được) vừa không khả tuyến tính hóa (đọc từ follower có thể ra dữ liệu cũ). Ông viết thẳng rằng cách nói "hai trong ba" thậm chí cho phép chọn một trong ba, hay không cái nào9. Đó là lý do ông đề nghị ngừng gọi cơ sở dữ liệu là “CP” hay “AP” và dùng thuật ngữ chính xác hơn10.

    Chính các tác giả cũng đã đính chính

    Mười năm sau bài chứng minh, Gilbert & Lynch quay lại viết “Perspectives on the CAP Theorem”, đặt CAP vào đúng chỗ của nó: một trường hợp riêng của đánh đổi rộng hơn giữa an toàn và sống động trong hệ không tin cậy, chứ không phải một bảng phân loại sản phẩm12.

  5. The latency price, paid every day

    Cái giá thường trực: độ trễThe standing price: latency

    Lý do thật khiến nhiều hệ đa-trung-tâm-dữ-liệu từ bỏ khả tuyến tính hóa thường không phải để chịu được phân vùng, mà là độ trễ của mạng diện rộng9. Attiya & Welch đã chứng minh giới hạn này: thời gian phản hồi của thao tác khả tuyến tính hóa tỉ lệ với độ bất định của độ trễ mạng — mạng càng thất thường, thao tác càng phải chờ lâu13. Đây là hóa đơn trả hằng ngày, không phải chỉ trong sự cố.

    Muốn chắc chắn thì phải hỏi ý người ở xa, mà hỏi người ở xa thì phải chờ. Đường truyền càng lúc nhanh lúc chậm thì càng phải chờ lâu cho chắc. Nhớ nhé: chắc chắn thì chậm — đó là luật, không phải lỗi phần mềm.

    The real reason many multi-datacenter systems give up linearizability is usually not partition tolerance but wide-area network latency9. Attiya & Welch proved the bound: the response time of a linearizable operation is proportional to the uncertainty of network delay — the more erratic the network, the longer each operation must wait13. This is a bill paid daily, not only during incidents.

    Khi nào đáng trảTrả khi sai là mất tiền hoặc mất dữ liệu (khóa, ghế, số dư). Không trả khi chỉ là hiển thị đếm lượt thích hay dòng thời gian — nơi dữ liệu cũ vài giây chẳng hại ai.
    Khi nào nên chờChờ khi sai sẽ mất tiền hay mất chỗ. Đừng chờ khi chỉ là hiển thị con số cho vui.
    When it's worth payingPay when being wrong costs money or data (locks, seats, balances). Don't pay for like counts or timelines, where a few seconds of staleness harms no one.

    Không chỉ chuyện mạng

    Ngay cả trong một máy, các lõi CPU không cho truy cập RAM theo kiểu khả tuyến tính hóa: mỗi lõi giữ bộ nhớ đệm riêng, và lập trình viên phải dùng memory barrier khi cần bảo đảm mạnh9. Lý do y hệt: đồng bộ tốn tiền, và phần lớn thời gian thì không cần.

    Hướng thoát

    Kleppmann kết phần này bằng một gợi ý1: nếu ta chấp nhận bảo đảm yếu hơn nhưng vẫn đủ dùng — chẳng hạn nhất quán nhân quả — thì có thể tránh phần lớn chi phí đồng bộ mà không rơi xuống mức "rồi sẽ nhất quán" mơ hồ. Đó chính là trục tiếp theo của chương.

Trục 3 · Ordering & causalityAxis 3 · Ordering & causality

Nhân quả là thứ tự bộ phận, không phải toàn phầnCausality is a partial order, not a total one

Kleppmann nối thứ tự với nhân quả1: nếu một thao tác biết về thao tác khác — đọc được giá trị nó ghi, trả lời tin nhắn nó gửi — thì hai thao tác ấy có quan hệ nhân quả và bắt buộc phải giữ đúng trước-sau. Nhưng hai thao tác không biết gì về nhau thì đồng thời, và ta không cần ép chúng vào một thứ tự nào cả. Vì thế nhân quả cho một thứ tự bộ phận: một số cặp so sánh được, một số cặp thì không — khác hẳn thứ tự toàn phần mà khả tuyến tính hóa áp đặt.

Có những việc rõ ràng phải xảy ra theo thứ tự: hỏi trước, trả lời sau. Nhưng có những việc chẳng liên quan gì nhau — hai bạn ở hai lớp cùng giơ tay lúc 9 giờ — thì xếp ai trước cũng được. Nhớ nhé: chỉ cần giữ thứ tự cho những việc có liên quan, không cần xếp hàng tất cả.

Kleppmann ties ordering to causality1: if one operation knows about another — it read the value that one wrote, or replied to the message it sent — then the two are causally related and their order must be preserved. But two operations that know nothing of each other are concurrent, and need not be forced into any order at all. So causality gives a partial order: some pairs are comparable, some are not — quite unlike the total order that linearizability imposes.

Happens-before: Lamport's partial order

Nền tảng là bài báo 1978 của Leslie Lamport, nơi ông định nghĩa quan hệ happens-before và chỉ ra rằng trong hệ phân tán, thứ tự "xảy ra trước" chỉ là một thứ tự bộ phận, còn mọi thứ tự toàn phần đều do ta áp đặt thêm16. Đây là bài mà toàn bộ phần thứ tự của Chương 9 dựng trên.

Từ năm 1978 người ta đã chứng minh: trong một nhóm máy, chỉ có thể nói chắc "việc này xảy ra trước việc kia" với một số cặp việc thôi. Muốn xếp tất cả thành một hàng thì phải tự đặt thêm luật. Nhớ nhé: hàng dọc không tự nhiên mà có.

The foundation is Leslie Lamport's 1978 paper, which defines the happens-before relation and shows that in a distributed system "happened earlier" is only a partial order — any total order is one we impose16. It is the paper the whole ordering half of Chapter 9 rests on.

Kleppmann dùng sự phân biệt bộ phận/toàn phần này để xếp hạng các mô hình nhất quán1: khả tuyến tính hóa cho thứ tự toàn phần (và do đó đắt), còn nhất quán nhân quả chỉ giữ thứ tự bộ phận. Điều đáng chú ý là nhân quả gần như là mức mạnh nhất còn khả thi khi mạng có sự cố: Mahajan, Alvisi & Dahlin chứng minh không hệ nào vừa luôn khả dụng, vừa hội tụ, lại cho bảo đảm mạnh hơn nhất quán nhân quả17. Nói cách khác, nhân quả là "trần" của phần rẻ tiền — vượt qua nó là bước vào lãnh địa đồng thuận.

Bộ phận Nhân quả chỉ sắp thứ tự các cặp có liên hệ; cặp đồng thời để tự do.
Toàn phần Khả tuyến tính hóa xếp mọi thao tác vào một hàng duy nhất khớp thời gian thực.
Bắc cầu Total order broadcast là cây cầu: một thứ tự toàn phần được mọi nút giao đúng như nhau.
Việc liên quan Hỏi trước, trả lời sau — thứ tự này phải giữ.
Việc rời nhau Không liên quan thì xếp ai trước cũng được.
Xếp một hàng Nếu muốn tất cả một hàng, phải có người đọc số thứ tự cho cả nhóm.
Partial Causality orders only related pairs; concurrent pairs are left free.
Total Linearizability puts every operation in one queue matching real time.
The bridge Total order broadcast is the bridge: one total order delivered identically to every node.
  1. Causal consistency: strong, and surprisingly cheap

    Mức mạnh nhất mà mạng đứt vẫn phục vụ đượcThe strongest model that survives a partition

    Nhất quán nhân quả giữ đúng mọi quan hệ "biết về", nhưng không đòi một thứ tự toàn phần — nên mỗi bản sao có thể trả lời ngay mà không cần hỏi ai, miễn là nó đã nhận đủ những gì đứng trước. Kết quả lý thuyết đi kèm rất mạnh: không có hệ nào vừa luôn khả dụng, vừa hội tụ, mà lại cho bảo đảm chặt hơn nhân quả17. Nói cách khác, đây là mức tốt nhất mà ta giữ được mà không phải trả phí đồng thuận.

    Có một mức "đủ đúng" rất tốt: chỉ cần bảo đảm câu trả lời không bao giờ hiện ra trước câu hỏi. Mức này không cần hỏi ý ai ở xa, nên vẫn chạy được khi đường dây trục trặc. Nhớ nhé: giữ đúng thứ tự trước-sau đã giải quyết phần lớn chuyện khó hiểu.

    Causal consistency preserves every "knows about" relation but demands no total order — so each replica can answer immediately without asking anyone, as long as it has received everything that precedes. The accompanying theory is strong: no system can be always available, convergent, and offer a guarantee stricter than causal consistency17. It is the best we can hold without paying for consensus.

    Nhận ra ở đâuMọi lỗi kiểu "thấy câu trả lời trước câu hỏi", "thấy bình luận trước bài viết", "thấy thông báo trước dữ liệu" đều là vi phạm nhân quả — và thường là thứ người dùng thật sự phàn nàn.
    Thấy ở đâuKhi bạn thấy lời bình luận mà chưa thấy bài viết nó bình luận — đó chính là lỗi này.
    Where you see itEvery "answer before question", "comment before post", "notification before data" bug is a causality violation — and usually what users actually complain about.

    Theo dõi nhân quả tốn gì

    Để giữ nhân quả, hệ phải biết thao tác nào "đã thấy" thao tác nào trước đó — thường bằng số phiên bản hoặc vector phiên bản, như Chương 5 đã dựng cho việc phát hiện ghi đồng thời. Chi phí nằm ở siêu dữ liệu phải mang theo, chứ không phải ở việc chờ quorum.

    Vì sao chưa phổ biến

    Kleppmann nhận xét đây vẫn là lĩnh vực nghiên cứu đang mở: giữ nhân quả đầy đủ trong một hệ lớn với nhiều phân mảnh là bài toán khó, và ít cơ sở dữ liệu thương mại cung cấp nó như một bảo đảm đầu bảng1.

  2. Lamport timestamps — and where they stop

    Đánh số thì dễ, quyết định ngay mới khóNumbering is easy; deciding now is hard

    Đồng hồ logic của Lamport là một cặp (bộ đếm, mã nút): mỗi nút tăng bộ đếm của mình, và mỗi khi nhận tin nhắn thì nâng bộ đếm lên ít nhất bằng giá trị nhận được; so sánh thì so bộ đếm trước, hòa thì so mã nút16. Cách này cho một thứ tự toàn phần nhất quán với nhân quả — và rẻ. Nhưng Kleppmann chỉ ra chỗ nó không đủ1: với một ràng buộc duy nhất, bạn phải trả lời "tên này có bị lấy chưa" ngay lúc này, trong khi thứ tự Lamport chỉ hoàn chỉnh sau khi đã gom hết mọi thao tác từ mọi nút.

    Có một mẹo đánh số rất gọn để xếp mọi việc thành một hàng. Nhưng muốn biết "mình có phải người đầu tiên lấy cái tên này không", bạn phải đợi nghe tin từ tất cả mọi người — mà chờ tất cả thì đâu còn nhanh nữa. Nhớ nhé: xếp hàng được sau đó không có nghĩa là quyết định được ngay bây giờ.

    Lamport's logical clock is a pair (counter, node id): each node increments its own counter, and on receiving a message raises its counter to at least the received value; comparison goes by counter first, node id as tie-break16. This yields a total order consistent with causality — cheaply. But Kleppmann points at where it falls short1: a uniqueness constraint must answer "is this name taken?" right now, whereas a Lamport order is only complete after collecting every operation from every node.

    Ranh giới cần nhớĐánh số thứ tự giải quyết bài toán sắp xếp lại; nó không giải quyết bài toán quyết định ngay. Ranh giới này chính là chỗ đồng thuận bắt đầu cần thiết.
    Ranh giớiĐánh số giúp xếp lại cho đúng về sau; nó không giúp bạn trả lời ngay lập tức.
    The boundarySequence numbers solve reordering; they do not solve deciding now. That boundary is exactly where consensus becomes necessary.

    Khác với vector clock

    Lamport timestamp cho thứ tự toàn phần nhưng mất thông tin về tính đồng thời: nhìn hai dấu thời gian, ta không phân biệt được "A thật sự xảy ra trước B" với "A và B đồng thời, chỉ là bị xếp trước". Vector clock giữ được thông tin ấy nhưng tốn siêu dữ liệu hơn và chỉ cho thứ tự bộ phận16.

    Vì sao "quyết định ngay" khó

    Vì để chắc chắn không ai khác đang tuyên bố cùng một tên, nút của bạn phải biết trạng thái hiện thời của mọi nút khác — kể cả nút vừa sập. Nếu một nút im lặng, bạn không thể phân biệt "nó chưa tuyên bố gì" với "nó đã tuyên bố mà tin chưa tới". Đó chính là bài toán Chương 8 để lại.

  3. Total order broadcast

    Phát sóng theo thứ tự toàn phầnBroadcasting in one agreed order

    Thứ ta thật sự cần là total order broadcast (còn gọi là atomic broadcast): một giao thức trao đổi tin nhắn giữa các nút với hai bảo đảm — giao hàng tin cậy (không tin nhắn nào bị mất; đã tới một nút thì tới mọi nút) và giao hàng theo thứ tự toàn phần (mọi nút nhận tin nhắn theo đúng cùng một thứ tự)18. Đây chính là hình dạng của một nhật ký sao chép: mọi bản sao phát lại cùng một chuỗi sự kiện thì cùng đi tới một trạng thái — kỹ thuật state machine replication19.

    Hãy hình dung một người phát loa cho cả trường: mọi lớp nghe cùng một câu, theo cùng một thứ tự. Nếu ai cũng làm theo lần lượt từng câu, cuối buổi cả trường sẽ ở cùng một trạng thái. Nhớ nhé: cùng nghe một thứ tự thì cùng ra một kết quả.

    What we actually need is total order broadcast (also called atomic broadcast): a protocol for exchanging messages between nodes with two guarantees — reliable delivery (no message is lost; if it reaches one node it reaches all) and totally ordered delivery (every node receives messages in the same order)18. This is exactly the shape of a replication log: replay the same sequence of events on every replica and they all reach the same state — the state machine replication technique19.

    Nhận ra ở đâuNhật ký sao chép của cơ sở dữ liệu, nhật ký phân vùng của một hệ nhắn tin, sổ ghi của một dịch vụ điều phối — tất cả đều là total order broadcast dưới những cái tên khác nhau.
    Thấy ở đâuMọi "cuốn nhật ký" mà các máy lần lượt chép lại theo đúng thứ tự.
    Where you see itA database replication log, a messaging system's partition log, a coordination service's journal — all are total order broadcast under different names.

    Chốt thứ tự, không sửa lại

    Điểm mạnh nằm ở chỗ thứ tự được chốt tại lúc giao: một khi tin nhắn đã được giao, vị trí của nó trong dãy là cố định, và các tin nhắn tới sau không được chen vào trước. Đây chính là điều Lamport timestamp không cho — nó chỉ sắp xếp hậu kiểm18.

    Dựng khả tuyến tính hóa từ nó

    Kleppmann chỉ ra cách bắc cầu ngược lại1: muốn một ràng buộc duy nhất khả tuyến tính hóa, hãy phát một tin nhắn "tôi nhận tên X" qua total order broadcast, rồi đọc lại nhật ký; nếu tin nhắn đầu tiên nhận tên X là của bạn thì bạn thắng, ngược lại thì bạn thua. Ghi trở nên khả tuyến tính hóa, còn đọc thì cần thêm một bước đồng bộ để bảo đảm đã theo kịp nhật ký.

Trục 4 · Distributed transactions & consensusAxis 4 · Distributed transactions & consensus

Từ 2PC đến đồng thuận chịu lỗiFrom 2PC to fault-tolerant consensus

Đồng thuận nghe đơn giản: "làm cho vài nút cùng đồng ý một điều". Kleppmann gọi đây là một trong những bài toán quan trọng và nền tảng nhất của tính toán phân tán — và cũng là một trong những bài toán tinh vi nhất1. Ta bắt đầu từ hình thức quen thuộc nhất của nó — atomic commit qua giao thức hai pha — rồi thấy vì sao nó chưa chịu được lỗi, và cuối cùng gặp lớp thuật toán thật sự chịu lỗi: Paxos, Raft, Zab, VSR.

Phần cuối nói về chuyện khó nhất: làm sao cả nhóm máy cùng chốt một quyết định và không ai đổi ý. Ta xem thử cách cũ (hỏi từng người rồi mới chốt) hỏng ở đâu, rồi xem cách mới sửa nó thế nào. Nhớ nhé: chốt xong là không ai được đổi ý.

Consensus sounds simple: "get several nodes to agree on something". Kleppmann calls it one of the most important and fundamental problems in distributed computing — and one of the subtlest1. We start from its most familiar form — atomic commit via the two-phase protocol — see why it is not yet fault-tolerant, and finally meet the algorithms that are: Paxos, Raft, Zab, VSR.

Consensus: agree on one value, irrevocably

Bài toán đồng thuận đòi bốn tính chất: thống nhất (không hai nút quyết định khác nhau), toàn vẹn (không nút nào quyết định hai lần), hợp lệ (giá trị được quyết định phải do một nút nào đó đề xuất) và kết thúc (mọi nút không sập cuối cùng đều quyết định)1. Ba tính chất đầu là về an toàn; tính chất thứ tư — kết thúc — là chỗ mọi khó khăn nằm ở đó.

Muốn gọi là "cả nhóm đã chốt", cần bốn điều: ai cũng chốt giống nhau, mỗi người chỉ chốt một lần, điều được chốt phải do ai đó đề nghị, và cuối cùng mọi người còn khỏe đều chốt được. Nhớ nhé: ba điều đầu dễ, điều cuối mới khó.

The consensus problem demands four properties: uniform agreement (no two nodes decide differently), integrity (no node decides twice), validity (the decided value was proposed by some node) and termination (every non-crashed node eventually decides)1. The first three are safety; the fourth — termination — is where all the difficulty lives.

Vì sao "kết thúc" khó đến thế? Vì nó buộc thuật toán phải tiến lên ngay cả khi một số nút đã chết mà không ai biết chắc. Nếu ta chỉ cần an toàn, một thuật toán không bao giờ quyết định gì cả đã là "đúng". Đây cũng chính là điểm mà định lý FLP cắm mốc: trong mô hình bất đồng bộ tất định, không thuật toán nào bảo đảm được cả an toàn lẫn kết thúc nếu có dù chỉ một nút có thể sập22.

2PC Chốt nguyên tử trên nhiều nút, nhưng dừng lại khi điều phối viên chết.
Đồng thuận Chốt được cả khi một thiểu số nút chết, nhờ quorum và đánh số epoch.
Tương đương Đồng thuận và total order broadcast quy về nhau được23.
Cách cũ Hỏi từng người rồi mới chốt — người hỏi mà nghỉ thì cả nhóm treo.
Cách mới Quá nửa đồng ý là chốt; thiếu vài người vẫn xong.
Cùng một việc "Chốt một điều" và "phát loa đúng thứ tự" thật ra là một bài toán.
2PC Atomic commit across nodes, but it stalls when the coordinator dies.
Consensus Decides even when a minority of nodes dies, via quorums and epoch numbers.
Equivalent Consensus and total order broadcast reduce to each other23.
  1. Two-phase commit and the coordinator's death

    Điểm chết của điều phối viênThe coordinator's single point of death

    2PC chia việc chốt làm hai pha: điều phối viên hỏi mọi bên "sẵn sàng chưa?" rồi mới ra lệnh chốt. Bí mật nằm ở chỗ một khi đã trả lời "sẵn sàng", bên tham gia mất quyền tự quyết: nó đã hứa sẽ chốt được, nên không được phép tự hủy nữa. Nếu điều phối viên sập sau khi thu đủ lời hứa nhưng trước khi gửi quyết định, các bên rơi vào trạng thái in doubt — không dám chốt, không dám hủy, và vẫn giữ khóa cho tới khi điều phối viên sống lại1.

    Muốn cả nhóm cùng làm một việc, người điều phối hỏi vòng quanh: "ai cũng sẵn sàng chứ?" Ai gật rồi thì không được rút lời. Nhưng nếu người điều phối đột nhiên biến mất sau khi mọi người đã gật, cả nhóm chỉ biết đứng chờ — không ai dám làm, cũng không ai dám bỏ. Nhớ nhé: hứa xong mà người ra lệnh biến mất là kẹt cứng.

    2PC splits committing into two phases: the coordinator asks everyone "are you ready?" and only then orders the commit. The secret is that once a participant answers "yes" it gives up the right to decide: it has promised it can commit, so it may no longer abort unilaterally. If the coordinator crashes after gathering the promises but before sending the decision, participants are left in doubt — unable to commit, unable to abort, still holding their locks until the coordinator returns1.

    Vì sao gọi là “blocking”Vì sự tiến triển của toàn hệ bị treo vào một nút duy nhất. Skeen đã phân tích chính xác tính chất này và đề xuất 3PC như một giao thức không-treo20.
    Vì sao gọi là “kẹt”Vì cả nhóm phải chờ đúng một người quay lại mới đi tiếp được.
    Why it's called “blocking”Because the whole system's progress hangs on one node. Skeen analysed exactly this property and proposed 3PC as a non-blocking alternative20.

    Vì sao 3PC không cứu được

    3PC chỉ không-treo dưới giả định mạng có độ trễ có giới hạn và nút phản hồi trong thời hạn biết trước — tức là cần một bộ phát hiện lỗi hoàn hảo20. Chương 8 đã cho thấy mạng thật không cho ta điều đó, nên Kleppmann kết luận 2PC vẫn được dùng dù mang tiếng xấu1.

    Nhật ký điều phối viên là trạng thái

    Điều phối viên phải ghi quyết định xuống đĩa trước khi công bố, và nhật ký ấy là trạng thái không thể mất. Điều đó biến điều phối viên thành một thành phần có trạng thái, khó nhân bản và khó đưa vào kiến trúc không-chia-sẻ — một trong những lý do khiến giao dịch phân tán khó sống chung với microservice.

  2. XA and the bad reputation of distributed transactions

    Vì sao giao dịch phân tán mang tiếng xấuWhy distributed transactions got a bad name

    Trong thực tế, giao dịch phân tán liên-hệ-thống thường đi qua XA — chuẩn Distributed Transaction Processing: The XA Specification do X/Open công bố năm 1991, định nghĩa giao diện giữa một điều phối viên giao dịch và các tài nguyên biết nói 2PC21. Nó được cài trong nhiều cơ sở dữ liệu và trình môi giới tin nhắn. Vấn đề là mọi nhược điểm của 2PC được thừa kế nguyên vẹn, cộng thêm việc chuẩn còn cho phép heuristic decision — bên tham gia tự ý chốt hoặc hủy khi kẹt quá lâu, phá vỡ đúng tính nguyên tử mà 2PC sinh ra để bảo vệ21.

    Người ta có sẵn một bộ luật chung để nhiều hệ thống khác nhau cùng chơi trò "hứa rồi mới chốt". Nhưng bộ luật ấy có một điều khoản nguy hiểm: nếu chờ quá lâu, một bên được tự quyết. Thế là điều mà cả trò chơi muốn bảo vệ — "hoặc tất cả cùng làm, hoặc không ai làm" — lại bị chính điều khoản đó phá. Nhớ nhé: luật có lối thoát hiểm thì lời hứa hết chắc.

    In practice, cross-system distributed transactions usually go through XA — the Distributed Transaction Processing: The XA Specification published by X/Open in 1991, defining the interface between a transaction coordinator and resources that speak 2PC21. It is implemented in many databases and message brokers. The trouble is that every weakness of 2PC is inherited intact, plus the standard's allowance for heuristic decisions — a participant unilaterally committing or aborting when stuck too long, breaking exactly the atomicity 2PC exists to protect21.

    Đọc cho công bằngKleppmann không nói "đừng bao giờ dùng"; ông tách hai thứ hay bị gộp: giao dịch phân tán trong cùng một cơ sở dữ liệu (thường chạy tốt) và giao dịch không đồng nhất qua XA (nơi sinh ra tiếng xấu)1.
    Công bằng mà nóiKhông phải cái nào cũng tệ: trong cùng một hệ thì ổn; nối nhiều hệ khác loại với nhau mới là chỗ hay hỏng.
    Read it fairlyKleppmann does not say "never use them"; he separates two things people conflate: distributed transactions inside one database (usually fine) and heterogeneous transactions over XA (where the bad name comes from)1.

    Giao dịch mồ côi

    Khi điều phối viên mất nhật ký của mình, các giao dịch đang treo trở thành mồ côi: không cách nào biết chúng nên chốt hay hủy một cách tự động, nên quản trị viên phải vào tận nơi quyết định bằng tay — và mọi lựa chọn đều có thể làm hai hệ lệch nhau vĩnh viễn1.

    Khóa bị giữ lâu

    Vì bên tham gia phải giữ khóa suốt thời gian "nghi ngờ", một điều phối viên chết có thể làm nghẽn cả những giao dịch chẳng liên quan. Chi phí này không xuất hiện trong sơ đồ giao thức nhưng là thứ đội vận hành cảm nhận rõ nhất.

  3. Fault-tolerant consensus: epochs and quorums

    Paxos, Raft, Zab, VSR — một gia đìnhPaxos, Raft, Zab, VSR — one family

    Bốn thuật toán nổi tiếng nhất — Paxos24, Raft25, Zab (nền của ZooKeeper)26 và Viewstamped Replication27 — có một hình dạng chung. Chúng không quyết định một giá trị mà quyết định một chuỗi giá trị, tức là chúng hiện thực total order broadcast. Cơ chế chung gồm hai mảnh: đánh số epoch (Paxos gọi là ballot number, Raft gọi là term, Zab gọi là epoch, VSR gọi là view number) và bỏ phiếu theo quorum: trong mỗi epoch chỉ có tối đa một leader, và mọi quyết định đều cần đa số25.

    Nhóm bầu ra một người cầm loa. Mỗi lần bầu lại thì ghi thêm một số "lần bầu thứ mấy" — số càng lớn càng mới, ai cầm số cũ thì bị bỏ qua. Và muốn chốt bất cứ điều gì, phải có quá nửa nhóm gật. Nhớ nhé: hai nhóm "quá nửa" luôn có ít nhất một người chung, nên không thể có hai quyết định trái nhau.

    The four best-known algorithms — Paxos24, Raft25, Zab (the basis of ZooKeeper)26 and Viewstamped Replication27 — share one shape. They decide not a value but a sequence of values, which is to say they implement total order broadcast. Two pieces do the work: epoch numbering (Paxos calls it a ballot number, Raft a term, Zab an epoch, VSR a view number) and quorum voting: within each epoch there is at most one leader, and every decision needs a majority25.

    Vì sao an toànVì hai quorum đa số bắt buộc giao nhau, một quyết định đã được một quorum chấp nhận sẽ luôn được nhìn thấy bởi quorum của epoch sau — nên leader mới không thể xóa quyết định cũ25.
    Vì sao chắcVì hai nhóm quá nửa luôn có người chung, nên chuyện đã chốt không thể bị người sau xóa.
    Why it's safeBecause two majority quorums must overlap, a decision accepted by one quorum is always visible to the next epoch's quorum — so a new leader cannot erase an older decision25.

    Hai vòng bỏ phiếu, không phải một

    Kleppmann nhấn một điểm dễ bỏ qua: có hai lượt bỏ phiếu — một để bầu leader, một để chấp nhận từng đề xuất của leader ấy. Leader không được tin vào chức vụ của chính mình; trước khi chốt, nó phải hỏi lại quorum xem có ai biết về một epoch mới hơn không. Nếu có, nó thoái vị25.

    Khác biệt giữa các thành viên gia đình

    Zab và Raft nghiêng về mô hình leader mạnh với nhật ký nối tiếp; Paxos nguyên bản tổng quát hơn nhưng khó hiện thực hơn — chính vì thế Ongaro & Ousterhout đặt tên bài báo là "đi tìm một thuật toán đồng thuận dễ hiểu"25, còn VSR là hướng tiếp cận độc lập từ 1988 mà sau này được thấy là rất gần Paxos27.

  4. The limits of consensus — and outsourcing it

    Giới hạn, FLP, và chuyện “thuê ngoài”Limits, FLP, and outsourcing the hard part

    Đồng thuận không miễn phí. Việc bỏ phiếu là một dạng sao chép đồng bộ, nên đắt về độ trễ; số nút tham gia thường cố định, thay đổi thành viên cần cơ chế riêng; và toàn bộ kiến trúc dựa vào timeout để đoán nút nào đã chết — trong mạng có độ trễ thất thường, điều này sinh ra những vòng bầu lại liên tục khiến hệ còn tệ hơn1. Vì thế lời khuyên thực dụng là đừng tự viết: giao phần khó cho ZooKeeper, etcd hay Chubby và chỉ gọi API28.

    Cách này tốt nhưng không rẻ: phải chờ quá nửa nhóm trả lời, và nhóm phải đoán ai đã nghỉ bằng cách "đợi một lúc không thấy trả lời". Nếu đường truyền lúc nhanh lúc chậm, nhóm sẽ cứ bầu đi bầu lại. Nhớ nhé: phần khó này đã có sẵn phần mềm chuyên làm — đừng tự viết lại.

    Consensus is not free. The voting is a form of synchronous replication, so it costs latency; the set of nodes is usually fixed, and changing membership needs its own mechanism; and the whole design leans on timeouts to guess which node has died — on a network with erratic delays this produces repeated leader elections that make things worse1. Hence the pragmatic advice: don't write your own; hand the hard part to ZooKeeper, etcd or Chubby and just call the API28.

    Dịch vụ điều phối cho gìKhông chỉ đồng thuận: thao tác nguyên tử khả tuyến tính hóa (so-sánh-rồi-đặt), thứ tự toàn phần cho mọi thao tác, phát hiện lỗi qua phiên và nhịp tim, và thông báo thay đổi30.
    Dịch vụ ấy làm gìGiữ khóa, đánh số thứ tự, biết ai còn sống, và báo cho bạn khi có gì đổi.
    What a coordination service givesNot just consensus: linearizable atomic operations (compare-and-set), a total ordering of operations, failure detection via sessions and heartbeats, and change notifications30.

    FLP nói gì — và không nói gì

    Fischer, Lynch & Paterson (1985) chứng minh rằng trong mô hình bất đồng bộ tất định — không đồng hồ, không timeout, thuật toán không được dùng ngẫu nhiên — không thuật toán nào luôn đạt đồng thuận nếu có dù chỉ một nút có thể sập22. Điều đó không có nghĩa đồng thuận là bất khả trong thực tế: hệ thật được phép dùng timeout, tức là mô hình bán-đồng-bộ. Chandra & Toueg hình thức hóa chính lối thoát này bằng khái niệm bộ phát hiện lỗi không tin cậy, và chứng minh đồng thuận giải được với chúng23; Raft thì dùng thời hạn bầu cử ngẫu nhiên để tránh hai ứng viên khóa nhau mãi25.

    Lý thuyết đúng chưa đủ để chạy

    Chandra, Griesemer & Redstone kể lại kinh nghiệm dựng một cơ sở dữ liệu chịu lỗi bằng Paxos tại Google và ghi nhận rằng dù tài liệu học thuật đã có sẵn, việc xây dựng nó hóa ra không hề tầm thường29. Khoảng cách giữa một bài báo đúng và một hệ chạy được là lý do chính đáng nhất để dùng lại phần mềm đã được kiểm chứng.

    Hành vi sản phẩm hôm nay (muộn hơn sách 2017)

    Tài liệu etcd hiện hành phát biểu bảo đảm của nhóm API KV là strict serializability, khả tuyến tính hóa mặc định cho mọi thao tác, và cho phép client chọn chế độ đọc serializable để bỏ vòng đồng thuận, đổi lấy độ trễ thấp nhưng có thể đọc dữ liệu cũ31. Tài liệu ZooKeeper thì liệt kê bảo đảm của nó là nhất quán tuần tự, nguyên tử, "ảnh chụp hệ thống duy nhất", tin cậy và kịp thời — đọc có thể ra dữ liệu cũ trừ khi gọi sync() trước30. Đây là nội dung tài liệu hiện thời, không phải trích từ bản in 2017.

Ba ngộ nhận lớn nhất của chương nàyThe three biggest misreadings of this chapter

“CAP: chọn 2 trong 3”"CAP: pick 2 of 3"

Sai. Định lý chỉ nói về khả tuyến tính hóa, chỉ trong mô hình một thanh ghi đọc-ghi, và chỉ khi đang có phân vùng mạng — thứ ta không chọn mà phải chịu9. Khi mạng lành thì không phải đánh đổi gì; và rất nhiều hệ thực tế chẳng phải “CP” lẫn “AP”.

Wrong. The theorem is about linearizability only, in a single read-write register model only, and only during a network partition — which we do not choose but suffer9. With a healthy network there is no trade-off to make; and many real systems are neither "CP" nor "AP".

“Linearizable tức là serializable”"Linearizable means serializable"

Sai. Một cái là bảo đảm về tính mới trên một đối tượng đơn; cái kia là bảo đảm về cô lập giao dịch trên nhóm thao tác, và không ràng buộc thời gian thực. Ghép cả hai mới thành strict serializability6.

Wrong. One is a recency guarantee on a single object; the other is a transaction isolation guarantee over groups of operations, with no real-time constraint. Only their combination is strict serializability6.

“FLP chứng minh đồng thuận là bất khả”"FLP proves consensus is impossible"

Sai. FLP chỉ đúng trong mô hình bất đồng bộ tất định, nơi thuật toán không được dùng đồng hồ hay timeout22. Hệ thật được phép dùng timeout và ngẫu nhiên, nên đồng thuận vẫn giải được — đó là lý do Paxos và Raft tồn tại23.

Wrong. FLP holds in the deterministic asynchronous model, where the algorithm may use no clocks or timeouts22. Real systems may use timeouts and randomisation, so consensus is achievable — which is why Paxos and Raft exist23.

Tự đọc mìnhRead yourself

Soi nhu cầu đồng bộ trong hệ của bạnAudit the coordination your system really needs

Chương 9 cho ta một bộ câu hỏi sắc bén để soi bất kỳ hệ nào: chỗ nào đang đòi bảo đảm mạnh, chỗ nào đang trả tiền cho bảo đảm mà nó không cần, và chỗ nào đang giả định một bảo đảm mà hệ không hề có.

Thử soi một hệ thật bằng mấy câu dưới. Mục tiêu không phải khoe hệ chắc chắn, mà để biết chỗ nào cần chắc chắn và chỗ nào chỉ đang tốn công vô ích. Nhớ nhé: hỏi đúng chỗ trước khi sửa.

Chapter 9 hands us a sharp set of questions for any system: where it demands a strong guarantee, where it pays for one it doesn't need, and where it assumes one it never had.

Chỗ nào trong hệ của bạn thật sự cần khả tuyến tính hóa?Hãy kể tên cụ thể: một cái khóa, một ràng buộc duy nhất, một cuộc bầu leader. Nếu danh sách dài hơn ba dòng, nhiều khả năng bạn đang trả tiền cho đồng bộ ở những chỗ chỉ cần nhất quán nhân quả.
Bạn có đang nhầm “khả tuyến tính hóa” với “khả tuần tự hóa” không?Cơ sở dữ liệu của bạn có thể cho mức cô lập serializable mà vẫn trả về dữ liệu cũ khi đọc từ bản sao. Hai bảo đảm này bật/tắt độc lập, và tài liệu sản phẩm thường dùng chung một chữ "consistency" cho cả hai.
Người dùng của bạn có kênh phụ nào không?Một hàng đợi tin nhắn, một webhook, một cuộc gọi điện thoại giữa hai nhân viên — bất kỳ đường nào truyền tin nhanh hơn đường sao chép dữ liệu đều biến "hơi cũ" thành "sai rõ ràng". Hãy vẽ các kênh ấy ra trước khi chọn mô hình nhất quán.
Khi có phân vùng mạng, bạn muốn nhánh thiểu số làm gì?Đây mới là câu hỏi CAP thật sự, và nó chỉ có ý nghĩa trong lúc phân vùng. Hai lựa chọn: từ chối phục vụ để giữ tính đúng đắn, hay tiếp tục phục vụ với dữ liệu có thể cũ. Hãy trả lời cho từng chức năng, đừng trả lời cho cả hệ.
Bạn đang trả bao nhiêu độ trễ cho việc đồng bộ, và trả ở đâu?Thời gian phản hồi của thao tác khả tuyến tính hóa tỉ lệ với độ bất định của độ trễ mạng13. Nếu quorum của bạn trải qua nhiều vùng địa lý, con số ấy nằm trong p99 của bạn mỗi ngày, không chỉ khi có sự cố.
Có chỗ nào trong hệ hiện ra “sau” trước “trước” không?Bình luận hiện trước bài viết, thông báo tới trước dữ liệu, câu trả lời xuất hiện trước câu hỏi — đó là vi phạm nhân quả, và thường là thứ người dùng phàn nàn trước cả khi bạn kịp nghĩ tới CAP.
Nếu điều phối viên giao dịch của bạn chết ngay bây giờ, ai đang giữ khóa?Với 2PC, các bên đã bỏ phiếu "sẵn sàng" sẽ treo ở trạng thái nghi ngờ và giữ khóa tới khi điều phối viên trở lại20. Bạn có biết thời gian phục hồi của nó, và có quy trình xử lý giao dịch mồ côi chưa?
Bạn đang tự viết đồng thuận, hay đang dùng lại?Nếu trong mã của bạn có chỗ nào tự bầu leader bằng timeout và cờ trong cơ sở dữ liệu, gần như chắc chắn bạn đang viết một thuật toán đồng thuận sai. Ngay cả Google cũng thấy việc hiện thực Paxos là không tầm thường29.
Chỗ nào trong hệ của bạn bắt buộc phải "chỉ một người được làm"?Đó là chỗ cần mức chắc chắn cao nhất. Những chỗ khác thì không cần.
Có chỗ nào hiện ra lộn thứ tự không?Ví dụ thấy lời bình luận mà chưa thấy bài viết. Đó là lỗi thứ tự trước-sau.
Nếu đường dây giữa các máy bị đứt, bạn muốn máy bên kia làm gì?Im lặng chờ cho chắc, hay cứ trả lời dù có thể trả lời số cũ? Chọn theo từng việc.
Ai đang là "người cầm loa" trong hệ của bạn?Nếu người đó nghỉ, nhóm có tự chọn được người khác không, hay treo luôn?
Where does your system genuinely need linearizability?Name them: a lock, a uniqueness constraint, a leader election. If the list runs past three lines, you are probably paying for coordination where causal consistency would do.
Are you confusing "linearizable" with "serializable"?Your database can offer serializable isolation and still return stale reads from a replica. The two guarantees toggle independently, and product docs often use one word "consistency" for both.
What side channels do your users have?A message queue, a webhook, one colleague phoning another — any path faster than replication turns "slightly stale" into "plainly wrong". Draw those channels before choosing a consistency model.
During a partition, what should the minority side do?This is the real CAP question, and it only means anything while the partition lasts. Refuse service to stay correct, or keep serving possibly-stale data. Answer per feature, not per system.
How much latency are you paying for coordination, and where?The response time of linearizable operations is proportional to network delay uncertainty13. If your quorum spans regions, that cost sits in your p99 every day, not only during incidents.
Does anything in your system show "after" before "before"?A comment before its post, a notification before the data, an answer before the question — these are causality violations, and usually what users complain about long before CAP comes up.
If your transaction coordinator died right now, who holds the locks?Under 2PC, participants that voted "yes" hang in doubt and hold their locks until the coordinator returns20. Do you know its recovery time, and do you have a runbook for orphaned transactions?
Are you writing consensus yourself, or reusing it?If your code elects a leader with a timeout and a flag in a database, you are almost certainly writing a broken consensus algorithm. Even Google found implementing Paxos non-trivial29.
Kết luận cô đọngThe conclusion, distilled
Nhất quán không phải một công tắc mà là một phổ có giá. Khả tuyến tính hóa bán cho bạn ảo giác chỉ có một bản sao, và thu tiền bằng độ trễ mỗi ngày cùng khả năng phục vụ khi mạng đứt — nên chỉ nên mua cho khóa, bầu leader và ràng buộc duy nhất. Nhân quả rẻ hơn nhiều mà chữa được phần lớn lỗi người dùng thật sự thấy. Còn khi bắt buộc phải có một thứ tự toàn phần, bạn đã bước vào lãnh địa đồng thuận — nơi total order broadcast và đồng thuận là một, nơi epoch và quorum giữ cho quyết định không bị xóa, và nơi lời khuyên đúng đắn nhất là đừng tự viết lại.Không phải lúc nào cũng cần mức chắc chắn cao nhất. Mức cao nhất giống như chỉ có một cuốn sổ duy nhất — rất chắc nhưng phải chờ lâu. Hãy dùng nó cho vài việc quan trọng: giữ khóa, chọn chỉ huy, giữ cái tên là duy nhất. Còn lại, chỉ cần giữ đúng thứ tự trước-sau là đủ. Nhớ nhé: chọn mức vừa đủ, và đừng tự viết lại thứ người ta đã làm tốt.Consistency is not a switch but a priced spectrum. Linearizability sells you the illusion of a single copy and charges in daily latency and in availability when the network breaks — so buy it only for locks, leader election and uniqueness. Causality is far cheaper and fixes most of the bugs users actually see. And when a total order is truly required, you have entered the land of consensus — where total order broadcast and consensus are one, where epochs and quorums keep decisions from being erased, and where the soundest advice is not to write your own.