Rate-limiting algorithms.

A limit such as "100 requests a minute" sounds exact until you have to decide what a minute is. Token buckets, leaky buckets, fixed windows, sliding logs and sliding counters answer that question differently. The answer decides whether a client can burst, how much memory each key needs and how wrong the count can be at a window's edge.

Beginner21 minUpdated 2 Oct 2026

Requirements.

Shiplane is our fictional API that sells shipping-label quotes to 40,000 merchants. For now, one gateway node and one rule per request: the question here is the counting rule itself.

Functional requirements

#1Given a key and a rule (a rate plus a burst, or a count per window), decide allow or deny for each request in O(1) time or close to it.

#2Let a client spend a configured burst after idling, but never more than the long-run rate over time.

#3Report, with every decision, what is left and when the next request would succeed.

#4Support request costs other than 1. A bulk-label call costs 10.

#5Keep the state per key small enough to hold millions of keys in memory.

Capacity estimates

Memory per algorithm (rough, for comparison)

Assumptions

Active keys: 2.04M40,000 merchant accounts + 2M anonymous IPs seen in an hour (our assumption)
Limit: 100 per 60 s
Map overhead per key: ~100 Bkey string, hash-map pointers; a round figure
One timestamp or counter: 8 B

Working

Token bucket, 2 numbers per key(2 × 8 B + 100 B) × 2.04M = 116 B × 2.04M≈ 240 MBfrom Active keys, Map overhead per key and One timestamp or counter
Sliding counter, 2 counters + window start(3 × 8 B + 100 B) × 2.04M = 124 B × 2.04M≈ 250 MBfrom Active keys, Map overhead per key and One timestamp or counter
Sliding log at the limit, merchant accounts only(100 × 8 B + 100 B) × 40,000 = 900 B × 40,000≈ 36 MBfrom Limit, Map overhead per key and One timestamp or counter
Sliding log at the limit, every key900 B × 2.04M≈ 1.8 GBfrom Active keys and Sliding log at the limit, merchant accounts only

What it means

A log's memory grows with the limit; a bucket's does not.
For per-IP rules with millions of keys, only constant-size state fits comfortably in one node's memory.

Was this section helpful?

High-level design.

Every request makes one decision on its way in, before any business logic runs.

Rate limiter on one gateway node

One Growth-plan request, token bucket

The five algorithms (and a sixth)

Token bucket

A bucket holds up to B tokens and refills at R per second. Each request spends its cost; an empty bucket means deny. Two numbers per key: tokens and the time of the last refill.

Leaky bucket

Requests join a queue of size B that drains at R per second; a full queue means deny. The output is perfectly smooth, but admitted requests wait. Run as a meter instead of a queue, it is a token bucket upside down.

Fixed window

One counter per key per window (a calendar minute, say), reset at the boundary. One increment per request. A client can spend a full window's allowance on each side of a boundary.

Sliding window log

Store the timestamp of every accepted request and drop those older than the window; allow if fewer than N remain. Exact, but memory grows with N.

Sliding window counter

Keep this window's count and the last window's, and weight the last one by how much of it still overlaps the sliding window. Close to exact with two counters.

GCRA

Token-bucket arithmetic kept as one timestamp, the theoretical arrival time (TAT) of the next request. No refill step and no floating-point token count.

Watching them decide

The same Free-plan rule, R = 10/s and B = 20, fed a burst: 25 requests at t = 0, 8 more at 0.5 s and one at 2.5 s.

Token bucket, Free plan

Notes

1 Tokens 20 → 0; the 5 denied get 429.

Timeline as a list

Token bucket, Free plan: 3 lanes, from 0 s to 3.5 s.

0 s · 25 at 0 s · 20 allowed, 5 denied — Tokens 20 → 0; the 5 denied get 429.
0.5 s · 8 at 0.5 s · 5 allowed, 3 denied
0.5–2.5 s · all lanes · window: idle: refill 2 s × 10 = 20 = B
2.5 s · 1 at 2.5 s · 1 allowed, 19 left (allowed)

The bucket starts full with 20 tokens. The first burst empties it, half a second of refill buys 5 more requests, and two idle seconds bring it back to exactly 20; idling longer would add nothing, because the cap is B = 20.

Tokens in the bucket

Refill is computed lazily when the next request arrives; the rising line is what that arithmetic would report at any instant.

Data

Time (s)	tokens
0	20
0.02	0
0.5	5
0.52	0
2.5	20
2.52	19
2.62	20
3	20

burst B = 20: Tokens = 20

One burst across a minute boundary

Arrivals (10/s)1API clients

Fixed window

Sliding log

Sliding counter

Token bucket (B 100, R 1.67/s)

Fixed: 200 in 20 s

100 requests1

100 requests7

100 allowed (window 12:00)2 allowed

100 allowed (new window)8⁸ allowed

100 allowed3 allowed

100 denied9⁹ denied

100 allowed4 allowed

~16 allowed, 84 denied10¹⁰ denied

100 allowed5⁵ allowed

~33 allowed, 67 denied11¹¹ denied

12:01:00 window boundary

40 s45 s50 s55 s60 s65 s70 s75 s80 s

Notes

5 Starts full at 100 and refills 16.7 while spending, so 16.7 left at 12:01:00.
8 Counter reset at 12:01:00, so 200 pass in 20 s.
9 All 100 earlier timestamps are younger than 60 s until 12:01:50.
10 At 12:01:10 the estimate is 100 × 50/60 + 16 ≈ 99.3; it assumed the last minute's 100 were spread evenly. This counts only admitted requests; a counter that also counts denied requests (as Cloudflare's does) would admit almost none of the second 100.
11 16.7 left over + 10 s × 1.67/s refill = 33.

Timeline as a list

One burst across a minute boundary: 5 lanes, from 40 s to 80 s.

50–60 s · Arrivals (10/s) · 100 requests
50–60 s · Fixed window · 100 allowed (window 12:00) (allowed)
50–60 s · Sliding log · 100 allowed (allowed)
50–60 s · Sliding counter · 100 allowed (allowed)
50–60 s · Token bucket (B 100, R 1.67/s) · 100 allowed (allowed) — Starts full at 100 and refills 16.7 while spending, so 16.7 left at 12:01:00.
50–70 s · all lanes · window: Fixed: 200 in 20 s
60–70 s · Arrivals (10/s) · 100 requests
60–70 s · Fixed window · 100 allowed (new window) (allowed) — Counter reset at 12:01:00, so 200 pass in 20 s.
60–70 s · Sliding log · 100 denied (denied) — All 100 earlier timestamps are younger than 60 s until 12:01:50.
60–70 s · Sliding counter · ~16 allowed, 84 denied (denied) — At 12:01:10 the estimate is 100 × 50/60 + 16 ≈ 99.3; it assumed the last minute's 100 were spread evenly. This counts only admitted requests; a counter that also counts denied requests (as Cloudflare's does) would admit almost none of the second 100.
60–70 s · Token bucket (B 100, R 1.67/s) · ~33 allowed, 67 denied (denied) — 16.7 left over + 10 s × 1.67/s refill = 33.
60 s · all lanes · 12:01:00 window boundary (deadline)

Limit 100 per minute; t = 0 is 12:00:00. The client sends 10 requests/s from 12:00:50 to 12:01:10, 200 in all. Each lane is one algorithm judging the same arrivals.

What each admitted in the 60 s ending 12:01:10

Algorithm	Admitted	Versus the limit of 100
Fixed window	100 + 100 = 200	2×: the worst case, a full allowance each side of the boundary
Sliding log	100 + 0 = 100	Exact by construction
Sliding counter	100 + 16 = 116	16% over, because the previous minute's traffic was packed at its end, not spread evenly
Token bucket	100 + 33 = 133	Allowed by design: a bucket promises B + R × t, here up to 100 + 1.67 × 60 = 200 in any 60 s

A sliding counter decision, ordinary traffic

Assumptions

Limit: 100 per 60 s
Now: 12:01:20 (20 s into the window)
Previous window (12:00) count: 80
Current window (12:01) count: 30

Working

Share of the previous window still inside the last 60 s(60 − 20) ÷ 600.667from Now
Estimated requests in the last 60 s80 × 0.667 + 3083.3from Previous window (12:00) count, Current window (12:01) count and Share of the previous window still inside the last 60 s
Decision for one more request83.3 + 1 ≤ 100allow; floor(100 − 84.3) = 15 leftfrom Estimated requests in the last 60 s and Limit

What it means

The estimate is only as good as the assumption that the previous window's requests were spread evenly.
On real traffic that assumption holds well: Cloudflare measured 0.003% of 400 million requests wrongly allowed or limited.

A sliding log for login attempts

203.0.113.95Counter state

1 item, Inside the last 60 s, value 12:00:01
1 item, Inside the last 60 s, value 12:00:02
1 item, Inside the last 60 s, value 12:00:03
1 item, Inside the last 60 s, value 12:00:04
1 item, Just appended, value 12:00:05

Inside the last 60 s
Older than 60 s (dropped)
Just appended

Start

As it starts. 3 steps follow.

Rule login-per-ip: 5 attempts per 60 s. The log holds accepted attempts only; a denied attempt is not written, so hammering does not push the retry time back.

GCRA, Free plan: T = 1/R = 100 ms, τ = (B − 1) × T = 1.9 s, 21 requests at t = 0 on a fresh key

Request	TAT before	TAT − now ≤ τ?	Verdict	TAT after
1	0 (fresh)	0 ≤ 1.9	allow	0.1 s
2	0.1 s	0.1 ≤ 1.9	allow	0.2 s
…	…	…	…	…
20	1.9 s	1.9 ≤ 1.9	allow	2.0 s
21	2.0 s	2.0 > 1.9	deny, retry in 2.0 − 1.9 = 0.1 s	2.0 s (unchanged)

Leaky bucket as a queue: NGINX limit_req rate=10r/s burst=20, 25 requests at once

Requests	Default (queue)	With nodelay
#1	Served now	Served now
#2–#21	Queued; released one every 100 ms, the last at 2.0 s	Served now; their 20 burst slots free up at 10/s over 2 s
#22–#25	Rejected (burst full): 503 unless limit_req_status is set	Rejected

Lazy refill, no timers

# integers only: tokens in milli-tokens, time in ms, rate in req/s
def check(b, rate, burst, cost, now_ms):
    if cost > burst:                  # can never fit: not retryable
        raise CostExceedsBurst        # 400, see client-experience
    # catch up on the time since the last request (clamp clock skew)
    elapsed = max(0, now_ms - b.last_refill_ms)
    # R per second = R milli-tokens per ms
    b.tokens_milli = min(burst * 1000, b.tokens_milli + elapsed * rate)
    b.last_refill_ms = now_ms
    need = cost * 1000
    if b.tokens_milli >= need:
        b.tokens_milli -= need
        return Decision(True, remaining=b.tokens_milli // 1000,
                        retry_after_ms=None)
    wait = (need - b.tokens_milli + rate - 1) // rate   # round up
    return Decision(False, remaining=b.tokens_milli // 1000,
                    retry_after_ms=wait)

# integers only: TAT and now in ms, like Gcra.tat_ms
def check(g, rate, burst, cost, now_ms):
    if cost > burst:
        raise CostExceedsBurst
    T = 1000 // rate                  # emission interval: 100 ms at 10/s
    tau = (burst - 1) * T             # how far ahead TAT may run: 1,900 ms
    tat = max(g.tat_ms, now_ms)
    new_tat = tat + cost * T
    if new_tat - now_ms > tau + T:    # would overdraw the burst
        return Decision(False, remaining=0,
                        retry_after_ms=new_tat - tau - T - now_ms)
    g.tat_ms = new_tat
    return Decision(True, remaining=(tau + T - (new_tat - now_ms)) // T,
                    retry_after_ms=None)

Was this section helpful?

Data model.

A rule is configuration; the state is whatever the algorithm has to remember per key.

Rules and state per key

A rule is read-only config; the state is one small record per (rule, key), created on first use and expired when idle.keywordmodelfieldprimitivevalue

// 01 · Rule

type Rule = {

id: string // e.g. free-global

match: { plan?, route?, identity: api_key | ip | user }

algorithm: Algorithm

rate_per_s?: int // token_bucket, gcra, leaky_queue

burst?: int // token_bucket, gcra, leaky_queue

limit?: int // count per window: fixed_window, sliding_log, sliding_counter

window_s?: int // with limit

cost_by_route?: map<route, int>

mode: enforce | shadow

}

type Algorithm =

| "token_bucket" | "gcra"

| "leaky_queue" | "fixed_window"

| "sliding_log" | "sliding_counter"

// State per key, by algorithm

type TokenBucket = {

tokens_milli: int64 // milli-tokens as an integer, no float drift

last_refill_ms: int64

}

type Gcra = {

tat_ms: int64

}

type FixedWindow = {

window_start: int64

count: int32

}

type SlidingLog = {

accepted_at_ms: list<int64>

}

type SlidingCounter = {

window_start: int64

prev_count: int32

curr_count: int32

}

State per key

Algorithm	State per key	Size	Grows with the limit?	Expire after idle
Token bucket	tokens + last refill	16 B	No	B ÷ R (it is full again, same as no entry)
Leaky bucket (meter)	level + last leak	16 B	No	B ÷ R
Leaky bucket (queue)	queued requests	up to B requests	Yes	when drained
Fixed window	counter + window id	8–16 B	No	one window
Sliding log	N timestamps	8 × N B	Yes	one window after the newest entry
Sliding counter	2 counters + window start	24 B	No	two windows
GCRA	one timestamp (TAT)	8 B	No	once TAT has passed

Was this section helpful?

Interface.

Inside the gateway the limiter is a function call, and rules are data.

The limiter's contract

@dataclass
class Decision:
    allowed: bool
    remaining: int            # requests (or cost units) left now
    reset_after_ms: int       # until the key is back to full capacity
    retry_after_ms: int | None  # set only when denied

def check(key: str, rule: Rule, cost: int = 1,
          now_ms: int | None = None) -> Decision: ...

- id: free-global
  match: { plan: free, identity: api_key }
  algorithm: token_bucket
  rate_per_s: 10
  burst: 20
- id: labels-bulk
  match: { route: "POST /v1/labels:batch", identity: api_key }
  algorithm: token_bucket
  rate_per_s: 10
  burst: 20
  cost_by_route: { "POST /v1/labels:batch": 10 }
- id: login-per-ip
  match: { route: "POST /v1/login", identity: ip }
  algorithm: sliding_log
  limit: 5             # window algorithms use limit + window_s,
  window_s: 60         # not rate_per_s + burst

How each algorithm fills the Decision

Algorithm	remaining	retry_after when denied	Precision
Token bucket	floor(tokens)	(cost − tokens) ÷ R	Exact
GCRA	floor((τ + T − (TAT − now)) ÷ T)	TAT − τ − now	Exact
Fixed window	N − count	window end − now	Coarse: a client denied at :01 waits 59 s
Sliding log	N − len(log)	oldest + window − now	Exact
Sliding counter	N − estimate	solve prev × (W − e)/W + curr + cost ≤ N for e	Approximate

What the gateway does with a decision

Code	Outcome	Kind	What happens	Reacts
allow	Admitted	success	Forward to the API; attach remaining and reset to the response.	2Gateway node
deny	Over the limit	error	429 Too Many Requests with a retry time. The headers and body are covered in client-experience.	2Gateway node
shadow-deny	Would have denied	challenge	The rule is in shadow mode: forward anyway and log who it would have hit.	2Gateway node

Was this section helpful?

Optimizations.

Six refinements that decide whether the limiter is cheap, fair and safe to roll out.

Lazy refill, no timers

Arithmetic on read replaces a background drip. Outcome: no per-key timers even at millions of keys, and idle keys cost nothing but their entry.

GCRA for one-number state

The same decisions as a token bucket with half the state and no float to drift: one timestamp per key (the Go library Throttled uses it; brandur.org explains the algorithm). It does need a clock every checker agrees on.

Sub-window buckets

Approximate a sliding window with k small fixed buckets. Figma chose counters each 1/60 of the window over a sliding log: by its own estimate, ~20 MB vs ~2.4 MB for 10,000 users at 500 requests a day. Accuracy improves as k grows.

Weighted costs

Charge by expected work, not by request. GitHub's secondary limit is 900 points a minute, with most GETs costing 1 point and most writes 5. A noisy expensive endpoint cannot hide inside a request count.

Shadow mode first

Count and log, don't enforce: NGINX has limit_req_dry_run, and Stripe dark-launches new limiters. Outcome: you see which merchants a new rule would hit before it hits them.

Pick the reject status deliberately

NGINX limit_req rejects with 503 unless you set limit_req_status 429. See client-experience for why the status matters to clients.

In the wild

System	Algorithm	Note
AWS API Gateway	Token bucket	10,000 req/s with a 5,000-request bucket per account per Region by default (2,500 and 1,250 in some Regions); best effort
NGINX limit_req	Leaky bucket	burst, nodelay and delay= choose between queueing and rejecting; 1 MB of zone holds about 8,000 states on 64-bit, least recently used evicted first
Stripe	Token bucket in Redis	Alongside a concurrency limiter and load shedders
Cloudflare	Sliding window counter	0.003% of 400 million requests wrongly allowed or limited
Figma	Sliding counters in sub-window buckets	Chosen over a sliding log to cut memory

Was this section helpful?

Trade-offs.

There is no single best algorithm; Shiplane uses a different one for each kind of rule. The chosen option is first.

Per-key API rate10/s, burst 20

Token bucket (or GCRA)

Pro:Allows bounded bursts that real integrations need
Pro:O(1) state of 8–16 B
Pro:Retry time is exact

Con:Burst B must be tuned
Con:Two parameters to explain to customers

Fixed window

Up to 2× the limit across a boundary; Denied clients all retry at :00, a herd

Sliding log

Memory grows with N; 1.8 GB for our 2.04M keys at 100/min

Daily and monthly quotasFree 10,000/day

Fixed calendar window

Pro:Matches billing periods
Pro:'Resets at 00:00 UTC' is easy to explain
Pro:One counter per key per day

Con:A client can spend two days' quota around midnight

Sliding counter

No single reset time to print on an invoice or a dashboard

Sliding log

Pro:N is 5, so 40 B of timestamps per IP
Pro:Exact; no edge burst for an attacker to exploit

Con:Needs a bounded map; spoofed IPs can flood it

Token bucket

A full bucket plus refill lets more than 5 through in some 60 s span

Reject or delay the excess

Reject (police)

Pro:No held connections
Pro:Clients learn their limit at once and can back off

Con:Clients must handle 429s

Delay (shape, leaky queue)

Holds a connection per queued request; Hides overload behind latency

What goes wrong

Failure	Impact	Detection	Mitigation	Meanwhile
The node's clock steps backwards (NTP correction)4Limiter engine	Negative elapsed time drains tokens or corrupts TAT	elapsed < 0 counter	Clamp elapsed to 0; use a monotonic clock for durations	A few requests see a slightly stingier limit
Floating-point tokens drift5Counter state	Limits off by a request at the edge; tests disagree across platforms	Property tests over long runs	Store integer milli-tokens
Key explosion from spoofed or rotating IPs5Counter state	Memory grows until the node is killed	Entry count and memory alarms	Bound the map and evict least recently used entries, as NGINX does when its zone fills	An evicted key starts again with a full allowance
Retries herd at the window boundary1API clients	A spike of load at every :00 with fixed windows	Per-second request histogram	Prefer buckets for rates; spread retries with jitter (client-experience)

Was this section helpful?

Builds on this

Limits across many servers