CAP Theorem

Đường cáp quang giữa hai trung tâm dữ liệu bị đứt

gdev-shop chạy ở hai trung tâm dữ liệu: Hà Nội và TP.HCM, mỗi nơi giữ một bản sao tồn kho. Một đêm, tàu kéo neo làm đứt đường cáp quang nối hai nơi. Cả hai trung tâm vẫn chạy bình thường, khách hàng vẫn truy cập được cả hai, nhưng hai bên không còn nói chuyện được với nhau. Một khách ở Hà Nội mua chiếc áo cuối cùng. Một khách ở TP.HCM, không biết điều đó, cũng muốn mua. Hệ thống phải quyết định ngay lúc này:

• Phương án A: TP.HCM từ chối đơn cho đến khi nối lại được với Hà Nội, để chắc chắn không bán quá. Khách TP.HCM thấy lỗi.
• Phương án B: TP.HCM vẫn nhận đơn dựa trên dữ liệu nó có. Khách vui, nhưng có nguy cơ bán lố số lượng.

Không có phương án C cho cả hai cùng đúng. Đây là nội dung của CAP Theorem.

Ba chữ cái, định nghĩa chính xác

CAP nói về ba thuộc tính của một hệ thống lưu trữ phân tán:

• C - Consistency: ở đây có nghĩa linearizability (nhất quán mạnh): mọi lần đọc thấy ghi mới nhất, như thể chỉ có một bản dữ liệu. Đây không phải chữ C trong ACID.
• A - Availability: mọi yêu cầu gửi đến một node đang hoạt động đều nhận được phản hồi (không phải lỗi hay timeout), dù có thể không phải dữ liệu mới nhất. Lưu ý đây là định nghĩa chặt hơn nghĩa "uptime" thông thường.
• P - Partition tolerance: hệ thống tiếp tục hoạt động khi mạng giữa các node bị chia cắt (partition): các node vẫn sống nhưng một số tin nhắn giữa chúng bị mất hoặc trễ vô hạn.

Phát biểu của định lý: khi có network partition, một hệ thống không thể đồng thời đảm bảo cả Consistency và Availability. Phải chọn một.

Hai chi tiết thường bị bỏ sót:

1. Định lý nói về tình huống khi có partition. Khi mạng bình thường, bạn không buộc phải từ bỏ C hay A.
2. Partition không phải thứ bạn có thể chọn bỏ. Mạng giữa các node (đặc biệt giữa các vùng) luôn có thể đứt. Vì vậy "chọn CA" (bỏ P) chỉ có ý nghĩa với hệ thống chạy trên một node duy nhất, không phải hệ phân tán thật sự. Lựa chọn thực tế trong hệ phân tán là CP hay AP khi có partition xảy ra.

Cái gì xảy ra khi có partition?

Cách đọc hình kiến trúc. Đường đỏ nét đứt là đường mạng bị cắt giữa hai data center (partition). Phía trái chọn CP: bên thiểu số từ chối phục vụ nên dữ liệu luôn đúng nhưng mất tính sẵn sàng. Phía phải chọn AP: cả hai bên vẫn trả lời nhưng dữ liệu có thể lệch và phải hợp nhất sau. Không có lựa chọn thứ ba khi partition xảy ra, và mỗi loại dữ liệu nên chọn theo chi phí của việc trả sai hoặc từ chối.

Cách đọc sơ đồ

1. Đường nối giữa hai node bị cắt (ghi chú network partition). Mỗi node vẫn sống nhưng không biết bên kia làm gì.
2. Hà Nội bán chiếc áo cuối cùng và cập nhật tồn kho thành 0, nhưng không thể báo cho Saigon.
3. Khách tại Saigon gửi yêu cầu mua. Saigon phải chọn:
   • Lựa chọn CP (ưu tiên Consistency): Saigon từ chối (trả lỗi hoặc yêu cầu thử lại sau), vì nó không thể chắc chắn dữ liệu của mình còn đúng. Hệ thống đúng nhưng không sẵn sàng với khách Saigon.
   • Lựa chọn AP (ưu tiên Availability): Saigon vẫn phục vụ, dựa trên bản sao cục bộ cho rằng còn 1. Hệ thống sẵn sàng nhưng có thể sai: sau khi mạng nối lại, hệ thống phải giải quyết việc chiếc áo bị bán hai lần (hoàn tiền, xin lỗi, hoặc cơ chế hợp nhất).

Chọn gì không phải câu hỏi kỹ thuật thuần túy. Nó phụ thuộc vào chi phí nghiệp vụ của mỗi loại sai.

Chọn CP hay AP theo dữ liệu

Mô hình dữ liệu thực tế của một ứng dụng thường pha trộn: thanh toán chọn CP, còn trải nghiệm duyệt chọn AP. Nhiều hệ thống thương mại thực tế chọn AP cho giỏ hàng và có cơ chế hợp nhất xung đột khi nối lại.

Những điều CAP không nói

• CAP không nói về hệ thống đang hoạt động bình thường. Khi không có partition, hệ thống có thể vừa nhất quán vừa sẵn sàng. Lúc đó có một đánh đổi khác giữa độ trễ và độ nhất quán (mở rộng của CAP gọi là PACELC, ở mức Good to Know): kể cả không có partition, nhất quán mạnh tốn độ trễ để các node phối hợp.
• CAP không có nghĩa "chọn hai trong ba". Vì P không thể bỏ, thực chất là chọn C hay A khi có P.
• "Availability" của CAP chặt hơn "uptime". Nó đòi mọi node hoạt động trả lời được, kể cả node bị cô lập. CP không có nghĩa hệ thống "luôn sập": nó chỉ từ chối ở phía thiểu số của partition, phía còn đa số vẫn có thể phục vụ bình thường.
• CAP không phân loại sản phẩm thành CP hay AP cố định. Nhiều database cho cấu hình để người dùng chọn mức nhất quán theo từng thao tác.

Hiểu lầm phổ biến

• "Chọn hai trong ba." Sai. Bạn không chọn bỏ partition. Câu hỏi là C hay A khi partition xảy ra.
• "Có hệ thống CA." Chỉ có thể với một node duy nhất, không phân tán, và nó sẽ không chịu được mất node.
• "AP nghĩa là dữ liệu không bao giờ nhất quán." Sau khi partition được chữa, AP hội tụ về nhất quán (nhất quán cuối cùng) và dùng quy tắc hợp nhất.
• "CP nghĩa là luôn sập." Chỉ từ chối ở những phần không thể đảm bảo; phía có đa số node vẫn phục vụ được.

Must Know, Good to Know, Advanced

• Must Know: định nghĩa C, A, P chính xác; định lý áp dụng khi có partition; P không thể bỏ; chọn CP hay AP theo chi phí nghiệp vụ của từng loại dữ liệu.
• Good to Know: CP từ chối ở phía thiểu số; khi không có partition vẫn có đánh đổi độ trễ và nhất quán (PACELC); hợp nhất sau khi nối lại.
• Advanced: chứng minh hình thức, các giao thức đồng thuận như Paxos và Raft giúp hệ CP chọn node quyết định. Chỉ cần biết rằng đồng thuận là cách thực hiện CP.

Tự kiểm tra

1. Khi đường cáp giữa hai trung tâm dữ liệu đứt, vì sao hệ thống không thể vừa nhất quán mạnh vừa trả lời mọi yêu cầu ở cả hai phía?
2. Chọn CP hay AP cho: thanh toán, giỏ hàng, số lượt thích? Lập luận bằng chi phí sai.
3. Vì sao câu "chọn hai trong ba" gây hiểu lầm?

Đáp án gợi ý

1. Khi cáp đứt, hai trung tâm không thể liên lạc. Nếu cả hai tiếp tục nhận ghi thì hai bên lệch nhau (mất nhất quán). Nếu muốn nhất quán thì ít nhất một bên phải từ chối phục vụ (mất sẵn sàng). Không có cách nào vừa trả lời mọi yêu cầu ở cả hai phía vừa đảm bảo cùng một dữ liệu, vì không bên nào biết bên kia đã làm gì.
2. Thanh toán: CP, vì sai tiền đắt hơn việc từ chối ngắn hạn. Giỏ hàng: thường AP, vì khách quan tâm luôn thêm được sản phẩm và sai lệch nhỏ có thể hợp nhất sau. Số lượt thích: AP, vì sai vài đơn vị tạm thời gần như không có hại. Tiêu chí là chi phí khi trả sai hoặc từ chối.
3. Vì partition không thể bỏ trong mạng thật, nên thực chất không có lựa chọn "bỏ P". Lựa chọn thật chỉ xảy ra khi có partition: C hay A. Khi mạng bình thường thì không phải từ bỏ điều nào về mặt định lý, chỉ có đánh đổi độ trễ và nhất quán (PACELC).

Nếu chỉ nhớ 3 điều

1. CAP: khi có partition, hệ phân tán phải chọn giữa nhất quán mạnh (từ chối bên không chắc chắn) và sẵn sàng (phục vụ dữ liệu có thể cũ).
2. Không thể bỏ partition; thực chất chọn là CP hay AP khi mạng đứt, và chọn theo chi phí nghiệp vụ từng loại dữ liệu.
3. Khi mạng bình thường không phải từ bỏ C hay A, nhưng vẫn có đánh đổi độ trễ và nhất quán.