Crate ratelimit_meter [−] [src]
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
There is currently one rate limiter implementation in this crate,
the Generic Cell Rate Algorithm. Use it by creating a builder from
the GCRA
struct:
use std::time::Duration; use ratelimit_meter::{Decider, GCRA, Decision}; let mut lim = GCRA::for_capacity(50).unwrap() // Allow 50 units of work .per(Duration::from_secs(1)) // We calculate per-second (this is the default). .cell_weight(1).unwrap() // Each cell is one unit of work "heavy". .build(); // 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.
Rate-limiting Algorithms
This crate implements two "serious" rate-limiting/traffic-shaping
algorithms:
GCRA
and a Leaky
Bucket. An
"unserious" implementation is provided also, the
Allower
, which returns
"Yes" to all rate-limiting queries.
Design and implementation of GCRA
The GCRA limits the rate of cells by determining when the "next" cell is expected to arrive; any cells that arrive before that time are classified as non-conforming; the methods for checking cells also return an expected arrival time for these cells, so that callers can choose to wait (adding jitter), or reject the cell.
Since using the GCRA results in a much smoother usage pattern, it appears to be very useful for "outgoing" traffic behaviors, e.g. throttling API call rates, or emails sent to a person in a period of time.
Unlike token or leaky bucket algorithms, the GCRA 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).
See the documentation of the GCRA type for more details on its implementation and on trade-offs that apply to it.
Design and implementation of the leaky bucket
In contrast to the GCRA, the leaky bucket algorithm does not place any constraints on the next cell's arrival time: Whenever there is capacity left in the bucket, it can be used. This means that the distribution of "yes" decisions from heavy usage on the leaky bucket rate-limiter will be clustered together. On average, the cell rates of both the GCRA and the leaky bucket will be the same, but in terms of observable behavior, the leaky bucket will appear to allow requests at a more predictable rate.
This kind of behavior is usually what people of online APIs expect these days, which makes the leaky bucket a very popular technique for rate-limiting on these kinds of services.
The leaky bucket algorithm implemented in this crate is fairly standard: It only updates the bucket fill gauge when a cell is checked, and supports checking "batches" of cells in a single call with no problems.
Thread-safe operation
None of the stateful implementations in this crate can be used
across threads by default. However, there is a wrapper struct
Threadsafe
, that wraps each
implementation's 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::{Decider, GCRA, Decision}; let mut lim = GCRA::for_capacity(50).unwrap() // Allow 50 units of work .per(Duration::from_secs(1)) // We calculate per-second (this is the default). .cell_weight(1).unwrap() // Each cell is one unit of work "heavy". .build_sync(); // Construct a threadsafe GCRA decider. assert_eq!(Decision::Yes, lim.check().unwrap());
Reexports
pub use errors::*; |
pub use self::algorithms::*; |
Modules
algorithms | |
errors | |
example_algorithms |
Enums
Decision |
A decision on a single cell from the metered rate-limiter. |
Traits
Decider |
The main decision trait. It allows checking a single cell against the rate-limiter, either at the current time instant, or at a given instant in time, both destructively. |
MultiDecider | |
TypedDecider |
A prerequisite for implementing any Decider trait. It provides the
associated type for |