1use 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
68const PAYLOAD_OVERHEAD: usize = 4 * 1024;
72
73const DEFAULT_MAX_PAYLOAD: usize = 1024 * 1024;
75
76const DEFAULT_VALUE_BUDGET: usize = 256 * 1024;
85
86const MAX_COMMIT_ATTEMPTS: usize = 64;
92
93const 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 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 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 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 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 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 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 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 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 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 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
410fn 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
435fn 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
462fn 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 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}