Requirements for the Rate Limiter

Let's define what our rate limiter needs to do. Each requirement is specific enough to drive a design decision — a class, method, or data structure.

1. R1 — Allow or Reject Requests: The system shall expose a single operation allowRequest(clientId) that returns true if the request is within the rate limit and false if it should be throttled. This is the core contract — every algorithm implements this same interface.

2. R2 — Per-Client Rate Tracking: Each client (identified by a string ID) shall have its own independent rate limit state. Client A exhausting its limit must not affect Client B. This means per-client state isolation — not a single global counter.

3. R3 — Configurable Limits: The rate limit parameters shall be configurable per instance: maximum number of requests (maxRequests) and time window (windowSize). For example, "100 requests per 60 seconds" or "10 requests per 1 second".

4. R4 — Token Bucket Algorithm Support: The system shall support a Token Bucket algorithm where tokens refill at a steady rate and each request consumes one token. When the bucket is empty, requests are rejected. The bucket has a configurable capacity that determines the maximum burst size.

5. R5 — Sliding Window Algorithm Support: The system shall support a Sliding Window algorithm that tracks individual request timestamps and counts requests within a rolling time window. This avoids the boundary problem where a burst at the edge of two fixed windows allows double the intended rate.

6. R6 — Leaky Bucket Algorithm Support: The system shall support a Leaky Bucket algorithm that processes requests at a fixed outflow rate. Incoming requests are queued; if the queue is full, new requests are rejected. Unlike Token Bucket, Leaky Bucket produces a smooth, constant output rate.

7. R7 — Algorithm Interchangeability: The system shall allow swapping the rate limiting algorithm at runtime without modifying client code. The calling code uses the same allowRequest(clientId) method regardless of which algorithm is active.

8. R8 — Time-Based State Management: Token counts and window boundaries shall be updated based on elapsed time. The system shall use lazy evaluation (compute state on demand when allowRequest is called) rather than requiring background threads for basic operation.

9. R9 — Burst Handling: Token Bucket shall allow short bursts up to the bucket capacity. Leaky Bucket shall smooth bursts into a constant output rate. Sliding Window shall strictly enforce the count within the rolling window. The behavior during bursts is algorithm-specific and must be documented.

Beyond functionality, a rate limiter has strict performance and safety constraints:

1. NF1 — Thread Safety: allowRequest() must be safe to call from multiple threads simultaneously. A race condition could allow more requests through than the limit permits (a security vulnerability) or incorrectly reject legitimate requests (a reliability bug). Both are unacceptable.

2. NF2 — Low Latency: allowRequest() sits in the critical path of every API request. It must execute in O(1) time for Token Bucket and Leaky Bucket, and O(n) worst-case for Sliding Window (where n is the number of requests in the current window). No algorithm should block on I/O or expensive computation.

3. NF3 — Memory Efficiency: Per-client state must be bounded. Token Bucket uses O(1) per client (a counter and a timestamp). Sliding Window Log uses O(n) per client (storing timestamps). The system should document these trade-offs so operators can choose appropriately.

4. NF4 — Extensibility (Open/Closed Principle): Adding a new rate limiting algorithm (e.g., Fixed Window Counter, Sliding Window Counter hybrid) must not require modifying existing algorithm classes or the rate limiter interface. New algorithms are added by implementing the interface.

5. NF5 — Testability: Each algorithm must be testable in isolation with deterministic, controllable time sources. Tests should not rely on time.sleep() or real wall-clock time — inject a clock for deterministic testing.

In Scope:

• The RateLimiter interface and three concrete algorithm implementations
• Per-client state tracking with configurable limits
• Thread-safe allowRequest() for all three algorithms
• Lazy time-based state updates (no background threads required for basic operation)
• Strategy Pattern for algorithm interchangeability

Out of Scope:

• Distributed rate limiting — sharing state across multiple servers (would need Redis, Lua scripts, and consensus). This is a System Design concern, not LLD.
• HTTP middleware integration — mounting the limiter as Express/Flask/Spring middleware. We design the engine, not the web framework glue.
• Response headers — X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset. These are presentation-layer concerns.
• Persistent storage — surviving server restarts. Our state lives in memory.
• Client identification — we accept a string clientId. How that ID is extracted (API key, IP address, JWT claim) is the caller's responsibility.
• Dynamic configuration — changing limits without restart. Our limits are set at construction time.

Each requirement maps to specific classes in our upcoming design:

Requirement	Drives	Key Design Decision
R1 — allowRequest	RateLimiter interface	Single abstract method, returns boolean
R2 — Per-client state	ClientState / per-client maps in each algorithm	HashMap of clientId → state
R3 — Configurable limits	Constructor parameters on each algorithm	maxRequests, windowSize, bucketCapacity, refillRate
R4 — Token Bucket	TokenBucketLimiter class	Lazy refill on each call, O(1) per request
R5 — Sliding Window	SlidingWindowLimiter class	Deque of timestamps, O(n) cleanup per call
R6 — Leaky Bucket	LeakyBucketLimiter class	Queue + fixed drain rate, O(1) per request
R7 — Interchangeability	Strategy Pattern + RateLimiter interface	All algorithms behind one interface
R8 — Lazy time management	last_refill_time / window_start fields	Calculate elapsed time on each call
R9 — Burst behavior	Algorithm-specific	Token Bucket allows bursts; Leaky Bucket smooths them
NF1 — Thread safety	Locks in each algorithm	threading.Lock / ReentrantLock
NF4 — Extensibility	Open hierarchy	New algorithms implement RateLimiter
NF5 — Testability	Injectable time source	Pass time_provider function for deterministic tests

In a real interview, spend 3-5 minutes clarifying requirements before jumping into algorithms. Ask questions like:

• "Should the rate limiter support per-client limits or a single global limit?" → Per-client is more realistic
• "Do we need to handle bursts gracefully or enforce strict smoothing?" → This determines Token Bucket vs. Leaky Bucket
• "Is this single-process or distributed?" → Scoping to single-process is appropriate for LLD
• "Should allowRequest be O(1) or is O(n) acceptable?" → This influences algorithm choice
• "Do we need to support multiple algorithms simultaneously?" → Strategy Pattern makes this trivial

These questions demonstrate that you understand the problem space deeply — interviewers value the questions you ask as much as the design you produce.