CAP theorem và lưu trữ phân tán

Giới thiệu

Bài này học CAP chọn 2 trong 3 khi mạng chia cắt. Định lý này giúp chọn kho dữ liệu đúng bài toán.

Kiến thức cần nhớ

CAP là gì

• C là mọi nút đọc cùng giá trị mới nhất.
• A là mọi yêu cầu đều có trả lời không treo.
• P là mạng chia cắt mà hệ vẫn chạy.
• Ví dụ đời thường: cáp đứt 2 miền thì chọn đúng hay chọn nhanh.

Ba họ CA AP CP

• CA: đúng và nhanh nhưng chỉ trong một trung tâm.
• AP: nhanh và chịu cắt, chấp nhận cũ tạm thời.
• CP: đúng và chịu cắt, thà từ chối còn hơn sai.
• Ví dụ đời thường: tiền phải CP, feed mạng xã hội nên AP.

Quorum và nén

• Ghi đa số bản sao thì đọc đa số sẽ thấy mới.
• Tăng bản ghi thì đúng hơn nhưng trễ lớn hơn.
• Sao 3 bản thì tiền đĩa phình, nén log giảm tiền.
• Ví dụ đời thường: hỏi 2 trong 3 thủ kho là biết hàng mới.

Ví dụ

• Input: tiền tệ chọn AP, mạng cắt 2 bên cùng trừ -> Output: số dư âm, kết luận chọn sai.
• Câu này cho thấy tiền phải CP chấp nhận từ chối.
• Input: log phình gấp 10 sau sao 3 bản -> Output: hướng sửa là nén log ít đọc.
• Câu này cho thấy nén cứu tiền đĩa và trễ sao chép.

💻 Bài tập

Ngôn ngữ: Python 3 (asyncio hoặc thread). Đây là mô phỏng, không cần mạng thật. Nộp vào day-060/.

Bài 1: Kho key-value nhân bản

class Node:
    def __init__(self, name): self.data = {}      # key -> (value, version)
class Cluster:
    def __init__(self, n_nodes: int, N: int, W: int, R: int): ...
    def put(self, key, value) -> bool: ...        # ghi vào W node, trả False nếu không đủ node sống
    def get(self, key): ...                        # đọc R node, trả value có version lớn nhất
    def partition(self, group_a: set, group_b: set): ...   # chặn liên lạc giữa 2 nhóm
    def kill(self, name); def revive(self, name)

Bài 2: Mô phỏng chia cắt mạng

Tài khoản ngân hàng có số dư 100. Cắt mạng thành 2 nhóm. Mỗi nhóm nhận 1 lệnh rút 80.

1. Chế độ AP: mỗi nhóm tự nhận lệnh. Sau khi nối lại, gộp bằng "version lớn nhất thắng". In số dư và số tiền đã rút. Chỉ ra sai ở đâu.
2. Chế độ CP: chỉ nhóm có đa số (≥ 2/3 node) nhận ghi. In số lệnh bị từ chối và số dư cuối.
3. Viết bảng: hệ thống nào (giỏ hàng, số dư ngân hàng, lượt thích, tồn kho vé máy bay) chọn AP hay CP, vì sao.

Bài 3: Chi phí nhân bản (nâng cao)

1. Mỗi lần gửi tới node có độ trễ ngẫu nhiên 5-50 ms. Đo độ trễ put/get p50, p99 với W, R từ 1 tới 3.
2. Ghi 10.000 bản log. Nén bằng zlib các bản cũ hơn 1000 lần ghi. In dung lượng trước và sau.
3. Vẽ biểu đồ: trục x là W + R, trục y là độ trễ p99.

✅ Tiêu chí hoàn thành

• Test chứng minh W + R > N đọc thấy bản mới, và W + R <= N có thể đọc cũ.
• Bài 2 in rõ lỗi của chế độ AP với dữ liệu tiền.
• Bảng AP/CP cho 4 hệ thống kèm lý do.
• Biểu đồ độ trễ theo W + R có số thật.

❓ Câu hỏi ôn tập

• CAP gồm 3 chữ nào?
• Vì sao mạng lớn chỉ chọn 2 trong 3?
• Tiền tệ nên AP hay CP?
• Quorum đa số giúp gì?

🌕 Bạn đã hoàn thành ngày 60. Làm hết bài tập phía trên rồi sang ngày tiếp theo.