Rate limiting is not merely a feature; it is the first line of defense in web application security. It protects your infrastructure from Denial of Service (DoS) attacks, prevents API abuse, and ensures fair resource allocation among users. While many developers rely on third-party services like Cloudflare or AWS WAF, understanding how to implement rate limiting from scratch is crucial for building custom solutions or optimizing lightweight microservices.
In this post, we will explore the core algorithms behind rate limiting, discuss state management strategies, and provide practical code examples in JavaScript and Go.
The Fixed Window Algorithm: Simplicity vs. The Cliff Effect
The Fixed Window algorithm is the simplest approach. It divides time into fixed intervals (e.g., 1-minute windows) and counts requests within that window. Once the counter exceeds the limit, subsequent requests are rejected until the window resets.
While efficient, this method suffers from the "cliff effect." If a user makes 100 requests at the very end of one window and 100 requests at the start of the next, they have effectively bypassed a 200-request-per-minute limit by making 200 requests in a 2-minute span. To mitigate this, some systems implement overlapping windows, but this adds complexity.
Implementation in JavaScript (Node.js)
Below is a simple middleware example using the Fixed Window approach with an in-memory store. Note that for production, you would replace the memory store with Redis to handle distributed state.
const RATE_LIMIT = 100;
const WINDOW_MS = 60000; // 1 minute
const requests = new Map();
function fixedWindowLimit(req, res, next) {
const ip = req.ip;
const now = Date.now();
const windowStart = Math.floor(now / WINDOW_MS) * WINDOW_MS;
if (!requests.has(ip) || requests.get(ip).windowStart !== windowStart) {
// New window, reset counter
requests.set(ip, { count: 1, windowStart });
} else {
const current = requests.get(ip);
if (current.count >= RATE_LIMIT) {
return res.status(429).json({ error: "Too Many Requests" });
}
current.count++;
}
next();
}The Sliding Window Log: Precision at a Cost
To eliminate the cliff effect, the Sliding Window Log algorithm records the timestamp of every request. When a new request arrives, the system calculates the number of requests in the last N seconds. If the count exceeds the limit, the request is denied.
This approach offers high precision but comes with a significant storage cost. As the number of requests increases, the log grows indefinitely unless you implement periodic cleanup or use a sorted data structure to efficiently discard old entries.
The Token Bucket: Smooth Traffic Flow
The Token Bucket algorithm is often considered the gold standard for balancing fairness and performance. Imagine a bucket with a fixed capacity. Tokens are added to the bucket at a constant rate. Each request consumes one token. If the bucket is empty, the request is denied.
This allows for bursts of traffic (if tokens are accumulated) while strictly capping the long-term average rate. It is mathematically elegant and performs well in distributed systems.
Implementation in Go
Go's concurrency model makes it an excellent choice for implementing token buckets. Here is a robust implementation using a mutex-protected structure.
package main
import (
"sync"
"time"
)
type TokenBucket struct {
tokens float64
maxTokens float64
refillRate float64
lastRefill time.Time
mu sync.Mutex
}
func NewTokenBucket(maxTokens, refillRate float64) *TokenBucket {
return &TokenBucket{
tokens: maxTokens,
maxTokens: maxTokens,
refillRate: refillRate,
lastRefill: time.Now(),
}
}
func (tb *TokenBucket) Allow() bool {
tb.mu.Lock()
defer tb.mu.Unlock()
now := time.Now()
elapsed := now.Sub(tb.lastRefill).Seconds()
tb.tokens += elapsed * tb.refillRate
if tb.tokens > tb.maxTokens {
tb.tokens = tb.maxTokens
}
tb.lastRefill = now
if tb.tokens >= 1.0 {
tb.tokens--
return true
}
return false
}State Management: Choosing Your Backend
The most critical aspect of production-grade rate limiting is state management. In-memory maps, as shown in the JavaScript example, work only for single-instance deployments. For multi-node environments, you need a shared state.
- Redis: The industry standard. Use sorted sets for sliding windows or simple hashes for fixed windows. Its speed and atomic operations make it ideal for high-throughput APIs.
- Memcached: Faster than Redis for simple key-value lookups but lacks the data structures needed for sliding windows.
- Distributed Locks: If you must use a database, ensure you use optimistic locking or database-level constraints to prevent race conditions during high concurrency.
Conclusion
Implementing rate limiting from scratch gives you granular control over your application's security posture. While the Fixed Window algorithm is easy to understand, the Token Bucket offers better flexibility for real-world traffic patterns. Regardless of the algorithm you choose, always prioritize efficient state management using tools like Redis to ensure consistency across distributed systems. By mastering these core algorithms, you build a resilient foundation that protects your application from abuse while maintaining a smooth experience for legitimate users.