Rate Limiting as a Contract: Token Bucket, Sliding Window, and What to Put in Your Headers

TL;DR: Rate limiting is not a defensive afterthought bolted onto an API gateway — it's a contract you're making with every client that consumes your service. The algorithm you pick (token bucket, sliding window, or GCRA) determines how bursty traffic is allowed to be; the headers you return determine whether clients can behave well or are forced to guess. Get both right and clients self-regulate. Get either wrong and you'll spend your on-call rotation fielding "your API randomly 429s us" tickets.

Most teams treat rate limiting as an infrastructure decision: pick a library, wire it into the gateway, move on. That's backwards. The rate limit is part of your API contract — as load-bearing as your request/response schema — and it deserves the same design rigor. This article covers the three algorithms worth knowing, when each is the right call, the emerging IETF standard for rate-limit headers, and the failure modes that show up once you're running this in production at scale.

Why rate limiting is a contract, not a control

When you rate-limit an API, you're making an implicit promise to every client: "here is how much of this service you can consume, and here is what happens when you exceed it." A vague or inconsistent rate limit breaks that promise in two directions.

First, if your limit is opaque, well-behaved clients can't self-regulate — they either under-use your API out of caution, or they hammer it and get throttled unpredictably. Second, if your limit is inconsistent across endpoints or client tiers without documentation, developers build defensive retry logic around guesswork instead of your actual policy, and that guesswork becomes brittle the moment you change the underlying limit.

The fix is to treat the limit itself as a versioned, documented part of the API surface — expressed in machine-readable response headers, not just a paragraph in your docs. That's the second half of this article. First, the algorithm.

Three algorithms, three different trade-offs

Fixed window

The simplest approach: count requests in fixed time buckets (e.g., per-minute), reset the counter at the boundary. Trivial to implement, cheap to reason about — and it has a well-known boundary bug. A client that sends its full quota at 23:59:59 and again at 00:00:00 effectively gets 2x its intended limit within a two-second window. For anything beyond an internal service or a low-stakes public API, this is rarely the right final answer, but it's a reasonable MVP.

Sliding window (log or counter)

Sliding window log keeps a timestamp per request and counts how many fall within the trailing window — perfectly accurate, but memory cost scales with request volume per key. Sliding window counter approximates this by weighting the previous fixed window's count by how far into the current window you are. It's a good practical middle ground: near-log accuracy, counter-level memory cost (O(1) per key).

Sliding window is the right choice when precision at the boundary matters — payment endpoints, auth endpoints, anything where letting a client sneak in 2x traffic at a window edge is a real abuse vector rather than a curiosity.

Token bucket

A bucket holds up to B tokens (burst capacity); tokens refill at rate R per second; each request costs one token (or more, for weighted operations); an empty bucket means a 429. Token bucket's defining property is that it allows controlled bursts — a client that's been idle can spend its full bucket in one burst, then has to wait for refill. This maps well onto real client behavior: a mobile app that syncs on foreground, a batch job that wakes up hourly.

Stripe, GitHub, and Shopify all use token-bucket-family algorithms in production, generally implemented via Redis for distributed consistency. GitHub's public writeup on scaling their API rate limiter and Stripe's "Scaling your API with rate limiters" post are both worth reading end to end if you're building this from scratch — they cover distributed-state failure modes this article only has room to summarize below.

GCRA: the algorithm underneath a good token bucket

The Generic Cell Rate Algorithm (GCRA), originally from ATM network traffic shaping, is how most production-grade token-bucket implementations are actually built. Instead of storing a token count and running a background refill process, GCRA stores a single value per key — the "theoretical arrival time" (TAT) of the next allowed request — and computes admission decisions from simple arithmetic against the current time. No background job, no counter drift, mathematically exact within the model, and cheap to implement atomically in a single Redis Lua script (EVAL) so a read-then-write race under concurrent requests can't let two requests both believe they got the last token.

-- simplified GCRA admission check, single Redis key
local tat = tonumber(redis.call("GET", key) or now)
local new_tat = math.max(tat, now) + emission_interval
if new_tat - now > (emission_interval * burst + emission_interval) then
  return 0 -- reject
else
  redis.call("SET", key, new_tat, "PX", ttl_ms)
  return 1 -- allow
end

If you're choosing an algorithm today: token bucket via GCRA for anything public-facing and burst-tolerant, sliding window counter for anything where boundary precision matters more than burst tolerance, and fixed window only as a quick internal stopgap.

What to put in your headers

This is the part most APIs get wrong even when the algorithm underneath is solid. The IETF's draft-ietf-httpapi-ratelimit-headers (an active Internet-Draft in the HTTPAPI working group, not yet an RFC as of 2026, but already the de facto convergence point after years of every vendor inventing its own X-RateLimit-* variant) defines four fields:

• RateLimit-Limit — the quota for the current window, in quota units.
• RateLimit-Remaining — quota units left in the current window.
• RateLimit-Reset — seconds until the window resets (or a delta-seconds value, per the draft's current semantics).
• RateLimit-Policy — optional, describes the policy itself (useful when a client is subject to more than one limit simultaneously, e.g., per-second burst plus per-day quota).

A response that includes RateLimit-Limit must also include RateLimit-Reset. Critically, the spec is explicit that a positive RateLimit-Remaining is not a guarantee — under concurrent requests from the same client, two requests can both see "remaining: 1" and both get admitted or both get rejected, depending on your consistency model. Don't let client-side documentation imply a stronger guarantee than your backend actually provides.

For the actual rejection, return 429 Too Many Requests with a Retry-After header (in seconds, per RFC 9110) — this is the one signal well-written HTTP clients already know how to consume for backoff, independent of whether they understand your custom rate-limit headers at all.

HTTP/1.1 429 Too Many Requests
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 34
Retry-After: 34
Content-Type: application/problem+json

{"type": "https://api.example.com/errors/rate-limited",
 "title": "Rate limit exceeded",
 "status": 429,
 "retry_after_seconds": 34}

If you support tiered limits (free/paid, or per-endpoint weighting), consider RateLimit-Policy to make the shape of the limit legible, not just the current count — e.g. RateLimit-Policy: "100;w=60" for 100 requests per 60-second window. Clients that bother to parse it can build genuinely predictive backoff instead of reactive backoff.

Failure modes to design against

Distributed state drift. If your rate limiter runs across multiple gateway instances with a shared Redis backend, a slow or partitioned Redis node means either false negatives (limits not enforced — an abuse vector) or false positives (legitimate clients throttled). Design your fallback behavior explicitly: fail-open (risk abuse) or fail-closed (risk availability) is a decision your team should make on purpose, not discover during an incident.

The thundering herd on reset. If every client's window resets on the same wall-clock boundary (fixed window's classic failure) and clients all retry on Retry-After, you get a synchronized spike at every window edge. Jittered reset times per client key, or a sliding/GCRA approach that doesn't have hard synchronized boundaries, avoids this by construction.

Weighted operations without weighted limits. A GET /users/:id and a POST /reports/generate that triggers a 30-second aggregation job cost your infrastructure wildly different amounts, but a naive "1 request = 1 token" model treats them identically. Weight expensive endpoints higher in your token cost, and say so in RateLimit-Policy or your docs — otherwise clients will rationally batch-call your cheapest endpoints and choke your expensive ones without ever hitting a limit.

Per-key granularity mismatches. Rate limiting by IP breaks for clients behind NAT or corporate proxies (many users share one limit) and is trivially bypassed by anyone with a botnet. Rate limiting by API key or OAuth client ID is the right default for authenticated APIs; IP-based limiting is a reasonable additional layer against unauthenticated abuse, not a substitute.

Multi-region rate limiting

Once your API is deployed across regions, "one counter per client" stops being a single Redis key and becomes a distributed-systems problem in its own right. Two approaches dominate in practice:

Centralized counting. Every region's gateway calls a single global Redis (or Redis Cluster) instance for admission decisions. Simple and exact, but it adds cross-region latency to every request and creates a single point of failure — if the counting service in us-east is unreachable from eu-west, you're back to the fail-open/fail-closed decision from the failure-modes section above, except now it's triggered by network partitions rather than local overload.

Local counting with periodic reconciliation. Each region enforces a local budget (e.g., global limit ÷ number of active regions, or a dynamically rebalanced share based on recent traffic), and regions periodically sync aggregate counts. This trades strict accuracy for latency and availability — a client could theoretically get up to N × per-region-limit requests through if it hits all N regions simultaneously within a reconciliation window, but for most APIs that slack is an acceptable price for not adding a cross-region round-trip to every request.

The choice mirrors the classic CAP-theorem trade-off: centralized counting favors consistency, local counting with reconciliation favors availability and latency. Payment and auth endpoints usually justify the centralized cost; general CRUD endpoints usually don't.

A related pattern worth naming explicitly: if your platform also does event-driven integration — webhook delivery, or CDC pipelines feeding downstream consumers — the same GCRA-style admission logic often gets reused to rate-limit outbound delivery to slow or misbehaving downstream endpoints, not just inbound requests to your own API. The bucket doesn't care which direction the traffic is going.

Client-side backoff: the other half of the contract

A rate limit is only as good as the retry behavior it produces on the client side. A well-designed contract assumes clients will implement exponential backoff with jitter — not because you can enforce it, but because your headers should make the correct behavior the path of least resistance:

import random
import time

def request_with_backoff(fn, max_retries=5):
    for attempt in range(max_retries):
        response = fn()
        if response.status_code != 429:
            return response
        retry_after = int(response.headers.get("Retry-After", 2 ** attempt))
        jitter = random.uniform(0, retry_after * 0.3)
        time.sleep(retry_after + jitter)
    raise RuntimeError("rate limited after max retries")

The jitter matters more than it looks — without it, every client that got rate-limited at the same moment retries at the same moment, recreating the thundering-herd problem from the server side on the client side. Document this expectation in your API docs, and ideally ship it as the default behavior in your official SDKs, since most integrators will copy whatever the SDK does rather than read the fine print.

A decision checklist

Before shipping a rate limit, it's worth confirming:

• Algorithm choice is documented and matches the traffic pattern you actually expect (bursty vs. steady).
• Response headers follow (or at minimum, are compatible with) the IETF draft field names, so client libraries that already understand the convention work out of the box.
• 429 responses include Retry-After regardless of whether custom headers are also present.
• Fail-open vs. fail-closed behavior under backend (Redis) unavailability is an explicit decision, not a default you inherited from a library.
• Expensive endpoints cost more than one unit, and that weighting is visible to clients.
• Reset timing is jittered per key where a synchronized herd is a realistic risk.

Syslabs' engineering team designs and implements API gateways and rate-limiting layers as part of our API integration work — happy to talk through the specifics of your traffic pattern.

Sources: draft-ietf-httpapi-ratelimit-headers, Stripe: Scaling your API with rate limiters, GitHub: How we scaled the GitHub API with a sharded, replicated rate limiter in Redis, Rate Limiting, Cells, and GCRA — brandur.org