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):

trypema = { version = "*", features = ["redis-tokio"] }

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):

trypema = { version = "*", default-features = false }

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

trypema 0.1.0-dev.7