use std::time::Duration;
use crate::clock::Clock;
use crate::types::Symbol;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct VenueBudget {
pub subscriptions_per_connection: usize,
pub max_connections: usize,
pub connect_interval: Duration,
pub connect_burst: u32,
pub rest_interval: Duration,
pub rest_burst: u32,
}
impl VenueBudget {
pub const fn conservative() -> Self {
VenueBudget {
subscriptions_per_connection: 10,
max_connections: 4,
connect_interval: Duration::from_secs(2),
connect_burst: 2,
rest_interval: Duration::from_secs(1),
rest_burst: 2,
}
}
pub fn capacity(&self) -> usize {
self.subscriptions_per_connection
.saturating_mul(self.max_connections)
}
}
impl Default for VenueBudget {
fn default() -> Self {
Self::conservative()
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum BudgetError {
OverCapacity {
requested: usize,
capacity: usize,
max_connections: usize,
},
Empty,
}
impl std::fmt::Display for BudgetError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
BudgetError::OverCapacity {
requested,
capacity,
max_connections,
} => write!(
f,
"{requested} symbols exceed this venue's budget of {capacity} \
({max_connections} connections); raise the budget deliberately \
rather than silently dropping symbols"
),
BudgetError::Empty => write!(f, "no symbols requested"),
}
}
}
impl std::error::Error for BudgetError {}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SubscriptionPlan {
pub connections: Vec<Vec<Symbol>>,
pub rationale: &'static str,
}
impl SubscriptionPlan {
pub fn connection_count(&self) -> usize {
self.connections.len()
}
pub fn symbol_count(&self) -> usize {
self.connections.iter().map(Vec::len).sum()
}
pub fn worst_case_blast_radius(&self, gap_is_connection_wide: bool) -> usize {
if gap_is_connection_wide {
self.connections.iter().map(Vec::len).max().unwrap_or(0)
} else {
1
}
}
}
pub fn plan(
symbols: &[Symbol],
budget: &VenueBudget,
spread: bool,
) -> Result<SubscriptionPlan, BudgetError> {
if symbols.is_empty() {
return Err(BudgetError::Empty);
}
let capacity = budget.capacity();
if symbols.len() > capacity {
return Err(BudgetError::OverCapacity {
requested: symbols.len(),
capacity,
max_connections: budget.max_connections,
});
}
let (buckets, rationale) = if spread {
let wanted = budget.max_connections.min(symbols.len()).max(1);
(
wanted,
"sequence numbers belong to the connection, so symbols are spread to \
limit how many a single gap invalidates",
)
} else {
let needed = symbols.len().div_ceil(budget.subscriptions_per_connection);
(
needed.max(1),
"sequence numbers are per symbol, so symbols are packed onto as few \
sockets as the budget allows",
)
};
let mut connections: Vec<Vec<Symbol>> = vec![Vec::new(); buckets];
for (i, symbol) in symbols.iter().enumerate() {
connections[i % buckets].push(symbol.clone());
}
connections.retain(|c| !c.is_empty());
debug_assert!(
connections
.iter()
.all(|c| c.len() <= budget.subscriptions_per_connection),
"planner produced a connection over the per-socket limit"
);
Ok(SubscriptionPlan {
connections,
rationale,
})
}
#[derive(Debug, Clone)]
pub struct RateLimiter {
capacity: f64,
tokens: f64,
per_second: f64,
last_nanos: Option<u64>,
}
impl RateLimiter {
pub fn new(interval: Duration, burst: u32) -> Self {
assert!(
!interval.is_zero(),
"a zero interval would make the limiter meaningless"
);
let per_second = 1.0 / interval.as_secs_f64();
let capacity = burst.max(1) as f64;
RateLimiter {
capacity,
tokens: capacity,
per_second,
last_nanos: None,
}
}
pub fn available(&self) -> f64 {
self.tokens
}
fn refill(&mut self, now_nanos: u64) {
if let Some(last) = self.last_nanos {
let elapsed = now_nanos.saturating_sub(last) as f64 / 1e9;
self.tokens = (self.tokens + elapsed * self.per_second).min(self.capacity);
}
self.last_nanos = Some(now_nanos);
}
pub fn acquire(&mut self, clock: &dyn Clock) -> Duration {
let now = clock.stamp().mono_nanos;
self.refill(now);
if self.tokens >= 1.0 {
self.tokens -= 1.0;
return Duration::ZERO;
}
let deficit = 1.0 - self.tokens;
let seconds = deficit / self.per_second;
self.tokens = 0.0;
Duration::from_secs_f64(seconds)
}
}
#[derive(Debug, Clone)]
pub struct VenueLimiter {
pub connects: RateLimiter,
pub rest: RateLimiter,
}
impl VenueLimiter {
pub fn new(budget: &VenueBudget) -> Self {
VenueLimiter {
connects: RateLimiter::new(budget.connect_interval, budget.connect_burst),
rest: RateLimiter::new(budget.rest_interval, budget.rest_burst),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::clock::ManualClock;
fn symbols(n: usize) -> Vec<Symbol> {
(0..n)
.map(|i| Symbol::new(&format!("A{i}"), "USD"))
.collect()
}
fn budget(per_conn: usize, conns: usize) -> VenueBudget {
VenueBudget {
subscriptions_per_connection: per_conn,
max_connections: conns,
..VenueBudget::conservative()
}
}
#[test]
fn packing_uses_as_few_sockets_as_possible() {
let packed = plan(&symbols(25), &budget(10, 8), false).unwrap();
assert_eq!(packed.connection_count(), 3);
assert_eq!(packed.symbol_count(), 25);
assert!(packed.connections.iter().all(|c| c.len() <= 10));
}
#[test]
fn spreading_uses_every_socket_the_budget_allows() {
let spread_plan = plan(&symbols(4), &budget(10, 8), true).unwrap();
assert_eq!(spread_plan.connection_count(), 4);
assert_eq!(spread_plan.worst_case_blast_radius(true), 1);
let packed = plan(&symbols(4), &budget(10, 8), false).unwrap();
assert_eq!(packed.connection_count(), 1);
assert_eq!(packed.worst_case_blast_radius(true), 4);
}
#[test]
fn spreading_still_respects_the_per_socket_limit() {
let laid_out = plan(&symbols(16), &budget(4, 8), true).unwrap();
assert!(
laid_out.connections.iter().all(|c| c.len() <= 4),
"{:?}",
laid_out
.connections
.iter()
.map(Vec::len)
.collect::<Vec<_>>()
);
assert_eq!(laid_out.symbol_count(), 16);
}
#[test]
fn every_symbol_appears_exactly_once_in_a_plan() {
for spread in [true, false] {
let all = symbols(23);
let laid_out = plan(&all, &budget(6, 8), spread).unwrap();
let mut flat: Vec<&Symbol> = laid_out.connections.iter().flatten().collect();
flat.sort();
flat.dedup();
assert_eq!(flat.len(), 23, "spread={spread}");
}
}
#[test]
fn exceeding_the_budget_is_an_error_not_a_silent_truncation() {
let err = plan(&symbols(50), &budget(10, 4), false).unwrap_err();
assert_eq!(
err,
BudgetError::OverCapacity {
requested: 50,
capacity: 40,
max_connections: 4
}
);
assert!(err.to_string().contains("rather than silently dropping"));
}
#[test]
fn an_empty_request_is_rejected() {
assert_eq!(plan(&[], &budget(10, 4), false), Err(BudgetError::Empty));
}
#[test]
fn a_full_bucket_lets_a_burst_through_then_makes_the_caller_wait() {
let clock = ManualClock::new(0, 0);
let mut limiter = RateLimiter::new(Duration::from_millis(500), 3);
for i in 0..3 {
assert_eq!(limiter.acquire(&clock), Duration::ZERO, "burst slot {i}");
}
let wait = limiter.acquire(&clock);
assert!(
(wait.as_secs_f64() - 0.5).abs() < 1e-6,
"expected ~0.5s, got {wait:?}"
);
}
#[test]
fn tokens_refill_as_the_clock_advances() {
let clock = ManualClock::new(0, 0);
let mut limiter = RateLimiter::new(Duration::from_millis(100), 2);
limiter.acquire(&clock);
limiter.acquire(&clock);
assert!(limiter.acquire(&clock) > Duration::ZERO);
clock.advance(1_000_000_000);
assert_eq!(limiter.acquire(&clock), Duration::ZERO);
assert!(
limiter.available() <= 2.0,
"refill must not exceed the burst capacity"
);
}
#[test]
fn a_limiter_is_deterministic_for_a_given_clock() {
let run = || {
let clock = ManualClock::new(0, 1_000_000);
let mut limiter = RateLimiter::new(Duration::from_millis(250), 2);
(0..6)
.map(|_| limiter.acquire(&clock))
.collect::<Vec<Duration>>()
};
assert_eq!(run(), run());
}
#[test]
fn capacity_is_the_product_of_the_two_limits() {
assert_eq!(budget(10, 4).capacity(), 40);
assert_eq!(VenueBudget::conservative().capacity(), 40);
}
}