API Rate Limiting: Algorithms and a Tested Token Bucket

API rate limiting decides whether work may be admitted within a defined allowance. A good design names the subject, unit, time behavior and enforcement scope. “One hundred requests per minute” is incomplete without saying whether the count applies to a user, tenant, IP, route or the entire service.

This guide includes an executable process-local Python token bucket. Its tests cover refill and concurrent callers. It is not a distributed quota service or a financial ledger, and those limitations are central to using it correctly.

Separate rate, concurrency and budget#

Rate limits control how quickly work is accepted. Concurrency limits control how much work is active at once. Financial budgets control accumulated spend. Input/output bounds limit work size. An AI service often needs all four.

For example, two requests per second may still exhaust capacity if every request runs for a minute. A per-request token cap may still permit excessive monthly spending. A spending cap may be too slow to protect a saturated worker. Assign each control a clear purpose.

Use authenticated identities for customer allowances. IP-based controls can help protect an edge, but shared networks and rotating addresses make them an imperfect substitute for account policy. Do not trust an arbitrary forwarded header without a reviewed proxy boundary.

Compare common algorithms#

Select based on product behavior, not algorithm fashion. A bursty interactive app may need a small burst allowance and a strict active-work cap. A background importer may need controlled queueing. Document whether rejected requests consume allowance.

The token-bucket rule#

Maintain current tokens and the last update time. On each decision, add elapsed time multiplied by refill rate, capped at capacity. If at least one token remains, consume it and admit the request. Otherwise reject it.

Use a monotonic clock for elapsed time inside a process. Wall-clock adjustments should not create or destroy allowance. The update and consume decision must be atomic relative to other callers.

from math import isfinite
from threading import Lock
from time import monotonic
 
class TokenBucket:
    def __init__(self, capacity, refill_per_second, clock=monotonic):
        if not all(isfinite(x) and x > 0 for x in (capacity, refill_per_second)):
            raise ValueError("positive finite limits required")
        self.capacity, self.rate, self.clock = capacity, refill_per_second, clock
        self.tokens, self.updated = float(capacity), clock()
        self.lock = Lock()
 
    def allow(self):
        with self.lock:
            now = self.clock()
            self.tokens = min(self.capacity, self.tokens + max(0, now - self.updated) * self.rate)
            self.updated = max(now, self.updated)
            if self.tokens < 1:
                return False
            self.tokens -= 1
            return True

The complete example source and tests use the same implementation. The lock protects one process. An application restart creates a new full bucket, and multiple workers each have their own allowance.

Read the behavior with a fake clock#

Imagine capacity three and refill two tokens per second. Three immediate calls succeed; a fourth fails. After a quarter-second, only half a token has accumulated, so another call still fails. After another quarter-second, one request can be admitted. A long idle interval refills only to capacity, never to an unlimited stored credit.

Those cases are covered by deterministic tests rather than sleeps. Another test submits one hundred concurrent attempts to a frozen-clock bucket with capacity seven and asserts exactly seven successes. Invalid zero or non-finite limits are rejected.

Run the isolated tests after installing the example's pinned dependencies:

cd examples/blog/infrastructure
.venv/bin/python -m pytest -q test_controls.py

Four control tests passed with Python 3.14.4 and pytest 9.2.0 on 9 November 2026. This result validates the local implementation's tested cases, not every possible distributed execution or a production capacity benchmark.

Distributed enforcement needs an atomic state transition#

Sharing a counter store is not sufficient if workers independently read, calculate and write. Concurrent decisions can overwrite one another. Use a storage mechanism that can atomically validate and update the allowance under the required consistency model.

Define key scope, expiration, clock authority and behavior during store failure. Decide whether the system rejects, permits a restricted local allowance or uses another reviewed policy. The correct failure mode depends on the protected resource; a financial spending boundary may need stricter behavior than a low-risk anonymous read route.

If you allocate local capacity to replicas, account for the sum and for stale allocations. Do not claim an exact global limit from independent full-sized local buckets. Document tolerated overshoot if the design is intentionally approximate.

Charge the appropriate work unit#

A request count treats a tiny classification and a long document analysis equally. For AI services, consider separate input-size, output and cost policies. Pre-admission estimates can reserve a maximum allowance; actual usage reconciliation then releases or charges the difference according to the product contract.

That reservation must be durable if it represents money or contractual entitlement. A token bucket held in memory cannot prevent double spending across retries, workers and restarts. Keep logical request IDs and attempt IDs separate so retries do not silently corrupt the ledger.

For model pricing and usage categories, see inference cost analysis. Do not multiply provider-reported units by an assumed universal token price.

Return a usable rejection#

HTTP 429 represents too many requests; the standard permits a Retry-After header. Choose a delay consistent with your policy and avoid exposing unnecessary internal details. RFC 6585.

Clients should respect the service's retry contract and their overall deadline. Bound retries and add appropriate backoff rather than immediately resubmitting an entire burst. A rejected local request should not call the expensive provider first.

The FastAPI gateway tests exactly that ordering for its local allowance. Its shared bucket is intentionally simple; do not describe it as per-user enforcement.

Operate and test the policy#

Track admitted and rejected counts by stable route and policy class. Avoid raw credentials or unbounded user IDs as metric labels. Observe queue delay, active work and upstream errors so rate rejection is not confused with provider failure.

Test window boundaries, concurrency, clock behavior, restart, multiple replicas and store outages. Include noisy-neighbor scenarios and permission changes. A policy should protect legitimate users from overload without silently turning a shared tenant into a single-user quota.

Start with an explicit admission specification, prove the local decision behavior, then choose the distributed state model your product needs. The algorithm is only one part of a reliable limit.