Module 9 — Tổng kết & cheat sheet
Recap phân tán: cheat sheet 6 thuật toán theo bài toán, 18 thuật ngữ bằng lời thường, bẫy hay gặp, tự kiểm tra khớp learning outcomes.
TL;DR: Module 9 gồm sáu thuật toán nền của hệ phân tán. Consistent hashing chia key lên các máy mà thêm máy chỉ dời cỡ K/(N+1) key. Quorum R+W>N làm tập đọc chạm bản ghi đã xác nhận. Merkle tree chỉ ra hai replica lệch ở đâu. Vector clock phân biệt "có trước" với "xảy ra song song". Gossip lan tin khắp cluster sau O(log N) vòng. Raft đưa cả cluster về một lịch sử lệnh duy nhất. Trang này là cheat sheet: bảng 6 thuật toán theo bài toán, 18 thuật ngữ, 3 bẫy liên module và 5 câu tự kiểm tra khớp learning outcomes.
Đã đi qua những gì
Bạn bắt đầu từ một câu hỏi: tại sao hệ phân tán cần thuật toán riêng? Vì không có bộ nhớ chung, không có đồng hồ chung, và không máy nào biết đủ trạng thái của cả hệ thống. Sáu thuật toán là sáu cách xử lý hệ quả của việc thiếu ba thứ đó.
Chi tiết từng thuật toán nằm ở bài 01 đến 08; bảng dưới gom chúng lại theo bài toán cần giải.
Cheat sheet
Bảng 6 thuật toán theo bài toán
| Thuật toán | Bài toán giải | Đánh đổi chính | Hệ thống thật |
|---|---|---|---|
| Consistent hashing | Phân mảnh key lên N node không xáo trộn khi co giãn | Cần sorted ring + binary search; vnode tốn thêm bộ nhớ | Cassandra, Dynamo, client Memcached (ketama) |
| Quorum R+W>N | Đọc/ghi nhất quán trên replica khi một số node chết | R+W cao → consistency tốt nhưng latency cao; R+W thấp → nhanh nhưng có thể đọc bản cũ (stale) | Cassandra (tunable), Riak, Dynamo (bài báo gốc) |
| Merkle tree | Phát hiện và sửa chênh lệch giữa replica trong O(log N) | Dựng tree tốn O(N) mỗi lần repair; chỉ hiệu quả khi chênh lệch nhỏ | Cassandra anti-entropy, Git, ZFS |
| Vector clock | Theo dõi quan hệ nhân quả giữa các sự kiện khi không có đồng hồ chung | Vector dài ra theo số process; chỉ phát hiện conflict chứ không tự giải quyết | Dynamo (bài báo gốc), Riak |
| Gossip protocol | Lan truyền membership và phát hiện node chết mà không cần coordinator | Eventual consistency (vài giây trễ); thông tin có thể cũ trước khi hội tụ | Cassandra, Bitcoin, Consul |
| Raft consensus | Đồng thuận mạnh trên một log thứ tự duy nhất | Mỗi nhóm Raft thường chỉ 3 đến 7 node; mất quorum = mất availability | etcd, Consul, TiKV, CockroachDB |
Quyết định chọn thuật toán
CAP tra nhanh
| Hệ thống | C | A | P | Lý do |
|---|---|---|---|---|
| Cassandra (ONE) | ✗ | ✓ | ✓ | AP: luôn ghi được, eventual consistency |
| Cassandra (QUORUM) | ✓ (khi đạt quorum) | ✗ (khi không đạt quorum) | ✓ | Mạng chia mà không đủ quorum thì từ chối, nghiêng về CP (nhưng R+W>N một mình chưa bằng linearizable) |
| etcd / Raft | ✓ | ✗ (khi mất quorum) | ✓ | CP: từ chối phục vụ khi mất quorum |
| Zookeeper | ✓ (ghi; đọc từ follower có thể cũ, cần sync()) | ✗ (leader election) | ✓ | CP: tương tự etcd |
All-Access Pass
Phần còn lại của bài dành cho All-Access Pass
Bạn vừa đọc phần xem trước. Hai bài đầu của mỗi khoá luôn đọc trọn miễn phí.
- Đọc trọn mọi bài trong 6 khoá System Design và dữ liệu phân tán
- AI Mentor trả lời theo toàn bộ nội dung bài
- Trả một lần, không tự gia hạn, không tự trừ tiền
Trọn đời
1.690.000 ₫
Trả một lần, dùng mãi mãi
Gói năm
699.000 ₫
365 ngày · ≈ 58.000 ₫/tháng
Thanh toán bằng thẻ Visa/Master/JCB qua Polar. Xem bảng giá
Bài này có giúp bạn hiểu bản chất không?
Bài này đáng gửi cho bạn học cùng?
Copy link đã gắn nguồn — dán group, chat, hoặc LinkedIn.
Thảo luận & góp ý
Hỏi đáp về bài này