CRDT State

Ahdapa replicates cluster state using Conflict-free Replicated Data Types (CRDTs). All replicated state lives in IdpCrdt (src/crdt/mod.rs). The design goal is that any node can merge state from any other node in any order and the result is the same — no coordination, no leader, no quorum.

The primitive implementations (OrMap, LwwMap, LwwRegister in src/crdt/primitives.rs, and the causal family in src/crdt/causal/) are thin wrappers around the agirru-crdt crate, extracted from ahdapa’s own original CRDT design into a standalone, generic library. The wrapper types keep the same names, method signatures, and call sites this crate always had — the migration was an internal swap of what backs them, not a rewrite of how they’re used.

IdpCrdt fields

#![allow(unused)]
fn main() {
pub struct IdpCrdt {
    pub signing_keys:       OrMap<String, SigningKeyEntry>,
    pub active_kid:         LwwRegister<String>,
    pub wrapping_key_id:    LwwRegister<String>,
    pub cluster_nodes:      OrMap<String, NodeEntry>,
    pub clients:            OrMap<String, ClientEntry>,
    pub refresh_families:   LwwMap<String, RefreshFamilyState>,
    pub revoked_sessions:   LwwMap<String, i64>,
    pub scope_definitions:  LwwMap<String, ScopeDefinition>,
    pub hbac_rules:         RuleSet,
    pub hbac_gen:           u64,       // local-only, not serialised
    pub hbac_clock:         HbacClock, // local-only, not serialised
    pub ipa_idp_overrides:  LwwMap<String, IpaIdpOverride>,
    // ... several more LWW-Map fields for SPIFFE, upstream tokens, SAML2, federation policies
    pub rar_types:          LwwMap<String, RarTypeEntry>,
    pub rar_rules:          RarRuleSet,
    pub rar_gen:            u64,       // local-only, not serialised
}
}

IdpCrdt implements agirru_crdt::{Merge, Delta, ReplicaScoped} directly (src/crdt/mod.rs) — merge/delta_since/delta_range aggregate one call per field, with hbac_rules and rar_rules special-cased to bump hbac_gen / rar_gen only when their merge actually changed something. ReplicaScoped::retain_replicas is scoped only to hbac_rules and rar_rules — it’s the mechanism AhdapaGossipHooks uses to reject a gossip peer trying to introduce or echo back HBAC tags for a replica it doesn’t own (see Admission filters).

CRDT_GENERATION counter

CRDT_GENERATION (src/crdt/mod.rs) is a process-wide agirru_crdt::GenerationClock — an Arc<AtomicU64> wrapper from the agirru-crdt crate, LazyLock-initialised. It is incremented on every mutation that actually changes CRDT state: new entries inserted via insert or merge, tombstones applied, LWW values set when the incoming timestamp wins. When a merge produces no net change (a redundant delivery of data already known), the counter does not advance and the field’s merge returns false — every primitive’s merge now reports whether it actually changed anything, which IdpCrdt::merge aggregates with |= across all fields into a single “did this round change local state” bool.

Per-peer generation bookkeeping — the equivalent of what used to be ahdapa’s own peer_last_gen/peer_response_gen maps — is now owned internally by agirru_engine::GossipEngine’s PeerBook, not by ahdapa. Ahdapa doesn’t see or manage this state directly; it only implements the Storage/Delta primitives the engine calls to build deltas and detect “nothing changed since last sync.” See Gossip Protocol for how the engine uses this to decide what to send.

CRDT primitives

All three wall-clock primitives below are backed by the corresponding agirru_crdt type (LwwRegister → agirru_crdt::LwwRegister, OrMap/LwwMap → agirru_crdt::RwMap). Every merge now returns bool — true if the merge actually changed local state, false for a redundant/no-op delivery — which IdpCrdt::merge aggregates across all fields to decide whether to bump CRDT_GENERATION and whether agirru_engine should fire its on_merged hook and changed notification at all.

LwwRegister

Last-Write-Wins Register. The value with the higher timestamp wins. On equal timestamps, the node with the lexicographically greater node_id wins (deterministic tie-breaking).

#![allow(unused)]
fn main() {
impl<T> LwwRegister<T> {
    pub fn set(&mut self, value: T, timestamp: i64, node_id: &str);
    pub fn get(&self) -> Option<&T>;
    pub fn merge(&mut self, other: Self) -> bool;
}
}

Used for active_kid and wrapping_key_id. Setting a value with an older timestamp is a no-op, making set idempotent.

OrMap

Observed-Remove Map. Supports soft deletes via tombstones. Merge semantics: the union of live entries, where any tombstone suppresses its entry on both sides.

#![allow(unused)]
fn main() {
impl<K, V> OrMap<K, V> {
    pub fn insert(&mut self, key: K, value: V, timestamp: i64);
    pub fn remove(&mut self, key: &K, timestamp: i64);   // sets tombstone
    pub fn upsert(&mut self, key: K, value: V, timestamp: i64); // for updates
    pub fn get(&self, key: &K) -> Option<&V>;            // None for tombstoned
    pub fn live_values(&self) -> impl Iterator<Item = (&K, &V)>;
    pub fn retain_keys<F: Fn(&K) -> bool>(&mut self, allowed: F); // admission filtering
    pub fn merge(&mut self, other: Self) -> bool;
    pub fn purge_old_tombstones(&mut self, cutoff: i64); // drops tombstones older than cutoff
}
}

Used for cluster_nodes and clients. A tombstone wins over a live entry on merge — deleting a client on any node will eventually suppress it everywhere.

remove records a tombstone even when the key is absent from the local map. This is necessary to prevent entry resurrection on out-of-order gossip delivery: if a remove arrives at a node before the corresponding insert (because gossip rounds fire in different orders), the pre-emptive tombstone suppresses the subsequent insert when it eventually arrives.

retain_keys(allowed) drops every entry whose key fails the predicate — this is what AhdapaGossipHooks::filter_inbound calls on cluster_nodes to enforce the node allowlist (see Admission filters).

purge_old_tombstones(cutoff) permanently removes tombstoned entries whose tombstone_at timestamp is older than cutoff. Called by the periodic maintenance task (src/routes/gossip/maintenance.rs) with cutoff = now - tombstone_ttl_secs. Entries that are still live (not tombstoned) are never removed by this call.

LwwMap

A map where each key has an independent LWW-Register value.

#![allow(unused)]
fn main() {
impl<K, V> LwwMap<K, V> {
    pub fn set(&mut self, key: K, value: V, timestamp: i64, node_id: &str);
    pub fn get(&self, key: &K) -> Option<&V>;
    pub fn merge(&mut self, other: Self) -> bool;
    pub fn retain<F: FnMut(&V) -> bool>(&mut self, f: F); // remove entries where f returns false
}
}

Used for refresh_families. Each family_id key has its own LWW value (RefreshFamilyState containing max_index and expires_at). The highest max_index seen propagates on merge; setting max_index = u64::MAX is the revocation signal.

retain(f) removes entries where f(value) returns false. Used for expired-family purge: IdpCrdt::purge_expired_families(now) calls retain(|s| s.expires_at > now). This runs on the periodic maintenance task’s cadence (src/routes/gossip/maintenance.rs, independent of gossip rounds), not per gossip round — an expired-but-not-yet-purged family riding along in one extra gossip round is a bandwidth/size concern only (expired families are already rejected on use elsewhere), not a correctness one.

Persistence

IdpCrdt is persisted to the local database on every mutation and after every gossip merge that actually changed state. The schema mirrors the CRDT structure exactly:

Three additional nullable columns were added to crdt_clients in migration 0022_client_kerberos.sql to support the kerberos_client_auth token endpoint authentication method:

Exactly one of kerberos_principal or kerberos_principal_pattern is set per Kerberos client; all three columns are NULL for non-Kerberos clients.

At startup, IdpCrdt::load_from_db reconstructs every field except hbac_rules/hbac_clock from the database; those two (and rar_rules) are loaded separately via load_hbac_rules(db, replica_id) (see Persistence above) and assigned onto the freshly-loaded IdpCrdt. Static HBAC and RAR rules and RAR types are then seeded from config, and the snapshot and types are persisted right away, so a restart neither re-seeds nor re-mints tags from a reset clock. replica_id is derived deterministically from this node’s node_id (replica_id_from_str), so a fresh HbacClock seeded on first startup is stable across restarts without needing extra stored state. Revoked session entries older than revocation_cutoff (derived from session_ttl) are filtered at load time so a restarted node does not carry stale revocations. Built-in scope definitions are seeded into crdt_scopes on first startup if not already present.

Causal CRDT primitives (hbac_rules)

hbac_rules uses a separate primitive family from the rest of IdpCrdt — true causal (vector-clock) conflict resolution rather than wall-clock (timestamp, node_id) LWW. This is a documented security invariant: all CRDT merge resolutions for HBAC access control must be conservative (remove-wins, disable-wins), so that a concurrent stale re-add or re-enable can never widen access. Wall-clock LWW cannot guarantee this under clock skew — a concurrent “add” could numerically outrace a “remove” and win.

These live in src/crdt/causal/ — thin wrappers, again, around agirru_crdt’s RwMap/DwRegister/LwwRegister/VectorClock/CausalTag types:

HbacClock (src/crdt/hbac/clock.rs) owns the local replica’s tag-minting state: a replica_id, a local Lamport counter, and a VectorClock. It replaces what used to be a separate hbac-crdt::OpLog’s clock-ownership role — now that the materialised rule state lives directly on IdpCrdt.hbac_rules, HbacClock only ever mints tags, it never owns rule content. Because agirru_crdt’s primitives deliberately don’t expose raw tag lists (by design), the clock can’t be reconstructed by scanning existing tags on restart the way the old OpLog::restore_clock_from_state did — so it’s persisted directly alongside hbac_rules instead (see Persistence).

Causal LWWRegisters order writes by (physical_ts, logical_ts, replica) only, and HbacClock mints physical_ts = 0. So that a write made after observing a remote one sorts after it, HbacClock::observe(vclock, max_logical_ts) both merges the vector clock and lifts the local counter past the highest logical timestamp in the merged LWW registers (RuleSet/RarRuleSet::max_lww_logical_ts) — the Lamport rule, as agirru_crdt::Clock::observe does for its own tags.

HBACRule/RuleSet (src/crdt/hbac/rule.rs) implement the local Merge trait (fn merge(&mut self, other: &Self) -> bool), bridging to agirru_crdt::Merge internally with a throwaway GenerationClock per call — safe because nothing in this crate consumes Delta/generation numbers for these fields. ReplicaScoped is implemented by delegating to every field (HBACRule) or to existence plus every rule (RuleSet), which is what lets IdpCrdt::retain_replicas — scoped only to hbac_rules and rar_rules — filter by replica ownership during gossip admission.

Bootstrap

On a brand-new node with an empty database:

1. load_from_db returns an all-default (empty) IdpCrdt.
2. bootstrap_node_kem_key() generates an ML-KEM-768 key pair and an ECDSA P-256 gossip signing key pair; stores all four DER values in node_keys.
3. bootstrap_signing_key() generates a JWT signing key pair using the algorithm from [server] jwt_signing_algorithm (default: ES256), stores the private key in node_keys.jwt_signing_priv_der (never in CRDT), computes kid = base64url(SHA256(spki_der)[..8]), inserts a SigningKeyEntry (public key + algorithm only) into signing_keys, and sets active_kid. If an existing key in node_keys uses a different algorithm than the configured one, a new key is generated automatically (algorithm upgrade path).
4. bootstrap_wrapping_key() checks node_keys.wrapping_key_cms_der:
   • If present: decrypts with open_raw() to recover the 32-byte key; restores wrapping_key_id to the CRDT if not already set.
   • If absent: generates 32 random bytes, seals them with seal_raw() to the node’s own KEM public key, stores the CMS blob in node_keys, generates a UUID, and publishes the UUID to the CRDT as wrapping_key_id with timestamp=1.
5. persist_to_db flushes to the database.

When gossip is enabled, the node receives the cluster’s existing CRDT state on the first gossip round and merges it. If the peer’s wrapping_key_id differs from the local UUID, the node pulls the actual key via GET /api/gossip/wrapping-key.

Key rotation

Rotating the signing key is an admin operation (POST /api/admin/keys/rotate):

1. Generate a new key pair using the algorithm from [server] jwt_signing_algorithm (default: ES256).
2. Compute kid = base64url(SHA256(spki_der)[..8]).
3. Store the private key in node_keys.jwt_signing_priv_der (replaces previous active key). The private key is never written to crdt_signing_keys.
4. Insert a SigningKeyEntry with public key + algorithm into crdt_signing_keys (OR-Map insert) and update crdt_active_kid (LWW INSERT OR REPLACE). A SAML2 signing certificate is generated with each new key (365-day validity) and stored in SigningKeyEntry.saml_cert_der (serde rename "sc", default; the manual PartialEq includes it). The certificate is served in the IdP metadata and in outgoing SAML KeyInfo, pinned per kid so it is stable across nodes and refreshes.
5. Write to the in-memory CRDT.
6. Gossip propagates the new public key entry to all peers immediately: the CRDT write calls engine.notify_local_change(), triggering an immediate off-cycle gossip round instead of waiting for the next periodic tick (see Gossip Protocol). Convergence is typically under 12 ms in a full-mesh cluster.

Old keys remain in signing_keys and continue to validate tokens signed before the rotation until their not_after timestamp passes. The JWKS endpoint (/jwks) serves all live (non-tombstoned) keys. Any node that issued a token with a given kid holds the corresponding private key; other nodes can still validate those tokens using the gossiped public key.

A signing key can be explicitly revoked before its not_after deadline via DELETE /api/admin/keys/{kid}. This tombstones the OR-Map entry so that live_values() skips it, and the key is no longer served from /jwks. If the revoked key is the active kid, a warning is logged; a key rotation (POST /api/admin/keys/rotate) should follow immediately. Tombstones for revoked signing keys are GC-purged by the same periodic maintenance task that processes client and node tombstones.

Refresh token family lifecycle

RefreshFamilyState carries an expires_at unix timestamp (set when the family is created from the max_refresh_token_age configuration). Two purge paths keep the CRDT bounded:

1. In-memory purge (periodic maintenance task): IdpCrdt::purge_expired_families(now) calls refresh_families.retain(|s| s.expires_at > now). Runs on the maintenance task’s cadence (src/routes/gossip/maintenance.rs), independent of gossip rounds — see the note under CRDT primitives → LwwMap above.

2. Database purge (approximately hourly): cleanup_expired_families deletes rows from crdt_refresh_families WHERE expires_at < now. On startup, load_refresh_families also filters out already-expired rows, so a crashed or restarted node does not re-inflate its CRDT from stale DB rows.

Refresh token revocation

Revoking a refresh token family (DELETE /api/admin/refresh-families/{family_id}) sets max_index = u64::MAX in the CRDT. Any node that receives this value via gossip will reject all future refresh tokens in that family, because every valid token_index is less than u64::MAX.

Partition behaviour

During a network partition, each node operates on its local CRDT snapshot. After the partition heals, the first gossip exchange merges the diverged states. For each CRDT type:

• OR-Map (signing keys): union of live entries; tombstones propagate — a key revoked on one side of the partition will suppress the corresponding entry on reconnect.
• LWW-Register (active_kid, wrapping_key_id): the highest timestamp wins; the losing side’s write is silently dropped. For wrapping_key_id, the winning UUID triggers an on-demand pull of the actual key from the peer that set it.
• OR-Map (clients, cluster_nodes): union of live entries; tombstones propagate on merge.
• LWW-Map (refresh_families): per-key, highest timestamp wins — a max_index set to u64::MAX (revocation) on one side of the partition propagates and invalidates any lower indexes issued during the partition.
• LWW-Map (revoked_sessions): per-subject, highest timestamp wins — a revocation recorded on one side of the partition propagates and invalidates sessions whose iat is before the winning revoked_at. Only present when distributed_mode >= eventual; in off mode the field is populated but stays empty and is only checked node-locally.
• LWW-Map (scope_definitions): per-scope-name, highest timestamp wins — a scope created or deleted on one side of the partition propagates on merge. Deletions (tombstones) set is_deleted = true in the LWW value; the winning entry suppresses the scope from discovery and UserInfo claim resolution on all nodes.
• RuleSet (hbac_rules): each axis within a rule uses a security-conservative causal CRDT — RW-Set (remove-wins) for member sets and DW-Register (disable-wins) for category flags and mfa_bypass, both backed by agirru_crdt (see Causal CRDT primitives above). Rule existence is an RW-Set of RuleIds; deleting a rule on one side of the partition propagates and suppresses it on the other side after merge. A concurrent stale re-enable or re-add on the other side of the partition cannot widen access because disable-wins and remove-wins semantics apply.