Định lý CAP

Tình huống: mất liên lạc giữa hai AZ đúng lúc flash sale

Dịch vụ tồn kho gdev-stock của gdev-shop chạy ở hai AZ, mỗi AZ có một bản dữ liệu. Trong đợt flash sale, đường mạng giữa hai AZ đứt 3 phút. Mỗi AZ vẫn sống, vẫn nhận request từ khách, nhưng hai bên không còn thấy nhau.

Còn đúng 5 sản phẩm trong kho. Có hai cách đối xử với khách trong 3 phút đó. Cách một: từ chối đặt hàng cho tới khi mạng nối lại, khách thấy lỗi nhưng không bán lố. Cách hai: cứ nhận đơn ở cả hai phía, khách vui, nhưng có thể mỗi phía bán hết 5 sản phẩm và bạn thiếu hàng thật. Không có cách thứ ba vừa luôn trả lời, vừa luôn đúng.

Đó là nội dung của định lý CAP. Bài này phát biểu nó cho đúng, chỉ ra những điều nó không nói, rồi cho bạn chạy một mô phỏng nhỏ để thấy hai cách hỏng khác nhau.

Sau bài này bạn làm được các việc sau:

• Phát biểu CAP chính xác, và giải thích vì sao "chọn 2 trong 3" là cách nói sai lệch.
• Quyết định hành vi khi có partition cho từng thao tác của hệ thống, kèm hậu quả vận hành.
• Giải thích vì sao cụm có quorum (đa số) vẫn phục vụ được ở phía đông hơn, và vì sao số node nên lẻ.
• Đọc tài liệu chính thức của một hệ dữ liệu và tìm ra nó xử lý partition như thế nào.

Bạn cần có sẵn: Python 3 và curl, đã đọc bài Availability. Bài này tách rõ: availability trong CAP là một khái niệm hẹp hơn tỷ lệ phần trăm uptime đã học ở bài trước.

Ba mô hình cần nhớ

1. Partition là sự kiện, không phải lựa chọn: mạng giữa các node sẽ đứt hoặc chậm đến mức coi như đứt. Thứ bạn chọn là hệ thống làm gì lúc đó: từ chối hay chấp nhận rồi tự lệch.
2. Lựa chọn nằm ở từng thao tác: đọc số dư, ghi đơn hàng, tăng bộ đếm lượt xem có thể chọn khác nhau, thậm chí cùng một hệ dữ liệu cho chọn từng request.
3. Đa số quyết định ai được tiếp tục: với quorum, chỉ phía có hơn một nửa node được ghi. Đó là cách hệ nhất quán vẫn chạy được lúc đứt mạng.

Phát biểu định lý cho đúng

Ba chữ cái, mỗi chữ có nghĩa hẹp hơn đời thường:

Định lý do Eric Brewer đưa ra như giả thuyết và Seth Gilbert cùng Nancy Lynch chứng minh năm 2002 cho mô hình trên. Phát biểu đúng: khi có partition, hệ thống không thể đồng thời bảo đảm C và A.

Vì sao? Hai node A và B không liên lạc được. Một lần ghi đến A. Nếu A phản hồi thành công, B không biết, nên đọc từ B sẽ thấy giá trị cũ và vi phạm C. Nếu A từ chối, hoặc chờ B, thì request này không có phản hồi hợp lệ và vi phạm A. Không còn lối thoát thứ ba.

Ba điều cần sửa trong cách hiểu "chọn 2 trong 3":

• P không phải thứ bạn bỏ được. Mạng thật có thể đứt. Hệ thống một node thì không có partition nhưng cũng không phải hệ phân tán. Vì vậy lựa chọn thực tế là C hay A khi có partition.
• Khi mạng ổn, bạn không phải hy sinh gì về mặt định lý. Nhưng vẫn có đánh đổi giữa độ trễ và độ nhất quán, được mô tả trong mô hình mở rộng PACELC của Daniel Abadi. Đây chỉ là con trỏ để bạn tìm đọc thêm, bài này không đi sâu.
• CAP không nói gì về độ bền dữ liệu, hiệu năng hay đúng sai của nghiệp vụ. Chữ C trong CAP cũng khác chữ C trong ACID của giao dịch: ACID nói về ràng buộc dữ liệu, CAP nói về việc các bản sao thống nhất với nhau.

Một lưu ý về chữ A: availability ở đây là "mọi request tới node sống đều được trả lời", rất khác SLO 99,9% đo theo thời gian ở bài trước. Một hệ thống CAP-available vẫn có thể trả lời sai hoặc chậm 30 giây.

Điều gì xảy ra với một lần ghi lúc đứt mạng

Dự đoán trước khi xem sơ đồ: node A nhận lệnh ghi stock=9 nhưng không liên lạc được node B. Về nguyên tắc A có bao nhiêu hướng xử lý, và mỗi hướng để lại món nợ gì?

Cách đọc sơ đồ:

• Nhánh trên cùng là ngày thường: A liên lạc được các bản sao, ghi xong rồi mới xác nhận. Không có đánh đổi gì lộ ra.
• Nhánh consistency first trả lỗi cho khách. Món nợ là availability: khách thấy lỗi, đơn hàng mất, người trực bị gọi. Ưu điểm là dữ liệu không bao giờ tự mâu thuẫn.
• Nhánh availability first xác nhận ngay. Món nợ chuyển sang phía sau: hai phía có hai sự thật khác nhau, và khi mạng nối lại phải có quy tắc hòa giải. Quy tắc phổ biến là "bản ghi mới nhất thắng" (last write wins), nghĩa là một lần ghi bị thay thế mà không ai báo.
• Kết luận cho vận hành: từ chối là lỗi bạn thấy ngay trên dashboard, còn chấp nhận rồi lệch là lỗi bạn chỉ phát hiện muộn qua phàn nàn của khách. Cả hai đều cần được thiết kế trước, không thể để mặc định.

Quorum: lối thoát để hệ nhất quán vẫn phục vụ được

Mô phỏng ở phần lab chỉ có hai node nên khi mất liên lạc, cả hai đều phải từ chối. Cụm thật dùng ba, năm node và quy tắc quorum: một thao tác ghi chỉ được chấp nhận khi hơn một nửa số node đồng ý. Phía đông hơn của partition tiếp tục chạy, phía ít hơn từ chối.

Hệ quả vận hành rất thực: cụm etcd của Kubernetes có 3 node trải trên 2 AZ, mỗi AZ 2 và 1 node. Nếu AZ chứa 2 node mất kết nối, cụm còn 1 node trong 3, dưới quorum, nên control plane ngừng nhận thay đổi dù node còn lại vẫn khỏe. Đặt 3 node vào 3 AZ thì mất bất kỳ AZ nào cũng còn đủ 2 node. Số node nên lẻ vì node thứ chẵn không thêm khả năng chịu lỗi, như hàng 4 node ở trên.

Chuẩn bị môi trường lab

Lab dùng Python 3 chuẩn (không cài thêm gì) và curl. Hai tiến trình chạy trên máy bạn đóng vai hai node. Cổng 47811 và 47812 là cổng cao ít dùng, đổi nếu máy bạn đã dùng.

mkdir dv3-cap && cd dv3-cap

Lưu file sau thành kv_node.py. Mỗi node giữ một kho khóa-giá trị trong bộ nhớ và biết địa chỉ node kia. Tham số đầu tiên chọn chế độ: cp hoặc ap. Công tắc partition có ở mỗi node qua endpoint /partition.

import json
import sys
import threading
import time
import urllib.request
from http.server import BaseHTTPRequestHandler, ThreadingHTTPServer
from urllib.parse import parse_qs, urlparse

MODE = sys.argv[1]
PORT = int(sys.argv[2])
PEER = int(sys.argv[3])

store = {}
state = {"partitioned": False}
lock = threading.Lock()


def call_peer(path, body):
    if state["partitioned"]:
        raise OSError("partitioned")
    req = urllib.request.Request(
        "http://127.0.0.1:%d%s" % (PEER, path),
        json.dumps(body).encode(),
        {"Content-Type": "application/json"},
    )
    return json.loads(urllib.request.urlopen(req, timeout=1).read())


def merge(other):
    for key, (value, ts) in other.items():
        if key not in store or store[key][1] < ts:
            store[key] = (value, ts)


class Handler(BaseHTTPRequestHandler):
    def reply(self, code, obj):
        data = json.dumps(obj).encode()
        self.send_response(code)
        self.send_header("Content-Type", "application/json")
        self.send_header("Content-Length", str(len(data)))
        self.end_headers()
        self.wfile.write(data)

    def body(self):
        n = int(self.headers.get("Content-Length", 0))
        return json.loads(self.rfile.read(n) or b"{}")

    def log_message(self, *args):
        pass

    def do_GET(self):
        key = parse_qs(urlparse(self.path).query).get("key", ["x"])[0]
        if MODE == "cp" and state["partitioned"]:
            return self.reply(503, {"node": PORT, "error": "cannot reach peer, refusing to read"})
        with lock:
            value = store.get(key, (None, 0))[0]
        self.reply(200, {"node": PORT, "mode": MODE, "key": key, "value": value})

    def do_POST(self):
        url = urlparse(self.path)
        if url.path == "/put":
            req = self.body()
            entry = (req["value"], time.time())
            if MODE == "cp":
                try:
                    call_peer("/replicate", {"key": req["key"], "entry": entry})
                except OSError:
                    return self.reply(503, {"node": PORT, "error": "cannot reach peer, refusing to write"})
            else:
                try:
                    call_peer("/replicate", {"key": req["key"], "entry": entry})
                except OSError:
                    pass
            with lock:
                store[req["key"]] = entry
            return self.reply(200, {"node": PORT, "mode": MODE, "stored": req["value"]})
        if url.path == "/replicate":
            if state["partitioned"]:
                return self.reply(503, {"error": "partitioned"})
            req = self.body()
            with lock:
                merge({req["key"]: tuple(req["entry"])})
            return self.reply(200, {"ok": True})
        if url.path == "/merge":
            if state["partitioned"]:
                return self.reply(503, {"error": "partitioned"})
            with lock:
                merge({k: tuple(v) for k, v in self.body().items()})
                return self.reply(200, store)
        if url.path == "/partition":
            state["partitioned"] = parse_qs(url.query).get("on", ["1"])[0] == "1"
            if not state["partitioned"] and MODE == "ap":
                try:
                    with lock:
                        mine = dict(store)
                    other = call_peer("/merge", mine)
                    with lock:
                        merge({k: tuple(v) for k, v in other.items()})
                except OSError:
                    pass
            return self.reply(200, {"node": PORT, "partitioned": state["partitioned"]})
        self.reply(404, {"error": "not found"})


ThreadingHTTPServer(("127.0.0.1", PORT), Handler).serve_forever()

Vài điểm cần đọc trong script trước khi chạy:

• Trong chế độ cp, hàm xử lý /put phải gọi được /replicate ở node kia thì mới ghi. Gọi không được thì trả 503 và không ghi gì. Đọc lúc partition cũng bị từ chối vì node không biết mình còn là bản mới nhất hay không.
• Trong chế độ ap, node ghi cục bộ trước, thử sao chép, lỗi thì bỏ qua và vẫn xác nhận.
• Công tắc /partition?on=1 làm node tự từ chối gọi và nhận cuộc gọi từ node kia. Bật ở cả hai node là mô phỏng đứt đường mạng hai chiều.
• Khi tắt partition ở chế độ ap, node đẩy toàn bộ kho của mình sang node kia và nhận về kho của nó, giữ bản ghi có dấu thời gian lớn hơn (last write wins).
• Script này là mô hình đồ chơi để thấy hành vi. Nó không có bền vững, không có bầu leader và không phải một thuật toán đồng thuận thật.

Hai hàm tiện ích trong shell, dùng cho mọi bước sau:

put() { curl -s -X POST localhost:$1/put -d "{\"key\":\"stock\",\"value\":\"$2\"}"; echo; }
get() { curl -s "localhost:$1/get?key=stock"; echo; }

Lab 1: node nhất quán từ chối khi đứt mạng

Khởi động hai node ở chế độ cp, ghi một giá trị lúc bình thường, rồi bật partition ở cả hai node và thử ghi từ cả hai phía.

python3 kv_node.py cp 47811 47812 &
python3 kv_node.py cp 47812 47811 &
sleep 1
put 47811 10
get 47812
curl -s -X POST "localhost:47811/partition?on=1"; echo
curl -s -X POST "localhost:47812/partition?on=1"; echo
put 47811 9
put 47812 8
get 47811
curl -s -X POST "localhost:47811/partition?on=0"; echo
curl -s -X POST "localhost:47812/partition?on=0"; echo
get 47811
get 47812
kill $(jobs -p)

Kết quả (xác định, không có giá trị thay đổi theo máy):

{"node": 47811, "mode": "cp", "stored": "10"}
{"node": 47812, "mode": "cp", "key": "stock", "value": "10"}
{"node": 47811, "partitioned": true}
{"node": 47812, "partitioned": true}
{"node": 47811, "error": "cannot reach peer, refusing to write"}
{"node": 47812, "error": "cannot reach peer, refusing to write"}
{"node": 47811, "error": "cannot reach peer, refusing to read"}
{"node": 47811, "partitioned": false}
{"node": 47812, "partitioned": false}
{"node": 47811, "mode": "cp", "key": "stock", "value": "10"}
{"node": 47812, "mode": "cp", "key": "stock", "value": "10"}

Phân tích:

• Hai dòng đầu: lúc mạng ổn, ghi vào 47811 và đọc từ 47812 thấy ngay 10. Đây là consistency theo nghĩa CAP: hai node cho cùng một câu trả lời.
• Hai lệnh ghi lúc partition đều bị từ chối bằng 503. Khách nhìn thấy lỗi nhưng dữ liệu vẫn đúng một giá trị.
• Sau khi nối lại, cả hai vẫn là 10. Hai giá trị 9 và 8 chưa bao giờ được ghi, không có dữ liệu nào lệch hay mất.
• Cái giá: trong suốt thời gian partition, dịch vụ không bán được hàng. Đây là phần availability bị hy sinh.

Hãy xem hai hành vi đối xử với cùng một đường mạng bị đứt. Trước khi bấm, dự đoán: ở chế độ nào khách của gdev-shop thấy lỗi, và ở chế độ nào thì lỗi chỉ lộ ra sau khi mạng nối lại?

Lab 2 (failure lab): node luôn trả lời và lệch dữ liệu

Chạy lại đúng kịch bản nhưng ở chế độ ap. Hãy hình dung khách ở phía 47811 mua 1 sản phẩm (kho còn 9), còn khách ở phía 47812 mua 2 sản phẩm (kho còn 8). Đúng ra kho phải còn 7.

python3 kv_node.py ap 47811 47812 &
python3 kv_node.py ap 47812 47811 &
sleep 1
put 47811 10
get 47812
curl -s -X POST "localhost:47811/partition?on=1"; echo
curl -s -X POST "localhost:47812/partition?on=1"; echo
put 47811 9
put 47812 8
get 47811
get 47812
curl -s -X POST "localhost:47811/partition?on=0"; echo
curl -s -X POST "localhost:47812/partition?on=0"; echo
get 47811
get 47812
kill $(jobs -p)

Kết quả (xác định):

{"node": 47811, "mode": "ap", "stored": "10"}
{"node": 47812, "mode": "ap", "key": "stock", "value": "10"}
{"node": 47811, "partitioned": true}
{"node": 47812, "partitioned": true}
{"node": 47811, "mode": "ap", "stored": "9"}
{"node": 47812, "mode": "ap", "stored": "8"}
{"node": 47811, "mode": "ap", "key": "stock", "value": "9"}
{"node": 47812, "mode": "ap", "key": "stock", "value": "8"}
{"node": 47811, "partitioned": false}
{"node": 47812, "partitioned": false}
{"node": 47811, "mode": "ap", "key": "stock", "value": "8"}
{"node": 47812, "mode": "ap", "key": "stock", "value": "8"}

Triệu chứng: không có một lỗi nào cả, mọi request đều trả 200. Nhưng giá trị cuối cùng là 8 trong khi sự thật là 7, nghĩa là hệ thống vừa bán lố một sản phẩm.

Nguyên nhân: lúc partition mỗi node trả lời theo bản dữ liệu của riêng nó (9 và 8 cùng tồn tại). Khi nối lại, quy tắc last write wins giữ giá trị ghi sau cùng là 8 và bỏ giá trị 9 mà không ghi lại việc đã bỏ. Phép trừ của khách thứ nhất bị xóa.

Cách kiểm chứng ở hệ thật: so sánh số dư cuối ngày với tổng các giao dịch, hoặc ghi log mọi bản ghi bị thay thế khi hòa giải. Cách sửa không nằm ở chọn CP hay AP mà ở thiết kế dữ liệu: ghi sự kiện thay vì giá trị tuyệt đối (mỗi giao dịch là một dòng "trừ 1", "trừ 2"), để hai phía cộng gộp lại được thay vì ghi đè lẫn nhau. Kiểu dữ liệu thiết kế sẵn để gộp như vậy gọi là CRDT, bài này chỉ nêu tên để bạn biết chỗ tìm.

Quyết định theo từng nghiệp vụ

Không có chế độ nào đúng cho cả hệ thống. Hãy ngồi với người làm sản phẩm và điền bảng này cho từng thao tác, với câu hỏi cụ thể: "đứt mạng 3 phút thì khách chịu điều gì?".

Một điểm tinh tế: hạn mức theo AZ là cách chuyển một bài toán nhất quán thành bài toán cục bộ. Nếu còn 5 sản phẩm, cho mỗi AZ bán tối đa 2 và giữ 1 chung, thì lúc đứt mạng mỗi bên tự bán trong hạn mức của mình mà không cần hỏi bên kia.

Hệ thống thật xử lý partition như thế nào

Chỉ nên nói về hành vi mà tài liệu chính thức mô tả, không dán nhãn từ trí nhớ. Các tài liệu dưới đây hầu như không dùng chữ "CP" hay "AP"; nhãn là cách ta diễn giải hành vi được mô tả.

Điểm chung: không hệ nào chọn một lần cho mọi trường hợp. Bạn chọn bằng cấu hình (số standby đồng bộ, cờ đọc, NODE_TIMEOUT), và mọi cấu hình đó là quyết định về hành vi khi partition.

Lỗi thường gặp

Tự kiểm tra

Hãy trả lời trước khi đọc đáp án ngay bên dưới mỗi câu.

Câu 1. Cụm etcd 5 node trải 3 AZ theo kiểu 2, 2 và 1. Một AZ bất kỳ mất kết nối thì cụm còn quorum không, và hai AZ cùng mất thì sao?

Đáp án: quorum là 3. Mất AZ có 1 node thì còn 4 node, mất AZ có 2 node thì còn 3 node, cả hai trường hợp đều còn quorum. Mất hai AZ cùng lúc thì chỉ còn 1 hoặc 2 node, dưới quorum, nên cụm chịu được mất đúng một AZ.

Câu 2. Một hệ thống trả lời mọi request trong 50 mili giây nhưng đôi khi trả dữ liệu cũ vài giây khi partition. Nó nghiêng về C hay A của CAP?

Đáp án: nghiêng về A, vì mọi request đều được trả lời. Dữ liệu cũ nghĩa là C không được bảo đảm.

Câu 3. Hai node ở chế độ AP cùng ghi một khóa khi bị partition, rồi hòa giải theo last write wins. Lần ghi nào mất, và làm sao để không mất?

Đáp án: lần ghi có dấu thời gian nhỏ hơn mất, mà không báo lỗi. Muốn không mất, ghi các sự kiện cộng gộp được (ví dụ "trừ 1", "trừ 2") thay vì ghi đè giá trị tuyệt đối.

Nếu chỉ nhớ 3 điều

1. Partition xảy ra thật. Câu hỏi thiết kế là khi đó từ chối (giữ đúng, mất availability) hay chấp nhận (giữ phục vụ, dữ liệu lệch rồi hòa giải).
2. Chọn theo từng thao tác và từng nghiệp vụ: tiền và tồn kho cuối cùng nghiêng về từ chối, bộ đếm và danh mục nghiêng về chấp nhận.
3. Quorum là cách hệ nhất quán vẫn phục vụ: dùng số node lẻ và rải node qua nhiều AZ sao cho mất một AZ vẫn còn đa số.

Bài tiếp theo là Load Balancing, nơi ta chạy một bộ cân bằng tải nginx thật và xem nó loại backend hỏng ra sao.

Tài liệu tham khảo: bài chứng minh của Gilbert và Lynch, PostgreSQL về synchronous replication, etcd API guarantees, Redis Cluster specification và DynamoDB read consistency.