Quorum — nhất quán đọc/ghi với R+W>N

TL;DR: Trong hệ thống replicate dữ liệu lên N node, đọc chờ R bản phản hồi và ghi chờ W bản xác nhận. Nếu R + W > N, tập đọc và tập ghi luôn giao nhau ít nhất một node, node đó có bản ghi đã được xác nhận, nên đọc chạm được bản mới nhất đã ghi thành công (chưa phải linearizable, tức chưa đảm bảo mọi lần đọc thấy kết quả của lần ghi đã hoàn tất gần nhất, như thể chỉ có một bản dữ liệu; xem mục 3.2). Cách làm này gọi là quorum (đủ số phiếu tối thiểu, như họp phải quá nửa mới tính). Điều chỉnh R và W theo yêu cầu: W=1 cho ghi nhanh, R=N cho đọc luôn mới nhất, hoặc W=R=⌊N/2⌋+1 cho cân bằng. Khi có partition (mạng bị chia), buộc phải chọn giữa consistency và availability: đó là bản chất của CAP theorem.

Hệ thống lưu trữ hồ sơ bệnh nhân của bạn replicate mỗi bản ghi lên 3 node (N=3). Bác sĩ cập nhật liều thuốc của bệnh nhân (write). Hai giây sau, y tá đọc hồ sơ trên máy khác. Nếu hệ thống không có cơ chế quorum, y tá có thể đọc liều cũ từ node chưa nhận được update, và bệnh nhân uống sai liều. Bài này tính xem cần đọc và ghi bao nhiêu bản để lần đọc chạm bản đã ghi, và chỗ nào phép tính đó vẫn hở.

1. Replication và bài toán consistency

Replication là việc lưu cùng một dữ liệu trên nhiều node để tăng availability và throughput đọc. Với N=3 replica:

• Khi write "liều = 500mg": gửi tới cả 3 node.
• Nếu network chậm, node3 nhận update muộn hơn 2 giây so với node1 và node2.
• Trong khoảng 2 giây đó, ai đọc từ node3 thấy "liều = 300mg" (giá trị cũ).

Tình trạng này gọi là eventual consistency (nhất quán sau cùng): cuối cùng mọi node sẽ giống nhau, nhưng trong khoảng giữa thì có lúc lệch nhau. Với like count trên mạng xã hội thì chấp nhận được. Với dữ liệu y tế thì không.

Câu hỏi: có cách nào đảm bảo đọc thấy write mới nhất mà không cần chờ tất cả N node xác nhận (vì vậy quá chậm, và chỉ cần một node chết là kẹt)?

2. Quorum: giao điểm đọc/ghi

Định nghĩa: quorum nghĩa là "đủ số máy trả lời" thay vì chờ tất cả. Với N replica, write được coi là thành công khi W node xác nhận; read trả về kết quả khi R node phản hồi.

Điều kiện quorum: nếu R + W > N, tập W node được ghi và tập R node được đọc phải giao nhau ít nhất 1 node. Node đó chứa write mới nhất → read sẽ thấy giá trị đó (sau khi so sánh version).

Chứng minh ngắn: giả sử ngược lại: tập W và tập R không giao nhau. Vậy |W| + |R| ≤ N, tức R + W ≤ N, mâu thuẫn với giả thiết R + W > N. Vậy tập giao không rỗng.

R + W > N không phải mẹo số học mà là nguyên lý chuồng bồ câu: bốn người ngồi trên ba cái ghế thì buộc có một ghế bị ngồi hai lần.

Thử ngẫmmột dịch vụ ghi log hàng nghìn lần mỗi giây nhưng hiếm khi đọc, N=5. Chọn W nhỏ nhất có thể thì R phải bằng bao nhiêu để lần đọc vẫn chạm bản mới nhất?