governor

To use a custom time source (e.g., for mocking time in tests or using a non-standard clock), you must implement two traits: Clock and Reference.

1. Clock: Defines the source of time. It requires an associated type Instant that implements Reference.
2. Reference: Represents a specific measurement of time. It requires implementing duration_since (for calculating elapsed time) and saturating_sub (for calculating a point in the past), as well as Add<Nanos>.

This allows governor to be independent of std and enables deterministic testing by controlling the passage of time.

# use std::ops::Add;
# use governor::clock::{Reference, Clock};
# use governor::nanos::Nanos;

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct MyInstant(u64);

// 1. Implement Add<Nanos> for your Instant type
impl Add<Nanos> for MyInstant {
    type Output = Self;

   fn add(self, other: Nanos) -> Self {
       Self(self.0 + other.as_u64())
    }
}

// 2. Implement Reference for your Instant type
impl Reference for MyInstant {
    fn duration_since(&self, earlier: Self) -> Nanos {
        self.0.checked_sub(earlier.0).unwrap_or(0).into()
    }

    fn saturating_sub(&self, duration: Nanos) -> Self {
        Self(self.0.checked_sub(duration.into()).unwrap_or(self.0))
    }
}

// 3. Implement Clock for your Clock type
struct MyCounter(u64);

impl Clock for MyCounter {
    type Instant = MyInstant;

    fn now(&self) -> Self::Instant {
        MyInstant(self.0)
    }
}

A Quota defines the rate-limiting parameters for a rate limiter. It is expressed by two values: the number of cells (the maximum burst size) and the replenishment interval (the time it takes to replenish a single cell).

Key Concepts

• Burst Size: The maximum number of cells that can be allowed through without replenishment. This is critical when using RateLimiter.check_n, as you cannot request more cells in a single call than the burst size allows.
• Replenishment: Cells are added back to the budget at a steady rate defined by the replenishment interval.

Construction Patterns

1. Fixed Intervals: Use per_second, per_minute, or per_hour. These methods set both the replenishment rate and the burst size to the same value (e.g., per_second(50) allows 50 cells per second and has a burst size of 50).
2. Custom Periods: Use with_period(duration) to define how long it takes to replenish a single cell. This defaults to a burst size of 1.
3. Adjusting Burst: Use .allow_burst(max_burst) to increase the capacity for simultaneous requests without changing the underlying replenishment rate.

Example: 50 cells per second with a burst of 50

use governor::Quota;
use nonzero_ext::nonzero;
use std::time::Duration;

let q = Quota::per_second(nonzero!(50u32));
assert_eq!(q.burst_size().get(), 50);
assert_eq!(q.replenish_interval(), Duration::from_millis(20));

Example: 2 cells per hour with a burst of 90

use governor::Quota;
use nonzero_ext::nonzero;
use std::time::Duration;

let q = Quota::per_hour(nonzero!(2u32)).allow_burst(nonzero!(90u32));
assert_eq!(q.replenish_interval(), Duration::from_secs(30 * 60));
assert_eq!(q.burst_size().get(), 90);
// Time to fully replenish the 90-cell burst:
assert_eq!(q.burst_size_replenished_in(), Duration::from_secs(60 * 60 * (90 / 2)));

The governor library uses two primary abstractions to regulate data flow: RateLimiter and StateStore.

• RateLimiter: The main structure that combines rate-limiting parameters (defined by a Quota) with a concrete StateStore and a Clock. It manages the logic of when requests should be allowed or denied.
• StateStore: An abstraction for where the rate-limiting state is persisted.

There are two fundamental patterns for state management:

1. Direct State (Global): Used for "global" rate limiting where there is only one state for the entire limiter (e.g., a process should never exceed $N$ tasks per day). In this mode, the StateStore::Key is effectively NotKeyed.
2. Keyed State (Per-entity): Used when you need one rate limit per unique key (e.g., an API budget per client API key). The StateStore uses a type parameter for the key to track state independently for each identifier.

To extend the library, you can implement the StateStore trait to provide custom storage (e.g., a distributed database) while using the existing RateLimiter logic.

Middleware allows you to customize the additional information returned when a rate-limiting decision is made. While middleware cannot override the decision itself (it remains either Ok or Err), it can override the value contained within that Result.

There are two primary ways to use middleware:

1. Use built-in middleware:
   • NoOpMiddleware: The cheapest option. Returns Ok(()) on success and Err(NotUntil) on failure.
   • StateInformationMiddleware: Returns Ok(StateSnapshot) on success and Err(NotUntil) on failure, providing details about the limiter's state.
2. Implement a custom middleware: By implementing the RateLimitingMiddleware trait, you can return custom types (like HTTP headers or counters) for both positive and negative outcomes.

Middleware is attached to a RateLimiter during construction using .with_middleware::<T>().

use governor::{RateLimiter, Quota, middleware::StateInformationMiddleware};
use nonzero_ext::nonzero;

let lim = RateLimiter::direct(Quota::per_hour(nonzero!(1_u32)))
    .with_middleware::<StateInformationMiddleware>();

Jitter is used to deviate from nominal wait times to prevent the 'thundering herd' problem, where multiple tasks wake up simultaneously and attempt to access a resource at the same time.

In governor, you can use the Jitter struct to manually add random delays to Duration or Instant objects. Additionally, asynchronous rate limiters like DirectRateLimiter provide methods such as until_ready_with_jitter to apply this automatically.

Note: Jitter functionality requires the jitter feature to be enabled in your Cargo.toml.

use governor::Jitter;
use std::time::Duration;

let reference = Duration::from_secs(24);
// Creates a jitter that adds between 1 and 2 seconds
let jitter = Jitter::new(Duration::from_secs(1), Duration::from_secs(1));
let result = jitter + reference;

assert!(result >= reference + Duration::from_secs(1));
assert!(result < reference + Duration::from_secs(2));

Keyed rate limiters apply a single set of rate-limiting parameters (like burst capacity) to multiple distinct keys (e.g., enforcing a per-API-key limit). You can construct them using several specialized methods depending on the desired backend storage:

• keyed(quota): Uses the DefaultKeyedStateStore (a mutex-wrapped HashMap or a DashMap depending on features).
• dashmap(quota): Uses a DashMap for concurrent access (requires std and dashmap features).
• hashmap(quota): Uses a std::collections::HashMap (requires std feature).
• hashmap_with_hasher(quota, hasher): Uses a std::collections::HashMap with a custom hasher.
• dashmap_with_hasher(quota, hasher): Uses a DashMap with a custom hasher (requires std and dashmap features).

// Example: Creating a keyed rate limiter with a default store
let quota = Quota::per_second(nonzero!(10_u32));
let limiter = RateLimiter::keyed(quota);