Design Rate Limiter
Implement request rate limiting
Overview
Design a rate limiter for an API endpoint to prevent abuse and DDoS. The system should grant permission to make a request or deny it based on user/IP rate limits.
Key Concepts
Algorithms: Token Bucket, Leaky Bucket, Sliding Window Log, Sliding Window Counter
Distributed Caching: Redis for tracking state across instances
Time complexity for checking limits: O(1)
Code Example
java
1public class TokenBucket {
2 private final long capacity;
3 private final double refillRatePerSecond;
4 private double tokens;
5 private long lastRefillTimestamp;
6
7 public synchronized boolean tryConsume() {
8 refill();
9 if (tokens >= 1) {
10 tokens -= 1;
11 return true;
12 }
13 return false;
14 }
15
16 private void refill() {
17 long now = System.currentTimeMillis();
18 double tokensToAdd = ((now - lastRefillTimestamp) / 1000.0) * refillRatePerSecond;
19 tokens = Math.min(capacity, tokens + tokensToAdd);
20 lastRefillTimestamp = now;
21 }
22}💡 Interview Tips
Deeply understand Token Bucket vs Sliding Window
Concurrency is the major pitfall here; use synchronized blocks or lock-free data structures in memory