Rate Limiting Algorithms | Token Bucket, Leaky Bucket, and Sliding Window Explained

Rate limiting algorithms are the mechanisms that enforce how many requests a client can make within a defined time window. The algorithm you choose determines how burst traffic is handled, how fairly limits are enforced, and how accurately the window is measured.

TL;DR The four main rate limiting algorithms are: fixed window counter (simple but vulnerable to boundary bursts), sliding window log (accurate but memory-intensive), sliding window counter (good balance of accuracy and efficiency), token bucket (allows controlled bursts), and leaky bucket (smooths output to a constant rate). Token bucket is the most common for API rate limiting because it allows short bursts while still enforcing an average rate. Leaky bucket is preferred when consistent output rate matters more than allowing bursts.

Why rate limiting algorithms matter

Rate limiting without a well-chosen algorithm creates two common failure modes:

1. The boundary burst problem — A naive fixed window allows 2× the intended rate at window boundaries. If the limit is 100 req/min, a client can send 100 requests at 11:59:59 and 100 more at 12:00:00 — 200 requests in 2 seconds.
2. Bursty vs smooth traffic — Some use cases require smooth, consistent output (payment processing, database writes). Others legitimately need short bursts (page loads that trigger multiple API calls simultaneously). The wrong algorithm punishes legitimate users or fails to protect the backend.

Fixed window counter

How it works: Divide time into fixed windows (e.g., 1-minute intervals). Count requests per client in the current window. If the count exceeds the limit, reject requests until the next window starts.

Window: 12:00:00 – 12:00:59
Limit: 100 requests

Client sends 80 requests at 12:00:05 → allowed (count: 80)
Client sends 30 more at 12:00:45 → rejected (count would be 110)
Window resets at 12:01:00 → client can send 100 again

The boundary burst problem:

Window 1: 12:00:00 – 12:00:59 → 100 requests at 12:00:55 ✓
Window 2: 12:01:00 – 12:01:59 → 100 requests at 12:01:05 ✓
Result: 200 requests in 10 seconds — 2× the intended rate

Pros: Simple to implement, low memory (one counter per client per window). Cons: Allows up to 2× burst at window boundaries.

Sliding window log

How it works: Store a timestamp for every request. When a new request arrives, count how many requests occurred in the last N seconds (the rolling window). If the count is below the limit, allow the request and add the timestamp.

Limit: 5 requests per 60 seconds
Current time: 12:05:30

Stored timestamps: [12:04:40, 12:05:00, 12:05:10, 12:05:20, 12:05:25]
Count in last 60s: 5 → reject new request

Pros: Perfectly accurate — no boundary burst problem. Cons: Memory-intensive (stores every request timestamp). For 1M users at 100 req/min, that’s 100M timestamp entries.

Sliding window counter

How it works: A practical approximation of the sliding window log. Maintains counters for the current and previous fixed windows, then estimates the count in the rolling window using the previous window’s count weighted by how much of that window overlaps with the current rolling window.

Limit: 100 req/min
Previous window count: 80
Current window count: 30
Current position: 75% through current window (45 seconds in)

Estimated count = (80 × 0.25) + 30 = 20 + 30 = 50 → allow request

Pros: Low memory (two counters per client), accurate enough for most use cases, no boundary burst problem. Cons: Approximate — may occasionally allow slightly more than the limit.

Token bucket

How it works: Each client has a bucket with a maximum capacity of N tokens. Tokens are added at a fixed rate (refill rate). Each request consumes one token. If the bucket is empty, the request is rejected or queued.

Bucket capacity: 20 tokens
Refill rate: 10 tokens/second

Client does nothing for 2 seconds → bucket fills to 20 tokens
Client sends 15 requests instantly → bucket has 5 tokens (allowed burst)
Client sends 6 more → rejected (only 5 tokens left)
After 0.1 seconds → 1 new token → can send 1 more request

Key property: Allows bursts up to the bucket capacity, while enforcing the average refill rate over time. A client that has been idle can accumulate tokens and spend them in a burst — this models legitimate user behavior (page load triggering multiple API calls).

Pros: Allows controlled bursts, simple conceptually, widely used. Cons: Two parameters to tune (capacity and refill rate). Clients can “save up” large bursts if they’ve been idle.

Leaky bucket

How it works: Requests go into a queue (the bucket). They are processed at a constant rate — the “leak” rate. If the queue is full, new requests are rejected.

Leak rate: 10 requests/second
Queue capacity: 50 requests

100 requests arrive at once:
→ 50 enter the queue (capacity full)
→ 50 are rejected
→ Queue drains at 10 req/sec → takes 5 seconds to empty

Key property: Output is always smooth and constant, regardless of input burstiness. Requests are never processed faster than the leak rate.

Pros: Guarantees consistent output rate, prevents backend overload from burst traffic. Cons: Does not allow any bursting — even short, legitimate bursts are queued or rejected. Higher latency during bursts (requests wait in queue). Less intuitive for per-user API rate limits.

Comparing the algorithms

Distributed rate limiting

Single-server rate limiting is straightforward — counters live in memory. In distributed systems (multiple API gateway instances), the counter must be shared:

• Centralized store (Redis) — All instances increment the same counter in Redis. Atomic INCR + EXPIRE operations ensure consistency. ~1ms overhead per request.
• Local approximation — Each instance tracks a local counter and periodically syncs with a central store. Less accurate but lower latency.
• Consistent hashing — Route each client to the same instance based on client ID. Avoids shared state but reduces load balancing flexibility.

Redis-based rate limiting is the most common production approach: INCR key, check against limit, set EXPIRE if it’s the first request in the window.

Frequently asked questions

What is the most common rate limiting algorithm? Token bucket is the most widely used for API rate limiting because it allows short, legitimate bursts (like a page load triggering 5 API calls simultaneously) while still enforcing an average rate. Most API gateways and cloud rate limiting products use token bucket or sliding window counter.

What is the difference between token bucket and leaky bucket? Token bucket allows bursts — clients can accumulate tokens when idle and spend them quickly. Leaky bucket produces a constant output rate regardless of input patterns — requests are queued and processed at a fixed rate, no bursting allowed. Token bucket is better for APIs where burst is legitimate. Leaky bucket is better for backend protection where constant throughput is required.

What is the boundary burst problem in fixed window rate limiting? A fixed window resets completely at the window boundary. A client can send the maximum allowed requests at the very end of one window and the maximum allowed at the very start of the next — effectively sending 2× the intended rate in a short burst. Sliding window algorithms eliminate this problem.

How do I implement rate limiting in a distributed system? Use a shared atomic counter in Redis or another distributed cache. The standard Redis pattern: INCR <key> (increment the counter), then check if it exceeds the limit, and set EXPIRE <key> <window_seconds> if this is the first request (to create the time window). This handles concurrent requests correctly using Redis’s atomic operations.

What HTTP status code does rate limiting return? 429 Too Many Requests is the standard status code for rate limiting responses. Include a Retry-After header indicating when the client can make another request. Many APIs also include X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset headers to help clients manage their request rates.

What is the difference between rate limiting and throttling? Rate limiting enforces a hard limit — requests over the limit are rejected. Throttling slows requests down — excess requests are queued and delayed rather than rejected. Rate limiting is simpler and more predictable. Throttling keeps more requests alive but can increase latency during high load.

Should rate limits be applied per IP or per user? Both. Per-IP limits protect against attacks from single sources. Per-user limits enforce fair use policies for authenticated clients. Per-IP alone is ineffective against distributed attacks using many IPs. Per-user alone doesn’t protect unauthenticated endpoints. A layered approach applies both.

How do I choose between sliding window and token bucket? Use sliding window counter when you need to enforce a strict requests-per-time-period limit (e.g., “100 requests per minute”) with no burst allowance. Use token bucket when clients legitimately need bursts (e.g., “burst of 20, then sustain 10/second”) — like page loads that fire multiple API calls simultaneously.