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

TL;DR: Module 4 trang bị sáu thuật toán nền tảng của hệ phân tán: consistent hashing phân mảnh dữ liệu lên ring chỉ dời K/N key khi co giãn, quorum R+W>N đảm bảo nhất quán khi đọc/ghi trên nhiều replica, Merkle tree phát hiện và sửa chênh lệch replica trong O(log N), vector clock theo dõi quan hệ nhân quả giữa các sự kiện không có đồng hồ chung, gossip lan truyền membership theo kiểu epidemic O(log N) bước, Raft đưa toàn cluster về một lịch sử log nhất quán duy nhất. Trang này là cheat sheet: bảng 6 thuật toán theo bài toán, glossary 18 thuật ngữ, 6 pitfall hay gặp, self-assessment 5 câu khớp learning outcomes.

Đã đi qua những gì

Bạn bắt đầu từ câu hỏi nền tảng: tại sao hệ phân tán cần thuật toán riêng? Vì không có shared memory, không có global clock, không có node nào biết đầy đủ trạng thái hệ thống. Sáu thuật toán trong module là sáu cách giải quyết hệ quả của sự thiếu vắng đó.

Bài 01 — Consistent hashing giải quyết phân mảnh: key và node đều được hash lên vòng tròn [0, 2^64). Key thuộc về node có position kế tiếp theo chiều kim đồng hồ. Thêm/bớt node chỉ dời khoảng K/N key thay vì rehash toàn bộ như modulo hashing. Virtual node (vnode) nhân bản mỗi node vật lý lên nhiều position trên ring để phân bố tải đều khi node có capacity khác nhau.

Bài 02 — Quorum giải quyết nhất quán khi đọc/ghi trên nhiều replica: với N replica, nếu ghi W replica và đọc R replica sao cho R+W>N, tập replica đọc và tập replica ghi phải overlap ít nhất 1 — đảm bảo luôn đọc được giá trị mới nhất. Điều kiện mạnh hơn: W>N/2 tránh write conflict (hai write đồng thời không thể cùng thành công). CAP theorem giải thích tại sao không thể có cả nhất quán (C), availability (A), partition tolerance (P) cùng lúc — hệ thống phải chọn 2 trong 3.

Bài 03 — Merkle tree giải quyết phát hiện và sửa chênh lệch giữa replica: mỗi block dữ liệu được hash, rồi hash của cặp block tạo thành node cha, đến tận root. Hai replica so sánh Merkle root: nếu trùng, dữ liệu giống nhau hoàn toàn; nếu khác, đi xuống cây theo nhánh sai đến đúng block bị chênh lệch trong O(log N) thay vì O(N). Git dùng Merkle tree để xác minh tính toàn vẹn của commit history.

Bài 04 — Vector clock giải quyết thứ tự sự kiện không có đồng hồ chung: mỗi process giữ một vector [c1, c2, ..., cN] đếm số sự kiện mà nó biết của từng process khác. Sự kiện A happens-before B nếu vector của A nhỏ hơn hoặc bằng vector của B trên mọi chiều. Nếu không thể so sánh (A không nhỏ hơn B và B không nhỏ hơn A), hai sự kiện là concurrent — không có thứ tự nhân quả.

Bài 05 — Gossip giải quyết lan truyền thông tin membership không có coordinator: mỗi node định kỳ chọn ngẫu nhiên vài node và trao đổi trạng thái. Sau O(log N) vòng, thông tin lan khắp cluster. Gossip chịu được node fail tốt vì không có single point of failure trong việc phát tán thông tin. Cassandra dùng gossip cho membership; Bitcoin dùng gossip để lan truyền giao dịch.

Bài 06 — Raft giải quyết consensus mạnh: leader duy nhất quyết định thứ tự entry trong log, nhân bản đến đa số follower trước khi commit. Leader election dùng term và randomized timeout để tránh split vote. Log replication đảm bảo follower có đúng log của leader — khi leader fail, follower có log đầy đủ nhất sẽ được bầu làm leader mới. etcd và Consul dùng Raft làm backbone.

Bài 07 — Mini-challenge tự cài hash ring với virtual node: lookup O(log N) bằng binary search, đo tỷ lệ key di chuyển ~K/N so với modulo ~100%.

Bài 08 — Case study thấy Cassandra ghép cả bốn thuật toán đầu (consistent hashing ring + tunable quorum + gossip membership + Merkle anti-entropy) để đạt AP, còn etcd dùng Raft để đạt CP — hai triết lý thiết kế phục vụ hai bài toán khác nhau.

🗺️ Cheat sheet

Bảng 6 thuật toán theo bài toán

Quyết định chọn thuật toán

graph TD
    START["Bài toán phân tán"] --> Q1{"Bài toán\nchính là?"}
    Q1 -- "Key ở node nào?\nCo giãn cluster" --> CH["Consistent hashing\n+ virtual node"]
    Q1 -- "Đọc/ghi nhất quán\ntrên replica" --> QU["Quorum R+W>N\n(chọn R,W theo SLA)"]
    Q1 -- "Phát hiện chênh lệch\ngiữa replica" --> MK["Merkle tree\n(anti-entropy)"]
    Q1 -- "Thứ tự sự kiện\nkhông đồng hồ" --> VC["Vector clock\n(happens-before)"]
    Q1 -- "Lan truyền info\nkhắp cluster" --> GO["Gossip protocol\n(eventual, O(log N))"]
    Q1 -- "Đồng thuận mạnh\ntoàn cluster" --> Q2{"Cluster\nnhỏ (<7 node)?"}
    Q2 -- "Có" --> RA["Raft\n(linearizable)"]
    Q2 -- "Không" --> PA["Paxos variants\nSpanner, CockroachDB"]

CAP quick-reference

📖 Glossary

⚠️ Pitfall tổng hợp

Pitfall 1 — Nhầm consistent hashing với modulo hashing.

-- SAI: dùng modulo cho distributed cache
node <- nodes[hash(key) % nodes.length]
-- Khi thêm 1 node: hash(key) % (N+1) ≠ hash(key) % N cho ~N/(N+1) key
-- → gần như toàn bộ cache miss, stampede

-- ĐÚNG: dùng consistent hashing ring
node <- lookupRing(ring, key)
-- Khi thêm 1 node: chỉ ~1/(N+1) key đổi node

Pitfall 2 — Đặt R+W = N thay vì R+W > N.

-- SAI: R=1, W=2, N=3 → R+W = 3 = N (không đảm bảo overlap)
-- Ví dụ: ghi W={Node1, Node2}, đọc R={Node3} → có thể đọc stale

-- ĐÚNG: R=2, W=2, N=3 → R+W = 4 > 3 (luôn overlap ít nhất 1 node)

Pitfall 3 — Đồng bộ vector clock khi merge sai.

-- SAI: merge bằng cách cộng, không lấy max
A.vc[i] <- A.vc[i] + B.vc[i]   -- sai: tạo ra vector không có ý nghĩa nhân quả

-- ĐÚNG: merge bằng cách lấy max từng chiều
A.vc[i] <- max(A.vc[i], B.vc[i])  -- đúng: cập nhật knowledge về mỗi process

Pitfall 4 — Gossip nhầm "eventual" là "ngay lập tức".

Gossip đảm bảo thông tin sẽ lan đến mọi node, nhưng mất O(log N) vòng (vài giây). Nếu đọc membership ngay sau khi một node join, có thể chưa thấy node đó. Không dùng gossip cho các quyết định cần strong consistency (ví dụ: tìm leader hiện tại).

Pitfall 5 — Raft election timeout quá ngắn gây election vòng.

-- SAI: election timeout cố định cho mọi node
ELECTION_TIMEOUT <- 150ms   -- tất cả node timeout cùng lúc → split vote liên tục

-- ĐÚNG: randomized timeout
ELECTION_TIMEOUT <- random(150ms, 300ms)   -- node đầu tiên hết timeout thường thắng

Pitfall 6 — Xây Merkle tree trên toàn bộ data mỗi lần repair thay vì partition theo token range.

Cassandra không xây một Merkle tree duy nhất cho toàn bộ data — nó xây Merkle tree trên từng token range (partition range). Nếu xây toàn bộ, khi hai replica chỉ khác 1 key vẫn phải rebuild cả tỷ-entry tree. Phân chia theo range giúp repair song song và granular hơn.

✅ Self-assessment

Bạn đã đạt module này nếu trả lời được:

• Giải thích được 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 — cho ví dụ cụ thể với Cassandra 1 000 node hoặc etcd làm backing store Kubernetes.
  • Nếu chưa: đọc lại bài 00 — Tổng quan mục "Vì sao module này tồn tại" và bài 08 — Case study mục "Vì sao etcd chọn CP".
• Implement được consistent hashing ring có virtual node, lookup key → node O(log N) bằng binary search, tính và giải thích tỷ lệ key di chuyển ~K/N khi thêm node so với modulo hashing ~100%.
  • Nếu chưa: làm lại bài 07 — Mini-challenge từ đầu không xem lời giải; đọc lại bài 01 — Consistent hashing mục virtual node và migration.
• Giải thích được cơ chế quorum R+W>N đảm bảo strong consistency và phân tích CAP tradeoff khi node fail trong Cassandra — tại sao QUORUM vẫn hoạt động khi 1 trong 3 node fail, tại sao ALL thì không.
  • Nếu chưa: đọc lại bài 02 — Quorum mục chứng minh overlap và bài 08 — Case study bảng consistency level.
• Trace được Raft leader election (term + vote) và log replication (AppendEntries + commit index) theo từng bước với 3 node để hiểu tại sao hệ thống vẫn nhất quán khi có minority failure.
  • Nếu chưa: đọc lại bài 06 — Raft và trace tay với 3 node: 1 leader gửi AppendEntries cho 2 follower, 1 follower crash, vẫn commit được.
• Compare được gossip (eventual consistency, epidemic propagation) với Raft (strong consensus, log replication) theo latency, partition tolerance và use-case phù hợp — giải thích tại sao Cassandra dùng gossip cho membership nhưng không thể dùng gossip để đảm bảo linearizability như etcd.
  • Nếu chưa: đọc lại bài 05 — Gossip và bài 08 — Case study mục "Cassandra AP vs etcd CP".

🚀 What's next

Module 4 hoàn thành bức tranh về thuật toán phân tán — từ phân mảnh không xáo trộn đến nhất quán replica đến đồng thuận mạnh. Module 5 — Hình học & Spatial chuyển sang một lớp bài toán hoàn toàn khác: dữ liệu địa lý và không gian. Quadtree và R-tree phân vùng không gian 2D để tìm kiếm điểm gần nhất, bounding box query và range query hiệu quả — nền tảng của Google Maps, Uber surge pricing và PostGIS.

Bài tiếp theo: Module 5 — Hình học & Spatial

📚 Tài liệu mở rộng

• Designing Data-Intensive Applications (Kleppmann), Chapter 5-9: Giải thích chi tiết replication, partitioning, transactions, consistency và consensus với các ví dụ thực tế. Chương 9 (Consistency and Consensus) là tài liệu đọc thêm tốt nhất cho toàn bộ module này.
• Dynamo paper (DeCandia et al., 2007) — "Dynamo: Amazon's Highly Available Key-value Store": Paper gốc mô tả consistent hashing + vector clock + quorum + gossip + Merkle tree trong một hệ thống thực tế. Đây là blueprint của Cassandra. ACM SOSP 2007.
• Raft paper (Ongaro & Ousterhout, 2014) — "In Search of an Understandable Consensus Algorithm": Paper gốc trình bày Raft với mục tiêu "dễ hiểu hơn Paxos". Visualization tương tác tại thesecretlivesofdata.com/raft.
• etcd documentation — "Why etcd?": Giải thích tại sao Kubernetes chọn etcd và Raft thay vì các lựa chọn khác. etcd.io/docs.
• Cassandra Architecture — Datastax docs: Hướng dẫn chi tiết về token ring, gossip, consistency level và anti-entropy repair trong Cassandra production. docs.datastax.com.