use std::{
collections::HashMap,
fmt,
sync::{Arc, Mutex},
time::{Duration, Instant},
};
use async_trait::async_trait;
use crate::clock::{SharedClock, system_clock};
use super::model::{
DEFAULT_MAX_IDEMPOTENCY_RECORDS, DEFAULT_MAX_IDEMPOTENCY_STORED_HEADER_BYTES,
DEFAULT_MAX_IDEMPOTENCY_STORED_RESPONSE_BYTES, IdempotencyKey, IdempotencyLease,
IdempotencyRequestHash, IdempotencyReservation, IdempotencyStore, IdempotencyStoreError,
StoredIdempotencyResponse,
};
#[derive(Debug, Clone)]
pub(super) struct IdempotencyEntry {
pub(super) request_hash: IdempotencyRequestHash,
pub(super) state: EntryState,
pub(super) expires_at: Instant,
}
#[derive(Debug, Clone)]
pub(super) enum EntryState {
Processing {
lease: IdempotencyLease,
reserved_response_bytes: usize,
},
Completed(StoredIdempotencyResponse),
}
#[derive(Clone)]
#[non_exhaustive]
pub struct MemoryIdempotencyStore {
pub(super) state: Arc<Mutex<MemoryIdempotencyState>>,
clock: SharedClock,
max_records: usize,
max_stored_response_bytes: usize,
pub(super) max_response_bytes_per_record: usize,
}
#[derive(Debug, Default)]
pub(super) struct MemoryIdempotencyState {
pub(super) records: HashMap<IdempotencyKey, IdempotencyEntry>,
pub(super) stored_response_bytes: usize,
pub(super) reserved_response_bytes: usize,
}
impl MemoryIdempotencyStore {
#[must_use]
pub fn new() -> Self {
Self::with_clock(system_clock())
}
#[must_use]
pub fn with_clock(clock: SharedClock) -> Self {
Self {
state: Arc::new(Mutex::new(MemoryIdempotencyState::default())),
clock,
max_records: DEFAULT_MAX_IDEMPOTENCY_RECORDS,
max_stored_response_bytes: DEFAULT_MAX_IDEMPOTENCY_STORED_RESPONSE_BYTES,
max_response_bytes_per_record: DEFAULT_MAX_IDEMPOTENCY_STORED_RESPONSE_BYTES,
}
}
pub fn for_response_body_limit(
max_response_body_bytes: usize,
) -> Result<Self, IdempotencyStoreError> {
if max_response_body_bytes == 0 {
return Err(IdempotencyStoreError::InvalidCapacity);
}
let per_record_bytes = max_response_body_bytes
.checked_add(DEFAULT_MAX_IDEMPOTENCY_STORED_HEADER_BYTES)
.ok_or(IdempotencyStoreError::InvalidCapacity)?;
Self::with_clock_and_limits_and_reservation(
system_clock(),
DEFAULT_MAX_IDEMPOTENCY_RECORDS,
DEFAULT_MAX_IDEMPOTENCY_STORED_RESPONSE_BYTES,
per_record_bytes,
)
}
pub fn with_clock_and_max_records(
clock: SharedClock,
max_records: usize,
) -> Result<Self, IdempotencyStoreError> {
Self::with_clock_and_limits(
clock,
max_records,
DEFAULT_MAX_IDEMPOTENCY_STORED_RESPONSE_BYTES,
)
}
pub(super) fn with_clock_and_limits(
clock: SharedClock,
max_records: usize,
max_stored_response_bytes: usize,
) -> Result<Self, IdempotencyStoreError> {
Self::with_clock_and_limits_and_reservation(
clock,
max_records,
max_stored_response_bytes,
max_stored_response_bytes,
)
}
pub(super) fn with_clock_and_limits_and_reservation(
clock: SharedClock,
max_records: usize,
max_stored_response_bytes: usize,
max_response_bytes_per_record: usize,
) -> Result<Self, IdempotencyStoreError> {
if max_records == 0
|| max_stored_response_bytes == 0
|| max_response_bytes_per_record == 0
|| max_response_bytes_per_record > max_stored_response_bytes
{
return Err(IdempotencyStoreError::InvalidCapacity);
}
Ok(Self {
state: Arc::new(Mutex::new(MemoryIdempotencyState::default())),
clock,
max_records,
max_stored_response_bytes,
max_response_bytes_per_record,
})
}
#[must_use]
pub fn clock(&self) -> &SharedClock {
&self.clock
}
#[must_use]
pub const fn max_records(&self) -> usize {
self.max_records
}
#[must_use]
pub const fn max_stored_response_bytes(&self) -> usize {
self.max_stored_response_bytes
}
pub fn record_count(&self) -> Result<usize, IdempotencyStoreError> {
self.state
.lock()
.map(|state| state.records.len())
.map_err(|_| IdempotencyStoreError::LockPoisoned)
}
pub fn stored_response_bytes(&self) -> Result<usize, IdempotencyStoreError> {
self.state
.lock()
.map(|state| state.stored_response_bytes)
.map_err(|_| IdempotencyStoreError::LockPoisoned)
}
pub fn reserved_response_bytes(&self) -> Result<usize, IdempotencyStoreError> {
self.state
.lock()
.map(|state| state.reserved_response_bytes)
.map_err(|_| IdempotencyStoreError::LockPoisoned)
}
pub fn prune_expired(&self) -> Result<usize, IdempotencyStoreError> {
let mut state = self
.state
.lock()
.map_err(|_| IdempotencyStoreError::LockPoisoned)?;
let now = self.clock.now();
Ok(prune_expired_records(&mut state, now))
}
}
impl Default for MemoryIdempotencyStore {
fn default() -> Self {
Self::new()
}
}
impl fmt::Debug for MemoryIdempotencyStore {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
let state = self.state.lock().ok();
formatter
.debug_struct("MemoryIdempotencyStore")
.field(
"record_count",
&state.as_ref().map(|state| state.records.len()),
)
.field(
"stored_response_bytes",
&state.as_ref().map(|state| state.stored_response_bytes),
)
.field(
"reserved_response_bytes",
&state.as_ref().map(|state| state.reserved_response_bytes),
)
.field("max_records", &self.max_records)
.field("max_stored_response_bytes", &self.max_stored_response_bytes)
.field(
"max_response_bytes_per_record",
&self.max_response_bytes_per_record,
)
.finish_non_exhaustive()
}
}
#[async_trait]
impl IdempotencyStore for MemoryIdempotencyStore {
async fn reserve(
&self,
key: IdempotencyKey,
request_hash: IdempotencyRequestHash,
processing_ttl: Duration,
response_capacity_bytes: usize,
) -> Result<IdempotencyReservation, IdempotencyStoreError> {
if response_capacity_bytes == 0
|| response_capacity_bytes > self.max_response_bytes_per_record
{
return Err(IdempotencyStoreError::CapacityExceeded);
}
let mut state = self
.state
.lock()
.map_err(|_| IdempotencyStoreError::LockPoisoned)?;
let now = self.clock.now();
prune_expired_records(&mut state, now);
let expires_at = expiry_after(now, processing_ttl)?;
match state.records.get(&key) {
Some(record) if record.request_hash != request_hash => {
Ok(IdempotencyReservation::Conflict)
}
Some(record) => Ok(match &record.state {
EntryState::Processing { .. } => IdempotencyReservation::Processing,
EntryState::Completed(response) => IdempotencyReservation::Replay(response.clone()),
}),
None => {
if state.records.len() >= self.max_records {
return Err(IdempotencyStoreError::CapacityExceeded);
}
let allocated_bytes = state
.stored_response_bytes
.checked_add(state.reserved_response_bytes)
.and_then(|bytes| bytes.checked_add(response_capacity_bytes))
.ok_or(IdempotencyStoreError::CapacityExceeded)?;
if allocated_bytes > self.max_stored_response_bytes {
return Err(IdempotencyStoreError::CapacityExceeded);
}
state.reserved_response_bytes += response_capacity_bytes;
let lease = IdempotencyLease::new();
state.records.insert(
key,
IdempotencyEntry {
request_hash,
state: EntryState::Processing {
lease,
reserved_response_bytes: response_capacity_bytes,
},
expires_at,
},
);
Ok(IdempotencyReservation::Reserved(lease))
}
}
}
async fn commit(
&self,
key: &IdempotencyKey,
lease: IdempotencyLease,
response: StoredIdempotencyResponse,
retention_ttl: Duration,
) -> Result<(), IdempotencyStoreError> {
let mut state = self
.state
.lock()
.map_err(|_| IdempotencyStoreError::LockPoisoned)?;
let now = self.clock.now();
let expires_at = expiry_after(now, retention_ttl)?;
prune_expired_records(&mut state, now);
let MemoryIdempotencyState {
records,
stored_response_bytes,
reserved_response_bytes,
} = &mut *state;
let Some(record) = records.get_mut(key) else {
return Err(IdempotencyStoreError::InconsistentRecord);
};
let EntryState::Processing {
lease: current_lease,
reserved_response_bytes: reserved_bytes,
} = record.state
else {
return Err(IdempotencyStoreError::InconsistentRecord);
};
if current_lease != lease {
return Err(IdempotencyStoreError::InconsistentRecord);
}
let response_bytes = stored_response_size(&response);
if response_bytes > reserved_bytes {
return Err(IdempotencyStoreError::CapacityExceeded);
}
record.state = EntryState::Completed(response);
record.expires_at = expires_at;
*stored_response_bytes += response_bytes;
*reserved_response_bytes -= reserved_bytes;
Ok(())
}
async fn abort(
&self,
key: &IdempotencyKey,
lease: IdempotencyLease,
) -> Result<(), IdempotencyStoreError> {
let mut state = self
.state
.lock()
.map_err(|_| IdempotencyStoreError::LockPoisoned)?;
if let Some(IdempotencyEntry {
state:
EntryState::Processing {
lease: current_lease,
reserved_response_bytes,
},
..
}) = state.records.get(key)
&& *current_lease == lease
{
let released = *reserved_response_bytes;
state.records.remove(key);
state.reserved_response_bytes -= released;
}
Ok(())
}
}
fn expiry_after(now: Instant, ttl: Duration) -> Result<Instant, IdempotencyStoreError> {
if ttl.is_zero() {
return Err(IdempotencyStoreError::InvalidExpiry);
}
now.checked_add(ttl)
.ok_or(IdempotencyStoreError::InvalidExpiry)
}
fn prune_expired_records(state: &mut MemoryIdempotencyState, now: Instant) -> usize {
let before = state.records.len();
state.records.retain(|_, record| {
if record.expires_at > now {
return true;
}
match &record.state {
EntryState::Processing {
reserved_response_bytes,
..
} => {
state.reserved_response_bytes -= reserved_response_bytes;
}
EntryState::Completed(response) => {
state.stored_response_bytes -= stored_response_size(response);
}
}
false
});
before - state.records.len()
}
pub(super) fn stored_response_size(response: &StoredIdempotencyResponse) -> usize {
response.body.len()
+ response
.headers
.iter()
.map(|(name, value)| name.len().saturating_add(value.len()))
.sum::<usize>()
}
#[cfg(test)]
mod tests {
use std::sync::mpsc;
use axum::http::StatusCode;
use super::*;
use crate::clock::{Clock, ManualClock};
struct PausingClock {
clock: ManualClock,
pause: Mutex<Option<(mpsc::Sender<()>, mpsc::Receiver<()>)>>,
}
impl Clock for PausingClock {
fn now(&self) -> Instant {
let now = self.clock.now();
let pause = self.pause.lock().unwrap().take();
if let Some((sampled, resume)) = pause {
sampled.send(()).unwrap();
resume.recv().unwrap();
}
now
}
}
fn test_store() -> (MemoryIdempotencyStore, Arc<PausingClock>) {
let clock = Arc::new(PausingClock {
clock: ManualClock::new(),
pause: Mutex::new(None),
});
(MemoryIdempotencyStore::with_clock(clock.clone()), clock)
}
fn contend_after_clock_read<T: Send>(
store: &MemoryIdempotencyStore,
clock: &PausingClock,
elapsed: Duration,
operation: impl FnOnce() -> T + Send,
) -> (T, bool) {
let (sampled, sampled_rx) = mpsc::channel();
let (resume, resume_rx) = mpsc::channel();
*clock.pause.lock().unwrap() = Some((sampled, resume_rx));
std::thread::scope(|scope| {
let task = scope.spawn(operation);
sampled_rx.recv().unwrap();
let state = match store.state.try_lock() {
Ok(state) => Some(state),
Err(std::sync::TryLockError::WouldBlock) => None,
Err(error) => panic!("unexpected state lock error: {error}"),
};
let advanced = state.is_some();
if advanced {
clock.clock.advance(elapsed).unwrap();
}
resume.send(()).unwrap();
drop(state);
(task.join().unwrap(), advanced)
})
}
#[tokio::test]
async fn reservation_remains_live_after_waiting_for_state_lock() {
let (store, clock) = test_store();
let key = IdempotencyKey::new("reservation").unwrap();
let hash = IdempotencyRequestHash::new("hash").unwrap();
let ttl = Duration::from_secs(10);
let handle = tokio::runtime::Handle::current();
let (reservation, _) = contend_after_clock_read(&store, &clock, ttl, || {
handle.block_on(store.reserve(key.clone(), hash.clone(), ttl, 64))
});
assert!(matches!(
reservation.unwrap(),
IdempotencyReservation::Reserved(_)
));
assert_eq!(
store.reserve(key, hash, ttl, 64).await.unwrap(),
IdempotencyReservation::Processing,
"a newly granted reservation must not already be expired"
);
}
#[tokio::test]
async fn commit_cannot_revive_a_lease_expired_while_waiting_for_state_lock() {
let (store, clock) = test_store();
let key = IdempotencyKey::new("commit").unwrap();
let hash = IdempotencyRequestHash::new("hash").unwrap();
let ttl = Duration::from_secs(10);
let IdempotencyReservation::Reserved(lease) =
store.reserve(key.clone(), hash, ttl, 64).await.unwrap()
else {
panic!("reservation must succeed");
};
let handle = tokio::runtime::Handle::current();
let (result, expired) = contend_after_clock_read(&store, &clock, ttl, || {
handle.block_on(store.commit(
&key,
lease,
StoredIdempotencyResponse::new(StatusCode::OK, "ok"),
Duration::from_secs(60),
))
});
if expired {
assert!(matches!(
result,
Err(IdempotencyStoreError::InconsistentRecord)
));
assert_eq!(store.record_count().unwrap(), 0);
assert_eq!(store.reserved_response_bytes().unwrap(), 0);
} else {
result.unwrap();
assert_eq!(store.stored_response_bytes().unwrap(), 2);
}
}
#[tokio::test]
async fn committed_response_retains_its_ttl_after_waiting_for_state_lock() {
let (store, clock) = test_store();
let key = IdempotencyKey::new("retention").unwrap();
let hash = IdempotencyRequestHash::new("hash").unwrap();
let ttl = Duration::from_secs(60);
let IdempotencyReservation::Reserved(lease) = store
.reserve(key.clone(), hash.clone(), ttl, 64)
.await
.unwrap()
else {
panic!("reservation must succeed");
};
let handle = tokio::runtime::Handle::current();
let (result, _) = contend_after_clock_read(&store, &clock, Duration::from_secs(20), || {
handle.block_on(store.commit(
&key,
lease,
StoredIdempotencyResponse::new(StatusCode::OK, "ok"),
Duration::from_secs(10),
))
});
result.unwrap();
assert!(matches!(
store.reserve(key, hash, ttl, 64).await.unwrap(),
IdempotencyReservation::Replay(_)
));
}
#[tokio::test]
async fn pruning_observes_expiry_after_waiting_for_state_lock() {
let (store, clock) = test_store();
let ttl = Duration::from_secs(10);
store
.reserve(
IdempotencyKey::new("prune").unwrap(),
IdempotencyRequestHash::new("hash").unwrap(),
ttl,
64,
)
.await
.unwrap();
let (result, expired) =
contend_after_clock_read(&store, &clock, ttl, || store.prune_expired());
assert_eq!(result.unwrap(), usize::from(expired));
assert_eq!(store.record_count().unwrap(), usize::from(!expired));
}
}