avocadoo
All postsSystem design

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

A practical design guide to rate limiting: fixed window, sliding log, sliding window counter and token bucket compared, with atomic Redis Lua implementations, a TypeScript middleware, response headers, failure modes and the trade-offs that matter in distributed systems.

Tran Quang · Sep 11, 2026 · 9 min read

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:

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:

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

AlgorithmMemory per keyAccuracyBurst behaviourGood fit
Fixed windowOne counterLow at window edgesUp to 2x at boundariesSimple quotas, coarse protection
Sliding logOne entry per requestExactStrictly enforcedLow limits needing precision, such as login attempts
Sliding window counterTwo countersApproximate, usually closeSmoothedGeneral API limits at scale
Token bucketTwo valuesExact for its modelExplicit, configurable burstAPIs that allow short bursts, cost-weighted requests

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

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.