Rate limiting caps how much work one caller may ask of a system in a period of time, and throttling is the wider act of slowing, queueing or rejecting work to protect the service. Interviewers probe it because it is a small algorithm with large consequences: the choice of algorithm decides whether bursts are tolerated, the choice of key decides who is protected from whom, and the implementation decides whether the limit survives running on ten servers instead of one. For a Backend or AI engineer there is an extra twist. A model endpoint is limited by GPU time and money, and one request can cost a hundred times another, so counting requests alone is not enough; the meaningful unit is generally tokens, and often concurrent in-flight requests as well.
The networking view (where the limiter sits, the four algorithms in the abstract) is on Rate Limiting in the Computer Networks section. This page takes the backend and LLM angle: the boundary-burst flaw of fixed windows, making a distributed limiter atomic, per-tenant fairness, limiting by tokens, and the 429 protocol between server and client. It connects to the LLM API gateway design, multi-tenant serving and circuit breakers.
Rate limiting is a hard cap on how many times someone can use a service in a given stretch of time, like "100 requests per minute." Once a caller hits that number, the service starts refusing further requests until enough time has passed, the same way a ticket counter stops selling once every seat is sold.
Throttling is the broader practice of deliberately slowing, delaying, or scaling back someone's usage instead of serving everything at full speed the instant it is asked for. Rate limiting (an outright cap) is one specific tool a system uses to throttle; other forms include making a request wait in line or reducing quality to keep the whole system stable.
Picture a popular brunch spot with only one host at the door. The host does not let in more customers than the kitchen and tables can actually handle; once the dining room is full, new arrivals are told to wait outside or come back in twenty minutes. Rate limiting is the fixed rule ("no more than 40 people at once"), and throttling is the host's overall job of pacing entry — sometimes seating people right away, sometimes making them wait a beat — so the kitchen never gets so slammed that every order comes out wrong.
TOKEN BUCKET bucket holds up to B tokens, refilled at R tokens/sec; a request takes a token.
allows bursts up to B, then sustains R. State: (tokens, last_refill_time).
LEAKY BUCKET requests enter a queue that drains at a fixed rate R; a full queue rejects.
output is smooth (good for protecting a fragile downstream); adds queueing delay.
FIXED WINDOW count requests per calendar window (e.g. per minute); reject above N.
State: one counter. Flaw: up to 2N pass across a window boundary.
SLIDING LOG keep a timestamp per request; count those in the last W seconds.
exact, but O(N) memory per key.
SLIDING COUNTER estimate = prev_window_count * (1 - fraction_elapsed) + current_window_count
two counters per key, close to the log; an approximation that assumes even spread.
algorithm memory/key burst behaviour precision
token bucket O(1) controlled burst (B) good
leaky bucket O(queue) none (smoothed) good, adds latency
fixed window O(1) 2x burst at the boundary poor at edges
sliding log O(N) none exact
sliding counter O(1) small error good enoughThe token bucket is the usual production choice because it has two intuitive knobs (sustained rate and burst size), constant state, and it matches how real clients behave: idle for a while, then a burst. Two parameters matter more than the algorithm name. The refill rate is the contract you sell ("5 requests per second on average"), and the bucket size is how much unevenness you forgive. A leaky bucket differs in intent: it shapes traffic into a steady stream, which suits protecting something that cannot absorb bursts, while a token bucket permits bursts and is better for user-facing APIs. Both are often described loosely, so in an interview say which behaviour you mean rather than just the name.
limit = 100 requests per 60-second window
window k window k+1
|---------------------------------|---------------------------------|
0s 59.9s 60.1s 120s
^^^^^^^^
100 requests at 59.9s + 100 requests at 60.1s
Each window sees exactly 100 -> both allowed.
But 200 requests arrived within 0.2 s: twice the intended rate.
sliding window: at 60.1 s the last 60 s already hold 100 requests -> the second batch is rejected.A fixed window is attractive because it is one counter and an expiry, for example INCR key with EXPIRE in Redis, but the counter resets at a boundary that has nothing to do with the client's behaviour. A client that sends its full allowance at the end of one window and again at the start of the next gets up to 2N through in an instant, so the downstream must be able to absorb twice the advertised rate. Sliding windows fix the flaw by measuring the trailing W seconds instead of a calendar window. The exact log costs memory proportional to the limit, which is fine for 100 requests per minute and painful for a million per hour per key; the sliding counter approximates it with two integers at the cost of a small error, which is why it is popular at scale. The Try It Yourself section runs all three on this exact scenario.
+--- gateway node A ---+
client ---> LB +--> shared counter store (e.g. Redis) --> allow / deny
+--- gateway node B ---+
Naive check-then-set is a race:
A: GET count -> 99 B: GET count -> 99
A: 99 + 1 <= 100 -> allow B: 99 + 1 <= 100 -> allow
A: SET 100 B: SET 100 -> 101 requests admitted, counter says 100
Atomic options: single INCR (returns the new value) | Lua script (read, compute, write as one unit)
| per-key single-writer routing (consistent hashing to one node)
Latency/accuracy trade-off:
strict global counter : one Redis round trip per request (~sub-ms to few ms in-region)
local approximation : each node gets a slice of the budget, syncs periodically -> cheaper, less exactWith one process, a limiter is a dictionary. With many, the state must be shared or the effective limit becomes the per-node limit times the node count, which changes as you autoscale. Redis is the usual shared store because each command, and each Lua script, executes atomically, so an increment-and-compare cannot interleave with another node's. The check itself must be one indivisible step; reading a value, deciding in application code, then writing it back is exactly the race shown above. A token bucket needs two fields (tokens and last-refill time), which is why it is normally implemented as a Lua script rather than as several commands. Time is the second trap: computing "now" on each node makes clock skew part of your limit, so take time from the store or accept the error.
At high scale the limiter becomes a dependency of every request, so its failure mode is a design decision. Fail open (allow traffic when the limiter is down) keeps the service available but removes protection exactly when load may be high; fail closed protects the backend but turns a Redis outage into a total outage. Most public APIs fail open with an in-process fallback limit. To cut the per-request hop, nodes can lease a slice of tokens from the shared store (for example 100 at a time) and spend them locally, accepting a bounded overshoot. The exact scripts depend on your Redis version and deployment (single node versus Cluster, where all keys touched by one script must live in one slot), so treat any snippet as a pattern to adapt.
Key choice decides who is protected from whom:
per IP cheap, but shared NATs punish many users; easy to evade
per API key the usual public-API unit
per tenant fairness between customers; add per-user limits inside a tenant
per endpoint expensive routes (generation) get stricter limits than cheap ones
global last line of defence for the backend itself
LLM cost is not proportional to request count (ILLUSTRATIVE, same 1 request/s):
client A: 500 tokens/request -> 30,000 tokens/min
client B: 20,000 tokens/request -> 1,200,000 tokens/min (40x the load)
a request limit alone treats A and B as equal. A tokens-per-minute (TPM) limit does not.
Problem: output length is unknown until generation ends.
1. estimate input tokens (tokenizer) + reserve max_tokens (or an expected output size)
2. admit if the bucket has that many tokens
3. after the response, refund the unused part (actual vs reserved)Fairness needs the right key and the right unit. Limiting per tenant stops one noisy customer from starving the rest, but a flat per-tenant number ignores plan tiers, so real systems attach a quota per plan and often a smaller per-user limit within it. For LLM APIs, request-per-minute (RPM) and tokens-per-minute (TPM) limits are commonly enforced together, and providers typically expose both, though the names, tiers and numbers differ by provider and change often, so read the current docs. The reservation approach above is the standard way to handle unknown output length: charging only what is known would let a request with a huge max_tokens slip through, and charging the worst case forever would waste capacity, hence reserve then refund.
A third control is concurrency: the number of in-flight requests per key. Because decode runs for seconds, by Little's Law the concurrent load is arrival rate times average duration. With an ILLUSTRATIVE 20 requests per second and an 8-second average generation, about 160 requests are in flight at once, and that number, not the request rate, is what fills GPU batch slots and KV-cache memory (see LLM Inference Fundamentals). A concurrency cap per tenant therefore protects a shared model server better than an RPM cap on its own. Beyond rejecting, the alternatives are queueing with a deadline, priority classes (interactive ahead of batch), and shedding the lowest-priority work first.
HTTP/1.1 429 Too Many Requests
Retry-After: 12 <- seconds to wait (an HTTP date is also allowed)
Content-Type: application/json
{"error": {"type": "rate_limited", "message": "tokens-per-minute limit exceeded"}}
429 = this caller is over ITS limit -> back off, slow down
503 = the service is overloaded (any caller) -> back off, maybe fail over
Client policy: wait Retry-After if present, else exponential backoff with jitter:
sleep = random(0, min(cap, base * 2^attempt)) (full jitter)
and cap total retries + total time; retry only idempotent or idempotency-keyed requestsA limiter is only useful if clients react well, and the usual failure is a retry storm: 1,000 clients are rejected together, all retry after exactly one second, and the synchronised wave is rejected again. Jittered exponential backoff spreads the retries; honouring Retry-After avoids guessing. Some services also return rate-limit headers describing the limit, remaining budget and reset time; the header names are not universal (a standard is still evolving and vendors use their own), so document yours. Retrying also multiplies load, so clients should cap attempts and, for non-idempotent calls, use an idempotency key as described in Idempotency and Exactly-Once Semantics. On the server side, reject early, at the gateway, before parsing large bodies or touching a model, so a rejection costs microseconds instead of GPU time.
# Python 3 (stdlib only): token bucket with an injected clock (deterministic)
class TokenBucket:
def __init__(self, rate, capacity, now=0.0):
self.rate, self.capacity = rate, capacity # tokens/sec, max burst
self.tokens, self.last = float(capacity), now
def allow(self, now, cost=1):
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
if self.tokens >= cost:
self.tokens -= cost
return True, 0.0
return False, (cost - self.tokens) / self.rate # seconds until enough tokens: Retry-After
tb = TokenBucket(rate=5, capacity=10) # 5 req/s sustained, burst of 10
res = [tb.allow(0.0)[0] for _ in range(15)] # 15 requests at t=0
print("burst of 15 at t=0 :", "".join("Y" if r else "N" for r in res), "-> allowed", sum(res))
ok, wait = tb.allow(0.0)
print("16th request : allowed=%s retry_after=%.1fs" % (ok, wait))
res = [tb.allow(1.0)[0] for _ in range(8)] # one second later: 5 tokens refilled
print("8 requests at t=1s :", "".join("Y" if r else "N" for r in res), "-> allowed", sum(res))
# Real output from python3:
# burst of 15 at t=0 : YYYYYYYYYYNNNNN -> allowed 10
# 16th request : allowed=False retry_after=0.2s
# 8 requests at t=1s : YYYYYNNN -> allowed 5
# Python 3: fixed window vs sliding log vs sliding counter: the boundary burst
from collections import deque
class FixedWindow:
def __init__(self, limit, window):
self.limit, self.window, self.counts = limit, window, {}
def allow(self, t):
w = int(t // self.window)
self.counts[w] = self.counts.get(w, 0) + 1
return self.counts[w] <= self.limit
class SlidingLog:
def __init__(self, limit, window):
self.limit, self.window, self.log = limit, window, deque()
def allow(self, t):
while self.log and self.log[0] <= t - self.window:
self.log.popleft()
if len(self.log) < self.limit:
self.log.append(t); return True
return False
class SlidingCounter: # weighted blend of previous and current window
def __init__(self, limit, window):
self.limit, self.window, self.counts = limit, window, {}
def allow(self, t):
w = int(t // self.window)
frac = (t % self.window) / self.window
est = self.counts.get(w - 1, 0) * (1 - frac) + self.counts.get(w, 0)
if est + 1 > self.limit: return False
self.counts[w] = self.counts.get(w, 0) + 1
return True
LIMIT, WINDOW = 100, 60.0 # 100 requests per minute
# client sends 100 requests at t=59.9s and 100 more at t=60.1s
times = [59.9] * 100 + [60.1] * 100
for name, cls in (("fixed window", FixedWindow), ("sliding log", SlidingLog), ("sliding counter", SlidingCounter)):
lim = cls(LIMIT, WINDOW)
allowed = sum(lim.allow(t) for t in times)
print("%-15s allowed %3d of 200 within 0.2 s (limit is %d per %d s)" % (name, allowed, LIMIT, WINDOW))
# Real output from python3:
# fixed window allowed 200 of 200 within 0.2 s (limit is 100 per 60 s)
# sliding log allowed 100 of 200 within 0.2 s (limit is 100 per 60 s)
# sliding counter allowed 100 of 200 within 0.2 s (limit is 100 per 60 s)
# Python 3: limiting by tokens (LLM cost) instead of request count
class TokenBudget:
"""Tokens-per-minute budget as a token bucket whose 'cost' is the request's token count."""
def __init__(self, tpm, now=0.0):
self.rate, self.capacity = tpm / 60.0, float(tpm)
self.tokens, self.last = float(tpm), now
def try_consume(self, now, cost):
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
if cost <= self.tokens:
self.tokens -= cost; return True
return False
# One request per second for 60 s. Limit: 60,000 tokens/min. A 60 requests/min limit alone would allow all 60.
def simulate(tokens_per_req):
budget, req_ok = TokenBudget(60_000), 0
for sec in range(60):
if budget.try_consume(float(sec), tokens_per_req):
req_ok += 1
return req_ok
print("60 requests in 60 s, budget 60,000 tokens/min:")
for size in (500, 1_000, 4_000, 20_000):
print(" %6d tokens/request -> %2d allowed by token budget" % (size, simulate(size)))
# Real output from python3:
# 60 requests in 60 s, budget 60,000 tokens/min:
# 500 tokens/request -> 60 allowed by token budget
# 1000 tokens/request -> 60 allowed by token budget
# 4000 tokens/request -> 29 allowed by token budget
# 20000 tokens/request -> 5 allowed by token budget
# Python 3: why the counter update must be atomic (two nodes, limit 100, counter at 99)
# The interleaving is forced so the result is deterministic.
store = {"count": 99}
LIMIT = 100
a_seen = store["count"] # node A: GET -> 99
b_seen = store["count"] # node B: GET -> 99
a_ok = a_seen + 1 <= LIMIT
b_ok = b_seen + 1 <= LIMIT
if a_ok: store["count"] = a_seen + 1 # node A: SET 100
if b_ok: store["count"] = b_seen + 1 # node B: SET 100 (lost update)
print("non-atomic: A allowed=%s B allowed=%s final count=%d (limit %d)" % (a_ok, b_ok, store["count"], LIMIT))
import threading
store = {"count": 99}
lock = threading.Lock()
def incr_and_check():
with lock: # stands in for Redis running one command or script at a time
store["count"] += 1
return store["count"] <= LIMIT
print("atomic : A allowed=%s B allowed=%s final count=%d" % (incr_and_check(), incr_and_check(), store["count"]))
# Real output from python3 (the atomic version still increments on a rejected call, so 101):
# non-atomic: A allowed=True B allowed=True final count=100 (limit 100)
# atomic : A allowed=True B allowed=False final count=101
# Redis Lua sketch of an atomic fixed-window check (NOT run here: needs a Redis server, so no output shown)
# local n = redis.call('INCR', KEYS[1])
# if n == 1 then redis.call('EXPIRE', KEYS[1], ARGV[1]) end
# if n > tonumber(ARGV[2]) then return 0 else return 1 endQ: Token bucket versus leaky bucket: what is the practical difference?
A: A token bucket lets a client spend saved-up tokens in a burst up to the bucket size and then sustains the refill rate, so it forgives uneven but average-conforming traffic. A leaky bucket drains a queue at a fixed rate, so the output is smooth but requests can wait or be dropped when the queue is full. Choose token bucket for user-facing APIs where bursts are normal, and leaky bucket (or a queue with a fixed-rate consumer) when the downstream cannot tolerate bursts, accepting added latency.
Q: What is wrong with a fixed-window counter?
A: The window resets at a calendar boundary, so a client can send the full limit just before the reset and the full limit just after it, getting up to twice the limit through in a very short time. In my simulation a limit of 100 per minute admitted 200 requests in 0.2 seconds, while sliding log and sliding counter admitted 100. The advantage is that it is one counter and trivial to implement, so it is fine when the downstream tolerates the 2x boundary spike and wrong when it does not.
Q: How do you implement a rate limiter that works across many servers?
A: Keep the state in a shared store such as Redis and make the check-and-update atomic, using INCR for a counter or a Lua script for a token bucket, because a separate read then write lets two nodes both see 99 and both admit the 100th request. The costs are a network hop per request and a new dependency, so I would decide fail-open versus fail-closed up front and consider local token leases to reduce round trips. Without shared state the effective limit is the per-node limit multiplied by the node count and changes on autoscaling.
Q: Why is limiting an LLM API by request count not enough?
A: Cost and GPU load scale with tokens, and a single request can be tiny or enormous: in a simple example at one request per second, 500-token requests and 20,000-token requests differ by 40 times in load under the same request limit. So I would enforce a tokens-per-minute budget alongside requests-per-minute, plus a cap on concurrent requests since long generations hold GPU batch slots and KV-cache memory. Because output length is unknown up front, reserve the estimated or max_tokens amount at admission and refund the unused part afterwards.
Q: What should a rejected request look like, and what should the client do?
A: Return 429 Too Many Requests with a Retry-After value computed from when enough budget will exist, and a body that says which limit was hit. The client should wait for Retry-After or use exponential backoff with full jitter, cap retries, and only retry idempotent operations or ones carrying an idempotency key. Without jitter, all rejected clients retry in lockstep and the limiter keeps rejecting the same synchronised wave.
Q: Which key do you limit on: IP, API key, user or tenant?
A: It depends on the fairness goal. IP is cheap but unfair behind shared NATs and easy to rotate; API key or tenant is the usual unit for paid APIs so one customer cannot starve others; a per-user limit inside a tenant stops one user from consuming the whole tenant quota. I would layer them, with stricter limits on expensive endpoints such as generation and a global limit protecting the backend, and allow quota tiers per plan rather than one flat number.
Follow-up: Your Redis-backed limiter goes down during a traffic spike. What happens?
A: That is the fail-open versus fail-closed decision. Failing open keeps the API up but removes protection when load is highest, so I would fall back to a conservative in-process limiter per node; failing closed protects the model backend but converts a limiter outage into a full outage. Most public APIs choose fail open with a local fallback, and I would alert on limiter errors and test the failure mode explicitly.
Follow-up: How would you rate limit streaming responses, where tokens are produced over 30 seconds?
A: Admission control happens at the start using the reserved estimate, and a concurrency limit covers the time the stream is open, since the request holds resources for its whole duration. Actual token counts are reconciled when the stream ends or is cancelled, refunding the difference. If tenants can exceed budgets mid-stream, you can truncate at max_tokens, but you should not silently cut a response the tenant has paid to start unless the contract says so.
Follow-up: Can a sliding window counter ever admit more than the limit?
A: Yes, slightly. It assumes requests in the previous window were spread evenly, so if they were actually bunched at the end, the weighted estimate under-counts the trailing window and lets a bit extra through. The error is usually small and bounded, and the trade is two integers per key instead of a log of timestamps. If you need an exact guarantee, use the sliding log or a token bucket with a burst size you can defend.
Rate limiting appears in almost every API design and is central to any LLM gateway: it sits at the edge or in the gateway so that rejected traffic costs microseconds, not GPU seconds. State the policy explicitly: keys (tenant, API key, user, endpoint), units (requests, tokens, concurrency), algorithm (token bucket for bursts), storage (Redis with atomic scripts, or local leases for scale), the failure mode, and the 429 and Retry-After contract. Do the arithmetic with stated assumptions. For example, assume 5,000 tenants on a shared model pool with 200 GPU-batch slots in total; giving each tenant a concurrency cap of 4 means a few noisy tenants cannot hold more than a small share, and a plan-based TPM limit bounds spend per tenant per minute. If the limiter does one Redis operation per request at 20,000 requests per second, that is 20,000 operations per second on the limiter store, which a single Redis instance can generally handle for simple commands but which you would still shard by key and monitor (measure it, do not assume). Tie it to autoscaling (limits keep autoscaling from chasing abusive load and running up cost), to cost optimization (per-tenant budgets), and to priority queues that shed batch work before interactive traffic.
Rate limiting trades some legitimate traffic and some complexity for protection against overload, abuse and runaway cost. Strict limits reject honest bursts and generate support tickets; generous limits fail to protect; token buckets tolerate bursts but the burst size becomes a second knob to tune; sliding windows are smoother than fixed ones at the cost of more state or an approximation; strict global counters are accurate but add a network hop and a dependency, while local approximations are cheap but can overshoot. Token and concurrency limits are more faithful for LLMs but need token estimation and reconciliation, and estimation errors mean users are sometimes rejected or under-charged. A limiter is the wrong tool when the real problem is missing capacity (use autoscaling and queues), when overload comes from inside the system (use circuit breakers and backpressure), or when abuse needs identity controls rather than throttling. Measure rejections by key and reason, since a limit nobody monitors is either silently hurting customers or silently doing nothing.