Rate Limiter
Design a distributed rate limiter that caps how many requests a client can make in a given time window, returning 429 when exceeded.
Low Level Design — covers service internals: DB schemas, API contracts, sequence flows, and class interfaces.
These designs are for learning purposes and may not be 100% accurate or production-ready. Always cross-reference with official docs and other resources. Report an issue if you spot something wrong.
Reference Documents
Redis Lua Scripting — Official Docs
Official Redis documentation on EVAL and Lua scripting — essential for implementing atomic rate-limit counter operations.
DocsBetter Rate Limiting with Redis Sorted Sets — Redis Blog
Redis patterns for rate limiting including sliding window with sorted sets and INCR-based fixed window approaches.
ArticleFigma — Rate Limiter Algorithms Compared
Figma Engineering's analysis of sliding window vs token bucket for their API, with production trade-off decisions.
BlogLLD Overview
Low-Level Design: Rate Limiter
The rate limiter is implemented as a middleware service called synchronously by the API Gateway before forwarding to the upstream app. It must add less than 5ms of latency.
Core Responsibilities
- Rule resolution: Look up the per-client / per-endpoint limit and window
- Counter management: Atomically increment and read counters in Redis
- Decision: Allow or reject the current request
- Headers: Set
X-RateLimit-Limit,X-RateLimit-Remaining,X-RateLimit-Reset,Retry-After
Key Design Decisions
| Concern | Decision |
|---|---|
| Counter store | Redis — shared, atomic, sub-millisecond |
| Atomicity | Lua script — INCR + TTL in one round-trip |
| Algorithm | Sliding window counter |
| Rule lookup | In-memory cache (60s TTL) backed by Rules DB |
| Failure mode | Fail open — Redis down → allow request |
Data Model
Data Model
RateRule (Rules DB document)
interface RateRule {
client_id: string; // IP, user_id, or api_key
endpoint: string; // '/api/search' or '*' for global
limit: number; // max requests allowed
window_sec: number; // window duration in seconds
tier: 'free' | 'pro' | 'enterprise';
created_at: Date;
updated_at: Date;
}
Redis Key Schema
rate:{client_id}:{endpoint}:{window_bucket}
- window_bucket =
Math.floor(Date.now() / 1000 / window_sec) - Value = integer (request count)
- TTL =
2 × window_sec(keep previous bucket for sliding window)
Counter Record (in-flight)
interface RateCheckResult {
allowed: boolean;
current_count: number;
limit: number;
remaining: number;
reset_at: number; // unix timestamp when window resets
retry_after?: number; // seconds to wait if rejected
}
Rules DB Index
- Primary:
{ client_id: 1, endpoint: 1 }— unique compound index - Secondary:
{ tier: 1 }— for bulk rule updates per tier
API Design
Internal API
RateLimiterService
class RateLimiterService {
/**
* Check and increment counter for a request.
* @returns RateCheckResult — caller decides whether to allow/reject
*/
async isAllowed(clientId: string, endpoint: string): Promise<RateCheckResult>
/**
* Load rule for client+endpoint. Falls back to tier default, then global default.
* Cached in-memory for 60 seconds.
*/
async getRuleFor(clientId: string, endpoint: string): Promise<RateRule>
/**
* Force-refresh the rules cache for a client (e.g. after tier upgrade).
*/
async invalidateRulesCache(clientId: string): Promise<void>
}
HTTP Response Headers
| Header | Value | Example |
|---|---|---|
X-RateLimit-Limit | Max requests per window | 100 |
X-RateLimit-Remaining | Requests left in window | 42 |
X-RateLimit-Reset | Unix timestamp of window reset | 1719500460 |
Retry-After | Seconds until retry allowed (429 only) | 37 |
External API: Rule Management
POST /admin/rate-rules # Create or update a rule
GET /admin/rate-rules/:client # Get all rules for a client
DELETE /admin/rate-rules/:id # Delete a rule
Sequence Diagrams
Allow Path
Reject Path
Redis Down (Fail Open)
LLD Tradeoffs
Implementation Tradeoffs
| Decision | Option A | Option B | Chosen | Reason |
|---|---|---|---|---|
| Atomicity | Redis MULTI/EXEC | Lua script | Lua | Single round-trip, no WATCH retry loop |
| Algorithm | Token bucket | Sliding window counter | Sliding window | Lua script simpler, 2 Redis keys max |
| Window type | Fixed window | Sliding window | Sliding | Prevents 2× burst at window boundary |
| Rules storage | Rules in Redis | Rules in DB + cache | DB + cache | DB is source of truth; cache avoids DB hit per request |
| Cache TTL | 5s | 60s | 60s | Rule changes are infrequent; 60s lag acceptable |
| Fail mode | Fail closed | Fail open | Fail open | Availability > strict rate enforcement during outages |
| Key granularity | Per-IP only | Per-IP + per-endpoint | Both | Endpoint-level limits needed for expensive operations |
Sliding Window Counter Math
prev_bucket_count × (1 - elapsed_fraction) + curr_bucket_count
elapsed_fraction= seconds elapsed in current window / window_sec- Uses prev + curr Redis keys (2 reads + 1 write per request)
- Approximation error < 0.1% in practice
Core Classes
Core Classes & Interfaces
// --- Data Types ---
interface RateRule {
clientId: string;
endpoint: string; // '*' = wildcard (global rule)
limit: number;
windowSec: number;
tier: 'free' | 'pro' | 'enterprise';
}
interface RateCheckResult {
allowed: boolean;
currentCount: number;
limit: number;
remaining: number;
resetAt: number; // unix timestamp
retryAfter?: number; // only set when allowed = false
}
// --- Service ---
class RateLimiterService {
private rulesCache: Map<string, { rule: RateRule; expiresAt: number }>;
private readonly CACHE_TTL_MS = 60_000;
constructor(
private readonly redis: RedisClient,
private readonly rulesDb: RulesRepository,
) {}
async isAllowed(clientId: string, endpoint: string): Promise<RateCheckResult> {
const rule = await this.getRuleFor(clientId, endpoint);
const windowBucket = Math.floor(Date.now() / 1000 / rule.windowSec);
const key = `rate:${clientId}:${endpoint}:${windowBucket}`;
try {
const count = await this.redis.eval(
LUA_INCR_SCRIPT,
[key],
[String(rule.windowSec * 2)] // TTL = 2 windows
) as number;
const allowed = count <= rule.limit;
const resetAt = (windowBucket + 1) * rule.windowSec;
return {
allowed,
currentCount: count,
limit: rule.limit,
remaining: Math.max(0, rule.limit - count),
resetAt,
retryAfter: allowed ? undefined : resetAt - Math.floor(Date.now() / 1000),
};
} catch (err) {
// Fail open on Redis error
logger.error('RateLimiter Redis error', { err });
metrics.increment('rate_limiter.redis.error');
return { allowed: true, currentCount: 0, limit: rule.limit, remaining: rule.limit, resetAt: 0 };
}
}
private async getRuleFor(clientId: string, endpoint: string): Promise<RateRule> {
const cacheKey = `${clientId}:${endpoint}`;
const cached = this.rulesCache.get(cacheKey);
if (cached && cached.expiresAt > Date.now()) return cached.rule;
// Lookup priority: exact match → wildcard endpoint → tier default
const rule =
await this.rulesDb.findOne({ clientId, endpoint }) ??
await this.rulesDb.findOne({ clientId, endpoint: '*' }) ??
DEFAULT_RULES['free'];
this.rulesCache.set(cacheKey, { rule, expiresAt: Date.now() + this.CACHE_TTL_MS });
return rule;
}
}
// --- Lua Script (atomic INCR + EXPIRE) ---
const LUA_INCR_SCRIPT = `
local count = redis.call('INCR', KEYS[1])
if count == 1 then
redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return count
`;
// --- Repository ---
interface RulesRepository {
findOne(query: { clientId: string; endpoint: string }): Promise<RateRule | null>;
upsert(rule: RateRule): Promise<void>;
deleteById(id: string): Promise<void>;
}