Per-User Token Bucket Throttling in FastAPI

Key takeaways:

  • Capacity sets the maximum burst; refill rate sets the sustained rate. They are independent knobs.
  • Refill is computed lazily from elapsed time, so idle buckets cost nothing and no timer is needed.
  • Costing expensive endpoints at several tokens lets one policy govern a whole API.
  • Buckets keyed on the principal isolate users; one client draining its bucket cannot affect another.
  • Refill-and-deduct is a read-modify-write, so it must be atomic or the limit leaks under concurrency.

This guide builds the algorithm behind Rate Limiting and Throttling. It goes a level below the library-based approach, which is worth reading first if you have not chosen an algorithm yet.

The Problem This Solves

Counter-based limits force an unpleasant choice. Set the limit high enough that a legitimate client's burst — a page loading twelve resources, a batch job flushing a queue — is not rejected, and you have set it too high for sustained abuse. Set it low enough to bound sustained load, and normal usage trips it.

A token bucket separates those two concerns. Capacity governs the burst; refill rate governs the average. A client can spend its whole allowance at once and then proceed at the sustained rate, which is what well-behaved clients naturally do anyway.

Why It Happens: The Arithmetic

A bucket is two numbers: a token balance and the time that balance was last correct. There is no timer and no background job. On each request you compute how much time has passed, add that many tokens' worth of refill, cap the result at capacity, and try to deduct the request's cost.

tokens = min(capacity, tokens + elapsed × refill_rate)

This lazy refill is the design's quiet strength. A bucket for a user who has not called in a week is not consuming CPU; it is a stale pair of numbers that becomes correct the instant it is read. Cost therefore scales with traffic, not with the size of your user base — the property that makes the pattern viable for millions of principals.

Two consequences fall out of the formula. The cap means idle time does not accumulate credit indefinitely: a user away for an hour returns with a full bucket, not an hour's worth of tokens. And because refill is continuous rather than stepped, there is no boundary at which a fresh allowance appears, which is precisely the weakness of fixed-window counters.

Bucket level during a burst and the refill that followsThe bucket starts full at five tokens, a burst of five requests drains it to zero, the next request is rejected, and refill at one token per second restores the balance linearly until it is capped at capacity.50tokenscapacity429 hereburst drainsrefill capped at capacity1 token/sectime

Prerequisites

  • An authenticated principal on the request. Keying on anything the client controls defeats the point.
  • For production, an async Redis client with EVAL support.

The Fix

The implementation below is executed, so the numbers in the transcript are the algorithm's real behaviour. Redis is not available in this site's verification environment, so state lives in a dictionary and the clock is a variable the test advances explicitly. Both are visible in the code you are reading; the arithmetic is identical to the Lua version that follows.

CAPACITY = 5.0        # Bucket size: the largest burst allowed from a cold bucket.
REFILL_PER_SEC = 1.0  # Sustained rate once the burst allowance is spent.

# A frozen clock the tests advance by hand. Real code calls time.monotonic().
CLOCK = {"now": 0.0}

BUCKETS: dict[str, tuple[float, float]] = {}   # principal -> (tokens, last_refill_ts)


def consume(principal: str, cost: float) -> tuple[bool, float, float]:
    """Refill by elapsed time, then take `cost` tokens. Returns (allowed, tokens, wait)."""
    now = CLOCK["now"]
    tokens, ts = BUCKETS.get(principal, (CAPACITY, now))
    tokens = min(CAPACITY, tokens + (now - ts) * REFILL_PER_SEC)
    if tokens >= cost:
        BUCKETS[principal] = (tokens - cost, now)
        return True, round(tokens - cost, 3), 0.0
    BUCKETS[principal] = (tokens, now)
    wait = round((cost - tokens) / REFILL_PER_SEC, 3)
    return False, round(tokens, 3), wait


def throttle(cost: float = 1.0):
    async def _dep(x_user: str = Header(default="anon")) -> None:
        allowed, tokens, wait = consume(x_user, cost)
        if not allowed:
            raise HTTPException(
                status_code=429,
                detail={"tokens_left": tokens, "retry_after_seconds": wait, "cost": cost},
            )
    return _dep


@app.get("/search", dependencies=[Depends(throttle(cost=1.0))])
async def search() -> dict[str, str]:
    return {"ok": "search"}


@app.post("/export", dependencies=[Depends(throttle(cost=3.0))])
async def export() -> dict[str, str]:
    """An expensive endpoint charges three tokens instead of one."""
    return {"ok": "export"}

Driving it with real requests — six from Alice, one from Bob, then two clock advances — gives this:

$ GET /selftest
200 OK
{
  "steps": [
    {
      "step": "alice #1",
      "user": "alice",
      "status": 200,
      "body": {
        "ok": "search"
      }
    },
    {
      "step": "alice #2",
      "user": "alice",
      "status": 200,
      "body": {
        "ok": "search"
      }
    },
    {
      "step": "alice #3",
      "user": "alice",
      "status": 200,
      "body": {
        "ok": "search"
      }
    },
    {
      "step": "alice #4",
      "user": "alice",
      "status": 200,
      "body": {
        "ok": "search"
      }
    },
    {
      "step": "alice #5",
      "user": "alice",
      "status": 200,
      "body": {
        "ok": "search"
      }
    },
    {
      "step": "alice #6",
      "user": "alice",
      "status": 429,
      "body": {
        "detail": {
          "tokens_left": 0.0,
          "retry_after_seconds": 1.0,
          "cost": 1.0
        }
      }
    },
    {
      "step": "bob first",
      "user": "bob",
      "status": 200,
      "body": {
        "ok": "search"
      }
    },
    {
      "step": "alice after +2s",
      "user": "alice",
      "status": 200,
      "body": {
        "ok": "search"
      }
    },
    {
      "step": "alice export",
      "user": "alice",
      "status": 429,
      "body": {
        "detail": {
          "tokens_left": 1.0,
          "retry_after_seconds": 2.0,
          "cost": 3.0
        }
      }
    }
  ],
  "final_state": {
    "now": 12.0,
    "buckets": {
      "alice": {
        "tokens": 1.0,
        "ts": 2.0
      },
      "bob": {
        "tokens": 4.0,
        "ts": 0.0
      }
    }
  }
}

What the numbers show

The burst is absorbed, then the rate binds. Alice's first five requests pass with no delay — that is capacity — and the sixth is refused with retry_after_seconds: 1.0, computed from the deficit and the refill rate rather than guessed. This is the field that makes a 429 actionable, and a token bucket can always produce it exactly.

Bob is unaffected. Alice exhausted her bucket entirely; Bob's next request succeeds against his own full one. That isolation is the reason to key per principal rather than per IP, where users behind one corporate NAT would share a limit and interfere with each other.

Cost weighting reuses one policy. After two seconds Alice has earned two tokens and spends one on a search. Her /export call, priced at three, is refused with tokens_left: 1.0. One bucket per user now governs cheap and expensive endpoints alike, which is far easier to reason about than a separate limit per route.

The stored state looks stale, and that is correct. At now: 12.0, Alice's bucket still reads tokens: 1.0, ts: 2.0. Ten seconds of refill have not been written anywhere, because nothing has read the bucket since. The stored pair is not the current balance; it is the balance as of ts. Anyone building a dashboard from raw bucket state has to apply the same refill formula, or every idle user will appear throttled.

Notice also that Bob's ts is still 0.0 while Alice's advanced — timestamps move only on access, which is exactly what makes lazy refill cheap.

Making It Atomic

The in-process version above is safe because the event loop does not interrupt consume. Across four Uvicorn workers and shared Redis, it is not: two workers can both read one token, both decide to allow, and both write back zero. The limit leaks by exactly the number of workers under concurrency, and it leaks most precisely when a client is hammering you.

The fix is to move the whole read-modify-write into Redis as a script, where it executes without interleaving:

-- token_bucket.lua: KEYS[1]=bucket  ARGV: capacity, refill_per_sec, cost
local now = redis.call('TIME')                 -- One clock, Redis's own: no host drift.
local t = tonumber(now[1]) + tonumber(now[2]) / 1000000
local data = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local capacity = tonumber(ARGV[1])
local tokens = tonumber(data[1]) or capacity
local ts = tonumber(data[2]) or t
tokens = math.min(capacity, tokens + (t - ts) * tonumber(ARGV[2]))
local cost = tonumber(ARGV[3])
local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', t)
-- Expire well past a full refill so idle buckets are reclaimed, not resurrected empty.
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / tonumber(ARGV[2])) * 2)
return { allowed, tostring(tokens) }

Reading TIME inside the script rather than passing a timestamp from Python removes the second correctness problem: with several application hosts, each sending its own clock, a host running a few seconds fast hands its users free tokens. One clock inside Redis makes that impossible.

The EXPIRE deserves a note. It must exceed the time to refill from empty to full, or a bucket can be evicted mid-refill and recreated at capacity — turning eviction into a way to reset the limit. Twice the full-refill time is a safe default.

Verification

Test the properties, not one path through them:

def test_burst_then_sustained_rate(client, clock):
    ok = sum(client.get("/search", headers=ALICE).status_code == 200 for _ in range(5))
    assert ok == 5                                              # Capacity absorbed the burst.
    assert client.get("/search", headers=ALICE).status_code == 429

    clock.advance(3)
    ok = sum(client.get("/search", headers=ALICE).status_code == 200 for _ in range(3))
    assert ok == 3                                              # Exactly the refill, not more.
    assert client.get("/search", headers=ALICE).status_code == 429


def test_buckets_are_isolated(client):
    for _ in range(5):
        client.get("/search", headers=ALICE)
    assert client.get("/search", headers=BOB).status_code == 200

An injectable clock is what makes these tests fast and deterministic; a test that calls time.sleep(3) to observe refill is a test people eventually delete. For the Redis version, the test worth writing fires many concurrent requests at one bucket and asserts the total admitted equals capacity exactly — that assertion fails against a non-atomic implementation and passes against the script.

Trade-offs and When Not To

Bursts reach your dependencies. Capacity of 20 means a cold client can hit the database twenty times before any limiting occurs. The bucket protects your average, not your instantaneous concurrency; if a downstream service has a hard concurrency ceiling, you want a semaphore or a queue as well.

Two knobs are harder to explain. "100 requests per minute" fits in API documentation. "Capacity 20, refilling at 1.67 per second" does not, and support will field questions about it. Publish the sustained rate and mention the burst allowance rather than the raw parameters.

A script is operational surface. Lua in Redis means a deployment artifact that lives outside your codebase's normal review path, needs SCRIPT LOAD handling for reconnects, and is awkward to debug. If a library's fixed window is adequate for your traffic shape, that simplicity is worth real money.

Cost weighting can be gamed backwards. If your cheap endpoint is expensive to you and you have priced it at one token, attackers will find it. Price by what the request actually costs your infrastructure, not by how it looks in the API.

FAQ

Why use a token bucket instead of a fixed window? A token bucket allows a burst up to its capacity while still enforcing a steady average through refill, which matches how real clients behave: mostly quiet with occasional spikes. It also has no window boundary, so it does not admit double the limit at a reset the way a fixed-window counter does.

Do I need a background job to refill the buckets? No, and you should not have one. Refill is computed lazily from the elapsed time whenever the bucket is read, so a bucket nobody touches costs nothing. A timer that walks every bucket would scale with your user count instead of with your traffic.

Why must the refill-and-consume step be atomic? It is a read-modify-write. If two requests interleave between reading the balance and writing it back, both can see the same last token and both spend it. Running the whole operation as one Redis Lua script closes that window, which is the main reason to use a script rather than several client calls.

How should I choose capacity and refill rate? Set the refill rate from the sustained throughput you can actually serve, then set capacity from the largest burst you are willing to absorb, typically a few seconds' worth of refill. Capacity that is large relative to the rate is forgiving to clients but lets a cold bucket hit a downstream service hard.

What clock should the bucket use? One clock, on the server side. Pass a timestamp from a single source, or better, read Redis TIME inside the script. Letting each application host use its own clock means drift between them shows up as buckets that refill too fast or reset themselves.