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.

22.5 KB
Raw Blame
//! State types for the personhog handoff-protocol model.
//!
//! Every field maps to a production counterpart (see the README mapping
//! table). The whole distributed system — etcd, coordinator, routers,
//! leader pods, and the Kafka changelog — is one plain-data `SystemState`
//! so the checker can hash, compare, and exhaustively explore it.

use std::collections::{BTreeMap, BTreeSet};

pub type PodId = u8;
pub type RouterId = u8;
pub type Partition = u8;
/// Identity of one handoff attempt — production `HandoffState.handoff_id`.
/// Acks echo it and quorum checks only count matching acks.
pub type HandoffId = u8;
/// A changelog generation's epoch (production `ChangelogConfig::epoch`).
pub type Epoch = u8;
/// A person key. The model's hash is the identity: like production's
/// hash-then-mod, a key's homes under two counts agree modulo their gcd.
pub type Key = u8;

/// The production phase enum, used directly: a new phase added to the
/// protocol breaks the model's exhaustive matches at compile time.
pub use personhog_coordination::types::HandoffPhase as Phase;
/// The production saga phases, used directly for the same reason.
pub use personhog_coordination::types::MigrationPhase;

/// Production `HandoffState`, in compact model form (u8 ids; the model
/// materializes production-typed views when calling shared logic).
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Handoff {
    pub id: HandoffId,
    pub old_owner: Option<PodId>,
    pub new_owner: PodId,
    pub phase: Phase,
    /// The freeze-quorum snapshot: routers registered when the rebalance
    /// created this handoff (production `HandoffState::freeze_quorum`,
    /// always captured — the model never writes legacy records, so the
    /// production `None` fallback is pinned by unit tests instead).
    /// With `RouterJoin` in the action space this diverges from the live
    /// registry, which is exactly what the checker is here to explore.
    pub quorum: BTreeSet<RouterId>,
    /// A migration's hold (production `held_by`): never advanced past Draining.
    pub held: bool,
    /// Production `config_epoch`: an acquisition parks until the config reaches it.
    pub config_epoch: Epoch,
}

/// One changelog generation (production: the live target, or a `draining` entry).
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Generation {
    pub partitions: u8,
    pub epoch: Epoch,
}

/// Production `ChangelogConfig`: the live generation and at most one draining.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Config {
    pub live: Generation,
    pub draining: Option<Generation>,
}

/// Production `MigrationState`.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Migration {
    pub from: Generation,
    pub to: u8,
    pub phase: MigrationPhase,
}

/// Per-partition warm state on a pod — everything the invariants need to
/// know about one warmed partition.
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct WarmState {
    /// What this warm was installed for (production:
    /// `WarmProvenance` on the pod handle). `None` is a serving-era warm
    /// (restart, or the returning old owner of an in-flight handoff);
    /// `Some(id)` was installed for that handoff's Warming. An Acquiring
    /// convergence honors a warm only when it carries the current
    /// handoff's id — anything else is a leftover from an earlier era
    /// whose cache may predate writes accepted since, and is released
    /// and rebuilt.
    pub for_handoff: Option<HandoffId>,
    /// The epoch captured at acquisition (production `Capture`).
    pub epoch: Epoch,
    /// Visible prefix per source log (production: marks keyed by stream);
    /// the live source advances with each accepted write.
    pub sources: BTreeMap<(Epoch, Partition), u8>,
}

/// A warm caught between its two steps, under the rejected read-first
/// ordering: the changelog read is taken while the fence — and with it
/// the rejection of a stale owner's write — does not exist yet, so a
/// write can be acked into the gap and sit above the cutoff forever.
///
/// Fence-first needs no such state. Its epoch bump precedes the read and
/// an append requires an installed warm carrying the current epoch, so
/// nothing can append between the two steps and the model installs the
/// warm atomically.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct PendingWarm {
    /// The live log's length captured before the fence existed.
    pub cutoff: u8,
}

/// One leader pod. `registered` is the etcd lease-bound registration key;
/// everything else is process memory and dies with the process.
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Pod {
    /// The etcd registration key exists (production: lease alive).
    pub registered: bool,
    /// The process is running and its data plane serves requests.
    pub running: bool,
    /// Partitions warmed by this process incarnation (production:
    /// `warmed_partitions` on the pod handle).
    pub warmed: BTreeMap<Partition, WarmState>,
    /// Warms mid-flight under `EpochFenced` — one step of
    /// `warm_partition` done, the other not (empty under `Current`,
    /// whose warm has no broker step to separate from the read).
    pub pending_warm: BTreeMap<Partition, PendingWarm>,
    /// Write-fenced partitions (production: `InflightTracker` fences +
    /// the pod handle's `fenced_partitions`).
    pub fenced: BTreeSet<Partition>,
    /// Old-topic partitions this incarnation sealed (the seal duty's memory).
    pub sealed: BTreeSet<Partition>,
    /// This incarnation's seal never succeeds.
    pub seal_broken: bool,
    /// Remaining writes this pod may accept after losing its lease before
    /// its keepalive notices and the process self-fences (production: the
    /// bounded zombie window; fix 1 bounds it to ~one heartbeat tick).
    pub zombie_writes_left: u8,
    /// Whether this pod still claims the right to serve (production: the
    /// `AuthorityClock` the keepalive stamps and the data plane reads).
    ///
    /// Deliberately not the same fact as `registered`. A lease can be
    /// revoked out from under a pod, leaving it claiming a partition it
    /// no longer holds until something tells it otherwise — which is the
    /// window the read gate is trying to close, and cannot be expressed
    /// if the two are one flag.
    pub claims_authority: bool,
}

/// One router. A clean router restart is indistinguishable from a
/// delayed `Observe` (production `load_initial` rebuilds everything from
/// etcd before serving), so restarts need no modeling — but lease expiry
/// does: an unregistered router is excluded from the freeze quorum while
/// its process may keep routing with a stale table until its keepalive
/// self-fences it (the zombie-router half of the double-zombie residual).
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Router {
    /// The etcd registration key exists (production: lease alive). Only
    /// registered routers count toward the freeze quorum.
    pub registered: bool,
    /// The process is running and forwards traffic.
    pub running: bool,
    /// The config this router hashes with (production `LiveChangelog`).
    pub adopted: Generation,
    /// partition → pod the router forwards to (production: the shared
    /// routing table, edge-updated from handoff Complete events).
    pub table: BTreeMap<Partition, PodId>,
    /// Partitions currently buffering leader-path requests (production:
    /// the `StashTable`'s open freezes).
    pub stashing: BTreeSet<Partition>,
    /// Parked leader-path requests in arrival order (production: the `StashTable`'s
    /// per-key queues). A drain for `p` takes those whose key maps to `p` under the router's count.
    pub stash: Vec<StashedRequest>,
}

/// One parked leader-path request.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum StashedRequest {
    Write(Key),
    StrongRead(Key),
}

impl StashedRequest {
    pub fn key(self) -> Key {
        match self {
            StashedRequest::Write(key) | StashedRequest::StrongRead(key) => key,
        }
    }
}

/// The Kafka changelog for one partition of one generation: the appended
/// keys (their count is the HWM) and the broker's producer fence.
#[derive(Clone, Debug, Default, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Changelog {
    pub records: Vec<Key>,
    /// The pod whose transactional producer the broker currently accepts:
    /// the latest `init_transactions` wins and every earlier producer is
    /// fenced out. A seal initializes the id and drops the producer.
    ///
    /// This is an owner rather than an epoch number because nothing
    /// compares epochs for order — the single consumer asks whether *this*
    /// pod's producer is the live one. A counter would have split states
    /// that differ only in how many fences had been acquired along the way,
    /// and, being a `u8`, would eventually have wrapped a stale epoch onto
    /// a live one and admitted a write it should reject.
    pub epoch_holder: Option<PodId>,
}

impl Changelog {
    pub fn len(&self) -> u8 {
        self.records.len() as u8
    }

    pub fn is_empty(&self) -> bool {
        self.records.is_empty()
    }
}

/// One planned-but-unapplied handoff from a chunked plan: the placement
/// decision plus its plan-time guards (production: a later `apply_plan`
/// chunk, applied without re-reading).
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct PendingUnit {
    pub partition: Partition,
    pub old_owner: Option<PodId>,
    pub new_owner: PodId,
    /// Freeze requirement snapshotted at plan time.
    pub quorum: BTreeSet<RouterId>,
    /// Assignment version at plan time (production: the mod_revision
    /// its `AssignmentPrecondition` compares; 0 = Absent).
    pub expected_assignment_version: u8,
    /// The plan's basis (production `PlanBasis`): a saga in flight, and the live epoch.
    pub basis: (bool, Epoch),
}

/// The entire distributed system. One value = one node in the explored
/// state graph.
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct SystemState {
    // ── durable (etcd) ─────────────────────────────────────────
    /// partition → owning pod (production: `PartitionAssignment`; flips
    /// only atomically with a handoff reaching Complete).
    pub assignments: BTreeMap<Partition, PodId>,
    /// In-flight handoffs, at most one per partition.
    pub handoffs: BTreeMap<Partition, Handoff>,
    /// (partition, router) → handoff id acked (production:
    /// `RouterFreezeAck` with `handoff_id`).
    pub freeze_acks: BTreeMap<(Partition, RouterId), HandoffId>,
    /// (partition, pod) → handoff id acked (production: `PodDrainedAck`).
    pub drained_acks: BTreeMap<(Partition, PodId), HandoffId>,
    /// (partition, pod) → handoff id acked (production: `PodWarmedAck`).
    pub warmed_acks: BTreeMap<(Partition, PodId), HandoffId>,
    /// Monotonic handoff id allocator (production: `new_handoff_id`).
    pub next_handoff_id: HandoffId,
    /// Unapplied suffix of a chunked plan, front unit next
    /// (production: `apply_plan`'s later chunks).
    pub pending_plan: Vec<PendingUnit>,
    /// partition → count of assignment writes (production: the
    /// mod_revision an `AssignmentPrecondition` compares). Only
    /// maintained under `chunked_plans`.
    pub assignment_versions: BTreeMap<Partition, u8>,
    /// Production `config/changelog`.
    pub config: Config,
    /// Production `migrations/current`.
    pub migration: Option<Migration>,
    /// pod → old-topic partitions its seal ack reports sealed.
    pub seal_acks: BTreeMap<PodId, BTreeSet<Partition>>,

    // ── processes ──────────────────────────────────────────────
    pub pods: BTreeMap<PodId, Pod>,
    pub routers: BTreeMap<RouterId, Router>,

    // ── kafka ──────────────────────────────────────────────────
    /// (generation epoch, partition) → its log.
    pub changelogs: BTreeMap<(Epoch, Partition), Changelog>,

    // ── failure/workload budgets (bound the state space) ───────
    pub writes_left: u8,
    pub reads_left: u8,
    pub crashes_left: u8,
    pub rejoins_left: u8,
    /// Times a router may (re)join: a late slot coming up for the first
    /// time, or a dead router returning as a fresh process.
    pub router_joins_left: u8,
    /// Deadline cancellations the checker may still inject.
    pub cancels_left: u8,
    pub migrations_left: u8,
    /// Whether any strong read was actually served (reachability evidence
    /// for the read properties). A flag rather than a count: nothing reads
    /// how many, and a count would split otherwise-identical states by
    /// their read history.
    pub read_served: bool,

    // ── violation flags (history-free invariant encoding) ──────
    /// Set when a write is acked by a pod while a *different* pod that
    /// the protocol has designated as the (incoming or current) owner
    /// has already warmed — the acked write sits beyond that owner's
    /// warm cutoff and is invisible to it forever. This is the
    /// acked-write loss the drain/fence/HWM machinery exists to prevent.
    pub lost_acked_write: bool,
    /// Set when a rebalance plans a partition that already has an
    /// in-flight handoff, clobbering it — the overlap
    /// `plan_partial_rebalance`'s pinning must make unreachable.
    pub double_planned_handoff: bool,
    /// Set when a strong read is served by a pod whose warm prefixes are
    /// behind some log holding the key.
    pub stale_strong_read: bool,
    /// Set when a pod acks a write under a captured epoch that is not the live one.
    pub mixed_modulus_acceptance: bool,
    /// Set when a router delivers a request while an earlier request for
    /// the same key is still parked, so the later one lands first.
    pub overtaken_request: bool,

    // ── reachability flags (probe evidence, history encoding) ──
    /// A cancellation resolved as a reaffirm-Complete toward the live
    /// current owner.
    pub reaffirmed: bool,
    /// A cancellation resolved as an atomic successor replacement.
    pub replaced_with_successor: bool,
    /// A cancellation happened while some router held parked requests
    /// for the partition — the composition the replacement design must
    /// keep safe and live.
    pub cancelled_while_stash_parked: bool,
    /// A pending chunk unit applied after its plan's first transaction.
    pub pending_unit_applied: bool,
    /// A pending chunk unit dropped by a failed plan-time guard.
    pub pending_unit_dropped: bool,
    pub migration_completed: bool,
    pub migration_cancelled: bool,
    /// A pod sealed an old-topic partition it had not loaded.
    pub sealed_without_warm: bool,
    /// A write for a partition born in the flip parked before its handoff existed.
    pub born_partition_write_parked: bool,
    /// A migration request is waiting to start.
    pub requested: bool,
    /// The Sealing grace has lapsed for the current saga.
    pub seal_overdue: bool,
    pub seal_breaks_left: u8,
}

/// Everything that can happen, from every actor, including failures.
/// The checker interleaves these exhaustively.
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Action {
    // ── coordinator (pure derivation over etcd state) ──────────
    /// Cancellation of a handoff whose new owner is unregistered — the
    /// dead-new-owner arm of the coordinator's cleanup, as a
    /// mod_revision-guarded atomic *replacement*: the record is swapped
    /// for whatever resolves its stashes (a reaffirm-Complete toward a
    /// live current owner, a successor Freezing handoff, or — only when
    /// nothing is placeable — a plain delete). Scheduled independently
    /// of `Rebalance` and `AdvancePhase` — the coordinator's watch
    /// handlers and tick run concurrently in production, and an
    /// overlapping outgoing coordinator is just more interleavings of
    /// the same guarded actions.
    CancelDeadNewOwner(Partition),
    /// Deadline cancellation of any in-flight handoff, with the same
    /// replacement disposition. The model has no clock, so the deadline
    /// trigger is "the checker schedules this whenever it likes" — a
    /// superset of every timing policy production could apply, which is
    /// exactly what makes the phase-aware deadline a production-only
    /// concern. Budgeted (`cancels_left`): an unbounded cancel action
    /// would let the checker cancel forever and vacuously defeat the
    /// convergence property.
    Cancel(Partition),
    /// The rebalance half of `handle_pod_change`: when no handoffs are
    /// in flight, create Freezing handoffs for every assignment diff in
    /// one transaction.
    Rebalance,
    /// The same rebalance applying its plan in chunks (production:
    /// `apply_plan` past the txn budget): the first planned handoff
    /// lands now, the rest wait in `pending_plan`.
    RebalanceChunked,
    /// Apply the front `pending_plan` unit — or drop it when its
    /// plan-time guards no longer hold (a conflicted unit standing down).
    ApplyPendingUnit,
    /// `check_phase_advance` for one partition (watch nudge or tick).
    AdvancePhase(Partition),
    /// Post-Complete cleanup: delete the handoff record and its acks
    /// (guarded on the record still being the same attempt).
    CleanupComplete(Partition),

    // ── the migration saga ─────────────────────────────────────
    /// The control plane writes `migrations/requested`. Budgeted.
    MigrateRequest,
    /// The coordinator starts the saga from the request once no handoff is in flight.
    MigrateStart,
    /// A request is rejected or expires before it starts.
    MigrateRequestExpires,
    /// One pass of the migration driver (`migration::reconcile`).
    MigrateDrive,
    /// A cancel before Sealing: the operator's, or the pre-flip deadline's.
    MigrateCancel,
    /// One pass of a pod's seal duty while the saga is Sealing.
    SealTick(PodId),
    /// The seal grace lapses: every leader now seals what no ack reports sealed.
    SealGraceElapses,
    /// A pod's seal keeps failing while its lease stays alive (a hung Kafka client).
    BreakSeal(PodId),
    /// A router's config watch delivers the live config.
    AdoptConfig(RouterId),

    // ── pods (the converge model) ──────────────────────────────
    /// One convergence step for (pod, partition): derive the desired
    /// state from durable state and apply the next transition toward it
    /// (warm / fence+ack / warm+ack / release / unfence).
    Converge(PodId, Partition),

    // ── routers ────────────────────────────────────────────────
    /// The router observes the current durable state of one partition
    /// and reacts: stash+ack during a handoff, cutover+drain at
    /// Complete, drain-back on cancellation. A stale router is modeled
    /// by the checker simply not scheduling this action for a while.
    Observe(RouterId, Partition),

    // ── workload ───────────────────────────────────────────────
    /// A client write for (router, key), hashed with the router's adopted modulus.
    ClientWrite(RouterId, Key),
    /// A strong read for (router, key); parks with the writes while stashing.
    ClientStrongRead(RouterId, Key),

    // ── failures ───────────────────────────────────────────────
    /// The pod process dies and instantly restarts under the same name
    /// before its lease expires: registration and assignments survive,
    /// all process memory (warmed, fenced) is wiped.
    CrashRestartWithinTtl(PodId),
    /// The pod's lease expires while the process is still running: the
    /// registration disappears, but the data plane keeps serving for a
    /// bounded number of writes (the zombie window) until `SelfFence`.
    LeaseExpire(PodId),
    /// The zombie's keepalive notices the dead lease and the process
    /// exits (production fix 1).
    SelfFence(PodId),
    /// A pod notices its lease is gone and stops claiming the partitions
    /// it holds (production: the keepalive's next round, or the
    /// registration watch firing). Only reachable under delayed
    /// detection; prompt detection drops the claim with the lease.
    NoticeLeaseLoss(PodId),
    /// A pod's published claim ages past the renewal margin while its
    /// registration still stands (production: the keepalive stops
    /// confirming, but etcd holds the lease until the full TTL). The pod
    /// refuses to serve and the coordinator, seeing a live registration,
    /// reassigns nothing.
    AuthorityLapse(PodId),
    /// A renewal lands and the claim comes back, without the session ever
    /// having ended.
    AuthorityRenew(PodId),
    /// A previously-dead pod rejoins under its old name: fresh
    /// registration, fresh lease, empty memory (production: normal pod
    /// startup; its partitions come back via Warming handoffs from the
    /// rebalance its registration triggers).
    Join(PodId),
    /// The router's lease expires while its process keeps running: it
    /// drops out of the freeze quorum but continues routing with its
    /// current table, and stops processing events (its watch loop is on
    /// its way down).
    RouterLeaseExpire(RouterId),
    /// The zombie router's keepalive notices the dead lease and the
    /// process exits (production fix 1).
    RouterSelfFence(RouterId),
    /// A router process starts and registers: a late slot coming up
    /// mid-run, or a dead router returning under its old name. Fresh
    /// process, empty table — production `load_initial` starts from an
    /// empty routing table that fails every lookup closed, and the
    /// model's `Observe` is its bootstrap. A joiner whose `Observe` the
    /// checker never schedules is precisely the silent late joiner the
    /// freeze-quorum snapshot exists to tolerate: registered, counted by
    /// the legacy live-set rule, acking nothing.
    RouterJoin(RouterId),
}