Designing a Rate Limiter: Token Bucket, Sliding Window and Redis

A rate limiter decides whether a request is allowed based on how many requests the same client has made recently. It protects services from abuse and accidental overload, keeps one noisy tenant from starving the others, and enforces commercial limits on API plans.

The idea is simple, but the details are not. The algorithm determines how bursts are handled, the storage determines whether limits hold across many instances, and the failure mode determines what happens when the limiter itself is down. This post covers the four common algorithms, implements them atomically in Redis with Lua, and wires one into a Node.js service.

Requirements first

Before choosing an algorithm, pin down what you are limiting:

• Key: per user, per API key, per IP, per tenant, per route, or a combination such as tenant:route.
• Limit shape: a steady rate (100 requests per minute), a burst allowance, or both.
• Accuracy: is it acceptable to let a few extra requests through at window edges?
• Scope: a single process, or shared across every instance behind a load balancer.
• Failure behaviour: if the limiter's store is unavailable, do you allow traffic (fail open) or reject it (fail closed)?

A limiter for login attempts wants accuracy and fail-closed behaviour. A limiter protecting a read-heavy public API usually wants low latency and fail-open behaviour.

Where the limiter lives

Rate limiting can happen at several layers, and production systems often use more than one:

• Edge or gateway: AWS WAF rate-based rules, API Gateway throttling and usage plans, or NGINX limit_req. Cheap and coarse, good for protecting against floods by IP.
• Application middleware: knows the authenticated user, tenant and plan, so it can enforce business limits.
• Before a fragile dependency: limits calls to a third-party API or a database with its own quota.

The rest of this post focuses on application-level limiting with a shared Redis instance, because that is where you need to make design decisions yourself.

The four algorithms

Fixed window counter

Count requests in discrete windows (for example, each calendar minute). If the count exceeds the limit, reject. It is one integer per key and one INCR per request.

The weakness is the boundary: a client can send the full limit at the end of one window and again at the start of the next, briefly getting twice the intended rate.

Sliding window log

Store a timestamp for every accepted request and count those within the last window. It is exact, with no boundary effect, but memory grows with the limit: a limit of 10,000 per hour stores up to 10,000 entries per key.

Sliding window counter

Keep counters for the current and previous fixed windows and estimate the rolling count by weighting the previous window by how much of it still overlaps the rolling window. It uses constant memory and removes most of the boundary burst, at the cost of being an approximation that assumes requests in the previous window were evenly distributed.

Token bucket

A bucket holds up to capacity tokens and refills at a steady rate. Each request removes one token (or more for expensive operations); if the bucket is empty, the request is rejected. It naturally supports a sustained rate plus a controlled burst, and only needs two values per key: the token count and the last refill time. Leaky bucket is a close relative that smooths output to a constant rate, usually by queueing requests rather than rejecting them.

Comparing the options

My default is the token bucket for API traffic and the sliding log for security-sensitive, low-volume limits.

Why atomicity matters

A naive implementation reads the counter, checks it in application code, then writes it back. Two instances can read the same value concurrently and both allow a request, exceeding the limit. Redis executes a Lua script atomically: no other command runs while the script is executing. Putting the read, decision and write in one script removes the race and also saves round trips.

All scripts below use Redis's own clock via TIME instead of the application's, so clock skew between app servers does not matter. Calling TIME inside a script that writes is safe on Redis 5 and later, where scripts replicate their effects rather than the script itself. Each script touches a single key passed in KEYS, which keeps them compatible with Redis Cluster.

Redis implementations

Fixed window

-- KEYS[1] = rate key, e.g. rl:fw:user:42
-- ARGV[1] = limit, ARGV[2] = window in milliseconds
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])

local count = redis.call('INCR', KEYS[1])
if count == 1 then
  redis.call('PEXPIRE', KEYS[1], window)
end

local ttl = redis.call('PTTL', KEYS[1])
if count > limit then
  return {0, 0, ttl}
end
return {1, limit - count, 0}

The window starts at the key's first request and ends when it expires. Setting the expiry in the same script as INCR avoids the classic bug where a crash between two separate commands leaves a counter with no TTL that never resets.

Sliding window log

-- KEYS[1] = rate key, e.g. rl:log:login:alice@example.com
-- ARGV[1] = limit, ARGV[2] = window in ms, ARGV[3] = unique request id
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])

local t = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

redis.call('ZREMRANGEBYSCORE', key, '-inf', now - window)
local count = redis.call('ZCARD', key)

if count < limit then
  redis.call('ZADD', key, now, ARGV[3])
  redis.call('PEXPIRE', key, window)
  return {1, limit - count - 1, 0}
end

local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
local retry_after = tonumber(oldest[2]) + window - now
return {0, 0, retry_after}

The member must be unique per request, otherwise two requests in the same millisecond collapse into one entry. Only accepted requests are logged, so a client that keeps retrying while blocked does not extend its own penalty.

Sliding window counter

-- KEYS[1] = rate key (a hash), e.g. rl:swc:tenant:acme
-- ARGV[1] = limit, ARGV[2] = window in ms
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])

local t = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local current_window = math.floor(now / window)

local state = redis.call('HMGET', key, 'win', 'cur', 'prev')
local win = tonumber(state[1])
local cur = tonumber(state[2]) or 0
local prev = tonumber(state[3]) or 0

if win == nil or win < current_window - 1 then
  prev = 0
  cur = 0
elseif win == current_window - 1 then
  prev = cur
  cur = 0
end

local elapsed_fraction = (now % window) / window
local estimated = prev * (1 - elapsed_fraction) + cur

if estimated + 1 > limit then
  redis.call('HSET', key, 'win', current_window, 'cur', cur, 'prev', prev)
  redis.call('PEXPIRE', key, window * 2)
  return {0, 0, window - (now % window)}
end

cur = cur + 1
redis.call('HSET', key, 'win', current_window, 'cur', cur, 'prev', prev)
redis.call('PEXPIRE', key, window * 2)
return {1, math.floor(limit - estimated - 1), 0}

Storing both windows in one hash keeps the script to a single key. The returned retry hint is conservative: it points to the next window boundary, where the weighted estimate is guaranteed to have dropped.

Token bucket

-- KEYS[1] = rate key (a hash), e.g. rl:tb:apikey:abc123
-- ARGV[1] = capacity, ARGV[2] = refill tokens per second, ARGV[3] = cost
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_per_ms = tonumber(ARGV[2]) / 1000
local cost = tonumber(ARGV[3])

local t = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local state = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(state[1])
local ts = tonumber(state[2])
if tokens == nil or ts == nil then
  tokens = capacity
  ts = now
end

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

local allowed = 0
local retry_after = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
else
  retry_after = math.ceil((cost - tokens) / refill_per_ms)
end

redis.call('HSET', key, 'tokens', tostring(tokens), 'ts', now)
local ttl = math.max(1, math.ceil(capacity / refill_per_ms))
redis.call('PEXPIRE', key, ttl)

return {allowed, math.floor(tokens), retry_after}

The key expires after the time it takes to refill completely, because a missing key and a full bucket mean the same thing. Tokens are stored as a string with tostring to preserve the fractional part; Redis converts Lua numbers in a script's return value to integers, which is why the returned token count is floored explicitly.

Using it from Node.js

With ioredis, defineCommand registers a script and calls it with EVALSHA, falling back to EVAL if the script is not cached on the server:

import Redis from 'ioredis';
import { readFileSync } from 'node:fs';
import type { Request, Response, NextFunction } from 'express';

const redis = new Redis(process.env.REDIS_URL!);

redis.defineCommand('tokenBucket', {
  numberOfKeys: 1,
  lua: readFileSync(new URL('./token-bucket.lua', import.meta.url), 'utf8'),
});

type TokenBucket = (key: string, capacity: number, ratePerSec: number, cost: number)
  => Promise<[number, number, number]>;

export function rateLimit(opts: { capacity: number; ratePerSec: number; failOpen: boolean }) {
  const tokenBucket = (redis as unknown as { tokenBucket: TokenBucket }).tokenBucket.bind(redis);

  return async (req: Request, res: Response, next: NextFunction) => {
    const subject = req.header('x-api-key') ?? req.ip;
    const key = `rl:tb:${subject}`;

    try {
      const [allowed, remaining, retryAfterMs] = await tokenBucket(key, opts.capacity, opts.ratePerSec, 1);

      res.setHeader('RateLimit-Limit', String(opts.capacity));
      res.setHeader('RateLimit-Remaining', String(remaining));

      if (allowed === 1) return next();

      res.setHeader('Retry-After', String(Math.ceil(retryAfterMs / 1000)));
      return res.status(429).json({ message: 'Too many requests' });
    } catch (err) {
      console.error('Rate limiter unavailable', err);
      return opts.failOpen ? next() : res.status(503).json({ message: 'Service unavailable' });
    }
  };
}

Return 429 Too Many Requests with a Retry-After header so well-behaved clients can back off. The RateLimit-* headers follow an IETF draft; many APIs still use the older X-RateLimit-* convention, so pick one and document it. In NestJS, the same logic fits in a guard, or you can start with @nestjs/throttler and plug in a Redis-backed storage.

Production concerns

• Redis latency is on the hot path. Keep Redis close to the application, set short command timeouts in the client, and decide explicitly on fail-open or fail-closed per limiter.
• Hot keys. A single tenant with huge traffic concentrates load on one Redis shard. For very high limits, consider a local in-memory token bucket per instance that periodically syncs with Redis, accepting some inaccuracy.
• Choosing the key. Limiting by IP punishes users behind shared NAT and is trivially evaded with many IPs. Prefer authenticated identities, and use IP limits only as a coarse outer layer. If you are behind a proxy or load balancer, configure the framework's trusted proxy settings so req.ip is the client, not the proxy.
• Layered limits. Combine a short burst limit (per second) with a longer quota (per hour or day); check both and reject if either fails.
• Observability. Emit metrics for allowed and rejected decisions by limiter and key class. A sudden spike in 429s is either an attack or a bug in a client you care about.
• Configuration. Store limits per plan or tenant in configuration, not constants, so support can raise a limit without a deploy.

Conclusion

A good rate limiter is a combination of the right algorithm, atomic shared state and deliberate failure behaviour. Fixed windows are simple but leaky at boundaries, sliding logs are exact but memory-hungry, sliding window counters are a cheap and accurate-enough approximation, and token buckets model sustained rate plus burst directly. Implement the decision in a single Redis Lua script so it is race-free and uses one round trip, return clear 429 responses with retry hints, and layer it with coarse limits at the edge. That combination holds up well from a single service to a fleet of instances.