CAP và nhất quán

CAP là gì, nói theo cách thực tế

CAP nói về một hệ thống lưu dữ liệu có nhiều bản sao nằm trên nhiều máy. Ba chữ cái là:

• C (Consistency): hỏi node nào cũng nhận cùng một câu trả lời (Building Microservices); theo Grokking ch.3, một nghĩa khác là mỗi lần đọc nhận được giá trị của lần ghi gần nhất.¹²
• A (Availability): mọi request đều nhận được phản hồi (Building Microservices).¹
• P (Partition tolerance): hệ thống xử lý được việc liên lạc giữa các phần của nó đôi khi không thể.¹

Định lý nói rằng khi có sự cố, bạn chỉ giữ được hai trong ba; vì partition không tránh được trong hệ phân tán nên thực tế là chọn C hoặc A.¹³ Cách diễn đạt "chọn 2 trong 3" dễ gây hiểu nhầm. Trong hệ phân tán thật, partition sẽ xảy ra: switch hỏng, cáp đứt, GC dừng một node 10 giây, một zone mất kết nối. Bạn không được chọn "bỏ P": Building Microservices viết hệ không chịu partition thì không chạy qua mạng được, tức là chỉ còn một process cục bộ, và "CA systems don't exist in distributed systems".³ Các ví dụ cụ thể về nguyên nhân partition (switch hỏng, GC dừng 10 giây) là minh họa của khoá học. Câu hỏi đúng là: khi partition xảy ra, tính năng này nên từ chối request để giữ dữ liệu đúng, hay tiếp tục phục vụ và chấp nhận dữ liệu lệch tạm thời?

Grokking ch.4 nói cùng ý từ góc replication: cập nhật bản sao đồng bộ thì nhất quán mạnh nhưng giảm availability, cập nhật bất đồng bộ thì chấp nhận eventual consistency, đọc có thể cũ cho tới khi các bản sao hội tụ; sách tóm lại là ta đánh đổi availability hoặc consistency khi có lỗi, và đó là nội dung của CAP.⁴

Vì sao quan trọng trong phỏng vấn

Gần như bài thiết kế nào cũng có một câu hỏi về nhất quán, dù người phỏng vấn không nói chữ "CAP":

• Hai người cùng bấm đặt một ghế thì sao?
• Người dùng vừa đăng bài, tải lại trang không thấy bài của mình thì sao?
• Số like hiển thị lệch vài giây có sao không?

Ứng viên yếu trả lời chung cho cả hệ thống: "hệ thống của em là AP". Ứng viên tốt chia theo tính năng: phần giữ chỗ và thanh toán cần nhất quán mạnh, phần feed, đếm view, gợi ý chấp nhận eventual consistency. Việc nói rõ ranh giới này trong bước yêu cầu phi chức năng giúp mọi quyết định sau đó (chọn database, cache, queue) có lý do rõ ràng. Building Microservices cũng nói hệ thống không cần là AP hay CP trọn vẹn: catalog có thể AP, inventory có thể CP, thậm chí một service con vẫn có thể đọc lỏng nhưng cập nhật chặt.⁵

Chuyện gì xảy ra khi mạng bị chia cắt

Lấy một kho có hai bản sao, node 1 ở zone A, node 2 ở zone B. Mạng giữa hai zone đứt. Một client ghi vào node 1, một client khác đọc từ node 2.

• Chọn CP: node 2 không thể phối hợp với node kia để bảo đảm nhất quán nên chỉ còn cách từ chối trả lời; Building Microservices gọi đây là hy sinh availability, hệ thống phải tự tính cách giảm chức năng tới khi partition lành. Người dùng thấy lỗi hoặc phải thử lại.¹
• Chọn AP: node 2 trả về giá trị nó đang có. Người dùng vẫn dùng được, nhưng có thể thấy dữ liệu cũ, và các ghi trong lúc partition phải được đồng bộ lại về sau; partition càng dài thì càng khó. Nếu cả hai phía cùng nhận ghi, khi mạng nối lại phải hòa giải xung đột: Grokking ch.9 nêu tránh xung đột, last-write-wins và logic tùy biến; ch.10 dùng vector clock để phát hiện xung đột.¹⁶⁷ CRDT là cách khác, ngoài thư viện.⁸

Grokking ch.10 thiết kế key-value store theo hướng AP: khi hai node mất liên lạc, cả hai tiếp tục nhận request và đồng bộ lại sau, dùng versioning để xử lý xung đột; chương này dựa trên Dynamo.⁹ Ngược lại, hệ cần nhất quán mạnh cần thêm thuật toán đồng thuận như Paxos và Raft, và Grokking ghi Spanner tuyên bố linearizable cho nhiều thao tác; Building Microservices nhắc Consul là kho key-value nhất quán mạnh.¹⁰¹ Phía thiểu số ngừng phục vụ ghi khi mất đa số là hệ quả của lựa chọn CP (suy luận của khoá học); ZooKeeper, etcd, CockroachDB cụ thể thì thư viện chưa có.¹¹

Chọn CP hay AP theo từng tính năng

Một hệ thống thường có cả hai loại. Bảng dưới là cách chia hay dùng trong các bài của khóa (lựa chọn của khoá học). Nguyên tắc nền theo Building Microservices: AP dễ scale và dễ xây hơn, CP cần nhiều công hơn; nên hỏi bản ghi cũ 5 phút có chấp nhận được không, số dư ngân hàng có thể cũ không, rồi mới chọn.¹²

PACELC: khi mạng bình thường

CAP chỉ nói về lúc có partition. Phần lớn thời gian mạng vẫn ổn, và lúc đó vẫn có một đánh đổi khác. Grokking ch.16 chỉ nhắc ngắn tên "CAP and PACELC theorems" khi nói về replication giữa data center; chi tiết định nghĩa PACELC dưới đây không có trong thư viện.¹³¹⁴ PACELC mở rộng như sau: nếu có Partition, chọn A hoặc C; Else (bình thường), chọn Latency hoặc Consistency.

Lý do: muốn mọi lần đọc thấy dữ liệu mới nhất, lần ghi phải chờ nhiều bản sao xác nhận. Chờ càng nhiều bản sao, càng xa, độ trễ càng cao. Grokking ch.16 nói ghi đồng bộ cho nhất quán mạnh làm tăng độ trễ, và ghi đồng bộ xuyên data center có tác động hiệu năng nghiêm trọng nên thường dùng replication bất đồng bộ giữa các data center.¹⁵

Bảng là phân loại của khoá học. Phần có trong thư viện: Cassandra cung cấp eventual consistency (Grokking ch.3), Spanner tuyên bố linearizable cho nhiều thao tác (ch.3), replication của Redis là bất đồng bộ (Grokking ch.16), replica đọc của RDBMS là eventually consistent (Building Microservices).^16101718 Các hệ còn lại (DynamoDB, CockroachDB, MongoDB readConcern) chưa có sách.¹⁹

Các mức nhất quán thường gặp

"Nhất quán" có nhiều mức. Biết tên từng mức giúp bạn đòi đúng thứ mình cần và không trả giá quá mức. Grokking ch.3 xếp các mô hình từ yếu tới mạnh: eventual, causal, sequential, strict (linearizability); mô hình mạnh hơn đổi lấy hiệu năng và availability kém hơn.²¹⁰

Eventual, causal và strong (linearizable) khớp với các mô hình của Grokking ch.3: eventual đảm bảo mọi bản sao cuối cùng trả cùng giá trị, causal giữ thứ tự các thao tác có quan hệ nhân quả (ví dụ hệ thống comment), linearizable đảm bảo đọc từ bất kỳ replica nào đều thấy lần ghi mới nhất, cần đồng bộ và đồng thuận như Paxos, Raft.¹⁶²⁰¹⁰ Read-your-writes và monotonic reads không có trong thư viện.²¹

Read-your-writes là mức bị quên nhiều nhất và gây lỗi dễ thấy nhất. Người dùng đổi avatar, trang tải lại đọc từ replica chưa cập nhật, avatar cũ hiện ra, người dùng nghĩ hệ thống hỏng. Cách sửa đơn giản: sau khi người dùng ghi, lưu thời điểm ghi vào session, các lần đọc của chính người đó trong 5–10 giây đi thẳng tới primary (kỹ thuật và con số 5–10 giây là của khoá học).²¹

Quorum R + W > N và giá của nhất quán

Quy tắc quorum

Với dữ liệu có N bản sao, mỗi lần ghi chờ W bản sao xác nhận, mỗi lần đọc hỏi R bản sao. Nếu R + W > N, tập đọc và tập ghi luôn giao nhau ít nhất một node, nên lần đọc chắc chắn chạm tới ít nhất một bản sao có giá trị mới nhất. Grokking ch.10 dùng đúng điều kiện này (r + w > n) để cấu hình kho key-value: chọn r và w sao cho có ít nhất một node chung, đảm bảo người đọc thấy giá trị ghi gần nhất.²²

Bảng trên khớp với bảng "Value Effects on Reads and Writes" của Grokking (n=3, r=2, w=2 được phép; r=3, w=1 ghi nhanh đọc chậm; r=1, w=3 đọc nhanh ghi chậm). Dòng n=5 và cột "chịu được bao nhiêu node chết" là suy ra của khoá học.²²

Trong Cassandra, đây là QUORUM cho cả đọc và ghi với RF = 3; quorum chưa đủ để có linearizable khi có ghi đồng thời, muốn compare-and-set đúng cần lightweight transaction (Paxos). Thư viện không có sách về Cassandra nên phần này chỉ giữ ở mức khái niệm.²³

Sloppy quorum và hinted handoff (Grokking ch.10) nới lỏng thêm: n node khoẻ đầu tiên trong preference list xử lý đọc ghi, và nếu node dự định tạm chết thì node thay thế giữ ghi kèm gợi ý rồi chuyển lại khi node cũ sống lại. Đổi lại, điều kiện giao nhau không còn chắc chắn trong lúc sự cố (suy luận của khoá học, vì n node khoẻ có thể không phải n node đầu tiên theo vòng).²⁴

Con số: nhất quán tốn bao nhiêu độ trễ

Mốc của Grokking ch.5: round trip trong cùng data center cỡ 500 µs, gói tin San Francisco tới New York cỡ 71 ms; các dòng còn lại là ước lượng của khoá học, cần đo lại.²⁵

Kết luận thực tế: nhất quán mạnh trong một region gần như miễn phí về độ trễ. Nhất quán mạnh xuyên lục địa đắt, nên chỉ dùng cho phần dữ liệu thật sự cần (số dư, tồn kho), phần còn lại replicate bất đồng bộ (cùng hướng với Grokking ch.16 ở trên).¹⁵

Sai lầm hay gặp

• Gán một nhãn cho cả hệ thống. Chia theo tính năng, như bảng ở trên.⁵
• Nhầm C trong CAP với C trong ACID. C của ACID là dữ liệu ở trạng thái nhất quán sau mỗi transaction (Grokking ch.9). C của CAP là hỏi node nào cũng nhận cùng câu trả lời.²⁶¹
• Đọc từ replica ngay sau khi ghi. Gây lỗi read-your-writes. Đọc lại từ primary hoặc trả luôn dữ liệu vừa ghi trong response.
• Dùng cache mà quên nó cũng là một bản sao. Cache trước database là một nguồn eventual consistency; Grokking ch.16 nhận định ghi bất đồng bộ vào cache làm hệ thống chịu bất nhất.¹⁵ Vé đã bán nhưng cache còn báo "còn ghế" vẫn ổn nếu bước giữ chỗ kiểm tra lại ở database.
• Đòi strong consistency cho đếm like. Trả giá độ trễ và khả năng chịu lỗi cho thứ không ai kiểm tra.
• Không nói cách hòa giải xung đột khi chọn AP. Chọn AP mà cho phép ghi ở hai phía thì phải nói rõ last-write-wins, gộp theo CRDT hay giữ nhiều version (vector clock, Grokking ch.10).⁶⁷

Khi nào nhắc tới trong phỏng vấn

Bảng dưới tóm cách khoá học áp CAP và các mức nhất quán vào từng bài; nguyên tắc nền ở phần trên.⁵²

Đọc tiếp: Tranh chấp tài nguyên cho các kỹ thuật khóa và giữ chỗ, Consistent hashing cho cách đặt bản sao, Cassandra và PostgreSQL cho hai đầu của phổ lựa chọn.

Nguồn trích dẫn

1. Building Microservices (file .zip, tải về giải nén) · ch.11 Microservices at Scale · mục "CAP Theorem" (gồm "Sacrificing Consistency", "Sacrificing Availability") (tr. 232–234). ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

2. Grokking Modern System Design · ch.3 Abstractions · bài về consistency, mục "What is consistency?". ↩ ↩² ↩³

3. Building Microservices (file .zip, tải về giải nén) · ch.11 Microservices at Scale · mục "Sacrificing Partition Tolerance?" (tr. 234–235). ↩ ↩² ↩³

4. Grokking Modern System Design · ch.4 Non-functional System Characteristics · bài "Fault Tolerance", mục "Fault tolerance techniques" → "Replication". ↩

5. Building Microservices (file .zip, tải về giải nén) · ch.11 Microservices at Scale · mục "It's Not All or Nothing" (tr. 235). ↩ ↩² ↩³

6. Grokking Modern System Design · ch.9 Databases · bài "Data Replication", mục "Multi-leader replication" → "Handle conflicts" (Conflict avoidance, Last-write-wins, Custom logic). ↩ ↩²

7. Grokking Modern System Design · ch.10 Key-value Store · bài "Versioning Data and Achieving Configurability", mục "Data versioning". ↩ ↩²

8. Chưa có nguồn trong thư viện: CRDT không có trong các sách của thư viện. ↩

9. Grokking Modern System Design · ch.10 Key-value Store · bài "Ensure Scalability and Replication" (đoạn cuối, về CAP) và Note "based on Dynamo". ↩

10. Grokking Modern System Design · ch.3 Abstractions · bài về consistency, mục "Strict consistency aka linearizability" và "Summary". ↩ ↩² ↩³ ↩⁴

11. Chưa có nguồn trong thư viện: thư viện không có sách về etcd, ZooKeeper (ở mức đồng thuận), CockroachDB; chỉ nêu tên như ví dụ. ↩

12. Building Microservices (file .zip, tải về giải nén) · ch.11 Microservices at Scale · mục "AP or CP?" (tr. 235). ↩

13. Grokking Modern System Design · ch.16 Distributed Cache · bài "Evaluation of a Distributed Cache Design", mục "High availability" (nhắc "CAP and PACELC theorems"). ↩

14. Lý thuyết · PACELC (Daniel Abadi đề xuất): nếu có phân vùng mạng (P) thì phải chọn giữa sẵn sàng (A) và nhất quán (C); nếu không (Else) thì vẫn phải chọn giữa độ trễ thấp (L) và nhất quán (C), vì đồng bộ các bản sao tốn thời gian. PA/EL nghĩa là ưu tiên sẵn sàng khi có phân vùng và ưu tiên độ trễ khi bình thường; PC/EC nghĩa là luôn ưu tiên nhất quán. PACELC bổ sung cho CAP ở chỗ CAP chỉ nói về lúc có lỗi mạng. ↩

15. Grokking Modern System Design · ch.16 Distributed Cache · bài "Evaluation of a Distributed Cache Design", mục "Consistency" và "High availability". ↩ ↩² ↩³

16. Grokking Modern System Design · ch.3 Abstractions · bài về consistency, mục "Eventual consistency". ↩ ↩²

17. Grokking Modern System Design · ch.16 Distributed Cache · bài "Memcached versus Redis", mục "Redis" (replication bất đồng bộ). ↩

18. Building Microservices (file .zip, tải về giải nén) · ch.11 Microservices at Scale · mục về read replicas để scale đọc (tr. 222–223). ↩

19. Chưa có nguồn trong thư viện: phân loại PACELC của DynamoDB, CockroachDB, MongoDB, Postgres chưa có sách tương ứng. ↩

20. Grokking Modern System Design · ch.3 Abstractions · bài về consistency, mục "Causal consistency". ↩

21. Chưa có nguồn trong thư viện: read-your-writes và monotonic reads, cách đạt chúng bằng sticky replica hay đọc từ primary, không có trong các sách của thư viện. ↩ ↩²

22. Grokking Modern System Design · ch.10 Key-value Store · bài "Versioning Data and Achieving Configurability", mục "Usage of r and w". ↩ ↩²

23. Chưa có nguồn trong thư viện: thư viện không có sách về Cassandra (QUORUM, lightweight transaction); phần này chỉ nêu khái niệm. ↩

24. Grokking Modern System Design · ch.10 Key-value Store · bài về fault tolerance, mục "Handle temporary failures" (sloppy quorum, hinted handoff). ↩

25. Grokking Modern System Design · ch.5 Back-of-the-envelope Calculations · mục "Standard numbers to remember", bảng "Important Latencies". ↩

26. Grokking Modern System Design · ch.9 Databases · bài "Types of Databases", mục "Relational databases" (ACID). ↩