SystemCraftSystemCraft
Back to Designs

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.

~3 min readeasy difficultyweb
Practice

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.

LLD 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

ConcernDecision
Counter storeRedis — shared, atomic, sub-millisecond
AtomicityLua script — INCR + TTL in one round-trip
AlgorithmSliding window counter
Rule lookupIn-memory cache (60s TTL) backed by Rules DB
Failure modeFail open — Redis down → allow request
Expand

Data Model

Data Model

RateRule (Rules DB document)

ts
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;
}
Expand

Redis Key Schema

Diagram
rate:{client_id}:{endpoint}:{window_bucket}
Expand
  • 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)

ts
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
}
Expand

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

ts
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>
}
Expand

HTTP Response Headers

HeaderValueExample
X-RateLimit-LimitMax requests per window100
X-RateLimit-RemainingRequests left in window42
X-RateLimit-ResetUnix timestamp of window reset1719500460
Retry-AfterSeconds until retry allowed (429 only)37
Expand

External API: Rule Management

Diagram
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
Expand

Sequence Diagrams

Allow Path

Diagram
Expand

Reject Path

Diagram
Expand

Redis Down (Fail Open)

Diagram
Expand

LLD Tradeoffs

Implementation Tradeoffs

DecisionOption AOption BChosenReason
AtomicityRedis MULTI/EXECLua scriptLuaSingle round-trip, no WATCH retry loop
AlgorithmToken bucketSliding window counterSliding windowLua script simpler, 2 Redis keys max
Window typeFixed windowSliding windowSlidingPrevents 2× burst at window boundary
Rules storageRules in RedisRules in DB + cacheDB + cacheDB is source of truth; cache avoids DB hit per request
Cache TTL5s60s60sRule changes are infrequent; 60s lag acceptable
Fail modeFail closedFail openFail openAvailability > strict rate enforcement during outages
Key granularityPer-IP onlyPer-IP + per-endpointBothEndpoint-level limits needed for expensive operations
Expand

Sliding Window Counter Math

Diagram
prev_bucket_count × (1 - elapsed_fraction) + curr_bucket_count
Expand
  • 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

typescript
// --- 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>;
}
Expand