<!--
Author: Simon-Pierre Boucher
Contact: contact@spboucher.ai
-->

# Patterns — Rate Limiting

## Contents
- Token bucket in Redis (atomic)
- Response headers
- Cost-weighted limits
- Local fallback
- Penalty escalation
- Load shedding
- Gotchas

## Token bucket in Redis (atomic)

```lua
-- KEYS[1]=bucket key  ARGV: rate_per_s, burst, now_ms, cost
-- Returns {allowed(0/1), remaining, retry_after_s}
local rate, burst = tonumber(ARGV[1]), tonumber(ARGV[2])
local now, cost   = tonumber(ARGV[3]), tonumber(ARGV[4])
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or burst
local ts     = tonumber(b[2]) or now
tokens = math.min(burst, tokens + (now - ts) / 1000 * rate)
local allowed = tokens >= cost and 1 or 0
if allowed == 1 then tokens = tokens - cost end
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(burst / rate * 2000)) -- self-clean idle keys
local retry = allowed == 1 and 0 or math.ceil((cost - tokens) / rate)
return {allowed, math.floor(tokens), retry}
```

```python
allowed, remaining, retry = redis.evalsha(
    SHA, 1, f"rl:{api_key}:{cls}", RATE, BURST, now_ms(), cost)
```

One Lua call = read-modify-write with no race; never split GET/SET
across the network.

## Response headers

```python
def limit_headers(limit, remaining, reset_epoch):
    return {
        "X-RateLimit-Limit": str(limit),
        "X-RateLimit-Remaining": str(max(0, remaining)),
        "X-RateLimit-Reset": str(reset_epoch),
    }

# On rejection add:
#   Retry-After: <seconds>   and body: {"error": "rate_limited", "retry_after": n}
```

Send the X-RateLimit-* trio on 200s too — clients pace themselves only if
they can see the meter.

## Cost-weighted limits

```python
COSTS = {          # units per call; base=1. Weigh by measured backend cost.
    "search": 10,  # fans out to the search cluster
    "export": 25,  # long-running, memory heavy
    "read":   1,
    "health": 0,   # never throttle probes
}
cost = COSTS.get(endpoint_class, 1)
```

## Local fallback

```python
NODE_SHARE = RATE // max(node_count(), 1)  # conservative split when Redis is down

def check(key, cost):
    try:
        return redis_bucket(key, cost)
    except RedisError:
        if key_route_is_sensitive(key):    # login/signup/reset/payment
            return REJECT                  # fail-closed
        return local_bucket(key, cost, rate=NODE_SHARE)  # fail-open, degraded
```

## Penalty escalation

```python
# Repeat offenders get exponentially longer cool-downs.
strikes = redis.incr(f"rl:strikes:{api_key}")
redis.expire(f"rl:strikes:{api_key}", 3600)
if strikes > 3:
    penalty = min(2 ** (strikes - 3) * 60, 3600)  # 1min → 1h cap
    redis.setex(f"rl:block:{api_key}", penalty, "1")
```

## Load shedding

```python
QUEUE_DEPTH_MAX = 100   # ≈ p99 concurrency × safety factor 2
def middleware(request):
    if executor.queue_depth() > QUEUE_DEPTH_MAX:
        return Response(503, headers={"Retry-After": "5"})
    ...
```

Shed at the cheapest point in the stack (edge/middleware), before auth and
DB work — the point of shedding is to spend nothing on rejected requests.

## Gotchas

- **Fixed windows double-dose at boundaries**: 100/min allows 200 requests
  in the 2 s straddling the minute mark; token bucket doesn't.
- **Limiting after authentication** spends a DB call on every rejected
  request — put coarse anti-abuse limits before auth, fine per-user limits
  after.
- **`Retry-After: 0`** (rounding down) makes clients hammer instantly;
  always `ceil`.
- **One bucket for reads and writes** lets a read storm starve writes;
  split classes.
- **Missing `PEXPIRE` on buckets** leaks a key per client forever.
- **Health checks and load-balancer probes** must bypass limits or the LB
  will mark healthy nodes dead during an attack — exactly when you need them.