Enumeration of supported rate limiting algorithms.

Each algorithm represents a different approach to rate limiting with distinct characteristics, use cases, and performance profiles. The type is promoted to the kind level using DataKinds for compile-time algorithm verification.

Algorithm Characteristics Comparison

Algorithm      | Bursts | Precision | Memory    | Use Case
---------------|--------|-----------|-----------|-------------------------
FixedWindow    | Yes    | Low       | Minimal   | Simple API rate limiting
SlidingWindow  | Smooth | High      | Variable  | Precise traffic shaping
TokenBucket    | Yes    | Medium    | Fixed     | Bursty API with sustained limits
LeakyBucket    | No     | High      | Fixed     | Smooth streaming/bandwidth
TinyLRU        | NA    | NA       | Bounded   | General caching with eviction

Detailed Algorithm Descriptions

• FixedWindow: Divides time into fixed intervals, counts requests per interval
• SlidingWindow: Maintains precise timestamps, allows smooth rate distribution
• TokenBucket: Accumulates tokens over time, consumes tokens per request
• LeakyBucket: Continuous leak rate, requests fill the bucket
• TinyLRU: Least-Recently-Used cache with size bounds and TTL

Cache wrapper that combines an algorithm specification with a storage backend.

The cache type provides a unified interface while maintaining algorithm-specific behavior through the type system. It encapsulates both the algorithm logic and the underlying storage implementation.

Type Parameters

The store parameter represents the storage backend type (e.g., InMemoryStore, Redis, etc.) The algorithm is captured in the store type for type safety

Example Usage

-- Create a token bucket cache
tokenStore <- createInMemoryStore @'TokenBucket
let tokenCache = Cache TokenBucket tokenStore

-- Create a fixed window cache
counterStore <- createInMemoryStore @'FixedWindow
let counterCache = Cache FixedWindow counterStore

Typeclass abstracting cache storage backends with functional dependencies.

This typeclass provides a uniform interface for different storage implementations while allowing each backend to specify its supported value types. The functional dependency store -> v ensures that each store type uniquely determines its value type, providing additional type safety.

Design Principles

• Type Safety: Functional dependencies prevent type mismatches
• Flexibility: Support for different storage backends (memory, Redis, etc.)
• Performance: Allow backend-specific optimizations
• Consistency: Uniform interface across all implementations

Default Implementations

The typeclass provides sensible defaults for increment operations, but backends can override for performance optimizations:

-- Default increment: read, modify, write
incStore store prefix key expires = do
  mval <- readStore store prefix key
  let newVal = maybe 1 (+1) mval
  writeStore store prefix key newVal expires
  return newVal

Atomicity Guarantees

Implementations should provide atomicity guarantees appropriate for their backend:

• STM-based stores: Full ACID transactions
• Memory stores: Process-level atomicity
• Distributed stores: Network-level consistency

Algorithm-parameterized in-memory storage using GADTs.

This type uses GADTs (Generalized Algebraic Data Types) to provide compile-time guarantees that each algorithm uses appropriate storage structures. The phantom type parameter ensures that token bucket operations can't be used on sliding window stores, etc.

GADT Benefits

• Type Safety: Prevents algorithm/storage mismatches at compile time
• Performance: Specialized storage for each algorithm's needs
• Extensibility: Easy to add new algorithms with appropriate storage
• Documentation: Types serve as executable documentation

Storage Specialization

Each algorithm gets optimized storage:

• Counters: Simple key-value cache with TTL
• Timestamps: STM Map of timestamp lists
• Token Buckets: STM Map of worker entries with background threads
• Leaky Buckets: STM Map with continuous drain workers
• TinyLRU: Bounded LRU cache with automatic eviction

Memory Management

• Token and Leaky bucket stores include automatic purging
• TinyLRU provides bounded memory usage
• Counter stores use TTL-based expiration
• All stores support manual reset for cleanup

Typeclass for storage backends that support complete reset operations.

Provides a way to clear all data from a store, useful for testing, maintenance, and emergency reset scenarios. Implementations should ensure thread safety and atomic reset behavior.

Use Cases

• Testing: Clean state between test runs
• Maintenance: Clear corrupted or stale data
• Memory Management: Recover from memory pressure
• Configuration Changes: Reset after algorithm parameter changes

Example

-- Reset all rate limiting data
resetStore myTokenBucketStore

-- Reset entire cache
cacheReset myCache

Typeclass for creating algorithm-specific storage instances.

Uses type-level programming to ensure each algorithm gets appropriate storage. The phantom type parameter prevents creation of incompatible store types.

Type-Level Dispatch

-- Compiler ensures correct store type
tokenStore <- createStore @'TokenBucket    -- Creates TokenBucketStore
counterStore <- createStore @'FixedWindow  -- Creates CounterStore

-- This would be a compile error:
-- tokenStore <- createStore @'SlidingWindow  -- Type mismatch!

Automatic Services

Some storage types automatically start background services:

• Token/Leaky buckets: Auto-purge threads for inactive entries
• Counter stores: TTL-based expiration threads
• Timestamp stores: Manual cleanup required
• TinyLRU: Built-in eviction on size limits

Read from cache using the algorithm-prefixed key.

Automatically applies the appropriate key prefix based on the cache's algorithm, then delegates to the storage backend's read operation. This ensures consistent key namespacing across all cache operations.

Key Transformation

-- For a TokenBucket cache with key "user123":
-- Actual key used: "token_bucket:token_bucket:user123"
--                   ^^^^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^
--                   prefix       prefixed key

Type Safety

The return type is determined by the storage backend's CacheStore instance, ensuring you get the correct value type for the algorithm:

• FixedWindow: Maybe Int (counter values)
• TokenBucket: Maybe TokenBucketState (bucket state)
• SlidingWindow: Maybe [Double] (timestamp lists)

Example

-- Read token bucket state
maybeState <- readCache tokenCache "user456"
case maybeState of
  Nothing -> putStrLn "No bucket exists for user"
  Just state -> putStrLn $ "User has " ++ show (tokens state) ++ " tokens"

Write to cache using the algorithm-prefixed key.

Stores a value with automatic key prefixing and TTL handling. The value type must match what the storage backend expects for the cache's algorithm.

TTL Behavior

• Absolute TTL: Expiration time calculated from current time
• Background Cleanup: Most stores have automatic cleanup threads
• Precision: Uses monotonic clock for accurate timing
• Consistency: TTL behavior consistent across all algorithms

Example

-- Store token bucket state for 1 hour
let initialState = TokenBucketState 100 currentTime
writeCache tokenCache "new_user" initialState 3600

-- Store counter value for 5 minutes
writeCache counterCache "api_limit" (42 :: Int) 300

Delete a key from cache using the algorithm-prefixed key.

Removes an entry from the cache, including any associated resources (worker threads, background tasks, etc.). The operation is atomic and thread-safe.

Resource Cleanup

• Token/Leaky Buckets: Terminates associated worker threads
• Counters: Simple key removal
• Timestamps: Clears timestamp lists
• LRU: Updates LRU ordering and frees space

Example

-- Remove user's rate limiting state
deleteCache tokenCache "inactive_user"

-- Clear API key's counter
deleteCache counterCache "expired_api_key"

Increment a numeric cache value or initialise it if missing.

Provides atomic increment-or-initialize semantics essential for counter-based rate limiting. If the key doesn't exist, initializes to 1. If it exists, increments by 1. The operation is atomic even under high concurrency.

Atomicity Guarantees

• STM-based stores: Full transaction isolation
• Memory stores: Process-level atomicity
• Distributed stores: Backend-specific consistency

Error Handling

• Type Mismatch: Returns error if existing value isn't numeric
• Serialization: Handles JSON encoding/decoding failures gracefully
• Overflow: Behavior depends on numeric type (Int, Double, etc.)

Example

-- Increment API request counter
newCount <- incrementCache apiCache "requests_per_minute" 60
when (newCount > 1000) $ throwError "Rate limit exceeded"

-- Initialize or increment user action count
actionCount <- incrementCache userCache "daily_actions" 86400

Create a new cache with a given Algorithm and store.

This is the primary constructor for cache instances. It combines an algorithm specification with a storage backend to create a fully functional cache. The algorithm parameter is used for key prefixing and operation validation.

Design Rationale

• Separation of Concerns: Algorithm logic separate from storage implementation
• Flexibility: Same algorithm can use different storage backends
• Type Safety: Algorithm-store compatibility enforced by types
• Testability: Easy to mock storage for testing

Example

-- Create a token bucket cache with in-memory storage
store <- createInMemoryStore @'TokenBucket
let cache = newCache TokenBucket store

-- Later operations use the unified cache interface
writeCache cache "user123" initialState 3600
result <- readCache cache "user123"

Create a new in-memory store for a specific rate-limiting algorithm.

This function provides a convenient, type-safe way to create algorithm-specific storage. It uses TypeApplications to specify which algorithm's store to create, ensuring compile-time correctness.

Type Safety Example

-- These are all valid and type-safe:
tokenStore <- createInMemoryStore @'TokenBucket
counterStore <- createInMemoryStore @'FixedWindow
lruStore <- createInMemoryStore @'TinyLRU

-- This would be a compile error (typo):
-- badStore <- createInMemoryStore @'TokenBuckett  -- Not a valid algorithm

Background Services

Some algorithms automatically start background services:

• TokenBucket/LeakyBucket: Purge threads for cleanup (60s interval, 1h TTL)
• FixedWindow: TTL-based expiration threads
• SlidingWindow/TinyLRU: No automatic background services

Example Usage

import Data.Proxy

main = do
  -- Create stores for different algorithms
  tokenStore <- createInMemoryStore @'TokenBucket
  slidingStore <- createInMemoryStore @'SlidingWindow
  
  -- Use in cache creation
  let tokenCache = newCache TokenBucket tokenStore
  let slidingCache = newCache SlidingWindow slidingStore

Clear all entries in an in-memory store.

Provides a direct interface to the ResettableStore functionality. Useful when you need to reset storage without going through the cache wrapper.

Use Cases

• Testing: Clean slate between test cases
• Maintenance: Clear corrupted state
• Memory Management: Free up memory during low usage
• Reconfiguration: Reset before changing algorithm parameters

Thread Safety

The operation is atomic and thread-safe, but concurrent operations may see the reset at different times. Consider coordinating with other threads if precise timing is required.

Example

-- Direct store reset
clearInMemoryStore myTokenBucketStore

-- Conditional reset based on memory usage
when memoryPressure $ clearInMemoryStore store

Reset all entries in a cache.

Clears all data from the cache's storage backend. This is a convenience wrapper around clearInMemoryStore that works at the cache level rather than the storage level.

Behavior

• Complete Reset: All keys and values are removed
• Background Services: Worker threads and purge threads continue running
• Algorithm State: Any algorithm-specific state is cleared
• Immediate Effect: Reset is visible to all threads immediately

Example

-- Reset entire token bucket cache
cacheReset tokenBucketCache

-- Reset counter cache for new time period
cacheReset apiCounterCache

Map each algorithm to its unique cache key prefix.

Prefixes prevent key collisions between different algorithms and provide clear identification of cached data types. Each algorithm uses a distinct namespace within the same storage backend.

Prefix Usage Pattern

-- Fixed window counter for API key "abc123"
Key: "rate_limiter:api:abc123"

-- Token bucket state for user "user456"  
Key: "token_bucket:user:user456"

-- Sliding window timestamps for IP "192.168.1.1"
Key: "timestamps:ip:192.168.1.1"

Example

ghci> algorithmPrefix TokenBucket
"token_bucket"
ghci> algorithmPrefix FixedWindow  
"rate_limiter"

Compose a unique cache key from throttle name, algorithm, IP zone, and user identifier.

Creates hierarchical cache keys that prevent collisions and enable efficient organization of rate limiting data. The key format follows a consistent pattern across all algorithms.

Key Format

<algorithm>:<throttleName>:<ipZone>:<userKey>

Use Cases

• Multi-tenant Applications: Separate rate limits per tenant
• Geographic Zones: Different limits for different regions
• Service Tiers: Varied limits based on user subscription level
• API Versioning: Separate limits for different API versions

Benefits

• Collision Prevention: Hierarchical structure prevents key conflicts
• Query Efficiency: Pattern-based queries and cleanup
• Debugging: Clear key structure aids troubleshooting
• Monitoring: Easy to aggregate metrics by zone or user type

Example

-- Create key for API rate limiting
let key = makeCacheKey "api_limit" TokenBucket "us-east-1" "user123"
-- Result: "TokenBucket:api_limit:us-east-1:user123"

-- Create key for login attempts
let key = makeCacheKey "login_attempts" FixedWindow "global" "192.168.1.1"
-- Result: "FixedWindow:login_attempts:global:192.168.1.1"

Convert seconds to TimeSpec for use with Data.Cache.

Calculates an absolute future time by adding the specified duration to the current monotonic time. Used for setting TTL values in cache operations.

Monotonic Time Benefits

• Clock Adjustments: Unaffected by system clock changes
• Precision: Nanosecond resolution for accurate timing
• Performance: Fast system call with minimal overhead
• Reliability: Guaranteed monotonic progression

Example

-- Create 5-minute expiration time
expiryTime <- secondsToTimeSpec 300

-- Use with cache operations
C.insertSTM key value cache (Just expiryTime)

Start a background thread that periodically purges expired entries from a generic cache.

This function creates a self-regulating purge thread that maintains precise timing intervals regardless of purge operation duration. It uses monotonic clock measurements to ensure accurate scheduling even under system load.

Timing Algorithm

The purge cycle works as follows:

1. Start Timer: Record monotonic timestamp before purge
2. Purge Operation: Call purgeExpired on the cache
3. Calculate Remaining: Subtract elapsed time from target interval
4. Precise Sleep: Wait for exactly the remaining time
5. Repeat: Continue with next cycle

Timing Precision

The algorithm ensures that purge cycles happen at regular intervals:

Target Interval:    |----10s----|----10s----|----10s----|
Actual Timing:      |--9s purge-|1s wait|--8s purge--|2s wait|
Result:             Consistent 10-second intervals maintained

Performance Considerations

• Non-blocking: Returns immediately after starting background thread
• Self-correcting: Adapts sleep time based on actual purge duration
• Memory efficient: Only maintains minimal state for timing
• CPU friendly: Sleeps for majority of time between purges

Example Usage

import qualified Data.Cache as C
import Data.Text

-- Create cache with 30-minute TTL
cache <- C.newCache (Just $ C.minutes 30)

-- Purge expired entries every 5 minutes (300 seconds)
startAutoPurge cache 300

-- Cache now automatically maintains itself
-- Memory usage remains bounded regardless of request patterns

Thread Safety: Safe to call concurrently. Each call creates independent purge thread.

Resource Usage: Creates one background thread with minimal memory footprint.

Error Handling: Thread continues running even if individual purge operations fail.

Start a specialized purge thread for token bucket entries in an STM map.

This function provides a convenient wrapper around startCustomPurge specifically configured for TokenBucketEntry cleanup. It handles the complexities of extracting timestamps from token bucket state and properly cleaning up worker threads.

Token Bucket Specific Behavior

• Timestamp Extraction: Uses lastUpdate field from TokenBucketState
• Worker Cleanup: Attempts to acquire worker lock and terminate threads
• Resource Release: Removes entry from STM map and frees all resources

TTL Behavior

Token buckets are considered expired when:

currentTime - lastUpdateTime >= ttlSeconds

This means buckets are purged based on when they were last used for rate limiting, not when they were created. Active buckets are never purged regardless of age.

Example Scenarios

-- High-frequency API with 5-minute cleanup cycles
tokenBuckets <- StmMap.newIO
threadId <- startCustomPurgeTokenBucket tokenBuckets 300 3600  -- 5min interval, 1hr TTL

-- Low-frequency batch processing with daily cleanup  
batchBuckets <- StmMap.newIO
threadId <- startCustomPurgeTokenBucket batchBuckets 86400 604800  -- 1day interval, 1week TTL

Thread Management: Returns ThreadId for thread control (e.g., killThread).

Memory Impact: Prevents unbounded memory growth in applications with dynamic rate limiting keys.

Performance: O(n) scan of all buckets, but typically runs infrequently during low-traffic periods.

• stmMap - STM map containing token bucket entries keyed by identifier. Typically uses API keys, user IDs, or IP addresses as keys. Map is scanned atomically during each purge cycle.
• intervalSeconds - Purge interval in seconds. How often to scan for expired buckets. Balance between cleanup responsiveness and CPU usage. Recommended: 300-3600 seconds depending on traffic patterns.
• ttlSeconds - TTL (time-to-live) in seconds. Buckets unused for this duration are considered expired and eligible for removal. Should be much larger than typical request intervals. Recommended: 3600-86400 seconds.

Returns thread ID of the background purge thread. Can be used with killThread to stop purging.

Start a specialized purge thread for leaky bucket entries in an STM map.

Similar to startCustomPurgeTokenBucket but configured for LeakyBucketEntry cleanup. Handles the specific requirements of leaky bucket timestamp extraction and worker thread management.

Leaky Bucket Specific Behavior

• Timestamp Precision: Uses Double timestamp from LeakyBucketState for sub-second accuracy
• Continuous Time Model: Supports fractional timestamps for precise drain calculations
• Worker Cleanup: Terminates continuous drain worker threads properly

TTL Calculation

Leaky buckets are expired when:

currentTime - lastTime >= fromIntegral ttlSeconds

The lastTime field represents the most recent bucket level update, providing more precise expiration timing than integer-based systems.

Use Cases

• Streaming Applications: Rate limiting for continuous data flows
• Real-time APIs: Sub-second precision rate limiting
• Traffic Shaping: Network bandwidth management with smooth rates

Example Configuration

-- Real-time streaming with frequent cleanup
streamBuckets <- StmMap.newIO  
threadId <- startCustomPurgeLeakyBucket streamBuckets 60 900  -- 1min interval, 15min TTL

-- Network traffic shaping with moderate cleanup
trafficBuckets <- StmMap.newIO
threadId <- startCustomPurgeLeakyBucket trafficBuckets 600 7200  -- 10min interval, 2hr TTL

Precision: Sub-second timestamp accuracy for fine-grained rate control.

Cleanup Behavior: More aggressive cleanup suitable for high-frequency, short-lived connections.

• stmMap - STM map containing leaky bucket entries keyed by identifier. Keys typically represent connections, streams, or data flows. All entries are scanned atomically during purge operations.
• intervalSeconds - Purge interval in seconds. Frequency of expired entry cleanup. For high-frequency applications, shorter intervals (60-600s) provide more responsive cleanup.
• ttlSeconds - TTL in seconds. Buckets inactive for this duration are purged. Should account for typical connection/stream lifetime patterns. Shorter TTL (900-3600s) suitable for transient connections.

Returns thread ID for background purge thread management. Thread runs continuously until explicitly terminated.

Start a dedicated worker thread for processing token bucket requests.

The worker runs in an infinite loop, processing requests from the provided queue. Each request is handled atomically: the bucket state is read, tokens are refilled based on elapsed time, a token is consumed if available, and the new state is written back.

Worker Lifecycle

1. Startup: Worker thread is forked and signals readiness via TMVar
2. Processing Loop: Worker waits for requests, processes them atomically
3. Response: Results are sent back to clients via MVar

Token Refill Algorithm

Tokens are refilled using the formula:

newTokens = min capacity (currentTokens + refillRate * elapsedSeconds)

This ensures:

• Tokens are added proportionally to elapsed time
• Bucket capacity is never exceeded
• Sub-second precision for refill calculations

Atomic Request Processing

Each request is processed in a single STM transaction that:

1. Reads current bucket state (tokens, lastUpdate)
2. Calculates elapsed time since last update
3. Computes available tokens after refill
4. Attempts to consume one token if available
5. Updates bucket state with new token count and timestamp
6. Returns allow/deny decision

Error Handling

The worker is designed to be resilient:

• Time calculation errors are handled by using floor for integer conversion
• Negative elapsed time (clock adjustments) results in no refill
• Worker continues running even if individual requests fail

Examples

-- Create a bucket for API rate limiting: 1000 requests/hour = ~0.278 req/sec
let capacity = 100              -- Allow bursts up to 100 requests
    refillRate = 1000.0 / 3600.0 -- 1000 requests per hour

initialState <- newTVarIO $ TokenBucketState capacity now
requestQueue <- newTBroadcastTQueueIO  
readySignal <- newEmptyTMVarIO

startTokenBucketWorker initialState requestQueue capacity refillRate readySignal

Leaky bucket worker thread implementation.

Implements the continuous drain algorithm for leaky buckets. Processes requests from a queue and updates bucket state based on elapsed time and leak rate.

Algorithm Details

1. Drain Calculation: level' = max(0, level - elapsed * leakRate)
2. Request Processing: level'' = level' + requestSize (typically 1)
3. Capacity Check: allowed = level'' <= capacity
4. State Update: Apply leak even on denial for accurate timing

Example

-- Start worker for streaming rate limiter
startLeakyBucketWorker stateVar queue 100 2.0
-- Capacity: 100 requests, Leak rate: 2 requests/second

Helper function to create a TokenBucketEntry with proper TMVar initialization.

Creates a complete token bucket entry with all necessary components: state storage, request queue, and worker synchronization. This ensures proper initialization of all STM components.

Entry Components

• State TVar: Atomic storage for bucket state (tokens, last update)
• Request Queue: TQueue for client-worker communication
• Worker Lock: TMVar for coordinating worker thread lifecycle

Example

-- Create entry for new user bucket
now floor <$ getPOSIXTime
let initialState = TokenBucketState 100 now  -- 100 tokens, current time
entry <- createTokenBucketEntry initialState

-- Entry is ready for insertion into STM map
atomically $ StmMap.insert entry "user123" bucketMap

Helper function to create a LeakyBucketEntry with proper TMVar initialization.

Similar to createTokenBucketEntry but for leaky bucket algorithm. Creates all necessary STM components for leaky bucket operation with continuous drain semantics.

Entry Components

• State TVar: Atomic storage for bucket level and last update time
• Request Queue: TQueue using TMVar for STM-based responses
• Worker Lock: TMVar for worker thread coordination

Example

-- Create entry for streaming connection
now realToFrac <$ getPOSIXTime
let initialState = LeakyBucketState 0.0 now  -- Empty bucket, current time
entry <- createLeakyBucketEntry initialState

-- Entry ready for continuous drain processing
atomically $ StmMap.insert entry "stream123" bucketMap

Convert an Algorithm value to its canonical Text representation.

This function provides a standardized textual representation of rate limiting algorithms for serialization, logging, and configuration files. Each algorithm has exactly one canonical PascalCase representation matching the constructor names.

Output Format

FixedWindow    → FixedWindow
SlidingWindow  → SlidingWindow 
TokenBucket    → TokenBucket
LeakyBucket    → LeakyBucket
TinyLRU        → TinyLRU

Examples

-- Basic usage
algoToText TokenBucket  -- TokenBucket

-- Configuration serialization
data RateLimitConfig = RateLimitConfig
  { algorithm :: Text, limit :: Int, window :: Int }

config = RateLimitConfig (algoToText SlidingWindow) 1000 3600

-- Logging
logInfo $ "Using " <> algoToText currentAlgo <> " rate limiting"

This function is pure, thread-safe, and forms a reversible pair with parseAlgoText. Time complexity: O(1), Space complexity: O(1).

Parse a Text representation back into an Algorithm value.

Provides flexible parsing with case-insensitive matching and hyphenated format support. Returns an Aeson Parser for seamless JSON integration with rich error reporting.

Supported Formats

Algorithm      │ Accepted Inputs (case-insensitive)
──────────────┼───────────────────────────────────
FixedWindow   │ "fixedwindow", "fixed-window"
SlidingWindow │ "slidingwindow", "sliding-window"
TokenBucket   │ "tokenbucket", "token-bucket"
LeakyBucket   │ "leakybucket", "leaky-bucket"
TinyLRU       │ "tinylru", "tiny-lru"

Examples

-- JSON parsing
instance FromJSON RateLimitConfig where
  parseJSON = withObject RateLimitConfig $ \o ->
    RateLimitConfig $ (o .: "algorithm" >>= parseAlgoText)
                    * o .: "limit"

-- Configuration file (accepts flexible formats)
parseAlgoText "token-bucket"    -- Success TokenBucket
parseAlgoText "SLIDING-WINDOW"  -- Success SlidingWindow
parseAlgoText "invalid"         -- Error "Unknown algorithm: invalid"

Error Handling

Calls fail with descriptive error messages for invalid inputs. In aeson's Parser context, this provides rich error reporting with parsing context.

Round-trip Property

forall algo. parseAlgoText (algoToText algo) == Success algo

This function is pure, thread-safe, with O(1) time complexity after O(n) normalization.