Implement a Per-IP Sliding Window Rate Limiter

Problem Statement

Design and implement an in-memory, per-IP rate limiter using the sliding window log strategy. The rate limiter must ensure that no single IP address can exceed a specified number of requests (limit) within any rolling time duration (window_size in seconds).

You need to implement the SlidingWindowRateLimiter class with the following methods:

• __init__(self, limit: int, window_size: int): Initializes the rate limiter with the allowed request limit and the sliding window_size in seconds.
• allow_request(self, ip: str, timestamp: int) -> bool: Determines whether a request from the given ip at Unix timestamp timestamp (in seconds) should be accepted. If accepted, record the request and return True. If rejected, do not record the request and return False.

A request is allowed if the number of accepted requests from that IP in the half-open interval (timestamp - window_size, timestamp] is strictly less than limit.

Class Interface

class SlidingWindowRateLimiter:
    def __init__(self, limit: int, window_size: int):
        """
        Initialize rate limiter with capacity limit and window size in seconds.
        """
        pass

    def allow_request(self, ip: str, timestamp: int) -> bool:
        """
        Check and record if request from IP at timestamp should be allowed.
        """
        pass

Example

limiter = SlidingWindowRateLimiter(limit=3, window_size=10)

# All requests for IP "10.0.0.1"
limiter.allow_request("10.0.0.1", 1)   # -> True (count in (1-10, 1] is 1)
limiter.allow_request("10.0.0.1", 2)   # -> True (count in (2-10, 2] is 2)
limiter.allow_request("10.0.0.1", 5)   # -> True (count in (5-10, 5] is 3)
limiter.allow_request("10.0.0.1", 8)   # -> False (limit reached, 3 requests in (0, 8])
limiter.allow_request("10.0.0.1", 11)  # -> True (request at t=1 fell out of (1, 11]; count becomes 3)

# Independent IP
limiter.allow_request("10.0.0.2", 8)   # -> True (new IP, count is 1)

Constraints

• 1 = 0
• Within calls for a given IP, timestamp values are provided in non-decreasing order.
• Total calls to allow_request: up to 10^6.

Edge Cases

• Multiple requests occurring at the exact same second.
• Boundary condition: a timestamp occurring exactly at timestamp - window_size must be expired.
• Inactive IP addresses should not accumulate memory indefinitely if their entries become empty.