Rate algorithms

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 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

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.

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:

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:

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.

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:

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:

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.

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.

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 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, and when a counter is written relative to the request is how a limit counts. How a counter is shared across replicas, with the bound each store discloses, is governance across replicas. The catalogue of knobs that validate and then do nothing is what governance does not do.