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

TL;DR: Gossip protocol mô phỏng cách dịch bệnh lây lan: mỗi giây mỗi node chọn ngẫu nhiên vài peer, trao đổi trạng thái (push/pull/push-pull). Sau O(log N) vòng, thông tin đã lan tới toàn bộ cụm N node, không cần server trung tâm, không có điểm chết duy nhất (single point of failure). Ưu điểm: mỗi node chỉ xử lý k message mỗi vòng dù cụm to bao nhiêu. Ứng dụng chính: cluster membership và failure detection (phát hiện node chết) bằng SWIM, giao thức ping gián tiếp, hoặc phi-accrual của Cassandra, bộ phát hiện chấm điểm nghi ngờ theo lịch sử heartbeat, cùng service discovery. Nhược điểm: eventual consistency (không phải strong), lượng message tăng theo N, khó debug khi tin sai đã lan rộng.

Hãy hình dung một cụm Cassandra vài trăm node cần biết node nào còn sống, node nào chết, mà không có master node nào chứa danh sách đó. Giải pháp: mỗi node định kỳ "buôn chuyện" với vài node ngẫu nhiên, chia sẻ danh sách thành viên. Sau vài giây, mọi node đều biết trạng thái toàn cụm. Đó là gossip protocol (giao thức tin đồn), lấy cảm hứng từ cách dịch bệnh lây trong cộng đồng.

1. Ý tưởng dịch tễ: tại sao "lây nhiễm" hoạt động

Dịch tễ học chia người thành ba nhóm; gossip mượn nguyên mô hình đó:

Sau mỗi vòng gossip (1 giây), mỗi node infected tiếp xúc k node ngẫu nhiên. Nếu một node susceptible tiếp xúc infected → trở thành infected. Số node biết tin tăng gấp đôi mỗi vòng (nếu k=1 và toàn bộ peer chưa biết) → hội tụ (mọi node cùng biết tin) sau O(log N) vòng.

Ví dụ số liệu: cụm 1024 node, k=1 gossip mỗi giây:

• Lúc đầu: 1 node biết.
• Sau vòng 1: 2 node; sau vòng 2: 4 node.
• Sau vòng 9: ~512 node; sau vòng 10: ~1024 node, tức cả cụm.

Đó là con số lý tưởng, khi mọi lần chọn đều trúng một node chưa biết tin. Đến những vòng cuối, nhiều lần chọn rơi vào node đã biết, nên thực tế (mô phỏng 1024 node, k=1, chỉ push) cỡ 18 vòng mới phủ hết, vẫn cùng bậc O(log N). Kẻ bảng "vòng, số node biết" như trên cũng là một cách làm bảng trace; nếu cần ôn, xem Bảng trace.

So với broadcast trực tiếp (1 node gửi tới N-1 node): O(N) message từ 1 nguồn, tạo nút thắt cổ chai (bottleneck) tại node đó. Với gossip, tải chia đều: mỗi node chỉ xử lý k message/vòng.

Thử ngẫmvới k=1 và mỗi vòng số node biết tin nhân đôi, cụm 2^20 node (khoảng một triệu) cần mấy vòng ở mức lý tưởng, và cụm to gấp nghìn lần 1024 node chậm hơn bao nhiêu vòng?