Design Rate Limiter

1. Requirements & Assumptions

Functional Requirements

• The rate limiter must limit requests based on client identifiers (e.g., Client IP or User ID).
• Allows configuring a maximum request limit per time window (e.g., 5 requests per second).
• Supports the Token Bucket algorithm to allow short traffic bursts while enforcing rate limits.
• Returns a boolean status indicating whether a request is allowed or blocked.

Non-Functional Requirements

• Low Latency: The rate limiter operates on the critical request path and must evaluate requests in microseconds.
• Thread Safety: Multiple concurrent requests from the same client must not bypass the rate limit due to race conditions.

Assumptions

• We will implement the rate limiter in memory for a single server instance.
• Refill tokens are calculated lazily during request evaluation to avoid background thread overhead.

2. Entities, Responsibilities & Relationships

• RateLimiter (Interface): Declares the allowRequest(clientId) method.
• TokenBucketRateLimiter: Implements the interface, maintaining a map of client IDs to their respective token buckets.
• TokenBucket: Tracks tokens, capacity, refill rate, and the last refill timestamp for a specific client.

3. Diagrams

UML Class Diagram

Sequence Diagram: Evaluating a Request

4. Design Decisions

• Lazy Refill Pattern: Instead of running a background thread for each client to add tokens every second, we calculate and add tokens lazily when a request arrives. This saves CPU and memory.
• Synchronized Token Modification: Token updates and consumption within the TokenBucket are synchronized to prevent race conditions from concurrent requests.

5. Step-by-Step Implementation

1. Create the RateLimiter interface.
2. Implement the TokenBucket class with lazy token calculations.
3. Implement the TokenBucketRateLimiter map container.
4. Use locking or synchronization blocks to ensure thread safety during token updates.

6. Complete Code

7. Test Cases & Verification

• Test Case 1: Simple Burst: Configure a capacity of 3. Send 3 rapid requests. Verify that all 3 are allowed.
• Test Case 2: Rate Limiting: Send a 4th request immediately after the first 3. Verify that the request is blocked.
• Test Case 3: Refill Recovery: Wait 1 second and send a 5th request. Verify that the request is allowed.

8. Scalability & SOLID Improvements

• SOLID - Dependency Inversion: The gateway relies on the RateLimiter interface, not the concrete TokenBucketRateLimiter class. This allows us to swap the token bucket algorithm for a Leaky Bucket or Sliding Window Log implementation without changing the gateway logic.
• Thread-Safe Segmented Map: We use ConcurrentHashMap to store client buckets. This allows requests from different clients (e.g., ClientA and ClientB) to execute concurrently without lock contention on the global map.

9. Production Considerations

• Distributed Rate Limiting: In production environments with multiple API gateway nodes, in-memory rate limiting is insufficient. You should persist token buckets in a shared Redis cache, using Redis Lua scripts to execute token checks and decrements atomically.
• Memory Management: If millions of clients access the system, the map can grow indefinitely, causing memory leaks. We must set an eviction policy (e.g., using a Least Recently Used (LRU) cache) to clean up inactive client buckets.

10. Next Lesson Preview

In the next case study, we will design an Elevator System. We will study SCAN/LOOK scheduling algorithms, state transitions, and request routing queues!