system-design · intermediate

Rate Limiting Algorithms — Token Bucket, Windows, and Bursts

The Central Question

Consider an enterprise API platform running on the TrafficLab platform (trafficlab.com) processing 50,000 requests per second across global microservices:

• During a breaking news event or high-traffic product release:
• Client A (a partner app with a bug) executes a tight loop sending 15,000 HTTP requests per second to /v1/forecast.
• The backend CPU hits 100%, memory exhausts, and database connection pools lock up.
• Clients B, C, and D receive HTTP 503 Service Unavailable errors because Client A consumed all available system capacity.

Rate limiting is the operational control mechanism that caps how many requests a client may execute within a designated time window, protecting backend stability and maintaining fair resource allocation across tenants.

This lesson answers one central question: How do rate limiting algorithms (Token Bucket, Leaky Bucket, Fixed Window Counter, Sliding Window Counter) govern API traffic volume, mathematically manage bursts, and enforce fairness using distributed Redis storage patterns?

The Four Core Rate Limiting Algorithms

Engineers implement rate limits using four primary algorithms, each offering different trade-offs between memory efficiency, burst tolerance, and traffic smoothness:

flowchart TD
  Alg[Rate Limiting Algorithms] --> FB[1. Fixed Window Counter]
  Alg --> SW[2. Sliding Window Counter]
  Alg --> TB[3. Token Bucket]
  Alg --> LB[4. Leaky Bucket]
  
  FB --> FBDesc["Resets count on fixed time boundaries (e.g. 1 minute). Simple, but prone to 2x boundary spikes."]
  SW --> SWDesc["Calculates weighted average across window boundaries. Prevents boundary spikes with minimal memory."]
  TB --> TBDesc["Refills tokens continuously up to capacity. Supports short bursts while capping average rate."]
  LB --> LBDesc["Drains requests at a constant output rate using a queue. Smooths traffic bursts into a steady flow."]

Figure 1: Overview of the four primary rate limiting algorithms.

1. Fixed Window Counter Algorithm

The Fixed Window Counter algorithm divides time into static, fixed intervals (such as 1-minute windows: 12:00:00 - 12:01:00, 12:01:00 - 12:02:00). Each window maintains an isolated request counter per client.

gantt
    title Fixed Window Boundary Spike Vulnerability (Limit: 100 req/min)
    dateFormat  ss
    axisFormat %S
    section Window 1 (12:00)
    Idle Period :done, w1a, 00, 50
    50 reqs sent (12:00:50) :active, w1b, 50, 60
    section Window 2 (12:01)
    100 reqs sent (12:01:00) :crit, w2a, 60, 70
    Idle Period :done, w2b, 70, 120

Figure 2: The boundary burst vulnerability in fixed windows allowing twice the allowed rate across window edges.

Mathematical Mechanics

• Let $T_{\text{window}} = 60\text{ seconds}$. Limit $N = 100\text{ requests}$.
• Counter Key: rate_limit:user_42:window_1201.
• If $\text{Counter} < N$: Increment counter and ALLOW request.
• Else: DENY request with HTTP 429.

The Boundary Burst Vulnerability

• Both individual windows see 100 requests (under the limit).
• In reality, the system processed 200 requests within 1 second of wall clock time, breaching the intended rate cap by $200\%$.

2. Sliding Window Counter Algorithm

The Sliding Window Counter algorithm resolves boundary spikes without storing raw timestamp logs by combining the request count of the current window with a weighted percentage of the previous window count.

flowchart LR
  subgraph Previous Window (12:00)
    PCount["Previous Count: 80 Requests"]
  end
  subgraph Current Window (12:01 - 36 Seconds Elapsed)
    CCount["Current Count: 30 Requests"]
  end
  subgraph Sliding Window Math
    Calc["Weight = (60 - 36) / 60 = 40%<br/>Estimated Rate = (80 * 0.40) + 30 = 62 Requests"]
  end
  
  PCount --> Calc
  CCount --> Calc

Figure 3: Calculating weighted request rates in the Sliding Window Counter algorithm.

Mathematical Formula

$$\text{Estimated Rate} = \text{Count}_{\text{current}} + \left( \text{Count}_{\text{previous}} \times \frac{W - t_{\text{elapsed}}}{W} \right)$$

3. Token Bucket Algorithm

The Token Bucket algorithm is the industry standard for public web APIs (such as Stripe and AWS). It maintains a bucket containing tokens up to a maximum Capacity ($C$), refilling tokens continuously at a fixed Refill Rate ($R$) per second.

flowchart TB
  Refill["Refill Generator: Adds R Tokens/sec"] --> Bucket["Token Bucket (Max Capacity: C)"]
  Req[Incoming HTTP Request] --> Check{Token Available?}
  Bucket -->|Check Balance| Check
  Check -->|Yes: Consume 1 Token| Allow[HTTP 200 OK: Request Allowed]
  Check -->|No: Zero Tokens| Deny[HTTP 429 Too Many Requests]

Figure 4: State machine governing token consumption and refill in the Token Bucket algorithm.

Mathematical Mechanics

$$\text{Tokens}_{\text{new}} = \min\left(C, \; \text{Tokens}_{\text{stored}} + (t_{\text{now}} - t_{\text{last}}) \times R\right)$$

4. Leaky Bucket Algorithm

The Leaky Bucket algorithm smooths traffic bursts into a steady, constant output rate using a First-In, First-Out (FIFO) queue.

flowchart TB
  BurstyInput["Bursty Traffic In: 100 reqs/sec"] --> BucketQueue["Leaky Bucket Queue (Capacity: 50)"]
  BucketQueue -->|Queue Full| Drop[HTTP 429 / Drop]
  BucketQueue -->|Drain at Fixed Rate| Outflow["Smooth Traffic Out: 10 reqs/sec"]
  Outflow --> Server[Backend Application]

Figure 5: Converting bursty input traffic into smooth outflow using the Leaky Bucket algorithm.

Complete Worked Example: Production Go Token Bucket Implementation

Let's inspect a complete, thread-safe Go implementation of the Token Bucket rate limiter for the TrafficLab platform (trafficlab.com).

package main
import (
	"fmt"
	"math"
	"sync"
	"time"
)
type TokenBucket struct {
	mu           sync.Mutex
	capacity     float64
	tokens       float64
	refillRate   float64 // Tokens per second
	lastRefilled time.Time
}
func NewTokenBucket(capacity float64, refillRate float64) *TokenBucket {
	return &TokenBucket{
		capacity:     capacity,
		tokens:       capacity,
		refillRate:   refillRate,
		lastRefilled: time.Now(),
	}
}
func (tb *TokenBucket) Allow() bool {
	tb.mu.Lock()
	defer tb.mu.Unlock()
now := time.Now()
	elapsed := now.Sub(tb.lastRefilled).Seconds()
	tb.lastRefilled = now
// 1. Refill tokens lazily
	tb.tokens = math.Min(tb.capacity, tb.tokens+elapsed*tb.refillRate)
// 2. Consume token if available
	if tb.tokens >= 1.0 {
		tb.tokens -= 1.0
		return true
	}
return false
}
func main() {
	limiter := NewTokenBucket(5, 1) // Capacity: 5, Refill: 1 token/sec
// Simulate 10 rapid request bursts
	for i := 1; i <= 10; i++ {
		if limiter.Allow() {
			fmt.Printf("Request %d: ALLOWED (HTTP 200)\n", i)
		} else {
			fmt.Printf("Request %d: DENIED (HTTP 429 Too Many Requests)\n", i)
		}
		time.Sleep(100 * time.Millisecond)
	}
}

Failure Modes and Engineering

Rate Limit Tier Matrix

Hierarchical Rate Limiting & Multi-Layer Quotas

1. Global Gateway Limit (e.g. Max 50,000 RPS across the entire platform to protect edge load balancers).
2. Tenant Account Limit (e.g. Max 1,000 RPS per customer account to enforce billing contract tiers).
3. Endpoint-Specific Limit (e.g. Max 5 RPS on POST /v1/reports/export to prevent CPU-intensive database queries).

Dynamic Rate Limits During Incidents

Rate Limiting Key Selection Best Practices

• By API Key / JWT Account ID: Best for authenticated developer APIs, ensuring account-wide quota enforcement across multiple user devices.
• By IP Address: Best for un-authenticated routes (login, registration), but requires handling shared NAT proxies to avoid blocking corporate networks.

What You Should Remember

1. Rate limiting protects stability and fairness: Rate limits prevent a single buggy or malicious client from consuming all system capacity.
2. Token Bucket supports controlled bursts: Token Bucket ($C, R$) allows short request spikes up to capacity $C$ while enforcing long-term average rate $R$.
3. Leaky Bucket forces constant outflow: Leaky Bucket queues requests to output a smooth, constant execution rate, ideal for traffic shaping.
4. Use Redis Lua scripts for distributed enforcement: Atomic Lua script execution in Redis prevents concurrency race conditions across multi-node gateway pools.
5. Return standard 429 headers: Always return HTTP 429 Too Many Requests with Retry-After headers and RFC 7807 error details.

Glossary of Terms

Practice Scenario and Self-Assessment

Architecture Scenario

1. GET /v1/market/prices (High volume, lightweight read)
2. POST /v1/trading/orders (Critical mutation, sensitive to database lock contention)
3. POST /v1/auth/login (Authentication endpoint, target for brute-force attacks)

1. Recommend the optimal rate limiting algorithm (Token Bucket vs Sliding Window vs Fixed Window) and policy configuration for each endpoint.
2. Formulate how your Token Bucket implementation calculates token refills lazily without running background timer threads.

Interactive Self-Assessment

It supports controlled traffic bursts up to capacity C while preventing 2x boundary spikes.

It consumes zero memory in Redis databases.

It forces incoming requests to execute at a strictly constant output rate.

It eliminates the need for HTTP 429 status codes.

It guarantees atomic, thread-safe execution, preventing multi-instance concurrency race conditions.

It allows client web browsers to execute rate limiting math locally.

It bypasses the need for in-memory key storage in Redis.

It converts HTTP status codes to TCP transport packets.

What to Learn Next

• Distributed Rate Limiting — Scaling Enforcement Across Microservices: Explore Redis Lua scripting and local batching synchronization.
• Circuit Breakers & Cascading Failure Control: Learn how to isolate downstream dependencies during outages.
• Backpressure — Flow Control Between Producers and Consumers: Discover stream flow control and reactive buffer management.

Track: Distributed Systems

Next: Design a URL Shortener — Interview Walkthrough

Series: Rate Limiting

1. Rate Limiting Algorithms — Token Bucket, Windows, and Bursts (this guide)
2. Rate Limiter Design — Case Study
3. Distributed Rate Limiting — Shared Quotas Across Many Pods
4. Circuit Breakers & Rate Limiting Together

All series

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab