Định lý CAP, còn được biết đến là định lý Brewer, được Eric Brewer giới thiệu vào năm 1998 dưới dạng giả thuyết. Vào năm 2002, định lý này đã được Seth Gilbert và Nancy Lynch chứng minh. Định lý này nêu rõ rằng bất kỳ hệ thống phân tán nào cũng không thể đồng thời có ba thuộc tính là tính nhất quán, tính khả dụng, và khả năng chịu phân mảnh:
- Tính nhất quán là thuộc tính đảm bảo rằng tất cả các nút trong hệ thống phân tán có một bản sao dữ liệu hiện tại và giống hệt nhau. Tính nhất quán được đạt được bằng cách sử dụng các thuật toán đồng thuận để đảm bảo rằng tất cả các nút có cùng một bản sao dữ liệu. Điều này còn được gọi là nhân bản trạng thái máy (SMR). Blockchain là một phương tiện để đạt được nhân bản trạng thái máy.
- Tính khả dụng có nghĩa là các nút trong hệ thống luôn hoạt động, có thể truy cập và chấp nhận các yêu cầu đầu vào cũng như phản hồi với dữ liệu mà không gặp lỗi khi cần thiết. Nói cách khác, dữ liệu có sẵn tại mỗi nút và các nút đang phản hồi các yêu cầu.
- Khả năng chịu phân mảnh đảm bảo rằng nếu một nhóm các nút không thể giao tiếp với các nút khác do lỗi mạng, hệ thống phân tán vẫn tiếp tục hoạt động đúng cách. Điều này có thể xảy ra do lỗi mạng và lỗi nút.
Một sơ đồ Venn thường được sử dụng để trực quan hóa định lý CAP, như sau:
Sơ đồ trước đó cho thấy rằng chỉ có thể đạt được hai thuộc tính cùng một lúc; tức là AP, CA, hoặc CP.
Tóm lại:
- Nếu chúng ta chọn CP (Consistency & Partition Tolerance_ tính nhất quán và khả năng chịu phân mảnh): Đảm bảo dữ liệu nhất quán và hệ thống vẫn hoạt động khi bị phân mảnh, nhưng phải đánh đổi khả dụng (Availability), nghĩa là có thể không phản hồi ngay lập tức trong một số trường hợp -> chúng ta sẽ phải hy sinh tính khả dụng.
- Nếu chúng ta chọn AP (Availability & Partition Tolerance_ tính khả dụng và khả năng chịu phân mảnh): Đảm bảo hệ thống luôn phản hồi yêu cầu và chịu được phân mảnh, nhưng phải đánh đổi tính nhất quán (Consistency), dữ liệu có thể không đồng bộ giữa các nút trong một thời gian ngắn. -> chúng ta sẽ phải hy sinh tính nhất quán.
- Nếu chúng ta chọn AC (Availability & Consistency_ tính khả dụng và tính nhất quán): Đảm bảo dữ liệu nhất quán và hệ thống luôn phản hồi, nhưng phải đánh đổi khả năng chịu phân mảnh (Partition Tolerance), tức là hệ thống sẽ không hoạt động nếu xảy ra sự phân mảnh mạng -> chúng ta sẽ phải hy sinh khả năng chịu phân mảnh.
Lưu ý rằng AC thực sự không tồn tại. Định lý CAP trong thực tế có nghĩa là trong trường hợp mạng bị phân mảnh. Khi xảy ra phân mảnh mạng (Partition Tolerance), không phải tất cả các nút trong mạng đều có thể giao tiếp với nhau một cách thông suốt vì lỗi hoặc mất kết nối giữa các nút có thể xảy ra bất cứ lúc nào. Một hệ thống phân tán sẽ phải chọn giữa tính khả dụng hoặc tính nhất quán. Vì phân mảnh mạng không thể bị bỏ qua, lựa chọn sẽ là giữa tính nhất quán hoặc tính khả dụng khi xảy ra phân mảnh mạng.
Chúng ta có thể giải thích khái niệm này bằng ví dụ sau:
Giả sử có một hệ thống phân tán với hai nút. Bây giờ, hãy áp dụng ba thuộc tính của định lý cho hệ thống phân tán nhỏ nhất có thể với chỉ hai nút:
- Tính nhất quán đạt được nếu cả hai nút có cùng trạng thái chia sẻ; nghĩa là, chúng có cùng bản sao dữ liệu cập nhật nhất.
- Tính khả dụng đạt được nếu cả hai nút đều hoạt động và phản hồi với bản sao dữ liệu mới nhất.
- Khả năng chịu phân mảnh đạt được nếu, mặc dù có lỗi hoặc trễ giao tiếp giữa các nút, mạng (hệ thống phân tán) tiếp tục hoạt động.
Bây giờ hãy tưởng tượng một kịch bản khi xảy ra phân mảnh và các nút không thể giao tiếp với nhau. Nếu dữ liệu mới cập nhật đến, nó chỉ có thể được cập nhật trên một nút. Nếu nút chấp nhận cập nhật, thì chỉ có một nút trong mạng được cập nhật, và như vậy sẽ mất tính nhất quán. Nếu nút từ chối cập nhật, điều này sẽ dẫn đến mất tính khả dụng. Điều này có nghĩa là trong tình huống phân mảnh mạng, không thể đạt được tính khả dụng hoặc tính nhất quán. Điều này có vẻ lạ vì bằng cách nào đó, blockchain quản lý để đạt được tất cả các thuộc tính này, vi phạm định lý (đặc biệt là trong thực hiện thành công nhất của nó, Bitcoin)—hoặc là không?
Trong các blockchain, tính nhất quán bị hy sinh để đổi lấy tính khả dụng và khả năng chịu phân mảnh. Trong tình huống này, tính nhất quán (C) trong blockchain không được đạt được đồng thời với khả năng chịu phân mảnh (P) và tính khả dụng (A), mà đạt được theo thời gian. Điều này được gọi là tính nhất quán cuối cùng, nơi tính nhất quán được đạt được nhờ sự xác thực từ nhiều nút theo thời gian. Có thể có sự bất đồng tạm thời giữa các nút về trạng thái cuối cùng, nhưng cuối cùng chúng sẽ đạt được sự đồng thuận.
Ví dụ, trong Bitcoin, nhiều lần xác nhận giao dịch là cần thiết để đạt được mức độ tin cậy cao rằng các giao dịch có thể không bị quay ngược lại trong tương lai. Cuối cùng, một cái nhìn nhất quán về lịch sử giao dịch có sẵn ở tất cả các nút. Nhiều lần xác nhận của một giao dịch theo thời gian cung cấp tính nhất quán cuối cùng trong Bitcoin. Để làm được điều này, quá trình khai thác đã được giới thiệu trong Bitcoin. Khai thác là một quá trình giúp đạt được sự đồng thuận bằng cách sử dụng thuật toán Proof of Work (PoW). Ở mức độ cao hơn, khai thác có thể được định nghĩa là một quá trình được sử dụng để thêm nhiều khối vào blockchain. Sẽ tìm hiểu thêm về điều này trong Kiến trúc Bitcoin. Một mở rộng của định lý CAP gọi là PACELC.
