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.

MotiveExampleWhat it implies
Protect capacityA client's retry loop sends 5,000 req/s to an endpoint sized for 800 totalApproximate is fine; must be fast; fail open
Fairness between tenantsOne customer's nightly analytics export starves everyone's checkout callsPer-tenant keys; priority classes; per-route limits
SecurityCredential stuffing, OTP guessing, card testing with stolen numbersPer-account and per-IP keys; fail closed; exact counts
Cost controlEvery POST /otp sends an SMS that costs money; every LLM call costs tokensWeighted cost per request; daily quotas; fail closed
Revenue / packagingFree: 60/min, Pro: 1,000/min, Enterprise: customTiered rules as data; overrides; accurate usage reporting
Smoothing spikesA partner's batch job arrives as 10,000 calls in the first second of every hourShaping (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 429 with Retry-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")
Output
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)])
Output
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 INCR on 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 − window and 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")
Output
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 refilled 30 s × 10/60 = 5 tokens. These are features: they give credit for idle time, which real clients expect.
  • A token bucket's true worst case is capacity + rate × T in 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

AlgorithmState per keyAccuracyBurstsUse it for
Fixed window1 integerUp to 2x at boundariesAllows edge burstsDaily/monthly quotas, "5 SMS per day", billing counters
Sliding log1 timestamp per accepted requestExactNone beyond limitLow limits that must be exact: login, OTP, password reset
Sliding window counter2 integersWithin a few %SmoothedGeneral "N per minute/hour" per-key rules
Token bucketFloat + timestampExact to its own definitionExplicit, configurablePublic API limits (average + burst), per-tenant fairness
Leaky bucketLevel + timestamp (+ a queue)Exact output rateAbsorbed by queueingProtecting 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")
Output
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))
Output
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 expiry

The 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}")
Output
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 remaining falling, and you never see those requests as denials.
  • Retry-After in 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-Policy fields come from the IETF httpapi working group's standardisation effort; the X-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

flowchart TB C[Clients] --> EDGE[CDN / WAF
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

WhereKnowsStrengthWeakness
CDN / WAF edgeIP, path, headersAbsorbs floods before they reach you; no infrastructure to runDoes not know API keys, tiers or cost; coarse
API gateway (filter or external service)Authenticated identity, route, tierOne policy for all services; denies before any app CPU is spentA shared dependency on the hot path; needs a counter store
Sidecar / service meshCalling service, destinationProtects each service from internal callers too; language-agnosticMany small local limits; global accuracy needs the same shared store
In-app libraryEverything, including business context ("this user's 3rd transfer today")Richest rules; no extra hopEvery 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

sequenceDiagram participant C as Client participant G as Gateway participant L as Local cache participant R as Redis shard participant S as Service C->>G: POST /v1/messages with API key G->>G: authenticate, resolve tier = pro G->>G: match rules v88 - per-key-global and per-route G->>L: is k_7f3a in deny cache? L-->>G: no G->>R: pipeline EVALSHA token_bucket x2 R-->>G: allowed, remaining 37 and 4 G->>S: forward request S-->>G: 201 Created G-->>C: 201 plus RateLimit headers Note over C,R: A later request finds the bucket empty G->>R: EVALSHA token_bucket R-->>G: denied, retry in 1200 ms G->>L: cache deny for k_7f3a for 1.2 s G-->>C: 429 with Retry-After 2 C->>G: retries immediately, misbehaving G->>L: deny cache hit G-->>C: 429 without touching Redis

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

  1. 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.
  2. Match rules from memory. The rules are already on the gateway; the only network call on this path is to the counter store.
  3. 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.
  4. All matching rules in one pipelined round trip. Two rules, two EVALSHAs, one network wait. Sequential calls would double the added latency.
  5. 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.
  6. 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}")
Output
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 reads redis.call('TIME') so every decision for a key uses the same clock. (Calling TIME before 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 the math.max(0, ...) guard.
  • Cluster slots. A script may only touch keys in one hash slot. Wrapping the identity in braces, rl:{k_7f3a}:tb and rl:{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:

  1. Local deny cache (Step 9): a denied key's traffic stops reaching Redis at all. Handles abusers, not legitimate heavy users.
  2. 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 × batch tokens can be in flight, so the limit is soft by that amount.
  3. 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.
  4. 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")
Output
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)
Output
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 failsWhat clients seeMechanism
Redis shard down or slowCapacity rules: nothing. Security and cost rules: 429 or 503 for that key range5 ms timeout; per-rule fail_mode; circuit breaker so a dead shard is not retried per request
Whole counter cluster downAPI keeps serving; limits temporarily approximateFall 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 failoverA few clients briefly get a little more than their limitAccept it; the replica missed the last increments. Cost counters are also recorded durably by the service
Rules service downNothingGateways 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 tierShadow mode first; CI validation that flags changes over 10x; canary gateways; one-command rollback to the previous version
Clock skew between gatewaysBuckets refill too fast or not at allUse the store's clock (TIME in the script); guard against negative elapsed time
Retry storm after a 429 waveLoad arrives in synchronized wavesHonest Retry-After; SDKs use exponential backoff with jitter; deny cache absorbs immediate retries
Key explosion (IPv6 scan, random API keys)Counter store memory climbsNormalize IPv6 to /64; reject malformed keys before creating counters; TTLs on everything; maxmemory with an eviction policy
Limiter bug denies everyoneOutage caused by the protectionA 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.

Up next · Lesson 10Key-Value Store and PastebinQuorums, versioning, LSM trees, bloom filters and a Pastebin built on top.