Rate Limiting Algorithms
You'll learn to
- -Explain what rate limiting protects against and where the limiter sits
- -Compare fixed window, sliding window, token bucket and leaky bucket by tracing a burst through each
- -Choose what to count (user, key, IP, endpoint) and what the client sees when it is over the limit
- -Make a limit hold across many servers, and size the shared counter store
A fast, well-cached system is still vulnerable to one thing: a single client, malicious or just buggy, sending far more requests than any reasonable user would. A script stuck in a retry loop can send thousands of requests a second, and every one of them costs your servers real work. Rate limiting is how you protect the system you have built from being overwhelmed by any one source, and it is also how you keep a fair share of capacity for everyone else.
An Analogy: The Token Jar at the Door
Imagine a club with a jar of tokens by the door. A helper drops in one new token every second, but the jar holds at most 10, so extra tokens spill and are lost. To get in, a visitor must take a token. If the jar is empty they are turned away, or told to wait. Someone who has been away for a while finds a full jar and can bring ten friends in at once, but over a long time nobody can get in faster than one visitor per second.
- -The visitors are requests, and the doorman is the rate limiter.
- -The jar is the bucket, and its size (10) is the burst the limiter will allow.
- -The one token per second is the refill rate, which is the long-run limit.
- -An empty jar means the request is rejected, usually with an HTTP 429 response.
The limiter sits at the edge and turns away excess requests before they reach the application servers:
The rate limiter sits at the edge, rejecting excess requests before they ever reach application servers.
Four Common Algorithms
- -Fixed window: count requests in each clock window (say each minute) and reject once the count passes the limit. Very simple and cheap, but it has a flaw at the window boundary, shown below.
- -Sliding window: count the requests in the last 60 seconds measured back from now, rather than from the clock minute. It removes the boundary flaw, at the cost of remembering more.
- -Token bucket: the jar above. It allows short bursts up to the bucket size while holding the average to the refill rate. This is the most widely used choice.
- -Leaky bucket: requests join a queue that drains at a constant rate, like water leaking from a bucket with a hole. The output is perfectly smooth, which suits protecting a backend that cannot handle bursts, but bursts are delayed or dropped rather than allowed.
Tracing a Burst
First, the boundary flaw. Say the limit is 100 requests per minute with fixed windows that reset on the minute. A client sends 100 requests at 12:00:59 and another 100 at 12:01:00. Each window sees exactly 100, so all 200 are accepted, yet 200 requests arrived within about a second, twice the intended rate. A sliding window looks back 60 seconds from each request, sees the first 100 still counting, and rejects the second batch.
Now the token bucket. Say it holds at most 10 tokens and refills 2 per second. A client that has been idle sends 15 requests at once. The bucket is full, so the first 10 are accepted and the other 5 are rejected. One second later 2 tokens have returned, so 2 more requests can pass. The client got its burst, but its average can never exceed 2 per second.
Choosing Who Gets Counted
- -Per user or per API key: the fairest choice when callers are logged in.
- -Per IP address: all you have for anonymous traffic, but many people can share one address (an office or a mobile carrier), so set it generously.
- -Per endpoint: expensive or sensitive operations need tighter limits, for example login attempts, to slow down password guessing.
- -Tiered: free and paid plans get different limits, which is how most public APIs work.
Making It Work Across Many Servers
If each of five application servers keeps its own counter, a limit of 100 per minute quietly becomes 500, because the client's requests are spread across them. The counters need to live in one shared place that every server consults. Redis is the usual choice: it is in memory, and a single atomic increment-and-check is fast enough for this job. A rough sizing shows why one Redis can cope:
What the Client Sees
A rejected request should say so clearly, so a well-behaved client can back off. The standard response is HTTP 429 Too Many Requests, usually with a header saying when to try again:
HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0One decision remains: what if the shared counter store itself is down? Failing open (letting traffic through) keeps the product working but removes protection. Failing closed (rejecting everything) protects the backend but turns a counter outage into a full outage. Many teams fail open for ordinary reads and fail closed for sensitive operations such as login.
In the lab, the Rate Limiter is a component you place at the front of the design. The card below describes it:
Imagine a water faucet with a governor that only lets through 10 drops per second, no matter how hard you turn the handle. A rate limiter does the same for API requests. It counts how many requests a user (or IP address, or API key) has made in a time window, and once they hit the limit (say, 100 requests per minute), it blocks any additional requests with a '429 Too Many Requests' error until the window resets. This protects your servers from being overwhelmed by a single abusive user, a bot scraping your site, or a DDoS attack flooding you with millions of fake requests. Without rate limiting, one bad actor can bring down your entire service for everyone.
Examples: Token Bucket algorithm in Redis, AWS WAF rate rules, Cloudflare rate limiting, Stripe's tiered rate limits, Nginx limit_req module
For a deeper side-by-side look at the algorithms and when each fits, the Wiki card below goes further:
How to throttle API requests fairly and efficiently to protect backends from overload.
A nightclub bouncer only lets in 100 people per hour. Algorithm 1 (Fixed Window): exactly 100 from 8pm-9pm, 100 from 9pm-10pm - but 99 arrive at 8:59pm and 99 at 9:01pm, so 198 rush in around 9pm. Algorithm 2 (Sliding Window): always count last 60 minutes, no such burst. Algorithm 3 (Token Bucket): a bucket fills at 100 tokens/hour, each entry costs 1 token. Early arrivals can have a brief burst if tokens accumulated overnight.
Fixed Window Counter: Divide time into fixed windows (e.g., 1 minute). Count requests per user in each window. Simple to implement with INCR key EXPIRE 60. Problem: boundary attack - a user can send 100 requests at 00:59 and 100 at 01:01 (a burst of 200 in 2 seconds).
Sliding Window Log: Store timestamps of each request for the user. On each request, evict timestamps older than the window. Count remaining. 100% accurate, no boundary burst. Problem: memory-intensive (must store all timestamps for active users).
Sliding Window Counter: Hybrid: count requests in the CURRENT window + (fraction of previous window × count in previous window). Very close to sliding window accuracy with fixed-window storage efficiency. Used by Cloudflare.
Token Bucket: Each user has a bucket that fills at N tokens/second (up to a max burst). Each request consumes 1 token. If the bucket is empty, reject. Allows legitimate burst traffic (if a user hasn't used the API for 10 minutes, they have accumulated tokens). Best for APIs with natural bursty usage patterns (user submitting a form, not polling every second).
Leaky Bucket: Requests enter a queue (the "bucket") and are processed at a fixed steady rate. Smooths out bursty traffic into a constant stream. Ideal for protecting downstream services that cannot handle bursts. The downside: requests in queue have unpredictable latency.
- -Rate limits are per-user (auth token or IP), not global.
- -Always return 429 Too Many Requests with Retry-After header.
- -Rate limit at the API Gateway/Load Balancer level to protect all services uniformly.
- -Distributed rate limiting needs shared state (Redis INCR + TTL is the standard).
- -Implement client-side exponential backoff - do not retry immediately on 429.
In one line: rate limiting is a doorman with a token jar. Choose an algorithm for the burst behavior you want (token bucket is the common default), count by the right key, keep the counters in one shared store, and answer rejected requests with a 429 and a Retry-After.
Interview Signal is part of Pro
See a real weak answer next to a real strong one for this exact topic.
Quiz is part of Pro
Test what you just read with a short quiz, and bank the XP.
Discussion0
Join the Discussion
Sign in to leave comments, reply to others, or like insights.
No comments yet. Be the first to start the thread!