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.

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:         hbac_crdt::RuleSet,
    pub ipa_idp_overrides:  LwwMap<String, IpaIdpOverride>,
}
}

CRDT_GENERATION counter

A process-global AtomicU64 (CRDT_GENERATION in src/crdt/mod.rs) 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 gossip round produces no net change (all merges are no-ops), the counter does not advance.

The gossip loop tracks two per-peer generation maps:

• peer_last_gen[peer] — the local CRDT_GENERATION after the last successful sync with this peer. Used for two purposes: (1) before each outbound push, if CRDT_GENERATION.load() equals peer_last_gen[peer], the CRDT has not changed and the push is skipped entirely; (2) when a push is needed, delta_since(peer_last_gen[peer]) produces a sparse delta that contains only new entries, reducing payload size.

• peer_response_gen[peer] — the peer’s CRDT_GENERATION reported in their last response envelope (GossipEnvelope.my_gen). This value is sent back to the peer in the next push as request_delta_since so the peer can construct a delta response rather than replying with its full state.

On any error (connection failure, non-2xx response, wrapping-key pull failure), both entries for that peer are cleared so the next round performs a full-state exchange and allows the lagging peer to catch up.

CRDT primitives

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: LwwRegister<T>);
}
}

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 merge(&mut self, other: OrMap<K, V>);
    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.

purge_old_tombstones(cutoff) permanently removes tombstoned entries whose tombstone_at timestamp is older than cutoff. Called approximately once per hour 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: LwwMap<K, V>);
    pub fn retain<F: Fn(&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: retain(|s| s.expires_at > now) drops all expired families before each outbound push and after each inbound merge, keeping the gossip payload bounded over time.

Persistence

IdpCrdt is persisted to the local database on every mutation and after every inbound gossip merge. 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 all ten fields from the database. 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.

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).
5. Write to the in-memory CRDT.
6. Gossip propagates the new public key entry to all peers within ~2 gossip intervals.

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 hourly 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 (every gossip round): IdpCrdt::purge_expired_families(now) calls refresh_families.retain(|s| s.expires_at > now) before each outbound push and after each inbound merge. Expired families are not included in the next gossip message and do not accumulate across peers.

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.
• hbac_crdt::RuleSet (hbac_rules): each axis within a rule uses a security-conservative CRDT — RW-Set (remove-wins) for member sets and DW-Register (disable-wins) for category flags and mfa_bypass. 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.