# Rate Limiting

> Give each client a refillable budget of calls - take a token to proceed, refuse with 429 and a Retry-After when the bucket is empty - so one client's burst cannot spend everyone's capacity.

- kind: pattern
- category: resilience
- aliases: Throttling
- canonical: https://aipatterns.dev/design-patterns/rate-limiting
- inspired-by: https://learn.microsoft.com/en-us/azure/architecture/patterns/rate-limiting-pattern

## Intent

Ration a shared resource by client. Each client holds a bucket of tokens that refills at a fixed rate; every call takes one token. A call with tokens available proceeds; an empty bucket refuses immediately with a `429` and a `Retry-After` that says exactly when to come back. Bursts within the budget pass through, sustained demand is capped at the refill rate, and no client's spike can spend another client's capacity.

## Forces

- **Shared capacity** vs **uneven demand**: the resource serves everyone, but one client's burst can consume what the others needed.
- **Reject early** vs **queue forever**: refusing fast lets the caller reschedule; letting everything through converts your limit into everyone's timeout.
- **Burst allowance** vs **average cap**: clients work in bursts, so a flat requests-per-second is either too tight or too loose; a bucket gives both a burst size and a sustained rate.
- **Fair share** vs **total throughput**: strict per-client fairness refuses work the resource could have done; dropping fairness rewards the loudest tenant.

## Therefore

**Charge every call to a per-client token bucket that refills on time; when the bucket is empty, refuse with 429 and a computed Retry-After instead of admitting the call.**

The bucket is a counter plus a clock, keyed per client. Refusal is not an error state to avoid - it is the contract that makes the caller's [Retry](https://aipatterns.dev/design-patterns/retry.md) policy honest: `Retry-After` tells the client exactly when capacity exists, and a well-behaved client spends the wait instead of hammering.

## Structure

```mermaid
flowchart TD
  A[Request arrives] --> B{Bucket has a token?}
  B -- yes --> C[Take one token and handle the request]
  B -- no --> D[Refuse with 429 and Retry-After]
  E[Time passes] -- refills at a fixed rate --> B
```

### Participants

- **Limiter** (`RateLimiter`): holds one bucket per client. `acquire` refills by elapsed time, takes a token, or returns the wait until one exists.
- **Bucket** (implicit in `RateLimiter`): capacity (burst size), refill rate (sustained rate), current tokens, last refill time.
- **Endpoint** (`ReportsEndpoint`): the guarded resource. Checks the limiter first; on refusal answers `429` with `Retry-After` instead of doing the work.
- **Client**: a caller identified by key - user id, API key, tenant. On `429`, waits the stated time (client-side limiting).
- **Clock** (`now`): injected so refill is testable without sleeping.

## Use it when

- A resource is shared by clients whose demand is uneven - an API route in front of a database, an expensive report, a model invocation billed per call.
- You must protect the resource from bursts while still letting well-behaved bursts through: the bucket's capacity is the burst allowance, the refill is the sustained rate.
- Each tenant needs a guaranteed share: one client hammering the endpoint must not starve the others.
- You are the client of a provider that rate-limits you - budget your own calls per key and honor the provider's `429` + `Retry-After`, so the provider's limiter never has to teach you the lesson.

## Do not use it when

- The resource is genuinely too small for its normal load. A limiter rationing an under-provisioned database moves the outage from everyone-at-once to first-come-first-served; add capacity or fix the query instead.
- The goal is stopping attackers or abusive scrapers. Limits throttle honest clients that count their calls; bad actors spin up more clients. Use allowlists, blocking and bot detection for that job.
- The calls are in-process functions. There is no shared resource to ration and no client boundary to key on.
- Work must not be lost under any circumstance. A `429` drops the call; if it must happen eventually, queue it with [Command](https://aipatterns.dev/design-patterns/command.md) and let a worker drain at a safe rate.

## Application grill

**Inspect first:** the entry points that need limits (public routes, webhooks, LLM and third-party calls with hard quotas); the platform's built-in limiters first (WAF rules, Vercel or Cloudflare rate limiting, gateway plugins, framework middleware); the instance count, which decides per-process versus shared counters.

**Missing pieces:** single instance: an in-memory token bucket - free. Multiple instances or serverless: shared counters in Redis or the platform's rate-limit bindings; a shared store adds its own latency to every request, so prefer the edge limiter when one exists.

**Ask before you build:**

- **Scale:** what is the limit per - user, IP, API key - and what burst is legitimate before refusing?
- **Performance:** can the check run at the edge so the origin never pays for refused calls?
- **Reliability:** when the counter store is down, does the service fail open (allow) or closed (refuse everything)?
- **Budget:** whose spend does the limiter protect (LLM tokens, vendor calls), and what does exceeding it cost?
- **Implementation:** what does a refused caller receive (429 with Retry-After), and where are limits configured?

## Implementation steps

1. Name the resource and the unit of spend: requests, model tokens, dollars, queue slots. The unit decides what one token means.
2. Pick the algorithm: a token bucket when clients work in bursts under an average cap; a sliding window when a hard count per period is the actual rule.
3. Key the buckets by client identity, and by resource when one client has different budgets for different endpoints.
4. Compute `Retry-After` from the bucket - the time until the next token exists - so refusal carries a recovery plan, not just a status code.
5. Decide where bucket state lives. In-process is simplest and means every instance enforces its own bucket; a shared store (Redis) gives one true budget per client at the cost of a read per call. Pick deliberately; silent per-instance limits are the default bug.
6. On the client side, treat `429` as a scheduled retry: wait exactly `Retry-After`, then [Retry](https://aipatterns.dev/design-patterns/retry.md) with [Exponential Backoff](https://aipatterns.dev/design-patterns/exponential-backoff.md) for anything without the header.
7. Emit per-client metrics: refused-per-minute per key is your fair-use signal, and a spike in refusals is a client bug or a capacity conversation, not noise.

## Example

A reports endpoint generates an expensive document per client. Each client holds a bucket of 2 tokens refilling at 1 per second. The first two calls of a burst pass; the third is refused with a `Retry-After` computed from the refill; after the wait, capacity exists again. A second client's bucket is untouched by the first client's burst.

```ts title="reports.ts"
type Refusal = { ok: false; retryAfterMs: number };

class RateLimiter {
  private buckets = new Map<string, { tokens: number; at: number }>();

  constructor(
    private readonly capacity: number, // burst size
    private readonly refillPerMs: number, // sustained rate
    private readonly now: () => number,
  ) {}

  acquire(client: string): { ok: true } | Refusal {
    const bucket = this.buckets.get(client) ?? {
      tokens: this.capacity,
      at: this.now(),
    };
    // Refill for the time that passed since the bucket was last touched.
    bucket.tokens = Math.min(
      this.capacity,
      bucket.tokens + (this.now() - bucket.at) * this.refillPerMs,
    );
    bucket.at = this.now();
    if (bucket.tokens >= 1) {
      bucket.tokens -= 1;
      this.buckets.set(client, bucket);
      return { ok: true };
    }
    this.buckets.set(client, bucket);
    const wait = Math.ceil((1 - bucket.tokens) / this.refillPerMs);
    return { ok: false, retryAfterMs: wait };
  }
}

class ReportsEndpoint {
  private limiter = new RateLimiter(2, 1 / 1_000, () => clock); // 2 burst, 1/s
  private generated = 0;

  report(client: string): string {
    const grant = this.limiter.acquire(client);
    if (!grant.ok)
      return `429 to ${client}, Retry-After ${grant.retryAfterMs}ms`;
    this.generated++;
    return `200 to ${client} (report #${this.generated})`;
  }
}

let clock = 0;
const endpoint = new ReportsEndpoint();

console.log(endpoint.report("acme")); // 200: token 1 of the burst
console.log(endpoint.report("acme")); // 200: token 2 of the burst
console.log(endpoint.report("acme")); // 429 with Retry-After 1000ms
console.log(endpoint.report("globex")); // 200: acme's burst never touched globex

clock += 1_000; // one refill period later
console.log(endpoint.report("acme")); // 200: the wait bought a token
```

```python title="reports.py"
import math
from typing import Callable

class Refusal:
    def __init__(self, retry_after_ms: int) -> None:
        self.retry_after_ms = retry_after_ms

class RateLimiter:
    def __init__(
        self, capacity: int, refill_per_ms: float, now: Callable[[], int]
    ) -> None:
        self._capacity, self._refill, self._now = capacity, refill_per_ms, now
        self._buckets: dict[str, list[float]] = {}  # client -> [tokens, last_at]

    def acquire(self, client: str) -> None | Refusal:
        tokens, at = self._buckets.get(client, [float(self._capacity), self._now()])
        tokens = min(self._capacity, tokens + (self._now() - at) * self._refill)
        if tokens >= 1:
            self._buckets[client] = [tokens - 1, self._now()]
            return None
        self._buckets[client] = [tokens, self._now()]
        return Refusal(retry_after_ms=math.ceil((1 - tokens) / self._refill))

class ReportsEndpoint:
    def __init__(self, now: Callable[[], int]) -> None:
        self._limiter = RateLimiter(capacity=2, refill_per_ms=1 / 1_000, now=now)
        self._generated = 0

    def report(self, client: str) -> str:
        refusal = self._limiter.acquire(client)
        if refusal is not None:
            return f"429 to {client}, Retry-After {refusal.retry_after_ms}ms"
        self._generated += 1
        return f"200 to {client} (report #{self._generated})"

clock = 0
now = lambda: clock  # noqa: E731 - injected clock
endpoint = ReportsEndpoint(now)

print(endpoint.report("acme"))  # 200: token 1 of the burst
print(endpoint.report("acme"))  # 200: token 2 of the burst
print(endpoint.report("acme"))  # 429 with Retry-After 1000ms
print(endpoint.report("globex"))  # 200: acme's burst never touched globex

clock += 1_000  # one refill period later
print(endpoint.report("acme"))  # 200: the wait bought a token
```

```go title="reports.go"
package main

import (
	"fmt"
	"math"
)

type refusal struct{ retryAfterMs int }

type RateLimiter struct {
	capacity    int
	refillPerMs float64
	now         func() int
	buckets     map[string]*bucketState
}

type bucketState struct {
	tokens float64
	at     int
}

func NewRateLimiter(capacity int, refillPerMs float64, now func() int) *RateLimiter {
	return &RateLimiter{
		capacity:    capacity,
		refillPerMs: refillPerMs,
		now:         now,
		buckets:     map[string]*bucketState{},
	}
}

func (l *RateLimiter) acquire(client string) *refusal {
	b, ok := l.buckets[client]
	if !ok {
		b = &bucketState{tokens: float64(l.capacity), at: l.now()}
	}
	b.tokens = math.Min(float64(l.capacity), b.tokens+float64(l.now()-b.at)*l.refillPerMs)
	if b.tokens >= 1 {
		b.tokens--
		b.at = l.now()
		l.buckets[client] = b
		return nil
	}
	b.at = l.now()
	l.buckets[client] = b
	wait := int(math.Ceil((1 - b.tokens) / l.refillPerMs))
	return &refusal{retryAfterMs: wait}
}

type ReportsEndpoint struct {
	limiter   *RateLimiter
	generated int
}

func NewReportsEndpoint(now func() int) *ReportsEndpoint {
	// 2-token burst, sustained rate of 1 per second.
	return &ReportsEndpoint{limiter: NewRateLimiter(2, 1.0/1_000, now)}
}

func (e *ReportsEndpoint) report(client string) string {
	if r := e.limiter.acquire(client); r != nil {
		return fmt.Sprintf("429 to %s, Retry-After %dms", client, r.retryAfterMs)
	}
	e.generated++
	return fmt.Sprintf("200 to %s (report #%d)", client, e.generated)
}

func main() {
	clock := 0
	now := func() int { return clock }
	endpoint := NewReportsEndpoint(now)

	fmt.Println(endpoint.report("acme"))  // 200: token 1 of the burst
	fmt.Println(endpoint.report("acme"))  // 200: token 2 of the burst
	fmt.Println(endpoint.report("acme"))  // 429 with Retry-After 1000ms
	fmt.Println(endpoint.report("globex")) // 200: acme's burst never touched globex

	clock += 1_000 // one refill period later
	fmt.Println(endpoint.report("acme")) // 200: the wait bought a token
}
```

```java title="Reports.java"
import java.util.HashMap;
import java.util.Map;
import java.util.function.IntSupplier;

public class Reports {
    record Refusal(int retryAfterMs) {}

    static final class RateLimiter {
        private static final class Bucket {
            double tokens;
            long at;
        }

        private final int capacity;
        private final double refillPerMs;
        private final IntSupplier now;
        private final Map<String, Bucket> buckets = new HashMap<>();

        RateLimiter(int capacity, double refillPerMs, IntSupplier now) {
            this.capacity = capacity;
            this.refillPerMs = refillPerMs;
            this.now = now;
        }

        Refusal acquire(String client) {
            Bucket b = buckets.computeIfAbsent(client, k -> {
                Bucket fresh = new Bucket();
                fresh.tokens = capacity;
                fresh.at = now.getAsLong();
                return fresh;
            });
            b.tokens = Math.min(capacity, b.tokens + (now.getAsLong() - b.at) * refillPerMs);
            if (b.tokens >= 1) {
                b.tokens -= 1;
                b.at = now.getAsLong();
                return null;
            }
            b.at = now.getAsLong();
            return new Refusal((int) Math.ceil((1 - b.tokens) / refillPerMs));
        }
    }

    static final class ReportsEndpoint {
        private final RateLimiter limiter;
        private int generated = 0;

        ReportsEndpoint(IntSupplier now) {
            // 2-token burst, sustained rate of 1 per second.
            this.limiter = new RateLimiter(2, 1.0 / 1_000, now);
        }

        String report(String client) {
            Refusal refusal = limiter.acquire(client);
            if (refusal != null) {
                return "429 to " + client + ", Retry-After " + refusal.retryAfterMs() + "ms";
            }
            generated++;
            return "200 to " + client + " (report #" + generated + ")";
        }
    }

    public static void main(String[] args) {
        long[] clock = {0};
        ReportsEndpoint endpoint = new ReportsEndpoint(() -> clock[0]);

        System.out.println(endpoint.report("acme")); // 200: token 1 of the burst
        System.out.println(endpoint.report("acme")); // 200: token 2 of the burst
        System.out.println(endpoint.report("acme")); // 429 with Retry-After 1000ms
        System.out.println(endpoint.report("globex")); // 200: acme's burst left globex alone

        clock[0] += 1_000; // one refill period later
        System.out.println(endpoint.report("acme")); // 200: the wait bought a token
    }
}
```

Under concurrency, the read-refill-take sequence must be atomic per bucket - a lock, an atomic compare-and-swap, or a Lua script in Redis - or two simultaneous callers can both see the last token and both take it.

## Trade-offs

**Gains**
- One client's burst stops being everyone's outage; per-client budgets make demand predictable.
- `429` + `Retry-After` converts overload into a schedule the client can follow.
- Refusing before the work starts protects the expensive resource, not just the response time.

**Costs**
- Rejected work is dropped - callers need the retry discipline, and non-idempotent calls need care ([Retry](https://aipatterns.dev/design-patterns/retry.md)).
- Bucket state must live somewhere: per-instance limits multiply with your fleet unless you share state.
- Thresholds are policy: too tight refuses honest load, too loose protects nothing, and both failings surface as support tickets.
- Fairness at the client key is only as good as the key - shared API keys collapse many users into one bucket.

## Relations

- [Retry](https://aipatterns.dev/design-patterns/retry.md): the two halves of one contract - the limiter's `Retry-After` is the retry policy's input, and a client's own budget prevents the `429`s in the first place.
- [Exponential Backoff](https://aipatterns.dev/design-patterns/exponential-backoff.md): the spacing rule for `429`s that arrive without a `Retry-After` header.
- [Circuit Breaker](https://aipatterns.dev/design-patterns/circuit-breaker.md): complementary jobs - the limiter rations a dependency that is up; the breaker stops calling one that is down.
- [Timeout](https://aipatterns.dev/design-patterns/timeout.md): bounds each admitted call; a limiter that admits a request cannot also promise it finishes.
- [Fallback](https://aipatterns.dev/design-patterns/fallback.md): the degraded answer a caller serves instead of the refused work - a cached report, a queue position, a "try later".

## Agent checklist

- [ ] Buckets are keyed per client (and per resource where budgets differ), and the key survives auth changes.
- [ ] Refusal answers `429` with a computed `Retry-After`, never a bare error.
- [ ] The read-refill-take step is atomic under concurrency.
- [ ] Bucket state's location (per instance or shared) is a written decision, not an accident.
- [ ] Client-side callers honor `Retry-After` and never retry a refusal immediately.
- [ ] Refusal counts per key are monitored; a rising refusal rate triggers a capacity or client-bug review, not silence.