# 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

| Field                 | Type                | Description                                                           | Typical Values      |
| --------------------- | ------------------- | --------------------------------------------------------------------- | ------------------- |
| `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:

| Field                | Type                | Description                                               |
| -------------------- | ------------------- | --------------------------------------------------------- |
| `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.
