Katkat
Back

Implement a Rolling-Window Rate Limiter

RobloxSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Implement an in-memory, rolling-window rate limiter supporting per-client limits, precise boundary expiration, and stale state cleanup.

Problem Statement

Implement an in-memory sliding-window log rate limiter. The rate limiter restricts the number of requests each client can make within a specified floating-point time window. Only accepted requests consume capacity; rejected requests must not be counted against the client's limit.

Implement the RollingWindowRateLimiter class with the following methods:

  • __init__(self, max_requests: int, window_size_seconds: float): Initializes the rate limiter with the maximum number of allowed requests and the window length in seconds.
  • allow_request(self, client_id: str, timestamp: float) -> bool: Checks if a request from client_id at timestamp is permitted. A previous request at t_prev is within the active window if timestamp - t_prev < window_size_seconds. If the number of active requests is strictly less than max_requests, the request is accepted, recorded, and returns True. Otherwise, it returns False without recording the timestamp.
  • cleanup_inactive(self, current_time: float) -> int: Evicts all tracked clients whose active request count is zero relative to current_time (i.e., all their past requests have expired). Returns the number of client records deleted from internal state.

Example

limiter = RollingWindowRateLimiter(max_requests=2, window_size_seconds=10.0)

# Client 1 makes requests
assert limiter.allow_request("user_1", 1.0) == True   # 1 active [1.0]
assert limiter.allow_request("user_1", 5.0) == True   # 2 active [1.0, 5.0]
assert limiter.allow_request("user_1", 8.0) == False  # Rejected; state remains [1.0, 5.0]

# At timestamp 11.0, 11.0 - 1.0 = 10.0 >= 10.0, so 1.0 expires
assert limiter.allow_request("user_1", 11.0) == True  # Active: [5.0, 11.0]

# Client 2 makes an independent request
assert limiter.allow_request("user_2", 12.0) == True  # Active: [12.0]

# Cleanup at timestamp 22.0
# For user_1: 22.0 - 11.0 = 11.0 >= 10.0 (all expired)
# For user_2: 22.0 - 12.0 = 10.0 >= 10.0 (all expired)
assert limiter.cleanup_inactive(22.0) == 2

Constraints

  • 1 = 0.0
  • Timestamps passed to allow_request for any given client_id are guaranteed to be monotonically non-decreasing.
  • client_id is a non-empty string.

Edge Cases

  • Exact Window Boundary: A request occurring at t_prev where timestamp - t_prev == window_size_seconds is considered expired.
  • Rejected Requests: Must never be stored; if rejected requests were appended, a client could DOS themselves indefinitely.
  • Zero-Active Clients: Clients that have expired entries should be lazily pruned during allow_request calls and eagerly removed during cleanup_inactive.

Hints

Hint 1

Use a hash map mapping each client ID to a double-ended queue (`collections.deque`) of accepted timestamps.

Hint 2

Before deciding whether to accept a new request, pop timestamps from the front of the client's deque that fall outside `timestamp - window_size_seconds`.

Hint 3

Ensure rejected requests are not added to the deque, and delete the client key during cleanup if their deque becomes empty after popping expired entries.

Follow-up questions

  • How would you ensure thread safety if `allow_request` is called concurrently across multiple worker threads in Python?
  • If scaling horizontally across multiple machines, how would you implement this rate limiter using Redis without race conditions?
  • Sliding window logs require storing every timestamp. How does a sliding window counter approximation trade off accuracy for memory?