| Copyright | (c) 2025 Oleksandr Zhabenko |
|---|---|
| License | MIT |
| Maintainer | oleksandr.zhabenko@yahoo.com |
| Stability | stable |
| Portability | portable |
| Safe Haskell | None |
| Language | Haskell2010 |
Keter.RateLimiter.SlidingWindow
Contents
Description
This module provides an implementation of the Sliding Window Counter algorithm for rate limiting. It is implemented using STM primitives and integrates with the Keter.RateLimiter.Cache key structure.
A sliding window allows a fixed number of requests within a moving time interval (window). It tracks individual request timestamps and filters them to only keep those within the defined time window. This allows for fine-grained request control and smooth rate-limiting behavior.
Example usage
let getTimeNow = realToFrac <$> getPOSIXTime result <- allowRequest getTimeNow myMap "zone1" "user42" 60 100 when result (putStrLn "Request allowed")
This example checks whether "user42" from "zone1" can make a request,
allowing up to 100 requests in a 60-second window.
Sliding Window Rate Limiting
Arguments
| :: IO Double | Action to get current time as fractional seconds since epoch |
| -> TVar (Map Text [Double]) | STM map storing per-client timestamp lists |
| -> Text | Throttle name (logical grouping identifier) |
| -> Text | IP zone identifier for multi-tenant isolation |
| -> Text | User key (unique client identifier) |
| -> Int | Sliding window size in seconds (must be positive) |
| -> Int | Maximum allowed requests within the time window (must be positive) |
| -> IO Bool |
Check whether a request is allowed under the sliding window policy.
This function implements a time-based sliding window algorithm. Each client is associated with a list of timestamps representing past allowed requests. If the number of timestamps in the current time window exceeds the limit, the request is denied.
This version is thread-safe and uses STM to avoid race conditions under
concurrency. The timestamp list is updated atomically using focus.
Algorithm Steps
- Time Acquisition: Get current timestamp using provided time function
- Key Construction: Build composite cache key from throttle name, IP zone, and user key
- Atomic Update: Use STM Focus to atomically read, filter, and update timestamp list
- Window Filtering: Remove timestamps older than the sliding window
- Limit Check: Allow request if filtered list length is below limit
- State Update: Add current timestamp to list if request is allowed
Memory Management
The algorithm automatically cleans up old timestamps and removes empty entries from the map, ensuring efficient memory usage for long-running applications.
Examples
-- Basic API rate limiting: 100 requests per minute getTime <- realToFrac <$> getPOSIXTime allowed <- allowRequest (pure getTime) stmMapTVar "api" "zone1" "user123" 60 100 if allowed then processApiRequest else sendRateLimitError
-- High-frequency trading API: 1000 requests per second let getTimeIO = realToFrac <$> getPOSIXTime result <- allowRequest getTimeIO storage "hft" "premium" "trader456" 1 1000 when result $ executeTrade
-- Multi-tier rate limiting with different windows
let (windowSecs, maxReqs) = case userTier of
Premium -> (60, 1000) -- 1000 requests per minute
Standard -> (60, 100) -- 100 requests per minute
Free -> (3600, 50) -- 50 requests per hour
allowed <- allowRequest getTime storage "tiered" zone userId windowSecs maxReqs
Thread Safety: All operations are atomic via STM. Multiple threads can safely call this function concurrently for the same or different keys.
Performance: Time complexity is O(n) where n is the number of timestamps within the sliding window. Space complexity is O(k*n) where k is the number of active clients.