Distributed Rate Limiter

Distributed Rate Limiter

Problem Context

You are building a distributed API gateway system where multiple server instances share traffic load. To prevent abuse and ensure fair usage, you need to implement a sliding window rate limiter that works consistently across all instances.

Each gateway instance records API requests with a timestamp. Given a unified log of requests across all instances, determine which requests should be allowed or denied based on a global rate limit.

The rate limit rule is: a user can make at most maxRequests requests within any sliding window of windowSize seconds.

Input Format

You are given:

• requests: a list of [userId, timestamp] pairs representing API requests arriving in chronological order (timestamps in seconds, possibly from multiple gateway instances but merged and sorted).
• maxRequests: the maximum number of requests allowed per user within the time window.
• windowSize: the duration of the sliding window in seconds.

Output Format

Return a list of strings — "allowed" or "denied" — for each request in the same order.

Examples

Example 1:

requests = [["user1", 1], ["user1", 2], ["user1", 3], ["user1", 4]]
maxRequests = 3
windowSize = 3

Output: ["allowed", "allowed", "allowed", "denied"]

Explanation: For user1:

• t=1: window [1,3] → 1 request → allowed
• t=2: window [2,4]... actually sliding: window covers [max(1, 2-3+1)=1 .. 2] → 2 requests → allowed
• t=3: window covers timestamps in (0, 3] → 3 requests → allowed (hits limit)
• t=4: window covers timestamps in (1, 4] → still 3 requests from t=2,3,4 → denied

Example 2:

requests = [["user1", 1], ["user2", 1], ["user1", 2], ["user2", 5]]
maxRequests = 2
windowSize = 3

Output: ["allowed", "allowed", "allowed", "allowed"]

Explanation: Each user is tracked independently. Both users stay within limit in their respective windows.

Example 3:

requests = [["user1", 1], ["user1", 1], ["user1", 1]]
maxRequests = 2
windowSize = 5

Output: ["allowed", "allowed", "denied"]

Explanation: All three requests come at the same timestamp. The first two are allowed (up to maxRequests=2). The third is denied.

Approach Hints

• Use a hash map to maintain a queue/deque of accepted request timestamps per user.