Implement a rate limiter at scale

Problem: Scalable Rate Limiter

Design a rate limiter class that restricts the number of requests a user can make within a specified time window. You must implement the following interface:

class RateLimiter:
    def __init__(self, max_requests: int, window_seconds: int):
        """Initializes the limiter with a capacity and time window."""

    def is_allowed(self, user_id: str) -> bool:
        """Returns True if the request is allowed, False otherwise."""

Requirements

1. Sliding Window: Use a sliding window approach (or an approximation like a token bucket) to ensure requests are spread out correctly, rather than resetting at fixed intervals.
2. Concurrency: The implementation must be thread-safe for a single-node environment.
3. Scale: Describe how you would handle this in a distributed system where multiple application servers share the rate limit state for a single user.

Examples

• Example 1: max_requests = 2, window_seconds = 10
  • is_allowed("user1") -> True (Count: 1)
  • is_allowed("user1") -> True (Count: 2)
  • is_allowed("user1") -> False (Over capacity)
  • Wait 10 seconds -> is_allowed("user1") -> True

Constraints

• max_requests will be up to 10,000.
• window_seconds will be between 1 and 3600.
• The solution should have an O(1) time complexity per call on average.

Considerations

• How will you store timestamps for each user?
• How do you handle expired timestamps to keep memory usage low?