Reliable Broadcast 101

Định nghĩa

Reliable broadcast là một phần lõi quan trọng trong kiến trúc các hệ thống phân tán. Nó có một mục đích đơn giản: đảm bảo “truyền tin nhắn” (broadcast) một cách đáng tin cậy (reliable) từ một node đến nhiều node trong một node-cluster. “Reliable” nghĩa rằng việc truyền tin nhắn vẫn được đảm bảo cho dù kết nối giữa các node có bị vỡ đi chăng nữa.

Xây dựng một hệ thống phân tán đòi hỏi việc truyền và nhận tin nhắn giữa các bên phải đáng tin cậy, “Reliable Broadcast” giúp chúng ta thực hiện điều đó.

Simple broadcast

Một broadcasted message m sẽ được nhân rộng (replicated) tại node sender và sau đó được gửi tới tất cả node khác trong một cluster.

Hình vẽ dưới cho thấy có một node (màu đỏ) trong cluster không thể nhận được broadcast message m gửi bởi node sender (do kết nối mạng giữa node đó với node gửi bị hỏng).

Nếu chúng ta muốn đảm bảo rằng node màu đỏ kia vẫn nhận được broadcast message trong trường hợp trên thì simple broadcast algorithm không đủ tốt để sử dụng.

Reliable broadcast naive algorithm

Reliable broadcast algorithm mở rộng Simple broadcast algorithm để việc truyền tin vẫn hoạt động ngay cả khi một số liên kết (mạng) giữa các node bị lỗi. Có nhiều cách triển khai khác nhau, ví dụ như:

Node p gửi m tới tất cả các node khác bao gồm chính nó
Mỗi node nhận được m lần đầu tiên, gửi tiếp m tới tất cả những node khác trong cluster (ngoại trừ node sender)

func Broadcast(m Message) {
	SendToAllNodes(m);
}

func Receive(m Message) {
	if !previouslyProcessed(m) {
		// Lần đầu nhận được tin nhắn này
		// Broadcast lại lần nữa
		Broadcast(m);
		// Xử lí tin nhắn
		Process(m);
	}
}

Hình vẽ bên dưới cho thấy cách hoạt động của một reliable broadcast. Miễn là có liên kết mạng từ node này đến nút node, message sẽ vẫn được broadcart.

Trường hợp duy nhất mà reliable broadcast không thể gửi tin nhắn tới tất cả node là khi một số node nào đó hoàn toàn bị ngắt kết nối với các node còn lại trong cluster (trường hợp này thì vô phương cứu chữa).

Implement: previouslyProcessed()?

Để kiểm tra xem tin nhắn được nhận đã được xử lí trước chưa (tại một node), có thể gán cho mỗi tin nhắn một ID, hoặc hash và lưu các IDs hoặc hash đã được xử lí vào Storage (DB, caching). Cách này sẽ làm tốn bộ nhớ thêm sau mỗi tin nhắn được xử lí, do đó nên có cơ chế reset định kì DB lưu trữ các IDs/hashes này.

func previouslyProcessed(m String) bool {
	hash := generateHashFromString(m)
	if isExistedInStorage(hash) {
		return true
	}

	addMessageHashToStorage(hash)
	return false
}

Atomic Broadcast

Atomic broadcast là một phần mở rộng của giao thức reliable broadcast để đáp ứng được ”total order property”, điều đó có nghĩa là tất cả những node tham gia nhận tin nhắn đều nhận được tin nhắn và nhận được theo thứ tự giống nhau. “Total order property” khá hữu ích để xây dựng các replicated state machines vì mỗi tin nhắn có thể đại diện cho một số loại chuyển đổi trạng thái (state transitions) khác nhau. Vì tất cả các tin nhắn được broadcast một cách đáng tin cậy theo thứ tự, tất cả các node đều nhận được các state transitions (chuyển đổi trạng thái) giống nhau và do đó đạt đến cùng một state giống nhau.

Atomic Broadcast == Consensus

Người ta đã cho thấy rằng atomic broadcast và consensus (thuật toán đồng thuận) khá tương đương nhau. Và vì các vấn đề khó khăn của consensus đã được giải quyết bằng Paxos và Raft (và nhiều thuật toán khác nữa), atomic broadcast theo đó sẽ được giải thích và triển khai một cách đơn giản hơn.

(Vì vậy phần Atomic Broadcast sẽ được cập nhật sau khi đã research xong phần consensus)