System Design · Lesson 9 of 18
Rate Limiter
Token bucket, sliding window, Redis counters and where to place a limiter.
- Advanced
- 60 min read
- 7 objectives
Before this lessonLesson 8: URL Shortener
What you will learn
- Size a limiter: QPS, latency budget and memory per algorithm
- Implement and compare all five algorithms at window boundaries
- Choose hard, soft or elastic throttling, and police vs shape
- Design the 429 contract, RateLimit headers and rules config
- Make distributed counting atomic with Redis Lua scripts
- Handle hot keys, multi-region limits and IP vs user keys
- Pick fail-open or fail-closed per rule and observe it
Your Progress
0 of 18 lessons 0%
- Lessons0 / 18
- Completed0
- Est. time left~ 16 hours
Progress is saved in this browser. No account needed.
Tip: pressing Next marks this lesson complete automatically.
A rate limiter decides, for every incoming request, whether the caller has used up its allowance for the current period. If it has, the request is refused before it costs you anything, usually with HTTP 429 Too Many Requests. It looks like the smallest system in this course: one counter and one comparison. That is exactly why it is a favourite interview prompt. The counter has to be shared by dozens of servers, updated a million times a second, checked in well under a millisecond, and still produce the right answer when two servers update it at the same instant, when a network partition hides it, or when one customer sends 40% of all traffic.
You will put a limiter in front of almost every design that follows: the URL shortener's create endpoint, the chat send path, the notification fan-out, the crawler's politeness per domain. Learn it properly once here.
Three ideas carry the whole lesson:
- The algorithm is a product decision. "Burst of 50 then 10 a second" and "exactly 600 an hour, never more" are different promises, and each algorithm keeps a different one. You will run all five side by side and see where they disagree.
- The hard part is the shared state. A limiter that is correct on one machine becomes wrong the moment it runs on twenty. Atomicity, clock choice and where the counter lives are the real design.
- A limiter is a safety device, so its own failure behaviour matters most. What happens when Redis is down is not an edge case; it is a requirement you decide per rule.
Step 1 — Clarify the requirements
Why are we limiting at all?
Ask this first, because the answer changes the design. Each motive pulls toward a different algorithm and a different failure mode.
| Motive | Example | What it implies |
|---|---|---|
| Protect capacity | A client's retry loop sends 5,000 req/s to an endpoint sized for 800 total | Approximate is fine; must be fast; fail open |
| Fairness between tenants | One customer's nightly analytics export starves everyone's checkout calls | Per-tenant keys; priority classes; per-route limits |
| Security | Credential stuffing, OTP guessing, card testing with stolen numbers | Per-account and per-IP keys; fail closed; exact counts |
| Cost control | Every POST /otp sends an SMS that costs money; every LLM call costs tokens | Weighted cost per request; daily quotas; fail closed |
| Revenue / packaging | Free: 60/min, Pro: 1,000/min, Enterprise: custom | Tiered rules as data; overrides; accurate usage reporting |
| Smoothing spikes | A partner's batch job arrives as 10,000 calls in the first second of every hour | Shaping (queue and drain) rather than rejecting |
Functional, in scope
- Limit the number of requests a client identity (API key, user id, IP prefix, or a combination) may make to a route or group of routes in a period, e.g. 1,000 per minute with bursts of 50.
- The limit is global across the fleet: a client spread over 40 gateway nodes gets 1,000 per minute in total, not 1,000 per node.
- Multiple rules can apply to one request (per-key global, per-route, per-IP); the request must pass all of them.
- Denied requests get a
429withRetry-After; every response carries remaining-quota headers. - Rules are configurable per tier and per customer without a deploy, and a new rule can run in shadow mode (log, do not block).
Explicitly out of scope (say it)
Volumetric DDoS at the network layer (that is the CDN and scrubbing provider's job, measured in Tbps, long before your gateway sees a packet), bot detection and fingerprinting, the billing system that turns usage into invoices, and adaptive load shedding based on server health (related, and covered briefly in Step 5, but a different control loop).
Non-functional
- Latency: the check is on the critical path of every request, so p99 added latency < 1 ms in-region, p99.9 < 5 ms. A limiter that adds 20 ms is a tax on the whole company.
- Throughput: 400k API requests/s average, 1.2M/s peak, each matching 2–3 rules.
- Accuracy: within ~5% of the configured limit for capacity rules; exact for security and cost rules (an OTP limit of 5 per day must not become 7).
- Availability: the limiter must never be the reason the API is down. Its own outage degrades to a documented per-rule behaviour (fail open or fail closed).
- Memory: millions of active keys, and an attacker must not be able to make that number unbounded.
Step 2 — Back-of-the-envelope estimation
# Traffic the LIMITER sees = traffic the API sees. Every request is a check.
api_keys_active = 2_000_000 # distinct callers seen in an hour
anon_ips_active = 5_000_000 # unauthenticated callers (per-IP rules)
api_rps_avg = 400_000 # whole platform, all routes
peak_factor = 3
peak_rps = api_rps_avg * peak_factor
print(f"limiter decisions: {api_rps_avg:,}/s avg, {peak_rps:,}/s peak")
# Each request usually matches 2-3 rules (per-key global, per-route, per-IP)
rules_per_request = 2.5
redis_ops = peak_rps * rules_per_request
print(f"counter operations at peak: {redis_ops:,.0f}/s")
# A Redis shard running a short Lua script sustains roughly 80-100k ops/s
ops_per_shard = 80_000
headroom = 0.5 # never plan a shard above 50% busy
shards = redis_ops / (ops_per_shard * headroom)
print(f"Redis primaries needed: {shards:.0f} (plus one replica each)")
# Latency budget: the check sits on EVERY request's critical path
network_rtt_ms, script_ms = 0.3, 0.05
print(f"added latency per check: ~{network_rtt_ms + script_ms:.2f} ms same-AZ")
print(f"same check cross-region (70 ms RTT): ~{70 + script_ms:.0f} ms <- why limits stay local")limiter decisions: 400,000/s avg, 1,200,000/s peak counter operations at peak: 3,000,000/s Redis primaries needed: 75 (plus one replica each) added latency per check: ~0.35 ms same-AZ same check cross-region (70 ms RTT): ~70 ms <- why limits stay local
What the numbers decide
- 3M counter operations per second is far beyond one Redis node (roughly 100k simple ops/s per core-bound shard). The counter store is sharded by key from day one. Sharding by key is natural: no request ever needs two clients' counters.
- ~0.35 ms per check in the same availability zone fits the budget; 70 ms across regions does not. So each region has its own counters, and "global" limits across regions must be approximate (Step 11). Anyone who draws one central Redis for a multi-region API has just added 70 ms to every request in the other regions.
- Every request pays this cost, including the ones you are about to deny. Once a client is over its limit, repeatedly asking Redis to confirm it is waste. A short-lived local deny cache (Step 11) removes most of that traffic exactly when an abuser is hammering.
Step 3 — The five algorithms, runnable
All five below answer the same question, allow(now) -> bool. They differ in what they remember and therefore what promise they keep. The clock is passed in rather than read inside, which makes them deterministic to test and lets the distributed version use the store's clock instead of each server's.
from collections import deque
# Every limiter takes `now` as an argument. Injecting the clock is what makes
# them deterministic, testable, and (later) able to use Redis TIME instead.
class FixedWindow:
"""One counter per (key, window). Resets hard on the boundary."""
def __init__(self, limit, window):
self.limit, self.window = limit, window
self.win_id, self.count = None, 0
def allow(self, now):
wid = int(now // self.window)
if wid != self.win_id: # new window: forget everything
self.win_id, self.count = wid, 0
if self.count < self.limit:
self.count += 1
return True
return False
class SlidingLog:
"""Exact: remember the timestamp of every accepted request."""
def __init__(self, limit, window):
self.limit, self.window, self.log = limit, window, deque()
def allow(self, now):
while self.log and self.log[0] <= now - self.window:
self.log.popleft() # evict anything older than the window
if len(self.log) < self.limit:
self.log.append(now)
return True
return False
class SlidingCounter:
"""Two counters; weight the previous window by how much still overlaps."""
def __init__(self, limit, window):
self.limit, self.window = limit, window
self.cur_id, self.cur, self.prev = None, 0, 0
def allow(self, now):
wid = int(now // self.window)
if wid != self.cur_id:
# if we skipped a whole window, the previous one is empty
self.prev = self.cur if self.cur_id == wid - 1 else 0
self.cur_id, self.cur = wid, 0
elapsed = (now % self.window) / self.window
estimate = self.prev * (1 - elapsed) + self.cur
if estimate < self.limit:
self.cur += 1
return True
return False
class TokenBucket:
"""Refill `rate` tokens/s up to `capacity`. Burst = capacity, average = rate."""
def __init__(self, rate, capacity):
self.rate, self.capacity = rate, capacity
self.tokens, self.last = float(capacity), None
def allow(self, now, cost=1):
if self.last is not None:
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
if self.tokens >= cost:
self.tokens -= cost
return True
return False
class LeakyBucket:
"""Queue of size `capacity` drained at `rate`/s. Output is perfectly smooth.
Implemented as a meter: `level` is the queue depth; each request adds 1."""
def __init__(self, rate, capacity):
self.rate, self.capacity = rate, capacity
self.level, self.last = 0.0, None
def allow(self, now):
if self.last is not None:
self.level = max(0.0, self.level - (now - self.last) * self.rate)
self.last = now
if self.level + 1 <= self.capacity:
self.level += 1
# the request is admitted but must WAIT until the queue ahead drains
self.delay = (self.level - 1) / self.rate
return True
return False
# Smoke test: 12 requests at the same instant, "10 per 10 s" style limits
for name, lim in [("fixed window", FixedWindow(10, 10)),
("sliding log", SlidingLog(10, 10)),
("sliding counter",SlidingCounter(10, 10)),
("token bucket", TokenBucket(rate=1, capacity=10)),
("leaky bucket", LeakyBucket(rate=1, capacity=10))]:
got = [lim.allow(5.0) for _ in range(12)]
print(f"{name:16} allowed {sum(got):2} of 12")
lb = LeakyBucket(rate=2, capacity=4)
print("leaky waits (s):", [lb.delay for _ in range(4) if lb.allow(0.0)])fixed window allowed 10 of 12 sliding log allowed 10 of 12 sliding counter allowed 10 of 12 token bucket allowed 10 of 12 leaky bucket allowed 10 of 12 leaky waits (s): [0.0, 0.5, 1.0, 1.5]
How each one works, and what it costs you
- Fixed window counter. Time is cut into aligned blocks (12:00:00–12:00:59, 12:01:00–12:01:59...). Keep one integer per key per block; increment; compare. In Redis this is one
INCRon a key that contains the window id, with a TTL. Cheapest possible, easy to explain to customers ("resets on the minute"). The flaw is the boundary: all of one window's allowance at 12:00:59 plus all of the next at 12:01:00 is twice the limit within one second. - Sliding window log. Remember the timestamp of every accepted request; on each call, drop timestamps older than
now − windowand count what is left. Exact: at no moment can any window of that length contain more than the limit. The price is memory proportional to the limit (a 10,000-per-hour key stores up to 10,000 timestamps) and O(log n) work per call in a sorted set. - Sliding window counter. Keep the fixed-window counts for the current and previous window, and estimate the rolling count as
prev × (fraction of prev still inside the window) + current. Two integers, nearly exact. It assumes requests in the previous window were spread evenly, which is where its small error comes from. Measured on real traffic it is typically within a few percent of the true sliding count, which is why it is the common production default for "N per period" rules. - Token bucket. A bucket holds up to capacity tokens and refills continuously at rate per second; each request spends one (or cost) tokens. Two numbers per key: the token count and the last refill time. It encodes two promises at once: average rate (refill) and maximum burst (capacity). That is what API customers actually want, which is why it is the default at most API platforms.
- Leaky bucket. Requests join a queue of fixed size that drains at a constant rate; a full queue rejects. The admission decision is mathematically the same as a token bucket with the same rate and size (the "meter" form above tracks the queue depth rather than the free space). The difference is what happens to admitted requests: a token bucket lets a burst through immediately; a leaky bucket releases it at the drain rate, so the downstream sees a perfectly flat line. Use it in front of something that cannot absorb bursts at all: a legacy payment processor, a third-party API with its own strict limit, an SMS aggregator. The last line of output shows the cost: requests wait in line.
Watch them disagree at a window boundary
The smoke test above is useless for comparison: everyone allows 10 of 12. The differences only show up in time. Same policy for all five, "10 requests per 60 seconds"; a client stays idle, then fires four bursts of 10.
# Policy for everyone: "10 requests per 60 seconds".
# A client stays idle, then fires bursts of 10 at t=59, t=60, t=90 and t=120.
bursts = [59.0, 60.0, 90.0, 120.0]
traffic = [t for t in bursts for _ in range(10)]
def worst_60s(accepted):
"""Largest number of accepted requests in ANY 60-second span."""
return max(sum(1 for x in accepted if s <= x < s + 60) for s in accepted)
limiters = {
"fixed window": FixedWindow(10, 60),
"sliding log": SlidingLog(10, 60),
"sliding counter": SlidingCounter(10, 60),
"token bucket": TokenBucket(rate=10/60, capacity=10),
"leaky bucket": LeakyBucket(rate=10/60, capacity=10),
}
print(f"{'algorithm':16} {'t=59':>5} {'t=60':>5} {'t=90':>5} {'t=120':>5} worst 60s")
for name, lim in limiters.items():
accepted, per_burst = [], []
for b in bursts:
ok = [b for _ in range(10) if lim.allow(b)]
accepted += ok
per_burst.append(len(ok))
cells = " ".join(f"{n:>5}" for n in per_burst)
print(f"{name:16} {cells} {worst_60s(accepted):>6}")
# Same admissions for token and leaky bucket -- the difference is WHEN they run.
lb, waits = LeakyBucket(rate=10/60, capacity=10), []
for _ in range(10):
lb.allow(59.0); waits.append(lb.delay)
print(f"leaky bucket: burst at t=59 executes over {waits[-1]:.0f}s, one every {waits[1]:.0f}s")algorithm t=59 t=60 t=90 t=120 worst 60s fixed window 10 10 0 10 20 sliding log 10 0 0 10 10 sliding counter 10 0 5 5 15 token bucket 10 0 5 5 15 leaky bucket 10 0 5 5 15 leaky bucket: burst at t=59 executes over 54s, one every 6s
Reading the table
- Fixed window let 20 through in one second (t=59 and t=60 are in different minutes). This is the answer to the classic question "what is wrong with a fixed window?" and the reason it is a poor choice for security rules. It then refused everything at t=90, even though the client had been quiet for 30 seconds, because the t=60 burst used the whole second window.
- Sliding log is the only one whose worst 60-second span equals the limit, 10. It refused t=60 and t=90 (the t=59 requests were still inside the window) and allowed t=120 only because the 59-second entries had just aged out.
- Sliding counter, token bucket and leaky bucket all allowed 15 in the worst span but for different reasons. The counter's estimate at t=90 was
10 × 0.5 + 0 = 5, so it let 5 more in. The token bucket had refilled30 s × 10/60 = 5tokens. These are features: they give credit for idle time, which real clients expect. - A token bucket's true worst case is
capacity + rate × Tin any span of length T: a full bucket spent at once, plus everything that refills during the span. With capacity 10 and 10/min that is 20 per minute in the worst case, the same as the fixed window's worst case, but spread differently. If you need "never more than N in any T", pick the sliding log or set capacity small. Candidates who claim a token bucket is "exact" have not done this sum.
The naive in-memory version, and its two bugs
The first design most people sketch is a hash map from user id to {count, window_start}: on each request, if the window has expired reset the count to 1, otherwise increment and compare. That is the fixed window above, and it has two problems worth naming out loud. First, the boundary burst you just measured. Second, read-then-write is not atomic: with two threads or two servers, both read count = 2, both decide there is room for one more, and both write 3. On one machine a per-key lock fixes it; across machines it needs an atomic operation in the shared store. Step 10 demonstrates the race and fixes it.
Choosing, in one table
| Algorithm | State per key | Accuracy | Bursts | Use it for |
|---|---|---|---|---|
| Fixed window | 1 integer | Up to 2x at boundaries | Allows edge bursts | Daily/monthly quotas, "5 SMS per day", billing counters |
| Sliding log | 1 timestamp per accepted request | Exact | None beyond limit | Low limits that must be exact: login, OTP, password reset |
| Sliding window counter | 2 integers | Within a few % | Smoothed | General "N per minute/hour" per-key rules |
| Token bucket | Float + timestamp | Exact to its own definition | Explicit, configurable | Public API limits (average + burst), per-tenant fairness |
| Leaky bucket | Level + timestamp (+ a queue) | Exact output rate | Absorbed by queueing | Protecting a fragile downstream; outbound calls to a strict third party |
Step 4 — Memory, per algorithm
The algorithm choice is also a memory choice, and the difference is two orders of magnitude. Size it for the worst case: an abuser sits exactly at the limit, and those are the keys that matter.
# Memory per tracked key, for a limit of 600 requests / hour, in Redis.
# Assumptions (stated, so the interviewer can argue with them):
KEY_NAME = 28 # "rl:{api_key_7f3a...}:route3" as bytes
KEY_OVH = 56 # Redis per-key cost: dict entry + object header + TTL entry
INT_VAL = 8 # a counter or timestamp stored as a native integer
ZSET_ENTRY = 64 # sorted-set member: 8B score + ~16B unique member + skiplist ptrs
HASH_FIELD = 16 # small-hash (listpack) field+value, packed
LIMIT = 600 # requests allowed per hour
active_keys = 2_000_000
per_key = {
# one INCR counter per (key, current window)
"fixed window": KEY_NAME + KEY_OVH + INT_VAL,
# one timestamp per ACCEPTED request, up to LIMIT of them
"sliding log": KEY_NAME + KEY_OVH + ZSET_ENTRY * LIMIT,
# two windows (current + previous) -> two counters
"sliding counter (2 win)": 2 * (KEY_NAME + KEY_OVH + INT_VAL),
# 60 one-minute buckets in a hash, summed on each check
"sliding counter (60 bk)": KEY_NAME + KEY_OVH + HASH_FIELD * 60,
# hash {tokens, last_refill}
"token bucket": KEY_NAME + KEY_OVH + 2 * HASH_FIELD,
# hash {level, last_leak}; the queue itself lives in the proxy, not Redis
"leaky bucket (meter)": KEY_NAME + KEY_OVH + 2 * HASH_FIELD,
}
print(f"{'algorithm':24} {'per key':>9} {'2M keys':>9}")
for name, b in per_key.items():
total = b * active_keys
unit = f"{total/1e9:.1f} GB" if total >= 1e9 else f"{total/1e6:.0f} MB"
print(f"{name:24} {b:>7,} B {unit:>9}")
log, bucket = per_key["sliding log"], per_key["token bucket"]
print(f"sliding log costs {log / bucket:,.0f}x a token bucket for the same key")algorithm per key 2M keys fixed window 92 B 184 MB sliding log 38,484 B 77.0 GB sliding counter (2 win) 184 B 368 MB sliding counter (60 bk) 1,044 B 2.1 GB token bucket 116 B 232 MB leaky bucket (meter) 116 B 232 MB sliding log costs 332x a token bucket for the same key
- The sliding log does not fit for a 600-per-hour rule on 2M keys: 77 GB of RAM to protect an API. Use it only where limits are small (10 logins per hour costs ~700 bytes per key) or the key population is small.
- The 60-bucket variant of the sliding counter (one sub-counter per minute of an hour, summed on each call) is more accurate than the two-window estimate and still ~37x cheaper than the log. It is the middle option when "per hour" limits need better precision, and it lets you enforce a per-minute sub-limit from the same data.
- Everything else is a few hundred MB, which fits comfortably on the 75 shards Step 2 already demanded for throughput. For this system throughput, not memory, sets the shard count.
- Always set a TTL. Without one, every key ever seen stays forever; a scan of the IPv6 space (Step 12) will fill any amount of RAM.
Step 5 — Throttling behaviour: hard, soft, elastic, and shaping
Separate two questions: where is the line, and what happens when a request crosses it.
- Hard throttling. The limit is a wall. Right for security and cost rules: the sixth OTP attempt is refused even if the servers are idle.
- Soft throttling. A published tolerance above the limit, say 10%. It absorbs the counting error of a distributed limiter and small client bursts without generating support tickets, and it lets you advertise a round number while enforcing slightly above it.
- Elastic (dynamic) throttling. A tenant may exceed its limit when the cluster has spare capacity, up to a ceiling. The signal comes from the backend (CPU, queue depth, p99), so this couples the limiter to health metrics and is how you avoid rejecting paying traffic at 3 a.m. when the fleet is idle.
def decide(used, limit, mode, soft_pct=0.10, spare_capacity=0.0, max_elastic=2.0):
"""used = requests already accepted this window. Returns (allowed, reason)."""
if used < limit:
return True, "within limit"
if mode == "hard":
return False, "hard cap"
if mode == "soft":
# a fixed, published tolerance above the limit
return (used < limit * (1 + soft_pct)), f"soft +{soft_pct:.0%}"
if mode == "elastic":
# borrow unused cluster capacity, bounded so one tenant cannot take it all
ceiling = limit * min(max_elastic, 1 + spare_capacity)
return used < ceiling, f"elastic ceiling {ceiling:.0f}"
limit = 100
for used in (99, 105, 115, 160):
row = [f"used={used:3}"]
for mode, kw in (("hard", {}), ("soft", {}),
("elastic", {"spare_capacity": 0.6})): # cluster 40% busy
ok, why = decide(used, limit, mode, **kw)
row.append(f"{mode}:{'allow' if ok else 'DENY'}")
print(" ".join(row))
print("elastic under load:", decide(115, limit, "elastic", spare_capacity=0.05))used= 99 hard:allow soft:allow elastic:allow used=105 hard:DENY soft:allow elastic:allow used=115 hard:DENY soft:DENY elastic:allow used=160 hard:DENY soft:DENY elastic:DENY elastic under load: (False, 'elastic ceiling 105')
Notice the last line: the same request that was allowed while the cluster was 40% busy is refused when it is 95% busy. Elastic limits must be bounded (max_elastic) or the tenant that borrows most becomes the one you cannot serve when the spare capacity disappears, and they must not be the only protection: health signals lag load by seconds, which is exactly when an overload builds.
Policing versus shaping
When a request is over the line you can reject it (policing: 429 now, cheap, the client decides when to retry) or delay it (shaping: hold it in a queue and run it later, the leaky bucket's model). Shape when the caller cannot handle rejection well, typically your own internal jobs or outbound calls to a partner with a strict limit. Police at the public edge: queuing untrusted traffic means holding sockets and memory for the very clients who are misbehaving, and a queue in front of an overloaded service only makes each request slower before it fails. A useful hybrid is to queue for at most a short time (say 200 ms) and reject beyond that.
Step 6 — The API contract: status codes and headers
A limiter has three audiences: the client being limited, the gateway asking for decisions, and the operators changing rules. Each gets its own interface.
## 1. What the CLIENT sees (public contract, on every response)
HTTP/1.1 200 OK
RateLimit-Policy: "per-key";q=1000;w=60, "burst";q=50;w=1
RateLimit: "per-key";r=412;t=23
X-RateLimit-Limit: 1000 # legacy trio -- still what most SDKs parse
X-RateLimit-Remaining: 412
X-RateLimit-Reset: 23 # seconds (say so in docs: some APIs use epoch!)
HTTP/1.1 429 Too Many Requests
Retry-After: 7 # seconds; the one header every client honours
RateLimit: "per-key";r=0;t=7
Content-Type: application/problem+json
{
"type": "https://api.example.com/errors/rate-limited",
"title": "Too many requests",
"status": 429,
"detail": "Limit of 1000 requests per 60s for this API key exceeded.",
"policy": "per-key", # WHICH rule tripped -- saves a support ticket
"retry_after_s": 7,
"upgrade_url": "https://example.com/pricing" # only for quota-type limits
}
# Status codes -- pick the one that tells the client what to do next:
# 429 YOU are over YOUR limit. Client action: back off, retry later.
# 503 WE are overloaded (load shedding). Client action: retry with jitter.
# 403 You are blocked (abuse, ban list). Client action: stop; do not retry.
# 402/403 + code QUOTA_EXHAUSTED monthly plan quota. Retrying in 7s is pointless.
## 2. What the GATEWAY calls (internal decision API, gRPC or in-process)
ShouldRateLimit(
domain = "public-api",
descriptors = [ # one request can match several rules
{ api_key: "k_7f3a", route: "POST /v1/messages" },
{ api_key: "k_7f3a" },
{ ip_prefix: "203.0.113.7" },
],
hits = 1 # cost; an expensive call may cost 10
) -> {
overall: OK | OVER_LIMIT,
statuses: [ { policy, limit, remaining, reset_s } ... ], # one per descriptor
}
# The request is denied if ANY descriptor is over. Headers report the tightest.
## 3. What OPERATORS call (rules admin API)
PUT /admin/v1/limits/{rule_id} { match, algorithm, limit, window_s, burst,
mode: enforce|shadow, fail: open|closed }
-> 200 { version: 88 } # versioned; gateways pull or get pushed v88
GET /admin/v1/limits?tenant=acme -> effective rules after tier + overrides
POST /admin/v1/limits/overrides { api_key, multiplier: 5, expires_at }
# time-boxed boost for a customer's launch day -- always with an expiryThe headers are computed from the limiter's state, so they are accurate only if the algorithm can report "remaining" and "time until reset". Here is the computation for a token bucket, reusing the class from Step 3:
import math
def headers_for(bucket, now, policy_name, window_s):
"""Turn token-bucket state into response headers. Called on EVERY response,
allowed or not, so well-behaved clients can pace themselves."""
remaining = math.floor(bucket.tokens)
# seconds until at least one token exists again
retry = 0 if bucket.tokens >= 1 else math.ceil((1 - bucket.tokens) / bucket.rate)
# seconds until the bucket is completely full (the "reset" in token terms)
reset = math.ceil((bucket.capacity - bucket.tokens) / bucket.rate)
h = {
"RateLimit-Policy": f'"{policy_name}";q={bucket.capacity};w={window_s}',
"RateLimit": f'"{policy_name}";r={remaining};t={reset}',
# legacy names many clients still read:
"X-RateLimit-Limit": str(bucket.capacity),
"X-RateLimit-Remaining": str(remaining),
}
if retry:
h["Retry-After"] = str(retry)
return h
b = TokenBucket(rate=2, capacity=20) # 20 burst, 2/s sustained (120/min)
for _ in range(20):
b.allow(100.0) # client drains the bucket at t=100
print("allowed?", b.allow(100.2)) # 0.4 tokens refilled -- not enough
for k, v in headers_for(b, 100.2, "per-key", 10).items():
print(f"{k}: {v}")allowed? False RateLimit-Policy: "per-key";q=20;w=10 RateLimit: "per-key";r=0;t=10 X-RateLimit-Limit: 20 X-RateLimit-Remaining: 0 Retry-After: 1
Contract decisions worth defending
- Send the quota headers on every response, not just the 429. Well-behaved clients (and your own SDK) pace themselves when they can see
remainingfalling, and you never see those requests as denials. Retry-Afterin seconds, and honest. For a token bucket it is "time until one token exists", which is often 1 s, not "time until the window resets". A falsely long value makes clients sit idle; a falsely short one triggers a retry storm.- The body names the policy that tripped. "You hit
expensive-search, not your global limit" turns a support ticket into a self-service fix. - 429 versus 503 versus 403 is not pedantry. Client libraries retry 429 and 503 with backoff and stop on 403. Returning 503 for a per-client limit makes every SDK retry immediately, which multiplies the load you were trying to shed.
- The
RateLimit/RateLimit-Policyfields come from the IETF httpapi working group's standardisation effort; theX-RateLimit-*trio is the older de-facto convention. Emit both during a migration, and document whether "reset" means seconds-from-now or a Unix timestamp, because public APIs disagree.
Step 7 — Rules configuration
The rules are the part of the system that changes weekly, so they are data, not code. A realistic rules file for a public API:
# rules.yaml -- versioned in git, validated in CI, pushed to every gateway.
domain: public-api
defaults:
fail_mode: open # a limiter outage must not become an API outage
key_ttl_slack: 2x # counters expire at 2 x window
tiers: # the revenue model, as data
free: { rate_per_min: 60, burst: 20, monthly_quota: 10_000 }
pro: { rate_per_min: 1_000, burst: 100, monthly_quota: 5_000_000 }
enterprise: { rate_per_min: 10_000, burst: 1000, monthly_quota: null }
rules:
- id: per-key-global # every authenticated call
match: { key: api_key }
algorithm: token_bucket
limit_from_tier: rate_per_min
burst_from_tier: burst
- id: expensive-search # an endpoint that costs 20x a normal call
match: { key: api_key, route: "GET /v1/search" }
algorithm: token_bucket
limit: 30/min
cost: 1 # or charge the global bucket cost: 20
- id: login-per-ip
match: { key: ip_prefix, route: "POST /v1/login" }
algorithm: sliding_window_counter
limit: 20/10min
fail_mode: closed # credential stuffing does not get a free pass
- id: login-per-account
match: { key: username_hash, route: "POST /v1/login" }
algorithm: sliding_window_counter
limit: 10/hour
fail_mode: closed
- id: sms-send # every call costs real money
match: { key: user_id, route: "POST /v1/otp" }
algorithm: fixed_window # simple, auditable, "5 per day" is what product said
limit: 5/day
fail_mode: closed
- id: anonymous-per-ip
match: { key: ip_prefix, authenticated: false }
algorithm: token_bucket
limit: 120/min
burst: 30
- id: new-rule-under-test
match: { key: api_key, route: "POST /v1/export" }
limit: 10/hour
mode: shadow # evaluate + log "would have denied", never block
# Precedence: ALL matching rules are evaluated; the request must pass every one.
# Overrides (per-customer multipliers) apply on top and always carry an expiry.- Descriptors, not endpoints, are the unit. A rule matches a combination of attributes (key, route, IP prefix, authenticated or not). This is the model Envoy's global rate limit service uses, and it lets one mechanism cover per-key, per-route and per-IP limits.
- Tiers are the revenue model expressed as data. Pro customers get a bigger bucket, not a different algorithm. Changing a plan is a config change that takes effect in seconds.
- Every rule carries its own fail mode. The same outage should fail open for reads and closed for OTPs; a global switch cannot express that.
- Shadow mode for every new rule. Run it for a week logging "would have denied", look at who it would have hit, then enforce. Turning on an untested limit is how you rate-limit your largest customer on a Monday morning.
- Distribution: the rules service pushes versioned snapshots; each gateway keeps the last good version in memory and on disk, so a rules-service outage changes nothing. A gateway never fetches rules on the request path.
Step 8 — High-level design: where the limiter lives
coarse per-IP shield] EDGE --> GW[API gateway fleet
auth + limiter filter
local deny cache] GW -->|pipelined EVALSHA| RC[(Redis cluster
counters sharded by key)] CFG[Rules config service] -.->|versioned push| GW GW -->|allowed| SVC[Backend services] GW -->|429| C SVC --> SC[Sidecar limiter
service-to-service] SC --> DEP[Fragile dependency
leaky bucket] GW --> OBS[Metrics + sampled
decision log]
Three layers of limiting, each doing what it is best placed to do: the edge absorbs floods by IP, the gateway enforces identity-aware product limits against shared counters, and sidecars protect individual dependencies from their own callers.
The placement options, compared
| Where | Knows | Strength | Weakness |
|---|---|---|---|
| CDN / WAF edge | IP, path, headers | Absorbs floods before they reach you; no infrastructure to run | Does not know API keys, tiers or cost; coarse |
| API gateway (filter or external service) | Authenticated identity, route, tier | One policy for all services; denies before any app CPU is spent | A shared dependency on the hot path; needs a counter store |
| Sidecar / service mesh | Calling service, destination | Protects each service from internal callers too; language-agnostic | Many small local limits; global accuracy needs the same shared store |
| In-app library | Everything, including business context ("this user's 3rd transfer today") | Richest rules; no extra hop | Every service re-implements it; easy to forget one endpoint |
The strong answer is layered: coarse per-IP at the edge, product limits at the gateway, per-dependency protection in sidecars, and business rules ("three failed card attempts per day") in the application that understands them. The common wrong answer is a counter in each app server's memory: with 40 nodes behind a round-robin load balancer, a "100 per minute" limit silently becomes 4,000 per minute, and it changes every time the fleet autoscales.
What each component owns
- Edge / WAF: volumetric protection and blunt per-IP caps (e.g. 3,000 req/min per IP). Deliberately generous so it never touches legitimate traffic.
- Gateway limiter filter: resolves identity, matches descriptors against cached rules, checks the local deny cache, calls the counter store, writes headers, returns 429. Stateless apart from caches.
- Counter store (Redis Cluster): holds every counter, executes the algorithm atomically in a script, expires idle keys. Treated as a cache: losing it loses some counts, never data that matters.
- Rules service: validates, versions and distributes rules; serves the admin API; owns tiers and overrides.
- Sidecars: local token buckets and concurrency limits in front of specific dependencies.
- Observability pipeline: metrics per rule and decision, plus a sampled log of denials for support and abuse teams.
Step 9 — One request, end to end
The limiter adds one pipelined round trip to an allowed request and zero round trips to a repeat offender. The service never sees denied traffic.
The order of operations, and why
- Authenticate before limiting by key, but limit by IP before authenticating. Checking a key is itself work (a signature verification or a cache lookup); an attacker sending garbage keys at 50k/s must be stopped by the IP rule first.
- Match rules from memory. The rules are already on the gateway; the only network call on this path is to the counter store.
- Check the local deny cache first. If this key was denied 300 ms ago with a 1.2 s retry, the answer has not changed. This is what keeps a hammering client from multiplying load on Redis.
- All matching rules in one pipelined round trip. Two rules, two
EVALSHAs, one network wait. Sequential calls would double the added latency. - Decide, then forward. The service receives only allowed traffic. Some designs increment after the response so failed requests do not count; that is a legitimate product choice (say it), but it lets concurrent requests all pass before any is counted, so it only suits low-stakes limits.
- Headers on the way out, from the state the script returned, not from a second lookup.
Step 10 — Distributed limiting with Redis
The race, demonstrated
Eight gateway workers handle one request each for the same key at the same moment. The limit is 5 and the count is already 3, so exactly two should pass. The scheduler below interleaves them the way real concurrency does: every worker reads before any worker writes.
# A fake Redis and 8 gateway workers, each handling one request for the same
# API key at the same moment. Limit is 5. Count starts at 3 (2 slots left).
LIMIT = 5
def read_then_write(store, key):
"""What most first drafts do: GET, compare in app code, then SET."""
count = store.get(key, 0) # step 1: every worker reads...
yield # ...the scheduler switches workers here
if count < LIMIT:
store[key] = count + 1 # step 2: ...then writes a stale value
return True
return False
def atomic_incr(store, key):
"""INCR (or a Lua script): read, compare and write are ONE server step."""
store[key] = store.get(key, 0) + 1
mine = store[key] # INCR returns the NEW value to this caller
yield
return mine <= LIMIT
def run(strategy):
store = {"rl:key42": 3}
workers = [strategy(store, "rl:key42") for _ in range(8)]
for w in workers: # everyone does their first step...
next(w)
allowed = 0
for w in workers: # ...then everyone finishes
try:
next(w)
except StopIteration as done:
allowed += done.value
return allowed, store["rl:key42"]
for s in (read_then_write, atomic_incr):
allowed, final = run(s)
print(f"{s.__name__:16} allowed {allowed} (should be 2), stored count = {final}")read_then_write allowed 8 (should be 2), stored count = 4 atomic_incr allowed 2 (should be 2), stored count = 11
The read-then-write version allowed all eight and left the counter at 4: every worker read 3, every worker wrote 4. This is not a theoretical concern; a client that opens 50 parallel connections produces exactly this pattern, and it is the easiest way to blow through a limit. The atomic version is correct because Redis executes one command at a time on a shard, so INCR hands each caller a distinct value. Note the final count of 11: the six denied attempts were counted too. Whether denials should consume quota is a product decision (it does punish hammering); if not, check and increment together in a script.
Wrong fixes candidates propose
- A distributed lock around read-modify-write. Correct but slow: at least two extra round trips per request, and every request for a hot key now queues behind a lock. The lock's own timeout creates new failure cases.
WATCH/MULTI/EXEC(optimistic transactions). Correct, but under contention (the hot key, again) most transactions abort and retry, so throughput collapses exactly when you need it.- Each server keeps its own count and "roughly" divides the limit. Fine as a deliberate approximation with a sync protocol (Step 11), wrong as the whole answer.
The right fix: the whole algorithm in one Lua script
Redis runs a Lua script atomically: no other command on that shard executes until it finishes. Putting the read, the refill arithmetic, the decision and the write in one script removes the race and needs one round trip. Keep scripts short (microseconds), since they block the shard while they run.
-- Fixed window. KEYS[1] = "rl:{k_7f3a}:fw:28391044" (window id in the key)
-- ARGV[1] = limit, ARGV[2] = window seconds
local n = redis.call('INCR', KEYS[1])
if n == 1 then
-- first hit of this window: set the TTL in the SAME atomic step.
-- Done as two round trips from the app, a crash between INCR and EXPIRE
-- leaves a counter that never expires -- that user is blocked forever.
redis.call('EXPIRE', KEYS[1], tonumber(ARGV[2]) * 2)
end
return { n <= tonumber(ARGV[1]) and 1 or 0, n }-- Sliding log. KEYS[1] = "rl:{k_7f3a}:log"
-- ARGV: [1] now_ms [2] window_ms [3] limit [4] unique request id
local now, win, limit = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', now - win) -- evict old entries
local n = redis.call('ZCARD', KEYS[1])
if n < limit then
-- the MEMBER must be unique: two requests in the same millisecond with
-- member = timestamp would collapse into one entry and undercount.
redis.call('ZADD', KEYS[1], now, ARGV[4])
redis.call('PEXPIRE', KEYS[1], win)
return { 1, limit - n - 1 }
end
return { 0, 0 } -- denied requests are NOT logged, so hammering costs no memory-- Token bucket. KEYS[1] = "rl:{k_7f3a}:tb" (hash: tokens, ts)
-- ARGV: [1] rate per second [2] capacity [3] cost
local t = redis.call('TIME') -- ONE clock: Redis's own
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000
local rate, cap, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local s = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or cap -- new key starts full
local ts = tonumber(s[2]) or now
tokens = math.min(cap, tokens + math.max(0, now - ts) * rate)
local allowed, retry_ms = 0, 0
if tokens >= cost then
tokens, allowed = tokens - cost, 1
else
retry_ms = math.ceil((cost - tokens) / rate * 1000)
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(cap / rate) * 2) -- idle keys vanish
-- Lua numbers become INTEGERS on the way back to the client, so a fractional
-- token count must be returned as a string or it is silently truncated.
return { allowed, tostring(tokens), retry_ms }# Gateway side (redis-py). Load the script once; call it by SHA afterwards.
import redis
r = redis.Redis(host="rl-redis", socket_timeout=0.005) # 5 ms, not the default!
token_bucket = r.register_script(TOKEN_BUCKET_LUA) # EVALSHA, and re-loads
# the script on NOSCRIPT
def check(api_key: str, rate: float, cap: int, fail_open: bool, cost: int = 1):
key = f"rl:{{{api_key}}}:tb" # braces = hash tag -> one cluster slot
try:
allowed, tokens, retry_ms = token_bucket(keys=[key], args=[rate, cap, cost])
return bool(allowed), int(retry_ms)
except (redis.TimeoutError, redis.ConnectionError):
return fail_open, 0 # the decision policy lives in the rule
# Several rules for one request? Run them in ONE pipeline: one round trip, not three.Four details that separate a working deployment from a demo
- Whose clock? If each gateway passes its own
now, a server whose clock runs 2 s fast refills buckets 2 s early and one running slow sees negative elapsed time. The token bucket script readsredis.call('TIME')so every decision for a key uses the same clock. (CallingTIMEbefore writing is safe on Redis 5+ because scripts replicate their effects, not the script text.) Passing time in is acceptable only with NTP-disciplined hosts and themath.max(0, ...)guard. - Cluster slots. A script may only touch keys in one hash slot. Wrapping the identity in braces,
rl:{k_7f3a}:tbandrl:{k_7f3a}:sw:prev, puts all of one client's keys on one shard, which also makes sliding-counter scripts that read two keys legal. - Tight timeouts. The Redis client timeout is 5 ms, not the library default of several seconds. A limiter that waits 2 s for a sick shard has turned a Redis problem into an API-wide latency incident.
- Replication lag. Always run limiter scripts on the primary. After a failover the new primary may be missing the last few hundred milliseconds of increments; clients get slightly more than their limit for one window. That is an accepted cost for capacity rules, and a reason cost-critical counters (SMS, payments) are also recorded durably by the service itself.
Step 11 — Scaling: sharding, hot keys and multiple regions
Sharding
Shard by the limit key, which Redis Cluster does with hash slots (a form of consistent partitioning: adding a node moves a fraction of slots, not everything). Nothing ever needs two keys from different clients, so there are no cross-shard operations. If different APIs have very different limits, include the route in the key (rl:{k_7f3a}:search) so heavy routes spread across shards. When the backend itself is partitioned, a second, smaller limit per partition (say, a per-shard cap on writes for one customer) stops a single tenant from overloading one database shard even while they are within their global limit.
Hot keys
One enterprise customer sending 200k req/s puts 200k script calls per second on one shard, because all their counters share one slot by design. Options, in the order you would try them:
- Local deny cache (Step 9): a denied key's traffic stops reaching Redis at all. Handles abusers, not legitimate heavy users.
- Local token leasing: each gateway takes a batch of tokens (say 100) from the global bucket in one call and spends them locally. Redis traffic for that key drops 100x; the cost is that up to
nodes × batchtokens can be in flight, so the limit is soft by that amount. - Key splitting: split one key's budget into N sub-keys on different shards (
rl:{k_7f3a#3}:tb), each with 1/N of the limit, and pick a sub-key at random. Accurate on average, slightly unfair per request. - Give the customer their own shard or a dedicated limiter cell. At enterprise scale this is normal, and it is also a sales conversation.
Local plus global: the hybrid
Every approximate design is some version of "count locally, reconcile globally". The trade-off is quantifiable: overshoot is roughly (total demand − limit) × sync interval. The simulation below serves one key from four gateway nodes with skewed traffic.
# One API key, limit 1,000 req per 1-second window, served by 4 gateway nodes.
# Demand is 1,600 req/s and skewed: node 0 gets 70% (sticky connections).
LIMIT, NODES, TICK_MS = 1000, 4, 10
share = [0.70, 0.10, 0.10, 0.10]
demand_per_tick = [1600 * s * TICK_MS / 1000 for s in share] # req per node per tick
def static_split():
"""Each node enforces LIMIT/NODES locally, never talks to anyone."""
allowed = [0.0] * NODES
for _ in range(1000 // TICK_MS):
for n in range(NODES):
allowed[n] += min(demand_per_tick[n], LIMIT / NODES - allowed[n])
return sum(allowed)
def synced(sync_ms):
"""Each node counts locally and every `sync_ms` pushes its delta to a global
counter (one INCRBY) and reads back the global total."""
global_count, known_global = 0.0, 0.0
local_delta = [0.0] * NODES
allowed = 0.0
for tick in range(1000 // TICK_MS):
for n in range(NODES):
headroom = LIMIT - known_global - local_delta[n] # a node's OWN view
take = max(0.0, min(demand_per_tick[n], headroom))
local_delta[n] += take
allowed += take
if (tick + 1) * TICK_MS % sync_ms == 0:
global_count += sum(local_delta)
local_delta = [0.0] * NODES
known_global = global_count
return allowed
print(f"static split (limit/4 each): {static_split():6.0f} allowed <- under-admits")
for ms in (10, 100, 250, 500):
a = synced(ms)
print(f"sync every {ms:3} ms: {a:6.0f} allowed overshoot {max(0, a - LIMIT):4.0f}")
print("exact (central counter): 1000 allowed")static split (limit/4 each): 730 allowed <- under-admits sync every 10 ms: 1005 allowed overshoot 5 sync every 100 ms: 1048 allowed overshoot 48 sync every 250 ms: 1120 allowed overshoot 120 sync every 500 ms: 1240 allowed overshoot 240 exact (central counter): 1000 allowed
- Static split (each node gets limit / nodes, no coordination) is the tempting answer and it is wrong in the other direction: the node receiving 70% of the traffic hits its quarter-share while the others sit idle, so the customer gets 730 of the 1,000 they pay for, and the shortfall changes whenever the load balancer rebalances.
- Batched sync converges to the limit, with an overshoot you can dial: 100 ms sync gives ~5%, which is inside the soft-throttling tolerance from Step 5 and cuts counter-store traffic from one call per request to one call per node per 100 ms.
- Multi-region: run the exact algorithm against the region's own Redis for each request, and treat cross-region limits with this batched approach, exchanging per-region counts every second or so (or give each region a share of the global budget, rebalanced from observed demand). Never put a cross-region round trip on the request path. Most APIs simply document that limits are enforced per region, which is honest and simple.
Step 12 — Who do you limit: IP, user, or both?
- By IP. Works before authentication, which makes it the only option for login, signup and anonymous traffic. It is also unfair and leaky: a university, an office NAT or a mobile carrier's CGNAT puts thousands of real users behind one IPv4 address, and an attacker with a botnet or residential proxies has thousands of IPs. IPv6 makes it worse, because one subscriber usually controls an entire /64, so limiting per full address lets a single machine appear as effectively unlimited clients while filling your counter store with keys.
- By user or API key. Accurate and fair, but only after authentication, and it opens a denial-of-service against the victim: if failed logins are limited only per account, an attacker can lock any user out by failing on purpose.
- Both, per route. Authenticated APIs limit by key (plus a generous IP cap as a backstop). Login limits by IP prefix, by account, and by the pair, with a CAPTCHA or email step instead of a hard lockout when the per-account limit trips, so the attacker cannot lock the real user out.
import ipaddress, hashlib
def ip_bucket(addr: str) -> str:
"""IPv4: the address. IPv6: the /64 prefix -- one home or phone typically gets
a whole /64, so limiting per full address lets one attacker rotate through
18 quintillion 'different' clients and exhaust your limiter's memory."""
ip = ipaddress.ip_address(addr)
if ip.version == 4:
return f"ip4:{ip}"
net = ipaddress.ip_network(f"{addr}/64", strict=False)
return f"ip6:{net.network_address}/64"
def login_keys(ip: str, username: str) -> list[str]:
"""Login gets THREE limits. Each one closes a hole the others leave open."""
user = hashlib.sha256(username.lower().encode()).hexdigest()[:12] # no PII in keys
return [
f"login:{ip_bucket(ip)}", # one IP spraying many accounts
f"login:user:{user}", # many IPs attacking one account
f"login:pair:{ip_bucket(ip)}:{user}", # tight: this device, this account
]
for a in ("203.0.113.7", "2001:db8:abcd:12:1111:2222:3333:4444",
"2001:db8:abcd:12:ffff:0:0:1"):
print(f"{a:40} -> {ip_bucket(a)}")
for k in login_keys("2001:db8:abcd:12::99", "Priya@Example.com"):
print(k)203.0.113.7 -> ip4:203.0.113.7 2001:db8:abcd:12:1111:2222:3333:4444 -> ip6:2001:db8:abcd:12::/64 2001:db8:abcd:12:ffff:0:0:1 -> ip6:2001:db8:abcd:12::/64 login:ip6:2001:db8:abcd:12::/64 login:user:6bdb7e961d54 login:pair:ip6:2001:db8:abcd:12::/64:6bdb7e961d54
The username is hashed in the key so that counter names, which end up in logs and metrics, do not contain personal data. The cost of the hybrid is more keys per request (three rules for login instead of one), which is why it is applied per route, not globally.
Step 13 — Failure modes: fail open or fail closed
The limiter is a protective device, which means its failure behaviour must be decided in advance, per rule, and tested.
| What fails | What clients see | Mechanism |
|---|---|---|
| Redis shard down or slow | Capacity rules: nothing. Security and cost rules: 429 or 503 for that key range | 5 ms timeout; per-rule fail_mode; circuit breaker so a dead shard is not retried per request |
| Whole counter cluster down | API keeps serving; limits temporarily approximate | Fall back to local in-memory token buckets at limit / nodes: under-admits, but protects the backend. Better than both "no limits" and "no API" |
| Redis failover | A few clients briefly get a little more than their limit | Accept it; the replica missed the last increments. Cost counters are also recorded durably by the service |
| Rules service down | Nothing | Gateways keep the last good rules version in memory and on disk |
| Bad rule pushed (limit 1/min instead of 1,000/min) | Mass 429s for one tier | Shadow mode first; CI validation that flags changes over 10x; canary gateways; one-command rollback to the previous version |
| Clock skew between gateways | Buckets refill too fast or not at all | Use the store's clock (TIME in the script); guard against negative elapsed time |
| Retry storm after a 429 wave | Load arrives in synchronized waves | Honest Retry-After; SDKs use exponential backoff with jitter; deny cache absorbs immediate retries |
| Key explosion (IPv6 scan, random API keys) | Counter store memory climbs | Normalize IPv6 to /64; reject malformed keys before creating counters; TTLs on everything; maxmemory with an eviction policy |
| Limiter bug denies everyone | Outage caused by the protection | A global kill switch that turns every rule into shadow mode in seconds |
Fail open (allow when you cannot decide) is right when the rule protects capacity and the backend has other protection (autoscaling, load shedding): a limiter outage must not become an API outage. Fail closed (deny) is right when an unlimited burst causes irreversible harm or cost: OTP and SMS sends, login attempts, payment attempts, expensive LLM calls. A third option is fail to local: use the in-process bucket from the table above. Say that there are three choices, not two.
Step 14 — Observability
- Decisions per rule: allowed, denied, shadow-denied, failed-open, failed-closed, per second, tagged by rule id and tier. A rule that has never denied anything is either unnecessary or misconfigured; a rule denying 30% of a paying tier is a product problem.
- Top denied keys, refreshed every minute: this is where abuse, broken client retry loops and customers who need an upgrade all show up. Feed it to the support and sales dashboards, not only to on-call.
- Limiter latency: p50/p99/p99.9 of the check, and counter-store errors and timeouts per shard. Page on the limiter's added latency, because it taxes every request.
- Accuracy audits: sample some keys, compute their exact sliding count offline from request logs, and compare with what the limiter allowed. This is how you notice the hybrid sync overshooting more than you thought.
- Hot shard and memory: ops/s and memory per shard, keys with the highest call rate, key count growth. A sudden growth in keys is usually an attack on your key space.
- Sampled decision log: for each denial, the rule, key, count and limit. When a customer says "you rate limited us at 14:02", this is the evidence.
The trade-off summary — how to close
- Token bucket for public API limits because it expresses the two things customers care about, average and burst. We accept that its worst case in any window is
capacity + rate × window, and say so. - Sliding log only where limits are small and must be exact (login, OTP), because its memory grows with the limit; sliding counter for general "N per period" rules; fixed window for daily and monthly quotas where aligned resets are what the product promises; leaky bucket in front of fragile dependencies.
- Redis with one Lua script per algorithm, not locks or optimistic transactions: atomic, one round trip, no contention collapse on hot keys.
- Limit at the gateway, layered with edge and sidecar limits, rather than in each app's memory, which silently multiplies the limit by the node count.
- Exact within a region, approximate across regions, because a cross-region round trip costs more latency than the whole budget.
- Fail mode per rule: open for capacity, closed for security and cost, local fallback for everything when the store is down.
- What I would build first: a gateway filter, one Redis primary with a replica, a token bucket script, rules in a config file, shadow mode, and the per-rule dashboard. Sharding, leasing and multi-region sync come when a number demands them.
// Write your solution here
// Write your solution here
// Write your solution here
Finished reading? Mark this lesson complete to track your progress.
