Thuật toán phân tán

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

Khi dữ liệu trải nhiều máy: consistent hashing, quorum, Merkle tree, vector clock, gossip, Raft. Nền của Cassandra, etcd, Git.

Consistent hashing — thêm/bớt node ít xáo trộn

Ánh xạ key và node lên vòng tròn hash; thêm/bớt node chỉ di chuyển K/N key thay vì rehash toàn bộ. Virtual node cân bằng tải.

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

Đọc R bản, ghi W bản; nếu R+W>N thì tập đọc và tập ghi luôn giao nhau nên đọc thấy ghi mới nhất. Tunable consistency và đánh đổi C vs A theo CAP.

Merkle tree — phát hiện khác biệt hiệu quả

Cây hash cho phép so sánh hai tập dữ liệu lớn và xác định phần khác nhau trong O(log n). Anti-entropy của Cassandra, sync của Git.

Vector clock — thứ tự nhân quả sự kiện

Mỗi node giữ vector đếm; so sánh vector xác định quan hệ happens-before hay concurrent. Phát hiện conflict trong hệ phân tán.

Gossip protocol — lan truyền trạng thái

Mỗi node định kỳ trao đổi thông tin với vài node ngẫu nhiên; trạng thái lan toàn cụm theo cấp số nhân. Membership của Cassandra.

Raft — đồng thuận leader & log replication

Thuật toán consensus dễ hiểu: bầu leader, nhân bản log, commit khi đa số xác nhận. Nền của etcd, Consul, TiKV.

Mini-challenge — consistent hashing ring có virtual node

Lab: cài hash ring với virtual node, lookup key → node O(log N), đo tỷ lệ key di chuyển khi thêm/bớt node so với modulo hashing.

Case study — Cassandra ring & etcd Raft

Cassandra ghép consistent hashing + tunable quorum + gossip + Merkle tree ra sao; etcd dùng Raft cho config nhất quán mạnh thế nào. Vì sao một chọn AP, một chọn CP.

Module 4 — Tổng kết & cheat sheet

Recap phân tán: cheat sheet 6 thuật toán theo bài toán, glossary 18 thuật ngữ, pitfall tổng hợp, self-assessment match learning outcomes.