# Trypema Rate Limiter
## 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 is a Rust rate limiting library supporting both in-process and Redis-backed distributed enforcement. It emphasizes predictable behavior, low overhead, and flexible rate limiting strategies.
Documentation: <https://trypema.davidoyinbo.com>
Benchmarks and comparisons:
- Local provider: <https://trypema.davidoyinbo.com/benchmarks/benchmark-results/local-benchmark-comparison>
- Redis provider: <https://trypema.davidoyinbo.com/benchmarks/benchmark-results/redis-benchmark-comparison>
### Features
**Providers:**
- **Local provider** (`local`): In-process rate limiting with per-key state
- **Redis provider** (`redis`): Distributed rate limiting backed by Redis 6.2+
- **Hybrid provider** (`hybrid`): Redis-backed limiter with a local fast-path and periodic Redis sync
**Strategies:**
- **Absolute** (`absolute`): Deterministic sliding-window limiter with strict enforcement
- **Suppressed** (`suppressed`): Probabilistic strategy that can gracefully degrade under load
**Key capabilities:**
- Non-integer rate limits (e.g., `0.5` requests per second)
- Sliding time windows for smooth burst handling
- Bucket coalescing to reduce overhead
- Automatic cleanup of stale keys
- Best-effort rejection metadata for backoff hints
### Non-goals
This crate is **not** designed for:
- Strictly linearizable admission control under high concurrency
- Strong consistency guarantees in distributed scenarios
Rate limiting is best-effort: concurrent requests may temporarily overshoot limits.
## Quick Start
## Running Redis-backed Tests
The Redis and hybrid providers have integration tests that require a running Redis instance.
Set `REDIS_URL` to enable them.
Example (local Redis):
```bash
REDIS_URL=redis://127.0.0.1:6379/ cargo test --features redis-tokio
```
### Local Provider (In-Process)
Use the local provider for single-process rate limiting with no external dependencies:
```toml
[dependencies]
trypema = "1.0"
```
```rust,no_run
use std::sync::Arc;
use trypema::{
HardLimitFactor, RateGroupSizeMs, RateLimit, RateLimitDecision, RateLimiter, RateLimiterOptions,
SuppressionFactorCacheMs, WindowSizeSeconds,
};
use trypema::local::LocalRateLimiterOptions;
let window_size_seconds = WindowSizeSeconds::try_from(60).unwrap();
let rate_group_size_ms = RateGroupSizeMs::try_from(10).unwrap();
let hard_limit_factor = HardLimitFactor::default();
let suppression_factor_cache_ms = SuppressionFactorCacheMs::default();
let options = RateLimiterOptions {
local: LocalRateLimiterOptions {
window_size_seconds,
rate_group_size_ms,
hard_limit_factor,
suppression_factor_cache_ms,
},
};
let rl = Arc::new(RateLimiter::new(options));
// Optional: start background cleanup to remove stale keys
// Idempotent: calling this multiple times is a no-op once running.
rl.run_cleanup_loop();
// Rate limit a key to 5 requests per second
let key = "user_123";
let rate_limit = RateLimit::try_from(5.0).unwrap();
// Absolute strategy (deterministic sliding-window enforcement)
match rl.local().absolute().inc(key, &rate_limit, 1) {
RateLimitDecision::Allowed => {
// Request allowed, proceed
}
RateLimitDecision::Rejected { retry_after_ms, .. } => {
// Request rejected, back off for retry_after_ms
let _ = retry_after_ms;
}
RateLimitDecision::Suppressed { .. } => {
unreachable!("absolute strategy never returns Suppressed");
}
}
// Suppressed strategy (probabilistic suppression near/over the target rate)
// You can also query the current suppression factor (useful for metrics/debugging).
let sf = rl.local().suppressed().get_suppression_factor(key);
let _ = sf;
match rl.local().suppressed().inc(key, &rate_limit, 1) {
RateLimitDecision::Allowed => {
// Below capacity: request allowed, proceed
}
RateLimitDecision::Suppressed {
is_allowed: true,
suppression_factor,
} => {
// At capacity: suppression active, but this request was allowed
let _ = suppression_factor;
}
RateLimitDecision::Suppressed {
is_allowed: false,
suppression_factor,
} => {
// At capacity: this request was suppressed (do not proceed)
let _ = suppression_factor;
}
RateLimitDecision::Rejected { retry_after_ms, .. } => {
// Over hard limit: request rejected
let _ = retry_after_ms;
}
}
```
### Redis Provider (Distributed)
Use the Redis provider for distributed rate limiting across multiple processes/servers:
**Requirements:**
- Redis >= 6.2
- Tokio or Smol async runtime
```toml
[dependencies]
trypema = { version = "1.0", features = ["redis-tokio"] }
redis = { version = "1", default-features = false, features = ["aio", "tokio-comp", "connection-manager"] }
tokio = { version = "1", features = ["full"] }
```
```rust,no_run
use std::sync::Arc;
use trypema::{
HardLimitFactor, RateGroupSizeMs, RateLimit, RateLimitDecision, RateLimiter, RateLimiterOptions,
SuppressionFactorCacheMs, WindowSizeSeconds,
};
use trypema::hybrid::SyncIntervalMs;
use trypema::local::LocalRateLimiterOptions;
use trypema::redis::{RedisKey, RedisRateLimiterOptions};
#[tokio::main]
async fn main() -> Result<(), trypema::TrypemaError> {
// Create Redis connection manager
let client = redis::Client::open("redis://127.0.0.1:6379/").unwrap();
let connection_manager = client.get_connection_manager().await.unwrap();
let window_size_seconds = WindowSizeSeconds::try_from(60).unwrap();
let rate_group_size_ms = RateGroupSizeMs::try_from(10).unwrap();
let hard_limit_factor = HardLimitFactor::default();
let suppression_factor_cache_ms = SuppressionFactorCacheMs::default();
let sync_interval_ms = SyncIntervalMs::default();
let rl = Arc::new(RateLimiter::new(RateLimiterOptions {
local: LocalRateLimiterOptions {
window_size_seconds,
rate_group_size_ms,
hard_limit_factor,
suppression_factor_cache_ms,
},
redis: RedisRateLimiterOptions {
connection_manager,
prefix: None,
window_size_seconds,
rate_group_size_ms,
hard_limit_factor,
suppression_factor_cache_ms,
sync_interval_ms,
},
}));
rl.run_cleanup_loop();
let rate_limit = RateLimit::try_from(5.0).unwrap();
let key = RedisKey::try_from("user_123".to_string()).unwrap();
// Absolute strategy (deterministic sliding-window enforcement)
match rl.redis().absolute().inc(&key, &rate_limit, 1).await? {
RateLimitDecision::Allowed => {
// Request allowed, proceed
}
RateLimitDecision::Rejected { retry_after_ms, .. } => {
// Request rejected, back off for retry_after_ms
let _ = retry_after_ms;
}
RateLimitDecision::Suppressed { .. } => {
unreachable!("absolute strategy never returns Suppressed");
}
}
// Suppressed strategy (probabilistic suppression near/over the target rate)
// You can also query the current suppression factor (useful for metrics/debugging).
let sf = rl.redis().suppressed().get_suppression_factor(&key).await?;
let _ = sf;
match rl.redis().suppressed().inc(&key, &rate_limit, 1).await? {
RateLimitDecision::Allowed => {
// Below capacity: request allowed, proceed
}
RateLimitDecision::Suppressed {
is_allowed: true,
suppression_factor,
} => {
// At capacity: suppression active, but this request was allowed
let _ = suppression_factor;
}
RateLimitDecision::Suppressed {
is_allowed: false,
suppression_factor,
} => {
// At capacity: this request was suppressed (do not proceed)
let _ = suppression_factor;
}
RateLimitDecision::Rejected { retry_after_ms, .. } => {
// Over hard limit: request rejected
let _ = retry_after_ms;
}
}
Ok(())
}
```
### Hybrid Provider (Local Cache + Redis Sync)
The hybrid provider is a Redis-backed limiter that keeps a local fast-path and periodically
flushes to Redis. It uses `RedisRateLimiterOptions`.
```rust,no_run
use std::sync::Arc;
use trypema::{
HardLimitFactor, RateGroupSizeMs, RateLimit, RateLimiter, RateLimiterOptions,
SuppressionFactorCacheMs, WindowSizeSeconds,
};
use trypema::hybrid::SyncIntervalMs;
use trypema::local::LocalRateLimiterOptions;
use trypema::redis::{RedisKey, RedisRateLimiterOptions};
#[tokio::main]
async fn main() -> Result<(), trypema::TrypemaError> {
let client = redis::Client::open("redis://127.0.0.1:6379/").unwrap();
let connection_manager = client.get_connection_manager().await.unwrap();
let window_size_seconds = WindowSizeSeconds::try_from(60).unwrap();
let rate_group_size_ms = RateGroupSizeMs::try_from(10).unwrap();
let hard_limit_factor = HardLimitFactor::default();
let suppression_factor_cache_ms = SuppressionFactorCacheMs::default();
let sync_interval_ms = SyncIntervalMs::default();
let rl = Arc::new(RateLimiter::new(RateLimiterOptions {
local: LocalRateLimiterOptions {
window_size_seconds,
rate_group_size_ms,
hard_limit_factor,
suppression_factor_cache_ms,
},
redis: RedisRateLimiterOptions {
connection_manager,
prefix: None,
window_size_seconds,
rate_group_size_ms,
hard_limit_factor,
suppression_factor_cache_ms,
sync_interval_ms,
},
}));
let key = RedisKey::try_from("user_123".to_string())?;
let rate = RateLimit::try_from(10.0)?;
let _decision = rl.hybrid().absolute().inc(&key, &rate, 1).await?;
// The hybrid provider also supports the suppressed strategy.
let _decision = rl.hybrid().suppressed().inc(&key, &rate, 1).await?;
Ok(())
}
```
## Core Concepts
### Keyed Limiting
Each key maintains independent rate limiting state.
- Local provider keys are arbitrary strings.
- Redis/hybrid provider keys use `RedisKey` (validated; see Redis Provider Details).
### Rate Limits
Rate limits are expressed as **requests per second** using the `RateLimit` type, which wraps a positive `f64`. This allows non-integer limits like `5.5` requests/second.
The actual window capacity is computed as: `window_size_seconds × rate_limit`
**Example:** With a 60-second window and a rate limit of 5.0:
- Window capacity = 60 × 5.0 = 300 requests
### Sliding Windows
Admission decisions are based on activity within the last `window_size_seconds`. As time progresses, old buckets expire and new capacity becomes available.
Unlike fixed windows, sliding windows provide smoother rate limiting without boundary resets.
### Bucket Coalescing
To reduce memory and computational overhead, increments that occur within `rate_group_size_ms` of each other are merged into the same time bucket.
## Configuration
### LocalRateLimiterOptions
| `window_size_seconds` | `WindowSizeSeconds` | Length of the sliding window for admission decisions | 10-300 seconds |
| `rate_group_size_ms` | `RateGroupSizeMs` | Coalescing interval for grouping nearby increments | 10-100 milliseconds |
| `hard_limit_factor` | `HardLimitFactor` | Multiplier for hard cutoff in suppressed strategy (1.0 = no headroom) | 1.0-2.0 |
| `suppression_factor_cache_ms` | `SuppressionFactorCacheMs` | Cache duration for per-key suppression factor recomputation | 10-1000 milliseconds |
### RedisRateLimiterOptions
Additional fields for Redis provider:
| `connection_manager` | `ConnectionManager` | Redis connection manager from `redis` crate |
| `prefix` | `Option<RedisKey>` | Optional prefix for all Redis keys (default: `"trypema"`) |
| `suppression_factor_cache_ms` | `SuppressionFactorCacheMs` | Cache duration for per-key suppression factor recomputation |
| `sync_interval_ms` | `SyncIntervalMs` | Hybrid provider flush cadence for its local fast-path (Redis provider ignores) |
Plus the same `window_size_seconds`, `rate_group_size_ms`, and `hard_limit_factor` fields.
## Rate Limit Decisions
All strategies return a `RateLimitDecision` enum:
### `Allowed`
The request is allowed and the increment has been recorded.
```rust
use trypema::RateLimitDecision;
let decision = RateLimitDecision::Allowed;
```
### `Rejected`
The request exceeds the rate limit and should not proceed. The increment was **not** recorded.
```rust
use trypema::RateLimitDecision;
let decision = RateLimitDecision::Rejected {
window_size_seconds: 60,
retry_after_ms: 2500,
remaining_after_waiting: 45,
};
```
**Fields:**
- `window_size_seconds`: The configured sliding window size
- `retry_after_ms`: **Best-effort** estimate of milliseconds until capacity becomes available (based on oldest bucket's TTL)
- `remaining_after_waiting`: **Best-effort** estimate of window usage after waiting (may be `0` if heavily coalesced)
**Important:** These hints are approximate due to bucket coalescing and concurrent access. Use them for backoff guidance, not strict guarantees.
### `Suppressed`
Only returned by the suppressed strategy. Indicates probabilistic suppression is active.
```rust
use trypema::RateLimitDecision;
let decision = RateLimitDecision::Suppressed {
suppression_factor: 0.3,
is_allowed: true,
};
```
**Fields:**
- `suppression_factor`: Calculated suppression rate (0.0 = no suppression, 1.0 = full suppression)
- `is_allowed`: Whether this specific call was admitted (**use this as the admission signal**)
When `is_allowed: false`, the call was not admitted.
In both providers, the suppressed strategy tracks:
- `observed`: total calls seen for the key (always incremented)
- `declined`: calls denied by suppression (`is_allowed: false`)
From these, you can derive accepted usage as: `accepted = observed - declined`.
## Rate Limiting Strategies
### Absolute Strategy
**Access:** `rl.local().absolute()` or `rl.redis().absolute()`
A deterministic sliding-window limiter that strictly enforces rate limits.
**Behavior:**
- Window capacity = `window_size_seconds × rate_limit`
- Per-key limits are **sticky**: the first call for a key stores the rate limit; subsequent calls don't update it
- Requests exceeding the window capacity are immediately rejected
**Use cases:**
- Simple per-key rate caps
- Predictable, strict enforcement
- Single-process (local) or multi-process (Redis) deployments
**Concurrency note:** Best-effort under concurrent load. Multiple threads/processes may temporarily overshoot limits as admission checks and increments are not atomic across calls.
### Suppressed Strategy
**Access:** `rl.local().suppressed()` or `rl.redis().suppressed()`
A probabilistic strategy that gracefully degrades under load by suppressing a portion of requests.
**Semantics:**
- A call returning `RateLimitDecision::Suppressed { is_allowed, .. }` always means "suppressed strategy active".
- Use `is_allowed` as the admission signal.
**Behavior:**
1. **Below capacity** (`observed_usage < window_capacity`):
- Suppression is bypassed, calls return `Allowed`
2. **At or above capacity (but below hard limit):**
- Suppression activates probabilistically based on current rate
- Returns `Suppressed { is_allowed: true/false }` to indicate suppression state
3. **At/above hard limit** (`observed_usage >= window_capacity × hard_limit_factor`):
- Local provider: returns `Suppressed { is_allowed: false, suppression_factor: 1.0 }`
- Redis provider: returns `Suppressed { is_allowed: false, suppression_factor: 1.0 }`
**Suppression calculation:**
```text
suppression_factor = 1.0 - (rate_limit / perceived_rate)
```
Where `perceived_rate = max(average_rate_in_window, rate_in_last_1000ms)`.
`rate_in_last_1000ms` is computed at millisecond granularity (not whole seconds), so suppression
responds more precisely to short spikes.
**Use cases:**
- Graceful degradation under load spikes
- Observability: distinguish between "hitting limit" and "over limit"
- Load shedding with visibility into suppression rates
**Inspiration:** Based on [Ably's distributed rate limiting approach](https://ably.com/blog/distributed-rate-limiting-scale-your-platform), which favors probabilistic suppression over hard cutoffs for better system behavior.
## Important Semantics & Limitations
### Eviction Granularity
**Local provider:** Uses `Instant::elapsed().as_millis()` for bucket expiration (millisecond granularity).
**Effect:** Buckets expire close to `window_size_seconds` (subject to ~1ms truncation and lazy eviction timing).
**Redis provider:** Bucket eviction uses Redis server time in milliseconds inside Lua scripts; additionally uses standard Redis TTL commands (`EXPIRE`, `SET` with `PX` option) for auxiliary keys.
### Memory Growth
Keys are **not automatically removed** from the internal map (local provider) or Redis (Redis provider) when they become inactive.
**Risk:** Unbounded or attacker-controlled key cardinality can lead to memory growth.
**Mitigation:** Use `run_cleanup_loop()` to periodically remove stale keys:
```rust,no_run
use std::sync::Arc;
use trypema::{HardLimitFactor, RateGroupSizeMs, RateLimiter, RateLimiterOptions, SuppressionFactorCacheMs, WindowSizeSeconds};
use trypema::local::LocalRateLimiterOptions;
let window_size_seconds = WindowSizeSeconds::try_from(60).unwrap();
let rate_group_size_ms = RateGroupSizeMs::try_from(10).unwrap();
let hard_limit_factor = HardLimitFactor::default();
let suppression_factor_cache_ms = SuppressionFactorCacheMs::default();
let options = RateLimiterOptions {
local: LocalRateLimiterOptions {
window_size_seconds,
rate_group_size_ms,
hard_limit_factor,
suppression_factor_cache_ms,
},
};
let rl = Arc::new(RateLimiter::new(options));
// Idempotent: calling this multiple times is a no-op once running.
rl.run_cleanup_loop();
// Optional: stop background cleanup
// Idempotent: safe to call multiple times.
rl.stop_cleanup_loop();
```
**Memory safety:** The cleanup loop holds only a `Weak<RateLimiter>` reference, so dropping all `Arc` references automatically stops cleanup.
## Tuning Guide
### `window_size_seconds`
**What it controls:** Length of the sliding window for rate limiting decisions.
**Trade-offs:**
- **Larger windows** (60-300s):
- ✅ Smooth out burst traffic
- ✅ More forgiving for intermittent usage patterns
- ❌ Slower recovery after hitting limits (old activity stays in window longer)
- ❌ Higher memory usage per key
- **Smaller windows** (5-30s):
- ✅ Faster recovery after hitting limits
- ✅ Lower memory usage
- ❌ Less burst tolerance
- ❌ More sensitive to temporary spikes
**Recommendation:** Start with 60 seconds for most use cases.
### `rate_group_size_ms`
**What it controls:** How aggressively increments are coalesced into buckets.
**Trade-offs:**
- **Larger coalescing** (50-100ms):
- ✅ Lower memory usage (fewer buckets)
- ✅ Better performance (fewer atomic operations)
- ❌ Coarser rejection metadata (`retry_after_ms` less accurate)
- **Smaller coalescing** (1-20ms):
- ✅ More accurate rejection metadata
- ✅ Finer-grained tracking
- ❌ Higher memory usage
- ❌ More overhead
**Recommendation:** Start with 10ms. Increase to 50-100ms if memory or performance becomes an issue.
### `hard_limit_factor`
**What it controls:** Hard cutoff multiplier for the suppressed strategy.
**Calculation:** `hard_limit = rate_limit × hard_limit_factor`
**Values:**
- `1.0`: No headroom; hard limit equals base limit (suppression less useful)
- `1.5-2.0`: **Recommended**; allows 50-100% burst above target rate before hard rejection
- `> 2.0`: Very permissive; large gap between target and hard limit
**Only relevant for:** Suppressed strategy. Ignored by absolute strategy.
## Project Structure
```text
src/
├── rate_limiter.rs # Top-level RateLimiter facade
├── common.rs # Shared types (RateLimitDecision, RateLimit, etc.)
├── error.rs # Error types
├── local/
│ ├── mod.rs
│ ├── local_rate_limiter_provider.rs
│ ├── absolute_local_rate_limiter.rs # Local absolute strategy
│ └── suppressed_local_rate_limiter.rs # Local suppressed strategy
├── hybrid/
│ ├── mod.rs
│ ├── common.rs
│ ├── hybrid_rate_limiter_provider.rs
│ └── absolute_hybrid_rate_limiter.rs # Hybrid absolute strategy (local fast-path + Redis sync)
└── redis/
├── mod.rs
├── redis_rate_limiter_provider.rs
├── absolute_redis_rate_limiter.rs # Redis absolute strategy (Lua scripts)
├── suppressed_redis_rate_limiter.rs # Redis suppressed strategy (Lua scripts)
└── common.rs # Redis-specific utilities
# (Rustdoc uses `docs/lib.md` for crate-level docs; this README is for GitHub/crates.io.)
```
## Redis Provider Details
This section applies to both the Redis provider and the hybrid provider.
### Requirements
- **Redis version:** >= 6.2.0
- **Async runtime:** Tokio or Smol
### Key Constraints
Redis keys use the `RedisKey` newtype with validation:
- **Must not be empty**
- **Must be ≤ 255 bytes**
- **Must not contain** `:` (used internally as a separator)
```rust,no_run
use trypema::redis::RedisKey;
// Valid
let _ = RedisKey::try_from("user_123".to_string()).unwrap();
let _ = RedisKey::try_from("api_v2_endpoint".to_string()).unwrap();
// Invalid
let _ = RedisKey::try_from("user:123".to_string());
let _ = RedisKey::try_from("".to_string());
```
### Feature Flags
Control Redis support at compile time:
```toml
# Default: local-only (no Redis)
trypema = { version = "1.0" }
# Enable Redis + hybrid provider with Tokio
trypema = { version = "1.0", features = ["redis-tokio"] }
# Enable Redis + hybrid provider with Smol
trypema = { version = "1.0", default-features = false, features = ["redis-smol"] }
```
## Roadmap
**Planned:**
- [ ] Comprehensive benchmarking suite
- [ ] Metrics and observability hooks
**Non-goals:**
- Strict linearizability (by design)
- Built-in retry logic (use case specific)
## Contributing
Feedback, issues, and PRs welcome. Please include tests for new features.
## License
MIT License. See the LICENSE file in the repository for details.