Crate trypema

Expand description

§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

Structs§

AbsoluteLocalRateLimiter: Local, per-key rate limiter with a sliding time window.
AbsoluteRedisRateLimiter: A rate limiter backed by Redis.
HardLimitFactor: Multiplier used by strategies that apply a “hard” cutoff beyond the base rate limit.
LocalRateLimiterOptions: Configuration for local rate limiter implementations.
LocalRateLimiterProvider: A collection of local rate limiter implementations.
RateGroupSizeMs: Coalescing interval (in milliseconds) for grouping increments close in time.
RateLimit: Per-second rate limit for a key.
RateLimiter: Rate limiter entrypoint.
RateLimiterOptions: Top-level configuration for RateLimiter.
RedisKey: A validated newtype for Redis keys.
RedisRateLimiterOptions: Configuration for Redis rate limiter implementations.
RedisRateLimiterProvider: A rate limiter backed by Redis.
SuppressedLocalRateLimiter: Local strategy that can probabilistically suppress work while tracking both observed and accepted rates.
SuppressedRedisRateLimiter: A rate limiter backed by Redis.
WindowSizeSeconds: Sliding window size in seconds.

Enums§

RateLimitDecision: Result of a rate limit admission check.
TrypemaError: Error type for this crate.

Crate trypema

Crate trypema Copy item path

§Trypema Rate Limiter

§Name and Biblical Inspiration

§Overview

§Status

§Quick Start

§Core Concepts

§Configuration

§Decisions

§Local Strategies

§Absolute (rl.local().absolute())

§Suppressed (rl.local().suppressed())

§Semantics (Important)

§Practical Tuning

§Crate Layout

§Redis Provider (Experimental)

§Feature Flags

§Testing

§Roadmap

Structs§

Enums§

Crate trypema

§Absolute (`rl.local().absolute()`)

§Suppressed (`rl.local().suppressed()`)