System Design: Designing a Highly Scalable Rate Limiter

Rate limiting is a foundational component of modern, high-scale distributed systems. Whether protecting large language model APIs (like ChatGPT or Claude) or safeguarding utility services (such as URL shorteners), a rate limiter acts as the defensive front door of an infrastructure. It ensures system availability, protects databases from resource exhaustion, and mitigates abuse without degrading the experience of legitimate users.

1. The Core Problem: Why Systems Need Rate Limiting

To understand the necessity of a rate limiter, consider a real-world abuse scenario on a public-facing service like a URL shortener.

Real-Life Analogy: The "Shadow" User

Imagine a user named Shadow who signs up for a free account on a URL shortener platform. Under normal circumstances, users generate a handful of short links per day. However, Shadow writes a simple script that runs in a loop, firing API requests to the creation endpoint continuously:

This high-volume burst introduces two critical failure modes to the system:

1. Database Pollution: The database is flooded with 1 million garbage links that serve no legitimate purpose, permanently consuming expensive storage.
2. Resource Starvation: The application servers and database are kept so busy processing Shadow's junk requests that legitimate users experience severe latency or complete service outages.

Crucially, Shadow has not hacked or breached the server; they are simply utilizing the public API too rapidly. To protect system resources, we must implement a component that caps the number of requests a user can make within a given timeframe. This component is the Rate Limiter.

2. Step 1: Clarifying Requirements & User Identification

When designing a rate limiter in an interview setting, the first step is to clarify the scope, rules, and identification mechanisms.

Identifying the Request Source

To limit requests, the system must identify who is making them. There are three primary identifiers, each with distinct trade-offs:

1. IP Address:
   • The Problem: Multiple users often share a single external IP address (e.g., an office of 300 people sharing a single NAT internet connection). If one person is noisy, the rate limiter might block all 300 users. Conversely, sophisticated attackers can easily rotate through thousands of cheap IP addresses to bypass limits.
2. API Key:
   • The Problem: This is highly effective but niche. It only works for developer-facing APIs. Standard consumer mobile or web application users do not have API keys.
3. User Account ID:
   • The Problem: This is the most reliable identifier, but it cannot be used for unauthenticated endpoints (e.g., landing pages, login screens, or signup APIs) where the user is not yet logged in.

The Hybrid Strategy

To balance these trade-offs, we adopt a hybrid identification strategy:

• Authenticated Users: Track and limit requests per Account ID.
• Unauthenticated Users: Track and limit requests per IP Address.

Defining the Limits & Rejection Behavior

• The Limit: Every user is allowed a maximum of 100 API requests per minute.

  Note on Setting Limits: In a real-world scenario, do not invent this number arbitrarily. You must analyze production traffic logs to determine what a normal human user actually does in a minute, and then set the limit comfortably above that baseline.

• Rejection Strategy (Drop vs. Queue):

  • Queueing: If excess requests are placed in a queue to be processed later, the client application—unaware of the queue—will often retry the request. This introduces duplicate requests and compounds system load.
  • Dropping (Polite Rejection): Excess requests must be rejected immediately but politely. The system must inform the client that they have been rate-limited and specify exactly when they can try again.

3. Step 2: Back-of-the-Envelope Estimations

To make informed architectural decisions, we must calculate the storage and throughput requirements of our rate limiter.

Memory Footprint Estimation

If we use a basic tracking mechanism, we need to store a minimal amount of data per user:

• Data points: One counter (integer) and one timestamp.
• Size: Approximately 50 bytes per user.

For a system with 10 million active users:

Because 500 MB of data easily fits within the RAM of a single modern virtual machine, memory capacity is not a bottleneck for a basic counter-based design.

Throughput and Request Rates

• Active Users: 10 million.
• Average Usage: 100 requests per user per day (note that this is average daily usage, not the maximum limit).
• Total Daily Requests: 1 billion requests/day.
• Average Request Rate:

• Peak Request Rate: Assuming peak traffic is $3\times$ the average:

Key Distinction: Do not confuse the average daily usage (100 requests per day) with the rate limit (100 requests per minute). Normal users generate traffic in short, concentrated bursts when they open the app, but their total daily volume remains low. A per-minute limit accommodates these natural human bursts while instantly blocking automated scripts that attempt sustained high-volume traffic.

4. Step 3: API Design & Architectural Placement

API Response Contract

When a request is allowed, the system processes it normally but appends metadata headers to help well-behaved clients self-regulate. When a request is blocked, the system returns an HTTP 429 Too Many Requests status code.

HTTP Headers for Rate Limiting

• X-RateLimit-Remaining: How many requests the user has left in the current window.
• X-RateLimit-Reset: The Unix timestamp indicating when the limit resets.
• Retry-After: The number of seconds the client must wait before making another request (crucial for preventing clients from continuously spamming the limiter).

Architectural Placement: The API Gateway

The rate limiter must sit at the absolute front door of the infrastructure, embedded within or directly behind the API Gateway.

If the rate limiter were placed deeper in the stack (e.g., next to the database), a rejected request would have already traversed the load balancer, gateway, and application servers—wasting valuable CPU, memory, and network bandwidth on a request destined for rejection.

5. Algorithmic Evolution: Fixed Window vs. Sliding Window Log

Choosing the right rate-limiting algorithm requires balancing accuracy against memory consumption.

Approach 1: Fixed Window Algorithm

The Fixed Window algorithm divides time into static, non-overlapping intervals (e.g., 1-minute windows based on the system clock).

[12:00:00 - 12:01:00]      [12:01:00 - 12:02:00]
  Counter: 0 to 100          Counter: 0 to 100

• Mechanism: For each user, a counter tracks requests within the current clock minute. If the counter is under 100, the request is allowed and the counter increments. When the clock strikes the next minute, the counter resets to 0.

• The Edge Case (The Double-Limit Burst): Suppose a user named Allen sends 100 requests in the very last second of Minute 1 (12:00:59). These are allowed. The clock rolls over to Minute 2 (12:01:00), and the counter resets to 0. Allen immediately sends another 100 requests in the first second of Minute 2 (12:01:01).

  CODE

  Copy

  Time:   12:00:58  12:00:59  |  12:01:00  12:01:01
  Reqs:      0        100     |     0        100
                              ^
                         Window Reset
  

  Result: Allen successfully pushed 200 requests within a 2-second window, completely bypassing the intended limit of 100 requests per minute. This occurs because the window boundaries are rigid and do not slide with time.

Approach 2: Sliding Window Log Algorithm

To eliminate the sharp edges of the Fixed Window algorithm, the Sliding Window Log tracks the exact timestamp of every single request.

• Mechanism:
  1. When a request arrives, write its timestamp to a list (log) associated with the user.
  2. Scan the list and delete all timestamps older than 60 seconds from the current time.
  3. Count the remaining timestamps in the list.
  4. If the count is less than 100, allow the request. If it is 100 or more, reject the request.

User Log: [ 12:00:15, 12:00:30, 12:00:45, 12:01:02 ]
             \_________________ _________________/
                               v
                     Only count timestamps 
                     within the last 60s

• The Problem (Memory Explosion): While highly accurate, this approach is extremely expensive. Instead of storing a single 50-byte counter, we must store every timestamp.
  • Storing 100 timestamps for an active user requires roughly 2.5 KB of memory.
  • For 10 million users, this requires:

• This cost scales linearly with the rate limit. If an interviewer increases the limit to 10,000 requests per minute, the memory requirements render this approach completely unfeasible.

6. The Token Bucket Algorithm: The Industry Standard

The Token Bucket algorithm is the production standard utilized by major API providers like Stripe and GitHub. It elegantly supports traffic bursts while maintaining a strict sustained rate limit, all with a minimal memory footprint.

How It Works

Imagine a bucket that holds a maximum of $N$ tokens (e.g., $N = 100$).

• Every API request consumes exactly 1 token from the bucket.
• If the bucket has tokens, the request is allowed, and a token is removed.
• If the bucket is empty, the request is rejected.
• The bucket is continuously refilled with tokens at a constant rate $R$ (e.g., 100 tokens per minute, which is approximately 1.67 tokens per second).

Handling Bursts vs. Sustained Rates

If Allen does not make any API calls for a while, his bucket fills up to its maximum capacity of 100 tokens.

• The Burst: Allen can execute 100 requests in a single 2-second burst. This drains the bucket to 0.
• The Sustained Rate: Once the bucket is empty, Allen is not completely locked out. He can continue to make requests, but only as fast as the bucket refills—approximately 2 requests per second.

This behavior is highly desirable: it allows applications to load quickly via initial bursts, but prevents sustained high-velocity abuse.

Memory Efficiency (Lazy Refilling)

We do not need a background thread constantly updating millions of buckets in memory (which would consume massive CPU cycles). Instead, we calculate the refill lazily whenever a request actually arrives.

We only need to store two values per user:

1. tokens_left (Float): The number of tokens currently in the bucket.
2. last_refill_timestamp (Timestamp): The exact time the bucket was last accessed.

The Lazy Refill Formula

When a new request arrives at current_time:

This calculation requires only basic arithmetic, and the storage footprint remains a tiny 50 bytes per user.

7. Comparative Synthesis of Rate Limiting Algorithms

8. Distributed Architecture: Solving the Multi-Gateway Problem

In a production environment, a single API Gateway is a single point of failure (SPOF) and cannot handle high traffic volumes. Instead, we run multiple API Gateways behind a Load Balancer.

The Local Counter Problem

If each API Gateway tracks token buckets in its own local, in-memory cache, the rate limiter becomes inaccurate:

If the Load Balancer splits Allen's traffic evenly between Gateway 1 and Gateway 2, Allen can make 200 requests because neither gateway knows about the requests processed by the other. The local counters "lie" in a distributed system.

The Solution: Centralized Shared Cache (Redis)

To maintain a single, accurate count, we move the token buckets out of the gateways' local memory and into a centralized, high-performance shared memory store: Redis.

Now, regardless of which gateway receives a request, it queries and updates the single, authoritative bucket stored in Redis.

9. Concurrency & Race Conditions: Achieving Atomicity with Lua Scripts

Moving the token buckets to Redis introduces a classic distributed systems problem: race conditions.

The Read-Modify-Write Race Condition

Accessing and updating a token bucket is not a single, atomic action. It consists of three distinct steps:

1. Read: Retrieve the current tokens_left and last_refill_timestamp from Redis.
2. Calculate: Compute the refilled tokens and determine if enough tokens exist to allow the request.
3. Write: Save the updated tokens_left and last_refill_timestamp back to Redis.

If two requests from the same user hit Gateway 1 and Gateway 2 at the exact same millisecond when only 1 token remains, the following sequence occurs:

Both gateways read a value of 1, both approve their respective requests, and both write back 0. The user successfully bypassed the rate limit because the operations overlapped.

The Fix: Atomic Operations via Redis Lua Scripts

To prevent this race condition, we must execute all three steps as a single, uninterrupted transaction. We achieve this by wrapping the logic in a Lua Script and executing it directly inside Redis.

Because Redis is single-threaded, it runs the entire Lua script in one go. While the script is executing for a specific user's bucket, no other gateway can read or write to that key.

Conceptual Token Bucket Lua Script

-- KEYS[1]: User's rate limit key (e.g., "limit:user_123")
-- ARGV[1]: Max bucket capacity (e.g., 100)
-- ARGV[2]: Refill rate per millisecond (e.g., 0.00167)
-- ARGV[3]: Current timestamp in milliseconds
-- ARGV[4]: Requested tokens (usually 1)

local rate_limit = redis.call('HMGET', KEYS[1], 'tokens', 'last_updated')

local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local current_tokens
local last_updated

if not rate_limit[1] then
    -- First request: initialize bucket
    current_tokens = capacity
    last_updated = now
else
    current_tokens = tonumber(rate_limit[1])
    last_updated = tonumber(rate_limit[2])
end

-- Calculate lazy refill
local elapsed = now - last_updated
local tokens_to_add = elapsed * refill_rate
current_tokens = math.min(capacity, current_tokens + tokens_to_add)
last_updated = now

-- Check if user has enough tokens
if current_tokens >= requested then
    current_tokens = current_tokens - requested
    redis.call('HMSET', KEYS[1], 'tokens', current_tokens, 'last_updated', last_updated)
    return 1 -- Allowed
else
    redis.call('HMSET', KEYS[1], 'tokens', current_tokens, 'last_updated', last_updated)
    return 0 -- Rejected
end

10. Bottleneck Analysis, Latency, and Failure Modes

Redis Performance & Scale

• Capacity: A single Redis instance can easily handle up to 100,000 operations per second.
• Our Peak Demand: Our back-of-the-envelope estimation calculated a peak of 35,000 requests per second.
• Conclusion: A single Redis instance is highly capable of handling our peak load, leaving ample room for future growth.

Network Latency and Co-location

Every API request must now make a round-trip to Redis before it can be processed.

• If the API Gateways and the Redis instance are co-located in the same data center/region, this network hop takes roughly 1 millisecond. This is highly acceptable.
• If the API Gateway is in one region (e.g., US-East) and the Redis instance is in another (e.g., EU-West), that hop can take 50 milliseconds or more. The rate limiter instantly becomes the primary bottleneck of the entire system.
• Mitigation: Ensure the Redis rate-limiting cluster is strictly co-located with the API Gateway instances.

Failure Modes: What If Redis Goes Down?

If the shared Redis instance crashes, the API Gateways can no longer verify token counts. We must choose between two classic failure modes:

1. Fail Open

• Behavior: If the gateway cannot reach Redis, it bypasses the rate limiter and allows all incoming requests through to the microservices.
• Trade-off: The system risks being overwhelmed by an attacker or a noisy user for a few minutes, but legitimate users experience zero downtime.
• Real-World Example: Stripe configures its rate limiters to fail open, ensuring their API remains functional for merchants even if the rate-limiting infrastructure experiences an outage.

2. Fail Closed

• Behavior: If the gateway cannot reach Redis, it blocks all incoming requests and returns an error.
• Trade-off: The system is completely safe from abuse, but 100% of legitimate users are locked out.
• Use Case: This is critical for highly sensitive endpoints, such as a /login or /reset-password endpoint, where failing open would allow attackers to launch massive, unchecked credential-stuffing or brute-force attacks.

Summary and Key Takeaways

• Front-Door Protection: A rate limiter belongs at the absolute front door of your system (the API Gateway) to reject abusive traffic before it consumes downstream application and database resources.
• Token Bucket Superiority: The Token Bucket algorithm is highly memory-efficient (~50 bytes per user) and allows you to configure the sustained rate and the burst allowance as two separate, independent numbers.
• Lazy Refilling: Avoid background cron jobs to update counters. Instead, calculate token refills lazily on request arrival using timestamps to save CPU cycles.
• Distributed State Management: Local in-memory counters lie in distributed environments. When scaling horizontally across multiple gateways, the rate-limiting state must live in a shared, centralized store like Redis.
• Atomic Operations: To prevent concurrency race conditions (Read-Modify-Write bugs) in a shared cache, use Redis Lua scripts to execute the rate-checking logic as a single, atomic step.
• Fail-Open vs. Fail-Closed: Choose your failure mode based on the endpoint's sensitivity. Fail open for standard product APIs to preserve user experience; fail closed for security-sensitive endpoints like authentication.
• The Shared-State Pattern: The pattern of using a centralized store with atomic updates to manage shared resources is a fundamental system design concept. It reappears in many other contexts, such as ensuring a concert ticket is not sold to two people, or ensuring a ride-share driver is not assigned to two passengers simultaneously.