Tìm hiểu định lý CAP / CAP THEOREM

Nhiều người trong chúng ta hẳn đã nghe về định lý CAP (CAP theorem), một trong các định lý phổ biến hay được dùng trong việc lựa chọn/phân tích các công nghệ phân tán hiện đại, đặc biệt là NoSQL.

Nhưng định lý này bắt nguồn từ đâu?

Theo định lý CAP, một hệ thống phân tán chỉ có thể chọn được giữa hai trong ba yếu tố (C-Consistency, A-Availability, P-Partial Tolerance), trong đó sự lựa chọn giữa một trong hai yếu tố C-A được xem là một trong những tranh luận cốt lõi.

  • Consistency: tính nhất quán, tất cả các node phải có dữ liệu đồng nhất với nhau.
  • Availability: tính sẵn sàng hoạt động của các node. Hệ thống có thể vẫn hoạt động được khi một số node bị chết hoặc không sẵn sàng.
  • Partition Fault Tolerance: trạng thái hoạt động của hệ thống khi đường kết nối (mạng) giữa các node bị đứt, hay còn gọi là khả năng chịu lỗi của hệ thống. Hệ thống vẫn phải hoạt động bình thường cho dù các kết nối của các node trong hệ thống bị đứt gãy.

Thật ra, những cuộc tranh luận về C-A vốn dĩ đã xuất hiện trước đó giữa ACID và BASE trong đó các nhà thiết kế có phần thiên về ACID, tuy nhiên, với sự xuất hiện của càng nhiều công nghệ dữ liệu lớn, các hệ thống càng ngày càng bự với càng nhiều server cùng tham gia hệ thống thì việc đảm bảo ACID không còn là chuyện đơn giản. Từ đó, định lý CAP được nêu ra như một mô hình suy nghĩ phù hợp hơn với thời đại công nghệ và dữ liệu lớn.

Chúng ta không thể thiết kế một hệ thống bao gồm cả ba tính CAP, bởi vì đảm bảo tính C (consistency) tất cả các cập nhật dữ liệu phải được thực hiện trên các node cùng một thời điểm. Nhưng nếu đường kết nối (mạng) giữa các node không được đảm bảo dẫn đến việc các node sẽ không được update dữ liệu cùng một thời điểm, điều này dẫn tới việc một vài node dữ liệu sẽ bị out-of-date do chưa được cập nhật dữ liệu từ đó vi phạm tính C (consistency). Và để đảm bảo đối phó với điều này ta sẽ ngừng phục vụ nhữg node bị out-of-date đó cho tới khi nó được update dữ liệu đầy đủ, nhưng việc này lại vi phạm tính A (availability) của hệ thống.

Thông thường, người ta thường đánh đổi yếu tố C để lấy hai yếu tố A và P. Khi đó họ sẽ thay thế Consistency thành eventually consistency (tính nhất quán có độ trễ), làm như thế hệ thống sẽ có hiệu năng tốt hơn

Định lý CAP được tác giả Eric Brewer nêu ra trong bài báo vào năm 1999, sau đó được đề cập lần nữa vào năm 2000 trong hội thảo “the Principles of Distributed Computing” trong một bài nói của mình không kèm chứng minh.

Sau đó 2 năm, hai nhà khoa học máy tính là Seth Gilbert và Nancy Lynch đã mô hình hoá và đưa ra công thức chứng minh cho định lý này trong bài báo xuất bản năm 2002 của mình với tiêu đề “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services” khiến định lý càng ngày càng phổ biến.

Tham khảo:

infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/?fbclid=IwAR0xPpnAI5Xgp0Pva8u8JJQ5IMr3lEZNVCr4jdBxt7Nq4SFkVwfDwsfJpPY

Leave a Reply

Your email address will not be published. Required fields are marked *