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

TL;DR: Gossip protocol mô phỏng lây nhiễm dịch tễ: 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 single point of failure. Ưu điểm: tự mở rộng, chịu lỗi cao, phi tập trung hoàn toàn. Ứng dụng chính: cluster membership + failure detection (SWIM, Phi-accrual của Cassandra), CRDT propagation, service discovery. Nhược điểm: eventual consistency (không phải strong), overhead message tăng theo N, khó debug khi thông tin sai lan truyền rộng.

Năm 2007, một cụm Cassandra 200 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. Đây là gossip protocol — kỹ thuật lấy cảm hứng từ cách dịch bệnh lây lan trong cộng đồng.

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

Mô hình SIR trong dịch tễ học: mỗi người trong trạng thái Susceptible (chưa biết), Infected (biết, đang lan), hoặc Removed (đã lan xong). Trong gossip:

• Infected = node đã có thông tin mới, đang gossip với peer.
• Susceptible = node chưa biết tin.

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ụ sau O(log N) vòng.

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

• Vòng 1: 1 node biết.
• Vòng 10: ~512 node biết.
• Vòng 11: ~1024 node biết.

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 bottleneck tại node đó. Với gossip: tải phân tán đều — mỗi node chỉ xử lý k message/vòng.

Thử ngẫmvới cụm 1024 node và k=1, vòng 10 có ~512 node biết tin. Tăng k lên 2 thì cụm hội tụ nhanh gấp đôi, hay nhanh hơn đáng kể hơn thế?

2. Ba chế độ gossip

-- Push: node A gửi state của mình cho B
function gossip_push(A, peers):
    B <- chọn ngẫu nhiên từ peers
    gửi state_A tới B
    B.merge(state_A)
// Tốt khi A có tin mới hơn B

-- Pull: node A hỏi state của B
function gossip_pull(A, peers):
    B <- chọn ngẫu nhiên từ peers
    request_state từ B
    A.merge(state_B)
// Tốt khi A lạc hậu và muốn cập nhật

-- Push-Pull: kết hợp (phổ biến nhất)
function gossip_push_pull(A, peers):
    B <- chọn ngẫu nhiên từ peers
    gửi state_A tới B; nhận state_B từ B
    A.merge(state_B)
    B.merge(state_A)
// Hiệu quả nhất: cả hai node cập nhật trong 1 round-trip

Push-pull thực tế: mỗi giây mỗi node khởi tạo 1 gossip round, trao đổi state với 1–3 peer ngẫu nhiên. Hai bên đều học từ nhau trong cùng một kết nối.

3. Pseudocode vòng gossip chính

-- Mỗi node duy trì: membership_table = { nodeId -> {state, heartbeat, timestamp} }
-- Chạy mỗi interval T (ví dụ 1 giây)

function gossip_round(self):
    -- 1. Tăng heartbeat của chính mình
    membership_table[self].heartbeat <- membership_table[self].heartbeat + 1
    membership_table[self].timestamp <- now()

    -- 2. Chọn ngẫu nhiên k peer để gossip
    peers <- chọn ngẫu nhiên k node từ membership_table (loại trừ self)

    -- 3. Gửi membership table (hoặc digest) tới mỗi peer
    for each peer trong peers:
        gửi membership_table tới peer

function on_receive_gossip(self, remote_table):
    -- 4. Merge: với mỗi entry, giữ version heartbeat cao hơn
    for each (nodeId, remote_entry) trong remote_table:
        if nodeId không tồn tại trong membership_table:
            membership_table[nodeId] <- remote_entry  -- node mới join
        else if remote_entry.heartbeat > membership_table[nodeId].heartbeat:
            membership_table[nodeId] <- remote_entry  -- cập nhật mới hơn

function detect_failures(self):
    -- 5. Đánh dấu node suspect nếu heartbeat không tăng trong timeout
    for each (nodeId, entry) trong membership_table:
        if now() - entry.timestamp > SUSPECT_TIMEOUT:
            đánh dấu nodeId là SUSPECT
        if now() - entry.timestamp > DEAD_TIMEOUT:
            đánh dấu nodeId là DEAD

// Time: O(k * n) message mỗi vòng, n = kích thước membership table
// Space: O(n) per node

Điểm cốt lõi ở bước merge: giữ heartbeat cao hơn đảm bảo thông tin mới nhất luôn thắng — đây là dạng last-write-wins đơn giản với heartbeat làm version.

Thử ngẫmtrong on_receive_gossip, điều kiện chỉ so remote_entry.heartbeat > membership_table[nodeId].heartbeat. Heartbeat hai bên bằng nhau nhưng timestamp khác nhau thì node nào thắng — và đó có phải hành vi đúng không?

4. Lan truyền qua các vòng gossip

Gossip nhanh không phải vì mỗi bước nhanh, mà vì số node biết tin nhân đôi sau mỗi vòng. Cụm 1000 node cũng chỉ mất 10 vòng — đó là lý do Cassandra dám dùng gossip cho cụm hàng trăm node mà không cần node điều phối nào.

5. Failure detection — SWIM và Phi-accrual

5.1 SWIM (Scalable Weakly-consistent Infection-style Membership)

SWIM (Das et al. 2002) tách failure detection ra khỏi membership protocol:

1. Node A ping node B định kỳ. Nếu không nhận ACK sau timeout:
2. A chọn k node ngẫu nhiên, nhờ chúng indirect ping B.
3. Nếu vẫn không có ACK: A đánh dấu B là suspect, gossip tin suspect toàn cụm.
4. Nếu B không phản bác trong SUSPECT_TIMEOUT: chuyển thành dead, gossip tin dead.

Indirect ping tránh false positive do mạng partition cục bộ giữa A và B — nếu k node khác đều không liên lạc được B thì mới thật sự dead.

5.2 Phi-accrual failure detector (Cassandra)

Thay vì "dead/alive" nhị phân, Cassandra dùng phi-accrual detector: tính xác suất phi (φ) rằng node đã chết dựa trên lịch sử heartbeat interval. φ tăng theo thời gian không nhận heartbeat. Ứng dụng đặt ngưỡng (ví dụ φ vượt 8 → node DEAD) thay vì threshold cứng — thích nghi tốt hơn với mạng có độ trễ biến động.

6. So sánh với broadcast và central registry

Thử ngẫmteam bạn có cluster chỉ 8 node nội bộ, ổn định, không scale thêm. Gossip protocol có đáng dùng ở quy mô này so với central registry đơn giản hơn?

7. Pitfall

Pitfall 1 — Quên merge hai chiều trong push-pull

-- SAI: chi cap nhat mot chieu
function on_push_pull_wrong(self, remote_table):
    for each (id, entry) trong remote_table:
        if entry.heartbeat > membership_table[id].heartbeat:
            membership_table[id] <- entry
    -- Quen: khong gui state cua self lai cho remote!

-- DUNG: tra ve state cua self truoc khi merge
function on_push_pull_correct(self, remote_table):
    response <- snapshot(membership_table)   -- ghi lai truoc khi merge
    for each (id, entry) trong remote_table:
        if entry.heartbeat > membership_table[id].heartbeat:
            membership_table[id] <- entry
    return response   -- remote merge tiep

Bỏ qua trả về state của self biến push-pull thành push đơn thuần — mất lợi ích đồng bộ hai chiều.

Pitfall 2 — Gossip state quá lớn (fanout không giới hạn)

-- SAI: gossip toan bo membership table moi round (N entries moi lan)
-- Voi N=10000 node, moi message la 10000 * 64 bytes = 640 KB
-- * k peers * 1 round/giay = gigabytes/giay traffic

-- DUNG: gossip digest (hash hoac heartbeat version), chi gui full entry khi can
function gossip_with_digest(A, B):
    digest <- {nodeId: heartbeat for nodeId trong membership_table}  -- nhe hon
    gửi digest tới B
    B so sanh digest voi membership_table cua B
    B yeu cau chi cac entry co heartbeat moi hon hoac entry thieu

Digest-based gossip: gửi tóm tắt trước, chỉ trao đổi delta thật sự cần thiết.

Pitfall 3 — Threshold failure detection quá thấp gây false positive

-- SAI: DEAD_TIMEOUT = 1 giay (bang interval gossip)
-- Mot round gossip bi delay la node bị đánh dấu dead
-- Tạo "flapping": node liên tục chuyển dead -> alive -> dead

-- DUNG: ngưỡng phát hiện = nhiều lần gossip interval (khong phai 1 round)
-- Cassandra dung phi-accrual (khong phai timeout cung): voi phi_convict_threshold=8
--   mac dinh, node unresponsive bi danh dau DEAD sau ~18 giay
-- Suspect truoc (reversible), Dead sau (irreversible) -- two-stage

Two-stage (suspect → dead) cho node cơ hội phản bác trước khi bị khai tử khỏi cụm.

8. Liên hệ các bài khác

• BFS — tìm kiếm theo chiều rộng: Lan truyền gossip giống BFS theo chiều rộng trên đồ thị mạng — mỗi "vòng gossip" tương tự một layer BFS. Khác biệt: gossip chọn peer ngẫu nhiên thay vì hàng xóm cố định, và chạy liên tục (không dừng khi đến đích).
• Raft — đồng thuận leader & log replication: Gossip đạt eventual consistency (vài giây lag), Raft đạt strong consistency (đa số confirm trước khi commit). Hai kỹ thuật bổ trợ: Gossip phát hiện node chết trong cụm Raft, Raft đảm bảo consensus khi gossip không đủ mạnh.
• Vector clock — thứ tự nhân quả: Gossip thường là cơ chế transport để lan truyền vector clock và version data giữa các node — đặc biệt trong Dynamo/Riak. Gossip cung cấp "ống dẫn", vector clock cung cấp "nhãn nhân quả".
• Consistent hashing: Khi ring consistent hashing thay đổi (node join/leave), gossip là cách Cassandra thông báo thay đổi ring tới toàn cụm mà không cần coordinator tập trung.
• Case study Cassandra & etcd: Thấy gossip hoạt động trong thực tế — Cassandra dùng gossip cho membership + schema propagation, etcd (Raft-based) dùng cơ chế heartbeat khác.

📚 Deep Dive

Tóm tắt

• Gossip mô phỏng lây nhiễm dịch tễ: thông tin lan sau O(log N) vòng, mỗi vòng mỗi node gossip với k peer ngẫu nhiên.
• Ba chế độ: push (gửi), pull (hỏi), push-pull (trao đổi hai chiều — phổ biến nhất).
• Merge dựa trên heartbeat: giữ entry có heartbeat cao hơn, tự động hội tụ.
• Failure detection: SWIM (indirect ping + suspect stage) hoặc phi-accrual (xác suất thay vì threshold cứng).
• Ưu điểm: phi tập trung, chịu lỗi, tự mở rộng. Nhược điểm: eventual consistency, overhead tăng theo N nếu không dùng digest.
• Nền tảng của Cassandra membership, Consul service discovery, CRDT propagation.

Tự kiểm tra

Bài tiếp theo: Raft — đồng thuận leader & log replication