use std::{
collections::HashMap,
fmt,
hash::Hash,
sync::Mutex,
time::{Duration, Instant},
};
use async_trait::async_trait;
use crate::clock::{SharedClock, system_clock};
use super::RateLimitStore;
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 = self.last_seen.max(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) -> u32 {
let elapsed = now.saturating_duration_since(self.refill_at);
let intervals = elapsed.as_nanos() / config.refill_interval().as_nanos();
if intervals == 0 {
return self.tokens;
}
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 remainder = elapsed.as_nanos() % config.refill_interval().as_nanos();
let remainder = Duration::new(
(remainder / 1_000_000_000) as u64,
(remainder % 1_000_000_000) as u32,
);
self.refill_at = now - remainder;
self.tokens
}
}
#[non_exhaustive]
pub struct TokenBucketRateLimiter<K> {
config: RateLimitConfig,
max_buckets: usize,
clock: SharedClock,
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]
impl RateLimitStore for TokenBucketRateLimiter<String> {
async fn check(
&self,
key: String,
config: RateLimitConfig,
) -> Result<RateLimitDecision, RateLimitError> {
self.check_with_time(key, config, None)
}
async fn prune_idle(&self, max_idle: Duration) -> Result<usize, RateLimitError> {
self.prune_idle(max_idle)
}
}
impl<K> TokenBucketRateLimiter<K>
where
K: Eq + Hash,
{
#[must_use]
pub fn new(config: RateLimitConfig) -> Self {
Self {
config,
max_buckets: DEFAULT_MAX_RATE_LIMIT_BUCKETS,
clock: system_clock(),
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 {
max_buckets,
..Self::new(config)
})
}
#[must_use]
pub fn with_clock(mut self, clock: SharedClock) -> Self {
self.clock = clock;
self
}
#[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_with_time(key, self.config, None)
}
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> {
self.check_with_time(key, config, Some(now))
}
fn check_with_time(
&self,
key: K,
config: RateLimitConfig,
now: Option<Instant>,
) -> Result<RateLimitDecision, RateLimitError> {
if config != self.config {
return Err(RateLimitError::ConfigMismatch);
}
let mut state = self
.state
.lock()
.map_err(|_| RateLimitError::LockPoisoned)?;
let now = now.unwrap_or_else(|| self.clock.now());
if let Some(bucket) = state.buckets.get_mut(&key) {
return Ok(bucket.decide(config, now));
}
let should_prune = state.buckets.len() >= self.max_buckets
&& 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.refill(config, now) < config.capacity());
}
if let Some(overflow) = &mut state.overflow_bucket
&& overflow.refill(config, now) < config.capacity()
{
return Ok(overflow.decide(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;
Ok(state
.buckets
.entry(key)
.or_insert_with(|| Bucket::new(config, now))
.decide(config, now))
}
pub fn prune_idle(&self, max_idle: Duration) -> Result<usize, RateLimitError> {
self.prune_idle_with_time(max_idle, None)
}
pub fn prune_idle_at(&self, max_idle: Duration, now: Instant) -> Result<usize, RateLimitError> {
self.prune_idle_with_time(max_idle, Some(now))
}
fn prune_idle_with_time(
&self,
max_idle: Duration,
now: Option<Instant>,
) -> Result<usize, RateLimitError> {
let mut state = self
.state
.lock()
.map_err(|_| RateLimitError::LockPoisoned)?;
let now = now.unwrap_or_else(|| self.clock.now());
let removable = |bucket: &mut Bucket| {
now.checked_duration_since(bucket.last_seen)
.is_some_and(|idle| idle >= max_idle)
&& bucket.refill(self.config, now) == self.config.capacity()
};
let before = state.buckets.len();
state.buckets.retain(|_, bucket| !removable(bucket));
if state.overflow_bucket.as_mut().is_some_and(removable) {
state.overflow_bucket = None;
}
Ok(before - state.buckets.len())
}
}