Design an API Rate Limiter

Rate Limiter Middleware

• Where it runs: As a middleware in the API Gateway or as a sidecar proxy (e.g., Envoy filter)
• Why middleware: Every request passes through it before reaching the API server. Centralized enforcement
• Flow:
  1. Extract client identifier (API key, user ID, IP)
  2. Look up applicable rate limit rules (from local cache, refreshed every 30s from Rules DB)
  3. Check counter in Redis: INCR + EXPIRE atomically
  4. If under limit → allow, pass X-RateLimit-Remaining header
  5. If over limit → reject with 429 Too Many Requests + Retry-After header

Redis Cluster (Rate State Store)

• Why Redis:
  • In-memory → sub-millisecond latency
  • Atomic operations (INCR, EXPIRE) → no race conditions
  • Built-in TTL → counters auto-expire
  • Single-threaded model → no locking needed for atomic ops
• Deployment: Redis Cluster with 6 nodes (3 masters + 3 replicas) for HA
• Data Model: Key = ratelimit:{client_id}:{endpoint}:{window}, Value = counter

Rules Configuration Service

• Purpose: Admin UI/API to create, update, delete rate limiting rules
• Rules stored in: MySQL (persistent) + cached in-memory on each API Gateway instance
• Rule format: YAML/JSON defining limits per client tier, per endpoint
• Push-based updates: When a rule changes, publish to a Kafka topic. All gateway instances subscribe and update their local cache

Rate Limiting Algorithms: Deep Dive

Algorithm 1: Token Bucket ⭐ (Most Common)

How it works:

• Each client has a "bucket" with a max capacity of N tokens
• Tokens are added at a fixed rate of R tokens/sec
• Each request consumes 1 token
• If bucket is empty → reject

Pros: Allows bursts (up to bucket capacity), smooth rate limiting

Cons: Two parameters to tune (bucket size + refill rate)

Redis Implementation:

Key: ratelimit:token:{client_id}
Value: {tokens: 8, last_refill: 1710320000}

Lua Script (atomic):
  local tokens = get current tokens
  local elapsed = now - last_refill
  tokens = min(max_tokens, tokens + elapsed * refill_rate)
  if tokens >= 1 then
    tokens = tokens - 1
    return ALLOWED
  else
    return REJECTED

Full Lua Script:

local key = KEYS[1]
local max_tokens = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])  -- tokens per second
local now = tonumber(ARGV[3])

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

-- Refill tokens
local elapsed = now - last_refill
tokens = math.min(max_tokens, tokens + elapsed * refill_rate)

if tokens >= 1 then
    tokens = tokens - 1
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, max_tokens / refill_rate * 2)
    return {1, tokens}  -- allowed, remaining
else
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    local retry_after = (1 - tokens) / refill_rate
    return {0, retry_after}  -- rejected, retry_after seconds
end

Algorithm 2: Sliding Window Log

How it works:

• Store timestamp of every request in a sorted set
• On new request, remove all entries older than the window
• Count remaining entries; if < limit → allow

Pros: Exact, no boundary issues

Cons: Memory-intensive (stores every timestamp)

-- Redis: ZSET per client
  ZREMRANGEBYSCORE key 0 (now - window)
  ZADD key now now
  ZCARD key → count

Algorithm 3: Sliding Window Counter ⭐ (Best Balance)

How it works:

• Combine fixed window counters with weighted overlap
• effective_count = prev_window_count × overlap_percentage + current_window_count
• Example: window = 1 min, at 0:30 → effective = prev × 0.5 + current

Pros: Memory efficient (two counters), smooth, no boundary spikes

Cons: Approximate (but very close to exact)

Redis:
  Key prev: ratelimit:{client}:{endpoint}:202603131000
  Key curr: ratelimit:{client}:{endpoint}:202603131001

  weight = (60 - seconds_into_current_window) / 60
  count = prev_count × weight + curr_count

Algorithm 4: Fixed Window Counter

How it works:

• Counter per fixed time window (e.g., 0:00-1:00, 1:00-2:00)
• INCR key; if count > limit → reject

Pros: Simple, memory efficient

Cons: Boundary problem: a burst at 0:59 and 1:01 allows 2× the limit in a 2-second span

Algorithm 5: Leaky Bucket

How it works:

• Requests enter a FIFO queue (the "bucket")
• Processed at a fixed rate
• If queue is full → reject

Pros: Smooth output rate

Cons: Burst traffic fills the queue; old requests may time out

Recommendation

Event Bus Design (Kafka)

Topic: api_rate_limiter-events
  Partitions: 64 (scale consumers horizontally)
  Partition key: entity_id (user_id / order_id — preserves per-entity ordering)
  Retention: 7 days (compliance) or 24h (high-volume telemetry)
  Replication factor: 3, min.insync.replicas: 2

Producer: idempotent producer enabled (enable.idempotence=true)
Consumer: consumer group "api_rate_limiter-processors"
  - At-least-once delivery + idempotent handlers (dedup by event_id)
  - DLQ topic: api_rate_limiter-events-dlq (poison messages after 3 retries)
  - Lag alert: consumer lag > 60s → scale workers

Design an API Rate Limiter: async side effects MUST NOT block the synchronous API response.
  Sync path: validate → persist source of truth → publish event → return 201
  Async path: consumers update caches, indexes, notifications, aggregates