Rate Limiting Deep Dive — Algorithms, Strategies, and Distributed Limits
In this tutorial, you'll learn about Rate Limiting Deep. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Rate limiting at the API Gateway prevents abuse by controlling how many requests a client can make within a given time window using various algorithmic approaches.
What You'll Learn
By the end of this lesson, you will implement token bucket, leaky bucket, and Sliding Window rate limiters, understand distributed rate limiting with Redis, and choose the right Strategy for your use case.
Why It Matters
Without rate limiting, a single misbehaving client can degrade or crash backend services. Choosing the right algorithm balances accuracy, memory, and performance.
Real-World Use
Durga Antivirus Pro uses a sliding window rate limiter at its gateway, allowing 100 scan requests per minute per API key with burst handling for legitimate traffic spikes.
Rate Limiting Algorithms Comparison
flowchart TD
Request-->Algorithms{Choose Algorithm}
Algorithms-->|Burst Tolerant|Token[Token Bucket]
Algorithms-->|Smooth Flow|Leaky[Leaky Bucket]
Algorithms-->|Accurate|Sliding[Sliding Window]
Algorithms-->|Simple|Fixed[Fixed Window]
Token-->Redis[Redis Counter]
Leaky-->Redis
Sliding-->Redis
Fixed-->Redis
Redis-->Response{Allowed?}
Response-->|Yes|Backend
Response-->|No|429[429 Too Many Requests]
Token Bucket Algorithm
The token bucket allows bursts up to the bucket size while maintaining a steady refill rate.
import time
from typing import Dict, Optional
class TokenBucket:
def __init__(self, capacity: int = 10,
refill_rate: float = 1.0):
self.capacity = capacity
self.refill_rate = refill_rate
self.tokens: Dict[str, float] = {}
self.timestamps: Dict[str, float] = {}
def allow(self, key: str, tokens: int = 1) -> bool:
now = time.time()
if key not in self.tokens:
self.tokens[key] = self.capacity
self.timestamps[key] = now
elapsed = now - self.timestamps[key]
self.tokens[key] = min(
self.capacity,
self.tokens[key] + elapsed * self.refill_rate
)
self.timestamps[key] = now
if self.tokens[key] >= tokens:
self.tokens[key] -= tokens
return True
return False
bucket = TokenBucket(capacity=5, refill_rate=2.0)
for i in range(8):
allowed = bucket.allow("client-1")
print(f"Request {i+1}: allowed={allowed}")
time.sleep(0.1)
Sliding Window Log
The sliding window maintains a log of timestamps per client, offering precise rate limiting.
from collections import defaultdict
from typing import Dict, List, Tuple
import time
class SlidingWindowLog:
def __init__(self, max_requests: int = 10,
window_seconds: int = 60):
self.max_requests = max_requests
self.window_seconds = window_seconds
self.logs: Dict[str, List[float]] = defaultdict(list)
def allow(self, client_id: str) -> Tuple[bool, int, int]:
now = time.time()
cutoff = now - self.window_seconds
self.logs[client_id] = [
t for t in self.logs[client_id]
if t > cutoff
]
count = len(self.logs[client_id])
if count < self.max_requests:
self.logs[client_id].append(now)
return True, count + 1, self.max_requests
return False, count, self.max_requests
def remaining(self, client_id: str) -> int:
now = time.time()
cutoff = now - self.window_seconds
active = sum(
1 for t in self.logs[client_id]
if t > cutoff
)
return max(0, self.max_requests - active)
limiter = SlidingWindowLog(max_requests=5, window_seconds=10)
for i in range(7):
allowed, current, limit = limiter.allow("client-1")
print(f"Request {i+1}: {allowed}, {current}/{limit}")
time.sleep(0.05)
Distributed Rate Limiting with Redis
For multi-instance gateways, Redis provides a shared counter for accurate distributed rate limiting.
import redis
import time
from typing import Tuple
class RedisSlidingWindow:
def __init__(self, redis_client: redis.Redis,
max_requests: int = 100,
window_seconds: int = 60):
self.redis = redis_client
self.max_requests = max_requests
self.window_seconds = window_seconds
def allow(self, client_id: str) -> Tuple[bool, int]:
now = int(time.time() * 1000)
window_start = now - self.window_seconds * 1000
key = f"ratelimit:{client_id}"
pipeline = self.redis.pipeline()
pipeline.zremrangebyscore(key, 0, window_start)
pipeline.zcard(key)
pipeline.zadd(key, {str(now): now})
pipeline.expire(key, self.window_seconds + 1)
_, count, _, _ = pipeline.execute()
allowed = count < self.max_requests
return allowed, max(0, self.max_requests - count - 1)
def get_ttl(self, client_id: str) -> int:
key = f"ratelimit:{client_id}"
return self.redis.ttl(key) or self.window_seconds
# Usage would require a running Redis instance
# r = redis.Redis(host='localhost', port=6379, db=0)
# limiter = RedisSlidingWindow(r, 100, 60)
# allowed, remaining = limiter.allow("client-1")
Adaptive Rate Limiting
Adaptive rate limiting adjusts limits based on backend health and client behavior.
from typing import Dict, Tuple
import time
class AdaptiveRateLimiter:
def __init__(self, base_limit: int = 100,
min_limit: int = 10):
self.base_limit = base_limit
self.min_limit = min_limit
self.client_limits: Dict[str, int] = {}
self.backend_latency: Dict[str, float] = {}
self.violations: Dict[str, int] = {}
def get_limit(self, client_id: str) -> int:
return self.client_limits.get(
client_id, self.base_limit
)
def record_backend_latency(self, latency_ms: float):
self.backend_latency["current"] = latency_ms
avg = sum(self.backend_latency.values())
count = len(self.backend_latency)
if avg / count > 1000:
self.base_limit = max(
self.min_limit,
self.base_limit - 10
)
def record_violation(self, client_id: str):
self.violations[client_id] = \
self.violations.get(client_id, 0) + 1
if self.violations[client_id] >= 3:
current = self.get_limit(client_id)
self.client_limits[client_id] = max(
self.min_limit,
current // 2
)
def allow(self, client_id: str) -> Tuple[bool, int]:
limit = self.get_limit(client_id)
current = 0
allowed = current < limit
return allowed, limit - current if allowed else 0
limiter = AdaptiveRateLimiter(base_limit=100)
limiter.record_violation("abusive-client")
limiter.record_violation("abusive-client")
limiter.record_violation("abusive-client")
print(f"New limit: {limiter.get_limit('abusive-client')}")
Common Mistakes
Mistake 1: Using Fixed Window at Scale
Fixed window limits cause traffic spikes at window boundaries. Always use sliding window or token bucket.
Mistake 2: Not Returning Rate Limit Headers
Clients need X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset headers to self-regulate.
Mistake 3: Rate Limiting by IP Only
NAT and VPN users share IPs. Rate limit by API key, user ID, or a combination.
Mistake 4: No Burst Allowance
Rejecting all requests above the limit breaks legitimate use cases. Allow short bursts with the token bucket algorithm.
Mistake 5: Ignoring Distributed State
Single-instance rate limiters break under horizontal scaling. Use Redis or another shared store.
Practice Questions
- What is the difference between token bucket and leaky bucket algorithms?
- Why does the fixed window algorithm have a boundary problem?
- How does Redis Sorted Set enable sliding window rate limiting?
- What headers should a rate-limited API response include?
- How do you handle rate limit configuration per client tier?
Challenge
Build a distributed rate limiter using Redis that allows 1000 requests per hour with a burst of 50 requests per minute, returning proper rate limit headers in the response.
FAQ
Mini Project
Build a distributed rate limiter using Redis and the sliding window log algorithm that supports per-client and per-endpoint limits, returns standard rate limit headers, and gracefully handles Redis failures by falling back to a local in-memory limiter.
What's Next
Learn about Authentication Deep at the gateway, or explore Caching Deep strategies for performance optimization.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro