# Rate algorithms
The four algorithms behind an rpm or tpm limit, what each admits under burst, which stores each can bind, and how to choose.
Source: https://tokentriage.com/docs/build/governance-rate-algorithms
---
import Callout from '../../../components/Callout.astro';
import NextSteps from '../../../components/NextSteps.astro';
A cap of 300 requests a minute does not say what happens when 300 arrive in the same second.
Are they all admitted? Is the 300th turned away? Both answers are defensible, and the
algorithm you name is what decides between them.
Four algorithms ship. `gcra` is the default and covers almost every case. The other three
exist because operators arrive with a counter shape already in mind. Two of them turn down
configurations the default accepts, and one of them runs on a single replica only.
This page is the catalogue: formulas, ceilings, the stores each one binds, and a decision
table at the end. For what a limit counts and when, read
[how a limit counts](/docs/build/governance-enforcement-classes) first.
## Where the algorithm knob applies
Four of the six limit types decline the key outright, so the first question is whether your
limit takes an algorithm at all.
| Limit type | Takes `algorithm:` | Accepted values |
|---|---|---|
| `rpm` | yes | `gcra`, `fixed_window`, `sliding_window`, `token_bucket` |
| `tpm` | yes | `gcra` only |
| `concurrency` | no | a live gauge, not a windowed rate |
| `budget_usd` | no | folded from ledger rows |
| `quota_tokens` | no | folded from ledger rows |
| `quota_requests` | no | folded from ledger rows |
An unregistered name is a path-named config error, and so is naming one on a type that takes
none. Three keys shape a rate-class limit, the same three for every algorithm:
| Key | Default | What it sets |
|---|---|---|
| `amount` | required | sustained units per window (requests for `rpm`, tokens for `tpm`) |
| `period` | required | the window `w`, written as a duration (`1s`, `1m`, `1h`); a calendar period does not compile |
| `burst` | `amount` | allowance depth, in units. Read by `gcra` and `token_bucket` only |
```yaml
governance:
limits:
- id: team_rpm
attach: { level: team }
type: rpm
amount: 300 # sustained ceiling per window
period: 1m # a rate-class limit without one does not compile
algorithm: gcra # the default; safe to omit
burst: 60 # depth a drained key can spend at once
posture: { mode: "on", enforce: hard, fail: open }
```
Leaving `algorithm:` out and writing `algorithm: gcra` produce byte-identical compiled limits.
The config layer fills the empty value in before the counter identity is computed, so spelling
out the default is a no-op rather than a counter reset.
## The four algorithms
All four answer the same question. Each sees one arrival with a cost and a timestamp, then
returns whether to admit it, a best-effort remaining count, a retry delay rounded up to whole
seconds, and a reset delay. `gcra` and `token_bucket` add an answer the window pair cannot
give: a typed signal that a cost cannot fit under this limit at any future moment, which
becomes a `quota_cost_unfittable` response rather than a retry that cannot succeed. An `rpm`
limit always presents a cost of 1; a `tpm` limit presents its token estimate. Per-key state is
one `int64` in every case, so the choice changes what those 64 bits mean and nothing else.
### `gcra`
Spaces arrivals one per emission interval, and lets a key that has gone quiet spend a stored
allowance in one go. The default, and a leaky bucket recorded as the instant the bucket next
runs empty.
**How it decides.** State is a single theoretical arrival time (TAT). With window `w` and
amount `r`, the emission interval is `T = w / r` and the allowance offset is `τ = T × burst`.
```text
tat = max(stored_tat, now)
new_tat = tat + n × T
allow_at = new_tat − τ
admit iff now ≥ allow_at
```
On admission the TAT advances. On a turn-away it is left untouched, so a rejected request
consumes no capacity and a retrying client cannot push its own recovery further out.
**What it guarantees.** A sustained `amount` per `period`, plus a one-time allowance of `burst`
units to a key that has drained. The constraint rolls with the clock; it is not aligned to one.
**Burst.** `amount: 300`, `period: 1m`, `burst: 60` gives `T = 200ms` and `τ = 12s`. A drained
key admits 60 arrivals at once, then one every 200 ms, so the minute after a drained start
admits about 360.
Leave `burst` out and it defaults to `amount`. The same limit then admits 300 at once and 300
more across the minute: about 600, or twice the amount. That is the same magnitude as the
fixed window's boundary burst, and the difference is shape rather than size. GCRA's excess is
a one-time allowance handed to a key that stopped sending. A fixed window's excess repeats at
every aligned boundary.
**Ceiling.** None on the count; the TAT is an unbounded `int64`. The one compile-time check is
that `τ = T × burst` fits in an `int64`, and a config that overflows it is turned down with a
path-named error rather than wrapping into a limit that admits nothing.
**Stores.** `local` (the default), `share`, and `redis`. GCRA is the only algorithm carrying the
per-step effective-rate form the `share` store drives, and it has its own Redis Lua asset.
**How it fails.** A single cost larger than the allowance returns the unfittable verdict. For
`rpm` that is unreachable, because the cost is always 1. For `tpm` it is the reason a burst
below the reserve cap does not compile.
**Reach for something else when.** Rarely. The one case is a counter you want aligned to clock
minutes, for parity with a provider's own reporting.
### `fixed_window`
Counts arrivals in the current clock-aligned window and drops the count to zero at the
boundary.
**How it decides.** One `int64` packs the window index with two 16-bit counters. It is the
sliding-window body with the previous window's weight forced to zero, so the test is
`curr + n ≤ amount`. Rolling into the next window resets `curr`; skipping more than one, or a
clock that moves backwards, resets both counters.
**What it guarantees.** At most `amount` inside any aligned window, and up to roughly twice
that across an interval spanning a boundary.
**Burst.** Not read. The frozen conformance vector shows the boundary instead: with
`amount: 10` and an 8-second window, the counter fills to 9 by t=2s and the next cost-3 arrival
at t=4s is turned away. At t=8s the window rolls, the counter resets, and 9 more are admitted
across the next two seconds. Eighteen units inside ten seconds, against a limit of ten a
window. Push the first nine to the last instant of window 0 and the two groups land back to
back.
**Ceiling.** An `amount` above 65535 does not compile. The counter field is 16 bits wide, and
clamping it would make the admit test true for every arrival above the ceiling, so the config
is turned down instead of saturated.
**Stores.** `local` and `redis`. The two window algorithms share one Lua script, selected by a
flag. `store: share` is a config error for both.
**How it fails.** The boundary burst is the headline, and it repeats every window. Underneath
it, `burst` is inert, and editing an inert `burst` costs you the live counter on the next
reload.
**Reach for something else when.** Your amount is above 65535, your callers cluster at the top
of the minute, or you need `store: share`.
### `sliding_window`
Weights the previous window's count by how much of it still falls inside the trailing window,
so the ceiling moves with the clock instead of resetting on it.
**How it decides.** The same packed `int64`, with the previous counter kept and decayed:
```text
rate(t) = prev × ((w − elapsed) / w) + curr
admit iff rate(t) + n ≤ amount
```
It is evaluated as `prev × (w − elapsed) + (curr + n) × w ≤ amount × w`, in scaled integers, so
no float rounding reaches an admit decision.
**What it guarantees.** No cliff at an aligned boundary. At the instant a window rolls, the
previous window still counts at full weight, and its contribution decays linearly across the
new one.
**Burst.** Not read. The vector shows the fractional weight doing the work instead: with
`amount: 10`, `w = 8s`, a previous count of 6 and a current count of 6 at 6 seconds elapsed,
the effective rate is `6 × (2/8) + 6 = 7.5`, so a cost-3 arrival is turned away. A fixed window
with the same history would have admitted it.
**Ceiling.** The same 65535 counter ceiling as `fixed_window`, turned down the same way.
**Stores.** `local` and `redis`. Not `share`.
**How it fails.** The two-counter form is an approximation: it treats the previous window's
arrivals as evenly spread, which they are not. Its retry delay is the time to the next
boundary, a safe upper bound rather than the earliest moment the decay would admit. The window
vectors assert the admit decision and the resulting counter and nothing else, so remaining,
retry and reset are pinned for `gcra` and for no other algorithm.
**Reach for something else when.** Your amount is above 65535, the limit is `tpm`, or you need
`store: share`.
### `token_bucket`
A bucket of depth `burst` refilling at `amount` per `period`. It is the same arithmetic as
`gcra` under a name more operators recognise.
**How it decides.** It builds the GCRA limiter and forwards every step to it. The equivalence
is not approximate: a bucket's level at any instant is `(τ − (TAT − now)) / T`, so storing the
TAT stores the level in one `int64` at full time resolution. The peer ships as config
vocabulary, not as different arithmetic.
**What it guarantees, and its burst.** Per arrival, whatever `gcra` gives: depth `burst`,
defaulting to `amount`.
**Ceiling.** None on the count, and the same `τ` overflow check.
**Stores.** `local` only. The wrapper does not expose the effective-rate form the `share` store
needs, and no Redis Lua asset is registered under its name, so a `token_bucket` limit naming
either store stops the process when governance arms. One message per config:
```text
Error: governance: compile limits: govern: limit "team_rpm": store "share": counter: store "share" requires an algorithm with a per-step effective-rate form (ratealg.EffectiveLimiter); "token_bucket" has none — use algorithm "gcra"
Error: governance: compile limits: govern: limit "team_rpm": store "redis": counter: algorithm has no distributed (redis) form
```
An identical limit spelling `algorithm: gcra` compiles against either store.
**How it fails.** No conformance vector covers it. Its correctness rides on GCRA's, which
follows from the delegation, and is still worth knowing before you pick the wrapper over the
thing it wraps.
**Reach for something else when.** In practice, always. Same arithmetic, fewer stores, no
vectors of its own.
## What `burst` does, and where it is read
This is the one knob whose name promises the same thing on all four and delivers on two.
| Algorithm | Reads `burst` | Stored default | Effect of setting it |
|---|---|---|---|
| `gcra` | yes | `amount` | sets `τ = T × burst`, the depth a drained key spends at once |
| `token_bucket` | yes | `amount` | the same, framed as bucket capacity |
| `fixed_window` | no | `amount` | none |
| `sliding_window` | no | `amount` | none |
A `sliding_window` limit carrying `burst: 5` behaves identically to the same limit without it.
The limiter is built from the window and the amount alone, the config validator checks only
the amount, and the distributed Lua says in its own header that the window algorithm ignores
the value. Nothing warns.
Editing that inert `burst` is not free. The hot-reload carry compares `burst` literally when
deciding whether a limit's live counter may be transplanted into the newly compiled set, so a
burst-only edit on a window limit fails the comparison and the counter restarts at zero. You
buy a window's worth of extra admissions and change enforcement by nothing. Leave `burst` off
a window limit, and if it is already there, drop it in the same reload as a change you meant
to make.
## Ceilings, and where they are enforced
Three compile-time domain checks exist, and all three run when governance arms rather than at
`tokentriage validate`, which resolves names and checks coherence without compiling a limit
type.
| Check | Applies to | What does not compile |
|---|---|---|
| packed counter ceiling 65535 | `fixed_window`, `sliding_window` | an `amount` above 65535 |
| `τ = T × burst` overflow | `gcra`, `token_bucket` | a burst so large the offset leaves `int64` |
| burst below the reserve cap 16384 | `tpm` | any burst under 16384, including the default when `amount` is under it |
The third is the friendliest message governance prints. It declines a config that would have
turned away 100% of traffic:
```text
Error: governance: compile limits: govern: limit "team_tpm": tpm limit "team_tpm": burst 500 is below the reserve cap 16384 — an ordinary max-token reserve could never fit (a permanent 100% refusal); raise burst (default is amount 500) to at least the reserve cap
```
The first surprises anyone running a fleet. It holds even with `store: redis`, where a Redis
integer has no such width, because the check runs against the chosen algorithm whatever the
store: the local fallback limiter is built from the same config. So a `sliding_window` limit
with `amount: 100000` and `store: redis` validates clean, given a config that declares
`shared_state.redis` so the store binding itself resolves. It prints `OK: configuration is
valid`, then stops the process when governance arms:
```text
Error: governance: compile limits: govern: limit "team_rpm": sliding_window: limit 100000 exceeds the packed window-counter ceiling 65535; the frozen int64 state holds a 16-bit per-window counter — use algorithm "gcra" (unbounded) for limits this large
```
The fix is the one the error names, and it is not a store change: move that limit to `gcra`.
A green `tokentriage validate` does not mean governance will arm. Every check in the preceding
table, plus the store bindings each algorithm supports, is evaluated at boot and at hot
reload, so a config that validates clean can still stop the process on the next restart. Run
`tokentriage govern preview -c --log ` before you deploy one: it compiles the
proposed limits against the same registries. It skips the store build, so the two
`token_bucket` store errors still wait for boot.
## What a caller sees on the success path
With `governance.keys.disclose_limits` at its default of `true`, a served request advertises
the tightest rate-class limit that applies to it. The pair of numbers is measured on two
different scales, which reads like a bug the first time you meet it.
```console
HTTP/1.1 200 OK
Content-Type: application/json
Ratelimit-Policy: "team_rpm";q=300;w=60
X-Ratelimit-Limit-Requests: 300
X-Ratelimit-Remaining-Requests: 59
X-Tt-Request-Id: tt_tbuhetygwddxiaprkw3j3fkwze
```
That capture is from a local sandbox against a fake upstream; the request id will differ. The
limit behind it is `amount: 300`, `period: 1m`, `burst: 60`, and one request has been served.
- `X-Ratelimit-Limit-Requests` reports the sustained ceiling, the `amount`.
- `X-Ratelimit-Remaining-Requests` reports the instantaneous headroom, which under GCRA is the
burst depth. One request has been spent against a depth of 60, so it reads 59.
The read behind that number is a non-committing unit probe through the same algorithm, with
the probe added back to recover the units consumed. Under GCRA that recovers burst headroom,
not the share of the minute left, so a caller dividing 59 by 300 is measuring pressure against
the allowance rather than against the rate. Leave `burst` at its default and the two scales
coincide: the same limit at `burst: 300` reads 299 of 300 after one request.
One store removes these headers entirely. A `redis`-backed rate limit reports no observation,
so it cannot be the tightest limit, and a deployment whose rate limits are all Redis-backed
writes no success rate headers at all. [Governance across
replicas](/docs/build/governance-distributed) covers the store side.
## Choosing one
Most of this page is detail you read once. The decision itself fits in eight rows, and the
default answers most of them.
| You want | Use |
|---|---|
| a rate limit, with no specific reason to differ | `gcra` |
| a token-rate limit (`tpm`) | `gcra`, the only value that compiles |
| counters aligned to clock minutes, matching a provider's own window | `fixed_window` |
| no cliff at the top of the minute, on counts under 65535 | `sliding_window` |
| a fleet cap divided across live replicas (`store: share`) | `gcra`, the only algorithm that store drives |
| a counter shared through Redis | `gcra`, `fixed_window` or `sliding_window` |
| an `amount` above 65535 | `gcra` |
| bucket vocabulary in your runbook | `gcra` anyway; `token_bucket` is the same arithmetic with fewer stores |
`gcra` is the default and it is the right answer unless a row in that table gives you a
specific reason. It has no counter ceiling, the widest store support, the only per-step
effective-rate form, and the only conformance vectors that cover the disclosure fields as well
as the admit decision.
## What this page does not cover
What each limit type counts is [the six limit types](/docs/build/governance-limits), and when
a counter is written relative to the request is [how a limit
counts](/docs/build/governance-enforcement-classes). How a counter is shared across replicas,
with the bound each store discloses, is [governance across
replicas](/docs/build/governance-distributed). The catalogue of knobs that validate and then
do nothing is [what governance does not do](/docs/build/governance-gaps).