Thread-Safe Rate Limiter

Concurrency System Design Implementation

Build a thread-safe RateLimiter class that supports the following API:

  • isAllowed(userId): Returns a boolean indicating whether a request from the specified user is permitted based on the rate limiting rules.

The RateLimiter should enforce a policy where a user is allowed at most N requests within any sliding window of T seconds. If the user exceeds the allowed number of requests in the window, subsequent calls to isAllowed(userId) should return false until the window moves.

Requirements:

  1. Your implementation should be thread-safe, meaning it must correctly handle multiple concurrent threads or processes invoking isAllowed for the same or different users.

  2. Choose any programming language you prefer.

  3. Design for efficiency in terms of both time and memory, considering that the number of users can be very large.

  4. Clearly document any assumptions in your code comments, including specifics about the internal data structures or synchronization mechanisms used.

Example scenario:

Assume N = 5 and T = 60 seconds. A user can make up to 5 requests in any 60-second interval. The 6th request within that period should be rejected (i.e., isAllowed returns false). As time passes and older requests fall out of the sliding window, new requests should be accepted.

Implement the RateLimiter class and include tests or demonstration code to show that your solution works as expected under concurrent access.