Rate limiting algorithms and where to enforce them

HOW IT FITS TOGETHER

KEY TERMS

Token bucket and leaky bucket

A token bucket has capacity B and refill rate R: it permits a burst of B, then R per second. A leaky bucket drains requests at a fixed rate; as a meter it is mathematically equivalent, as a queue it delays instead of rejecting. Neither needs a timer: compute refill lazily from the elapsed time on each request.

Window counters

A fixed window counts per calendar interval (INCR plus EXPIRE), so a client can send the full limit at 00:59 and again at 01:00. A sliding window counter estimates the rolling count as previous × (time left in the window fraction) + current, which removes most of the edge burst with two integers. A sliding log stores every timestamp and is exact but costs memory proportional to the limit.

GCRA

The generic cell rate algorithm stores one value per key: the theoretical arrival time (TAT). Each request advances TAT by the emission interval (period / rate); it is allowed if TAT minus the burst tolerance is not in the future. Same behaviour as a token bucket, but a single timestamp is cheap to keep and update atomically in Redis, and remaining quota and retry time fall out of the arithmetic.

Choosing the key

IP is available before authentication but punishes NAT, mobile carriers and corporate proxies, and IPv6 makes per-address limits trivial to evade (limit by /64 instead). API key, tenant or user ID are fair and stable but only exist after authentication. Sensitive actions need composite keys: per account and per IP for login, so neither a botnet nor one attacker against many accounts gets through. Behind a proxy, derive the client IP from a trusted header only.

Local vs distributed

In-process limiters are fast and need no network, but with N instances the effective limit is N × limit and depends on load balancing. A shared store (Redis) gives one global count at the cost of a round trip, so do the read-modify-write atomically in a Lua script or module, use the store's clock rather than each app server's, and decide whether to fail open (availability) or closed (protection) when it is down.

Telling the client

Reject with 429 and Retry-After (seconds or an HTTP date, RFC 9110). The IETF RateLimit-Policy and RateLimit fields (draft-ietf-httpapi-ratelimit-headers, still an Internet-Draft at -11) express quota, remaining units and reset time in structured form; many APIs still send the older de facto X-RateLimit-Limit/Remaining/Reset headers. Document which ones you send.

IN YOUR STACK

type Bucket = { tokens: number; updatedAt: number };

export class TokenBucketLimiter {
  private buckets = new Map<string, Bucket>();
  constructor(private capacity: number, private refillPerSec: number, private now = () => performance.now()) {}

  take(key: string, cost = 1): { allowed: boolean; retryAfterMs: number } {
    const t = this.now();
    const b = this.buckets.get(key) ?? { tokens: this.capacity, updatedAt: t };
    // Lazy refill: no timers, only the time elapsed since this key's last request.
    b.tokens = Math.min(this.capacity, b.tokens + ((t - b.updatedAt) / 1000) * this.refillPerSec);
    b.updatedAt = t;
    this.buckets.set(key, b);
    if (b.tokens >= cost) return (b.tokens -= cost), { allowed: true, retryAfterMs: 0 };
    return { allowed: false, retryAfterMs: Math.ceil(((cost - b.tokens) / this.refillPerSec) * 1000) };
  }
}
const limiter = new TokenBucketLimiter(20, 5); // burst of 20, then 5 requests/second
export function guard(userId: string): Response | null {
  const { allowed, retryAfterMs } = limiter.take(`user:${userId}`);
  return allowed ? null : new Response("Too Many Requests", {
    status: 429, headers: { "Retry-After": String(Math.ceil(retryAfterMs / 1000)) },
  });
}

-- Sliding window counter. KEYS[1] = "rl:{key}", ARGV[1] = limit, ARGV[2] = window ms
-- EVALSHA <sha> 1 rl:{apikey:abc} 100 60000  ->  {allowed, remaining, retry_ms}
local limit, window = tonumber(ARGV[1]), tonumber(ARGV[2])
local t = redis.call('TIME') -- one clock for every app server
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local win = math.floor(now / window)
local s = redis.call('HMGET', KEYS[1], 'win', 'cur', 'prev')
local w, cur, prev = tonumber(s[1]) or win, tonumber(s[2]) or 0, tonumber(s[3]) or 0
if w == win - 1 then prev, cur = cur, 0 elseif w < win - 1 then prev, cur = 0, 0 end

local into = (now % window) / window -- fraction of the current window elapsed
local estimate = prev * (1 - into) + cur
if estimate + 1 > limit then
  -- Retry when the estimate drops below the limit: either prev's weight decays
  -- enough in this window, or, after the boundary, cur (now prev) decays enough.
  local need, left = estimate + 1 - limit, window - now % window
  local retry
  if prev > 0 and need / prev * window <= left then
    retry = math.ceil(need / prev * window)
  else
    retry = left + math.ceil(math.max(0, 1 - (limit - 1) / cur) * window)
  end
  return {0, 0, retry}
end
cur = cur + 1
redis.call('HSET', KEYS[1], 'win', win, 'cur', cur, 'prev', prev)
redis.call('PEXPIRE', KEYS[1], window * 2)
return {1, math.floor(limit - estimate - 1), 0}

// import "github.com/go-redis/redis_rate/v10" plus fmt, math, net/http, strconv, time

func TenantLimit(limiter *redis_rate.Limiter, next http.Handler) http.Handler {
	limit := redis_rate.Limit{Rate: 600, Burst: 60, Period: time.Minute}
	return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
		res, err := limiter.Allow(r.Context(), "tenant:"+tenantID(r), limit)
		if err != nil { // Redis unavailable: fail open, but alert on it
			next.ServeHTTP(w, r)
			return
		}
		w.Header().Set("RateLimit-Policy", fmt.Sprintf(`"tenant";q=%d;w=60`, limit.Rate))
		w.Header().Set("RateLimit", fmt.Sprintf(`"tenant";r=%d;t=%d`, res.Remaining, int(math.Ceil(res.ResetAfter.Seconds()))))
		if res.Allowed == 0 {
			w.Header().Set("Retry-After", strconv.Itoa(int(math.Ceil(res.RetryAfter.Seconds()))))
			http.Error(w, "rate limit exceeded", http.StatusTooManyRequests)
			return
		}
		next.ServeHTTP(w, r)
	})
}

http {
    # 1 MB holds about 16k IPv4 states; 10 MB is plenty for most single-host setups.
    limit_req_zone $binary_remote_addr zone=per_ip:10m  rate=10r/s;
    limit_req_zone $http_x_api_key     zone=per_key:10m rate=600r/m;
    limit_req_status 429;          # default is 503
    limit_req_log_level warn;

    server {
        location /api/ {
            limit_req zone=per_ip  burst=20 nodelay;   # allow short spikes, reject beyond
            limit_req zone=per_key burst=50 delay=10;  # first 10 immediate, rest smoothed
            proxy_pass http://app;
        }

        location = /login {
            limit_req zone=per_ip burst=5;             # queued and delayed, never bursty
            proxy_pass http://app;
        }
    }
}

# Add a rule to the zone's http_ratelimit phase entry point ruleset.
curl "https://api.cloudflare.com/client/v4/zones/$ZONE_ID/rulesets/$RULESET_ID/rules" \
  --request POST \
  --header "Authorization: Bearer $CLOUDFLARE_API_TOKEN" \
  --header "Content-Type: application/json" \
  --data '{
    "description": "Login: 5 attempts per minute per IP",
    "expression": "(http.request.uri.path eq \"/login\" and http.request.method eq \"POST\")",
    "action": "block",
    "ratelimit": {
      "characteristics": ["cf.colo.id", "ip.src"],
      "period": 60,
      "requests_per_period": 5,
      "mitigation_timeout": 600
    }
  }'
# Get $RULESET_ID from GET /zones/$ZONE_ID/rulesets/phases/http_ratelimit/entrypoint

type perKey struct {
	mu       sync.Mutex
	limiters map[string]*rate.Limiter // evict idle keys periodically in production
}

func (p *perKey) get(key string) *rate.Limiter {
	p.mu.Lock()
	defer p.mu.Unlock()
	l, ok := p.limiters[key]
	if !ok {
		l = rate.NewLimiter(rate.Every(200*time.Millisecond), 10) // 5/s, burst 10
		p.limiters[key] = l
	}
	return l
}
// Inbound: drop with Allow().
func (p *perKey) allow(userID string) bool { return p.get(userID).Allow() }
// Outbound: wait with Wait(), to stay under a vendor's 10 requests/second.
var vendor = rate.NewLimiter(10, 1)
func callVendor(ctx context.Context, req *http.Request) (*http.Response, error) {
	if err := vendor.Wait(ctx); err != nil {
		return nil, err // context cancelled, or the wait would exceed its deadline
	}
	return http.DefaultClient.Do(req.WithContext(ctx))
}

WHEN TO REACH FOR WHAT

WHERE IT BITES

• Limiting only by IP: whole offices and mobile carriers share one address, and IPv6 or residential proxies give attackers endless ones.
• Using X-Forwarded-For as the key without validating which proxy set it; clients can send any value and get a fresh bucket per request.
• In-process limiters behind a load balancer, giving an effective limit of instances × limit that changes every time you autoscale.
• Non-atomic GET then SET in Redis, so concurrent requests all pass the check. Use a Lua script, a module, or INCR-first logic.
• Returning 500 or a generic error instead of 429 with Retry-After, which makes clients retry immediately and turns a limit into a retry storm.
• Counting failed and successful logins in one bucket per IP only; credential stuffing spreads across IPs, so also limit per target account.

WHEN IT BREAKS IN PRODUCTION

• A third-party API starts returning 429
• The login endpoint is hammered with leaked passwords
• A brief blip turns into a long outage
• The database spikes when a hot cache key expires
• Memory balloons when producers outpace consumers

SOURCES

• IETF draft: RateLimit header fields for HTTP (draft-ietf-httpapi-ratelimit-headers) (opens in new tab)Checked 2026-11-06
• MDN: Retry-After (opens in new tab)Checked 2026-11-06
• Brandur Leach: Rate limiting, Cells, and GCRA (opens in new tab)Checked 2026-11-06
• nginx: ngx_http_limit_req_module (opens in new tab)Checked 2026-11-06
• Cloudflare: Rate limiting rules (opens in new tab)Checked 2026-11-06
• Redis: Scripting with Lua (opens in new tab)Checked 2026-11-06