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
    return fmt.Errorf("cluster lost quorum: %w", err)
}

Trong hệ AP, node minority vẫn nhận write, gắn version vector / vector clock, đồng bộ sau khi partition heal — có thể conflict và cần resolution (last-write-wins, CRDT, application merge):

# Cassandra: tunable consistency, ONE cho phép write vào node đơn lẻ
session.execute(
    "INSERT INTO cart (user_id, item, qty) VALUES (%s, %s, %s)",
    (user_id, item, qty),
    consistency_level=ConsistencyLevel.ONE,   # AP-style, vẫn ghi khi partition
)
# read sau đó với ONE có thể trả về giá trị cũ ở replica khác

Brewer viết lại năm 2012 (bài "CAP Twelve Years Later" trên IEEE Computer) rằng framing "chọn 2 trong 3" gây hiểu lầm: partition hiếm, và ngay cả một service cũng có thể là CP cho một số operation (thanh toán) và AP cho operation khác (đếm view). CAP là quyết định per-operation, không phải per-system.

Vấn đề gặp trong production

Failure mode 1: giả định là CA (có cả ba) trong một hệ phân tán. Đây là cái bẫy phổ biến nhất. Team dùng Postgres primary cộng read replica, viết code như thể replica luôn có dữ liệu mới nhất:

# SAI — assume read-after-write consistency across replicas
def create_order_and_show(user_id, items):
    order_id = primary.execute("INSERT INTO orders ... RETURNING id", ...)
    # ngay lập tức đọc từ replica để hiển thị
    order = replica.execute("SELECT * FROM orders WHERE id = %s", order_id)
    return order  # None khi replication lag lớn hơn round-trip

Khi replication lag tăng (batch load, network hiccup), order trả về None. Bug này không hiện trong staging vì lag ở đó thường rất nhỏ. Cách sửa: read-your-writes bằng cách đọc lại từ primary sau khi write, hoặc dùng session token / GTID để wait cho replica bắt kịp, hoặc chấp nhận eventual consistency và render optimistic từ input.

# ĐÚNG — đọc lại từ primary trong cùng transaction
def create_order_and_show(user_id, items):
    with primary.transaction() as tx:
        order_id = tx.execute("INSERT INTO orders ... RETURNING id", ...)
        order = tx.execute("SELECT * FROM orders WHERE id = %s", order_id)
    return order

Failure mode 2: chọn AP cho use case cần linearizable. Kinh điển: dùng DynamoDB eventually-consistent read hoặc Cassandra ONE cho counter tồn kho, kết quả oversell. Hai request cùng thấy stock=1, cả hai decrement, cuối cùng stock=-1. Postmortem loại này lặp đi lặp lại trong các báo cáo Jepsen của Kyle Kingsbury: Riak, Cassandra, MongoDB (khi chưa dùng majority write concern và linearizable read concern) đều bị bắt lỗi consistency claim.

// SAI — Cassandra ONE cho inventory decrement, không linearizable
session.execute("UPDATE inventory SET stock = stock - 1 WHERE sku = ?", sku);

// ĐÚNG — dùng lightweight transaction (Paxos) khi cần compare-and-set
session.execute(
    "UPDATE inventory SET stock = ? WHERE sku = ? IF stock = ?",
    newStock, sku, currentStock
);  // trả về applied=false nếu ai đó đã ghi trước — retry

Failure mode 3: chọn CP nhưng không lường được blast radius khi mất quorum. GitHub công bố postmortem về một sự cố cross-DC partition ngắn (dưới một phút) trong tháng 10 năm 2018 khiến MySQL Orchestrator promote replica ở DC khác; khi link phục hồi, có writes ở hai phía — team chọn ưu tiên consistency, dừng writes để reconcile thủ công, chấp nhận degradation kéo dài nhiều giờ. Đó là quyết định CP đúng nhưng cost cao. Nhiều team gặp incident tương tự với Consul, etcd, Zookeeper cluster khi cross-AZ latency spike làm minority partition từ chối phục vụ; nếu health check của app không phân biệt "cluster down" với "cluster unavailable to me", cả service tier bị đánh dấu unhealthy.

Failure mode 4: split-brain do quorum sai. Cluster 2 node với "majority = 1" là công thức split-brain. Khi partition xảy ra, cả hai bên đều nghĩ mình là majority. Đây là lý do Raft/ZAB yêu cầu odd number of voting member và các hệ như etcd, Consul cảnh báo rõ ràng khi số voter chẵn. Với 3 node chịu mất được 1; với 5 node chịu mất được 2 — đó là tradeoff giữa fault tolerance và write latency (quorum càng lớn càng chậm).

Cách debug và monitor

Triệu chứng partition thường bị chẩn đoán nhầm thành "database chậm". Cần phân biệt:

• Cluster health metric: etcd_server_has_leader, etcd_server_leader_changes_seen_total, consul.raft.leader.lastContact, MongoDB rs.status() — thay đổi state đột ngột là dấu hiệu leader election, thường do partition.
• Replication lag: Postgres pg_stat_replication.replay_lag, MySQL SHOW SLAVE STATUS với Seconds_Behind_Master, Kafka consumer lag. Lag tăng đột ngột trên tất cả replica cùng lúc là network issue, không phải replica chậm.
• Quorum loss log: etcd log lost quorum, Zookeeper chuyển LEADING sang LOOKING, Consul raft: heartbeat timeout — những dòng này phải được alert.
• Client-side symptom: tỷ lệ context.DeadlineExceeded hoặc NoHostAvailable tăng đột biến trên một subset client (một AZ), trong khi các AZ khác ổn — partial partition.
• Consistency test: chạy Jepsen (framework của Kyle Kingsbury) hoặc elle để verify hệ mình dùng có giữ contract quảng cáo không. Nhiều DB đã bị Jepsen bắt lỗi consistency claim, kết quả được document công khai trên jepsen.io.

Rule phòng ngừa:

• Không deploy quorum-based cluster với số voter chẵn.
• Đặt cluster member ở ít nhất 3 failure domain (AZ) khác nhau; tránh 2-DC setup nếu cần CP.
• Health check của app phải phân biệt "tôi không tới được DB" với "DB down globally"; không cascade fail cả tier khi chỉ minority-side unhealthy.
• Test partition trong staging bằng tc qdisc (drop packet), iptables -A INPUT -s <peer> -j DROP, hoặc chaos tool (Toxiproxy, Chaos Mesh).

Tradeoff

CP đổi availability lấy correctness: khi partition, minority side từ chối phục vụ, client thấy error, nhưng không bao giờ có hai giá trị mâu thuẫn cùng tồn tại. Phù hợp cho money, inventory, unique constraint (username, order ID), config store, service discovery — nơi trả về stale hoặc conflict tệ hơn trả về error. Cost: write latency cao hơn (phải wait quorum ack), và availability giảm đúng bằng xác suất mất quorum.

AP đổi consistency lấy uptime: mọi replica vẫn nhận request khi partition, đồng bộ sau. Phù hợp cho shopping cart (merge được), social feed, view counter, log ingestion, DNS-style lookup — nơi stale trong vài giây chấp nhận được và downtime tệ hơn. Cost: application phải handle conflict resolution (CRDT, LWW, user chọn merge), read có thể thấy giá trị cũ, monotonic guarantee yếu.

PACELC (Daniel Abadi, 2010) mở rộng CAP: Partition thì chọn A hay C; Else thì chọn Latency hay Consistency. Kể cả khi không có partition, việc chờ replica ack (strong consistency) vẫn thêm latency; nhiều hệ (DynamoDB, Cassandra) chọn EL — hy sinh consistency lấy latency thấp ngay cả trong điều kiện bình thường.

Rule of thumb: quyết định per-operation, không per-system. Money / inventory / unique ID chọn CP path (Raft-backed store, LWT, transactional DB với SERIALIZABLE). Feed / cart / counter / cache chọn AP path (eventual, CRDT hoặc idempotent merge). Không viết code như thể hệ CA tồn tại — nó không tồn tại trong hệ phân tán thật.

Câu hỏi phỏng vấn

CAP theorem nói gì, và tại sao "chọn 2 trong 3" là cách phát biểu sai? Cho một use case cụ thể để minh hoạ khi nào chọn CP, khi nào chọn AP.

CAP (Gilbert và Lynch, 2002, formal hoá conjecture của Brewer 2000) chứng minh rằng trong hệ phân tán có shared state, khi network partition xảy ra không thể đồng thời giữ linearizable consistency và availability (mọi request tới non-failing node đều nhận response). "Chọn 2 trong 3" gây hiểu lầm vì Partition tolerance không phải lựa chọn — network sẽ partition (TCP timeout, GC pause, switch chết); nếu hệ thống không tolerate partition, nó không phải hệ phân tán. Câu hỏi thật là khi partition xảy ra, hy sinh C hay A. Ví dụ: hệ thanh toán và inventory phải CP — dùng Postgres transactional hoặc Raft-backed store (etcd, Spanner-style); khi minority side mất quorum, nó từ chối write, client thấy error, nhưng không có double-charge hay oversell. Ngược lại, shopping cart hoặc social feed nên AP — Cassandra hoặc DynamoDB eventually consistent, merge conflict bằng CRDT hoặc LWW; user vẫn add item được khi partition, đồng bộ sau. Điểm ăn điểm là: nêu Brewer 2012 clarification rằng CAP là quyết định per-operation không per-system; đề cập PACELC — kể cả khi không partition vẫn có tradeoff latency-vs-consistency; kể failure mode thật — giả định CA gây bug read-after-write khi có replication lag, chọn AP cho inventory gây oversell (Jepsen documented cho nhiều DB), chọn CP không lường quorum loss gây incident kiểu GitHub tháng 10 năm 2018 (partition ngắn nhưng downtime dài để reconcile).

Hands-on

Dựng một cluster etcd 3 node local qua Docker để tận mắt quan sát hành vi CP khi partition. Tạo file docker-compose.yml:

version: "3"
services:
  etcd1:
    image: quay.io/coreos/etcd:v3.5.9
    command: >
      etcd --name etcd1
      --initial-advertise-peer-urls http://etcd1:2380
      --listen-peer-urls http://0.0.0.0:2380
      --advertise-client-urls http://etcd1:2379
      --listen-client-urls http://0.0.0.0:2379
      --initial-cluster etcd1=http://etcd1:2380,etcd2=http://etcd2:2380,etcd3=http://etcd3:2380
      --initial-cluster-state new
      --initial-cluster-token cap-lab
    ports:
      - "2379:2379"
  etcd2:
    image: quay.io/coreos/etcd:v3.5.9
    command: >
      etcd --name etcd2
      --initial-advertise-peer-urls http://etcd2:2380
      --listen-peer-urls http://0.0.0.0:2380
      --advertise-client-urls http://etcd2:2379
      --listen-client-urls http://0.0.0.0:2379
      --initial-cluster etcd1=http://etcd1:2380,etcd2=http://etcd2:2380,etcd3=http://etcd3:2380
      --initial-cluster-state new
      --initial-cluster-token cap-lab
  etcd3:
    image: quay.io/coreos/etcd:v3.5.9
    command: >
      etcd --name etcd3
      --initial-advertise-peer-urls http://etcd3:2380
      --listen-peer-urls http://0.0.0.0:2380
      --advertise-client-urls http://etcd3:2379
      --listen-client-urls http://0.0.0.0:2379
      --initial-cluster etcd1=http://etcd1:2380,etcd2=http://etcd2:2380,etcd3=http://etcd3:2380
      --initial-cluster-state new
      --initial-cluster-token cap-lab

Chạy và verify leader:

docker compose up -d
docker compose exec etcd1 etcdctl \
  --endpoints=http://etcd1:2379,http://etcd2:2379,http://etcd3:2379 \
  endpoint status --write-out=table
docker compose exec etcd1 etcdctl put /order/42 paid
docker compose exec etcd1 etcdctl get /order/42

Tạo partition bằng cách cắt etcd1 khỏi hai node còn lại (etcd1 rơi vào minority):

docker network disconnect cap-lab_default cap-lab-etcd1-1
# hoặc dùng iptables trong container để drop packet tới etcd2, etcd3

Thử write vào minority side — quan sát nó fail sau election timeout:

docker compose exec etcd1 etcdctl --command-timeout=5s put /order/43 attempted
# expected: context deadline exceeded — CP behavior đúng

Thử write vào majority side (etcd2 hoặc etcd3) — vẫn chạy:

docker compose exec etcd2 etcdctl put /order/43 paid
docker compose exec etcd2 etcdctl get /order/43

Heal partition và verify etcd1 catch up:

docker network connect cap-lab_default cap-lab-etcd1-1
sleep 5
docker compose exec etcd1 etcdctl get /order/43   # thấy giá trị từ majority

Sau đó lặp lại thí nghiệm với một AP store (Cassandra 3-node) để so sánh. Dùng docker compose với image cassandra:4.1, tạo keyspace với replication_factor = 3, ghi bằng CONSISTENCY ONE khi partition, quan sát mỗi node có thể trả về giá trị khác nhau, rồi resolve sau khi heal. So sánh hai hành vi trên cùng một scenario: etcd từ chối write ở minority (CP), Cassandra chấp nhận write ở mọi node (AP) — chính là tradeoff C-vs-A trong thực tế.