Design a Rate Limiter

Difficulty: Intermediate

Question

Design a rate limiter that can handle millions of requests. Explain different algorithms and their trade-offs.

Answer

Rate limiting controls how many requests a client can make in a given time window. It protects services from abuse and ensures fair usage.

Common algorithms: 1. Token Bucket: Tokens added at fixed rate, each request consumes a token. Allows bursts. 2. Leaky Bucket: Requests queued and processed at fixed rate. Smooths out bursts. 3. Fixed Window: Count requests in fixed time windows (e.g., per minute). Simple but has boundary burst problem. 4. Sliding Window Log: Track exact timestamp of each request. Accurate but memory-intensive. 5. Sliding Window Counter: Hybrid of fixed window and sliding log. Good balance of accuracy and performance.

Placement: API Gateway level (global) or per-service (granular).

Code examples

Token Bucket Algorithm

class TokenBucket {
  constructor(capacity, refillRate) {
    this.capacity = capacity;     // max tokens
    this.tokens = capacity;       // current tokens
    this.refillRate = refillRate; // tokens per second
    this.lastRefill = Date.now();
  }

  tryConsume() {
    this.refill();

    if (this.tokens >= 1) {
      this.tokens -= 1;
      return true;  // request allowed
    }
    return false;   // rate limited
  }

  refill() {
    const now = Date.now();
    const elapsed = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(
      this.capacity,
      this.tokens + elapsed * this.refillRate
    );
    this.lastRefill = now;
  }
}

// Usage: 10 requests/second, burst up to 20
const limiter = new TokenBucket(20, 10);

app.use((req, res, next) => {
  if (limiter.tryConsume()) {
    next();
  } else {
    res.status(429).json({
      error: 'Too Many Requests',
      retryAfter: Math.ceil(1 / limiter.refillRate)
    });
  }
});

Token bucket allows short bursts (up to capacity) while enforcing an average rate. It is the most commonly used algorithm in production systems like AWS and Stripe.

Distributed Rate Limiter with Redis

// Sliding window counter using Redis
async function slidingWindowRateLimit(userId, limit, windowSec) {
  const now = Date.now();
  const windowStart = now - windowSec * 1000;
  const key = `ratelimit:${userId}`;

  // Use Redis sorted set with timestamps as scores
  const multi = redis.multi();

  // Remove expired entries
  multi.zremrangebyscore(key, 0, windowStart);

  // Count requests in current window
  multi.zcard(key);

  // Add current request
  multi.zadd(key, now, `${now}:${Math.random()}`);

  // Set expiry on the key
  multi.expire(key, windowSec);

  const results = await multi.exec();
  const requestCount = results[1][1];

  return {
    allowed: requestCount < limit,
    remaining: Math.max(0, limit - requestCount - 1),
    resetAt: new Date(now + windowSec * 1000)
  };
}

// Middleware
app.use(async (req, res, next) => {
  const result = await slidingWindowRateLimit(
    req.ip, 100, 60  // 100 requests per 60 seconds
  );

  res.set('X-RateLimit-Limit', '100');
  res.set('X-RateLimit-Remaining', result.remaining);
  res.set('X-RateLimit-Reset', result.resetAt.toISOString());

  if (!result.allowed) {
    return res.status(429).json({ error: 'Rate limit exceeded' });
  }
  next();
});

Redis sorted sets enable distributed rate limiting across multiple server instances. The sliding window approach is accurate and avoids the boundary burst problem of fixed windows.

Multi-Tier Rate Limiting

// Different limits for different tiers and endpoints
const RATE_LIMITS = {
  free: {
    global: { limit: 100, window: 3600 },    // 100/hour
    search: { limit: 10, window: 60 },        // 10/min
    upload: { limit: 5, window: 3600 }        // 5/hour
  },
  premium: {
    global: { limit: 1000, window: 3600 },   // 1000/hour
    search: { limit: 60, window: 60 },        // 60/min
    upload: { limit: 50, window: 3600 }       // 50/hour
  }
};

function rateLimitMiddleware(action) {
  return async (req, res, next) => {
    const tier = req.user?.plan || 'free';
    const config = RATE_LIMITS[tier][action];
    const key = `${req.user?.id || req.ip}:${action}`;

    const result = await slidingWindowRateLimit(
      key, config.limit, config.window
    );

    if (!result.allowed) {
      return res.status(429).json({
        error: `Rate limit exceeded for ${action}`,
        retryAfter: config.window,
        upgrade: tier === 'free'
          ? 'Upgrade to premium for higher limits'
          : undefined
      });
    }
    next();
  };
}

// Apply per-route
app.get('/api/search', rateLimitMiddleware('search'), searchHandler);
app.post('/api/upload', rateLimitMiddleware('upload'), uploadHandler);

Production systems use tiered rate limiting: different limits per user plan and per endpoint. This prevents abuse while allowing legitimate heavy usage for paying customers.

Key points

Concepts covered

Token Bucket, Sliding Window, Fixed Window, Redis, Distributed Rate Limiting