# Trypema Rate Limiter
Status: in development (pre-release).
## Name and Biblical Inspiration
The name is inspired by the Koine Greek word "τρυπήματος" (trypematos, "hole/opening") from the phrase "διὰ τρυπήματος ῥαφίδος" ("through the eye of a needle") in the Bible: Matthew 19:24, Mark 10:25, Luke 18:25
## Overview
Trypema provides rate limiting primitives for both in-process use and Redis-backed (shared/distributed) enforcement, with a focus on predictable behavior and low overhead.
What you get today:
- A `RateLimiter` facade that exposes a `local` provider.
- A Redis-backed provider (`redis`) for shared/distributed rate limiting (experimental).
- A deterministic sliding-window strategy (`absolute`) and a suppression-capable strategy (`suppressed`).
What this crate is not (currently):
- A drop-in, strongly-consistent admission controller under high concurrency.
- A strict/linearizable admission controller under high concurrency.
## Status
- `local` provider: implemented
- `redis` provider: experimental (absolute implemented; suppressed placeholder)
## Quick Start
Default build (Redis enabled):
```toml
trypema = { version = "*", features = ["redis-tokio"] }
```
```rust,no_run
use trypema::{
HardLimitFactor, LocalRateLimiterOptions, RateGroupSizeMs, RateLimit, RateLimitDecision,
RateLimiter, RateLimiterOptions, RedisKey, RedisRateLimiterOptions, WindowSizeSeconds,
};
let rt = tokio::runtime::Runtime::new().unwrap();
rt.block_on(async {
let client = redis::Client::open("redis://127.0.0.1:6379/").unwrap();
let connection_manager = client.get_connection_manager().await.unwrap();
let rl = RateLimiter::new(RateLimiterOptions {
local: LocalRateLimiterOptions {
window_size_seconds: WindowSizeSeconds::try_from(60).unwrap(),
rate_group_size_ms: RateGroupSizeMs::try_from(10).unwrap(),
hard_limit_factor: HardLimitFactor::default(),
},
redis: RedisRateLimiterOptions {
connection_manager,
prefix: None,
window_size_seconds: WindowSizeSeconds::try_from(60).unwrap(),
rate_group_size_ms: RateGroupSizeMs::try_from(10).unwrap(),
},
});
let key = "user:123";
let rate_limit = RateLimit::try_from(5.0).unwrap();
// Local: check + record work
let _ = rl.local().absolute().inc(key, &rate_limit, 1);
// Redis: check + record work
// Note: Redis keys are validated and must not contain ':'
let redis_key = RedisKey::try_from("user_123".to_string()).unwrap();
let _ = rl.redis().absolute().inc(&redis_key, &rate_limit, 1).await.unwrap();
});
```
Local-only build (disable Redis features):
```toml
trypema = { version = "*", default-features = false }
```
```rust,ignore
use trypema::{
HardLimitFactor, LocalRateLimiterOptions, RateGroupSizeMs, RateLimit, RateLimitDecision,
RateLimiter, RateLimiterOptions, WindowSizeSeconds,
};
let rl = RateLimiter::new(RateLimiterOptions {
local: LocalRateLimiterOptions {
window_size_seconds: WindowSizeSeconds::try_from(60).unwrap(),
rate_group_size_ms: RateGroupSizeMs::try_from(10).unwrap(),
hard_limit_factor: HardLimitFactor::default(),
},
});
let key = "user:123";
let rate_limit = RateLimit::try_from(5.0).unwrap();
match rl.local().absolute().inc(key, &rate_limit, 1) {
RateLimitDecision::Allowed => {}
RateLimitDecision::Rejected { .. } => {}
RateLimitDecision::Suppressed { .. } => {}
}
```
## Core Concepts
- Keyed limiting: each `key` has independent state.
- `RateLimit`: per-second limit for a key (positive `f64`, so non-integer limits are allowed).
- Sliding window: admission is based on the last `window_size_seconds` of history.
- Bucket coalescing: increments close together can be merged into time buckets to reduce overhead.
## Configuration
`LocalRateLimiterOptions`:
- `window_size_seconds`: sliding window length used for admission.
- `rate_group_size_ms`: coalescing interval for increments close in time.
- `hard_limit_factor`: used by the suppressed strategy as a hard cutoff multiplier.
## Decisions
All strategies return `RateLimitDecision`:
- `Allowed`: proceed; the increment was applied.
- `Rejected { window_size_seconds, retry_after_ms, remaining_after_waiting }`:
do not proceed; includes best-effort backoff hints.
- `Suppressed { suppression_factor, is_allowed }`:
returned by suppression-based strategies; treat `is_allowed` as the admission decision.
Notes on metadata:
- `retry_after_ms` is computed from the oldest in-window bucket, so it is best-effort (especially with coalescing and concurrency).
- `remaining_after_waiting` is also best-effort; if usage is heavily coalesced into one bucket it can be `0`.
## Local Strategies
### Absolute (`rl.local().absolute()`)
Deterministic sliding-window limiter with per-key state stored in-process.
Behavior:
- Window capacity is approximately `W * R` (window seconds `W` times per-second limit `R`).
- Per-key limit is sticky: the first call for a key stores the `RateLimit`; later calls for that key do not update it.
Good for:
- simple per-key rate caps
- low overhead checks in a single process
### Suppressed (`rl.local().suppressed()`)
Strategy that can probabilistically deny work while tracking both:
- observed usage (all calls)
- accepted usage (only admitted calls)
This strategy can return `RateLimitDecision::Suppressed` to expose suppression metadata. It also enforces a hard cutoff:
- hard cutoff: `rate_limit * hard_limit_factor`
- hitting the hard cutoff returns `Rejected` (a hard rejection, not suppressible)
Suppression activation:
- Suppression is only considered once accepted usage meets/exceeds the base window capacity (`window_size_seconds * rate_limit`).
- Below that capacity, suppression is bypassed (calls return `Allowed`, subject to the hard cutoff).
Inspiration:
- The suppressed strategy is inspired by Ably's approach to distributed rate limiting, where they describe preferring suppression over a strict hard limit once the target rate is exceeded: <https://ably.com/blog/distributed-rate-limiting-scale-your-platform>
## Semantics (Important)
- Best-effort under concurrency: `inc` does an admission check and then applies the increment. Under high contention, several threads can observe `Allowed` and increment concurrently, so temporary overshoot is possible.
- Eviction granularity: eviction uses `Instant::elapsed().as_secs()` (whole-second truncation). This is conservative; e.g. a `1s` window can effectively require ~`2s` before a bucket is considered expired.
- Key cardinality: keys are not automatically removed from the internal map; unbounded/attacker-controlled keys can grow memory usage.
## Practical Tuning
- `window_size_seconds`:
larger windows smooth bursts but increase the amount of history affecting admission/unblocking.
- `rate_group_size_ms`:
larger values reduce overhead by coalescing increments into fewer buckets, but make rejection metadata coarser.
## Crate Layout
- `src/rate_limiter.rs`: `RateLimiter` facade and options
- `src/local/absolute_local_rate_limiter.rs`: absolute local implementation
- `src/local/suppressed_local_rate_limiter.rs`: suppression-capable local implementation
- `src/redis/absolute_redis_rate_limiter.rs`: absolute Redis implementation (Lua)
- `src/redis/redis_rate_limiter_provider.rs`: Redis provider facade and options
- `src/common.rs`: shared types (`RateLimitDecision`, newtypes, internal series)
## Redis Provider (Experimental)
- Requires Redis >= 7.4 due to hash-field TTL commands used by the Lua scripts.
- See `docs/redis.md` for key layout, semantics, and operational notes.
- Default Redis URL example: `redis://127.0.0.1:6379/`
### Feature Flags
- Default features enable Redis support via `redis-tokio`.
- Redis support is gated behind one of:
- `redis-tokio` (Tokio runtime)
- `redis-smol` (Smol runtime)
- Disable Redis support entirely with `--no-default-features`.
## Testing
- Local-only tests: `cargo test`
- Redis integration tests: `make test-redis`
- Override port: `REDIS_PORT=16379 make test-redis`
- Or point at your own Redis: `REDIS_URL=redis://127.0.0.1:6379 cargo test`
More details: `docs/testing.md`
## Roadmap
Planned directions (subject to change):
- additional providers (shared/distributed state)
- additional strategies and tighter semantics where needed