Reason About Rate Limiting Under Memory and Throughput Pressure

Problem Statement

At high request volumes, maintaining an exact sliding-window rate limiter by storing individual request timestamps consumes O(R) memory (where R is the number of requests in the window). Under heavy load (e.g., 50,000 requests per second per client), this approach leads to prohibitive memory usage and severe garbage collection pressure.

Design an in-memory, bounded-memory rate limiter that supports sliding window semantics using a bucketed sliding window counter. Instead of storing raw timestamps, the limiter divides the time window into B fixed-size sub-buckets, bounding the memory footprint to O(B) per client key regardless of request volume.

Implement the SlidingWindowCounterLimiter class with the following methods:

class SlidingWindowCounterLimiter:
    def __init__(self, max_requests: int, window_seconds: int, bucket_count: int):
        """
        max_requests: Maximum allowed requests within any rolling window.
        window_seconds: Total duration of the rate limit window in seconds.
        bucket_count: Number of sub-buckets to slice the window into (controls precision).
        """
        pass

    def allow(self, key: str, current_time_ms: int) -> bool:
        """
        Determines whether a request with the given key at current_time_ms is permitted.
        If permitted, increments the count and returns True; otherwise, returns False.
        """
        pass

Approximation Logic

• The duration of each sub-bucket is bucket_duration_ms = (window_seconds * 1000) // bucket_count.
• Upon a request at current_time_ms, expire and clear any buckets older than window_seconds * 1000 ms from current_time_ms.
• Compute the total active requests across the valid buckets.
• If active_requests < max_requests, record the request in the bucket corresponding to current_time_ms and return True. Otherwise, return False.

Example

limiter = SlidingWindowCounterLimiter(max_requests=3, window_seconds=10, bucket_count=5)
# Each bucket represents (10 * 1000) / 5 = 2000 ms (2 seconds)

limiter.allow("client_a", 1000)  # True, bucket [0, 2000), total = 1
limiter.allow("client_a", 1500)  # True, bucket [0, 2000), total = 2
limiter.allow("client_a", 3000)  # True, bucket [2000, 4000), total = 3
limiter.allow("client_a", 3500)  # False, total = 3 (limit reached)
limiter.allow("client_a", 11500) # True, bucket [0, 2000) expired (> 10s old), total = 1 + 1 = 2 < 3

Constraints & Edge Cases

• 1 <= max_requests <= 10^9
• 1 <= window_seconds <= 3600
• 1 <= bucket_count <= 100
• Requests are generally monotonic in time per worker, but small out-of-order arrivals within clock skew tolerances (e.g., within the current bucket) must not crash the state.
• Consider memory reclamation: idle keys must not leak memory indefinitely.