use std::{
collections::HashMap,
fmt,
hash::Hash,
sync::Mutex,
time::{Duration, Instant},
};
use async_trait::async_trait;
use super::model::{
DEFAULT_MAX_RATE_LIMIT_BUCKETS, RateLimitConfig, RateLimitDecision, RateLimitError,
};
#[derive(Debug, Clone)]
struct Bucket {
tokens: u32,
refill_at: Instant,
last_seen: Instant,
}
impl Bucket {
fn new(config: RateLimitConfig, now: Instant) -> Self {
Self {
tokens: config.capacity(),
refill_at: now,
last_seen: now,
}
}
fn decide(&mut self, config: RateLimitConfig, now: Instant) -> RateLimitDecision {
self.refill(config, now);
self.last_seen = now;
if self.tokens > 0 {
self.tokens -= 1;
RateLimitDecision::allowed(self.tokens)
} else {
let elapsed = now.saturating_duration_since(self.refill_at);
let retry_after = config.refill_interval().saturating_sub(elapsed);
RateLimitDecision::denied(retry_after)
}
}
fn refill(&mut self, config: RateLimitConfig, now: Instant) {
let elapsed = now.saturating_duration_since(self.refill_at);
let intervals = elapsed.as_nanos() / config.refill_interval().as_nanos();
if intervals == 0 {
return;
}
let refill = u32::try_from(intervals)
.unwrap_or(u32::MAX)
.saturating_mul(config.refill_tokens());
self.tokens = self.tokens.saturating_add(refill).min(config.capacity());
let refill_elapsed = multiply_duration(config.refill_interval(), intervals);
self.refill_at = self.refill_at.checked_add(refill_elapsed).unwrap_or(now);
}
fn would_be_fully_refilled(&self, config: RateLimitConfig, now: Instant) -> bool {
let elapsed = now.saturating_duration_since(self.refill_at);
let intervals = elapsed.as_nanos() / config.refill_interval().as_nanos();
let refill = u32::try_from(intervals)
.unwrap_or(u32::MAX)
.saturating_mul(config.refill_tokens());
self.tokens.saturating_add(refill) >= config.capacity()
}
}
#[non_exhaustive]
pub struct TokenBucketRateLimiter<K> {
config: RateLimitConfig,
max_buckets: usize,
state: Mutex<BucketState<K>>,
}
struct BucketState<K> {
buckets: HashMap<K, Bucket>,
overflow_bucket: Option<Bucket>,
last_capacity_prune: Option<Instant>,
}
impl<K> fmt::Debug for TokenBucketRateLimiter<K> {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
formatter
.debug_struct("TokenBucketRateLimiter")
.field("config", &self.config)
.field("max_buckets", &self.max_buckets)
.field(
"bucket_count",
&self.state.try_lock().ok().map(|state| state.buckets.len()),
)
.finish_non_exhaustive()
}
}
#[async_trait]
pub trait RateLimitStore: Send + Sync {
async fn check(
&self,
key: String,
config: RateLimitConfig,
now: Instant,
) -> Result<RateLimitDecision, RateLimitError>;
async fn prune_idle(&self, older_than: Instant) -> Result<usize, RateLimitError>;
}
#[derive(Debug)]
#[non_exhaustive]
pub struct MemoryRateLimitStore {
limiter: TokenBucketRateLimiter<String>,
}
impl MemoryRateLimitStore {
#[must_use]
pub fn new(config: RateLimitConfig) -> Self {
Self {
limiter: TokenBucketRateLimiter::new(config),
}
}
#[must_use]
pub const fn limiter(&self) -> &TokenBucketRateLimiter<String> {
&self.limiter
}
}
#[async_trait]
impl RateLimitStore for MemoryRateLimitStore {
async fn check(
&self,
key: String,
config: RateLimitConfig,
now: Instant,
) -> Result<RateLimitDecision, RateLimitError> {
self.limiter.check_at_with_config(key, config, now)
}
async fn prune_idle(&self, older_than: Instant) -> Result<usize, RateLimitError> {
self.limiter.prune_idle(older_than)
}
}
impl<K> TokenBucketRateLimiter<K>
where
K: Eq + Hash + Clone,
{
#[must_use]
pub fn new(config: RateLimitConfig) -> Self {
Self {
config,
max_buckets: DEFAULT_MAX_RATE_LIMIT_BUCKETS,
state: Mutex::new(BucketState {
buckets: HashMap::new(),
overflow_bucket: None,
last_capacity_prune: None,
}),
}
}
pub fn with_max_buckets(
config: RateLimitConfig,
max_buckets: usize,
) -> Result<Self, RateLimitError> {
if max_buckets == 0 {
return Err(RateLimitError::InvalidMaxBuckets);
}
Ok(Self {
config,
max_buckets,
state: Mutex::new(BucketState {
buckets: HashMap::new(),
overflow_bucket: None,
last_capacity_prune: None,
}),
})
}
#[must_use]
pub const fn config(&self) -> RateLimitConfig {
self.config
}
#[must_use]
pub const fn max_buckets(&self) -> usize {
self.max_buckets
}
pub fn bucket_count(&self) -> Result<usize, RateLimitError> {
self.state
.lock()
.map(|state| state.buckets.len())
.map_err(|_| RateLimitError::LockPoisoned)
}
pub fn check(&self, key: K) -> Result<RateLimitDecision, RateLimitError> {
self.check_at(key, Instant::now())
}
pub fn check_at(&self, key: K, now: Instant) -> Result<RateLimitDecision, RateLimitError> {
self.check_at_with_config(key, self.config, now)
}
pub fn check_at_with_config(
&self,
key: K,
config: RateLimitConfig,
now: Instant,
) -> Result<RateLimitDecision, RateLimitError> {
if config != self.config {
return Err(RateLimitError::ConfigMismatch);
}
let mut state = self
.state
.lock()
.map_err(|_| RateLimitError::LockPoisoned)?;
if !state.buckets.contains_key(&key) {
if state.buckets.len() >= self.max_buckets {
let should_prune = state.last_capacity_prune.is_none_or(|last_prune| {
now.saturating_duration_since(last_prune) >= config.refill_interval()
});
if should_prune {
state.last_capacity_prune = Some(now);
state
.buckets
.retain(|_, bucket| !bucket.would_be_fully_refilled(config, now));
}
if state.buckets.len() >= self.max_buckets {
return Ok(state
.overflow_bucket
.get_or_insert_with(|| Bucket::new(config, now))
.decide(config, now));
}
state.overflow_bucket = None;
}
state.buckets.insert(key.clone(), Bucket::new(config, now));
}
state
.buckets
.get_mut(&key)
.map(|bucket| bucket.decide(config, now))
.ok_or(RateLimitError::StoreUnavailable)
}
pub fn prune_idle(&self, older_than: Instant) -> Result<usize, RateLimitError> {
let mut state = self
.state
.lock()
.map_err(|_| RateLimitError::LockPoisoned)?;
let before = state.buckets.len();
state
.buckets
.retain(|_, bucket| bucket.last_seen >= older_than);
if state.buckets.len() < self.max_buckets {
state.overflow_bucket = None;
}
Ok(before - state.buckets.len())
}
}
fn multiply_duration(duration: Duration, multiplier: u128) -> Duration {
let nanos = duration.as_nanos().saturating_mul(multiplier);
Duration::from_nanos(u64::try_from(nanos).unwrap_or(u64::MAX))
}