Định lý CAP
Trong khoa học máy tính lý thuyết, định lý CAP hay còn gọi là định lý Brewer (được đặt theo tên nhà khoa học máy tính Eric Brewer và được đưa ra vào năm 2000), phát biểu rằng bất kỳ hệ thống dữ liệu phân tán nào chỉ có thể đảm bảo hai trong ba yếu tố sau đây:[1][2]
| Tính nhất quán (Consistency) | Tính khả dụng (Availability) | Tính chịu thương tổn phân vùng (Partition Fault Tolerance) |
|---|---|---|
| Mỗi lần đọc sẽ nhận được dữ liệu mới nhất hoặc lỗi (error). | Mỗi truy vấn luôn nhận được một trả lời không lỗi (non-error response), nhưng không đảm bảo dữ liệu trả về chứa thông tin mới nhất. | Hệ thống tiếp tục hoạt động bình thường mặc dù một số lượng bất kỳ các thông điệp (message) bị mất (hoặc trễ) vì lỗi mạng giữa các node. |
Khi lỗi phân vùng mạng (network partition failure) xảy ra, hệ thống phải lựa chọn một trong hai phương án sau đây:
- Hủy tác vụ, điều này làm giảm tính khả dụng (availability) nhưng đảm bảo tính nhất quán (consistency) của hệ thống.
- Tiếp tục thực hiện tác vụ để đảm bảo tính khả dụng nhưng có thể dẫn đến không nhất quán trong dữ liệu trả về.
Nói cách khác, định lý CAP chỉ ra rằng khi có phân vùng mạng (network partition), người ta phải lựa chọn giữa tính nhất quán và tính khả dụng. Lưu ý rằng tính nhất quán như định nghĩa trong định lý CAP khá khác so với sự nhất quán được đảm bảo trong các giao dịch cơ sở dữ liệu ACID.
Giải thích
Không có hệ thống phân tán nào có thể đảm bảo được an toàn trước các sự cố mạng, khi đó việc phân vùng mạng trở nên cần thiết.[3] Nếu mạng bị phân vùng thì ta chỉ có thể thỏa mãn được một trong hai yếu tố còn lại: tính nhất quán hoặc tính khả dụng. Khi chọn tính nhất quán thay vì tính khả dụng, hệ thống sẽ trả lại lỗi (error) hoặc lỗi hết thời gian chờ (time out) nếu thông tin được truy vấn không thể đảm bảo được là mới nhất. Khi chọn tính khả dụng thay vì tính nhất quán, hệ thống sẽ luôn xử lý truy vấn và cố gắng trả lại phiên bản hiện có của thông tin, ngay cả khi nó không thể đảm bảo đó là phiên bản mới nhất.[4]
Sự lựa chọn giữa tính nhất quán và tính khả dụng chỉ xảy ra khi mạng bị phân vùng; trong trường hợp mạng không phân vùng, cả tính nhất quán lẫn tính khả dụng của thông tin đều được đảm bảo.
Các hệ thống cơ sở dữ liệu truyền thống được thiết kế dựa trên các tính chất ACID như RDBMS ưu tiên tính nhất quán thay vì tính khả dụng, trong khi các hệ thống được thiết kế dựa trên lý thuyết BASE, ví dụ như các mô hình NoSQL, chọn tính khả dụng thay vì tính nhất quán.
Tham khảo
Liên kết ngoài
- CAP Twelve Years Later: How the "Rules" Have Changed Brewer's 2012 article on CRDTs (conflict free replicated data types).
- https://research.google.com/pubs/pub45855.html Spanner, TrueTime and the CAP Theorem