Linearizability — nhất quán mạnh và cái giá của nó

TL;DR: Linearizability (nhất quán mạnh) đảm bảo hệ hành xử như thể chỉ có MỘT bản dữ liệu, dù nhân bản trên nhiều node: mỗi thao tác trông như xảy ra tức thời tại một điểm giữa lúc client gửi lệnh và nhận kết quả, và các điểm đó tôn trọng thời gian thực. Hệ quả cốt lõi là recency: đã thấy giá trị mới thì mọi lần đọc sau không bao giờ thấy giá trị cũ. Khác serializability (thứ tự giao dịch, không đòi khớp real-time) — linearizability chỉ một object nhưng có ràng buộc real-time. Cái giá: cần phối hợp giữa bản sao, chậm hơn và mất khả dụng khi mạng phân mảnh — nền cho CAP ở bài sau.

Bạn vừa đổi mật khẩu, hệ báo "thành công". Bạn đăng nhập lại ngay bằng mật khẩu mới — nhưng bị từ chối, vì lần đăng nhập trúng một bản sao chưa kịp nhận cập nhật. Một hệ linearizable cấm đúng tình huống này: đã ghi xong và được xác nhận thì mọi lần đọc sau phải thấy giá trị mới. Đây là đảm bảo mạnh nhất về "mọi người thấy cùng một dữ liệu mới nhất".

Bài này định nghĩa chính xác linearizability, mổ cơ chế khiến nó mạnh (recency qua real-time order), phân biệt nó với serializability (hai khái niệm rất hay bị trộn), và chỉ ra cái giá — mở đường cho CAP và consensus ở các bài sau.

1. Analogy — bảng tỉ số duy nhất trên sân vận động

Trong một trận bóng, cả sân nhìn chung một bảng tỉ số điện tử. Khi trọng tài công nhận bàn thắng, bảng đổi từ 1-0 sang 2-0. Kể từ khoảnh khắc đó, không một ai — khán giả A ở khán đài Bắc, khán giả B ở khán đài Nam — còn thấy 1-0 nữa. Không có chuyện người này thấy 2-0 rồi người kia vẫn thấy 1-0: chỉ có một bảng, một sự thật, và nó nhảy tức thời tại một thời điểm.

Linearizability đem đúng ảo giác đó vào hệ phân tán nhiều bản sao: dù bên trong dữ liệu nằm trên năm máy, người dùng bên ngoài thấy như thể chỉ có một bảng tỉ số.

2. Định nghĩa chính xác — một điểm giữa invoke và response

Mỗi thao tác trong hệ thực chất kéo dài một khoảng thời gian: từ lúc client gửi lệnh (invoke) tới lúc nhận kết quả (response) — vì lệnh phải đi qua mạng, tới bản sao, xử lý, rồi về. Linearizability (Herlihy & Wing, 1990) đòi: tồn tại một cách gán cho mỗi thao tác một điểm duy nhất (linearization point) nằm trong khoảng của nó, sao cho:

1. Nếu ta sắp các thao tác theo các điểm đó thành một dãy tuần tự, kết quả hợp lệ như một bản dữ liệu đơn (đọc trả về giá trị của lần ghi gần nhất trước nó).
2. Thứ tự các điểm tôn trọng real-time: nếu thao tác X kết thúc (response) trước khi thao tác Y bắt đầu (invoke), thì điểm của X phải đứng trước điểm của Y.

Điều kiện (2) là thứ khiến linearizability mạnh hơn các mô hình khác: nó gắn thứ tự logic với thời gian thực. Hệ quả trực tiếp là recency guarantee — một khi lần ghi x=2 đã response, mọi lần đọc bắt đầu sau đó phải thấy 2 (hoặc mới hơn), không được thấy 1.

3. Cơ chế — worked example: lịch sử này có linearizable không?

Cách chắc nhất để "thấy" định nghĩa là chấm một lịch sử thao tác cụ thể. Xét một thanh ghi x (khởi tạo 0), ba client thao tác đồng thời. Mỗi thanh ngang là khoảng invoke → response:

Thoi gian ---->

A:  write(x=1) |=========|                       (ghi 1)
B:            |===== read -> ? =====|             (doc, chong len ghi cua A)
C:                          |== read -> ? ==|     (doc, bat dau SAU khi A xong)

Ta lần theo hai điều kiện của mục 2 để chấm:

• C bắt đầu SAU khi A response → theo real-time order, điểm của write(x=1) phải đứng trước điểm của C. Vậy C bắt buộc đọc 1. Nếu C đọc 0 → KHÔNG linearizable (vi phạm recency).
• B chồng lên A (concurrent) → điểm của B có thể rơi trước hoặc sau điểm ghi. Nên B đọc 0 hoặc 1 đều hợp lệ — miễn là nhất quán với ràng buộc tiếp theo.
• Ràng buộc chốt: không được lùi. Nếu B đọc 1 (nghĩa là điểm ghi đã "xảy ra" trước điểm của B), thì C — bắt đầu còn sau nữa — không thể đọc 0. Một khi giá trị mới lộ ra, nó không quay lại được.

Ta tìm được một cách đặt điểm hợp lệ (ví dụ: điểm ghi giữa khoảng A, B đọc 1, C đọc 1) → lịch sử này linearizable. Nhưng nếu quan sát thực tế là B=1, C=0, không cách đặt điểm nào cứu được → không linearizable.

Điểm mấu chốt của cơ chế: mỗi thao tác "nhảy" từ giá trị này sang giá trị kia tại một thời điểm, và cả hệ đồng ý về thứ tự các bước nhảy đó — đúng như bảng tỉ số. Để đạt điều này với nhiều bản sao, hệ phải phối hợp: một lần đọc không thể trả lời từ một bản sao cũ mà chưa chắc mình có giá trị mới nhất; nó phải đồng bộ với các bản khác (hoặc đọc qua leader/quorum có đọc-sửa). Chính bước phối hợp đó là nguồn của cái giá ở mục 5.

4. Linearizability KHÁC serializability thế nào?

Hai từ nghe giống nhau nhưng là hai trục hoàn toàn khác — trộn chúng là lỗi kinh điển.

Nói ngắn: serializability (đã học ở Module 4) bảo "các giao dịch không giẫm chân nhau, kết quả như một lịch tuần tự nào đó" — nhưng lịch nào thì không cần khớp thời gian thực. Linearizability bảo "mỗi thao tác lên một object thấy giá trị mới nhất theo đồng hồ tường". Một hệ có thể serializable mà không linearizable (ví dụ Serializable Snapshot Isolation — SSI — đọc từ một snapshot nhất quán chứ không phải giá trị mới nhất), và ngược lại. Khi cần cả hai — giao dịch tuần tự và khớp thời gian thực — ta nói strict serializability.

5. Cái giá — vì sao nhất quán mạnh thì đắt?

Recency không miễn phí. Để mọi lần đọc thấy giá trị mới nhất, một bản sao không được tự tin trả lời từ dữ liệu cục bộ có thể đã cũ; nó phải phối hợp — hỏi leader, hoặc đọc/ghi qua quorum có đồng bộ, hoặc chạy một giao thức consensus. Ba hệ quả:

1. Chậm hơn (latency): mỗi thao tác gánh thêm ít nhất một vòng đi-về mạng để phối hợp, thay vì trả lời ngay từ bản gần nhất.
2. Kém chịu lỗi khi mạng phân mảnh (availability): nếu một bản sao bị cắt khỏi phần còn lại (network partition), nó không thể biết chắc mình có giá trị mới nhất → để giữ linearizability, nó phải từ chối phục vụ thay vì trả lời liều. Đây chính là đánh đổi C-vs-A của định lý CAP — bài 03.
3. Không phải lúc nào cũng cần: rất nhiều tính năng (số like, feed, gợi ý) chịu được dữ liệu trễ vài giây. Áp linearizability lên chúng là trả giá đắt cho một đảm bảo không dùng đến.

Vì vậy linearizability là công cụ dành cho chỗ thật sự cần "một sự thật mới nhất": khoá phân tán, bầu leader, số dư tài khoản khi ràng buộc cứng, uniqueness constraint. Những mức yếu hơn mà rẻ hơn (như causal consistency, bài 02) đủ cho phần còn lại.

6. Pitfall — nhầm linearizability với serializability, và "quorum là đủ"

❌ "He serializable roi thi doc luon thay gia tri moi nhat"
   -> SAI: serializability khong rang buoc real-time; mot giao dich
   co the doc snapshot cu van "tuan tu hop le". Recency la linearizability.

❌ "Quorum read/write (w + r > n) => linearizable"
   -> KHONG du: quorum chong mat ghi, nhung do dinh thoi (doc chay song song
   voi ghi chua kip lan toi) van co the tra ve gia tri cu. Can them dong bo
   (read-repair dong bo / doc qua leader) moi dat linearizable.

7. 📚 Đào sâu — nguồn gốc & tài liệu

8. Liên hệ các bài khác

• Bài 02 — Causal consistency: mức yếu hơn ngay dưới linearizability — bỏ ràng buộc total order/real-time để đổi lấy khả dụng khi partition; đọc để thấy "rẻ hơn" nghĩa là gì.
• Bài 03 — CAP đúng nghĩa: "kém khả dụng khi partition" ở mục 5 chính là nửa C của CAP — bài 03 hình thức hoá đánh đổi đó.
• Module 2 — Leaderless replication: quorum w + r > n được mổ ở đó; bài này chỉ ra vì sao quorum một mình chưa đạt linearizability.
• Module 4 — Anomaly & serializability: trục còn lại (isolation của giao dịch) — đối chiếu để không trộn hai khái niệm.

9. Tóm tắt

• Chấm một lịch sử = tìm cách đặt linearization point cho mọi thao tác thoả cả hai điều kiện; đọc sau một ghi đã xong thì bắt buộc thấy giá trị mới.
• Khác serializability: một object + real-time (linearizability) vs nhiều giao dịch + "tuần tự nào đó" (serializability); cả hai = strict serializability.
• Cái giá: phối hợp giữa bản sao → chậm + mất khả dụng khi partition; chỉ nên bật ở chỗ cần recency thật (khoá, leader, uniqueness).
• Pitfall: nhầm với serializability; tưởng quorum một mình là đủ cho nhất quán mạnh.

10. Tự kiểm tra

Bài tiếp theo: Causal consistency — yếu hơn nhưng đủ, rẻ hơn