Rate Limiting Algorithms

Rate limiting algorithms regulate how many requests a system accepts within a defined time window, preventing overload, resource exhaustion, and service degradation. They are essential in distributed systems where clients — from mobile apps to microservices — consume APIs at varying rates, and where backend services have finite capacity. This is especially critical under high load, during traffic spikes, or when external services impose quotas, such as in cloud infrastructure, payment gateways, or third-party data providers.

When to Apply Rate Limiting

Rate limiting is not a one-size-fits-all solution. Choose it when:

• A service exposes an API that clients can call frequently, and the backend has bounded capacity (e.g., database connections, CPU, memory).
• Clients (internal or external) may exceed expected request volumes, leading to cascading failures.
• You need to enforce usage tiers (e.g., free, premium, enterprise) with distinct request limits.
• A system must protect itself from abuse (e.g., DDoS, bot traffic) or external systems (e.g., throttling a third-party API).

Choosing a Rate Limiting Algorithm

The core trade-off is between simplicity, accuracy, and memory efficiency. The right algorithm depends on whether you need:

• Fixed window (simple, fast, but may allow bursts).
• Sliding window (accurate, supports fine-grained bursts, but more complex).
• Leaky bucket (smooths traffic, enforces average rate, good for consistent data flows).
• Token bucket (flexible, allows burstiness and gradual refill, widely used).

Fixed Window Algorithm

A fixed window divides time into equal intervals (e.g., 1 minute) and resets a counter at the start of each interval.

Request: GET /api/users/123
Headers:
  Authorization: Bearer abc123
  X-RateLimit-Key: user-123

At the start of each minute, the system resets a counter for user-123 to zero. Each request increments the counter. When the counter reaches the limit (e.g., 100 requests per minute), subsequent requests receive a 429 Too Many Requests response.

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 60

{
  "error": "Rate limit exceeded",
  "limit": 100,
  "remaining": 0,
  "reset": 1710000000
}

The X-RateLimit-* headers convey the current state:

• X-RateLimit-Limit: 100
• X-RateLimit-Remaining: 0
• X-RateLimit-Reset: 1710000000 (Unix timestamp)

Key failure modes:

• Bursts across window boundaries: 99 requests in the last second of minute 1, then 1 request in the first second of minute 2 — only 100 total, but 100 requests are accepted, even though the window is only 60 seconds.
• Clock skew: When the server clock drifts, window boundaries drift, leading to inconsistent rate limits across a cluster.

Configuration example (Redis-based):

rate_limiting:
  algorithm: fixed-window
  window_size: 60s
  max_requests: 100
  cache:
    type: redis
    host: redis.example.com
    port: 6379
    key_prefix: "rl:fixed:"

Sliding Window Algorithm

The sliding window tracks individual request timestamps and computes the number of requests in the last N seconds.

For each request, the system:

1. Records the request timestamp.
2. Filters all recorded timestamps to those within the last window_size seconds.
3. Returns the count of requests in that window.

HTTP/1.1 200 OK
Content-Type: application/json
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 87
X-RateLimit-Reset: 1710000000

{
  "id": 123,
  "name": "Alice"
}

Implementation with Redis (using sorted sets):

redis-cli ZADD rl:sliding:user-123 1709999900.123456 {request_id}
redis-cli ZREMRANGEBYSCORE rl:sliding:user-123 1709999900.123456 -inf (1709999900.123456 - 60)
redis-cli ZCARD rl:sliding:user-123

The ZCARD command returns the number of requests in the current window. The ZREMRANGEBYSCORE ensures only requests from the last 60 seconds remain.

Common pitfalls:

• Memory growth: Without periodic cleanup, the sorted set grows indefinitely. Use ZREMRANGEBYRANK or ZREMRANGEBYSCORE with a cleanup job.
• Inaccurate window edges: A request at t = 1709999900 is included in the window [1709999900, 1709999960], but a request at t = 1709999960.000001 is not included in the next window, even though it’s within 60 seconds of the previous request.

Leaky Bucket Algorithm

The leaky bucket enforces a constant output rate. Requests are queued in a buffer (the bucket), and the system outputs requests at a fixed rate (e.g., 10 requests per second), with the bucket draining at a fixed rate.

Data flow:

• Requests arrive at arbitrary intervals.
• Each request fills one "slot" in the bucket.
• The bucket drains at a fixed rate (e.g., 1 slot per 0.1 seconds).
• If the bucket is full, new requests are rejected or queued.

Implementation with a queue (e.g., RabbitMQ or Kafka):

{
  "queue": "rate-limiting-leaky",
  "max_capacity": 100,
  "drain_rate": 10,
  "drain_interval": 1.0
}

Each incoming request is published to the queue. A worker process continuously polls the queue and processes one request every 1 / drain_rate seconds.

Error response when the bucket is full:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 10

{
  "error": "Leaky bucket full",
  "bucket_capacity": 100,
  "current_fill": 100,
  "drain_rate": 10,
  "next_available": 1710000015
}

Key characteristics:

• Smooth output: Even if requests arrive in bursts, the service receives requests at a steady rate.
• Predictable latency: Requests are delayed by up to max_capacity / drain_rate seconds.
• Memory efficient: Only requires a queue and a counter.

Failure modes:

• Drain rate mismatch: If the worker processes requests faster than the drain rate, the queue empties and the system waits for new requests.
• Bursts with high latency: A burst of 200 requests into a bucket of 100 slots causes a 10-second delay before the first request is processed.

Token Bucket Algorithm

The token bucket allows flexible, bursty traffic. Tokens are added to a bucket at a fixed rate. Each request consumes one token. If tokens are available, the request is accepted; otherwise, it is rejected or queued.

Data flow:

• The bucket starts with initial_tokens.
• Tokens are added at fill_rate per second.
• A request consumes one token; if none are available, it is rejected.

Implementation using Redis:

# On request arrival:
redis-cli INCRBY rl:token:api-key-abc123 1
redis-cli EXPIRE rl:token:api-key-abc123 60
redis-cli GET rl:token:api-key-abc123

The INCRBY command adds one token (or increments the counter). The EXPIRE ensures the key is removed after the window.

Response when token is available:

HTTP/1.1 200 OK
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 98
X-RateLimit-Reset: 1710000000

When no tokens are available:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 5

{
  "error": "Token bucket depleted",
  "limit": 100,
  "remaining": 0,
  "next_available": 1710000005
}

Configuration:

rate_limiting:
  algorithm: token-bucket
  initial_tokens: 10
  fill_rate: 10
  window_size: 60s
  cache:
    type: redis
    key: "rl:token:{key}"

Subtle points:

• Token refill granularity: The rate is not perfectly continuous. If the system updates the token count every 10 seconds, a burst of 100 requests in 5 seconds may not fully utilize the bucket.
• Hybrid approach: Combine token bucket with fixed window to allow both burst and smooth rate.

Selecting the Right Algorithm

Goal	Algorithm	Why
Simple, fast, low memory	Fixed window	Easy to implement, ideal for edge services
Accurate burst detection	Sliding window	Prevents window boundary overflows
Smooth, predictable output	Leaky bucket	Ideal for streaming, real-time systems
Flexible bursts and average rate	Token bucket	Best for APIs with varied client behavior

Common Patterns and Pitfalls

• Combining algorithms: Use token bucket for per-user limits and fixed window for global limits. The global limit is applied after the per-user limit.
• Hierarchical rate limiting: A service may apply limits at the API level, user level, and client key level simultaneously.
• Fallback strategies:
• If the cache (e.g., Redis) is down, fall back to in-memory counters.
• If the rate limiter is unavailable, return 429 with Retry-After and X-RateLimit-Remaining.
• Client-side handling:
• Clients should respect Retry-After and retry with exponential backoff.
• Use X-RateLimit-* headers to dynamically adjust client behavior.

Error Handling and Response Contracts

All rate limiters return a standard set of headers:

• X-RateLimit-Limit: The maximum number of requests allowed.
• X-RateLimit-Remaining: The number of requests remaining in the current window.
• X-RateLimit-Reset: The timestamp (Unix) when the window resets.
• Retry-After: The number of seconds to wait before retrying.

When a request exceeds the limit, the response body includes:

{
  "error": "Rate limit exceeded",
  "details": {
    "limit": 100,
    "remaining": 0,
    "reset": 1710000000,
    "window": "minute",
    "type": "fixed-window"
  }
}

Failure modes:

• Clock drift across services: A service receives a request at t = 1710000000, but the rate limiter expects t = 1710000005, causing a misalignment.
• Cache invalidation: A key is invalidated in Redis but not updated in the primary database, leading to inconsistent rate limits.
• Race conditions: Two requests arrive nearly simultaneously and both update the counter, but only one wins.

Summary

Rate limiting algorithms are the backbone of API resilience. The choice between fixed window, sliding window, leaky bucket, and token bucket depends on the required accuracy, burst tolerance, and resource constraints. Each algorithm has subtle behaviors and failure modes that are not immediately apparent. Implementing them effectively requires attention to response contracts, error handling, and fallback strategies. The real challenge lies not in applying an algorithm, but in understanding the trade-offs and making them visible through consistent, predictable responses.

This page was rewritten on 18 October 2026. It replaced a templated version that was not specific to its own title. How these pages are written and checked. If anything here is wrong, tell us at [email protected] and we will correct it.