Designing an API Rate Limiter

1. What is a Rate Limiter?

A rate limiter caps how many requests a sender can issue in a specific time window. Once the cap is reached, further requests are blocked or throttled. Examples include:

• A user can send only one message per second.
• A user is allowed only three failed credit card transactions per day.
• A single IP can only create twenty accounts per day.

2. Why do we need API Rate Limiting?

Rate limiting protects services from abusive behavior at the application layer, such as denial-of-service attacks, brute-force password attempts, and brute-force credit card transactions. It also helps:

• Misbehaving clients/scripts: Prevent intentional or accidental traffic spikes from overwhelming a service.
• Security: Limit the number of second-factor attempts or failed logins.
• Cost control: Stop sloppy client behavior like requesting the same data repeatedly.
• Revenue tiers: Offer different rate limits based on customer plan.
• Traffic smoothing: Keep the service stable for all users.

3. Requirements and Goals

Functional:

• Limit requests per entity within a time window, e.g., 15 requests per second.
• The limit must be considered across the entire cluster, not just one server.

Non-functional:

• High availability: the rate limiter should continue to protect the service even during failures.
• Low latency: it should not add substantial latency to requests.

4. How to do Rate Limiting?

Rate limiting defines the rate and speed at which consumers can access APIs. Throttling controls usage during a given period and can be applied at the application or API level. When a throttle limit is crossed, the system can reject, queue, or degrade the request.

5. Types of Throttling

• Hard throttling: Requests cannot exceed the limit.
• Soft throttling: The limit can be exceeded by a configured percentage, e.g., 110% of the base limit.
• Elastic throttling: Requests can exceed the limit when the system has spare resources.

6. Algorithms for Rate Limiting

Four algorithms cover almost every production rate limiter. The choice is a trade-off between accuracy, memory, burst tolerance, and downstream protection.

• Fixed window: Count requests within fixed time buckets, e.g., every minute on the clock. Simple and O(1) memory, but can allow bursts at bucket boundaries.
• Sliding window: Count requests within a window that slides with each request. More accurate but stores every timestamp (or approximates with sub-windows).
• Token bucket: A bucket holds up to capacity tokens and refills at rate tokens per second. A request spends one token; if no token is available it is rejected. Allows bursts up to the capacity, then throttles to the steady rate.
• Leaky bucket: A bucket drains at a fixed leak rate. Incoming requests add water; if the bucket would overflow, they are rejected. Smooths bursts into a flat output rate, which protects a fragile downstream.

Algorithm decision table

The token bucket and the leaky bucket admit the same number of requests under the same limits, but the timing differs: a token bucket serves a burst immediately, while a leaky bucket spreads the admitted requests out at the leak rate. See the interactive walkthrough at the end of this page for a side-by-side trace.

7. High-level Design

When a request arrives, the web server asks the rate limiter whether to serve or throttle it. If the request is allowed, it proceeds to the API servers; otherwise it is rejected with an appropriate status code.

8. API Contract

The rate limiter is consulted before a request reaches the API server. A minimal design exposes it as middleware or an internal service:

• GET /allow?entity={userId}&api={createURL} → returns {"allowed": true/false, "limit": 100, "remaining": 87, "resetAt": 1719000000}.
• The edge server calls this (or a local sidecar) and returns HTTP 429 when allowed: false.
• The key is entity + api + window, e.g., rate:user:42:createURL:2024-06-21T14:05.

Example request trace

Limit: 3 requests per minute for user 42 on the createURL API. Redis fixed-window counter keyed by minute bucket.

9. Basic System Design and Algorithm

Suppose we want to limit each user to three requests per minute. For each user we store a counter and the start time of the current window. On each request:

1. If the user is not in the store, insert them with count 1 and start time now, then allow.
2. If CurrentTime - StartTime >= 1 minute, reset the start time and count to 1, then allow.
3. If CurrentTime - StartTime < 1 minute and Count < 3, increment count and allow.
4. If Count >= 3, reject.

Problems:

• Boundary burst: A fixed window can allow twice the intended rate at the boundary, e.g., three requests at the last second of one minute and three at the first second of the next.
• Race conditions: In a distributed environment, two processes may read the same counter, both increment, and exceed the limit.

Atomicity with Redis: If Redis stores the counter, avoid a separate distributed lock for the read-update cycle. Locks serialize requests from the same user and add latency. Instead, use an atomic Redis operation such as a Lua script or INCR with TTL. A Lua script can read the current window, reset it if expired, and increment the counter in a single server-side execution, eliminating the race without a lock.

10. Sliding Window Algorithm

Store the timestamp of each request in a Redis sorted set per user. For each new request:

1. Remove timestamps older than CurrentTime - window.
2. If the set size is greater than or equal to the limit, reject; otherwise insert the current timestamp and allow. (With > alone, a set already holding exactly limit timestamps would admit one more — limit + 1 requests in a window.)

This is accurate but memory-intensive because every request is stored: at a limit of 500 requests/hour, 500 × (8-byte timestamp + ≈20 bytes of sorted-set overhead) ≈ 14 KB per user — ~14 GB for one million active users.

11. Sliding Window with Counters

Keep counts for smaller sub-windows, e.g., one count per minute for an hourly limit. When a request arrives, sum the counts in the relevant sub-windows to estimate the current rolling count. Store counters in a Redis hash with an expiration time. This uses far less memory than storing every timestamp.

Memory estimate

For a limit of 500 requests/hour with one-minute sub-windows, a user needs at most 60 counters. A counter (2 bytes) plus a normalized timestamp (4 bytes) plus Redis hash overhead (≈20 bytes) gives about 1.6 KB per user, or ~1.6 GB for one million active users — roughly an order of magnitude less than storing every request timestamp.

12. Data Sharding and Caching

Shard state by UserID to distribute load. For fault tolerance, replicate shards with consistent hashing. If different APIs need different limits, shard per user per API.

Caching recent active users in application servers reduces backend lookups. A write-back cache, where counters are updated in cache and written to the store asynchronously, is fast but can lose state if the cache crashes before flushing. For rate limiting, that may mean allowing more requests than intended after a failure. Use write-through or periodic persistence if strict enforcement matters, and design the cache to recover quickly from restarts.

13. Should we rate limit by IP or by user?

• IP: Simple but imprecise; multiple users can share a public IP, and a single user can rotate IPs.
• User: Requires authentication but accurately tracks the entity. Use a token passed with each request.
• Hybrid: Combine per-IP and per-user limits for defense in depth. This uses more memory but covers more abuse patterns.

14. Failure mode: what if the limiter backend is down?

A centralized rate limiter usually depends on a shared Redis instance. If Redis becomes unreachable, the limiter has two extreme answers and one practical middle ground:

• Fail-open: Admit every request. This preserves availability for legitimate users but removes protection exactly when a correlated traffic spike may be happening.
• Fail-closed: Reject every request. This protects downstream but turns a short Redis blip into a total outage for the API.
• Conservative local fallback: Each app server keeps a last-known-good snapshot of the bucket and enforces a stricter local-only limit while Redis is unreachable. This blocks egregious abuse without rejecting all legitimate traffic.

The right default depends on the endpoint: fail-closed for correctness or cost boundaries (e.g., a paid third-party API you are billed per call for); fail-open or local-fallback for availability-sensitive read paths. Either way, alert loudly when the fallback path is active — both “unenforced” and “rejecting everything” are incidents, not steady states.

15. Interactive walkthrough

Step through fixed, sliding, token-bucket, and leaky-bucket behavior on the same bursty traffic patterns.

🪜 Drill ladder: rate-limiter follow-ups

1. Boundary burst

Question: a fixed window of 100 requests/minute sees 100 requests at 14:05:59 and 100 requests at 14:06:00. Is this allowed?

Answer: yes, and it is usually wrong. A fixed window can admit 2× the intended rate across a one-second boundary. If that matters for your downstream, use a sliding window or a token bucket with capacity ≤ the steady-state burst you actually want to allow.

2. Distributed state

Question: you shard rate-limit state by user ID across Redis instances. One Redis node fails. What happens to users whose state was on that node?

Answer: without replication, those users are unprotected (fail-open) or locked out (fail-closed) until the node recovers. The better design replicates the counter or uses a consensus-backed store (e.g., Redis Cluster with replicas + failover) and a local fallback. The choice depends on whether the endpoint protects money (fail-closed) or availability (fail-open/fallback).

3. Fail-open vs fail-closed

Question: when is fail-closed the right answer?

Answer: fail-closed is correct when the limiter guards a finite, billable, or safety-critical resource: paid API calls, SMS sends, inventory reservations, or medical-device requests. Fail-open is correct when the limiter is a best-effort guardrail on an availability-critical read path, and rejecting everything would cause a larger outage than a temporary abuse spike. Document the choice per endpoint; do not let it be accidental.

Rate-limit headers: a worked example

When you reject or throttle a request, tell the client how to behave. The de-facto standard headers are:

Trace: user 42 is limited to 3 requests/minute on POST /createURL.

• At 14:05:40 the third request succeeds. Response: 200 OK, X-RateLimit-Remaining: 0, X-RateLimit-Reset: 1719000360.
• At 14:05:55 a fourth request arrives. Response: 429 Too Many Requests, Retry-After: 5 (the counter key is named by the minute bucket, so a fresh key takes over at 14:06:00 — the old key's 60s TTL merely garbage-collects it, it does not define the window edge). The client should back off, not retry immediately.
• At 14:06:01 a request lands in the new …:14:06 bucket. Response: 200 OK, X-RateLimit-Remaining: 2.

Client contract: a well-behaved client reads Retry-After and sleeps; a naive client that ignores it will be throttled again and may be penalized with exponential backoff on the server side.

Takeaways

• Rate limiters protect services from abuse, cost overruns, and cascading failures.
• Fixed windows are simple but inaccurate at boundaries; sliding windows are accurate but costly; token and leaky buckets are O(1) and differ in burst timing.
• Use atomic Redis operations (Lua scripts or INCR with TTL) rather than distributed locks to avoid races and latency.
• Be aware that write-back caching improves performance at the cost of durability during cache failures.
• Decide up front how the limiter behaves when its own backend is down; the answer is endpoint-specific.

Adapted from DesignGurus and standard rate-limiting practice. Re-authored and corrected for this guide. See also: Rate Limiting Algorithms: Token Bucket vs Leaky Bucket, System Design Problems II — Resolution Mechanisms.

16. Multi-region enforcement and where to place the limiter

Where the limiter lives. Two placements, and you usually want both: at the edge/API gateway for coarse per-IP / per-API-key limits (cheap, protects the whole fleet, stops floods before they cost you anything), and at the service/mesh layer for per-tenant business quotas that need application context (plan tier, per-endpoint cost). Edge limits are the blunt instrument; app-level limits know what the request actually costs.

The multi-region overshoot trap. If each region enforces the limit against its own local store, the global limit is silently multiplied by the number of regions. Concretely: a 100 req/min limit enforced independently in 3 regions admits up to 3 × 100 = 300 req/min globally for a user whose traffic is spread across them. You have three honest options:

• Single global store — every region checks one authoritative counter. Exact, but every decision now pays a cross-region round-trip (tens to hundreds of ms), which usually defeats the "must not add latency" requirement.
• Soft global budget — split the limit across regions (e.g. give each of 3 regions ~33 req/min). Bounds the global total with zero coordination, but wastes headroom when a user's traffic is skewed to one region.
• Local + global hybrid — each region admits fast against a local allowance (a fraction of the quota) and asynchronously reconciles usage with a global aggregator. This keeps the hot path off the cross-region path (low Redis QPS, low latency) while bounding overshoot to roughly the local slack, not N×. It is the common production compromise.

The point an interviewer probes: naming that distributed enforcement is a consistency-vs-latency choice, and that "just use one Redis" trades your latency SLO for exactness. Recompute the overshoot for the region count in the prompt before you pick.