Skip to content

:hedgehog: PostHog is the leading platform for building self-driving products. Our developer tools – AI observability, analytics, session replay, flags, experiments, error tracking, logs, and more – capture all the context agents need to diagnose problems, uncover opportunities, and ship fixes. Steer it all from Slack, web, desktop, or the MCP.

20.3 KB
Raw Blame
//! Pure protocol decision functions, shared between the coordinator and
//! the stateright model (`personhog-stateright`).
//!
//! The coordinator calls these on state it reads from etcd; the model
//! calls them on checker state. One implementation on both sides means
//! the logic the checker verifies is the logic production runs — the
//! phase-advancement rules cannot drift from their verified form.
//!
//! Every function is a pure predicate over partition-scoped inputs: the
//! caller supplies the acks already filtered to one partition (as
//! `list_*_acks(partition)` returns them).

use std::collections::{HashMap, HashSet};
use std::time::Duration;

use assignment_coordination::util::compute_required_handoffs;

use crate::strategy::{AssignmentStrategy, Member};
use crate::types::{
    HandoffPhase, HandoffState, PodDrainedAck, PodWarmedAck, RegisteredPod, RegisteredRouter,
    RouterFreezeAck,
};

pub mod migration;

/// One handoff a rebalance has decided to create. `old_owner` is `None`
/// for a fresh assignment (no prior owner), which skips the drain.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PlannedHandoff {
    pub partition: u32,
    pub old_owner: Option<String>,
    pub new_owner: String,
}

/// A rebalance decision: the full desired placement, and the handoffs
/// required to reach it from the current placement.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RebalancePlan {
    /// partition → owner for every assigned partition (the strategy's
    /// output, verbatim).
    pub desired: HashMap<u32, String>,
    /// Handoffs to create: moves (owner changed) carry the prior owner;
    /// fresh partitions (assigned for the first time) carry none.
    /// Partitions already owned by their target appear in `desired` only.
    pub handoffs: Vec<PlannedHandoff>,
}

/// Plan a rebalance: compute the desired placement via `strategy`, then
/// diff it against the current assignments. Every planned handoff starts
/// at Freezing — including fresh assignments — so routers never route to
/// a pod whose cache hasn't been warmed.
///
/// Callers with handoffs in flight must plan through
/// `plan_partial_rebalance`, which pins those partitions — planning a
/// mid-move partition twice would create overlapping handoffs and
/// conflicting assignment writes. The coordinator and the stateright
/// model both plan through the partial variant; the model's
/// `no_double_planned_handoff` property verifies the pinning across
/// every interleaving of rebalances with in-flight handoffs.
pub fn plan_rebalance<S: AssignmentStrategy + ?Sized>(
    strategy: &S,
    current: &HashMap<u32, String>,
    members: &[Member],
    total_partitions: u32,
) -> RebalancePlan {
    let desired = strategy.compute_assignments(current, members, total_partitions);
    let moves = compute_required_handoffs(current, &desired);
    let moved: HashSet<u32> = moves.iter().map(|(p, _, _)| *p).collect();

    let mut handoffs: Vec<PlannedHandoff> = moves
        .into_iter()
        .map(|(partition, old_owner, new_owner)| PlannedHandoff {
            partition,
            old_owner: Some(old_owner),
            new_owner,
        })
        .collect();
    for (partition, new_owner) in &desired {
        if !current.contains_key(partition) && !moved.contains(partition) {
            handoffs.push(PlannedHandoff {
                partition: *partition,
                old_owner: None,
                new_owner: new_owner.clone(),
            });
        }
    }
    RebalancePlan { desired, handoffs }
}

/// Plan a rebalance around in-flight handoffs. Their partitions are
/// pinned: excluded from the planned handoffs and from `desired` (whose
/// entries the coordinator writes as stable assignments), so the two
/// overlap hazards — a second handoff for a mid-move partition, and an
/// assignment write for one — are impossible by construction, and a
/// stuck handoff defers only its own partition instead of the topology.
/// For the placement computation each pinned partition is attributed to
/// its handoff's new owner, so the balance math agrees with the imminent
/// state and a sticky strategy plans around the in-flight moves instead
/// of fighting them.
pub fn plan_partial_rebalance<S: AssignmentStrategy + ?Sized>(
    strategy: &S,
    current: &HashMap<u32, String>,
    in_flight: &[HandoffState],
    members: &[Member],
    total_partitions: u32,
) -> RebalancePlan {
    let pinned: HashSet<u32> = in_flight.iter().map(|h| h.partition).collect();
    let mut effective = current.clone();
    for handoff in in_flight {
        effective.insert(handoff.partition, handoff.new_owner.clone());
    }
    let mut plan = plan_rebalance(strategy, &effective, members, total_partitions);
    plan.handoffs.retain(|h| !pinned.contains(&h.partition));
    plan.desired
        .retain(|partition, _| !pinned.contains(partition));
    plan
}

/// Whether the freeze quorum for `handoff` is met.
///
/// Identity-based: every router this handoff requires must have acked
/// this partition's freeze. A count comparison would let a stale ack
/// from a departed router (acks are not lease-bound) stand in for a live
/// router that hasn't stashed yet — advancing to Draining while that
/// router still forwards writes to the old owner. Only acks echoing this
/// handoff's id count: an ack left over from a previous handoff of the
/// same partition proves nothing about this one.
///
/// The required set is the handoff's creation-time snapshot intersected
/// with the live registry, so it only ever shrinks; see
/// [`required_freeze_ackers`].
///
/// With no required routers there is no traffic to stash, so the quorum
/// is vacuously met. This keeps bootstrap and router-less configurations
/// (e.g. tests exercising only the coordinator+pod) unblocked.
pub fn freeze_quorum_met(
    routers: &[RegisteredRouter],
    freeze_acks: &[RouterFreezeAck],
    handoff: &HandoffState,
    quorum: Option<&[String]>,
) -> bool {
    let acked: HashSet<&str> = freeze_acks
        .iter()
        .filter(|a| a.handoff_id == handoff.handoff_id)
        .map(|a| a.router_name.as_str())
        .collect();
    required_freeze_ackers(routers, quorum).all(|name| acked.contains(name))
}

/// The routers whose freeze ack a handoff needs: the membership it was
/// created with, intersected with those still registered.
///
/// Intersecting the snapshot with the live set makes the requirement
/// monotonic — it can only shrink. A router that dies drops out (it is no
/// longer routing, so it cannot reach the old owner), and one that joins
/// later is never added (safe to exclude — see
/// [`HandoffState::freeze_quorum_ref`] for why).
///
/// `quorum` is the membership already resolved from the record. `None`
/// means none was recorded — a pre-upgrade record, or a reference that
/// no longer resolves — and falls back to requiring every live router,
/// the rule such records were written under and the stricter of the
/// two. `Some` is authoritative even when empty: zero routers
/// registered at creation means nobody must ack.
pub fn required_freeze_ackers<'a>(
    routers: &'a [RegisteredRouter],
    quorum: Option<&'a [String]>,
) -> impl Iterator<Item = &'a str> + 'a {
    routers
        .iter()
        .map(|r| r.router_name.as_str())
        .filter(move |name| match quorum {
            None => true,
            Some(members) => members.iter().any(|member| member == name),
        })
}

/// Whether `handoff` has sat in its *current phase* longer than that
/// phase's deadline.
///
/// Per-phase rather than total-age on purpose: the deadline exists to
/// catch a handoff that is wedged, and wedged is a property of a phase,
/// not of a lifetime. Freezing and Draining wait only on
/// acknowledgements, so their budget is short. Warming replays a
/// changelog whose length scales with the partition — a total-age
/// deadline would cancel a legitimately long warm and restart it from
/// zero, forever. Warming therefore gets its own, far more generous
/// budget (`warming_deadline`; zero disables it).
///
/// Records written before the phase clock existed carry a zero
/// `phase_entered_at_ms`; they fall back to the creation-time seconds
/// clock. A record with neither stamp cannot be judged on age at all —
/// acting on it would be acting on an age of "since the epoch".
pub fn past_phase_deadline(
    handoff: &HandoffState,
    now_ms: i64,
    handoff_deadline: Duration,
    warming_deadline: Duration,
) -> bool {
    if handoff.phase == HandoffPhase::Complete {
        return false;
    }
    let entered_ms = if handoff.phase_entered_at_ms > 0 {
        handoff.phase_entered_at_ms
    } else if handoff.started_at > 0 {
        handoff.started_at.saturating_mul(1000)
    } else {
        return false;
    };
    let deadline = match handoff.phase {
        HandoffPhase::Warming => warming_deadline,
        _ => handoff_deadline,
    };
    if deadline.is_zero() {
        return false;
    }
    now_ms.saturating_sub(entered_ms) > deadline.as_millis() as i64
}

/// The subset of [`required_freeze_ackers`] whose ack for `handoff` has
/// not arrived. Acks are correlated by handoff id, exactly as in
/// [`freeze_quorum_met`]: a stale ack left over from a predecessor
/// handoff of the same partition must not mask a router that has yet to
/// observe this one.
pub fn missing_freeze_ackers(
    routers: &[RegisteredRouter],
    freeze_acks: &[RouterFreezeAck],
    handoff: &HandoffState,
    quorum: Option<&[String]>,
) -> Vec<String> {
    let acked: HashSet<&str> = freeze_acks
        .iter()
        .filter(|a| a.handoff_id == handoff.handoff_id)
        .map(|a| a.router_name.as_str())
        .collect();
    required_freeze_ackers(routers, quorum)
        .filter(|name| !acked.contains(name))
        .map(str::to_string)
        .collect()
}

/// Whether the drain requirement for `handoff` is satisfied.
///
/// "Alive" here means the old owner's etcd registration key still exists
/// (its lease hasn't expired) — not just that it's `Ready`. A `Draining`
/// pod is shutting down gracefully but is still capable of running its
/// handoff handler and writing a `DrainedAck`, and may still have
/// inflight handlers. Bypassing the drain requirement for such a pod
/// would let the coordinator advance to Warming while the old owner is
/// still producing — breaking the protocol's core invariant. Only treat
/// the old owner as drained when its key is genuinely absent, or when it
/// has acked this handoff attempt.
pub fn drain_satisfied(
    registered_pods: &[RegisteredPod],
    drained_acks: &[PodDrainedAck],
    handoff: &HandoffState,
) -> bool {
    match &handoff.old_owner {
        // Defensive: a handoff that reached Draining without an old owner
        // shouldn't exist (Freezing skips Draining when old_owner is
        // None), but if it does, there's nothing to drain.
        None => true,
        Some(name) => {
            let old_owner_present = registered_pods.iter().any(|p| p.pod_name == *name);
            !old_owner_present
                || drained_acks
                    .iter()
                    .any(|a| a.pod_name == *name && a.handoff_id == handoff.handoff_id)
        }
    }
}

/// Whether the new owner has warmed for this handoff attempt.
pub fn warm_satisfied(warmed_acks: &[PodWarmedAck], handoff: &HandoffState) -> bool {
    warmed_acks
        .iter()
        .any(|a| a.pod_name == handoff.new_owner && a.handoff_id == handoff.handoff_id)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::strategy::StickyBalancedStrategy;

    fn handoff(partition: u32, old_owner: Option<&str>, new_owner: &str) -> HandoffState {
        HandoffState {
            partition,
            old_owner: old_owner.map(str::to_string),
            new_owner: new_owner.to_string(),
            phase: HandoffPhase::Warming,
            started_at: 0,
            handoff_id: String::new(),
            freeze_quorum: None,
            freeze_quorum_ref: None,
            created_at_ms: 0,
            phase_entered_at_ms: 0,
            held_by: None,
            config_epoch: 0,
            new_owner_address: None,
        }
    }

    fn router(name: &str) -> RegisteredRouter {
        RegisteredRouter {
            router_name: name.to_string(),
            registered_at: 0,
            last_heartbeat: 0,
        }
    }

    fn freeze_ack(router: &str, handoff: &HandoffState) -> RouterFreezeAck {
        RouterFreezeAck {
            router_name: router.to_string(),
            partition: handoff.partition,
            acked_at: 0,
            acked_at_ms: 0,
            handoff_id: handoff.handoff_id.clone(),
        }
    }

    /// The wedge this snapshot exists to prevent: a router that
    /// registers after the handoff was created never receives its
    /// `Freezing` event, so requiring its ack leaves a quorum that
    /// nothing can satisfy and no cleanup path removes.
    #[test]
    fn a_router_that_joined_after_creation_is_not_required() {
        let h = handoff(0, Some("pod-a"), "pod-b");
        let quorum = ["router-0".to_string()];
        let acks = [freeze_ack("router-0", &h)];

        assert!(
            freeze_quorum_met(
                &[router("router-0"), router("late-joiner")],
                &acks,
                &h,
                Some(&quorum)
            ),
            "a router registered after creation must not block the quorum"
        );
    }

    /// The deadline is a per-phase clock: a warm that outlives the
    /// general deadline must survive on Warming's own budget, while a
    /// wedged freeze of the same age cancels. A total-age deadline would
    /// livelock any partition whose changelog replay exceeds it — cancel,
    /// replan, warm from zero, cancel again.
    #[test]
    fn deadline_is_per_phase_and_patient_with_warming() {
        let short = Duration::from_secs(120);
        let long = Duration::from_secs(1800);
        let mut h = handoff(0, Some("pod-a"), "pod-b");
        h.phase = HandoffPhase::Warming;
        h.phase_entered_at_ms = 1_000;
        let now = 1_000 + 600_000;

        assert!(
            !past_phase_deadline(&h, now, short, long),
            "ten minutes into a warm is within Warming's budget"
        );
        h.phase = HandoffPhase::Freezing;
        assert!(
            past_phase_deadline(&h, now, short, long),
            "the same age in Freezing is a wedge"
        );

        // The phase clock restarts on advancement: a warm that follows a
        // slow freeze starts a fresh budget.
        h.phase = HandoffPhase::Warming;
        h.phase_entered_at_ms = now - 1_000;
        assert!(!past_phase_deadline(&h, now, short, long));

        // Zero disables a budget outright.
        h.phase_entered_at_ms = 1_000;
        assert!(!past_phase_deadline(&h, now, short, Duration::ZERO));
    }

    /// Pre-upgrade records fall back to the creation-time seconds clock;
    /// a record with no stamp at all is never judged on age.
    #[test]
    fn deadline_falls_back_to_started_at_and_skips_unstamped_records() {
        let short = Duration::from_secs(120);
        let long = Duration::from_secs(1800);
        let mut h = handoff(0, Some("pod-a"), "pod-b");
        h.phase = HandoffPhase::Freezing;

        h.started_at = 1;
        assert!(past_phase_deadline(&h, 601_000, short, long));

        h.started_at = 0;
        assert!(!past_phase_deadline(&h, i64::MAX, short, long));
    }

    /// Attribution mirror of the quorum predicate: the missing set names
    /// exactly the required routers whose ack for *this* handoff hasn't
    /// arrived — a stale ack from a predecessor handoff must not hide
    /// one.
    #[test]
    fn missing_ackers_names_the_holdout_and_ignores_stale_acks() {
        let h = handoff(0, Some("pod-a"), "pod-b");
        let quorum = ["router-0".to_string(), "router-1".to_string()];
        let mut stale = freeze_ack("router-1", &h);
        stale.handoff_id = "a-previous-handoff".to_string();
        let acks = [freeze_ack("router-0", &h), stale];

        assert_eq!(
            missing_freeze_ackers(
                &[router("router-0"), router("router-1")],
                &acks,
                &h,
                Some(&quorum)
            ),
            vec!["router-1".to_string()],
            "router-1's stale ack proves nothing about this handoff"
        );
    }

    /// The other direction is what keeps it safe: a router that was
    /// present at creation may hold a routing table pointing at the old
    /// owner, so its ack stays mandatory.
    #[test]
    fn a_router_present_at_creation_is_still_required() {
        let h = handoff(0, Some("pod-a"), "pod-b");
        let quorum = ["router-0".to_string(), "router-1".to_string()];
        let acks = [freeze_ack("router-0", &h)];

        assert!(
            !freeze_quorum_met(
                &[router("router-0"), router("router-1")],
                &acks,
                &h,
                Some(&quorum)
            ),
            "a snapshot member that has not acked must block the quorum"
        );
        // ...until it departs: a router that is gone cannot route.
        assert!(
            freeze_quorum_met(&[router("router-0")], &acks, &h, Some(&quorum)),
            "a departed snapshot member must drop out of the requirement"
        );
    }

    /// Records written before the snapshot existed must keep their old
    /// meaning: with no captured requirement, every live router is
    /// required, since any of them might hold a table pointing at the
    /// old owner.
    #[test]
    fn an_absent_snapshot_requires_every_live_router() {
        let h = handoff(0, Some("pod-a"), "pod-b");
        let acks = [freeze_ack("router-0", &h)];

        assert!(
            !freeze_quorum_met(&[router("router-0"), router("router-1")], &acks, &h, None),
            "without a membership every live router must still be required"
        );
        assert!(freeze_quorum_met(&[router("router-0")], &acks, &h, None));
    }

    /// A captured-but-empty snapshot is not the legacy fallback: zero
    /// routers were registered at creation, so nobody must ack — even
    /// routers that register afterward. Falling back to the live-set
    /// rule here would let the requirement grow from zero and reopen
    /// the wedge for exactly this corner.
    #[test]
    fn an_empty_snapshot_requires_nobody() {
        let h = handoff(0, Some("pod-a"), "pod-b");
        let quorum: [String; 0] = [];

        assert!(
            freeze_quorum_met(&[router("late-joiner")], &[], &h, Some(&quorum)),
            "a router that registered after a zero-router creation must not be required"
        );
    }

    #[test]
    fn pinned_partitions_are_never_planned() {
        let current: HashMap<u32, String> = (0..4).map(|p| (p, "pod-a".to_string())).collect();
        let in_flight = [handoff(0, Some("pod-a"), "pod-b")];
        let active = Member::active_all(&["pod-a", "pod-b", "pod-c"]);

        let plan =
            plan_partial_rebalance(&StickyBalancedStrategy, &current, &in_flight, &active, 4);

        assert!(
            plan.handoffs.iter().all(|h| h.partition != 0),
            "a pinned partition must never get a second handoff"
        );
        assert!(
            !plan.desired.contains_key(&0),
            "a pinned partition must never get an assignment write"
        );
        // A stuck handoff defers only itself: the new pod still receives
        // partitions from the unpinned remainder.
        assert!(
            plan.handoffs.iter().any(|h| h.new_owner == "pod-c"),
            "unpinned partitions must still rebalance toward the new pod"
        );
    }

    #[test]
    fn pinned_partitions_count_against_their_target() {
        // Two of pod-a's four partitions are mid-move to pod-b. Attributed
        // to their target, the placement is already balanced — a plan that
        // read the raw current map would see 4-vs-0 and churn the other
        // two partitions to pod-b right behind the in-flight moves.
        let current: HashMap<u32, String> = (0..4).map(|p| (p, "pod-a".to_string())).collect();
        let in_flight = [
            handoff(0, Some("pod-a"), "pod-b"),
            handoff(1, Some("pod-a"), "pod-b"),
        ];
        let active = Member::active_all(&["pod-a", "pod-b"]);

        let plan =
            plan_partial_rebalance(&StickyBalancedStrategy, &current, &in_flight, &active, 4);

        assert!(
            plan.handoffs.is_empty(),
            "in-flight moves already balance the placement; planning more is churn: {:?}",
            plan.handoffs
        );
    }
}