Leaderless — mọi bản bình đẳng, dùng quorum

TL;DR: Leaderless (kiểu Dynamo) bỏ hẳn vai trò leader: client gửi mỗi ghi tới nhiều bản cùng lúc và coi là thành công khi W bản xác nhận; gửi mỗi đọc tới nhiều bản và lấy giá trị mới nhất trong R bản trả lời. Nếu chọn R + W vượt N (tổng số bản), tập bản đọc và tập bản ghi chắc chắn giao nhau — nên đọc luôn chạm ít nhất một bản có ghi mới nhất. Vì không có leader điều phối, các bản sẽ lệch nhau; hệ hàn lại bằng read repair (lúc đọc thấy bản cũ thì ghi đè bản mới vào) và anti-entropy (tiến trình nền so sánh và đồng bộ, thường dùng Merkle tree). Đổi lại sự đối xứng và khả dụng cao, leaderless không có thứ tự ghi toàn cục — ghi song song vẫn phải giải quyết như multi-leader (vector clock).

Single-leader có một nơi quyết thứ tự; multi-leader có vài nơi. Leaderless đi tới cực còn lại: không nơi nào đặc biệt. Client (hoặc một coordinator không-đặc-quyền) tự nói chuyện với nhiều bản và dùng số phiếu (quorum) thay cho quyền lực (leader). Đây là kiến trúc của các kho khả-dụng-cao như Dynamo/Cassandra — và là nơi mọi cơ chế bạn học ở track thuật toán phân tán hội tụ lại.

1. Analogy — hỏi nhiều người thay vì hỏi sếp

Muốn biết số liệu mới nhất, bạn có hai cách. Cách single-leader: hỏi đúng người phụ trách (leader) — chính xác nhưng nếu người đó nghỉ thì tắc. Cách leaderless: hỏi năm đồng nghiệp cùng lúc, ai cũng giữ một bản; bạn lấy câu trả lời mới nhất trong số người trả lời. Không phụ thuộc một ai — ba người bận vẫn hỏi được hai người còn lại.

Nhưng để chắc "mới nhất" là thật mới, phải có quy tắc số: khi cập nhật, bạn báo cho ít nhất ba người; khi hỏi, bạn hỏi ít nhất ba người. Vì hai nhóm ba người trong tổng năm người chắc chắn trùng ít nhất một người, người đó biết bản mới nhất — bạn không bao giờ bỏ sót. Đó chính là quorum.

2. Cơ chế quorum — R + W vượt N

Gọi N = số bản của mỗi dữ liệu. Client:

• Ghi: gửi tới cả N bản, coi thành công khi W bản xác nhận.
• Đọc: hỏi N bản, chờ R bản trả lời, lấy giá trị mới nhất (kèm version) trong số đó.

flowchart LR
  W["Ghi: cho W ban ack"] --> O["Tap W va tap R<br/>GIAO nhau >=1 ban"]
  R["Doc: hoi R ban"] --> O
  O --> V["Ban giao co ghi moi nhat<br/>-> doc khong bo sot"]

Nếu chọn R + W vượt N, thì tập W bản đã ghi và tập R bản đang đọc buộc phải giao nhau ít nhất một bản — bản giao đó có ghi mới nhất, nên đọc không bỏ sót.

N = 3 ban.
  W=2, R=2 -> R+W=4 > 3 -> giao nhau: doc luon thay ghi moi nhat (can bang)
  W=3, R=1 -> ghi cham (cho ca 3), doc RAT nhanh (1 ban)  -> hop doc-nhieu
  W=1, R=3 -> ghi RAT nhanh (1 ban), doc cham (ca 3)      -> hop ghi-nhieu
  W=1, R=1 -> R+W=2 < 3 -> KHONG dam bao giao -> co the doc ban cu

Quan sát: R và W là hai cần gạt để nghiêng hệ về đọc-nhanh hay ghi-nhanh, miễn giữ R+W vượt N. Đây là điểm mạnh của leaderless — chỉnh nhất quán/hiệu năng bằng tham số, không đổi kiến trúc.

3. Vì sao quorum không phải đảm bảo tuyệt đối?

Lần theo cơ chế: ghi X=5 chỉ chạm một trong ba bản — gọi là bản A. Lần đọc lấy hai bản bất kỳ; nếu nó trúng đúng hai bản kia (B và C, không có A), cả hai đều chưa có X=5 → client đọc phải giá trị cũ. Với R+W đúng bằng N (ở đây 1+2=3), tập ghi (1 bản) và tập đọc (2 bản) có thể vừa khít phủ kín N mà không chồng lấn — không có bản giao. Chỉ khi R+W vượt hẳn N thì hai tập buộc phải chồng ít nhất một bản; đó là lý do công thức đòi dấu lớn hơn, không phải lớn hơn hoặc bằng.

Nhưng ngay cả khi giữ đúng R+W>N, thực tế vẫn còn kẽ hở:

• Sloppy quorum: khi nhiều bản "đúng nhà" bị lỗi, hệ có thể chấp nhận ghi vào các bản tạm (hàng xóm) để giữ khả dụng — lúc đó W bản ack có thể không nằm trong N bản gốc, phá tính giao nhau. Ghi được lưu và chuyển về đúng nhà sau (hinted handoff), nhưng trong khoảng đó đọc có thể trượt.
• Ghi song song: quorum đảm bảo đọc thấy các ghi, nhưng nếu hai ghi song song (không thứ tự toàn cục), quorum không tự quyết cái nào "đúng" — vẫn phải giải xung đột bằng version/vector clock (như multi-leader bài 03).
• Ghi thất bại một phần: ghi thành công ở vài bản rồi lỗi (chưa đủ W) — một số bản đã có giá trị mới, khó rollback sạch.

Nên quorum cho xác suất cao đọc thấy ghi mới, không phải đảm bảo tuyệt đối như linearizability (Module 6). Đây là đánh đổi có chủ đích để lấy khả dụng.

4. Read repair và anti-entropy — hàn các bản lệch

Vì không leader ép đồng bộ, các bản trôi lệch (một bản bỏ lỡ ghi lúc nó đang lỗi). Hai cơ chế kéo chúng về:

• Read repair (sửa lúc đọc): khi client đọc từ nhiều bản và thấy một bản trả về giá trị cũ hơn, nó ghi đè giá trị mới vào bản đó ngay. Sửa "thụ động" — chỉ dữ liệu được đọc mới được hàn.
• Anti-entropy (đồng bộ nền): một tiến trình nền định kỳ so sánh các bản và chép phần thiếu — kể cả dữ liệu ít được đọc (thứ read repair bỏ sót). So sánh nguyên hai bản thì tốn; nên dùng Merkle tree để tìm nhanh chỗ khác nhau mà không truyền cả dữ liệu.

Việc phát tán thông tin thành viên/trạng thái giữa các node (ai còn sống, ai giữ khoảng khoá nào) thường dùng gossip — cũng là cơ chế bạn đã gặp ở track thuật toán.

5. Pitfall — tưởng quorum là nhất quán mạnh

❌ Tuong: R+W>N => moi doc thay ghi moi nhat, thu tu chuan
   Thuc te:
   - sloppy quorum lay ban tam -> W ack KHONG trong N goc -> doc co the truot
   - hai ghi SONG SONG -> quorum khong quyet duoc cai nao dung -> van xung dot
   - trong luc read repair chua chay het -> hai client co the thay 2 gia tri

6. 📚 Deep Dive

7. Liên hệ các bài khác

• Bài 03 — Multi-leader: leaderless cũng đối mặt ghi song song và dùng chính version/vector clock để giải — cùng bài toán xung đột, kiến trúc khác (không leader).
• Bài 02 — Replication lag: quorum R+W>N là cách giảm stale read chủ động, thay vì chỉ sống chung với lag bằng các đảm bảo session.
• Module 3 — Phân mảnh: Dynamo dùng consistent hashing để chọn N bản cho mỗi khoá — replication và partitioning gắn chặt ở đây.
• Module 6 — Consistency & consensus: vì sao quorum ≠ linearizability, và khi nào phải trả giá cho nhất quán mạnh.

8. Tóm tắt

• Leaderless: không leader; ghi tới nhiều bản (thành công khi W ack), đọc từ nhiều bản (lấy mới nhất trong R).
• Quorum R+W>N: tập ghi và tập đọc chắc chắn giao nhau → đọc chạm ít nhất một bản có ghi mới nhất. R, W là hai cần gạt nghiêng đọc-nhanh vs ghi-nhanh.
• Quorum là nhất quán cao xác suất, không tuyệt đối: sloppy quorum, ghi song song, ghi lỗi một phần đều tạo kẽ hở.
• Read repair (sửa lúc đọc) + anti-entropy (đồng bộ nền, Merkle tree) hàn các bản lệch; gossip phát tán trạng thái thành viên.
• Không có thứ tự ghi toàn cục → ghi song song vẫn xung đột, giải bằng version/vector clock (như bài 03).
• Anti-pattern: coi R+W>N là linearizability → dùng cho check-and-set/khoá → sai âm thầm. Thao tác cần đảm bảo tuyệt đối thuộc về consensus (Module 6).

9. Tự kiểm tra

Bài tiếp theo: Chọn mô hình replication theo workload