CAP Theorem — Consistency vs Availability
CAP: khi network partition xảy ra, chỉ được chọn C hoặc A — không có "cả ba" CAP theorem là kết quả của Gilbert và Lynch (formal proof năm 2002 cho conjecture Brewer đưa ra ở PODC keynote 2000): một hệ phân tán có shared state không thể đồng thời cung cấp cả linearizable Consistency , Availability (mọi request tới non-failing node đều trả lời không lỗi), và Partition tolerance khi có network partition. Trong thực tế, partition là thứ sẽ xảy ra — TCP retransmit, GC pause dài, switch chết, cross-region link flap — nên P là ràng buộc bắt buộc, không phải lựa chọn. Câu hỏi thật là: khi partition xảy ra, hệ thống hy sinh C hay A? Chọn sai gây ra hai loại incident khác nhau: chọn AP mà dữ liệu cần linearizable dẫn tới double-charge, oversell inventory, split-brain; chọn CP mà dữ liệu chỉ cần eventually consistent dẫn tới downtime không cần thiết, user không đọc được profile của chính mình. Cơ chế hoạt động Định nghĩa formal theo Gilbert và Lynch: Consistency ở đây là linearizability : mọi read sau một write hoàn tất phải thấy giá trị mới (hoặc mới hơn); tồn tại một total order các operation phù hợp với real-time. Availability : mọi request tới một non-failing node phải nhận response (không timeout, không error). Partition tolerance : hệ thống tiếp tục hoạt động dù network drop tuỳ ý message giữa các node. Proof intuition: giả sử có 2 node N1, N2 giữ cùng key x=0 . Client ghi x=1 vào N1. Link N1 và N2 đứt. Một client khác đọc x từ N2. Nếu N2 trả về 0 thì không linearizable (mất C). Nếu N2 chờ đến khi thấy được N1 thì mất A. Nếu N2 từ chối phục vụ thì cũng mất A. Không có cách thứ ba. Trong hệ CP, mỗi write phải qua quorum (Raft, Paxos, ZAB); khi node bị isolate khỏi quorum, nó từ chối phục vụ để giữ linearizability: // etcd/Raft-style: khi mất quorum, leader step down và write fail resp , err := kv . Put ( ctx , "order/42" , "paid" ) if err != nil { // err là ErrLeaderChanged hoặc context.DeadlineExceeded khi ở minority side // client thấy unavailable — đúng contract CP re