Rate Limiting Implementation: Algorithms and Tradeoffs

Rate limiting controls how many requests a client can make in a given time period. Without it, a single aggressive client can monopolize your server’s resources, a buggy integration can hammer your API with retries, and a malicious actor can attempt brute-force attacks unimpeded.

Every production API needs rate limiting. The question is which algorithm to use, where to enforce it, and how to communicate limits to clients.

Fixed window

The simplest approach. Divide time into fixed intervals (e.g., 1-minute windows) and count requests per client in each window.

Window: 14:00:00 - 14:00:59 -> 47 requests (limit: 100)
Window: 14:01:00 - 14:01:59 -> 12 requests

Implementation with Redis:

async function fixedWindowRateLimit(clientId, limit, windowSec) {
  const key = `rate:${clientId}:${Math.floor(Date.now() / 1000 / windowSec)}`;

  const current = await redis.incr(key);
  if (current === 1) {
    await redis.expire(key, windowSec);
  }

  return {
    allowed: current <= limit,
    remaining: Math.max(0, limit - current),
    resetAt: (Math.floor(Date.now() / 1000 / windowSec) + 1) * windowSec,
  };
}

The key includes the window number, so it automatically rotates. Redis INCR is atomic, so concurrent requests get accurate counts.

The problem: burst at window boundaries. A client can send 100 requests at 14:00:59 and another 100 at 14:01:00, effectively making 200 requests in 2 seconds while technically staying within the per-minute limit.

Sliding window log

Track the timestamp of every request and count how many fall within the trailing window.

async function slidingWindowLog(clientId, limit, windowSec) {
  const key = `rate:${clientId}`;
  const now = Date.now();
  const windowStart = now - windowSec * 1000;

  const pipeline = redis.pipeline();
  pipeline.zremrangebyscore(key, 0, windowStart);
  pipeline.zadd(key, now, `${now}:${Math.random()}`);
  pipeline.zcard(key);
  pipeline.expire(key, windowSec);
  const results = await pipeline.exec();

  const count = results[2][1];
  return {
    allowed: count <= limit,
    remaining: Math.max(0, limit - count),
  };
}

This uses a Redis sorted set where each member is a request timestamp. Before counting, it removes entries older than the window. The count is always accurate across window boundaries.

The tradeoff: memory. Every request is stored as a sorted set member. At 10,000 requests per minute per client, that is 10,000 entries in Redis per client. For high-volume APIs, this becomes expensive.

Sliding window counter

A hybrid that approximates the sliding window without storing individual timestamps. It uses two fixed windows and weights the previous window by the overlap.

async function slidingWindowCounter(clientId, limit, windowSec) {
  const now = Date.now() / 1000;
  const currentWindow = Math.floor(now / windowSec);
  const previousWindow = currentWindow - 1;
  const elapsed = (now % windowSec) / windowSec;

  const [currentCount, previousCount] = await Promise.all([
    redis.get(`rate:${clientId}:${currentWindow}`).then(v => parseInt(v) || 0),
    redis.get(`rate:${clientId}:${previousWindow}`).then(v => parseInt(v) || 0),
  ]);

  const estimate = previousCount * (1 - elapsed) + currentCount;

  if (estimate >= limit) {
    return { allowed: false, remaining: 0 };
  }

  await redis.incr(`rate:${clientId}:${currentWindow}`);
  await redis.expire(`rate:${clientId}:${currentWindow}`, windowSec * 2);

  return {
    allowed: true,
    remaining: Math.max(0, Math.floor(limit - estimate - 1)),
  };
}

This uses only two counters (two Redis keys) regardless of request volume. The weighted estimate smooths out the boundary burst problem. Cloudflare uses this approach for their rate limiting.

Token bucket

The most flexible algorithm. A bucket starts with a fixed number of tokens. Each request consumes one token. Tokens are added back at a steady rate. If the bucket is empty, the request is rejected.

async function tokenBucket(clientId, capacity, refillRate, refillIntervalMs) {
  const key = `bucket:${clientId}`;
  const now = Date.now();

  const script = `
    local data = redis.call('HMGET', KEYS[1], 'tokens', 'last_refill')
    local tokens = tonumber(data[1]) or tonumber(ARGV[1])
    local last_refill = tonumber(data[2]) or tonumber(ARGV[3])

    local elapsed = tonumber(ARGV[3]) - last_refill
    local refill = math.floor(elapsed / tonumber(ARGV[4])) * tonumber(ARGV[2])
    tokens = math.min(tonumber(ARGV[1]), tokens + refill)

    if tokens < 1 then
      return {0, tokens, 0}
    end

    tokens = tokens - 1
    redis.call('HMSET', KEYS[1], 'tokens', tokens, 'last_refill', ARGV[3])
    redis.call('EXPIRE', KEYS[1], math.ceil(tonumber(ARGV[1]) / tonumber(ARGV[2]) * tonumber(ARGV[4]) / 1000))
    return {1, tokens, 1}
  `;

  const result = await redis.eval(
    script, 1, key,
    capacity, refillRate, now, refillIntervalMs
  );

  return {
    allowed: result[0] === 1,
    remaining: result[1],
  };
}

The Lua script runs atomically in Redis. It calculates how many tokens to add since the last refill, checks if tokens are available, and decrements. Using a Lua script prevents race conditions between concurrent requests.

Token bucket allows bursts up to the bucket capacity while enforcing a sustained average rate. This matches how most APIs want to behave: tolerate short spikes but throttle sustained abuse.

Response headers

Clients need to know their rate limit status. The IETF draft standard (RFC 6585 and draft-ietf-httpapi-ratelimit-headers) defines these headers:

RateLimit-Limit: 100
RateLimit-Remaining: 42
RateLimit-Reset: 1719936000

When a request is rejected, return 429 Too Many Requests with a Retry-After header:

if (!result.allowed) {
  res.set('Retry-After', String(result.retryAfterSec));
  res.set('RateLimit-Limit', String(limit));
  res.set('RateLimit-Remaining', '0');
  return res.status(429).json({
    error: 'rate_limit_exceeded',
    message: 'Too many requests. Please retry after the specified time.',
    retry_after: result.retryAfterSec,
  });
}

Always include these headers on successful responses too, so well-behaved clients can self-throttle before hitting the limit.

Distributed rate limiting

With multiple API servers behind a load balancer, rate limits must be shared. Redis is the standard solution because it is fast, atomic, and all servers can access the same state.

If Redis is unavailable, you have two fallback options:

1. Local rate limiting with reduced limits. Each server enforces limit / server_count. This is approximate but prevents total failure.
2. Allow all requests. If rate limiting is primarily about fairness rather than security, failing open may be acceptable.

For globally distributed APIs, consider a rate limiting service that runs at the edge (Cloudflare Workers, AWS WAF) rather than at the application layer. This stops abusive traffic before it reaches your servers.

Choosing an algorithm

Algorithm	Memory	Accuracy	Burst handling	Complexity
Fixed window	Low	Low	Poor (boundary burst)	Simple
Sliding window log	High	Exact	Good	Moderate
Sliding window counter	Low	Approximate	Good	Moderate
Token bucket	Low	Good	Configurable	Moderate

For most APIs, the sliding window counter or token bucket is the right choice. The sliding window counter is simpler to reason about. The token bucket gives more control over burst behavior.

Applying limits by tier

Different clients often deserve different limits. Use API keys or authentication tokens to identify the client and look up their tier:

const TIERS = {
  free:       { limit: 100,   window: 60 },
  starter:    { limit: 1000,  window: 60 },
  business:   { limit: 10000, window: 60 },
  enterprise: { limit: 50000, window: 60 },
};

const tier = await getTierForApiKey(req.headers['x-api-key']);
const config = TIERS[tier] || TIERS.free;

Rate limiting is not just about protecting your servers. It is about building a predictable, fair API that clients can program against reliably. The headers, the error responses, and the documentation matter as much as the algorithm.