Crate ratelimit_meter

Leaky Bucket Rate-Limiting (as a meter) in Rust

This crate implements the generic cell rate algorithm (GCRA) for rate-limiting and scheduling in Rust.

Interface

You construct a rate limiter using the Limiter builder:

use std::time::Duration;
use ratelimit_meter::{Limiter, Decider, GCRA, Decision};

let mut lim = Limiter::new()
    .time_unit(Duration::from_secs(1)) // We calculate per-second (this is the default).
    .capacity(50) // Allow 50 units of work per second
    .weight(1) // Each cell is one unit of work "heavy".
    .build::<GCRA>().unwrap(); // Construct a non-threadsafe GCRA decider.
assert_eq!(Decision::Yes, lim.check().unwrap());

The rate-limiter interface is intentionally geared towards only providing callers with the information they need to make decisions about what to do with each cell. Whenever possible, additional information about why a cell should be denied - the GCRA implementation will return a time::Instant alongside the decision to allow callers to e.g. provide better error messages to users.

Due to this, the ratelimit_meter crate does not provide any facility to wait until a cell would be allowed - if you require this, you should use the Instant returned with negative decisions and wait in your own, e.g. event loop.

Design and implementation

Unlike some other token bucket algorithms, the GCRA one assumes that all units of work are of the same "weight", and so allows some optimizations which result in much more consise and fast code (it does not even use multiplication or division in the "hot" path).

The trade-off here this is that there is currently no support for assigning different weights to incoming cells (say, particularly heavy api calls vs. lightweight ones) using the same rate-limiter structure.

Thread-safe operation

The default GCRA implementation can not be used across threads. However, there is a wrapper struct Threadsafe, that wraps the hot path in an atomically reference-counted mutex. It still manages to be pretty fast (see the benchmarks above), but the lock comes with an overhead even in single-threaded operation.

Example:

use std::time::Duration;
use ratelimit_meter::{Limiter, Decider, GCRA, Threadsafe, Decision};

let mut lim = Limiter::new()
    .time_unit(Duration::from_secs(1)) // We calculate per-second (this is the default).
    .capacity(50) // Allow 50 units of work per second
    .weight(1) // Each cell is one unit of work "heavy".
    .build::<Threadsafe<GCRA>>().unwrap(); // Construct a threadsafe GCRA decider.
assert_eq!(Decision::Yes, lim.check().unwrap());

Reexports

pub use errors::*;

Modules

errors
example_algorithms

Structs

GCRA	Implements the virtual scheduling description of the Generic Cell Rate Algorithm, attributed to ITU-T in recommendation I.371 Traffic control and congestion control in B-ISDN; from Wikipedia.
Limiter	A builder object that can be used to construct rate-limiters as meters.
Threadsafe	A wrapper that ensures operations in otherwise thread-unsafe rate-limiting decision algorithms are thread-safe. This is implemented by wrapping the actual Decider implementation in an atomically reference-counted mutex. It takes out a mutex whenever .test_and_update() is called.

Enums

Decision

A decision on a single cell from the metered rate-limiter.

Traits

Decider	The external interface offered by all rate-limiting implementations.
DeciderImpl	The trait that implementations of the metered rate-limiter interface have to implement. Users of this library should rely on Decider for the external interface.