Catalog My learning Blog
System Design Roadmap: 100-Day Course for Engineers · Phase 8 · Lesson 72 · 4 min read

Rate Limiting Algorithms: Token vs Leaky Bucket

On this page
  1. Why rate limiting needs an algorithm
  2. Rate limiting algorithms compared
  3. Rate limiting in ASP.NET Core and API gateways
  4. Distributed rate limiting across instances
  5. What to rate limit by: user, API key, IP or endpoint
  6. Check yourself

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.

Token bucket allows a burst up to its capacity; leaky bucket smooths all traffic to one constant output rate.
Token bucket allows a burst up to its capacity; leaky bucket smooths all traffic to one constant output rate.
AlgorithmBurstsOver-limit requestsMemory per client
Fixed windowUp to 2× at boundariesRejectedOne counter
Sliding window logNoneRejectedOne entry per request
Sliding window counterSmallRejectedTwo counters
Token bucketUp to capacity CRejectedToken count and timestamp
Leaky bucketAbsorbed, then smoothedQueued, dropped when fullA 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.

C#
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 /products and POST /exports cost 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.