Implement a rule-based rate limiter

Problem Statement

In reverse proxies and edge networks (such as Cloudflare), incoming HTTP requests are evaluated against a set of firewall and rate-limiting rules. Implement an in-memory, rule-based rate limiter that enforces sliding window rate limits across configurable URL path prefixes.

Implement the RateLimiter class with the following methods:

• add_rule(rule_id: str, path_prefix: str, limit: int, window_seconds: int) -> None: Registers a new rate-limiting rule. Any request whose path starts with path_prefix is subject to this rule. A client is permitted at most limit requests within any rolling interval of window_seconds.

• allow_request(timestamp: int, client_id: str, path: str) -> bool: Evaluates an incoming request from client_id for URL path at time timestamp (in seconds).

  • A request matches a rule if path.startswith(path_prefix).
  • A request may match zero, one, or multiple rules.
  • The request is allowed if and only if all matching rules have capacity for this client (i.e., the client has made strictly fewer than limit requests within the window (timestamp - window_seconds, timestamp] for every matched rule).
  • If the request is allowed, it consumes 1 quota unit under all matching rules for that client_id.
  • If the request is denied, it does not consume quota under any rule.
  • If no rules match the request, it is allowed by default.

Assume timestamps are provided in non-decreasing order across successive calls to allow_request.

Interface

class RateLimiter:
    def __init__(self):
        pass

    def add_rule(self, rule_id: str, path_prefix: str, limit: int, window_seconds: int) -> None:
        pass

    def allow_request(self, timestamp: int, client_id: str, path: str) -> bool:
        pass

Example

limiter = RateLimiter()
limiter.add_rule("api_general", "/api", limit=2, window_seconds=10)
limiter.add_rule("api_auth", "/api/auth", limit=1, window_seconds=5)

# t=1: matches both "api_general" and "api_auth"
limiter.allow_request(1, "client_1", "/api/auth/login")  # returns True

# t=2: matches both. "api_general" has 1/2, but "api_auth" has 1/1 (full)
limiter.allow_request(2, "client_1", "/api/auth/login")  # returns False (quota not consumed)

# t=3: matches only "api_general". Currently at 1/2
limiter.allow_request(3, "client_1", "/api/data")        # returns True (now at 2/2)

# t=7: matches both.
# "api_auth" window is (2, 7]: request at t=1 has expired (0/1 used).
# "api_general" window is (0, 7]: requests at t=1 and t=3 are active (2/2 used).
limiter.allow_request(7, "client_1", "/api/auth/login")  # returns False

Constraints

• Total calls to allow_request <= 100,000
• Total calls to add_rule <= 100
• 1 <= limit <= 10,000
• 1 <= window_seconds <= 86,400
• timestamp is a non-negative integer, monotonically non-decreasing
• Strings rule_id, client_id, path, and path_prefix are non-empty ASCII strings of length <= 100