Quorum — nhất quán đọc/ghi với R+W>N

TL;DR: Trong hệ thống replicate dữ liệu lên N node, đọc chờ R bản phản hồi và ghi chờ W bản xác nhận. Nếu R + W > N, tập đọc và tập ghi luôn giao nhau ít nhất một node — node đó chắc chắn có phiên bản mới nhất, đảm bảo đọc không bao giờ thấy dữ liệu cũ. Đây gọi là quorum. Điều chỉnh R và W theo yêu cầu: W=1 cho ghi nhanh, R=N cho đọc luôn mới nhất, hoặc W=R=⌊N/2⌋+1 cho cân bằng. Khi có partition (mạng bị chia), buộc phải chọn giữa consistency và availability — đây là bản chất CAP theorem.

Hệ thống lưu trữ hồ sơ bệnh nhân của bạn replicate mỗi bản ghi lên 3 node (N=3). Bác sĩ cập nhật liều thuốc của bệnh nhân (write). Hai giây sau, y tá đọc hồ sơ trên máy khác. Nếu hệ thống không có cơ chế quorum, y tá có thể đọc liều cũ từ node chưa nhận được update — hậu quả nghiêm trọng. Bài này giải thích cơ chế toán học đảm bảo điều đó không xảy ra.

1. Replication và bài toán consistency

Replication là việc lưu cùng một dữ liệu trên nhiều node để tăng availability và throughput đọc. Với N=3 replica:

• Khi write "liều = 500mg": gửi tới cả 3 node.
• Nếu network chậm, node3 nhận update muộn hơn 2 giây so với node1 và node2.
• Trong khoảng 2 giây đó, ai đọc từ node3 thấy "liều = 300mg" (giá trị cũ).

Đây gọi là eventual consistency — cuối cùng tất cả node đồng thuận, nhưng trong thời gian trung gian có sự không nhất quán. Với dữ liệu không quan trọng (like count trên mạng xã hội), acceptable. Với dữ liệu y tế, không chấp nhận được.

Câu hỏi: có cách nào đảm bảo đọc thấy write mới nhất mà không cần chờ tất cả N node xác nhận (vì như vậy quá chậm và không fault-tolerant)?

2. Quorum — giao điểm đọc/ghi

Định nghĩa: với N replica, write được coi là thành công khi W node xác nhận; read trả về kết quả khi R node phản hồi.

Điều kiện quorum: nếu R + W > N, tập W node được ghi và tập R node được đọc phải giao nhau ít nhất 1 node. Node đó chứa write mới nhất → read sẽ thấy giá trị đó (sau khi so sánh version).

Chứng minh ngắn: giả sử ngược lại — tập W và tập R không giao nhau. Vậy |W| + |R| ≤ N, tức R + W ≤ N — mâu thuẫn với giả thiết R + W > N. Vậy tập giao không rỗng.

flowchart TB
    subgraph Write["Ghi (W=2 trên N=3)"]
        WC["Client ghi"] --> WN1["Node 1 ✓"]
        WC --> WN2["Node 2 ✓"]
        WC -.->|"chưa đến"| WN3["Node 3 ✗"]
    end
    subgraph Read["Đọc (R=2 trên N=3)"]
        RC["Client đọc"] --> RN2["Node 2 ✓"]
        RC --> RN3["Node 3 ✓"]
        RC -.->|"bỏ qua"| RN1["Node 1 ✗"]
    end
    WN2 -->|"Node 2 là giao điểm"| RN2

Trong sơ đồ trên: Write đến Node 1 và Node 2 (W=2). Read hỏi Node 2 và Node 3 (R=2). Node 2 là giao điểm — nó có write mới nhất, đảm bảo read thấy giá trị đúng.

3. Pseudocode — read/write với quorum

-- Ghi với quorum (W acks cần thiết)
function quorumWrite(key, value, version, nodes, W):
    acks <- 0
    for each node in nodes:
        gửi WriteRequest(key, value, version) tới node không đồng bộ
    -- chờ đủ W ack
    while acks < W:
        response <- chờ ack tiếp theo (có timeout)
        if response.ok:
            acks <- acks + 1
        if timeout hoặc tất cả node đã phản hồi mà acks < W:
            return ERROR_WRITE_QUORUM_NOT_MET
    return SUCCESS
// Time: O(W) ack chờ đợi  Space: O(N) buffer responses

-- Đọc với quorum (R responses cần thiết)
function quorumRead(key, nodes, R):
    responses <- []
    for each node in nodes:
        gửi ReadRequest(key) tới node không đồng bộ
    -- chờ đủ R phản hồi
    while responses.length < R:
        response <- chờ response tiếp theo (có timeout)
        if response.ok:
            responses.append(response)
        if timeout hoặc tất cả node đã phản hồi mà responses.length < R:
            return ERROR_READ_QUORUM_NOT_MET
    -- chọn phiên bản mới nhất trong R responses
    return max(responses, by = version)
// Time: O(R) responses  Space: O(R) buffer

Dòng max(responses, by = version) là then chốt: trong R responses, mỗi node trả về (value, version). Node trong giao điểm đọc/ghi có version cao nhất → client chọn đúng giá trị mới nhất. Version thường là timestamp (Lamport clock) hoặc vector clock (bài 04).

3.1 Ví dụ cụ thể N=3, R=2, W=2

R=2, W=2, N=3: R+W=4 > N=3 → quorum đảm bảo. Node 2 có trong cả tập ghi lẫn tập đọc.

4. Tunable consistency — đánh đổi theo yêu cầu

Điều chỉnh R và W cho các use case khác nhau:

Với N=3: R=W=2 (⌊3/2⌋+1=2). Tolerate 1 node failure: ngay cả khi 1 node chết, 2 node còn lại đủ để đạt quorum.

5. Quorum và CAP theorem

CAP theorem phát biểu: một hệ thống phân tán không thể đồng thời đảm bảo cả ba tính chất — Consistency (đọc thấy write mới nhất), Availability (mọi request đều nhận response), Partition tolerance (hệ thống tiếp tục hoạt động khi network bị chia).

Trong thực tế, network partition là điều không thể tránh (P phải giữ). Vậy phải chọn giữa C và A:

flowchart LR
    P["Network Partition\n(bắt buộc xảy ra)"] --> CHOICE{"Chọn C hay A?"}
    CHOICE -->|"Chọn C"| CP["CP System\nTừ chối serve\nkhi không đạt quorum\n(Zookeeper, etcd, HBase)"]
    CHOICE -->|"Chọn A"| AP["AP System\nVẫn serve dù stale\ndata (Cassandra,\nDynamo, CouchDB)"]

Khi partition xảy ra và quorum không đạt được:

• CP (chọn C): trả lỗi, từ chối request. Đúng data hoặc không có gì.
• AP (chọn A): vẫn trả response từ node available, dù có thể stale. Sai data hơn là không có gì.

Cassandra mặc định AP: với CONSISTENCY ONE, vẫn serve kể cả khi partition. Với CONSISTENCY QUORUM, nó có thể fail nếu partition chia đôi cluster — hành xử như CP.

6. Vấn đề version — cần vector clock

Quorum dùng version để chọn giá trị mới nhất trong R responses. Nhưng với write đồng thời từ nhiều client, timestamp đơn giản có thể sai: hai client ghi cùng lúc trên đồng hồ server khác nhau vài millisecond → thứ tự thực sự không được bảo toàn.

Vector clock (bài 04) giải quyết vấn đề này: thay vì một số timestamp, mỗi event mang một vector (một số/node), cho phép xác định quan hệ nhân quả chính xác — "write A xảy ra trước write B", "A và B đồng thời" (conflict cần resolve). Đây là bước tự nhiên tiếp theo sau quorum.

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

• Consistent hashing: quyết định key nào vào node nào (routing). Quorum quyết định cần bao nhiêu node xác nhận để đảm bảo consistency. Hai kỹ thuật cùng nhau tạo nền tảng Dynamo-style storage.
• Vector clock: cơ chế version chính xác hơn timestamp đơn giản — cần thiết khi có write đồng thời từ nhiều client. Quorum phát hiện có conflict, vector clock giúp resolve conflict đó.
• Gossip protocol: trong AP systems, sau khi quorum write thành công (W acks), các node còn lại nhận update qua gossip — đây là cơ chế anti-entropy đảm bảo eventual consistency.
• Case study Cassandra & etcd: Cassandra (AP, tunable) và etcd (CP, Raft-based) là hai cực của design space — xem cách chúng triển khai quorum/consensus trong production.

📚 Deep Dive

Tóm tắt

• Replication lên N node tăng availability nhưng tạo ra inconsistency window khi node nhận update chậm hơn.
• Quorum: write chờ W ack, read chờ R response. Nếu R+W > N, tập đọc và tập ghi luôn giao nhau ≥1 node.
• Node giao điểm có write mới nhất → client chọn max(version) trong R responses để đọc đúng.
• Tunable: W=1 (ghi nhanh), R=N (đọc luôn mới nhất), R=W=⌊N/2⌋+1 (cân bằng, tolerate ⌊N/2⌋ failure).
• CAP theorem: khi partition xảy ra, chọn C (từ chối request, CP) hoặc A (serve stale data, AP).
• Version bằng timestamp đơn giản không đủ khi có write đồng thời — cần vector clock (bài 04).

Tự kiểm tra

Bài tiếp theo: Merkle tree — phát hiện khác biệt hiệu quả