Sliding Window Rate Limiter

Data Structures System Design Rate Limiter

Implement a sliding window rate limiter. In this problem, you need to design and implement a class (or module) named RateLimiter that enforces a maximum number of allowed events over a sliding time window for any given user. Your implementation must support the following operations:

  • recordEvent(userId, timestamp): Record that an event occurred for the given user at the specified timestamp (measured in seconds).

  • isAllowed(userId, timestamp): Return a boolean indicating whether an event for the given user at the specified timestamp can be allowed. An event is allowed if the total number of events recorded in the preceding sliding window of a configurable duration is less than a defined threshold.

Assume that all users share the same configuration with two parameters:

  • t: The size of the sliding window in seconds.
  • w: The maximum number of allowed events within any window of length t.

The sliding window should be defined such that, for an event occurring at time T, only events with timestamps in the range [T - t, T) are considered. Your solution should manage a high volume of events and queries efficiently, so choose your data structures wisely to handle insertion, deletion, and query operations.

Example Scenario:

Assume t = 60 seconds and w = 3. The following sequence of operations should behave as described:

  1. recordEvent("user1", 1)
  2. recordEvent("user1", 20)
  3. isAllowed("user1", 30) // Returns true (only 2 events in the past 60 seconds)
  4. recordEvent("user1", 40)
  5. isAllowed("user1", 50) // Returns false (3 events in the past 60 seconds)
  6. recordEvent("user1", 90)
  7. isAllowed("user1", 100) // Returns true (the event at time 1 is now outside the 60-second window)

Design and implement your solution in the programming language of your choice. Ensure that your code is well-structured and makes appropriate use of algorithms and data structures to achieve efficient time and space complexity.