Implementing Rate Limiting
1. Using Token Bucket Algorithm
| Element | Detail |
|---|---|
| Bucket capacity | Burst size |
| Refill rate | Tokens added per second |
| Behavior | Allow if token available; else 429 |
| Use | Smooth burst tolerance (most common) |
Example: Token bucket (Redis Lua)
// Pseudo: capacity=100, refill=10/s
long now = clock.millis();
long tokens = redis.evalsha(luaTokenBucket, key, capacity, refill, now);
if (tokens < 1) throw new RateLimitedException();2. Using Leaky Bucket Algorithm
| Element | Detail |
|---|---|
| Queue | Fixed-size buffer of requests |
| Leak rate | Constant outflow |
| Behavior | Smooth output; reject when full |
| Use | Traffic shaping; constant downstream rate |
3. Using Fixed Window Counter
| Aspect | Detail |
|---|---|
| Window | e.g. per minute |
| Counter | Increment per request; reset at boundary |
| Pros | Simple, low memory |
| Cons | Edge bursts at window boundary (2× limit) |
4. Using Sliding Window Log
| Aspect | Detail |
|---|---|
| Storage | Sorted set of timestamps |
| Check | Count entries in last N seconds |
| Pros | Most accurate |
| Cons | O(N) memory per key |
5. Using Sliding Window Counter
| Aspect | Detail |
|---|---|
| Approximation | Weighted blend of current + previous window |
| Memory | Two counters per key |
| Pros | Smooth, low memory |
| Use | Default for HTTP rate limiters |
6. Implementing Per-User Limits
| Key | Detail |
|---|---|
| Authenticated | JWT subject ID |
| Anonymous | Hashed IP |
| API tier | Free / Pro / Enterprise quotas |
| Quota window | Per second / minute / day |
7. Implementing Per-Service Limits
| Scope | Detail |
|---|---|
| Per upstream | Protect dependency from overload |
| Per route | Different limits per endpoint |
| Tenant | Multi-tenant fairness |
| Concurrency limit | Cap in-flight requests (semaphore) |
8. Handling Rate Limit Responses
| Element | Detail |
|---|---|
| Status | 429 Too Many Requests |
| Retry-After | Seconds or HTTP date |
| Error body | JSON with code & doc link |
| Client | Backoff with jitter |
9. Using Distributed Rate Limiting
| Backend | Detail |
|---|---|
| Redis | INCR + EXPIRE; Lua for atomicity |
| Envoy global RL service | gRPC (Lyft Ratelimit) |
| Cell-based | Hash key → shard for scale |
| Local + global | Cheap local cap; global precise |
10. Implementing Rate Limit Headers
| Header | Meaning |
|---|---|
| X-RateLimit-Limit | Quota in window |
| X-RateLimit-Remaining | Calls left |
| X-RateLimit-Reset | Reset time (epoch / seconds) |
| RateLimit (RFC draft) | RateLimit: limit=100, remaining=42, reset=30 |
| Retry-After | On 429 |
11. Managing Rate Limit Tiers
| Tier | Quota |
|---|---|
| Free | 60 req/min, 10k/day |
| Pro | 600 req/min, 1M/day |
| Enterprise | Custom; SLAs |
| Burst | Allow short overage with token refill |
12. Implementing Adaptive Rate Limiting
| Signal | Action |
|---|---|
| Latency rise | Reduce concurrency |
| Error spike | Tighten quotas |
| Healthy | Relax limits |
| Algorithms | AIMD, concurrency limits (Netflix Limit lib) |