Design a Production Rate Limiter: Algorithms Seniors Actually Use in Interviews and at Work

// Redis Lua script — atomic token bucket (no race conditions)
// Run with: redis.call('EVAL', script, 1, key, capacity, rate, now)

const tokenBucketScript = `
local key = KEYS[1]
local capacity = tonumber(ARGV[1]) -- max tokens
local rate = tonumber(ARGV[2]) -- tokens per second
local now = tonumber(ARGV[3]) -- current timestamp (ms)

local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(bucket[1]) or capacity
local last_refill = tonumber(bucket[2]) or now

-- Calculate tokens to add since last request
local elapsed = (now - last_refill) / 1000 -- seconds
local new_tokens = math.min(capacity, tokens + (elapsed * rate))

if new_tokens >= 1 then
 -- Allow request, consume 1 token
 redis.call('HMSET', key, 'tokens', new_tokens - 1, 'last_refill', now)
 redis.call('EXPIRE', key, 3600) -- auto-expire inactive users
 return {1, math.floor(new_tokens - 1)} -- {allowed, remaining}
else
 -- Reject request
 redis.call('HMSET', key, 'tokens', new_tokens, 'last_refill', now)
 redis.call('EXPIRE', key, 3600)
 return {0, 0} -- {rejected, remaining}
end
`;

// Node.js implementation
const redis = require('ioredis');
const client = new redis();

async function tokenBucket(userId, capacity = 100, rate = 10) {
 const key = `ratelimit:token:${userId}`;
 const now = Date.now();
 const [allowed, remaining] = await client.eval(
 tokenBucketScript, 1, key, capacity, rate, now
 );
 return {
 allowed: allowed === 1,
 remaining: parseInt(remaining),
 retryAfter: allowed ? null : Math.ceil(1000 / rate) // ms until next token
 };
}

// Express middleware
app.use(async (req, res, next) => {
 const result = await tokenBucket(req.user.id);
 res.set('X-RateLimit-Remaining', result.remaining);
 if (!result.allowed) {
 return res.status(429).json({
 error: 'Rate limit exceeded',
 retryAfter: result.retryAfter + 'ms'
 });
 }
 next();
});

// Stores timestamp of each request in a sorted set
// Counts requests in the rolling window (e.g., last 60 seconds)
// Most accurate but uses the most memory (O(requests) per user)

async function slidingWindowLog(userId, limit = 100, windowMs = 60000) {
 const key = `ratelimit:swl:${userId}`;
 const now = Date.now();
 const windowStart = now - windowMs;

 const pipeline = client.pipeline();
 pipeline.zremrangebyscore(key, 0, windowStart); // Remove old entries
 pipeline.zadd(key, now, `${now}-${Math.random()}`); // Add current request
 pipeline.zcard(key); // Count requests in window
 pipeline.expire(key, Math.ceil(windowMs / 1000));
 const results = await pipeline.exec();

 const requestCount = results[2][1];
 const allowed = requestCount <= limit;

 if (!allowed) {
 // Remove the request we just added (rejected)
 await client.zremrangebyscore(key, now, now);
 }

 return {
 allowed,
 remaining: Math.max(0, limit - requestCount),
 resetAt: windowStart + windowMs
 };
}
// Advantage: perfectly accurate, no boundary spikes
// Disadvantage: Redis memory grows with request volume

// Simplest algorithm — count requests per time window
// Gotcha: boundary spike — user can make 2x limit at window boundary

async function fixedWindow(userId, limit = 100, windowSec = 60) {
 const window = Math.floor(Date.now() / 1000 / windowSec); // Current window ID
 const key = `ratelimit:fw:${userId}:${window}`;

 const count = await client.incr(key);
 if (count === 1) {
 // First request in this window — set expiry
 await client.expire(key, windowSec * 2);
 }

 return {
 allowed: count <= limit,
 remaining: Math.max(0, limit - count),
 resetAt: (window + 1) * windowSec * 1000 // Next window start
 };
}

// The boundary spike problem:
// Window: 12:00:00 → 12:01:00
// User sends 100 requests at 12:00:59 (allowed — new window starts at :00)
// User sends 100 more at 12:01:01 (allowed — new window)
// Effectively 200 requests in 2 seconds — NOT 100/minute
// Fix: use sliding window log OR sliding window counter for strict limits

// Problem 1: Multiple API gateway nodes without Redis coordination
// Node A and Node B each have their own in-memory counter
// User gets 100 req/min per node = 100 * N nodes effective limit
// ✅ Fix: Always use Redis (or Memcached) for shared state

// Problem 2: Redis connection failure = no rate limiting or total outage
// ✅ Fix: Fail open (allow requests) on Redis error, log it, alert
async function rateLimitWithFallback(userId) {
 try {
 return await tokenBucket(userId);
 } catch (err) {
 console.error('Rate limiter Redis error:', err);
 // Fail open — better than taking down the service
 return { allowed: true, remaining: -1, error: true };
 }
}

// Problem 3: Different limits per endpoint or tier
// ✅ Fix: Include resource in key
const key = `ratelimit:${userId}:${endpoint}:${tier}`;
// E.g.: "ratelimit:u123:/api/search:free"

// Problem 4: Rate limit headers for good UX
res.set({
 'X-RateLimit-Limit': limit,
 'X-RateLimit-Remaining': result.remaining,
 'X-RateLimit-Reset': result.resetAt, // Unix timestamp
 'Retry-After': result.retryAfter / 1000 // Seconds (RFC 7231)
});