Rate Limiters

It is 10 am, and the tatkal window opens on a railway booking site. A student in a Pune hostel taps Book for a seat home for Diwali, along with lakhs of other people. So do a few hundred scripts on rented servers, each firing hundreds of requests a second. Within a minute the booking service is buried in bot traffic, the login service has sent thousands of billed OTP messages to numbers the scripts typed in, and most real passengers stare at a spinner until the seats are gone. Nothing crashed. The site served whoever asked fastest, and a rate limiter is what changes that.

A rate limiter caps how many requests a client may make in a period, such as 3 OTP requests per 10 minutes per phone number. Requests over the cap are rejected, or sometimes delayed, before they cost anything. The tatkal morning shows all four reasons to have one:

• Abuse: scripts grabbing seats, guessing OTPs or scraping seat availability.
• Fairness: one heavy client, whether a bot or a partner travel app, should not crowd out everyone else.
• Cost: every OTP message and every call to a paid third-party API is billed.
• Protection: the booking service can take only so much load, and a limit keeps it there during a rush or a retry storm.

Each reason leads to a different limit, and every limit starts with one decision: who counts as one client?

A limit is only as good as its key, the identity it counts against. Here are limits the booking site might set, each with the key that makes it work:

The numbers are illustrative; you pick yours from real traffic. A user id works for logged-in calls and an API key for partners. An IP address is the fallback for anonymous traffic, and it is blunt in both directions.

It is too coarse because many people share one address: a whole hostel or office sits behind one public IP, and mobile networks put thousands of phones behind a few. It is too fine because of IPv6: a phone or server usually controls a whole /64 block, about 18 quintillion addresses, and can use a new one for each request. Key IPv6 traffic on its /64 prefix, never on the full address.

With the key chosen, the next question is where to count. A limit can be enforced at several points between the passenger's phone and the database. Earlier is cheaper, because a rejected request does no work, but later points know more about what a request will cost.

The gateway is the usual home: it sits behind the load balancer (the load balancer chapter) and in front of every service, so one component enforces the rules for all of them. Most real systems still limit in layers: a coarse per-IP limit at the edge stops floods cheaply, a per-user limit at the gateway keeps things fair, and a per-operation limit inside the service guards expensive work such as sending OTPs.

Once the limiter has a place, it needs a rule for counting. A common default is the token bucket: think of a jar of tickets that refills slowly. Each client has a bucket that holds up to capacity tokens and refills at rate tokens a second. Every request takes one token, and a request that finds the bucket empty is rejected.

The two numbers mean different things. Capacity is the burst a client may make at once; rate is the long-run average it may sustain. With capacity 10 and a rate of 1 a second, a passenger can fire 10 requests together, then 1 a second after that.

import time

class TokenBucket:
    def __init__(self, capacity, refill_per_sec):
        self.capacity = capacity
        self.rate = refill_per_sec
        self.tokens = capacity
        self.last = time.monotonic()

    def allow(self):
        now = time.monotonic()
        # add the tokens earned since the last call, never above capacity
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False                     # the caller returns HTTP 429

No timer refills the bucket: each call adds the tokens earned since the last one. Per client you store just two numbers, the token count and a timestamp.

Here is user 42's bucket, with capacity 3 and a refill of 1 token a second, meeting a burst at 10:00.

The burst of three went straight through, the fourth request was turned away without touching the booking service, and one second later exactly one more fitted. Capacity sets the burst, rate sets the average, so tune them separately.

A token bucket lets bursts through. Sometimes you want the opposite. A leaky bucket turns any input into a steady output: requests join a queue of fixed size and leave it at a constant rate, like water dripping from a hole. A burst waits in the queue, and when the queue is full, new requests are dropped. Some texts use the name for a version that only counts and rejects; that one behaves much like a token bucket.

That makes it the right shape in front of something that needs an even rate. If the SMS provider accepts 50 messages a second, a leaky bucket in front of it sends at most 50 a second however unevenly the 10 am logins arrive. The cost is delay: a message at the back of a queue of 500 waits 10 seconds. Side by side:

The token bucket suits APIs; the leaky bucket suits feeding a fixed-rate dependency. Simpler still is a fixed window counter: count each client's requests per calendar minute in a key such as rl:42:10:05, reject once the count passes the limit, and let the key expire when the minute ends.

Sliding windows fix the boundary problem by asking about the last 60 seconds from now, not about the current calendar minute. A sliding window log stores a timestamp for every request; on each new request it drops timestamps older than 60 seconds and counts the rest. It is exact, but memory grows with the limit: 1,000 requests a minute for each of a million users is up to a billion timestamps, 8 GB before any overhead.

A sliding window counter keeps only two counters, this minute's and last minute's, and assumes last minute's requests were spread evenly. The estimate is the current count plus the previous count, weighted by how much of the previous minute still lies inside the last 60 seconds.

limit: 100 per minute          now: 10:01:15, a quarter into the minute
previous minute (10:00):  80 requests
current minute  (10:01):  30 requests so far

estimate = 30 + 80 × (1 − 0.25) = 30 + 60 = 90    → under 100, allow

Two small counters per client, and no 2× burst at the boundary.

Now send the boundary burst from the previous page to both kinds of limiter at once.

Half a second into the new minute, 59.5 of the previous minute's 60 seconds still lie inside the sliding window, so its 100 requests count as 100 × 59.5 ÷ 60 ≈ 99, and at most one more request fits. The estimate errs a little either way when traffic within a minute is uneven, but for two counters per client it is a good trade.

With five algorithms on the table, the choice comes down to memory, accuracy and how each treats bursts:

For most API limits, pick the token bucket. It allows the short bursts real apps make, such as a screen that fires five calls when it opens, and still caps the average. Use a sliding window counter for a plain "N per minute" rule without boundary bursts, and a leaky bucket when the thing you protect needs a steady rate.

Fixed windows are still fine for long quotas, such as 10,000 partner calls a day, where a burst at midnight hardly matters. The sliding log is worth its memory only when limits are small and exactness matters, like 3 OTPs in 10 minutes.

Every algorithm so far counts requests per second. Some endpoints hurt because of how long each request runs instead: a partner's export of a month of bookings that takes 30 seconds, a bulk upload, a large report. Ten such requests a second are harmless at 100 ms each and crushing at 30 seconds each. A concurrency limit caps how many requests a client may have in progress at once.

The link between the two is Little's law: requests in flight = arrival rate × time each one takes. At 10 exports a second and 30 seconds each, 300 run at once. A per-partner limit of, say, 5 exports in progress keeps any one partner from holding every export worker, whatever its request rate.

Count it with one entry per running request: add the request id with its start time when it begins, remove it when it ends, and before admitting a new one, drop entries older than the longest allowed request and count the rest. A plain counter would leak a slot every time a request crashed before finishing.

Concurrency limits protect your own services too. A cap on calls in flight to one dependency, called a bulkhead, stops a single stuck dependency, such as a slow payment gateway, from tying up every thread. It reacts the moment latency rises, while a rate limit notices only when the request count changes.

So far each limiter lived in one place. With one gateway, the bucket can live in its memory. The booking site runs 10 gateway instances behind a load balancer, though, and each sees only about a tenth of a passenger's requests, so in-memory counters would let a script make up to 10 times the limit. The count has to be shared, and there are three ways to share it:

The shared store is usually an in-memory key-value store like the one in the distributed caches chapter, with each client's counters on one shard: one round trip of under a millisecond buys an exact count. It brings its own trap, though, which the next page shows.

The trap is a race condition: two gateways read the same count at the same moment, both decide, and both write. Each step is correct on its own; the problem is the gap between reading and writing.

The fix is to make check-and-update one atomic step inside the store. For window counters, use the store's atomic increment, which returns the new value, and compare after incrementing. For a token bucket, run the whole read, refill, take and write as one script inside the store, so no other request can slip in between.

import time

def allow(user_id, limit=100):
    window = int(time.time() // 60)        # the current minute
    key = f'rl:{user_id}:{window}'
    count = store.incr(key)                # atomic: returns the new value
    if count == 1:
        store.expire(key, 120)             # tidy up after the window
    return count <= limit

Increment first, then compare, so two gateways can never both see 99. In production, set the expiry inside the same atomic script, so a crash between the two calls cannot leave a key that never expires.

Every request now costs at least one call to the store for each rule it matches: an increment for a window counter, a short script for a token bucket. Suppose the gateways see 1 M requests a second at the tatkal peak, each matching one rule. Operations a second, not memory, decide the size of the store.

One in-memory node handles roughly 100,000 simple operations a second, so plain increments need about 10 nodes of capacity. A token-bucket script reads, refills and writes, so it costs several simple operations; at, say, 30,000 to 50,000 scripts a second per node, the same traffic needs 20 to 35 nodes. Keep each about two-thirds busy and give each a replica for failover. Measure your own script before you trust either number.

Memory is small by comparison. A token bucket needs a count and a timestamp; with the key and the store's own overhead that is about 100 to 200 bytes per client, so 10 M active clients need 1 to 2 GB.

Shard by client key. Hash the key, such as user 42 or a partner's API key, to pick the node, so each check is one operation on one node. Pre-count hot keys locally. One partner sending 50,000 requests a second would put them all on one shard. For keys like that, each of 20 gateways counts locally and sends one increment of about +250 every 100 ms: 200 store calls a second instead of 50,000, for a small overshoot.

Refill on the store's clock. A gateway whose clock runs 2 seconds fast would hand out 2 seconds of extra tokens, and one running slow can compute negative time. Read the time inside the atomic script from the store itself, so every gateway uses the same clock.

The store now sits on the path of every request, so it must not become the outage. Give each store call a tight timeout of a few milliseconds, and wrap it in a circuit breaker: after repeated timeouts, stop calling the store for a few seconds, so a dead store costs one timeout every few seconds instead of one on every request. Then decide in advance what happens while it is gone:

A good middle path is a local limiter in each gateway, set to the global limit divided by the number of instances, read at run time because autoscaling changes it. It is approximate in both directions. A passenger whose long-lived connection pins them to one gateway gets only that gateway's share, so some teams set the fallback a little above the fair share and accept some overshoot. Decide fail open or fail closed per rule, before the outage, not during it.

Across several regions, one global counter would add a cross-region round trip, 30 ms or more, to every request. The usual choice is to count per region, giving each region a share of the limit or syncing counts in the background, and accept a small overshoot.

With counting and failure settled, the last piece is the rules themselves. A real API has dozens: per plan, per endpoint, per partner, plus emergency blocks for a bot network found at 10:02. Hard-coding them means a deploy for every change, so keep rules as data: a table or config file that every gateway loads and refreshes every few seconds.

- match: POST /v1/otp
  key: phone_number
  limit: 3 per 10m
  algorithm: sliding_window_log
  if_store_down: fail_closed
- match: /v1/*
  key: api_key
  algorithm: token_bucket
  limit: { free: 1 per 1s, pro: 20 per 1s }
  burst: { free: 10, pro: 100 }
  if_store_down: local_fallback
- match: GET /v1/availability
  key: client_ip
  limit: 20 per 1s
  mode: shadow          # log would-be 429s, block nothing yet

A request is checked against every rule it matches and must pass all of them.

Three habits make rules safe to change:

• Overrides are rows, not code. A partner running a sale gets 5× its limit for 24 hours, and the row expires on its own.
• Shadow mode first. Log which clients a new rule would block, check that list for real customers, then switch it to enforce.
• Treat changes like code. Validate every edit and roll it out to one gateway first: a typo that sets a limit to 0 is an outage.

A limited client should learn three things: that it was limited, when to try again, and how much room it has. The status code for the first is 429 Too Many Requests, and the Retry-After header says how long to wait, usually in seconds.

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

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

Header names for the limit details vary between APIs, and a standard set is still being worked out. Reset here means seconds until the window resets.

Use 429 when this client sent too much. When the whole service is overloaded no matter who is calling, 503 Service Unavailable with Retry-After is the honest answer, and dropping excess work that way is called load shedding. Successful responses can carry the same limit headers, so well-behaved clients slow down before they hit the wall. Limits also differ in how hard they bite:

Choose hard where a breach costs money or safety, soft where cutting a customer off costs more. Either way, a client that retries a 429 at once, in a loop, makes things worse: it should respect Retry-After, or back off exponentially with jitter, as in the message queue chapter.

A rate limiter is a building block in larger designs and a full question of its own. For "design a rate limiter", spend the 40 minutes of design time like this:

Deep-dive the atomic counter if they ask how ten gateways enforce one limit, and failure modes if they ask about a slow store or a limit that guards money, such as OTP sends.