Sliding Windows & Buckets

Sliding time window

Trypema uses a sliding time window for admission decisions. At any point in time, the limiter considers all activity within the last window_size_seconds. As time advances, old buckets expire and new capacity becomes available continuously.

This avoids the boundary-reset problem of fixed windows. With a fixed window, a burst at the end of one window followed by a burst at the start of the next could allow 2x the intended rate. Sliding windows prevent this.

Example

With window_size_seconds = 60 and rate_limit = 10.0:

• At time T, the limiter looks at all requests from T-60s to T.
• If 599 requests have been recorded in that interval, the next request is allowed (capacity is 600).
• At time T+1s, the oldest 1 second of activity slides out of the window, freeing capacity.

WindowSizeSeconds

The window size is a validated newtype. It must be >= 1:

use trypema::WindowSizeSeconds;

let window = WindowSizeSeconds::try_from(60).unwrap();
assert_eq!(*window, 60);

// Invalid: must be >= 1
assert!(WindowSizeSeconds::try_from(0).is_err());

Trade-offs

Recommendation: Start with 60 seconds for most use cases.

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 rather than tracked individually.

How it works

When inc() is called, the limiter checks the most recent bucket. If that bucket was created within rate_group_size_ms ago, the new increment is added to that bucket. Otherwise, a new bucket is created.

Example with rate_group_size_ms = 10:

• 50 requests arriving within 10ms produce 1 bucket with count = 50.
• 50 requests spread over 100ms produce roughly 10 buckets with count ~ 5 each.

RateGroupSizeMs

The coalescing interval is a validated newtype. It must be >= 1:

use trypema::RateGroupSizeMs;

let coalescing = RateGroupSizeMs::try_from(10).unwrap();
assert_eq!(*coalescing, 10);

// Default is 100ms
let default_coalescing = RateGroupSizeMs::default();
assert_eq!(*default_coalescing, 100);

// Invalid: must be >= 1
assert!(RateGroupSizeMs::try_from(0).is_err());

Trade-offs

Recommendation: Start with 10ms. Increase to 50-100ms if memory or performance is an issue.

How eviction works

Local provider

The local provider uses Instant::elapsed().as_millis() for bucket expiration. Eviction is lazy: expired buckets are only removed when the key is next accessed (via inc() or is_allowed()). Between accesses, stale buckets remain in memory.

The cleanup loop periodically removes entire stale key entries (keys that have not been accessed for a configurable duration).

Redis provider

The Redis provider uses Redis server time in milliseconds inside Lua scripts for bucket eviction. Auxiliary keys (like the window limit) use standard Redis TTL commands (EXPIRE, SET ... PX).

Hybrid provider

The hybrid provider maintains local in-memory state that is periodically synced with Redis. Eviction follows the same patterns as the Redis provider during sync.

Next steps

• Decisions -- what Allowed, Rejected, and Suppressed mean
• Configuration & Tuning -- tune window size and coalescing