Skip to main content

nopace_nats/
lib.rs

1//! Durable NATS JetStream KV store for nopace.
2//!
3//! # What one key holds
4//!
5//! One key holds the state of **one partition inside one scope**, and nothing
6//! else. That is the whole design, and it is worth being explicit about why,
7//! because the obvious alternative — one key per scope — is what this crate
8//! used to do and it took a service down for nine and a half hours.
9//!
10//! A scope is the budget's identity, so applications reasonably configure one
11//! constant scope and put the customer in the partition. Serializing a scope
12//! meant serializing every partition in it into a single KV value, so that
13//! value grew linearly with the tenant count. At about two thousand tenants it
14//! crossed the server's `max_payload`, NATS refused the write, and because the
15//! write error was discarded the store retried the same oversized value for
16//! ever. Every admission blocked, every request failed closed, and no counter
17//! moved. Keying by partition makes the value's size a function of one
18//! tenant's traffic instead of the whole customer base, and it is also what
19//! stops unrelated tenants from contending on one revision.
20//!
21//! # Delete is a reset
22//!
23//! Deleting or purging a KV key does not remove it; it appends a tombstone,
24//! which `Store::entry` returns with an empty value and a real revision. The
25//! previous implementation fed that empty value to the deserializer and
26//! returned "invalid state" for ever after, so the documented operator
27//! mitigation — `nats kv del` — bricked the key instead of resetting it. The
28//! same went for writing an empty value by hand, which is an ordinary put and
29//! not a tombstone at all. Anything empty is now read as absent state, while
30//! its revision is still used for the next compare-and-set, so a reset is a
31//! reset and the write that follows it is still atomic.
32//!
33//! Bytes that are present but do not decode stay an error: that is corruption
34//! or an incompatible build, not a reset, and quietly discarding live quota
35//! for it would be worse than refusing.
36//!
37//! # What this backend cannot do
38//!
39//! All claims of one call are admitted atomically. Two partitions are two
40//! keys, and two KV keys have no shared transaction, so a call whose claims
41//! span more than one partition is refused with
42//! [`NatsError::CrossPartitionCall`] rather than silently split into
43//! independent decisions that would each let the other's traffic through.
44//! Model such a call as one partition — the group's identity — or use a
45//! backend whose durable unit is the scope.
46
47use std::{
48    collections::BTreeSet,
49    fmt::Write as _,
50    time::{Duration, SystemTime},
51};
52
53use async_nats::jetstream::{
54    self,
55    kv::{self, CreateErrorKind, UpdateErrorKind},
56};
57use bytes::Bytes;
58use futures_util::TryStreamExt;
59use nopace_core::{
60    AdmissionRequest, Completion, CompletionResult, LeaseRenewal, LeaseRenewalResult, PartitionKey,
61    PolicyId, ResetReport, Retention, ScopeKey, ScopeState, Store, StoreDecision, StorePeek,
62    StoreSnapshot, collect_at, decide_at, finish_at, peek_at, renew_at, reset_policy, snapshot_at,
63    unix_millis,
64};
65use sha2::{Digest, Sha256};
66use thiserror::Error;
67
68/// Bytes reserved inside `max_payload` for the subject, the headers carrying
69/// the expected revision, and protocol framing. A write is the value plus all
70/// of that, so the value's ceiling has to sit below the server's.
71const PAYLOAD_OVERHEAD: usize = 4 * 1024;
72
73/// Assumed `max_payload` when the server does not report one.
74const DEFAULT_MAX_PAYLOAD: usize = 1024 * 1024;
75
76/// Default ceiling for one key's serialized state.
77///
78/// Well under the payload limit on purpose. Partition state is a small set of
79/// counters plus a replay cache that grows with that partition's request rate,
80/// and the budget is what turns "the replay cache grew past the transport
81/// limit" — the second way this store can hit the same cliff, on one busy
82/// tenant rather than many quiet ones — into "the oldest replay records are
83/// dropped".
84const DEFAULT_VALUE_BUDGET: usize = 256 * 1024;
85
86/// How many compare-and-set rounds one operation may lose before giving up.
87///
88/// Losing a round means another writer committed to the same partition first.
89/// Per-partition keys make that rare, so exhausting this many rounds is
90/// contention worth reporting rather than waiting out for ever.
91const MAX_COMMIT_ATTEMPTS: usize = 64;
92
93/// Longest characters of an identifier kept in a key for readability.
94const LABEL_BYTES: usize = 48;
95
96#[derive(Clone)]
97pub struct NatsStore {
98    kv: kv::Store,
99    prefix: String,
100    retention: Retention,
101    max_value_bytes: usize,
102    value_budget: usize,
103}
104
105impl NatsStore {
106    pub async fn connect(url: &str, bucket: &str) -> Result<Self, NatsError> {
107        let client = async_nats::connect(url).await.map_err(NatsError::boxed)?;
108        let max_payload = match client.server_info().max_payload {
109            0 => DEFAULT_MAX_PAYLOAD,
110            reported => reported,
111        };
112        let max_value_bytes = max_payload.saturating_sub(PAYLOAD_OVERHEAD).max(1);
113        let context = jetstream::new(client);
114        let kv = match context.get_key_value(bucket).await {
115            Ok(store) => store,
116            Err(_) => context
117                .create_key_value(kv::Config {
118                    bucket: bucket.to_owned(),
119                    history: 1,
120                    // Let the server refuse an oversized value with an error
121                    // instead of closing the connection under it.
122                    max_value_size: i32::try_from(max_value_bytes).unwrap_or(i32::MAX),
123                    ..Default::default()
124                })
125                .await
126                .map_err(NatsError::boxed)?,
127        };
128        Ok(Self {
129            kv,
130            prefix: "nopace.v2".into(),
131            retention: Retention::default(),
132            max_value_bytes,
133            value_budget: DEFAULT_VALUE_BUDGET.min(max_value_bytes),
134        })
135    }
136
137    /// Sets the key prefix.
138    ///
139    /// Keys are `<prefix>.<scope>.<partition>`. The default carries a version
140    /// because keys written by releases before per-partition state have a
141    /// different shape; they are never read or written again, and can be
142    /// purged whenever it suits.
143    pub fn with_prefix(mut self, prefix: impl Into<String>) -> Self {
144        self.prefix = prefix.into();
145        self
146    }
147
148    pub fn with_retention(mut self, retention: Retention) -> Self {
149        self.retention = retention;
150        self
151    }
152
153    /// Sets the ceiling for one key's serialized state.
154    ///
155    /// Replay records older than the budget allows are dropped oldest-first
156    /// once a partition's state reaches it. Clamped to what the server will
157    /// accept.
158    pub fn with_value_budget(mut self, bytes: usize) -> Self {
159        self.value_budget = bytes.clamp(1, self.max_value_bytes);
160        self
161    }
162
163    /// Runs expiry over every partition of one scope.
164    ///
165    /// Returns the number of keys visited. This walks the bucket, so it is a
166    /// maintenance call, not a request-path one.
167    pub async fn collect(&self, scope: &ScopeKey) -> Result<usize, NatsError> {
168        let keys = self.scope_keys(scope).await?;
169        for key in &keys {
170            self.apply_key(key, |state, now| collect_at(state, now, self.retention))
171                .await?;
172        }
173        Ok(keys.len())
174    }
175
176    pub async fn snapshot(
177        &self,
178        scope: &ScopeKey,
179        partition: &PartitionKey,
180    ) -> Result<Option<StoreSnapshot>, NatsError> {
181        Ok(self
182            .read(&self.key(scope, partition))
183            .await?
184            .map(|(state, _)| snapshot_at(&state)))
185    }
186
187    /// Drops one partition's state, the way `nats kv del` does.
188    ///
189    /// The next operation on that partition starts from empty.
190    pub async fn reset(&self, scope: &ScopeKey, partition: &PartitionKey) -> Result<(), NatsError> {
191        self.kv
192            .delete(self.key(scope, partition))
193            .await
194            .map_err(NatsError::boxed)
195    }
196
197    /// Clears a policy's counters, for one partition or for every partition in
198    /// the scope. The second form walks the bucket.
199    pub async fn reset_policy(
200        &self,
201        scope: &ScopeKey,
202        policy: &PolicyId,
203        partition: Option<&PartitionKey>,
204    ) -> Result<ResetReport, NatsError> {
205        let keys = match partition {
206            Some(partition) => vec![self.key(scope, partition)],
207            None => self.scope_keys(scope).await?,
208        };
209        let mut total = ResetReport::default();
210        for key in &keys {
211            let report = self
212                .apply_key(key, |state, _| reset_policy(state, policy, partition))
213                .await?;
214            total.limits += report.limits;
215            total.learned_constraints += report.learned_constraints;
216            total.policy_bindings += report.policy_bindings;
217        }
218        Ok(total)
219    }
220
221    /// Reads a key, treating anything empty as absent state while keeping its
222    /// revision for the next compare-and-set.
223    ///
224    /// Empty arrives two ways, and both are somebody resetting a partition.
225    /// A delete or purge appends a tombstone, which `entry` returns with an
226    /// empty value and a real revision. An operator can also write an empty
227    /// value directly, which is an ordinary `Put` and not a tombstone at all.
228    ///
229    /// Neither is state this store wrote: the smallest encoding of
230    /// `ScopeState` is a sequence number and ten map lengths, so a real value
231    /// is never zero bytes. Reading empty as absent therefore cannot
232    /// misinterpret anything real, and it is what makes both gestures a reset
233    /// rather than a key that answers "stored nopace state is invalid" for ever.
234    ///
235    /// Bytes that are present but will not decode are a different thing —
236    /// corruption, or a value from an incompatible build — and stay an error.
237    /// Silently resetting those would throw away live quota on a bad deploy.
238    async fn read(&self, key: &str) -> Result<Option<(ScopeState, u64)>, NatsError> {
239        let Some(entry) = self.kv.entry(key).await.map_err(NatsError::boxed)? else {
240            return Ok(None);
241        };
242        match entry.operation {
243            _ if entry.value.is_empty() => Ok(Some((ScopeState::default(), entry.revision))),
244            kv::Operation::Put => Ok(Some((bincode::deserialize(&entry.value)?, entry.revision))),
245            kv::Operation::Delete | kv::Operation::Purge => {
246                Ok(Some((ScopeState::default(), entry.revision)))
247            }
248        }
249    }
250
251    async fn apply<T>(
252        &self,
253        scope: &ScopeKey,
254        partition: &PartitionKey,
255        operation: impl Fn(&mut ScopeState, u64) -> T,
256    ) -> Result<T, NatsError> {
257        self.apply_key(&self.key(scope, partition), operation).await
258    }
259
260    /// Reads, transforms and writes one partition under compare-and-set.
261    ///
262    /// Only a lost revision is retried. Anything else — a closed connection, a
263    /// value the server will not accept — is returned, because retrying an
264    /// operation that cannot succeed is how a rate limiter stops answering
265    /// without anybody noticing.
266    async fn apply_key<T>(
267        &self,
268        key: &str,
269        operation: impl Fn(&mut ScopeState, u64) -> T,
270    ) -> Result<T, NatsError> {
271        for attempt in 0..MAX_COMMIT_ATTEMPTS {
272            let existing = self.read(key).await?;
273            let (mut state, revision) = match existing {
274                Some((state, revision)) => (state, Some(revision)),
275                None => (ScopeState::default(), None),
276            };
277            let result = operation(&mut state, unix_millis());
278            let value = self.encode(key, &mut state)?;
279            let committed =
280                match revision {
281                    Some(revision) => self
282                        .kv
283                        .update(key, value, revision)
284                        .await
285                        .map(|_| true)
286                        .or_else(|error| match error.kind() {
287                            UpdateErrorKind::WrongLastRevision => Ok(false),
288                            _ => Err(NatsError::boxed(error)),
289                        })?,
290                    None => {
291                        self.kv.create(key, value).await.map(|_| true).or_else(
292                            |error| match error.kind() {
293                                CreateErrorKind::AlreadyExists => Ok(false),
294                                _ => Err(NatsError::boxed(error)),
295                            },
296                        )?
297                    }
298                };
299            if committed {
300                return Ok(result);
301            }
302            tokio::time::sleep(contention_backoff(attempt)).await;
303        }
304        Err(NatsError::Contended {
305            key: key.to_owned(),
306            attempts: MAX_COMMIT_ATTEMPTS,
307        })
308    }
309
310    /// Serializes one partition's state, dropping the oldest replay records
311    /// first if it does not fit the budget.
312    ///
313    /// Quota counters are never dropped: losing those would hand back capacity
314    /// nobody paid for. The replay cache is what gives up, so a retried
315    /// command that has aged out is re-executed rather than replayed, which is
316    /// the same thing that happens once the retention horizon passes.
317    fn encode(&self, key: &str, state: &mut ScopeState) -> Result<Bytes, NatsError> {
318        let mut encoded = bincode::serialize(state)?;
319        let mut batch = 16usize;
320        while encoded.len() > self.value_budget && evict_oldest(state, batch) {
321            encoded = bincode::serialize(state)?;
322            batch = batch.saturating_mul(2);
323        }
324        if encoded.len() > self.max_value_bytes {
325            return Err(NatsError::StateTooLarge {
326                key: key.to_owned(),
327                bytes: encoded.len(),
328                limit: self.max_value_bytes,
329            });
330        }
331        Ok(Bytes::from(encoded))
332    }
333
334    async fn scope_keys(&self, scope: &ScopeKey) -> Result<Vec<String>, NatsError> {
335        let prefix = format!("{}.{}.", self.prefix, token(scope.as_str()));
336        let mut keys = self.kv.keys().await.map_err(NatsError::boxed)?;
337        let mut matched = Vec::new();
338        while let Some(key) = keys.try_next().await.map_err(NatsError::boxed)? {
339            if key.starts_with(&prefix) {
340                matched.push(key);
341            }
342        }
343        Ok(matched)
344    }
345
346    fn key(&self, scope: &ScopeKey, partition: &PartitionKey) -> String {
347        format!(
348            "{}.{}.{}",
349            self.prefix,
350            token(scope.as_str()),
351            token(partition.as_str())
352        )
353    }
354
355    /// The single partition a command addresses.
356    fn addressed(partitions: &BTreeSet<PartitionKey>) -> Result<&PartitionKey, NatsError> {
357        let mut iterator = partitions.iter();
358        match (iterator.next(), iterator.next()) {
359            (Some(partition), None) => Ok(partition),
360            _ => Err(NatsError::CrossPartitionCall {
361                partitions: partitions.iter().cloned().collect(),
362            }),
363        }
364    }
365}
366
367impl Store for NatsStore {
368    type Error = NatsError;
369
370    async fn decide(&self, request: AdmissionRequest) -> Result<StoreDecision, Self::Error> {
371        let partitions = request.partitions();
372        let partition = Self::addressed(&partitions)?.clone();
373        let scope = request.scope.clone();
374        self.apply(&scope, &partition, |state, now| {
375            decide_at(state, &request, now, self.retention)
376        })
377        .await
378    }
379
380    async fn peek(&self, request: AdmissionRequest) -> Result<StorePeek, Self::Error> {
381        let partitions = request.partitions();
382        let partition = Self::addressed(&partitions)?;
383        let state = self
384            .read(&self.key(&request.scope, partition))
385            .await?
386            .map(|(state, _)| state)
387            .unwrap_or_default();
388        Ok(peek_at(&state, &request, unix_millis()))
389    }
390
391    async fn renew(&self, renewal: LeaseRenewal) -> Result<LeaseRenewalResult, Self::Error> {
392        let partition = Self::addressed(&renewal.partitions)?.clone();
393        let scope = renewal.scope.clone();
394        self.apply(&scope, &partition, |state, now| {
395            renew_at(state, &renewal, now, self.retention)
396        })
397        .await
398    }
399
400    async fn finish(&self, completion: Completion) -> Result<CompletionResult, Self::Error> {
401        let partition = Self::addressed(&completion.partitions)?.clone();
402        let scope = completion.scope.clone();
403        self.apply(&scope, &partition, |state, now| {
404            finish_at(state, &completion, now, self.retention)
405        })
406        .await
407    }
408}
409
410/// Drops up to `batch` of the oldest entries from the replay caches.
411///
412/// Returns whether anything was dropped. The order is least harmful first:
413/// decision replays, then completion and renewal replays, then the record that
414/// a permit was completed, and only then the permits themselves — dropping one
415/// of those makes a late completion report an unknown permit and leaves a
416/// concurrency lease to expire on its own.
417///
418/// Keys are UUIDv7, so ascending key order is the order they were issued in.
419fn evict_oldest(state: &mut ScopeState, batch: usize) -> bool {
420    fn drop_oldest<V>(map: &mut std::collections::BTreeMap<uuid::Uuid, V>, batch: usize) -> bool {
421        let victims: Vec<_> = map.keys().take(batch).copied().collect();
422        for victim in &victims {
423            map.remove(victim);
424        }
425        !victims.is_empty()
426    }
427
428    drop_oldest(&mut state.decisions, batch)
429        || drop_oldest(&mut state.completions, batch)
430        || drop_oldest(&mut state.renewals, batch)
431        || drop_oldest(&mut state.completed_permits, batch)
432        || drop_oldest(&mut state.permits, batch)
433}
434
435/// Encodes a caller-controlled identifier as one NATS KV key token.
436///
437/// KV keys accept `[-/_=.a-zA-Z0-9]` and `.` separates subject tokens, so an
438/// identifier can be neither trusted to be representable nor to stay inside
439/// one token — nopace identifiers allow `:` and `/` and run to 128 bytes.
440/// Substituting the unrepresentable characters is not enough on its own:
441/// `tenant:a` and `tenant/a` would become the same key and silently share one
442/// budget. So the readable part is only a label for whoever runs `nats kv ls`,
443/// and a digest of the original bytes carries the identity.
444///
445/// The result is stable across processes and releases, bounded at
446/// `LABEL_BYTES + 33` bytes, and contains only `[-_a-zA-Z0-9]`.
447fn token(value: &str) -> String {
448    let mut encoded = String::with_capacity(LABEL_BYTES + 33);
449    for character in value.chars().take(LABEL_BYTES) {
450        encoded.push(match character {
451            'a'..='z' | 'A'..='Z' | '0'..='9' | '-' | '_' => character,
452            _ => '-',
453        });
454    }
455    encoded.push('-');
456    for byte in &Sha256::digest(value.as_bytes())[..16] {
457        let _ = write!(encoded, "{byte:02x}");
458    }
459    encoded
460}
461
462/// Backs off a little further each lost round, with jitter so that two
463/// contending writers do not keep colliding in step.
464fn contention_backoff(attempt: usize) -> Duration {
465    let base = 1u64 << attempt.min(6);
466    let jitter = SystemTime::now()
467        .duration_since(SystemTime::UNIX_EPOCH)
468        .map(|since| since.subsec_nanos() as u64 % 4)
469        .unwrap_or(0);
470    Duration::from_millis(base + jitter)
471}
472
473#[derive(Debug, Error)]
474pub enum NatsError {
475    #[error("nats operation failed: {0}")]
476    Nats(Box<dyn std::error::Error + Send + Sync>),
477    #[error("stored nopace state is invalid: {0}")]
478    Serialization(#[from] bincode::Error),
479    #[error(
480        "this store keys state per partition, so a call spanning {} partitions ({}) cannot be admitted atomically",
481        .partitions.len(),
482        .partitions.iter().map(PartitionKey::as_str).collect::<Vec<_>>().join(", ")
483    )]
484    CrossPartitionCall { partitions: Vec<PartitionKey> },
485    #[error("lost {attempts} compare-and-set rounds for {key}")]
486    Contended { key: String, attempts: usize },
487    #[error("state for {key} is {bytes} bytes, over the {limit} byte transport limit")]
488    StateTooLarge {
489        key: String,
490        bytes: usize,
491        limit: usize,
492    },
493}
494
495impl NatsError {
496    fn boxed(error: impl std::error::Error + Send + Sync + 'static) -> Self {
497        Self::Nats(Box::new(error))
498    }
499}
500
501#[cfg(test)]
502mod tests {
503    use super::*;
504
505    #[test]
506    fn a_key_token_stays_inside_one_subject_token() {
507        for identifier in [
508            "tenant:a",
509            "tenant/a",
510            "tenant.a",
511            "tenant-a",
512            &"x".repeat(128),
513        ] {
514            let encoded = token(identifier);
515            assert!(
516                encoded
517                    .chars()
518                    .all(|c| c.is_ascii_alphanumeric() || c == '-' || c == '_'),
519                "{encoded} is not one subject token"
520            );
521            assert!(encoded.len() <= LABEL_BYTES + 33, "{encoded} is unbounded");
522        }
523    }
524
525    #[test]
526    fn identifiers_that_flatten_to_the_same_label_keep_different_keys() {
527        // The bug this replaces: `replace(['/', ':'], "_")` gave all of these
528        // one key, so three tenants shared one budget.
529        let collided = ["tenant:a", "tenant/a", "tenant_a", "tenant.a"];
530        let keys: BTreeSet<_> = collided.iter().map(|value| token(value)).collect();
531        assert_eq!(keys.len(), collided.len(), "identifiers collided: {keys:?}");
532    }
533
534    #[test]
535    fn a_key_token_is_stable() {
536        assert_eq!(token("acct-1"), token("acct-1"));
537        assert_ne!(token("acct-1"), token("acct-2"));
538    }
539
540    #[test]
541    fn eviction_gives_up_replay_before_it_gives_up_permits() {
542        let mut state = ScopeState::default();
543        state.decisions.insert(
544            uuid::Uuid::now_v7(),
545            nopace_core::DecisionRecord {
546                decision: StoreDecision::Wait {
547                    retry_at: nopace_core::Eligibility::At(0),
548                    limited_by: Vec::new(),
549                },
550                expires_at: 0,
551            },
552        );
553        state.completed_permits.insert(uuid::Uuid::now_v7(), 0);
554
555        assert!(evict_oldest(&mut state, 8));
556        assert!(state.decisions.is_empty());
557        assert_eq!(state.completed_permits.len(), 1, "permits outlive replays");
558        assert!(evict_oldest(&mut state, 8));
559        assert!(!evict_oldest(&mut state, 8), "nothing left to give up");
560    }
561}