Rate Limiter

A rate limiter controls the number of requests a client can make to a service within a given time window. In system design interviews, rate limiting appears whenever you discuss API design, security, or protecting backend services from being overwhelmed.

This page covers what you need to know for interviews: why rate limiting matters, the algorithms that power it, how to design a distributed rate limiter, and the trade-offs between different approaches. Understanding these concepts helps you design systems that stay available under load and protect against abuse.

Why Rate Limiting Matters

Without rate limiting, a single client—whether malicious or buggy—can overwhelm your service. Rate limiters provide:

• Protection from abuse — Defend against denial-of-service (DoS) attacks, brute-force login attempts, and API scraping
• Resource fairness — Ensure one heavy user doesn't degrade service for others
• Cost control — Prevent runaway costs from excessive API calls or compute usage
• Stability — Smooth out traffic spikes and protect downstream services

Where to Place Rate Limiters

Rate limiting can happen at different layers. Each location has trade-offs.

Client-Side

Enforce limits in the client application itself.

Pros: Reduces unnecessary requests, improves user experience Cons: Can be bypassed, can't protect against malicious clients

Client-side limiting is a courtesy, not a security measure. Always have server-side enforcement.

Server-Side

Place the rate limiter in your application servers or as a dedicated service.

In-application:

• Simple to implement
• No extra network hop
• Harder to manage across multiple services

Dedicated service:

• Centralized policy management
• Reusable across services
• Adds latency (extra network hop)

API Gateway / Middleware

Most common in production. Rate limiting happens at the API gateway or load balancer layer before requests reach backend services.

Advantages:

• Single enforcement point
• Works across all services
• Often built into API gateway products (Kong, AWS API Gateway, NGINX)

Types of Throttling

When a client exceeds their limit, you have options for how strictly to enforce it.

Hard Throttling

Strictly enforce the limit. Once exceeded, all requests are rejected until the window resets.

Limit: 100 requests/minute
Request 101: Rejected (429 Too Many Requests)
Request 102: Rejected
...
Next minute: Counter resets, requests allowed again

Use when: Security is critical, resource protection is paramount, or you're billing by request count.

Soft Throttling

Allow a small percentage above the limit. Useful for handling brief spikes gracefully.

Limit: 100 requests/minute (with 10% soft limit)
Requests 1-100: Allowed
Requests 101-110: Allowed (within soft limit)
Request 111+: Rejected

Use when: You want to accommodate legitimate traffic bursts without disrupting user experience.

Elastic / Dynamic Throttling

Adjust limits based on system capacity. When the system is healthy, allow more requests; when under stress, tighten limits.

System at 50% capacity: Allow 200 requests/minute
System at 80% capacity: Allow 100 requests/minute
System at 95% capacity: Allow 50 requests/minute

Use when: You want to maximize throughput while protecting system stability.

Rate Limiting Algorithms

Five algorithms dominate rate limiting implementations. Each has distinct characteristics for interviews.

Token Bucket

The bucket holds tokens (permissions to make requests). Tokens are added at a constant rate. Each request consumes a token. If the bucket is empty, the request is rejected.

How it works:

1. Bucket has capacity C (maximum tokens)
2. Tokens added at rate R per time unit
3. Request arrives → check if tokens available
4. If yes: consume token, allow request
5. If no: reject request

Parameters:

• Bucket capacity (C) — Maximum burst size
• Refill rate (R) — Sustained request rate

Example: Bucket capacity = 10, refill rate = 1 token/second

• Can handle a burst of 10 requests instantly
• Sustained rate limited to 1 request/second
• After burst, must wait for tokens to refill

Used by: AWS, Stripe, many API providers

Leaking Bucket

Requests enter a queue (bucket) and are processed at a constant rate. If the queue is full, new requests are dropped.

How it works:

1. Requests added to a FIFO queue
2. Queue has fixed capacity
3. Requests processed at constant rate (leak rate)
4. If queue full, new requests dropped

Parameters:

• Bucket capacity (C) — Queue size
• Outflow rate (R) — Processing rate

Best for: When you need a strictly constant processing rate, like network traffic shaping.

Fixed Window Counter

Divide time into fixed windows (e.g., each minute). Count requests per window. Reject when count exceeds limit.

Window: 12:00:00 - 12:00:59
Limit: 100 requests
Requests 1-100: Allowed
Requests 101+: Rejected

Window: 12:01:00 - 12:01:59
Counter resets to 0

Parameters:

• Window size (W) — Time duration (e.g., 1 minute)
• Request limit (R) — Max requests per window

The Boundary Problem:

A client can make 2x the limit by timing requests at window boundaries:

Limit: 100 requests per minute

12:00:30 - 12:00:59: 100 requests (allowed)
12:01:00 - 12:01:30: 100 requests (allowed)

Result: 200 requests in 1 minute (12:00:30 to 12:01:30)

This violates the intended rate limit.

Sliding Window Log

Track the timestamp of each request in a sorted log. When a new request arrives, remove expired entries and count remaining ones.

How it works:

1. Store timestamp of each request in a log (sorted set)
2. New request arrives → remove timestamps older than window size
3. Count remaining entries
4. If count < limit: allow and add timestamp
5. If count >= limit: reject

Example: Limit 2 requests per minute

12:00:10 - Request 1: Log = [12:00:10], Count = 1, Allowed
12:00:40 - Request 2: Log = [12:00:10, 12:00:40], Count = 2, Allowed
12:00:50 - Request 3: Log = [12:00:10, 12:00:40], Count = 2, Rejected
12:01:15 - Request 4: Log = [12:00:40] (12:00:10 expired), Count = 1, Allowed

Best for: When accuracy is critical and you can afford the memory cost.

Sliding Window Counter

Combines fixed window counter with sliding window concept. Uses weighted average of current and previous window counts.

How it works:

1. Track counts for current window and previous window
2. Calculate weighted rate based on position in current window
3. Allow if weighted rate < limit

Formula:

Rate = (Previous window count × overlap%) + Current window count

Where overlap% = (window_size - elapsed_time) / window_size

Example: Limit 100 requests/minute, current time is 15 seconds into the window

Previous window: 88 requests
Current window: 12 requests
Overlap: (60 - 15) / 60 = 75%

Weighted rate = 88 × 0.75 + 12 = 66 + 12 = 78

78 < 100 → Allow request

Best for: Most production use cases. Good default choice.

Redis implementation:

def is_allowed_sliding_window(user_id, limit, window_seconds):
    now = time.time()
    current_window = int(now // window_seconds)
    prev_window = current_window - 1
    elapsed = now % window_seconds

    # Get counts from both windows
    prev_count = int(redis.get(f"rate:{user_id}:{prev_window}") or 0)
    curr_count = int(redis.get(f"rate:{user_id}:{current_window}") or 0)

    # Calculate weighted rate
    weight = (window_seconds - elapsed) / window_seconds
    rate = prev_count * weight + curr_count

    if rate >= limit:
        return False

    # Increment current window counter
    pipe = redis.pipeline()
    pipe.incr(f"rate:{user_id}:{current_window}")
    pipe.expire(f"rate:{user_id}:{current_window}", window_seconds * 2)
    pipe.execute()
    return True

Algorithm Comparison

High-Level Design

Let's design a rate limiting service. Start with requirements.

Requirements

Functional:

• Limit requests based on configurable rules (requests per time window)
• Support multiple rate limiting dimensions (per user, per IP, per API key, per endpoint)
• Return appropriate response when limit exceeded (HTTP 429)

Non-Functional:

• Low latency — Rate check should add minimal overhead (<5ms)
• High availability — Rate limiter failure shouldn't block all traffic
• Scalability — Handle millions of requests across distributed servers
• Accuracy — Limits should be reasonably accurate (not necessarily exact)

Architecture Overview

Components:

1. Rate Limiter Service — Checks requests against rules, allows or rejects
2. Rules Database — Stores rate limiting rules (limit, window, dimensions)
3. Counter Store (Redis) — Fast storage for request counts
4. Rules Cache — Cache rules locally to avoid DB lookups per request

Detailed Design

Rules Configuration

Rate limiting rules define the limits. Example rule from Lyft's rate limiter:

domain: messaging
descriptors:
  - key: message_type
    value: marketing
    rate_limit:
      unit: day
      requests_per_unit: 5

This limits marketing messages to 5 per day per user.

Common rule dimensions:

• Per user — user_id:123 → 100 requests/minute
• Per IP — ip:192.168.1.1 → 50 requests/minute
• Per API key — api_key:abc → 1000 requests/hour
• Per endpoint — POST /api/upload → 10 requests/minute

Rules are stored in a database and cached in memory for fast access.

Request Flow

Steps:

1. Identify client — Extract user ID, IP address, or API key
2. Get rules — Look up applicable rate limit rules (from cache)
3. Check counter — Query Redis for current request count
4. Make decision — Allow if under limit, reject if over
5. Update counter — Increment count (even for allowed requests)
6. Return response — Include rate limit headers

Response Headers

Standard headers communicate rate limit status to clients:

HTTP/1.1 200 OK
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 45
X-RateLimit-Reset: 1640000000

# Or when exceeded:
HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1640000000
Retry-After: 30

• X-RateLimit-Limit — Maximum requests allowed
• X-RateLimit-Remaining — Requests remaining in window
• X-RateLimit-Reset — Unix timestamp when window resets
• Retry-After — Seconds to wait before retrying (on 429)

Distributed Rate Limiting

When rate limiters run on multiple servers, they need shared state. Two approaches:

Centralized (Redis)

All rate limiter instances share a Redis cluster for counters.

Rate Limiter 1 ─┐
Rate Limiter 2 ─┼─→ Redis Cluster
Rate Limiter 3 ─┘

Pros: Accurate counts, consistent enforcement Cons: Redis becomes a dependency, adds latency

Local with Synchronization

Each instance maintains local counters, periodically syncing with central store.

Pros: Faster (no network hop for most checks), more resilient Cons: Less accurate (can temporarily exceed limits during sync gaps)

Handling Race Conditions

High concurrency creates race conditions with the "get-then-set" pattern:

Thread 1: GET counter → 99
Thread 2: GET counter → 99
Thread 1: SET counter → 100 (allows request)
Thread 2: SET counter → 100 (allows request - should have been rejected!)

Solutions:

1. Lua scripts — Redis executes Lua scripts atomically as a single unit. This ensures INCR + EXPIRE happen together without interleaving from other clients.

-- Redis Lua script for atomic rate limiting
-- Entire script executes atomically - no race conditions
local current = redis.call('INCR', KEYS[1])
if current == 1 then
    redis.call('EXPIRE', KEYS[1], ARGV[1])
end
if current > tonumber(ARGV[2]) then
    return 0  -- Reject
end
return 1  -- Allow

2. Distributed locks — Acquire lock before read-modify-write (adds latency)

3. Sorted sets with timestamps — For sliding window log algorithm

Redis's single-threaded execution model means Lua scripts run without interruption, making them ideal for rate limiting.

Handling Failures

What happens when the rate limiter or Redis fails?

Fail-Open (Allow All)

• If rate limiter can't check, allow the request
• Maintains availability but loses protection
• Use for non-critical rate limiting

Fail-Closed (Deny All)

• If rate limiter can't check, deny the request
• Maintains protection but hurts availability
• Use for security-critical limits (login attempts)

Performance Optimization

Rate limiting should add minimal latency. Optimizations:

1. Local caching of rules Don't fetch rules from database for every request. Cache them locally with periodic refresh.

2. Async counter updates For non-critical limits, check the counter synchronously but update asynchronously.

1. GET current_count from Redis
2. If under limit: allow request immediately
3. INCR counter asynchronously (don't wait)

3. Sharded counters For extremely high-traffic keys, shard the counter across multiple Redis keys and aggregate.

Instead of: user:123:count = 1000
Use: user:123:count:0 = 250
     user:123:count:1 = 250
     user:123:count:2 = 250
     user:123:count:3 = 250

Design Evaluation

Low Latency

• Rules cached locally (no DB lookup per request)
• Redis provides sub-millisecond counter operations
• Async updates reduce critical path latency
• Typical overhead: 1-5ms per request

High Availability

• Multiple rate limiter instances behind load balancer
• Redis Cluster with replication for counter storage
• Fail-open policy prevents total outages
• Graceful degradation when Redis is unavailable

Scalability

• Stateless rate limiter instances scale horizontally
• Redis Cluster handles high throughput
• Sharded counters for hot keys
• Rules database read-replicas for scale

Accuracy Trade-offs

Perfect accuracy requires coordination, which adds latency. Most systems accept some inaccuracy:

• Sliding window counter is approximate but efficient
• Distributed instances may briefly allow slightly over the limit
• This trade-off is usually acceptable—rate limiting is about protection, not billing

Common Interview Patterns

Rate Limiting by Different Dimensions

Per-user limiting: Prevent individual users from abusing the service

Key: user:{user_id}:requests
Limit: 100 requests/minute

Per-IP limiting: Basic protection against unauthenticated abuse

Key: ip:{ip_address}:requests
Limit: 50 requests/minute

Per-endpoint limiting: Protect expensive operations

Key: endpoint:POST:/api/upload:requests
Limit: 10 requests/minute

Global limiting: Protect overall system capacity

Key: global:requests
Limit: 10,000 requests/second

Tiered Rate Limits

Different limits for different user tiers:

Implementation: Look up user tier, apply corresponding rules.

Handling Distributed Denial of Service

Rate limiting alone doesn't stop DDoS attacks—traffic still hits your infrastructure. Defense in depth:

1. Edge protection — CDN/WAF blocks obvious attacks
2. IP reputation — Block known bad IPs
3. Rate limiting — Per-IP limits catch distributed attacks
4. Circuit breakers — Shed load when overwhelmed

Technology Options

Redis

The most common choice for distributed rate limiting. For more on Redis capabilities and patterns, see Distributed Cache.

Why Redis:

• Sub-millisecond latency
• Atomic operations (INCR, Lua scripts)
• Built-in expiration (TTL for windows)
• Redis Cluster for high availability

Example implementation:

def is_allowed(user_id, limit, window_seconds):
    key = f"rate_limit:{user_id}"
    current = redis.incr(key)
    if current == 1:
        redis.expire(key, window_seconds)
    return current <= limit

In-Memory (Local)

For single-server or when eventual consistency is acceptable.

Libraries: Guava RateLimiter (Java), python-ratelimit

Pros: No external dependency, very fast Cons: Not distributed, lost on restart

API Gateway Built-in

Most API gateways include rate limiting:

Quick Reference

Algorithm Selection

Throttling Type Selection

Interview Checklist

When discussing rate limiting:

• Explained why rate limiting is needed (protection, fairness, cost)
• Chose where to place it (API gateway default)
• Selected an algorithm (sliding window counter default)
• Discussed distributed implementation (Redis)
• Addressed race conditions (atomic operations)
• Covered failure modes (fail-open vs fail-closed)
• Mentioned response headers (429, Retry-After)
• Discussed multiple dimensions (per-user, per-IP, per-endpoint)

What Interviewers Look For

1. Understanding of purpose — You know rate limiting protects systems from abuse and ensures fairness, not just that "you need it."

2. Algorithm knowledge — You can explain token bucket and sliding window, know the fixed window boundary problem, and choose appropriately.

3. Distributed thinking — You understand that rate limiting across multiple servers requires shared state and can discuss Redis-based solutions.

4. Trade-off awareness — You can articulate the accuracy vs. latency trade-off and explain fail-open vs. fail-closed decisions.

5. Practical knowledge — You mention real solutions (Redis, API gateway rate limiting) and know about 429 responses and Retry-After headers.

Rate limiting is infrastructure that protects your system—demonstrate competence by explaining where you'd place it, which algorithm you'd use, and how you'd handle the distributed case. Then move on to the unique aspects of your design.