Phi accrual failure detector

Deep dive

How it works

In: heartbeat arrival times, query time now · Out: suspicion level φ per peer · State: ring buffer of inter-arrival times plus running sums · Cost: O(1) per heartbeat and per query

1. On each heartbeat at time t, record t − t_last in a ring buffer; maintain running sum and sum of squares.
2. On query at now: Δ = now − t_last. Normal model (paper, Akka): μ = mean (+ acceptable pause), σ = max(std. dev., min σ); φ = −log10(1 − F(Δ)), F the normal CDF.
3. Akka uses a logistic approximation of the CDF: with y = (Δ − μ)/σ, e = exp(−y(1.5976 + 0.070566 y²)); φ = −log10(e/(1+e)) if Δ > μ else −log10(1 − 1/(1+e)).
4. Exponential model (Cassandra): P(later) = e^(−Δ/μ), so φ = Δ / (μ ln 10) ≈ 0.434 Δ/μ.
5. Suspect when φ > threshold.

φ │                    ╱  normal: φ rises steeply once Δ exceeds μ + a few σ
8 ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╱─ ─ ─ threshold
  │                  ╱
  │________________╱
  └────────────────┴──────► Δ since last heartbeat
                 μ+pause

Code

use std::collections::VecDeque;

pub struct PhiAccrual {
    window: VecDeque<f64>,      // inter-arrival times, ms
    max_samples: usize,
    sum: f64,
    sum_sq: f64,
    last_ms: Option<f64>,
    min_std_ms: f64,
    acceptable_pause_ms: f64,
}

impl PhiAccrual {
    /// Akka-like defaults: new(1000, 100.0, 3000.0, 1000.0)
    pub fn new(max_samples: usize, min_std_ms: f64, acceptable_pause_ms: f64, first_estimate_ms: f64) -> Self {
        let mut d = PhiAccrual { window: VecDeque::with_capacity(max_samples), max_samples,
                                 sum: 0.0, sum_sq: 0.0, last_ms: None, min_std_ms, acceptable_pause_ms };
        // Seed with mean = estimate, std = estimate/4 (two samples), as Akka does.
        let std = first_estimate_ms / 4.0;
        d.push(first_estimate_ms - std);
        d.push(first_estimate_ms + std);
        d
    }

    fn push(&mut self, x: f64) {
        if self.window.len() == self.max_samples {
            let old = self.window.pop_front().unwrap();
            self.sum -= old;
            self.sum_sq -= old * old;
        }
        self.window.push_back(x);
        self.sum += x;
        self.sum_sq += x * x;
    }

    pub fn heartbeat(&mut self, now_ms: f64) {
        if let Some(last) = self.last_ms { self.push(now_ms - last); }
        self.last_ms = Some(now_ms);
    }

    fn mean_std(&self) -> (f64, f64) {
        let n = self.window.len() as f64;
        let mean = self.sum / n;
        let var = (self.sum_sq / n - mean * mean).max(0.0); // clamp float cancellation
        (mean, var.sqrt().max(self.min_std_ms))
    }

    /// Normal model with Akka's logistic CDF approximation.
    pub fn phi(&self, now_ms: f64) -> f64 {
        let Some(last) = self.last_ms else { return 0.0 };
        let (mean, std) = self.mean_std();
        let mean = mean + self.acceptable_pause_ms;
        let dt = now_ms - last;
        let y = (dt - mean) / std;
        let e = (-y * (1.5976 + 0.070566 * y * y)).exp();
        if dt > mean { -(e / (1.0 + e)).log10() } else { -(1.0 - 1.0 / (1.0 + e)).log10() }
    }

    /// Exponential model (Cassandra): phi = dt / (mean * ln 10).
    pub fn phi_exponential(&self, now_ms: f64) -> f64 {
        let Some(last) = self.last_ms else { return 0.0 };
        let (mean, _) = self.mean_std();
        (now_ms - last) / (mean * std::f64::consts::LN_10)
    }

    pub fn is_available(&self, now_ms: f64, threshold: f64) -> bool { self.phi(now_ms) < threshold }
}

fn main() {
    let mut d = PhiAccrual::new(1000, 100.0, 3000.0, 1000.0);
    for i in 0..100 { d.heartbeat(i as f64 * 1000.0); }
    for dt in [1000.0, 3000.0, 4000.0, 4500.0, 5000.0] {
        println!("dt={dt:>6} ms  phi={:.2}", d.phi(99_000.0 + dt));
    }
}

Complexity and constants

• O(1) per heartbeat and per query with running sums; 8 bytes × window (8 KB at 1,000 samples).
• phi costs one exp and one log10: order of 20-50 ns.
• Akka defaults on a steady 1 s heartbeat: φ crosses 8 at Δ ≈ μ + pause + 5.2σ ≈ 1 + 3 + 0.52 ≈ 4.5 s.
• Exponential model with μ = 1 s: φ = 8 at Δ ≈ 18.4 s; the exponential is much more conservative.
• All-pairs heartbeating costs n(n−1) messages per interval: fine for tens of nodes, not thousands.

Efficiency

• Cost: O(1) per heartbeat and per query with running sums. Memory 8 bytes per sample (8 KB at 1,000 samples) per monitored peer. A query costs one exp and one log10, order of 20-50 ns. All-pairs heartbeating costs n(n−1) messages per interval. Bound: network and timers, not compute.
• Levers:
  • running sum and sum of squares — O(1) update instead of O(window) rescans (Complexity above) — any window size
  • bounded window (e.g. 1,000 samples) — fixed memory and fast adaptation — long-lived links
  • dedicated high-priority heartbeat path — measures liveness, not queueing (Implementation notes) — mixed bulk and control traffic
  • gossip or probe overlay instead of all-pairs heartbeats — per-node load stays constant — beyond tens of nodes (SWIM)
  • min_std and acceptable_pause — fewer false suspicions without retraining — regular links, GC or VM pauses
• Naive → standard → state of the art:
  • fixed timeout · O(1), wrong on jittery or clean links alike
  • φ accrual with a running-sum window · O(1) per heartbeat, order of 20-50 ns per query
  • φ accrual on a gossip overlay (Cassandra, chitchat) · constant per-node load, adaptive threshold per link

Implementation notes

• Use a monotonic clock (Instant) for arrival times; a wall-clock step fakes a huge interval.
• Running sums drift with floating-point error over millions of updates; recompute from the window occasionally, or use Welford's update with removal.
• Set min_std (e.g. 100 ms): a perfectly regular link has σ ≈ 0 and would otherwise make φ explode on the first late packet.
• acceptable_pause absorbs known pauses (GC, VM migration) without retraining the window.
• Send heartbeats on a dedicated, high-priority path; heartbeats queued behind bulk traffic measure the queue, not liveness.
• Bootstrap the window: before any samples exist, seed it with the expected interval (Akka uses the configured heartbeat interval with σ = interval/4) so the first missed beats still produce a sensible φ.
• On noisy cloud networks Cassandra's documentation suggests raising phi_convict_threshold from 8 toward 10-12; each +1 roughly multiplies the time to conviction on an exponential model by (φ+1)/φ, not by 10.

Pitfalls

• Treating φ as a true probability: real inter-arrival tails (GC, retransmits) are heavy; threshold 8 does not mean one false positive per 10⁸ checks.
• Sample-window poisoning: after a long outage the window contains huge intervals and detection becomes slow; cap recorded intervals.
• Detector says "dead" while the node still acts (partition, pause): never use it alone to hand over exclusive ownership.
• Same threshold for every consumer: a load balancer should react far sooner than cluster eviction.

Variants and alternatives

In production

Actor clusters: Akka / Apache Pekko cluster (default detector). Databases: Apache Cassandra gossip failure detector (phi_convict_threshold). Data grids: Hazelcast (optional phi-accrual detector). Search and log analytics: Quickwit's chitchat (phi-accrual detection on scuttlebutt gossip, per its README).

Implementations

Sources

• Naohiro Hayashibara, Xavier Défago, Rami Yared, Takuya Katayama, The φ Accrual Failure Detector, SRDS 2004. paper
• Wei Chen, Sam Toueg, Marcos K. Aguilera, On the Quality of Service of Failure Detectors, IEEE Transactions on Computers, 2002. paper