use std::fmt;
use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
use std::time::{Duration, Instant};
use tokio::sync::watch;
use tracing::{debug, warn};
use crate::constants;
const NS_PER_SEC: u64 = 1_000_000_000;
const MIN_SLEEP: Duration = Duration::from_micros(1);
pub struct TokenBucket {
tokens_milli: AtomicU64,
capacity_milli: u64,
rate_milli_per_sec: AtomicU64,
last_refill_elapsed_ns: AtomicU64,
unlimited: AtomicBool,
anchor: Instant,
rate_changed: watch::Sender<u64>,
}
impl fmt::Debug for TokenBucket {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("TokenBucket")
.field("tokens_milli", &self.tokens_milli.load(Ordering::Relaxed))
.field("capacity_milli", &self.capacity_milli)
.field(
"rate_milli_per_sec",
&self.rate_milli_per_sec.load(Ordering::Relaxed),
)
.field("unlimited", &self.unlimited.load(Ordering::Relaxed))
.finish()
}
}
impl TokenBucket {
pub fn new(rate_bytes_per_sec: u64, burst_bytes: Option<u64>) -> Self {
let burst = burst_bytes.unwrap_or(constants::DEFAULT_BURST_BYTES as u64);
let anchor = Instant::now();
let (rate_changed, _) = watch::channel(0u64);
Self {
tokens_milli: AtomicU64::new(burst.saturating_mul(1000)),
capacity_milli: burst.saturating_mul(1000),
rate_milli_per_sec: AtomicU64::new(rate_bytes_per_sec.saturating_mul(1000)),
last_refill_elapsed_ns: AtomicU64::new(0),
unlimited: AtomicBool::new(false),
anchor,
rate_changed,
}
}
pub fn unlimited() -> Self {
Self::unlimited_with_burst(None)
}
pub(crate) fn unlimited_with_burst(burst_bytes: Option<u64>) -> Self {
let anchor = Instant::now();
let (rate_changed, _) = watch::channel(0u64);
let capacity_milli = burst_bytes
.unwrap_or(constants::DEFAULT_BURST_BYTES as u64)
.saturating_mul(1000);
Self {
tokens_milli: AtomicU64::new(capacity_milli),
capacity_milli,
rate_milli_per_sec: AtomicU64::new(u64::MAX / 4),
last_refill_elapsed_ns: AtomicU64::new(0),
unlimited: AtomicBool::new(true),
anchor,
rate_changed,
}
}
pub fn is_unlimited(&self) -> bool {
self.unlimited.load(Ordering::Relaxed)
}
pub fn rate(&self) -> f64 {
if self.unlimited.load(Ordering::Relaxed) {
f64::MAX
} else {
self.rate_milli_per_sec.load(Ordering::Relaxed) as f64 / 1000.0
}
}
pub fn available_tokens(&self) -> f64 {
if self.unlimited.load(Ordering::Relaxed) {
return f64::MAX;
}
self.refill();
self.tokens_milli.load(Ordering::Relaxed) as f64 / 1000.0
}
#[inline]
fn now_ns(&self) -> u64 {
Instant::now()
.saturating_duration_since(self.anchor)
.as_nanos() as u64
}
fn refill(&self) {
if self.unlimited.load(Ordering::Relaxed) {
return;
}
let now = self.now_ns();
let last = self.last_refill_elapsed_ns.load(Ordering::Relaxed);
if now <= last {
return;
}
let elapsed_ns = now - last;
let added_milli = ((elapsed_ns as u128)
* (self.rate_milli_per_sec.load(Ordering::Relaxed) as u128)
/ NS_PER_SEC as u128) as u64;
if added_milli == 0 {
return;
}
match self.last_refill_elapsed_ns.compare_exchange(
last,
now,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => {
loop {
let current = self.tokens_milli.load(Ordering::Relaxed);
let new = current.saturating_add(added_milli).min(self.capacity_milli);
match self.tokens_milli.compare_exchange_weak(
current,
new,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => break,
Err(_) => continue, }
}
}
Err(_) => {
}
}
}
pub async fn acquire(&self, bytes: u64) {
if self.unlimited.load(Ordering::Relaxed) {
return;
}
let needed_milli = bytes.saturating_mul(1000);
loop {
if self.unlimited.load(Ordering::Relaxed) {
return;
}
let mut rate_changes = self.rate_changed.subscribe();
self.refill();
let current = self.tokens_milli.load(Ordering::Relaxed);
if current >= needed_milli {
match self.tokens_milli.compare_exchange_weak(
current,
current - needed_milli,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => return,
Err(_) => continue, }
}
let deficit_milli = needed_milli - current;
let rate_milli = self.rate_milli_per_sec.load(Ordering::Relaxed);
if rate_milli == 0 {
warn!("TokenBucket::acquire with rate=0; treating as unlimited");
return;
}
let wait_ns =
((deficit_milli as u128) * NS_PER_SEC as u128 / rate_milli as u128) as u64;
let wait = Duration::from_nanos(wait_ns);
if wait < MIN_SLEEP {
std::hint::spin_loop();
continue;
}
debug!(
bytes = bytes,
deficit_milli = deficit_milli,
wait_ns = wait_ns,
"throttling: sleeping for token refill"
);
tokio::select! {
_ = tokio::time::sleep(wait) => {}
changed = rate_changes.changed() => {
if changed.is_ok() {
continue;
}
}
}
self.refill();
loop {
let cur = self.tokens_milli.load(Ordering::Relaxed);
let new = cur.saturating_sub(needed_milli);
match self.tokens_milli.compare_exchange_weak(
cur,
new,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => return,
Err(_) => continue,
}
}
}
}
pub(crate) fn time_until_acquire(&self, bytes: u64) -> Duration {
if self.unlimited.load(Ordering::Relaxed) {
return Duration::ZERO;
}
self.refill();
let needed_milli = bytes.saturating_mul(1000);
let current = self.tokens_milli.load(Ordering::Relaxed);
if current >= needed_milli {
return Duration::ZERO;
}
let rate_milli = self.rate_milli_per_sec.load(Ordering::Relaxed);
if rate_milli == 0 {
return Duration::ZERO;
}
let deficit_milli = needed_milli - current;
let wait_ns = (deficit_milli as u128)
.saturating_mul(NS_PER_SEC as u128)
.div_ceil(rate_milli as u128)
.min(u64::MAX as u128) as u64;
Duration::from_nanos(wait_ns.max(1))
}
pub(crate) fn subscribe_rate_changes(&self) -> watch::Receiver<u64> {
self.rate_changed.subscribe()
}
pub fn try_acquire(&self, bytes: u64) -> bool {
if self.unlimited.load(Ordering::Relaxed) {
return true;
}
self.refill();
let needed_milli = bytes.saturating_mul(1000);
loop {
let current = self.tokens_milli.load(Ordering::Relaxed);
if current < needed_milli {
return false;
}
match self.tokens_milli.compare_exchange_weak(
current,
current - needed_milli,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => return true,
Err(_) => continue,
}
}
}
pub fn refund(&self, bytes: u64) {
if self.unlimited.load(Ordering::Relaxed) {
return;
}
let refunded_milli = bytes.saturating_mul(1000);
let mut current = self.tokens_milli.load(Ordering::Relaxed);
loop {
let refunded = current
.saturating_add(refunded_milli)
.min(self.capacity_milli);
match self.tokens_milli.compare_exchange_weak(
current,
refunded,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => return,
Err(observed) => current = observed,
}
}
}
pub fn set_rate(&self, rate_bytes_per_sec: u64) {
self.rate_milli_per_sec
.store(rate_bytes_per_sec.saturating_mul(1000), Ordering::Relaxed);
self.rate_changed
.send_modify(|version| *version = version.wrapping_add(1));
}
pub fn set_unlimited(&self, unlimited: bool) {
self.unlimited.store(unlimited, Ordering::Relaxed);
self.rate_changed
.send_modify(|version| *version = version.wrapping_add(1));
}
}