Sliding Window API Rate Limiter

MediumPython

Problem

Meta wants to protect an internal API endpoint used by systems like TAO-backed services from bursts of traffic. Implement a per-user sliding window rate limiter that decides whether each request should be allowed.

Given a list of request events sorted by non-decreasing timestamp, determine for each event whether it is accepted under the rule: a user may make at most limit requests in any rolling interval of window_size seconds, inclusive of the current timestamp.

Formal Specification

Implement a function:

Input: requests: List[List[int]], where each element is [timestamp, user_id]
Input: limit: int
Input: window_size: int
Output: List[bool], where result[i] is True if requests[i] is allowed, otherwise False

A request at time t counts all previously accepted requests for the same user with timestamp >= t - window_size + 1 and <= t.

Constraints

1 <= len(requests) <= 2 * 10^5
1 <= limit <= 10^5
1 <= window_size <= 10^9
0 <= timestamp <= 10^9
1 <= user_id <= 10^9
requests is sorted by non-decreasing timestamp

Function Signature

def rate_limiter(requests, limit, window_size):

Formal Specification

Implement a function:

Input: requests: List[List[int]], where each element is [timestamp, user_id]
Input: limit: int
Input: window_size: int
Output: List[bool], where result[i] is True if requests[i] is allowed, otherwise False

A request at time t counts all previously accepted requests for the same user with timestamp >= t - window_size + 1 and <= t.