SWIM gossip membership

Deep dive

How it works

Parts:

• member list — every known node with state (Alive, Suspect, Dead) and incarnation number
• probe schedule — shuffled round-robin list of targets, one per period
• failure detector — ping, then ping-req through k peers on timeout
• suspicion timer — per suspect; expiry confirms Dead
• update buffer — recent changes, each piggybacked about λ·log n times

Operations: probe, indirect probe, suspect, refute, disseminate (steps below).

Each protocol period T (e.g. 1 s), node M:

1. Picks the next target from a shuffled list of members (reshuffle after each pass, round-robin).
2. Sends ping; waits a timeout (< T, e.g. T/2) for ack.
3. On timeout, sends ping-req(target) to k random members; they ping the target and forward any ack.
4. No ack by period end → mark target Suspect and gossip Suspect(target, inc).
5. A suspect that doesn't refute within the suspicion timeout becomes Dead (Confirm), gossiped and removed.
6. A node that hears it is suspected increments its own incarnation and gossips Alive(self, inc+1).

Update precedence for member X:

• Alive(i) overrides Suspect(j) and Alive(j) if i > j.
• Suspect(i) overrides Suspect(j) if i > j, and Alive(j) if i ≥ j.
• Dead overrides everything; only Alive with a higher incarnation (a restarted node) brings it back.

Dissemination: every message carries a few recent updates; each update is piggybacked λ·log n times, then dropped.

states: Alive ─no ack─► Suspect ─suspicion timeout─► Dead
          ▲                 │ Alive(inc+1) refutes
          └─────────────────┘

M ──ping──► T   (timeout)
M ──ping-req(T)──► A, B, C ──ping──► T ──ack──► A ──ack──► M     any ack = alive

Code

use std::collections::HashMap;

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum State { Alive, Suspect, Dead }

#[derive(Clone, Copy, Debug)]
pub struct Update { pub node: u32, pub state: State, pub inc: u64 }

pub struct Member { pub state: State, pub inc: u64, pub suspect_since_ms: Option<u64> }

pub struct Swim {
    pub me: u32,
    pub my_inc: u64,
    pub members: HashMap<u32, Member>,
    gossip: Vec<(Update, u32)>, // (update, times piggybacked so far)
    order: Vec<u32>, cursor: usize, rng: u64,
}

fn overrides(new: &Update, cur: &Member) -> bool {
    use State::*;
    match (new.state, cur.state) {
        (Alive, Dead) => new.inc > cur.inc, // rejoin after restart with a higher incarnation
        (_, Dead) => false,
        (Dead, _) => true,
        (Alive, _) => new.inc > cur.inc,
        (Suspect, Suspect) => new.inc > cur.inc,
        (Suspect, Alive) => new.inc >= cur.inc,
    }
}

impl Swim {
    pub fn new(me: u32, seed: u64) -> Self {
        Swim { me, my_inc: 0, members: HashMap::new(), gossip: Vec::new(),
               order: Vec::new(), cursor: 0, rng: seed | 1 }
    }

    /// Apply a received (or locally generated) update; returns true if it was news.
    pub fn apply(&mut self, u: Update, now_ms: u64) -> bool {
        if u.node == self.me {
            if u.state != State::Alive && u.inc >= self.my_inc {
                self.my_inc = u.inc + 1;  // refute: only I may raise my incarnation
                self.enqueue(Update { node: self.me, state: State::Alive, inc: self.my_inc });
            }
            return false;
        }
        let known = self.members.contains_key(&u.node);
        let m = self.members.entry(u.node)
            .or_insert(Member { state: u.state, inc: u.inc, suspect_since_ms: None });
        if known && !overrides(&u, m) { return false; }
        m.state = u.state;
        m.inc = u.inc;
        m.suspect_since_ms = (u.state == State::Suspect).then_some(now_ms);
        self.enqueue(u);
        true
    }

    fn enqueue(&mut self, u: Update) {
        self.gossip.retain(|(g, _)| g.node != u.node); // newest update per node wins
        self.gossip.push((u, 0));
    }

    /// Up to `max` updates to piggyback; each is sent at most mult * ceil(log10(n+1)) times.
    pub fn piggyback(&mut self, max: usize, mult: u32) -> Vec<Update> {
        let n = self.members.len() as f64 + 1.0;                 // including me
        let limit = mult * (n + 1.0).log10().ceil().max(1.0) as u32; // memberlist's formula
        self.gossip.sort_by_key(|&(_, sent)| sent);              // least-sent first
        let out: Vec<Update> = self.gossip.iter_mut().take(max)
            .map(|(u, sent)| { *sent += 1; *u }).collect();
        self.gossip.retain(|&(_, sent)| sent < limit);
        out
    }

    /// Round-robin over a shuffled member list: bounded worst-case detection time.
    pub fn next_target(&mut self) -> Option<u32> {
        if self.cursor >= self.order.len() {
            self.order = self.members.iter()
                .filter(|(_, m)| m.state != State::Dead).map(|(&id, _)| id).collect();
            for i in (1..self.order.len()).rev() {                 // Fisher-Yates
                self.rng ^= self.rng << 13; self.rng ^= self.rng >> 7; self.rng ^= self.rng << 17;
                self.order.swap(i, (self.rng % (i as u64 + 1)) as usize);
            }
            self.cursor = 0;
        }
        let t = self.order.get(self.cursor).copied();
        self.cursor += 1;
        t
    }

    /// Promote suspects whose timeout expired to Dead.
    pub fn expire(&mut self, now_ms: u64, suspicion_ms: u64) {
        let expired: Vec<Update> = self.members.iter()
            .filter(|(_, m)| m.suspect_since_ms.map_or(false, |t| now_ms >= t + suspicion_ms))
            .map(|(&node, m)| Update { node, state: State::Dead, inc: m.inc }).collect();
        for u in expired { self.apply(u, now_ms); }
    }
}

The ping / ping-req / ack exchange is a small timer-driven loop around next_target, calling apply(Suspect) when no ack arrives by the end of the period.

Complexity and constants

• Messages per node per period: 1 ping + 1 ack, plus k ping-req (and their pings/acks) only on timeouts. With 1 s periods, a 1,000-node cluster sends order of 2,000 small UDP packets/s in total.
• Dissemination: an update reaches everyone in O(log n) periods; with 3-4 piggybacks × log n it is very unlikely any node misses it.
• Detection latency ≈ time to be probed (≈ 1.6 periods expected) + suspicion timeout (memberlist: 4 × log10(n) × 1 s, so 12 s at n = 1,000).
• Packet size: keep piggyback payload under the UDP MTU (memberlist caps a UDP packet at 1,400 bytes), so a handful of updates per message.

Efficiency

• Cost: per node per period, 1 ping plus 1 ack, plus k ping-req rounds only on timeouts: order of 2,000 small UDP packets/s in total for 1,000 nodes at 1 s periods. An update reaches everyone in O(log n) periods. Detection takes about 1.6 periods to be probed plus the suspicion timeout (memberlist: 4 × log10(n) × 1 s, 12 s at n = 1,000). A UDP packet is capped at 1,400 bytes in memberlist. Bound: network, constant per node.
• Levers:
  • indirect probes through k peers — one bad link no longer condemns a healthy node (SWIM paper) — lossy networks
  • suspicion timeout scaled by log n and shrunk by independent suspicions — fewer false positives without slower detection (Lifeguard) — large clusters
  • Lifeguard local health — a slow node widens its own timeouts instead of accusing others (arXiv 1707.00788) — CPU-starved or GC-prone hosts
  • piggyback updates on pings and acks — no extra dissemination messages — always
  • periodic TCP push-pull sync (memberlist: every 30 s) — repairs missed gossip — lossy UDP paths
• Naive → standard → state of the art:
  • all-to-all heartbeats · O(n²) messages per period
  • SWIM probing with piggybacked updates · O(1) messages per node, O(log n) dissemination
  • SWIM plus Lifeguard and push-pull sync (memberlist) · same load, far fewer false positives (Lifeguard paper)

Implementation notes

• Make the suspicion timeout grow with log n (more nodes → more chances of a single bad observer) and shrink it as independent suspicions arrive (Lifeguard).
• Lifeguard local health: a node that is itself slow (CPU starved, GC) widens its own timeouts instead of accusing others; it greatly cut false positives in Consul.
• Use TCP fallback for indirect probes and periodic full-state push-pull sync (memberlist: every 30 s) to repair missed gossip.
• Encrypt and authenticate gossip (memberlist supports AES-GCM keyring); otherwise anyone on the network can declare nodes dead.
• Separate identity from address; a restarted node rejoins with a higher incarnation.

Pitfalls

• Removing a dead node's tombstone too early: stale Alive gossip resurrects it. Keep Dead entries for a while.
• Overloaded nodes marking healthy peers suspect (the motivation for Lifeguard).
• Asymmetric partitions: A can't reach B but C can; indirect probes cover this, direct-only heartbeats don't.
• Treating SWIM membership as consistent: two nodes can briefly disagree about who's alive; never use it alone for exclusive ownership.

Variants and alternatives

In production

Service discovery and orchestration: HashiCorp memberlist (Consul, Nomad, Serf). Observability storage: Grafana Mimir/Loki hash rings (memberlist KV via dskit). Application sharding: Uber Ringpop. Apache Cassandra uses its own gossip with a phi accrual detector instead.

Implementations

Sources

• Abhinandan Das, Indranil Gupta, Ashish Motivala, SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol, DSN 2002. paper
• Armon Dadgar, James Phillips, Jon Currey, Lifeguard: Local Health Awareness for More Accurate Failure Detection, arXiv 1707.00788, 2017. paper