Giới hạn của định lý CAP và định lý PACELC
1. Tổng quan
A. Định lý CAP và giới hạn của nó
Định lý CAP là lý thuyết cho rằng hệ thống phân tán không thể đồng thời thỏa mãn cả ba thuộc tính tính nhất quán (Consistency)·tính sẵn sàng (Availability)·khả năng chịu phân vùng (Partition tolerance), và khi xảy ra phân vùng mạng thì chỉ có thể bảo đảm tối đa hai. Được Eric Brewer đưa ra năm 2000 và Gilbert·Lynch chứng minh hình thức năm 2002.
Nhận thức cốt lõi của định lý CAP là 'khi mạng bị đứt (phân vùng) thì phải từ bỏ một trong hai: tính nhất quán hoặc tính sẵn sàng'. Ở đây phải hiểu chính xác ý nghĩa của từng thuộc tính để tránh hiểu lầm. Tính nhất quán (C) nghĩa là mọi nút thấy cùng một dữ liệu mới nhất tại cùng thời điểm (chặt chẽ là khả tuyến tính hóa, linearizability), tính sẵn sàng (A) nghĩa là nút bình thường nhất định phải phản hồi mọi yêu cầu, còn khả năng chịu phân vùng (P) nghĩa là hệ thống tiếp tục hoạt động dù thông điệp giữa các nút bị trễ·mất tùy ý. Hiểu lầm phổ biến ở đây là cách nói "chọn hai trong ba", đó chỉ là hiểu một nửa.
Trong hệ thống phân tán, phân vùng (P) — việc liên lạc giữa các nút bị đứt — có thể xảy ra bất cứ lúc nào do mạng diện rộng·sự cố trung tâm dữ liệu·lỗi switch, nên thực chất không phải là lựa chọn mà là tiền đề phải chịu đựng. Trừ khi có thể tin cậy hoàn toàn vào mạng, hệ thống phân tán thực tế không thể từ bỏ P. Khi đó, lựa chọn thực tế thu hẹp lại không phải là CA mà là chọn một giữa C và A tại thời điểm xảy ra phân vùng. Khi có phân vùng, muốn giữ nhất quán dữ liệu mới nhất (C) thì phải chặn phản hồi của nút không xác nhận được đồng bộ với nút khác nên mất tính sẵn sàng; còn muốn phản hồi vô điều kiện (A) thì có thể trả về dữ liệu cũ chưa đồng bộ nên mất tính nhất quán.
Tuy nhiên CAP có một giới hạn mang tính quyết định. Đó là nó chỉ xử lý 'khi đã xảy ra phân vùng'. Thực tế trong hệ thống phân tán quy mô lớn, phân vùng mạng là sự kiện tương đối hiếm, và hệ thống dành phần lớn thời gian ở 'trạng thái bình thường' không có phân vùng. Vậy khi bình thường, hệ thống chọn gì giữa tính nhất quán và tốc độ phản hồi? CAP không đưa ra câu trả lời nào cho điều này. Tức là CAP không giải thích được đánh đổi thiết kế ở trạng thái bình thường chiếm hơn 99% vòng đời hệ thống. Thứ lấp đầy khoảng trống này là PACELC.
B. Bối cảnh ra đời của PACELC
Để bù đắp giới hạn CAP chỉ giải thích tình huống ngoại lệ là phân vùng, năm 2010 Daniel Abadi của Đại học Yale đề xuất PACELC bao gồm cả đánh đổi ở trạng thái bình thường. Ý thức vấn đề của ông rất rõ ràng. Đó là "câu hỏi thực sự mà nhà phát triển đối mặt khi thực tế chọn cơ sở dữ liệu phân tán không phải là 'từ bỏ gì khi có phân vùng' mà là 'bình thường được phép chậm đến đâu và phải chính xác đến đâu'". Chẳng hạn, hệ thống đặt bản sao ở nhiều trung tâm dữ liệu thì dù không có phân vùng, bản thân việc đồng bộ giữa các bản sao đã tạo ra độ trễ. Sự cân bằng độ trễ-nhất quán thường ngày này nằm ngoài khung CAP, nên Abadi đã dựng một khung rộng hơn chứa CAP như tập con.
2. Cấu trúc của định lý PACELC
PACELC: Là lý thuyết cho rằng khi phân vùng (P) xảy ra thì phải chọn giữa tính sẵn sàng (A) và tính nhất quán (C), còn nếu không (Else) thì phải chọn giữa độ trễ (Latency) và tính nhất quán (C). Đọc theo đúng chữ viết tắt là "if P then A or C, Else L or C".
flowchart LR
N{"Xảy ra phân vùng mạng?"} -->|"P (trạng thái phân vùng)"| AC["A vs C<br/>Sẵn sàng vs nhất quán"]
N -->|"E (trạng thái bình thường)"| LC["L vs C<br/>Độ trễ vs nhất quán"]
AC --> PA["PA: ưu tiên phản hồi"]
AC --> PC["PC: ưu tiên chính xác"]
LC --> EL["EL: ưu tiên độ trễ thấp"]
LC --> EC["EC: ưu tiên nhất quán mạnh"]
style LC fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
style N fill:#fff3cd,stroke:#d39e00,stroke-width:2px
Nền tảng của sự phân nhánh bình thường/phân vùng này là cấu trúc 'nhân bản (replication)'. Dù là lựa chọn L-C ở trạng thái bình thường hay A-C ở trạng thái phân vùng, rốt cuộc đều được quyết định bởi cách xác nhận (acknowledge) việc ghi trên nhiều bản sao và việc đọc được xử lý ở bản sao nào. Dưới đây là cấu trúc tương tác giữa client·coordinator·bản sao trong nhân bản dựa trên đại biểu (Quorum); trong bố trí này, cách đặt giá trị R·W chính là xác định vị trí trên phổ EL/EC.
flowchart TB
CL["Client"] --> CO["Nút coordinator"]
CO -->|"Chờ xác nhận ghi W bản"| R1["Bản sao 1"]
CO --> R2["Bản sao 2"]
CO --> R3["Bản sao 3"]
R1 -.->|"Lan truyền bất đồng bộ"| R2
R2 -.->|"Lan truyền bất đồng bộ"| R3
CO -->|"Đọc R bản rồi trả giá trị mới nhất"| CL
style CO fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
style CL fill:#f1f8e9,stroke:#558b2f,stroke-width:2px
Trong cấu trúc này, nếu đặt W (số xác nhận ghi) và R (số bản đọc) lớn để thỏa R + W > N thì luôn đọc được giá trị mới nhất và tiến gần tới nhất quán mạnh (EC), nhưng coordinator phải chờ phản hồi của nhiều bản sao hơn nên độ trễ tăng. Ngược lại, nếu hạ xuống như W=1, R=1 thì chỉ xác nhận một bản sao gần nhất nên độ trễ được tối thiểu hóa (EL), nhưng phát sinh rủi ro đọc giá trị cũ từ bản sao khác chưa được lan truyền. Như vậy, việc tọa độ PACELC dịch chuyển chỉ bằng tham số trên cùng một kiến trúc chính là thực chất của 'nhất quán có thể điều chỉnh' trong các DB phân tán hiện đại.
A. Trạng thái phân vùng (PA/PC) — vùng trùng với CAP
Nửa trước của PACELC (P → A or C) thực chất giống với CAP. Trong tình huống mạng bị phân vùng và các nhóm nút không liên lạc được với nhau, hệ thống phải quyết định để từng nhóm tự nhận và xử lý yêu cầu (PA), hay phía không nhận được xác nhận của nhóm đa số sẽ từ chối phản hồi (PC). Ví dụ, dữ liệu mà giá trị sai là chí mạng như số dư tài khoản ngân hàng phải chọn PC để các nút thiểu số bị phân vùng từ chối ghi, còn dữ liệu lệch một chút cũng không sao như giỏ hàng hay số 'like' thì nên chọn PA để cứ phản hồi trước rồi hợp nhất (conflict resolution) sau.
Hàm ý thực tiễn của lựa chọn này nằm ở việc làm rõ 'định nghĩa của tính sẵn sàng'. Ngay cả hệ thống chọn PA cũng không từ bỏ tính đúng đắn vô hạn, mà sau khi phân vùng được giải quyết sẽ làm dữ liệu hội tụ bằng các kỹ thuật như vector clock·ghi sau cùng thắng (LWW)·CRDT. Tức là tính sẵn sàng với tiền đề 'nhất quán cuối cùng (Eventual Consistency)'. Ngược lại, hệ thống PC trong lúc phân vùng có thể làm thất bại một số yêu cầu, nhưng các phản hồi thành công thì luôn bảo đảm chính xác.
B. Trạng thái bình thường (EL/EC) — đóng góp riêng của PACELC
Đóng góp cốt lõi thực sự của PACELC nằm ở nửa sau, tức là làm lộ ra đánh đổi ở trạng thái bình thường (Else). Dù không có phân vùng, để giữ dữ liệu nhất quán mạnh trên nhiều bản sao thì chỉ có thể phản hồi sau khi xác nhận yêu cầu ghi đã được phản ánh vào mọi bản sao (hoặc đủ đại biểu), nên phản hồi chậm lại (Latency↑). Nếu là các trung tâm dữ liệu cách xa về địa lý, do giới hạn vật lý là tốc độ ánh sáng, độ trễ khứ hồi (RTT) lên tới hàng chục~hàng trăm ms nên chi phí này hoàn toàn không nhỏ.
Ngược lại, để giảm độ trễ thì nới lỏng đồng bộ nhân bản: chỉ đọc một bản sao gần và phản hồi (nhân bản bất đồng bộ) hoặc chấp nhận ghi mà không cần đa số xác nhận. Khi đó phản hồi nhanh nhưng giá trị vừa ghi vào nút khác có thể chưa được lan truyền nên có thể đọc giá trị cũ, tức nhượng bộ tính nhất quán. Rốt cuộc, ngay cả lúc bình thường không có ngoại lệ phân vùng, hệ thống vẫn không ngừng lựa chọn giữa độ trễ và tính nhất quán. Trong phương thức Quorum, sự cân bằng này được điều chỉnh bằng việc có thỏa điều kiện R + W > N (tổng đại biểu đọc·ghi lớn hơn số bản sao) hay không; thỏa thì gần với nhất quán mạnh (EC), hạ R·W thì dịch về phía độ trễ thấp (EL).
| Loại | Khi phân vùng (PA/PC) | Khi bình thường (EL/EC) | Ví dụ tiêu biểu | Mục đích sử dụng tiêu biểu |
|---|---|---|---|---|
| PA/EL | Ưu tiên sẵn sàng | Ưu tiên độ trễ thấp | Cassandra, DynamoDB, Riak | Giỏ hàng, phiên, log, gợi ý |
| PC/EC | Ưu tiên nhất quán | Ưu tiên nhất quán mạnh | RDBMS truyền thống, VoltDB, HBase | Sổ cái tài chính, tồn kho, đặt chỗ |
| PA/EC | Ưu tiên sẵn sàng | Ưu tiên nhất quán | MongoDB (tùy cấu hình) | Điều chỉnh cân bằng bằng tinh chỉnh |
| PC/EL | Ưu tiên nhất quán | Ưu tiên độ trễ thấp | PNUTS (Yahoo), một số cấu hình | Đọc gần theo khu vực+ghi nhất quán mạnh từ xa |
Điểm cần lưu ý ở đây là phân loại trên không phải nhãn tuyệt đối mà biểu thị giá trị cấu hình mặc định (default). Ví dụ, Cassandra mặc định là PA/EL nhưng khi nâng mức nhất quán đọc·ghi lên QUORUM thì được tinh chỉnh gần với EC. MongoDB cũng dịch chuyển trên phổ từ EC sang EL tùy theo cấu hình writeConcern và readConcern. Tức là DB phân tán hiện đại không phải một điểm cố định mà cung cấp một khoảng trên trục 'nhất quán có thể điều chỉnh (Tunable Consistency)', và PACELC đóng vai trò hệ tọa độ để hiểu trục đó.
3. So sánh CAP và PACELC
Khác biệt giữa hai lý thuyết không đơn thuần là 'PACELC giải thích nhiều hơn', mà nằm ở việc nắm bắt được các điểm quyết định mà nhà thiết kế thực sự đối mặt đến đâu. CAP nhấn mạnh lựa chọn cực đoan trong tình huống khủng hoảng hiếm hoi là phân vùng, nhưng chính sự nhấn mạnh đó lại làm tăng hiểu lầm. Nhiều nhà phát triển nói "DB của chúng tôi là CA", nhưng chừng nào không thể từ bỏ P thì CA là tổ hợp không thành lập trong môi trường phân tán, và điều họ thực sự muốn nói thường là "duy trì nhất quán mạnh lúc bình thường (EC)". PACELC dọn dẹp sự nhầm lẫn đó bằng cách nêu rõ trục của trạng thái bình thường.
| Phân loại | CAP | PACELC |
|---|---|---|
| Tình huống xử lý | Chỉ khi phân vùng | Khi phân vùng + khi bình thường |
| Đánh đổi | C vs A | (P)A vs C + (E)L vs C |
| Giải thích trạng thái bình thường | Không thể | Có thể (L vs C) |
| Thời điểm/người đề xuất | 2000, E. Brewer | 2010, D. Abadi |
| Tính thực dụng | Hạn chế (tập trung tình huống khủng hoảng) | Giải thích toàn bộ vòng đời |
Hàm ý thực tiễn rút ra từ so sánh có hai điểm. Thứ nhất, nếu chỉ dùng CAP để chọn DB thì sẽ bị cuốn quá mức vào kịch bản hiếm "khi phân vùng từ bỏ gì", và bỏ lỡ chính sự cân bằng độ trễ-nhất quán quyết định trải nghiệm người dùng hàng ngày. Thứ hai, nhìn theo PACELC sẽ thấy dù cùng 'họ AP' nhưng chính sách nhất quán lúc bình thường (EL hay EC) khác nhau khiến hiệu năng cảm nhận và độ chính xác thực tế chênh lệch lớn. Ví dụ, Cassandra (PA/EL) và một hệ thống PA/EC lý thuyết có hành vi khi phân vùng giống nhau nhưng độ mới của dữ liệu đọc lúc bình thường khác nhau.
A. Khác biệt qua kịch bản cụ thể
Hình dung một tình huống thực tế sẽ thấy rõ khác biệt giữa hai lý thuyết. Giả sử một sàn thương mại toàn cầu đặt bản sao ở hai region Seoul và Virginia. Mạng phần lớn bình thường nhưng độ trễ khứ hồi giữa hai region lên tới khoảng 180 ms. Theo góc nhìn CAP, chỉ có thể hỏi "khi hai region bị đứt (phân vùng) thì dừng phía nào". Nhưng vấn đề gặp phải mỗi khoảnh khắc trong vận hành thực tế là "có xác nhận đơn hàng của người dùng Seoul tới cả bản sao Virginia rồi mới phản hồi (EC, +180 ms), hay chỉ xác nhận bản sao Seoul rồi phản hồi ngay (EL)". Chính câu hỏi thường ngày này là trục Else của PACELC mà CAP không trả lời được.
Khi đó tính chất dữ liệu quyết định lựa chọn. Dữ liệu mà bán trùng là chí mạng như trừ tồn kho thì chọn EC và chấp nhận độ trễ, còn dữ liệu lệch một chút cũng không sao như lượt xem sản phẩm hay sản phẩm vừa xem thì chọn EL để giữ độ nhạy phản hồi. Rốt cuộc, thiết kế thực tế là ngay trong một dịch vụ cũng đặt tọa độ PACELC khác nhau theo từng loại giao dịch.
4. Chuyên sâu — Ví dụ áp dụng thiết kế và xu hướng mới
A. Ví dụ áp dụng trong công nghiệp
Amazon DynamoDB là đại diện của họ PA/EL, vốn xuất phát từ yêu cầu như giỏ hàng — "tuyệt đối không được để lộ việc thêm vào giỏ thất bại" — nên ưu tiên hàng đầu tính sẵn sàng và độ trễ thấp. Tuy nhiên từ sau 2018 đã bổ sung tùy chọn đọc nhất quán mạnh (ConsistentRead) và giao dịch (TransactWriteItems), tiến hóa để có thể chọn EL hoặc EC theo tính chất dữ liệu ngay trong một hệ thống. Đây là ví dụ cho thấy loại PACELC không cố định mà được tổ hợp theo nhu cầu.
Google Spanner ở một vị trí thú vị. Nó dùng đồng bộ thời gian chính xác gọi là TrueTime (dựa trên đồng hồ nguyên tử·GPS) để cung cấp nhất quán ngoại (external consistency) ngay cả trong trạng thái phân tán địa lý, hướng tới PC/EC. Tuy nhiên ghi nhất quán mạnh đi kèm độ trễ chờ commit (commit-wait), nên thể hiện nguyên vẹn bản chất của EC là "chấp nhận độ trễ vì tính nhất quán". Tức là ngay cả Spanner cũng không thoát khỏi định luật vật lý và đánh đổi PACELC, và hiểu chính xác hơn là nó đạt được thành tựu kỹ thuật trong việc tối thiểu hóa cái giá đó.
B. Xu hướng mới
Dòng chảy gần đây của cơ sở dữ liệu phân tán là hướng chi tiết hóa 'lựa chọn nhất quán theo tình huống·dữ liệu'. NewSQL (CockroachDB, YugabyteDB v.v.) cố gắng cung cấp đồng thời khả năng mở rộng phân tán và giao dịch nhất quán mạnh, có thể xem là sự dung hòa lấy PC/EC làm mặc định nhưng giảm độ trễ bằng bố trí gần theo khu vực. Ngoài ra, các mô hình trung gian giữa nhất quán mạnh và nhất quán cuối cùng như 'nhất quán nhân quả (Causal Consistency)' đang được chú ý, đây là nỗ lực mở rộng trục L-C của PACELC thành phổ liên tục thay vì nhị phân. Tuy nhiên mức trưởng thành và phạm vi áp dụng của các mô hình dung hòa mới này chênh lệch lớn theo sản phẩm·phiên bản, nên khi áp dụng an toàn hơn là xác nhận mức bảo đảm qua tài liệu chính thức của sản phẩm.
C. Hiểu lầm phổ biến và điểm cần lưu ý
Hiểu lầm hay gặp ngoài thực tế là cách nói "hệ thống của chúng tôi là CA". Như đã thấy, trong môi trường phân tán không thể từ bỏ P thì tổ hợp CA không thành lập, và hệ thống nói như vậy thường là nút đơn (không phân tán) hoặc thực chất muốn nói 'nhất quán mạnh lúc bình thường (EC)'. Một hiểu lầm khác là coi nhãn PACELC là thuộc tính bất biến của sản phẩm. Thực tế phần lớn DB phân tán qua lại giữa khoảng EL~EC bằng cấu hình, nên mô tả chính xác là "DB này mặc định EL và có thể điều chỉnh tới EC bằng cấu hình đại biểu" thay vì "DB này là EL".
Do đó, khi review kiến trúc, thay vì chấp nhận nguyên nhãn sản phẩm, phải xác nhận giá trị cấu hình nhất quán đọc·ghi sẽ thực sự áp dụng và kiểm chứng tổ hợp đó có đồng thời thỏa yêu cầu chính xác của từng loại dữ liệu và SLA độ trễ hay không.
5. Các điểm cần cân nhắc và hàm ý (góc nhìn Kỹ sư chuyên nghiệp)
- Lựa chọn độ trễ-nhất quán lúc bình thường thực chất quan trọng hơn. Phân vùng hiếm nhưng hệ thống hoạt động ở trạng thái bình thường phần lớn vòng đời, nên lựa chọn Else (L vs C) của PACELC quyết định trải nghiệm người dùng thực tế (tốc độ phản hồi·độ mới dữ liệu). Khi review thiết kế, không chỉ "ứng phó khi phân vùng" mà "chính sách nhất quán lúc bình thường" cũng phải được quyết định tường minh.
- Áp dụng chính sách khác nhau theo tính chất dữ liệu. Thiết kế chính sách phân cấp theo dữ liệu (polyglot persistence) ngay trong một dịch vụ, chẳng hạn chọn EC (nhất quán mạnh) khi độ chính xác là quyết định như sổ cái tài chính·tồn kho·đặt chỗ, và chọn EL (độ trễ thấp·nhất quán cuối cùng) khi tốc độ và tính sẵn sàng quan trọng như feed SNS·gợi ý·lượt xem.
- Là la bàn để chọn NoSQL·NewSQL. Khi chọn DB phân tán như Cassandra (PA/EL), Spanner (PC/EC), DynamoDB (PA/EL+tinh chỉnh), hãy dùng phân loại PACELC để hiểu rõ đánh đổi, và điều chỉnh theo tình huống bằng các tùy chọn nhất quán có thể điều chỉnh (đại biểu R·W, writeConcern v.v.). [[nosql]]
- Thiết kế với tiền đề nhất quán là phổ chứ không phải nhị phân. Giữa nhất quán mạnh và nhất quán cuối cùng có nhiều mô hình trung gian như nhân quả·đọc được giá trị mình ghi (read-your-writes)·đọc đơn điệu, nên hãy chọn mức nhất quán tối thiểu vừa đúng yêu cầu để tránh chi phí độ trễ không cần thiết.
- Gắn đánh đổi với SLA·chi phí. Nhất quán mạnh làm tăng độ trễ·chi phí hạ tầng (nhân bản theo đại biểu, RTT diện rộng), nên phải cân nhắc đồng thời SLA thời gian phản hồi·mức độ rủi ro kinh doanh·chi phí vận hành để tìm điểm cân bằng ngăn cả lãng phí do nhất quán thừa lẫn sự cố do nhất quán thiếu.
- Kiểm chứng bằng cấu hình thực tế chứ không phải nhãn sản phẩm. Cùng một sản phẩm cũng qua lại EL~EC tùy cấu hình đại biểu·writeConcern, nên khi xem xét áp dụng, an toàn hơn là xác nhận bằng benchmark các tham số nhất quán sẽ thực sự áp dụng và mức bảo đảm của tổ hợp đó, thay vì tin nguyên phân loại trong catalog.
Tài liệu tham khảo
- Daniel Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design", IEEE Computer, 2012: https://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf
- Gilbert & Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services", 2002: https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf
- Wikipedia, PACELC theorem: https://en.wikipedia.org/wiki/PACELC_theorem
Tóm tắt một câu: CAP có giới hạn là chỉ giải thích việc chọn một giữa C·A khi phân vùng, còn PACELC bổ sung đánh đổi độ trễ (L) vs nhất quán (C) khi bình thường, trở thành hệ tọa độ thực dụng định hướng lựa chọn thiết kế hệ thống phân tán phù hợp tính chất dữ liệu trong mọi trạng thái phân vùng·bình thường.