Rate Limiting — Algorithmics

“100 requests per minute” sounds unambiguous. It is not — and the difference between readings is the difference between a working limiter and one that lets through twice what you promised.

Fixed window

Count requests per calendar minute. Reset at the top of each minute.

const key = `${userId}:${Math.floor(Date.now() / 60_000)}`;
const count = await redis.incr(key);
await redis.expire(key, 60);
return count <= 100;

One counter, trivially cheap, and everyone reaches for it first.

Sliding window log

Store a timestamp per request; count how many fall inside the last 60 seconds.

Exact, with no boundary problem — and it stores every timestamp. At 10,000 requests per second per user that is a lot of memory, so it is used mainly for low limits.

Sliding window counter

The practical compromise: weight the previous window by how much of it is still in view.

const elapsed = (now % 60_000) / 60_000;          // 0…1 through the current minute
const estimate = previousCount * (1 - elapsed) + currentCount;
return estimate <= 100;

Two counters, no boundary burst, and an approximation that is wrong only when traffic is very bursty within a window. This is what Cloudflare uses, and it is usually the right answer for an HTTP API.

Token bucket

The one that models the intent best. Tokens accumulate at a fixed rate up to a cap; each request spends one.

Second 1 / 9

capacity 5 · refills 1/second

requests

allowed

rejected

Nothing arrived, so the bucket refills. Saved tokens are what let a client burst later — a fixed per-second counter would have thrown this capacity away.

function allow(bucket: Bucket, now: number): boolean {
  const elapsed = (now - bucket.last) / 1000;
  bucket.tokens = Math.min(bucket.capacity, bucket.tokens + elapsed * bucket.refillRate);
  bucket.last = now;

  if (bucket.tokens < 1) return false;
  bucket.tokens -= 1;
  return true;
}

Distributed is the hard part

Ten servers each allowing 100/minute is a 1,000/minute limit.

Shared counter in Redis — correct, and adds a round trip to every request. Use a Lua script so the read-modify-write is atomic; INCR plus a separate EXPIRE has a race that can leave a key with no TTL.

Local buckets with a share each — 10 per server, no coordination, and unfair when load is uneven.

Local with periodic sync — approximate, cheap, and what most large systems actually do. Accept that the limit is soft.

Tell the client what happened

HTTP/1.1 429 Too Many Requests
Retry-After: 30
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 30

Without Retry-After, well-behaved clients guess — and guessing usually means retrying immediately, turning your rate limit into a busy loop that costs you more than the original traffic.

Also: do not rate-limit by IP alone. One corporate NAT is thousands of users, and one attacker is thousands of IPs. Limit by authenticated identity where you have one, and treat IP as a fallback with a much looser bound.

What to limit, and where

Different resources want different limits: reads and writes, cheap endpoints and expensive ones. A single global number is easy to explain and usually protects the wrong thing.

Put the limiter at the edge — an API gateway or CDN — so rejected traffic never reaches your application. A 429 generated after your service has already done the authentication and database work has not saved you anything.

And rate limiting is only one of the load-shedding tools. It bounds a client; backpressure bounds the system when it is overloaded regardless of who is asking, and a circuit breaker stops you calling a dependency that is already failing. You want all three.