Rate Limiting Algorithms: Token vs Leaky Bucket
On this page
Why rate limiting needs an algorithm
Your API needs limits: to stop one client from starving others, to protect the database, and to control cost. "100 requests per minute" sounds simple until you ask: can a client send all 100 in the first second? What happens to request 101: rejected or delayed? The algorithm answers those questions.
Rate limiting algorithms compared
Fixed window counter. Count requests per client per calendar minute; reset at the boundary. Tiny and simple. Weakness: 100 requests at 12:00:59 and 100 more at 12:01:00 means 200 in two seconds.
Sliding window. Count requests in the last 60 seconds, either exactly (store each timestamp) or approximately (weight the previous window's count by how much of it still overlaps). No boundary burst.
Token bucket. A bucket holds up to C tokens and refills at r tokens per second. Each request takes a token; with none left, the request is rejected. Bursts up to C are allowed, and the long-run rate is capped at r. Real clients are bursty (a page load fires ten API calls at once), so this matches them well.
Leaky bucket. Requests enter a queue (the bucket) and leave at a constant rate; when the queue is full, new requests are dropped. Output is perfectly smooth regardless of input bursts, at the cost of added waiting. Good in front of something that can only handle a steady rate, such as a partner API or a legacy system.
| Algorithm | Bursts | Over-limit requests | Memory per client |
|---|---|---|---|
| Fixed window | Up to 2× at boundaries | Rejected | One counter |
| Sliding window log | None | Rejected | One entry per request |
| Sliding window counter | Small | Rejected | Two counters |
| Token bucket | Up to capacity C | Rejected | Token count and timestamp |
| Leaky bucket | Absorbed, then smoothed | Queued, dropped when full | A queue |
Rate limiting in ASP.NET Core and API gateways
ASP.NET Core ships rate limiting middleware (Microsoft.AspNetCore.RateLimiting) with fixed window, sliding window, token bucket and concurrency limiters. Gateways such as NGINX (limit_req, a leaky bucket), Envoy and cloud API gateways provide the same at the edge.
builder.Services.AddRateLimiter(o => o.AddTokenBucketLimiter("api", opt =>
{
opt.TokenLimit = 100; // bucket capacity: burst size
opt.TokensPerPeriod = 20; // refill 20 tokens...
opt.ReplenishmentPeriod = TimeSpan.FromSeconds(10); // ...every 10 seconds = 2/s average
opt.QueueLimit = 0; // reject instead of queueing
}));Distributed rate limiting across instances
These in-process limiters count per instance. With four API instances behind a load balancer, each enforces the full limit separately, so a client gets up to four times its quota. Options:
- Shared state in Redis with an atomic script per request (Day 20; the Redis course and the System Design Interview course include tested scripts). Exact, at the cost of a Redis call.
- Divide the limit by instance count locally. Cheap, approximate, and wrong whenever the count changes.
- Limit at the gateway in front of all instances.
Return 429 Too Many Requests with Retry-After and quota headers, so well-behaved clients back off.
What to rate limit by: user, API key, IP or endpoint
The key you count against matters as much as the algorithm:
- API key or user id is the fairest for authenticated traffic: each customer gets their own quota.
- IP address works for anonymous traffic, with two traps. A whole office or mobile carrier can share one public IP behind NAT, so a per-IP limit blocks thousands of innocent users at once. And with IPv6, one client may control a huge range of addresses, so limit by the /64 prefix rather than the full address.
- Per endpoint, because
GET /productsandPOST /exportscost very different amounts. A cheap endpoint can allow hundreds a minute; an expensive one, a few.
For endpoints where each request holds resources for a long time, a concurrency limit, at most 5 reports running per customer, protects better than a rate. ASP.NET Core's middleware includes a concurrency limiter for exactly this.
Check yourself
A token bucket with a capacity of 50 tokens and a refill rate of 5 tokens per second. A client that's been quiet has a full bucket and can send 50 requests at once, but sustained traffic is limited by the refill rate, so the long-run average can't exceed 5 per second.
When the downstream needs a smooth, constant rate, for example a partner API with a strict per-second limit, and queueing delay is acceptable.
The company's staff share one public IP behind NAT, so their requests add up. Limit authenticated traffic by user or API key, and keep IP limits coarse.
Up to 400 per minute, because each instance counts only the requests it sees and the load balancer spreads the client's traffic across all four. To enforce a true limit, keep the counters in a shared store such as Redis, or enforce the limit once, at the gateway.