Rate Limiter

Design a rate limiter that limits how many requests each client can make in a time window, with swappable algorithms. In LLD rounds the focus is on clean algorithm abstractions, correct time handling, and thread safety; distributed concerns usually come up as follow-ups.

Requirements

Functional

• allow(client_id) -> bool decides whether a request is permitted.
• Limits configurable per client or tier (e.g. free: 10 req/s, pro: 100 req/s) and per API (e.g. /login stricter).
• Support multiple algorithms: fixed window, sliding window log, sliding window counter, token bucket, leaky bucket.
• Return metadata for rejected requests: retry-after, remaining quota (for 429 headers).

Non-functional

• O(1) or close to it per decision; tiny memory per client.
• Thread-safe for concurrent requests.
• Clock injectable for testing.
• Low latency; never become the bottleneck.