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

TL;DR: Module 9 dạy sáu thuật toán nền của hệ phân tán, mỗi cái trả lời một câu hỏi. Consistent hashing: key nằm ở máy nào mà thêm máy không phải xáo lại hết. Quorum: đọc ghi bao nhiêu bản thì đủ nhất quán. Merkle tree: hai bản có giống nhau không, khác ở đâu. Vector clock: sự kiện nào xảy ra trước khi không có đồng hồ chung. Gossip: tin lan khắp cluster kiểu tin đồn. Raft: cả cluster đồng ý về cùng một lịch sử lệnh. Đây là nền của Cassandra, etcd và Git.

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

Ba tình huống thực tế dưới đây cho thấy vì sao cần nhóm thuật toán này.

Cassandra cụm cỡ hàng nghìn node (như cụm của Netflix) lưu dữ liệu người xem cỡ petabyte. 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 phần key mà node mới nhận về, cỡ K/(N+1) khi thêm một node (K là tổng số key, N là số node trước khi thêm).

etcd lưu config cho toàn bộ cluster Kubernetes. Mỗi thay đổi (thêm pod, scale deployment) phải được mọi node ghi nhận giống nhau. Nếu có node chết 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 đó: một lần ghi chỉ tính là committed (đã chốt) khi đa số node xác nhận.

Git tính hash cho mỗi commit và dùng cây kiểu Merkle để kiểm tra dữ liệu có bị sửa không: đổi một byte trong lịch sử là hash của mọi commit phía sau đổi theo. Đó là Merkle tree dùng cho version control.

Ba tình huống này có chung một điểm: không có bộ nhớ dùng chung, không có đồng hồ chung, và không node nào biết đủ trạng thái của cả hệ thống. Thuật toán đơn máy dựa vào cả ba thứ đó, nên cần thuật toán riêng cho hệ phân tán.

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 làm tập đọc và tập ghi giao nhau (chưa phải linearizable), các kẽ hở của nó 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, giải thích vì sao hệ thống vẫn nhất quán khi có minority failure và vì sao đọc từ leader cần xác nhận quyền (ReadIndex).
• Compare gossip (eventual consistency, epidemic propagation, phát hiện node chết bằng SWIM/phi-accrual) 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: phân mảnh dữ liệu (bài 01), nhất quán replica (bài 02, 03), đồng bộ sự kiện (bài 04) và membership kèm đồng thuận (bài 05, 06). Hiểu bốn nhóm này là biết chọn đúng thuật toán.

Lộ trình module

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

Bài 01: Consistent hashing đứng đầu vì mọi thứ bên trên đều cần biết key nằm ở đâu.

Bài 02: Quorum xây ngay trên ring: đã biết key ở node nào thì mới hỏi được cần bao nhiêu node xác nhận.

Bài 03: Merkle tree đứng sau quorum vì quorum vẫn để replica lệch nhau, và cần cách tìm chỗ lệch mà không so từng key.

Bài 04: Vector clock chuyển sang thời gian: khi replica lệch, cần biết bản nào có trước mà không có đồng hồ chung.

Bài 05: Gossip cho thấy các node tự biết nhau còn sống thế nào khi không có máy trung tâm, nên đứng trước Raft.

Bài 06: Raft là đỉnh của module: đồng thuận (consensus) cần mọi thứ trước đó làm nền. Leader election và log replication tránh split-brain, tức là hai nhóm node cùng tin mình là chủ và cùng nhận ghi. 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, từ điển thuật ngữ và phần tự kiểm tra.

Sáu thuật ngữ bằng lời thường

Vài từ sẽ lặp lại suốt module. Đọc qua một lần, mỗi bài sẽ giải thích kỹ hơn.

• Quorum: số máy tối thiểu phải trả lời trước khi coi một lần đọc hoặc ghi là xong, thường là hơn một nửa. Giống bỏ phiếu: quá nửa đồng ý thì tính.
• Vector clock: mỗi máy giữ một bảng đếm "tôi đã thấy bao nhiêu việc của từng máy". So hai bảng là biết việc nào có trước, hay hai việc xảy ra song song.
• Gossip: mỗi máy cứ vài giây kể tin mình biết cho vài máy ngẫu nhiên, như tin đồn trong xóm. Không cần ai làm loa phát thanh mà tin vẫn lan hết.
• Term: số thứ tự nhiệm kỳ của leader trong Raft. Nhiệm kỳ mới thì số lớn hơn, nên tin nhắn từ leader cũ dễ nhận ra là hết hạn.
• Leader election: cả nhóm bầu ra một máy làm trưởng nhóm. Chỉ trưởng nhóm được quyết thứ tự lệnh, cho khỏi cãi nhau.
• Anti-entropy: việc định kỳ so các bản sao với nhau rồi vá chỗ lệch.

Bản đồ khái niệm

Vào từ phía bài toán, không phải từ phía hệ thống đang dùng, nhờ vậy cây còn dùng được khi đổi hệ thống. Hai nhánh cuối trông như hai mức của cùng một thứ, nhưng chúng đứng ở hai phía của CAP.

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 khoá Thuật toán Cốt lõi trước khi học consistent hashing.

Thời lượng

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 vì bạn đã biết nó giải bài toán nào.

Với consistent hashing, vẽ ring tay. Làm tay trước khi làm máy là thói quen đã ôn ở Làm tay trước khi làm máy. 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), kẻ bảng như ở Bảng trace. Cảm giác "quá nửa (2/3) mới được tiến" sẽ đến sau khi bạn trace ít nhất một tình huống có node chết.

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