Module 4 — Thuật toán phân tán: tổng quan

TL;DR: Module 4 dạy sáu thuật toán nền tảng của hệ phân tán — từ consistent hashing giải quyết bài toán phân mảnh dữ liệu không xáo trộn khi co giãn cluster, quorum đảm bảo nhất quán khi node fail, Merkle tree phát hiện chênh lệch dữ liệu giữa các replica, vector clock theo dõi thứ tự sự kiện không có đồng hồ chung, gossip lan truyền thông tin kiểu dịch bệnh, đến Raft đưa cả cluster về một lịch sử log duy nhất. Đây là nền của Cassandra, etcd, Git và mọi hệ thống phân tán hiện đại — hiểu sáu thuật toán này là hiểu tại sao chúng hoạt động được.

Vì sao module này tồn tại

Hãy xét ba tình huống thực tế:

Cassandra 1 000 node tại Netflix lưu hàng petabyte dữ liệu người xem. Khi thêm 100 node mới để mở rộng, làm sao biết key nào chuyển sang node nào mà không phải rehash toàn bộ — tức là không làm cả hệ thống ngừng hoạt động? Modulo hashing (hash(key) % N) sẽ dời gần như 100% key khi N thay đổi. Consistent hashing chỉ dời khoảng K/N key (K = tổng số key).

etcd lưu config cho toàn bộ cluster Kubernetes — mỗi thay đổi (thêm pod, scale deployment) phải được ghi nhận nhất quán trên mọi node. Nếu có node fail giữa chừng, cluster không được rơi vào trạng thái mâu thuẫn. Raft đảm bảo điều này bằng cách yêu cầu đa số node xác nhận trước khi một ghi được coi là committed.

Git tính hash của mỗi commit và dùng tree cấu trúc Merkle để xác minh tính toàn vẹn — thay đổi một byte trong lịch sử sẽ làm thay đổi hash của tất cả commit phía trên. Đây chính là Merkle tree ứng dụng cho version control.

Ba tình huống này đều có điểm chung: không có shared memory, không có global clock, không có node nào biết trạng thái đầy đủ của hệ thống. Đây là lý do các thuật toán phân tán tồn tại — chúng giải quyết bài toán mà thuật toán đơn máy không thể giải quyết trực tiếp.

Sau module này bạn sẽ

• Explain vì sao hệ phân tán không có shared memory và global clock, dẫn đến cần thuật toán riêng cho phân mảnh, nhất quán và đồng thuận.
• Implement consistent hashing ring có virtual node: lookup key → node O(log N), tính tỷ lệ key di chuyển khi thêm/bớt node so với modulo hashing.
• Explain cơ chế quorum R+W>N đảm bảo strong consistency và phân tích CAP tradeoff khi node fail trong Cassandra.
• Trace Raft leader election (term + vote) và log replication (AppendEntries + commit index) theo từng bước để hiểu tại sao hệ thống vẫn nhất quán khi có minority failure.
• Compare gossip (eventual consistency, epidemic propagation) với Raft (strong consensus, log replication) theo latency, partition tolerance và use-case phù hợp.

Bốn nhóm bài toán phân tán

Sáu thuật toán trong module giải quyết bốn nhóm bài toán khác nhau — hiểu bốn nhóm này là chìa khoá chọn đúng thuật toán:

Consistent hashing — key nào lên node nào, co giãn không rehash

Quorum R+W>N, Merkle tree anti-entropy — đọc/ghi nhất quán, phát hiện chênh lệch

Vector clock — happens-before, concurrent, nhân quả không cần đồng hồ

Gossip lan truyền membership, Raft đồng thuận log — hai mức nhất quán khác nhau

Lộ trình module

flowchart LR
    OV["00\nTổng quan"] --> CH["01\nConsistent\nHashing"]
    CH --> QU["02\nQuorum\nR+W>N"]
    QU --> MK["03\nMerkle\nTree"]
    MK --> VC["04\nVector\nClock"]
    VC --> GO["05\nGossip\nProtocol"]
    GO --> RA["06\nRaft\nConsensus"]
    RA --> MC["07\nMini-challenge\nHash ring"]
    MC --> CS["08\nCase study\nCassandra & etcd"]
    CS --> REC["09\nTổng kết"]

Thứ tự bài — vì sao thiết kế như vậy

Bài 01 — Consistent hashing là điểm xuất phát vì nó giải quyết bài toán nền tảng nhất: key đặt ở đâu. Không có phân mảnh đúng, mọi thuật toán nhất quán bên trên đều vô nghĩa.

Bài 02 — Quorum xây ngay trên consistent hashing: đã biết key ở node nào, câu hỏi tiếp theo là đọc/ghi cần bao nhiêu node xác nhận để nhất quán. Quorum R+W>N là câu trả lời toán học.

Bài 03 — Merkle tree giải quyết bài toán kiểm tra: hai replica có giống nhau không, khác ở đâu, mà không phải so từng key. Đây là cơ chế anti-entropy của Cassandra và tính toàn vẹn của Git.

Bài 04 — Vector clock chuyển sang bài toán thời gian: không có đồng hồ chung, làm sao biết sự kiện A xảy ra trước hay sau B? Vector clock mã hóa quan hệ nhân quả (happens-before) qua message.

Bài 05 — Gossip là cơ chế lan truyền thông tin kiểu epidemic: mỗi node chỉ nói chuyện với vài node ngẫu nhiên, nhưng thông tin lan khắp cluster trong O(log N) bước. Cassandra dùng gossip cho membership.

Bài 06 — Raft là đỉnh của module: consensus mạnh — toàn cluster đồng ý trên một lịch sử log duy nhất. Leader election + log replication đảm bảo không có split-brain. etcd và Consul dùng Raft.

Bài 07 — Mini-challenge tự implement hash ring với virtual node và đo tỷ lệ key di chuyển.

Bài 08 — Case study thấy Cassandra ghép cả bốn thuật toán đầu, còn etcd chọn Raft để đổi lấy strong consistency.

Bài 09 — Tổng kết gom cheat sheet, glossary và self-assessment.

Bản đồ khái niệm

graph TD
    PROB["Hệ phân tán:\nkhông shared memory,\nkhông global clock"] --> P1["Phân mảnh\ndữ liệu"]
    PROB --> P2["Nhất quán\ngiữa replica"]
    PROB --> P3["Thứ tự sự kiện\nkhông đồng hồ"]
    PROB --> P4["Đồng thuận\ntoàn cluster"]
    P1 --> CH2["Consistent hashing\n+ virtual node"]
    P2 --> QU2["Quorum R+W>N\n(CAP tradeoff)"]
    P2 --> MK2["Merkle tree\n(anti-entropy)"]
    P3 --> VC2["Vector clock\n(happens-before)"]
    P4 --> GO2["Gossip\n(eventual, AP)"]
    P4 --> RA2["Raft\n(strong, CP)"]

Yêu cầu trước

Module này xây trên hai nền tảng:

• Hash function và hash table — từ Thuật toán Cốt lõi — Hash function: consistent hashing dùng hash để ánh xạ key và node lên vòng tròn; Merkle tree hash từng block dữ liệu.
• Tree và binary search — từ Thuật toán Cốt lõi — Cây tìm kiếm nhị phân và Tìm kiếm nhị phân: consistent hashing ring lưu virtual node trong sorted array, lookup bằng binary search; Merkle tree là cây nhị phân hash.

Nếu bạn chưa quen với hash function (tính đồng đều, tránh collision), đọc bài hash function trong Thuật toán Cốt lõi — Module 1 trước khi học consistent hashing.

Time budget

Cách học module này hiệu quả

Đọc theo thứ tự, đừng nhảy thẳng vào Raft. Raft là bài phức tạp nhất — nhưng nếu đã hiểu consistent hashing (phân mảnh) và quorum (nhất quán), Raft sẽ rõ hơn nhiều vì bạn biết bài toán nó giải quyết là gì.

Với consistent hashing, vẽ ring tay. Vẽ vòng tròn, đặt 3 node, đặt 5 key, tìm node cho mỗi key bằng cách đi theo chiều kim đồng hồ. Sau đó thêm 1 node và quan sát chỉ key nào di chuyển.

Với Raft, trace từng pha. Leader election, log replication, commit — mỗi pha trace tay với 3 node (N=3). Cảm giác "đa số" (2/3) là điều kiện tiến sẽ đến sau khi trace ít nhất một scenario failure.

Làm mini-challenge trước case study. Tự cài hash ring một lần rồi mới đọc case study Cassandra — các con số (% key di chuyển, virtual node count) sẽ có ý nghĩa hơn nhiều.

Bài tiếp theo: Consistent hashing — thêm/bớt node ít xáo trộn