CAP và các Mô hình Nhất quán

Các mô hình nhất quán định nghĩa những đảm bảo mà một hệ thống sao chép đưa ra về các giá trị mà các lần đọc trả về, và định lý CAP giới hạn những đảm bảo nào trong số đó có thể cùng tồn tại với tính khả dụng dưới các phân vùng mạng.

Definition

Mô hình nhất quán là một hợp đồng giữa một kho dữ liệu sao chép và các máy khách của nó, chỉ rõ các kết quả cho phép của các lần đọc và ghi đồng thời; định lý CAP phát biểu rằng khi có một phân vùng mạng, một kho dữ liệu phân tán không thể cung cấp cả tính nhất quán tuyến tính hóa và tính khả dụng.

Scope

Chủ đề này bao gồm các mô hình nhất quán chính thức—tính tuyến tính hóa (linearizability), tính nhất quán tuần tự (sequential consistency), tính nhất quán nhân quả (causal consistency) và tính nhất quán cuối cùng (eventual consistency)—và thứ tự sức mạnh của chúng; định lý CAP cùng với phát biểu và chứng minh chính xác của nó; và các tinh chỉnh như PACELC cũng tính đến sự đánh đổi giữa độ trễ và tính nhất quán khi không có phân vùng. Nó cung cấp từ vựng để chỉ định và so sánh các đảm bảo của hệ thống sao chép.

Core questions

• Tính tuyến tính hóa, tính nhất quán tuần tự, nhân quả và cuối cùng khác nhau về sức mạnh như thế nào?
• Định lý CAP chính xác cấm điều gì và cho phép điều gì?
• Các cân nhắc về độ trễ tinh chỉnh sự đánh đổi nhất quán như thế nào khi không có phân vùng?

Key theories

Tính tuyến tính hóa và tính nhất quán tuần tự

Tính tuyến tính hóa yêu cầu mỗi thao tác phải xuất hiện như thể nó có hiệu lực một cách nguyên tử tại một thời điểm nào đó giữa lúc được gọi và lúc phản hồi, phù hợp với thời gian thực; tính nhất quán tuần tự bỏ qua yêu cầu thời gian thực, chỉ đòi hỏi một sự xen kẽ hợp lệ duy nhất tôn trọng thứ tự của mỗi tiến trình.

Định lý CAP

Gilbert và Lynch đã chứng minh rằng không có kho dữ liệu sao chép nào có thể đảm bảo cả tính nhất quán tuyến tính hóa và tính khả dụng khi mạng có thể làm mất tin nhắn giữa các bản sao, buộc phải lựa chọn trong các phân vùng.

Tinh chỉnh PACELC

PACELC mở rộng CAP bằng cách lưu ý rằng ngay cả khi không có phân vùng, một hệ thống vẫn đánh đổi độ trễ với tính nhất quán, vì vậy các thiết kế được đặc trưng bởi hành vi của chúng cả trong các phân vùng và trong hoạt động bình thường.

Clinical relevance

Mọi cơ sở dữ liệu phân tán và dịch vụ lưu trữ phải công bố một mô hình nhất quán, và các đánh đổi CAP và PACELC giải thích tại sao một số hệ thống ưu tiên tính khả dụng trong khi những hệ thống khác ưu tiên tính nhất quán; hiểu rõ chúng là điều cần thiết để lựa chọn và vận hành cơ sở hạ tầng dữ liệu.

History

Lamport đã định nghĩa tính nhất quán tuần tự vào năm 1979 và Herlihy cùng Wing đã chính thức hóa tính tuyến tính hóa vào năm 1990; Brewer đã đưa ra giả thuyết về sự đánh đổi CAP vào năm 2000, Gilbert và Lynch đã chứng minh nó vào năm 2002, và việc tái cấu trúc PACELC của Abadi vào năm 2012 đã làm rõ rằng độ trễ, không chỉ các phân vùng, thúc đẩy các lựa chọn nhất quán.

Debates

CAP có thường bị hiểu sai không?

CAP thường được tóm tắt là 'chọn hai trong ba', nhưng kết quả chính xác chỉ buộc phải lựa chọn nhất quán-khả dụng trong một phân vùng; các nhà phê bình cho rằng sự đơn giản hóa quá mức này che khuất sự đánh đổi độ trễ-nhất quán hàng ngày phù hợp hơn được PACELC nắm bắt.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

CAP có nghĩa là một hệ thống chỉ có thể có hai trong số tính nhất quán, tính khả dụng và khả năng chịu phân vùng không?

Không hoàn toàn. Các phân vùng là một thực tế của mạng, không phải là một lựa chọn thiết kế, vì vậy quyết định thực sự là phải làm gì trong một phân vùng: hy sinh tính nhất quán mạnh để duy trì khả dụng, hoặc hy sinh tính khả dụng để duy trì nhất quán. Khi không có phân vùng, một hệ thống có thể vừa nhất quán vừa khả dụng.