Định lý CAP và các mô hình nhất quán

Định lý CAP phát biểu rằng một kho dữ liệu phân tán đối mặt với sự cố phân vùng mạng phải hy sinh tính nhất quán hoặc tính khả dụng, và các mô hình nhất quán chỉ rõ chính xác những đảm bảo mà một hệ thống đưa ra về khả năng hiển thị và thứ tự của các bản cập nhật.

Definition

Định lý CAP khẳng định rằng một hệ thống dữ liệu chia sẻ qua mạng có thể đảm bảo đồng thời tối đa hai trong số các thuộc tính nhất quán, khả dụng và chịu lỗi phân vùng; một mô hình nhất quán là một hợp đồng chỉ rõ những gì một ứng dụng có thể quan sát được về thứ tự và khả năng hiển thị của các thao tác đọc và ghi trên các bản sao.

Scope

Chủ đề này bao gồm định lý CAP và sự hình thức hóa của nó, cách hiểu thực tế rằng sự đánh đổi thực sự chỉ phát sinh trong quá trình phân vùng mạng, và sự tinh chỉnh PACELC sau đó. Nó bao gồm phổ các mô hình nhất quán — từ nhất quán mạnh (tuyến tính hóa) thông qua nhất quán nhân quả đến nhất quán cuối cùng — và phong cách BASE đối lập với ACID. Nó đề cập đến cách các mô hình này hướng dẫn thiết kế các kho dữ liệu được sao chép. Nó không bao gồm các giao thức đồng thuận và cam kết được sử dụng để triển khai tính nhất quán mạnh, vốn được đề cập trong các cơ sở dữ liệu phân tán.

Core questions

• Tính nhất quán, tính khả dụng và khả năng chịu lỗi phân vùng có ý nghĩa chính xác là gì trong CAP?
• Tại sao sự lựa chọn thực sự giữa tính nhất quán và tính khả dụng chỉ bị buộc phải đưa ra trong quá trình phân vùng?
• Tính nhất quán mạnh, nhân quả và cuối cùng khác nhau như thế nào về các đảm bảo của chúng?
• Tính nhất quán cuối cùng hứa hẹn điều gì, và không hứa hẹn điều gì?
• Triết lý BASE đối lập với ACID như thế nào?

Key concepts

• nhất quán, khả dụng, chịu lỗi phân vùng
• phân vùng mạng
• tuyến tính hóa / nhất quán mạnh
• nhất quán nhân quả
• nhất quán cuối cùng
• PACELC
• BASE so với ACID
• giải quyết xung đột

Key theories

Định lý CAP

Được Gilbert và Lynch hình thức hóa, CAP cho thấy rằng khi mạng bị phân vùng, một kho dữ liệu được sao chép phải chọn giữa việc trả về dữ liệu có thể đã cũ (tính khả dụng) và từ chối dịch vụ để duy trì một giá trị nhất quán duy nhất (tính nhất quán); khả năng chịu lỗi phân vùng không phải là tùy chọn trong các mạng thực tế.

Phổ nhất quán

Các mô hình nhất quán trải dài từ nhất quán mạnh (tuyến tính hóa), nơi các thao tác đọc luôn thấy bản ghi mới nhất, thông qua nhất quán nhân quả, duy trì thứ tự nguyên nhân-kết quả, đến nhất quán cuối cùng, nơi các bản sao hội tụ theo thời gian khi không có bản ghi mới.

BASE so với ACID

Các hệ thống có tính khả dụng cao thường áp dụng phong cách BASE — về cơ bản là khả dụng, trạng thái mềm, nhất quán cuối cùng — cố tình nới lỏng các đảm bảo ACID mạnh mẽ để duy trì khả năng phản hồi dưới các phân vùng và ở quy mô lớn.

Clinical relevance

CAP và các mô hình nhất quán định hình lựa chọn thiết kế trung tâm trong các hệ thống dữ liệu phân tán: liệu một kho dữ liệu ưu tiên luôn trả lời (tính khả dụng) hay luôn trả lời chính xác (tính nhất quán) khi mạng gặp sự cố, một quyết định định hình hành vi và đảm bảo của mọi ứng dụng phân tán toàn cầu.

History

Eric Brewer đã đưa ra giả thuyết về sự đánh đổi CAP vào khoảng năm 2000; Gilbert và Lynch đã chứng minh nó một cách chính thức vào năm 2002. Dynamo của Amazon (2007) và bài luận năm 2009 của Vogels đã phổ biến tính nhất quán cuối cùng trong thực tế. Bài đánh giá năm 2012 của Brewer đã làm rõ rằng CAP cấm tính nhất quán và khả dụng hoàn hảo chỉ trong quá trình phân vùng, và công thức PACELC sau đó đã bổ sung sự đánh đổi độ trễ-nhất quán trong trường hợp không có phân vùng.

Debates

Sự đánh đổi giữa tính nhất quán và tính khả dụng cơ bản đến mức nào

Các cách hiểu ban đầu coi CAP như buộc phải đưa ra lựa chọn vĩnh viễn giữa tính nhất quán và tính khả dụng; các phân tích sau này, bao gồm cả bài đánh giá của Brewer, lập luận rằng sự đánh đổi chỉ xảy ra trong quá trình phân vùng và các hệ thống có thể phần lớn là nhất quán và khả dụng trong các trường hợp khác, định hình lại mức độ nghiêm ngặt mà CAP hạn chế thiết kế.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Werner Vogels

Seminal works

• gilbert2002
• brewer2012
• vogels2009

Frequently asked questions

CAP có nghĩa là tôi chỉ có thể có hai trong ba thuộc tính không?

Cách diễn đạt phổ biến 'chọn hai' là gây hiểu lầm. Khả năng chịu lỗi phân vùng thực sự không phải là tùy chọn trong một hệ thống phân tán, vì vậy lựa chọn thực sự là giữa tính nhất quán và tính khả dụng, và lựa chọn đó chỉ phải được đưa ra khi một phân vùng thực sự đang xảy ra. Khi mạng hoạt động bình thường, một hệ thống có thể cung cấp cả tính nhất quán và tính khả dụng.

Tính nhất quán cuối cùng thực sự đảm bảo điều gì?

Nó đảm bảo rằng nếu không có bản cập nhật mới nào được thực hiện cho một mục dữ liệu, tất cả các bản sao cuối cùng sẽ hội tụ về cùng một giá trị. Nó không đảm bảo khi nào, cũng như không đảm bảo rằng một thao tác đọc sẽ phản ánh bản ghi gần đây nhất, vì vậy các ứng dụng sử dụng tính nhất quán cuối cùng phải chấp nhận các thao tác đọc tạm thời cũ hoặc xung đột và thường phải tự xử lý việc giải quyết xung đột.