API Rate Limiting: Token Bucket, Redis, and 429 Headers

Rate limiting gets added after the incident. A scraper discovers an expensive endpoint, or a client ships a retry loop with no backoff, and suddenly the database is saturated by one caller. The fix is not hard. Choosing the wrong algorithm, or limiting on the wrong key, is what turns it into a support problem instead.

Two references worth having open: RFC 6585, which defines 429 and says explicitly that the response should explain how long to wait, and the Redis scripting guide, since the atomicity a correct distributed limiter needs is the whole reason a Lua script shows up later in this post.

Four API rate limiting algorithms

They differ in how they handle bursts, and that difference is the whole decision.

Why is fixed window not enough?

A limit of 100 per minute, implemented as a counter that resets on the minute, lets a client send 100 requests at 10:00:59 and another 100 at 10:01:00. Two hundred requests in one second, inside the limit as written. If you are rate limiting to protect a resource, that burst is exactly what you were trying to prevent.

It is still the right choice sometimes. For a coarse abuse limit like 10,000 per hour, the boundary effect does not matter and one integer per key is very cheap.

Token bucket, and why I default to it

A bucket holds tokens up to a maximum. Tokens refill at a steady rate. Each request removes one, and a request with no token available is rejected.

This models real usage better than a flat window. A client that has been idle accumulates tokens and can burst, which is usually what you want: someone opening a dashboard fires twelve requests at once and that is legitimate. Sustained load is still capped at the refill rate.

type Bucket = { tokens: number; lastRefill: number };

const CAPACITY = 20;          // burst allowance
const REFILL_PER_SECOND = 2;  // sustained rate

function consume(bucket: Bucket, now: number): boolean {
  // Refill lazily rather than on a timer: no background job, and the
  // arithmetic is identical.
  const elapsed = (now - bucket.lastRefill) / 1000;
  bucket.tokens = Math.min(CAPACITY, bucket.tokens + elapsed * REFILL_PER_SECOND);
  bucket.lastRefill = now;

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

Lazy refill is the part worth copying. There is no scheduled job topping up buckets; you compute how much time has passed when the request arrives. That is what makes the whole thing two numbers in Redis.

Doing it in Redis, atomically

In-memory counters break the moment you run two instances, because each one enforces the limit independently and a client with three servers behind a load balancer gets three times the allowance.

Moving to Redis introduces a different problem: read, modify, write is not atomic across concurrent requests. Two requests arriving together both read one token remaining and both proceed. A Lua script runs server-side in a single step and removes the race.

const TOKEN_BUCKET = `
local key       = KEYS[1]
local capacity  = tonumber(ARGV[1])
local refill    = tonumber(ARGV[2])   -- tokens per second
local now       = tonumber(ARGV[3])   -- milliseconds
local requested = tonumber(ARGV[4])

local state = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(state[1])
local ts     = tonumber(state[2])

if tokens == nil then
  tokens = capacity
  ts = now
end

local elapsed = math.max(0, now - ts) / 1000
tokens = math.min(capacity, tokens + elapsed * refill)

local allowed = 0
if tokens >= requested then
  tokens = tokens - requested
  allowed = 1
end

redis.call('HSET', key, 'tokens', tokens, 'ts', now)
-- Expire idle buckets so keys do not accumulate forever.
redis.call('PEXPIRE', key, math.ceil((capacity / refill) * 1000) + 1000)

return { allowed, tokens }
`;

export async function checkLimit(key: string) {
  const [allowed, remaining] = (await redis.eval(
    TOKEN_BUCKET,
    { keys: [`rl:${key}`], arguments: ['20', '2', String(Date.now()), '1'] }
  )) as [number, number];

  return { allowed: allowed === 1, remaining: Math.floor(remaining) };
}

The PEXPIRE matters more than it looks. Without it, every key that ever hit your API stays in Redis forever, and on a public endpoint that is an unbounded memory leak with a slow fuse.

What should you limit on?

The key you choose determines whether the limit protects you or annoys your users.

IP address is the only option for unauthenticated traffic, and it is blunt. An office, a university or a mobile carrier NAT puts hundreds of people behind one address, so a per-IP limit tuned for one person locks out a building. Keep IP limits generous and treat them as abuse protection, not as quota.

User or API key is what you want wherever the request is authenticated. It is fair, it survives the user changing networks, and it lets you sell tiers.

Both, in practice: a loose IP limit in front for unauthenticated abuse, and a per-user limit behind it for quota.

Tell the client what happened

A bare 429 with no information forces clients to guess, and clients guess by retrying immediately. Send the headers.

export async function rateLimit(req: Request, res: Response, next: NextFunction) {
  const key = req.user?.id ?? req.ip;
  const { allowed, remaining, resetSeconds } = await checkLimit(key);

  // The IETF draft header format, now widely supported.
  res.setHeader('RateLimit-Limit', LIMIT);
  res.setHeader('RateLimit-Remaining', Math.max(0, remaining));
  res.setHeader('RateLimit-Reset', resetSeconds);

  if (!allowed) {
    // Retry-After is the one clients and crawlers actually respect.
    res.setHeader('Retry-After', resetSeconds);
    return res.status(429).json({
      error: {
        code: 'RATE_LIMITED',
        message: `Too many requests. Retry in ${resetSeconds}s.`,
      },
    });
  }

  next();
}

Retry-After is the important one. It is standard, well understood, and well-behaved HTTP clients honour it automatically. The RateLimit-* family lets a good client slow down before it hits the wall rather than after.

The error body follows the same shape as every other error in the API, which is the point made in REST API design: one error structure means clients write one handler.

Backing off on the client side

async function requestWithRetry(url: string, attempt = 0): Promise<Response> {
  const res = await fetch(url);
  if (res.status !== 429 || attempt >= 4) return res;

  const retryAfter = Number(res.headers.get('Retry-After'));
  // Exponential backoff with jitter, so a thousand clients that were
  // limited together do not all return at the same instant.
  const backoff = Number.isFinite(retryAfter)
    ? retryAfter * 1000
    : 2 ** attempt * 500 + Math.random() * 500;

  await new Promise((r) => setTimeout(r, backoff));
  return requestWithRetry(url, attempt + 1);
}

The jitter is not optional at scale. Synchronised retries produce a thundering herd that arrives together, gets limited together, and comes back together, which is a self-sustaining outage.

Not all endpoints deserve the same limit

One global limit is easy and wrong. A cached GET costs almost nothing; a report generator costs seconds of CPU; a login endpoint is where credential stuffing happens.

That last row is worth singling out. An endpoint that forwards to a metered third-party service turns request volume directly into money, and an unlimited one is a way for a stranger to spend your budget. This is the specific risk I raised in LLM API integration, where the per-request cost is high enough that a short burst is expensive.

Limiting login attempts on both IP and account is deliberate. Per-IP alone misses a distributed attack on one account; per-account alone lets one IP spray thousands of accounts with common passwords. You need both counters.

Roll out with logging first

The most common way to get this wrong is to deploy a limit tuned from intuition and discover it was set below what a legitimate heavy user does. Run it in shadow mode first: compute the decision, log what would have been blocked, enforce nothing.

const { allowed } = await checkLimit(key);

if (!allowed) {
  if (ENFORCE_LIMITS) {
    return res.status(429).json(/* ... */);
  }
  // Shadow mode: measure before you enforce.
  logger.warn({ key, path: req.path }, 'would have rate limited');
}
next();

A week of that data tells you where the real ceiling is. Then set the limit above your heaviest legitimate user and turn enforcement on.

What I would ship

Token bucket in Redis behind a Lua script, keyed on user ID with an IP fallback, different limits per endpoint class, standard headers including Retry-After, and key expiry so Redis does not grow forever. Shadow mode for a week before enforcing.

And use a maintained library rather than the code above if you can. The implementations here are to show what is happening underneath, because when a limit behaves unexpectedly the fix depends on knowing which algorithm you are running.

Rate limiting is one of several decisions that are much cheaper to make before an API has consumers. The rest of them, error shape, pagination and versioning, are in REST API design.