Chapter 21 of 33

Rate Limiting

Imagine the results of a big university exam are announced at 10:00 AM. Within seconds, lakhs of students hit refresh again and again. A few scripts written by curious students fire hundreds of requests per second. Without any protection, the result server slows down for everyone and may crash completely.

The fix is to put a limit on how many requests each client may send in a given time. This is called rate limiting. In the previous chapter, API Gateway & Service Discovery, we saw that the gateway is a natural place to enforce such rules. In this chapter we look at how a rate limiter actually decides "allow" or "reject", the main algorithms, and how to build one that works across many servers.

Rate limiting is the practice of controlling how many requests a client (a user, an API key, an IP address or a service) can make to a system within a fixed period of time. Requests above the limit are rejected, delayed or queued.

Clients ──→ [ Rate Limiter ] ──allowed──→ API servers
                   │
                   └──rejected──→ HTTP 429 Too Many Requests

Why Do We Need Rate Limiting?

  • Protect against overload. A sudden spike (a viral post, a sale, a buggy client stuck in a retry loop) should not take down the service for everyone.

  • Stop abuse. Brute-force password guessing, OTP flooding, scraping and some kinds of denial-of-service attacks all depend on sending many requests quickly.

  • Fairness. One heavy user should not use up the capacity that a thousand normal users need.

  • Cost control. If every request calls a paid third-party API (SMS, maps, payments, an AI model), unlimited requests mean an unlimited bill.

  • Business plans. Many APIs sell tiers: free users get 100 requests per minute, paid users get 10,000.

A simple example: an OTP endpoint might allow 3 OTP requests per phone number per 10 minutes. Without that rule, an attacker could make your system send thousands of SMS messages to one victim, and you would pay for every single one.


Key Terms

Term

Meaning

Limit

Maximum number of requests allowed, e.g. 100

Window

The time period the limit applies to, e.g. 1 minute

Key / identity

What we count against: user ID, API key, IP address, phone number, or a combination

Burst

A short group of requests arriving almost together

Throttling

Slowing a client down (delaying or rejecting extra requests). Often used as another word for rate limiting

Choosing the key matters a lot. Limiting by IP address is easy but unfair: in India, many users share one public IP through mobile carrier NAT or a college Wi-Fi network, so one IP limit can block an entire hostel. Limiting by user ID or API key is fairer, but it only works after the user is identified. Real systems often combine both: a loose limit per IP for anonymous traffic and a tighter limit per user for logged-in traffic.


The Five Classic Algorithms

All rate limiters answer the same question: "Given what this client has done recently, should I allow this request?" They differ in how they remember "recently".

1. Token Bucket

Think of a bucket that holds at most C tokens. Tokens are added at a steady rate of r per second, and extra tokens spill over once the bucket is full. Every request must take one token. No token, no entry.

   refill r tokens/second
            │
            ▼
      ┌───────────┐
      │ ● ● ● ●   │   capacity C (max tokens)
      └─────┬─────┘
            │ each request takes 1 token
            ▼
   token available? ── yes → allow
                    └─ no  → reject (429)
  • Capacity C controls the largest burst allowed.

  • Refill rate r controls the long-term average rate.

So a bucket with C = 10 and r = 1 per second lets a client send 10 requests at once after being quiet, but on average no more than 1 per second. This "bursty but bounded" behaviour matches how real users behave (open an app, it fires 8 API calls together, then goes quiet), which is why the token bucket is the most widely used algorithm.

Implementation trick: we do not need a timer adding tokens every second. We store just two numbers per client, tokens and last_refill_time, and when a request arrives we add (now − last) × r tokens in one go (capped at C). This is called lazy refill.

2. Leaky Bucket

Requests are poured into a bucket (a FIFO queue) of fixed size. The bucket "leaks", that is, requests are taken out and processed, at a constant rate. If the bucket is full, new requests overflow and are dropped.

  bursty requests in
    ↓ ↓↓↓ ↓    ↓↓
  ┌───────────────┐
  │ R7 R6 R5 R4   │  queue of size B (overflow → drop)
  └───────┬───────┘
          │ processed at a fixed rate, e.g. 5 per second
          ▼
       servers

The key difference from the token bucket: output is perfectly smooth. Even if 50 requests arrive together, the servers see them one by one at the fixed rate. This is great when the downstream system cannot handle bursts at all (for example, a legacy payment system), but it adds waiting time, and a burst of old requests can delay fresh ones.

Nginx's limit_req module, for example, is documented as using the leaky bucket method, with a burst setting for the queue size. (Some textbooks describe a "leaky bucket as a meter" that rejects instead of queueing; that version behaves the same as a token bucket. In interviews, describe the queue version and mention this if asked.)

3. Fixed Window Counter

Split time into fixed windows (e.g. 10:00:00–10:00:59, 10:01:00–10:01:59) and keep one counter per client per window. Each request increases the counter; if it is already at the limit, reject. When a new window starts, the counter starts again from zero.

Limit = 5 per minute

window 10:00            window 10:01
[ ✓ ✓ ✓ ✓ ✓ ✗ ✗ ]       [ ✓ ✓ ... ]
  counter: 1 2 3 4 5 5 5   counter reset to 0

It is the simplest algorithm and needs only one integer per client. But it has a famous flaw, the boundary burst problem:

Limit 5 per minute
                10:00:59 │ 10:01:00
   ... 5 requests here → │ ← 5 requests here ...
                         │
   10 requests in about 2 seconds, yet both windows say "only 5"

A client can send up to 2 × limit requests in a short period that straddles the boundary.

4. Sliding Window Log

Store the timestamp of every accepted request for each client. When a new request arrives, delete timestamps older than one window, then count what is left. If the count is below the limit, accept and record the timestamp.

This is perfectly accurate: at any moment, the last 60 seconds contain at most the limit. The cost is memory: a limit of 1,000 per hour means storing up to 1,000 timestamps per client.

5. Sliding Window Counter

A clever middle ground. Keep only two counters: the current fixed window and the previous one. Estimate the requests in the last full window by assuming the previous window's requests were spread evenly:

estimate = previous_count × (overlap fraction of previous window)
         + current_count

Worked example: limit = 100 per minute. The previous minute had 80 requests; the current minute has had 30 so far, and we are 15 seconds into it.

The rolling 60-second window covers the last 45 s of the previous
minute and the first 15 s of the current minute.

overlap fraction = 45 / 60 = 0.75
estimate = 80 × 0.75 + 30 = 60 + 30 = 90

90 < 100  → allow the request (current_count becomes 31)

Memory is tiny (two counters), and the boundary burst problem mostly disappears. The answer is approximate because it assumes uniform traffic in the previous window, but in practice the error is small.


Seeing the Algorithms in Code

The program below implements four of the algorithms in Python. Time is passed in as a number (seconds) instead of reading the real clock, so the output is the same every time you run it. "A" means allowed and "x" means rejected.

from collections import deque


class TokenBucket:
    """Allows bursts up to `capacity`, refills at `rate` tokens per second."""

    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity          # start full
        self.last = 0.0                 # time of last refill

    def allow(self, now):
        # 1. Refill lazily based on time passed (no background timer needed)
        elapsed = now - self.last
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last = now
        # 2. Spend one token if we have it
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False


class FixedWindow:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.current_window = None
        self.count = 0

    def allow(self, now):
        w = int(now // self.window)     # which window are we in?
        if w != self.current_window:
            self.current_window, self.count = w, 0
        if self.count < self.limit:
            self.count += 1
            return True
        return False


class SlidingWindowLog:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.log = deque()              # timestamps of accepted requests

    def allow(self, now):
        while self.log and self.log[0] <= now - self.window:
            self.log.popleft()          # forget requests older than the window
        if len(self.log) < self.limit:
            self.log.append(now)
            return True
        return False


class SlidingWindowCounter:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.curr_start = 0
        self.curr = 0
        self.prev = 0

    def allow(self, now):
        start = int(now // self.window) * self.window
        if start != self.curr_start:
            # moved forward: the old "current" becomes "previous"
            self.prev = self.curr if start - self.curr_start == self.window else 0
            self.curr, self.curr_start = 0, start
        overlap = 1 - (now - start) / self.window   # fraction of prev window still inside
        estimate = self.prev * overlap + self.curr
        if estimate < self.limit:
            self.curr += 1
            return True
        return False


def run(name, limiter, times):
    result = "".join("A" if limiter.allow(t) else "x" for t in times)
    print(f"{name:<22} {result}  allowed={result.count('A')}")


if __name__ == "__main__":
    # Burst test: 8 requests at t=0.0, then 4 requests at t=2.0
    burst = [0.0] * 8 + [2.0] * 4
    print("Burst test (8 at t=0, 4 at t=2)")
    run("TokenBucket(5, 1/s)", TokenBucket(5, 1), burst)

    # Boundary test: limit 5 per 1-second window.
    # 5 requests at t=0.9 and 5 at t=1.1 -> 10 requests within 0.2 s
    edge = [0.9] * 5 + [1.1] * 5
    print("\nBoundary test (5 at t=0.9, 5 at t=1.1, limit 5/s)")
    run("FixedWindow", FixedWindow(5, 1), edge)
    run("SlidingWindowLog", SlidingWindowLog(5, 1), edge)
    run("SlidingWindowCounter", SlidingWindowCounter(5, 1), edge)

Output:

Burst test (8 at t=0, 4 at t=2)
TokenBucket(5, 1/s)    AAAAAxxxAAxx  allowed=7

Boundary test (5 at t=0.9, 5 at t=1.1, limit 5/s)
FixedWindow            AAAAAAAAAA  allowed=10
SlidingWindowLog       AAAAAxxxxx  allowed=5
SlidingWindowCounter   AAAAAAxxxx  allowed=6

Let's read the results:

  • Token bucket: the bucket starts with 5 tokens, so the first 5 requests at t = 0 pass and the next 3 fail. By t = 2, two tokens have been refilled (2 s × 1 token/s), so exactly 2 of the 4 later requests pass.

  • Fixed window: t = 0.9 is in window 0 and t = 1.1 is in window 1, so the counter resets in between and all 10 requests pass within 0.2 seconds. That is the boundary burst problem, live.

  • Sliding window log: exact. At t = 1.1, the five requests from t = 0.9 are still inside the last second, so everything else is rejected.

  • Sliding window counter: at t = 1.1 the estimate is 5 × 0.9 + 0 = 4.5, which is below 5, so one request slips in. Then 5 × 0.9 + 1 = 5.5, so the rest fail. It allowed 6 instead of 5: a small, bounded error in exchange for using only two counters.


Comparing the Algorithms

Algorithm

Memory per client

Allows bursts?

Accuracy

Typical use

Token bucket

2 numbers

Yes, up to capacity

Good

Public APIs, gateways (most common)

Leaky bucket (queue)

A queue of size B

Absorbs them, outputs smoothly

Good

Protecting a downstream that needs a steady rate

Fixed window

1 counter

Up to 2× at boundaries

Weak at edges

Simple daily or hourly quotas

Sliding window log

1 timestamp per request

No

Exact

Low limits that must be strict (login, OTP)

Sliding window counter

2 counters

Slightly

Approximate, close

High-traffic APIs needing low memory

Memory estimate for 10 million active users (rough sizes, including the key):

Token bucket:   10,000,000 × ~64 bytes            ≈ 640 MB
Sliding log:    10,000,000 × 100 timestamps × 8 B ≈ 8 GB  (limit 100/window,
                raw timestamps only; a Redis sorted set needs several times more)

640 MB fits comfortably in one Redis node; 8 GB of timestamps needs much more memory. This is why the sliding log is used only for small limits.


Where Should the Rate Limiter Live?

Client ──→ CDN / edge ──→ API Gateway ──→ Service ──→ Database
           (IP limits,    (per-user /     (per-endpoint,
            DDoS)          per-key limits)  business rules)
  • Client side: useful to be polite (an app that waits between retries), but never trust it. Anyone can modify a client.

  • Edge / CDN: blocks huge floods by IP before they even reach your data centre.

  • API gateway or middleware: the usual place for per-user and per-API-key limits, because the gateway already knows who the caller is.

  • Inside the service: for business rules such as "3 OTPs per phone number per 10 minutes" or "5 failed logins per account".


Rate Limiting Across Many Servers

Our Python code keeps counters in memory. That breaks as soon as there are several API servers behind a load balancer (see Load Balancing): if the limit is 100 per minute and there are 4 servers, each with its own counter, a client could get up to 400 through.

Option 1: A Shared Counter Store

All servers keep their counters in one fast, shared store, usually Redis. A fixed window counter in Redis looks like this:

key = "rl:user42:202611021015"      (user + current minute)

INCR key          → returns the new count, e.g. 37
if count == 1:  EXPIRE key 60   (old windows clean themselves up)
if count > 100: reject with 429

(In production, run INCR and EXPIRE together, in a small Lua script or a MULTI transaction, so a crash between the two commands can never leave a counter key with no expiry.)

Two details matter:

  • Atomicity. INCR is atomic, so two servers incrementing at the same moment never lose an update. But a "read the value, compute, write back" flow (needed for token bucket) is not atomic across servers. Two servers could both read "1 token left" and both allow a request. The standard fix is to run the whole check-and-update as a single Lua script inside Redis, which Redis executes atomically.

  • Latency. Every request now makes a network call to Redis (typically well under a millisecond inside one data centre). That is usually fine, but it is extra work on the hot path.

Option 2: Local Counters with Periodic Sync

Each server limits locally (fast, no network call) and periodically shares its counts with the others, or simply gets a share of the global limit (e.g. 4 servers × 25 = 100). This is less accurate (traffic is rarely spread evenly) but has no single point of failure. Many large systems mix both: a quick local check first, and a global check for the expensive or sensitive limits.

Fail Open or Fail Closed?

What if Redis goes down? You must choose:

  • Fail open: allow all requests while the limiter is unavailable. The service stays up, but you are unprotected for a while. Common for general API limits.

  • Fail closed: reject requests when you cannot check the limit. Safer for security-critical limits such as login attempts or OTP sending.


Telling the Client: HTTP 429 and Headers

When a request is rejected, the server should say so clearly so that well-behaved clients can back off.

  • Status code 429 Too Many Requests, defined in RFC 6585, is the standard response.

  • Retry-After (defined in the HTTP Semantics standard, RFC 9110) tells the client how long to wait, either as a number of seconds or as a date.

  • Many APIs also send informal headers such as X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset on every response. The IETF HTTPAPI working group is standardising this idea as RateLimit and RateLimit-Policy header fields; at the time of writing that is still an Internet-Draft, not a final RFC, so the exact format may change.

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0

{"error": "rate_limited", "message": "Too many requests. Try again in 30 seconds."}

On the client side, the right reaction to 429 (or 503) is exponential backoff with jitter: wait 1 s, then 2 s, then 4 s, and so on, plus a small random amount, so that thousands of clients do not all retry at the same instant and cause a fresh spike.

Note: Some servers (Nginx's limit_req, for example) return 503 Service Unavailable by default when a limit is hit. It can be configured to return 429, which is more accurate because the server is not actually down.


Worked Example: Designing a Limiter for a Public API

Requirement: free users get 100 requests per minute with short bursts allowed; paid users get 2,000 per minute. There are 20 API servers.

  1. Algorithm: token bucket, since bursts are allowed. Free plan: capacity 100, refill 100/60 ≈ 1.67 tokens per second. Paid plan: capacity 2,000, refill ≈ 33.3 per second.

  2. Key: the API key (fall back to IP for unauthenticated calls).

  3. Storage: a Redis cluster, sharded by key, holding {tokens, last_refill} per API key, updated with an atomic Lua script. Keys expire after a period of inactivity.

  4. Location: a middleware in the API gateway, so every service is protected without writing extra code.

  5. Rules config: limits are read from a config store (plan → capacity, rate), so they can change without a deploy.

  6. Response: 429 with Retry-After; log every rejection and expose a metric "requests rejected per minute" so a sudden jump in rejections can raise an alert (monitoring gets its own chapter later).

  7. Failure mode: fail open if Redis is unreachable, with an alert to the on-call engineer.


Common Mistakes

  • Limiting only by IP. Shared IPs (mobile carrier NAT, colleges, offices) cause false blocks, while attackers simply rotate IPs.

  • Read-then-write without atomicity in a shared store, which lets concurrent requests exceed the limit.

  • Per-server counters behind a load balancer, which silently multiply the limit by the number of servers.

  • Forgetting the boundary burst of the fixed window algorithm when a strict limit is required.

  • Returning 500 or a generic error instead of 429 with Retry-After, which makes clients retry immediately and makes things worse.

  • Treating rate limiting as full DDoS protection. A rate limiter still has to receive and inspect each request; very large floods must be stopped earlier, at the network edge.


Interview Questions

Q1. What is the difference between the token bucket and the leaky bucket?

The token bucket allows bursts up to its capacity and controls only the average rate; requests are processed immediately if a token is available. The leaky bucket (queue form) accepts bursts into a queue but sends them out at a constant rate, so output is smooth but requests may wait.

Q2. What is the boundary problem of the fixed window counter?

Because the counter resets at fixed points in time, a client can send the full limit at the end of one window and the full limit again at the start of the next, getting up to 2× the limit within a short interval. Sliding window algorithms fix this.

Q3. A limit is 100 per minute. The previous minute had 60 requests, and 20 seconds into the current minute there have been 70. Will the sliding window counter allow the next request?

Overlap of the previous window = 40/60 ≈ 0.667. Estimate = 60 × 0.667 + 70 = 40 + 70 = 110, which is ≥ 100, so the request is rejected.

Q4. How do you rate limit correctly across 50 API servers?

Keep the counters in a shared, fast store such as Redis, and make the check-and-update atomic (atomic INCR for counters, or a Lua script for token bucket). Alternatively split the limit among servers or use local limits with periodic sync, accepting some inaccuracy.

Q5. Which HTTP status code and header should a rate-limited response use?

429 Too Many Requests (RFC 6585), with a Retry-After header telling the client how many seconds to wait. Optionally also send remaining-quota headers.

Q6. Should a login rate limiter fail open or fail closed?

Usually fail closed, because the limiter is a security control against password guessing. A general API rate limiter is usually fail open, to keep the service available.


Summary

  • Rate limiting caps how many requests a client can make in a time window, protecting against overload, abuse and runaway cost.

  • Token bucket: bursts up to capacity, steady average rate; the most common choice.

  • Leaky bucket: queue that drains at a constant rate; smooth output.

  • Fixed window: simplest, but allows up to 2× the limit at window edges.

  • Sliding window log: exact, memory-heavy. Sliding window counter: approximate, very cheap.

  • In a distributed system, use a shared store (Redis) with atomic operations, and decide whether to fail open or closed.

  • Reject with 429 and Retry-After; clients should back off exponentially with jitter.

Token bucket for APIs, sliding windows for strict limits, Redis for sharing, and 429 to say "slow down".