định lý C.A.P.

4.1 Tính nhất quán về Brewera

Đầu tiên, Eric Brewer không phải và chưa bao giờ tự nhận mình là một chuyên gia về cơ sở dữ liệu. Anh ấy thuộc cộng đồng các hệ thống phân tán, và bài nói chuyện nổi tiếng của anh ấy, trong đó xuất hiện "định lý" CAP, đã được đưa ra tại hội nghị "Các nguyên tắc của tính toán phân tán". (Nhân tiện, mười năm sau, vào năm 2010, anh ấy lại có một buổi nói chuyện được mời tại cùng một hội nghị, và đặc biệt, trong buổi nói chuyện này, anh ấy đã đưa ra một số ví dụ về các hệ thống phân tán, sự phát triển của nó đã tính đến " định lý" của CAP.) Trong lĩnh vực này có cách giải thích riêng về các thuật ngữ được sử dụng trong lĩnh vực cơ sở dữ liệu.

Cụ thể, thuật ngữ "tính nhất quán ngay lập tức" có nghĩa là sau khi người dùng nhận được thông báo từ hệ thống về việc hoàn thành thành công một số thao tác cập nhật dữ liệu, kết quả của thao tác này sẽ hiển thị ngay lập tức cho tất cả những người quan sát.

Tính nhất quán cuối cùng có nghĩa là nếu không có hoạt động cập nhật dữ liệu mới nào vào hệ thống trong một khoảng thời gian đủ dài, thì có thể dự kiến ​​rằng kết quả của tất cả các hoạt động cập nhật dữ liệu trước đó cuối cùng sẽ lan sang tất cả các nút của hệ thống và tất cả dữ liệu bản sao đều được nhất quán (rõ ràng, điều này nên được hiểu là "tất cả các bản sao sẽ có cùng trạng thái".

Với ý nghĩa nhất quán này, "định lý" của Brewer có thể được coi là khá dễ hiểu và hiển nhiên: trong bất kỳ hệ thống phân tán nào có dữ liệu được chia sẻ, chỉ có thể đảm bảo đồng thời hai thuộc tính bất kỳ về tính nhất quán, tính khả dụng và dung sai phân vùng của mạng. Về vấn đề này, Brewer thậm chí còn đối chiếu tập hợp các thuộc tính ACID với tập hợp các thuộc tính CƠ SỞ được đề xuất của ông (Khả dụng về cơ bản, Trạng thái mềm, Tính nhất quán cuối cùng - tính khả dụng trong hầu hết các trường hợp; trạng thái không ổn định; tính nhất quán cuối cùng). Nhưng theo tôi, sự phản đối này là không chính đáng, vì trong trường hợp đầu tiên chúng ta đang nói về các đặc điểm logic của giao dịch và trong trường hợp thứ hai - về các đặc tính vật lý của các hệ thống phân tán.

4.2 Chứng minh định lý

Nhiều người tin rằng "định lý" của Brewer đã được chứng minh chính thức. Thật vậy, bài báo của Seth Gilbert và Nancy Lynch giới thiệu một số (gần như) định nghĩa hình thức trong đó ngữ cảnh của "định lý" thực sự trở thành một định lý và được chứng minh. Tuy nhiên, hãy xem cách xác định ba thuộc tính đó của một hệ thống phân tán, trong đó, theo "định lý" của Brewer, chỉ có hai thuộc tính có thể được hỗ trợ đồng thời.

Tính nhất quán được gọi là tính nhất quán nguyên tử, hoặc tính nhất quán có thể tuyến tính hóa (atomic, or linearizablenhất quán), là một thuộc tính của hệ thống, tất cả các đối tượng dữ liệu riêng lẻ trong số đó là nguyên tử (có thể tuyến tính hóa). Đổi lại, một đối tượng nguyên tử là một đối tượng có một số thao tác, sao cho việc gọi thao tác và nhận dữ liệu phản hồi xảy ra như thể ngay lập tức, tức là. đối tượng không chấp nhận cuộc gọi của hoạt động tiếp theo cho đến khi hoạt động trước đó hoàn thành. Thứ tự các thao tác được nhận phải sao cho nếu thao tác kiểu đọc đến sau khi thao tác kiểu ghi nào đó đã được thực hiện, thì thao tác đọc phải trả về giá trị được ghi bởi thao tác này hoặc thao tác ghi sau này.

Một hệ thống phân tán luôn sẵn sàng nếu mọi yêu cầu nhận được bởi một nút không bị lỗi phải được trả lời. Khả năng phục hồi của hệ thống đối với phân vùng mạng được mô hình hóa như là khả năng duy trì khả năng tồn tại của hệ thống trong trường hợp mất một số lượng tin nhắn tùy ý được gửi từ nút này sang nút khác.

Dựa trên các định nghĩa này, Hilbert và Lynch xây dựng định lý sau (không có đồng hồ trong mô hình mạng không đồng bộ và các nút chỉ nên đưa ra quyết định trên cơ sở các thông báo nhận được và tính toán cục bộ):

Trong mô hình mạng không đồng bộ, không thể triển khai đối tượng dữ liệu đọc/ghi đảm bảo tính khả dụng và tính nhất quán nguyên tử cho tất cả các lần thực thi hợp lệ (bao gồm cả những lần thực hiện mất thông báo).

Định lý này thực sự được chứng minh khá đơn giản về mặt hình thức bằng phương pháp "bằng mâu thuẫn". Bài báo tiếp tục kết luận rằng:

Trong mô hình mạng không đồng bộ, không thể triển khai đối tượng dữ liệu đọc/ghi đảm bảo các thuộc tính khả năng truy cập cho tất cả các lần thực thi hợp lệ và tính nhất quán nguyên tử cho các lần thực thi hợp lệ trong đó các thông báo không bị mất.

Ngoài ra, sự thật của định lý chính được chứng minh cho mô hình mạng đồng bộ một phần, trong đó mỗi nút có một đồng hồ, thời gian được hiển thị theo đó tăng với cùng tốc độ, nhưng không được đồng bộ hóa, tức là có thể hiển thị các thời điểm khác nhau tại cùng một thời điểm thực. Nó chỉ ra rằng đối với trường hợp này, một hậu quả tương tự không xảy ra và do đó, đối với các mạng đồng bộ một phần, có nhiều khả năng hơn để tổ chức các hệ thống phân tán có thuộc tính "tốt".

Vâng, theo một nghĩa nào đó (không nhất thiết phải giống như dự định của Brewer) Gilbert và Lynch có thể được coi là đã chứng minh rằng không thể đảm bảo đồng thời các thuộc tính về tính nhất quán nguyên tử, tính khả dụng và dung sai phân vùng của mạng trong một hệ thống phân tán duy nhất. Nhưng điều này có liên quan gì đến các giao dịch cơ sở dữ liệu nói chung và các giao dịch ACID nói riêng?

4.3 Giao dịch ACID

Đây là những gì Julian Browne viết về điều này trong ghi chú của ông về cuộc thảo luận về "định lý" của CAP:

Trong chứng minh của họ, Hilbert và Lynch sử dụng thuật ngữ tính nguyên tử thay vì tính nhất quán, thuật ngữ này có ý nghĩa hơn từ quan điểm kỹ thuật bởi vì, nói đúng ra, tính nhất quán theo nghĩa ACID đề cập đến các thuộc tính lý tưởng của các giao dịch cơ sở dữ liệu và có nghĩa là không có dữ liệu nào sẽ trở nên dai dẳng nếu chúng vi phạm một số hạn chế được thiết lập trước. Nhưng nếu chúng ta cho rằng một hạn chế được thiết lập trước của các hệ thống phân tán là việc cấm sự hiện diện của một số giá trị khác nhau cho cùng một phần tử dữ liệu, thì theo tôi, lỗ hổng này trong việc trừu tượng hóa tính nhất quán có thể được coi là không đáng kể (ngoài ra, nếu Brewer sử dụng thuật ngữ nguyên tử, thì định lý AAP sẽ xuất hiện, tên của nó sẽ cực kỳ bất tiện khi phát âm).

Điều này được viết không nghiêm túc lắm, nhưng trung thực. Và trên thực tế, không nên trộn lẫn yêu cầu về tính nhất quán nguyên tử với yêu cầu về tính nhất quán trong giao dịch theo nghĩa ACID. Ràng buộc toàn vẹn cơ sở dữ liệu là hợp lý, nếu bạn muốn, yêu cầu kinh doanh. Chúng đến từ logic miền ứng dụng. Yêu cầu về tính nhất quán nguyên tử thuộc một loại rất khác. Đây là một yêu cầu triển khai thuộc danh mục thường được gọi trong ngành cơ sở dữ liệu là tính nhất quán vật lý (ví dụ: khi thực hiện bất kỳ thao tác thay đổi chỉ mục nào, tất cả các khối của cây B+ tương ứng phải chứa các giá trị hợp lệ và được liên kết bởi các tham chiếu hợp lệ ).

Và đây là những gì đại diện của cộng đồng cơ sở dữ liệu Daniel Abadi và Alexander Thomson viết khá nghiêm túc trong ghi chú của họ:

... yêu cầu về tính khả dụng của các hệ thống giao dịch có thể mở rộng ngày càng trở nên quan trọng và điều này thường được đáp ứng thông qua sao chép và tự động chuyển hướng các yêu cầu trong trường hợp một trong các nút bị lỗi. Do đó, các nhà phát triển ứng dụng kỳ vọng rằng các đảm bảo về tính nhất quán của các hệ thống ACID (ban đầu bao gồm hỗ trợ cục bộ cho các bất biến do người dùng xác định) sẽ được mở rộng để đảm bảo tính nhất quán cao (rằng tất cả các bản sao của cùng một dữ liệu tại bất kỳ thời điểm nào sẽ là các bản sao giống hệt nhau, tức là trong tính nhất quán của trường hợp này được ngụ ý theo nghĩa của CAP/PACELC.

Nói cách khác, tính nhất quán của Brewer không liên quan gì đến tính nhất quán theo nghĩa của ACID, nhưng trong các hệ thống tập trung vào việc cung cấp tính sẵn sàng cao thông qua sao chép dữ liệu, điều mong muốn là duy trì tính nhất quán mạnh mẽ của bản sao. Đây không phải là một thuộc tính ACID, mà là một tính năng kỹ thuật (vật lý) của DBMS song song lớn tạo điều kiện phát triển ứng dụng.

Theo Michael Stonebreaker, chìa khóa để xây dựng một DBMS hiện đại chất lượng cao là sự lựa chọn đúng đắn về các thỏa hiệp kỹ thuật. Khi chọn một giải pháp kỹ thuật cụ thể, nhiều yếu tố phải được tính đến - yêu cầu của người dùng trong tương lai, khả năng xảy ra các tình huống lỗi khác nhau, v.v. và không được hướng dẫn một cách giáo điều bởi bất kỳ hướng dẫn lý thuyết chung nào (bao gồm cả "định lý" CAP).

Stonebreaker tin rằng trong lĩnh vực hệ thống cơ sở dữ liệu song song giao dịch, việc từ bỏ tính nhất quán của Brewer để hỗ trợ tính khả dụng cao và dung sai phân vùng mạng là một sự đánh đổi kém vì (a) tính nhất quán của bản sao là một tính năng rất hữu ích của hệ thống; (b) DBMS song song khối lượng giao dịch không cần các cụm có số lượng nút rất lớn, do đó, tình huống chia tách mạng khó xảy ra; (c) hệ thống có thể dễ dàng trở nên không khả dụng, không phải do phân vùng mạng, mà, ví dụ, do các lỗi phần mềm thường xuyên xảy ra.

Do đó, hoạt động tích cực của các đại diện của trại NoSQL (đọc là NoACID), người thường đề cập đến "định lý" của Brewer, không liên quan đến việc không thể xây dựng DBMS giao dịch song song ồ ạt hỗ trợ các giao dịch ACID, mà với thực tế là các hệ thống đã được đơn giản hóa không chỉ hỗ trợ các giao dịch ACID mà còn hỗ trợ tính nhất quán của bản sao, được tạo ra dễ dàng và nhanh hơn. Do tổ chức đơn giản, chúng có khả năng xử lý dữ liệu rất nhanh và đối với một số ứng dụng, điều này quan trọng hơn tất cả các tiện ích vốn có trong công nghệ cơ sở dữ liệu.

Hãy xem cách cộng đồng cơ sở dữ liệu phản ứng với thách thức này.