Rate limiting is one of those things that seems simple until you actually implement it. “Allow 100 requests per minute” sounds trivial. Then you discover that naive implementations let users burst 200 requests by straddling a minute boundary, that distributed systems require atomic operations across nodes, that different endpoints need different limits, that you need to tell clients what their limit is and when it resets, and that the wrong algorithm can make your service unusable under bursty but legitimate traffic.
This guide covers the five major rate limiting algorithms — their trade-offs, failure modes, and production implementations — then addresses the harder problems: distributed rate limiting with Redis, per-user and per-tier limits, and communicating limits clearly to API clients.
Why Rate Limiting Exists
Before algorithms, it’s worth being precise about what you’re protecting against, because the answer shapes which algorithm to use:
Abuse and scraping — a single actor consuming resources intended for many. Wants a hard per-user limit with no forgiveness for bursts.
Accidental client bugs — a mobile app enters a retry loop and fires 500 requests per second. Wants a limit that lets legitimate bursts through but catches runaway loops.
Cost control — your LLM inference endpoint costs $0.01 per call. A single free-tier user should not be able to generate a $500 bill. Wants hard daily/monthly limits.
DDoS protection — many actors overwhelming a service. Rate limiting alone is insufficient here; you want this at the edge (Cloudflare, AWS Shield), not in your application.
Fair sharing — ensuring one power user doesn’t starve others. Wants a smooth rate rather than a hard cap.
The algorithm you choose should match the threat model.
Algorithm 1: Fixed Window Counter
The simplest algorithm. Divide time into fixed windows (e.g., each minute from :00 to :59). Maintain a counter per window. Increment on each request. Reject when counter exceeds limit.
Window [14:00:00 - 14:00:59]: count = 0
Request arrives 14:00:30 → count = 1 → allow
Request arrives 14:00:45 → count = 2 → allow
...
Request arrives 14:00:58 → count = 100 → allow
Request arrives 14:00:59 → count = 101 → REJECT
Window resets at 14:01:00: count = 0
Request arrives 14:01:00 → count = 1 → allow
Implementation (Go + Redis):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
func (rl *FixedWindowLimiter) Allow(ctx context.Context, key string) (bool, *RateLimitInfo, error) {
// Window key: "ratelimit:user:123:2026032714" (per-minute: use minute precision)
now := time.Now().UTC()
windowKey := fmt.Sprintf("%s:%s", key, now.Format("200601021504")) // YYYYMMDDHHmm
pipe := rl.redis.Pipeline()
incr := pipe.Incr(ctx, windowKey)
pipe.Expire(ctx, windowKey, 2*time.Minute) // TTL slightly longer than window
_, err := pipe.Exec(ctx)
if err != nil {
return true, nil, err // fail open on Redis errors
}
count := incr.Val()
remaining := rl.limit - count
if remaining < 0 {
remaining = 0
}
// Reset time: start of next window
nextWindow := now.Truncate(time.Minute).Add(time.Minute)
info := &RateLimitInfo{
Limit: rl.limit,
Remaining: remaining,
ResetAt: nextWindow,
}
return count <= rl.limit, info, nil
}
|
The boundary burst problem:
Limit: 100 req/min
14:00:50 → 100 requests (all allowed — within limit for the :00 window)
14:01:00 → window resets
14:01:00 → 100 more requests (all allowed — fresh window)
Result: 200 requests in 10 seconds. Double the intended rate.
This is the fundamental flaw of fixed windows. Every window boundary is a burst opportunity.
When to use it: Simple internal rate limiting where the burst problem is acceptable, or when you need minimal storage and compute overhead at extremely high throughput.
Algorithm 2: Sliding Window Log
Track the exact timestamp of every request. To check the limit, count how many requests fall within the last N seconds. Sliding window: no boundary burst problem.
Limit: 5 req/min
Current time: 14:01:30
Log: [14:00:35, 14:00:50, 14:01:05, 14:01:20, 14:01:25]
Window: [14:00:30 - 14:01:30]
Count in window: 5 → at limit
Next request: REJECT
At 14:01:36, the entry 14:00:35 falls out of the window.
Count drops to 4 → allow.
Implementation with Redis sorted set:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
func (rl *SlidingWindowLogLimiter) Allow(ctx context.Context, key string) (bool, *RateLimitInfo, error) {
now := time.Now().UnixNano()
windowStart := now - rl.window.Nanoseconds()
pipe := rl.redis.TxPipeline()
// Remove entries outside the window
pipe.ZRemRangeByScore(ctx, key, "0", strconv.FormatInt(windowStart, 10))
// Count entries in window
count := pipe.ZCard(ctx, key)
// Add current request with timestamp as both score and member
// Use nano timestamp as member to ensure uniqueness
pipe.ZAdd(ctx, key, redis.Z{Score: float64(now), Member: now})
// Set TTL to clean up idle keys
pipe.Expire(ctx, key, rl.window+time.Second)
_, err := pipe.Exec(ctx)
if err != nil {
return true, nil, err
}
currentCount := count.Val() + 1 // +1 for the request we just added
allowed := currentCount <= rl.limit
if !allowed {
// Remove the entry we just added (we're rejecting this request)
rl.redis.ZRem(ctx, key, now)
}
remaining := rl.limit - currentCount
if remaining < 0 {
remaining = 0
}
info := &RateLimitInfo{
Limit: rl.limit,
Remaining: remaining,
// RetryAfter: time until oldest entry exits the window
RetryAfter: rl.retryAfter(ctx, key),
}
return allowed, info, nil
}
func (rl *SlidingWindowLogLimiter) retryAfter(ctx context.Context, key string) time.Duration {
// Get the oldest entry in the window
entries, err := rl.redis.ZRangeWithScores(ctx, key, 0, 0).Result()
if err != nil || len(entries) == 0 {
return 0
}
oldestNs := int64(entries[0].Score)
expiresAt := time.Unix(0, oldestNs).Add(rl.window)
return time.Until(expiresAt)
}
|
Trade-off: Exact accuracy, but memory grows linearly with request count. Each request stores a timestamp. At 1,000 req/min per user with 10,000 active users, that’s 10 million sorted set members in Redis. Workable, but monitor it.
When to use it: Low-volume, high-accuracy requirements. Audit logging contexts where exact counts matter. When the burst problem of fixed windows is genuinely unacceptable.
Algorithm 3: Sliding Window Counter
The practical compromise — combines the memory efficiency of fixed windows with most of the accuracy of sliding window logs. Uses two adjacent fixed windows and interpolates.
Limit: 100 req/min
Previous window [14:00 - 14:00:59]: count = 80
Current window [14:01 - 14:01:59]: count = 30
Current time: 14:01:15 (25% into the current window)
Estimated count for the last 60 seconds:
= (previous_count × overlap_fraction) + current_count
= (80 × 0.75) + 30 ← 75% of previous window still in our 60s window
= 60 + 30
= 90 → under limit → allow
Implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
func (rl *SlidingWindowCounterLimiter) Allow(ctx context.Context, key string) (bool, *RateLimitInfo, error) {
now := time.Now().UTC()
// Keys for current and previous windows
currentWindow := now.Truncate(rl.window)
previousWindow := currentWindow.Add(-rl.window)
currentKey := fmt.Sprintf("%s:%d", key, currentWindow.Unix())
previousKey := fmt.Sprintf("%s:%d", key, previousWindow.Unix())
pipe := rl.redis.Pipeline()
currentCount := pipe.Get(ctx, currentKey)
previousCount := pipe.Get(ctx, previousKey)
pipe.Exec(ctx)
current := parseInt64(currentCount.Val())
previous := parseInt64(previousCount.Val())
// How far through the current window are we?
elapsed := now.Sub(currentWindow)
overlapFraction := 1.0 - (elapsed.Seconds() / rl.window.Seconds())
// Weighted estimate
estimated := float64(previous)*overlapFraction + float64(current)
allowed := estimated < float64(rl.limit)
if allowed {
// Increment current window counter
pipe2 := rl.redis.Pipeline()
pipe2.Incr(ctx, currentKey)
pipe2.Expire(ctx, currentKey, 2*rl.window)
pipe2.Exec(ctx)
}
remaining := float64(rl.limit) - estimated
if remaining < 0 {
remaining = 0
}
return allowed, &RateLimitInfo{
Limit: rl.limit,
Remaining: int64(remaining),
ResetAt: currentWindow.Add(rl.window),
}, nil
}
|
When to use it: The default choice for most production APIs. Memory efficient (two integers per user per window), accurate enough for practical purposes, no boundary burst problem for typical traffic patterns. Used by Cloudflare’s public rate limiter.
Algorithm 4: Token Bucket
A bucket holds tokens. Tokens refill at a constant rate up to the bucket’s capacity. Each request consumes one token. If the bucket is empty, the request is rejected.
Bucket capacity: 100 tokens
Refill rate: 10 tokens/second
State: 100 tokens (full)
10 requests arrive simultaneously → 90 tokens remain → all allowed
1 second passes → 10 tokens added → 100 tokens
State: 10 tokens
50 requests arrive simultaneously → 10 allowed, 40 rejected
5 seconds pass → 50 tokens added → 60 tokens
The bucket naturally absorbs bursts up to its capacity, then enforces a sustained rate equal to the refill rate. This is the right algorithm when you want to allow legitimate bursts (a mobile client that batches requests on reconnect) while still enforcing an average rate.
Implementation (Redis with Lua for atomicity):
The challenge with token bucket in Redis is atomicity — you need to read the current token count, compute new tokens based on elapsed time, and update the count, all in one operation. Lua scripts run atomically in Redis:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
-- token_bucket.lua
-- KEYS[1]: the bucket key
-- ARGV[1]: max tokens (capacity)
-- ARGV[2]: refill rate (tokens per second, as float)
-- ARGV[3]: current time (unix timestamp as float, nanosecond precision)
-- ARGV[4]: tokens requested (usually 1)
-- Returns: {allowed (0/1), tokens_remaining, retry_after_ms}
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])
local bucket = redis.call("HMGET", key, "tokens", "last_refill")
local tokens = tonumber(bucket[1])
local last_refill = tonumber(bucket[2])
-- First request: initialize bucket to capacity
if tokens == nil then
tokens = capacity
last_refill = now
end
-- Add tokens for time elapsed since last refill
local elapsed = now - last_refill
local new_tokens = elapsed * rate
tokens = math.min(capacity, tokens + new_tokens)
last_refill = now
local allowed = 0
local retry_after_ms = 0
if tokens >= requested then
tokens = tokens - requested
allowed = 1
else
-- How long until we have enough tokens?
local deficit = requested - tokens
retry_after_ms = math.ceil((deficit / rate) * 1000)
end
-- Store updated bucket state with TTL
redis.call("HMSET", key, "tokens", tokens, "last_refill", last_refill)
redis.call("PEXPIRE", key, math.ceil(capacity / rate * 1000) + 5000)
return {allowed, math.floor(tokens), retry_after_ms}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
// token_bucket.go
package ratelimit
import (
_ "embed"
"context"
"fmt"
"time"
"github.com/redis/go-redis/v9"
)
//go:embed token_bucket.lua
var tokenBucketScript string
type TokenBucketLimiter struct {
redis *redis.Client
script *redis.Script
capacity int64
rate float64 // tokens per second
}
func NewTokenBucketLimiter(rdb *redis.Client, capacity int64, rate float64) *TokenBucketLimiter {
return &TokenBucketLimiter{
redis: rdb,
script: redis.NewScript(tokenBucketScript),
capacity: capacity,
rate: rate,
}
}
func (l *TokenBucketLimiter) Allow(ctx context.Context, key string) (bool, *RateLimitInfo, error) {
nowNs := float64(time.Now().UnixNano()) / 1e9 // seconds with nanosecond precision
result, err := l.script.Run(ctx, l.redis,
[]string{key},
l.capacity,
l.rate,
nowNs,
1, // request 1 token
).Slice()
if err != nil {
return true, nil, fmt.Errorf("token bucket script: %w", err)
}
allowed := result[0].(int64) == 1
remaining := result[1].(int64)
retryAfterMs := result[2].(int64)
info := &RateLimitInfo{
Limit: l.capacity,
Remaining: remaining,
}
if retryAfterMs > 0 {
info.RetryAfter = time.Duration(retryAfterMs) * time.Millisecond
}
return allowed, info, nil
}
|
When to use it: When you need to allow legitimate bursts. Payment processors, file upload APIs, webhooks delivery — anything where a client legitimately needs to send several requests at once but shouldn’t be able to sustain a high rate indefinitely. AWS API Gateway and Stripe both use token bucket.
Algorithm 5: Leaky Bucket
Requests enter a queue (the “bucket”). A fixed-rate processor drains the queue. New requests are rejected if the queue is full. This produces perfectly smooth output regardless of input burstiness — no burst absorption.
Queue capacity: 10
Drain rate: 2 req/sec
50 requests arrive simultaneously:
→ 10 queued, 40 rejected immediately
→ 2 processed per second
vs. Token Bucket with same capacity/rate:
→ 10 processed immediately (burst absorbed)
→ 2 per second after bucket empties
Leaky bucket is the right choice when downstream systems can only handle a perfectly smooth request rate — for example, a third-party API that imposes a strict per-second rate limit with no burst tolerance. You act as the rate limiter for your own service to protect the downstream.
In practice, leaky bucket is often implemented as an async queue (Redis list + worker) rather than inline in request handling, since “queue the request and process it later” is a different model from “allow or reject immediately.”
When to use it: Outbound API calls to rate-limited third parties. Email/SMS sending where you have a fixed throughput limit. Anywhere smooth output matters more than request latency.
Choosing the Right Algorithm
| Algorithm |
Burst handling |
Memory |
Accuracy |
Best for |
| Fixed window |
Poor (boundary burst) |
O(1) |
Moderate |
Internal tools, rough protection |
| Sliding window log |
None (strict) |
O(requests) |
Exact |
Audit logging, strict billing |
| Sliding window counter |
Good (interpolated) |
O(1) |
~98% |
Most production APIs |
| Token bucket |
Excellent |
O(1) |
Exact |
User-facing APIs with bursty clients |
| Leaky bucket |
None (queues/rejects) |
O(queue) |
Exact |
Protecting rate-limited upstreams |
Multi-Level Rate Limiting
Real APIs need limits at multiple granularities simultaneously. A user might be allowed 1,000 requests per day, 100 per minute, and 20 per second — all three enforced concurrently.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
type MultiLimiter struct {
limiters []Limiter
}
func (m *MultiLimiter) Allow(ctx context.Context, key string) (bool, *RateLimitInfo, error) {
var mostRestrictive *RateLimitInfo
for _, limiter := range m.limiters {
allowed, info, err := limiter.Allow(ctx, key)
if err != nil {
return true, nil, err // fail open
}
if mostRestrictive == nil || info.Remaining < mostRestrictive.Remaining {
mostRestrictive = info
}
if !allowed {
// Return the most restrictive info for the Retry-After header
return false, info, nil
}
}
return true, mostRestrictive, nil
}
// Usage:
userLimiter := NewMultiLimiter([]Limiter{
NewSlidingWindowCounterLimiter(rdb, 20, time.Second), // 20/sec
NewSlidingWindowCounterLimiter(rdb, 100, time.Minute), // 100/min
NewSlidingWindowCounterLimiter(rdb, 1000, 24*time.Hour), // 1000/day
})
|
The key: check all limiters but return on the first rejection. The Retry-After header should reflect the soonest the request would succeed — which is the reset time of the rejected window.
Per-User and Per-Tier Rate Limiting
Different customers deserve different limits. Free users get 100 requests per minute; paid users get 1,000; enterprise gets 10,000. This requires building the limit into the key lookup.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
// middleware/rate_limit.go
type Tier struct {
RequestsPerMinute int64
RequestsPerDay int64
BurstCapacity int64
}
var tiers = map[string]Tier{
"free": {RequestsPerMinute: 60, RequestsPerDay: 1000, BurstCapacity: 20},
"pro": {RequestsPerMinute: 600, RequestsPerDay: 50000, BurstCapacity: 100},
"enterprise": {RequestsPerMinute: 6000, RequestsPerDay: 1000000, BurstCapacity: 500},
}
func RateLimitMiddleware(limiterFactory *LimiterFactory) func(http.Handler) http.Handler {
return func(next http.Handler) http.Handler {
return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
user := userFromContext(r.Context())
if user == nil {
// Unauthenticated: limit by IP
ip := realIP(r)
limiter := limiterFactory.GetIPLimiter(ip)
enforceLimit(w, r, next, limiter, "ip:"+ip)
return
}
tier, ok := tiers[user.Tier]
if !ok {
tier = tiers["free"]
}
// Namespace keys by user ID — different limits per tier
limiter := limiterFactory.GetUserLimiter(user.ID, tier)
enforceLimit(w, r, next, limiter, "user:"+user.ID)
})
}
}
func enforceLimit(w http.ResponseWriter, r *http.Request, next http.Handler,
limiter Limiter, key string) {
allowed, info, err := limiter.Allow(r.Context(), key)
if err != nil {
// Log but fail open — don't let Redis outages take down the API
log.Warn("rate limiter error, failing open", zap.Error(err))
next.ServeHTTP(w, r)
return
}
// Always set rate limit headers — even on allowed requests
setRateLimitHeaders(w, info)
if !allowed {
w.Header().Set("Content-Type", "application/json")
w.WriteHeader(http.StatusTooManyRequests)
json.NewEncoder(w).Encode(map[string]interface{}{
"error": "rate_limit_exceeded",
"message": "You have exceeded your rate limit. Please slow down.",
"retry_after": info.RetryAfter.Seconds(),
"limit": info.Limit,
"reset_at": info.ResetAt.Unix(),
})
return
}
next.ServeHTTP(w, r)
}
|
Communicating Limits to Clients
A rate limiter that silently rejects requests is useless. Clients need to know their limit, how much they’ve used, when it resets, and how long to wait before retrying. The industry has converged on a standard set of response headers.
Standard Rate Limit Headers
RateLimit-Limit: 100
RateLimit-Remaining: 73
RateLimit-Reset: 1711544580 ← Unix timestamp when limit resets
RateLimit-Policy: "100;w=60" ← IETF draft: 100 requests per 60 second window
X-RateLimit-Limit: 100 ← Legacy prefixed form (still widely used)
X-RateLimit-Remaining: 73
X-RateLimit-Reset: 1711544580
Retry-After: 27 ← Seconds until retry (only on 429 responses)
The IETF RateLimit Header Fields draft is becoming the standard. Support both the RateLimit-* (new) and X-RateLimit-* (legacy) forms during the transition period.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func setRateLimitHeaders(w http.ResponseWriter, info *RateLimitInfo) {
w.Header().Set("RateLimit-Limit", strconv.FormatInt(info.Limit, 10))
w.Header().Set("RateLimit-Remaining", strconv.FormatInt(info.Remaining, 10))
w.Header().Set("RateLimit-Policy",
fmt.Sprintf(`%d;w=%d`, info.Limit, int(info.Window.Seconds())))
// Legacy headers for compatibility
w.Header().Set("X-RateLimit-Limit", strconv.FormatInt(info.Limit, 10))
w.Header().Set("X-RateLimit-Remaining", strconv.FormatInt(info.Remaining, 10))
if !info.ResetAt.IsZero() {
resetUnix := strconv.FormatInt(info.ResetAt.Unix(), 10)
w.Header().Set("RateLimit-Reset", resetUnix)
w.Header().Set("X-RateLimit-Reset", resetUnix)
}
if info.RetryAfter > 0 {
// Retry-After in seconds (integer per RFC 7231)
seconds := int(math.Ceil(info.RetryAfter.Seconds()))
w.Header().Set("Retry-After", strconv.Itoa(seconds))
}
}
|
The 429 Response Body
Don’t just return a 429 status code — give clients enough context to adapt:
1
2
3
4
5
6
7
8
9
10
|
{
"error": "rate_limit_exceeded",
"message": "API rate limit exceeded for your plan.",
"limit": 100,
"window": "60s",
"retry_after_seconds": 23,
"reset_at": "2026-03-27T14:32:00Z",
"documentation_url": "https://docs.yourapi.com/rate-limits",
"upgrade_url": "https://yourapi.com/pricing"
}
|
Client Retry Logic: Exponential Backoff with Jitter
Show clients what proper retry behavior looks like in your documentation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
# Python client example
import time
import random
import httpx
def request_with_retry(client: httpx.Client, url: str, max_retries: int = 5) -> httpx.Response:
for attempt in range(max_retries):
response = client.get(url)
if response.status_code == 429:
# Respect the Retry-After header if present
retry_after = response.headers.get("Retry-After")
if retry_after:
wait = float(retry_after)
else:
# Exponential backoff: 1s, 2s, 4s, 8s, 16s
# Plus jitter: ±25% to prevent thundering herd
base_wait = 2 ** attempt
jitter = base_wait * 0.25 * (random.random() * 2 - 1)
wait = base_wait + jitter
if attempt < max_retries - 1:
time.sleep(wait)
continue
return response
raise Exception(f"Rate limit exceeded after {max_retries} attempts")
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
// Go client example
func requestWithRetry(ctx context.Context, client *http.Client, url string) (*http.Response, error) {
maxRetries := 5
for attempt := range maxRetries {
req, _ := http.NewRequestWithContext(ctx, "GET", url, nil)
resp, err := client.Do(req)
if err != nil {
return nil, err
}
if resp.StatusCode != http.StatusTooManyRequests {
return resp, nil
}
resp.Body.Close()
if attempt == maxRetries-1 {
break
}
var wait time.Duration
if ra := resp.Header.Get("Retry-After"); ra != "" {
if secs, err := strconv.ParseFloat(ra, 64); err == nil {
wait = time.Duration(secs * float64(time.Second))
}
}
if wait == 0 {
// Exponential backoff with full jitter
base := time.Duration(1<<attempt) * time.Second
wait = time.Duration(rand.Int63n(int64(base)))
}
select {
case <-time.After(wait):
case <-ctx.Done():
return nil, ctx.Err()
}
}
return nil, fmt.Errorf("rate limit exceeded after %d attempts", maxRetries)
}
|
Distributed Rate Limiting with Redis
All the implementations above use Redis — but there are important operational details for production.
Redis Cluster Considerations
With Redis Cluster, keys are distributed across shards by their hash slot. If you naively use user:123 as your key, different window keys for the same user might land on different shards, breaking multi-key operations.
Solutions:
1. Hash tags — force related keys to the same shard:
1
2
3
4
|
// Keys with the same content in {} go to the same hash slot
currentKey := fmt.Sprintf("{user:%s}:ratelimit:%d", userID, window.Unix())
previousKey := fmt.Sprintf("{user:%s}:ratelimit:%d", userID, prevWindow.Unix())
// Both keys hash to the same slot because {user:123} is identical
|
2. Cluster-aware pipelines — use a client that handles cross-slot pipelines:
1
2
3
4
5
|
// go-redis automatically handles cross-slot operations in cluster mode
// but Lua scripts must use keys on the same slot
rdb := redis.NewClusterClient(&redis.ClusterOptions{
Addrs: []string{"redis-1:6379", "redis-2:6379", "redis-3:6379"},
})
|
3. Single-node Redis with replication — for most applications, a single Redis primary with read replicas is sufficient. Rate limit writes go to the primary. The only real concern is the primary failing.
Handling Redis Failures
Your rate limiter should not take down your API when Redis is unavailable. Two safe patterns:
Fail open — allow all requests when Redis is down. Abuse risk, but API stays up:
1
2
3
4
5
6
7
|
allowed, info, err := limiter.Allow(ctx, key)
if err != nil {
log.Error("rate limiter unavailable, failing open", zap.Error(err))
metrics.RateLimiterErrors.Inc()
next.ServeHTTP(w, r) // allow through
return
}
|
Local fallback — use an in-process fallback limiter (e.g., golang.org/x/time/rate) when Redis is unavailable. Less accurate (each instance has its own counters) but prevents abuse:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
type ResilientLimiter struct {
redis *RedisSlidingWindowLimiter
local *rate.Limiter // stdlib token bucket, per-process
useLocal atomic.Bool
}
func (l *ResilientLimiter) Allow(ctx context.Context, key string) (bool, *RateLimitInfo, error) {
if l.useLocal.Load() {
allowed := l.local.Allow()
return allowed, &RateLimitInfo{Limit: l.local.Burst()}, nil
}
allowed, info, err := l.redis.Allow(ctx, key)
if err != nil {
l.useLocal.Store(true)
// Schedule Redis check to re-enable distributed limiting
go l.checkRedisRecovery()
return l.local.Allow(), &RateLimitInfo{}, nil
}
return allowed, info, nil
}
|
Atomic Operations are Non-Negotiable
Every rate limit check-and-increment must be atomic. The classic TOCTOU (time-of-check time-of-use) race:
Goroutine 1: GET counter → 99
Goroutine 2: GET counter → 99 ← reads same value
Goroutine 1: 99 < 100 → allowed → INCR → 100
Goroutine 2: 99 < 100 → allowed → INCR → 101 ← OVER LIMIT
Fix: use Redis transactions (MULTI/EXEC), Lua scripts (run atomically on Redis server), or INCR + EXPIRE in a pipeline (the fixed window implementation shown earlier).
The Lua script approach is the most reliable for complex logic. The pipeline approach works for simple increment-and-check patterns.
Rate Limiting at Different Layers
Rate limiting doesn’t belong exclusively in your application. The right architecture uses multiple layers:
Edge (Cloudflare / AWS WAF)
→ IP-based, global DDoS protection, no application context
→ Limits: 1000 req/min per IP to any endpoint
API Gateway (Kong / AWS API GW / Nginx)
→ API-key-based, before application code runs
→ Limits: per-plan request quotas (daily/monthly)
→ Low latency, no Redis required (uses its own counters)
Application middleware
→ User-context-aware, endpoint-specific limits
→ Example: /api/search limited more aggressively than /api/profile
→ Implements business rules (free vs paid tier)
Service mesh (Istio / Envoy)
→ Service-to-service rate limiting
→ Prevents one internal service from overwhelming another
Nginx rate limiting (for the gateway layer):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
# nginx.conf
# Define a shared memory zone: 10MB holds ~160,000 IP states
limit_req_zone $binary_remote_addr zone=api_by_ip:10m rate=100r/m;
# Per API key (requires setting $api_key in an auth step)
limit_req_zone $http_x_api_key zone=api_by_key:10m rate=600r/m;
server {
location /api/ {
# Burst allows up to 20 extra requests queued, nodelay processes them immediately
limit_req zone=api_by_ip burst=20 nodelay;
limit_req zone=api_by_key burst=100 nodelay;
limit_req_status 429;
# Custom 429 response
error_page 429 /rate_limit.json;
proxy_pass http://backend;
}
location = /rate_limit.json {
internal;
default_type application/json;
return 429 '{"error":"rate_limit_exceeded","message":"Too many requests"}';
}
}
|
Endpoint-Specific Limits
Not all endpoints should share the same limit. A search endpoint that triggers expensive database queries deserves a tighter limit than a profile read endpoint.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
type EndpointConfig struct {
RequestsPerMinute int64
BurstCapacity int64
CostWeight float64 // expensive endpoints cost more tokens
}
var endpointLimits = map[string]EndpointConfig{
// Expensive: tight limits
"POST /api/search": {60, 10, 1.0},
"POST /api/export": {10, 2, 5.0}, // each export costs 5 tokens
"POST /api/ai/complete": {30, 5, 1.0},
// Cheap: generous limits
"GET /api/profile": {600, 100, 1.0},
"GET /api/notifications": {300, 50, 1.0},
// Default for unlisted endpoints
"default": {300, 60, 1.0},
}
func routeKey(r *http.Request) string {
// Normalize: "GET /api/users/123/profile" → "GET /api/users/:id/profile"
return r.Method + " " + normalizePath(r.URL.Path)
}
// Composite key: user + endpoint → each user has a separate bucket per endpoint
func rateLimitKey(userID, route string) string {
return fmt.Sprintf("ratelimit:{user:%s}:%s", userID, route)
}
|
Weighted token consumption — expensive operations deduct more tokens:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// Modify the token bucket Allow() to accept a cost parameter:
func (l *TokenBucketLimiter) AllowN(ctx context.Context, key string, n int64) (bool, *RateLimitInfo, error) {
// Pass n as ARGV[4] in the Lua script instead of hardcoded 1
result, err := l.script.Run(ctx, l.redis,
[]string{key},
l.capacity, l.rate, nowNs,
n, // consume n tokens
).Slice()
// ...
}
// Usage for an expensive AI endpoint:
config := endpointLimits["POST /api/ai/complete"]
allowed, info, err := limiter.AllowN(ctx, key, int64(config.CostWeight))
|
Testing Rate Limiters
Rate limiters are notoriously hard to test correctly. Key scenarios:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
// rate_limiter_test.go
func TestSlidingWindowCounterAtBoundary(t *testing.T) {
rdb := miniredis.RunT(t) // in-memory Redis for testing
client := redis.NewClient(&redis.Options{Addr: rdb.Addr()})
limiter := NewSlidingWindowCounterLimiter(client, 10, time.Minute)
key := "test:user:1"
// Consume exactly the limit
for i := range 10 {
allowed, _, _ := limiter.Allow(context.Background(), key)
if !allowed {
t.Fatalf("request %d should be allowed, got rejected", i+1)
}
}
// Next request should be rejected
allowed, info, _ := limiter.Allow(context.Background(), key)
if allowed {
t.Error("request 11 should be rejected")
}
if info.Remaining != 0 {
t.Errorf("remaining should be 0, got %d", info.Remaining)
}
if info.RetryAfter == 0 {
t.Error("RetryAfter should be set on rejected request")
}
}
func TestTokenBucketBurstAbsorption(t *testing.T) {
rdb := miniredis.RunT(t)
client := redis.NewClient(&redis.Options{Addr: rdb.Addr()})
// 10 tokens capacity, 1 token/second refill
limiter := NewTokenBucketLimiter(client, 10, 1.0)
key := "test:user:2"
// Burst of 10 should all succeed immediately
for i := range 10 {
allowed, _, _ := limiter.Allow(context.Background(), key)
if !allowed {
t.Fatalf("burst request %d should be allowed", i+1)
}
}
// 11th should fail
allowed, _, _ := limiter.Allow(context.Background(), key)
if allowed {
t.Error("burst of 11 should fail on empty bucket")
}
// Advance time by 5 seconds → 5 tokens refilled
rdb.FastForward(5 * time.Second)
// Should allow 5 more
for i := range 5 {
allowed, _, _ := limiter.Allow(context.Background(), key)
if !allowed {
t.Fatalf("post-refill request %d should be allowed", i+1)
}
}
}
func TestRateLimiterFailOpen(t *testing.T) {
// Test that the middleware fails open when Redis is unavailable
rdb := miniredis.RunT(t)
client := redis.NewClient(&redis.Options{Addr: rdb.Addr()})
limiter := NewSlidingWindowCounterLimiter(client, 1, time.Minute)
// Kill Redis
rdb.Close()
allowed, _, err := limiter.Allow(context.Background(), "test")
if err == nil {
t.Error("expected error when Redis is down")
}
if !allowed {
t.Error("should fail open when Redis is unavailable")
}
}
func TestConcurrentRequests(t *testing.T) {
rdb := miniredis.RunT(t)
client := redis.NewClient(&redis.Options{Addr: rdb.Addr()})
limiter := NewSlidingWindowCounterLimiter(client, 100, time.Minute)
key := "concurrent:test"
// Fire 200 concurrent requests, exactly 100 should succeed
var (
allowed atomic.Int64
wg sync.WaitGroup
)
for range 200 {
wg.Add(1)
go func() {
defer wg.Done()
ok, _, _ := limiter.Allow(context.Background(), key)
if ok {
allowed.Add(1)
}
}()
}
wg.Wait()
// Allow some tolerance for the sliding window approximation
if allowed.Load() < 95 || allowed.Load() > 105 {
t.Errorf("expected ~100 allowed requests, got %d", allowed.Load())
}
}
|
Observability
A rate limiter you can’t observe is a rate limiter you can’t tune.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
var (
rateLimitChecks = promauto.NewCounterVec(
prometheus.CounterOpts{
Name: "rate_limit_checks_total",
},
[]string{"result", "tier", "endpoint"},
// result: "allowed" | "rejected"
)
rateLimitRemaining = promauto.NewHistogramVec(
prometheus.HistogramOpts{
Name: "rate_limit_remaining_fraction",
Help: "Fraction of rate limit remaining at request time (0=empty, 1=full)",
Buckets: prometheus.LinearBuckets(0, 0.1, 11),
},
[]string{"tier"},
)
rateLimiterErrors = promauto.NewCounter(prometheus.CounterOpts{
Name: "rate_limiter_errors_total",
Help: "Rate limiter backend errors (fail-open count)",
})
)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# Prometheus alerts
- alert: HighRateLimitRejectionRate
expr: |
rate(rate_limit_checks_total{result="rejected"}[5m])
/ rate(rate_limit_checks_total[5m]) > 0.1
for: 5m
annotations:
summary: "More than 10% of requests are being rate limited"
description: "Possible abuse or misconfigured client. Check rate_limit_checks_total{result='rejected'}"
- alert: RateLimiterRedisErrors
expr: rate(rate_limiter_errors_total[5m]) > 1
annotations:
summary: "Rate limiter failing open — Redis connectivity issues"
|
Quick Reference: Implementation Checklist
Before shipping a rate limiter to production:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
- [ ] Algorithm chosen matches the use case (burst-tolerant vs strict)
- [ ] Operations are atomic (Lua script or pipeline — no TOCTOU)
- [ ] Keys are namespaced to avoid collisions across services
- [ ] Hash tags ensure cluster-compatible key co-location
- [ ] Fail-open behavior implemented for Redis outages
- [ ] RateLimit-* and X-RateLimit-* headers set on every response
- [ ] Retry-After header set on 429 responses
- [ ] 429 response body includes limit, remaining, and reset time
- [ ] Per-tier limits configured (free/pro/enterprise)
- [ ] Endpoint-specific limits where endpoints have different costs
- [ ] Test coverage for: at-limit, over-limit, concurrent, Redis-down
- [ ] Metrics: allowed rate, rejection rate, Redis errors
- [ ] Alerts: high rejection rate, Redis errors
- [ ] Documentation shows clients how to handle 429 with backoff
|
Related: API Design Principles, Caching Strategies, Designing for Observability, Redis Beyond Caching
Comments