cexy 0.1.0-dev.16

Official Rust SDK for the CEXY.io exchange API (REST + WebSocket)
Documentation
//! Client-side rate limiter: a token bucket that adapts to the server's `X-RateLimit-*` headers.

use std::sync::{Arc, Mutex};
use std::time::{Duration, Instant, SystemTime, UNIX_EPOCH};

use reqwest::header::HeaderMap;

use crate::clock::Clock;
use crate::error::{MAX_SERVER_WAIT, header, server_secs};

/// A snapshot of the client-side rate limiter.
#[derive(Debug, Clone, PartialEq)]
pub struct RateLimitState {
    /// Current limit (it only ever adapts downwards).
    pub requests_per_minute: f64,
    /// Tokens available now.
    pub tokens: f64,
    /// Requests wait until this much time has passed (a 429 or an exhausted window).
    pub blocked_for: Duration,
}

/// Token bucket. It adapts downwards to `X-RateLimit-Limit`, `X-RateLimit-Remaining` and
/// `X-RateLimit-Reset` (seconds until the window resets), and to the Retry-After of a 429. It
/// never raises the configured limit.
pub(crate) struct RateLimiter {
    state: Mutex<Bucket>,
    clock: Arc<dyn Clock>,
}

struct Bucket {
    rpm: f64,
    /// The most tokens it holds (the burst): `rpm` for the request limiter, one second's worth
    /// for the order-actions budget.
    cap: f64,
    tokens: f64,
    last: Instant,
    blocked_until: Option<Instant>,
}

impl RateLimiter {
    pub(crate) fn new(rpm: u32, clock: Arc<dyn Clock>) -> Self {
        Self::with_cap(rpm as f64, rpm as f64, clock)
    }

    /// A budget of `per_second` tokens a second that holds at most one second's worth (the
    /// optional order-actions budget).
    pub(crate) fn per_second(per_second: f64, clock: Arc<dyn Clock>) -> Self {
        Self::with_cap(per_second * 60.0, per_second, clock)
    }

    fn with_cap(rpm: f64, cap: f64, clock: Arc<dyn Clock>) -> Self {
        let now = clock.now();
        RateLimiter {
            state: Mutex::new(Bucket {
                rpm,
                cap,
                tokens: cap,
                last: now,
                blocked_until: None,
            }),
            clock,
        }
    }

    pub(crate) fn state(&self) -> RateLimitState {
        let now = self.clock.now();
        let mut b = self.state.lock().unwrap();
        b.refill(now);
        RateLimitState {
            requests_per_minute: b.rpm,
            tokens: b.tokens,
            blocked_for: b
                .blocked_until
                .map(|u| u.saturating_duration_since(now))
                .unwrap_or_default(),
        }
    }

    /// Waits until a request may be sent, then takes `cost` tokens (a batch of N takes N). A
    /// cost above the bucket's size waits for a full bucket and leaves it in debt, so the calls
    /// after it wait for the rest.
    pub(crate) async fn acquire(&self, cost: u32) {
        let cost = cost as f64;
        loop {
            let wait = {
                let now = self.clock.now();
                let mut b = self.state.lock().unwrap();
                b.refill(now);
                let need = cost.min(b.cap);
                match b.blocked_until {
                    Some(u) if now < u => u - now,
                    // A nanosecond's worth of float error never makes a caller wait (a wait that
                    // rounds to zero would never refill a fake clock).
                    _ if b.tokens + 1e-9 >= need => {
                        b.tokens -= cost;
                        return;
                    }
                    _ => {
                        let per_token = 60.0 / b.rpm;
                        server_secs((need - b.tokens) * per_token)
                            .filter(|d| !d.is_zero())
                            .unwrap_or(Duration::from_millis(1))
                            .min(MAX_SERVER_WAIT)
                    }
                }
            };
            self.clock.sleep(wait).await;
        }
    }

    /// Adapts to the server's rate-limit headers.
    pub(crate) fn update(&self, headers: &HeaderMap) {
        let now = self.clock.now();
        let mut b = self.state.lock().unwrap();
        b.refill(now);
        // A limit below 1 a minute is not a real limit (and would stall the client): ignored.
        if let Some(limit) = num(headers, "x-ratelimit-limit")
            && limit >= 1.0
            && limit < b.rpm
        {
            b.rpm = limit;
            b.cap = b.cap.min(limit);
            b.tokens = b.tokens.min(limit);
        }
        let Some(remaining) = num(headers, "x-ratelimit-remaining") else {
            return;
        };
        if remaining >= 0.0 && remaining < b.tokens {
            b.tokens = remaining;
        }
        if remaining == 0.0 {
            let d = match num(headers, "x-ratelimit-reset") {
                Some(reset) => reset_duration(reset),
                None => server_secs(60.0 / b.rpm).unwrap_or(Duration::ZERO),
            };
            b.block(now, d);
        }
    }

    /// Blocks every request for `d` (a 429's Retry-After).
    pub(crate) fn block_for(&self, d: Duration) {
        let now = self.clock.now();
        self.state.lock().unwrap().block(now, d);
    }
}

/// The hold an `order_actions` 429 puts on placements only: reads and cancels are not held.
/// Capped at [`MAX_SERVER_WAIT`] like the limiter's own hold; a later, shorter hint never
/// shortens it.
pub(crate) struct PlacementHold {
    until: Mutex<Option<Instant>>,
    clock: Arc<dyn Clock>,
}

impl PlacementHold {
    pub(crate) fn new(clock: Arc<dyn Clock>) -> Self {
        PlacementHold {
            until: Mutex::new(None),
            clock,
        }
    }

    /// Holds placements for `d`.
    pub(crate) fn hold_for(&self, d: Duration) {
        if d.is_zero() {
            return;
        }
        let Some(until) = self.clock.now().checked_add(d.min(MAX_SERVER_WAIT)) else {
            return;
        };
        let mut u = self.until.lock().unwrap();
        if u.is_none_or(|cur| until > cur) {
            *u = Some(until);
        }
    }

    /// Waits until placements may be sent, checking again after each wait (a 429 during the
    /// wait may have extended the hold).
    pub(crate) async fn wait(&self) {
        loop {
            let wait = {
                let now = self.clock.now();
                match *self.until.lock().unwrap() {
                    Some(u) if now < u => u - now,
                    _ => return,
                }
            };
            self.clock.sleep(wait).await;
        }
    }

    /// When the latest hold ends (`None`: never held).
    #[cfg(test)]
    pub(crate) fn held_until(&self) -> Option<Instant> {
        *self.until.lock().unwrap()
    }
}

impl Bucket {
    fn refill(&mut self, now: Instant) {
        if now > self.last {
            let elapsed = (now - self.last).as_secs_f64() / 60.0;
            self.tokens = self.cap.min(self.tokens + elapsed * self.rpm);
            self.last = now;
        }
    }

    /// Blocks until `now + d`, with `d` capped at [`MAX_SERVER_WAIT`]: a server hint never
    /// stalls the client longer than that.
    fn block(&mut self, now: Instant, d: Duration) {
        if d.is_zero() {
            return;
        }
        let Some(until) = now.checked_add(d.min(MAX_SERVER_WAIT)) else {
            return;
        };
        if self.blocked_until.is_none_or(|u| until > u) {
            self.blocked_until = Some(until);
        }
    }
}

/// `X-RateLimit-Reset` is seconds until the window resets. Values that can only be epoch
/// timestamps (seconds or milliseconds) are tolerated.
fn reset_duration(reset: f64) -> Duration {
    let now_ms = SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .unwrap_or_default()
        .as_millis() as f64;
    let secs = if reset > 1e12 {
        (reset - now_ms) / 1000.0
    } else if reset > 1e9 {
        reset - now_ms / 1000.0
    } else {
        reset
    };
    server_secs(secs).unwrap_or(Duration::ZERO)
}

fn num(headers: &HeaderMap, name: &str) -> Option<f64> {
    header(headers, name)
        .and_then(|v| v.parse::<f64>().ok())
        .filter(|f| f.is_finite())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::clock::FakeClock;
    use reqwest::header::{HeaderName, HeaderValue};

    fn headers(pairs: &[(&str, &str)]) -> HeaderMap {
        let mut h = HeaderMap::new();
        for (k, v) in pairs {
            h.insert(
                HeaderName::from_bytes(k.as_bytes()).unwrap(),
                HeaderValue::from_str(v).unwrap(),
            );
        }
        h
    }

    #[tokio::test]
    async fn a_cost_above_the_bucket_leaves_a_debt() {
        let clock = FakeClock::default();
        let l = RateLimiter::per_second(3.0, Arc::new(clock.clone()));
        l.acquire(5).await; // a full bucket (3) is enough to start; 2 are owed
        assert!(clock.sleeps().is_empty());
        l.acquire(1).await; // 3 tokens at 3 a second
        assert_eq!(clock.sleeps(), vec![Duration::from_secs(1)]);
    }

    #[tokio::test]
    async fn fractional_rates_never_sleep_zero() {
        let clock = FakeClock::default();
        let l = RateLimiter::new(7, Arc::new(clock.clone()));
        for _ in 0..50 {
            l.acquire(3).await;
        }
        let sleeps = clock.sleeps();
        assert!(sleeps.len() < 60, "{}", sleeps.len());
        assert!(sleeps.iter().all(|d| !d.is_zero()));
    }

    #[tokio::test]
    async fn spends_tokens_then_waits() {
        let clock = FakeClock::default();
        let l = RateLimiter::new(60, Arc::new(clock.clone()));
        for _ in 0..60 {
            l.acquire(1).await;
        }
        assert!(clock.sleeps().is_empty());
        l.acquire(1).await;
        assert_eq!(clock.sleeps(), vec![Duration::from_secs(1)]);
    }

    #[tokio::test]
    async fn adapts_to_headers_and_reset_seconds() {
        let clock = FakeClock::default();
        let l = RateLimiter::new(300, Arc::new(clock.clone()));
        l.update(&headers(&[
            ("X-RateLimit-Limit", "120"),
            ("X-RateLimit-Remaining", "0"),
            ("X-RateLimit-Reset", "7"),
        ]));
        let s = l.state();
        assert_eq!(s.requests_per_minute, 120.0);
        assert_eq!(s.blocked_for, Duration::from_secs(7));
        l.acquire(1).await;
        assert_eq!(clock.sleeps()[0], Duration::from_secs(7));
    }

    #[tokio::test]
    async fn absurd_server_hints_never_panic_or_stall() {
        let clock = FakeClock::default();
        let l = RateLimiter::new(300, Arc::new(clock.clone()));
        for (limit, reset) in [("1e-300", "1e300"), ("0.0001", "9999999999"), ("1", "1e20")] {
            l.update(&headers(&[
                ("X-RateLimit-Limit", limit),
                ("X-RateLimit-Remaining", "0"),
                ("X-RateLimit-Reset", reset),
            ]));
        }
        l.block_for(Duration::MAX);
        assert!(l.state().blocked_for <= MAX_SERVER_WAIT);
        l.acquire(1).await;
        l.acquire(1).await;
        assert!(clock.sleeps().iter().all(|d| *d <= MAX_SERVER_WAIT));
    }

    #[tokio::test]
    async fn never_raises_the_limit() {
        let l = RateLimiter::new(100, Arc::new(FakeClock::default()));
        l.update(&headers(&[("X-RateLimit-Limit", "600")]));
        assert_eq!(l.state().requests_per_minute, 100.0);
    }
}