Module P-18·36 min read

Token bucket, leaky bucket, and sliding window log vs counter — implemented as distributed counters in Redis, with the per-tenant limits P-8 needs.

JJS
Written by Jatin Jain Saraf · Senior Software Engineer

Module P-18 — Rate Limiting and Quotas

What this module covers: Rate limiting as admission control — converting overload into a cheap, explicit, immediate rejection instead of an expensive collapse. The four algorithms and what each one actually permits: fixed window and its boundary burst, sliding window log and its memory bill, sliding window counter as the working compromise, and token bucket as the only one that expresses "sustained rate plus a burst allowance." Where the counter lives, and why a per-instance counter silently multiplies your limit by your fleet size. Correct Redis implementations, in one round trip, and the INCR-without-EXPIRE bug that produces a permanent lockout. What to key on, and why X-Forwarded-For is attacker-controlled until you know your proxy depth. Why request count is a poor proxy for cost, and when a concurrency limit is the right control instead. Quotas as a billing construct with different storage requirements. And the response contract — 429, Retry-After, and why publishing your limits reduces the load on you.


A Limiter Exists to Make Rejection Cheaper Than Collapse

Start with what happens without one. Your service can serve 4,000 requests per second before latency leaves its SLO. At 6,000 it does not serve 4,000 and reject 2,000 — it accepts all 6,000, queues them, and every request gets slower. Queues grow, p99 crosses client timeouts, clients retry, offered load rises to 9,000, and you have Module A-6's retry storm feeding on a service that is now doing more work than it did at the start while completing less of it. Throughput past the knee of the curve does not plateau, it declines.

A rate limiter is the decision to spend one cheap operation — a counter increment and a comparison — to refuse work you cannot do, so that the work you accept still completes inside its budget. Four distinct motives lead teams here, and they want different designs:

MotiveWhat you are protectingNatural keyNatural limit
Capacity protectionyour own latency SLOglobal, or per-endpointderived from measured capacity
Fairnessone tenant's share of shared capacitytenant / API keyproportional to plan
Cost controlyour bill (Module O-8)tenant, weighted by costbudget ÷ unit cost
Abuse preventioncredential stuffing, scraping, enumerationIP, account, endpointdeliberately tight

Conflating them is the usual design error. A limit tuned to stop credential stuffing on /login (five attempts per account per fifteen minutes) applied to /api/orders is absurd; a limit sized for fairness across tenants does nothing about a single tenant whose plan legitimately allows enough traffic to saturate you. Most mature systems run several limiters at different scopes simultaneously, which is the multi-tier section below.

One boundary to draw immediately, because it is the most common category error in this area: rate limiting is not load shedding. A limiter enforces a policy — a number you decided in advance, usually contractual and published. Load shedding (Module A-8) reacts to your current state — queue depth, latency, saturation — and drops work you nominally promised to accept because accepting it would make things worse. You need both. A limiter with a limit set above your real capacity protects nothing; a shedder without a limiter has no way to distinguish the tenant who is inside their contract from the one who is not.

Analogy: a nightclub with a door policy. The capacity sign is load shedding: when the room is full, nobody else comes in regardless of who they are. The guest list with plus-ones is rate limiting: each named guest may bring a set number of people, decided before the evening, whether or not the room is busy. The bouncer turning someone away in two seconds is the cheap rejection — the alternative is letting everyone in until nobody can reach the bar, at which point the people already inside leave.


Four Algorithms, and What Each One Actually Permits

The algorithm choice is not academic: each one permits a different traffic shape at the same nominal limit, and the difference shows up as an incident.

Fixed window counter

Divide time into aligned windows — every minute on the minute — keep a counter per key per window, reject when it exceeds the limit.

text

Cheap — one integer per key — and simple to reason about, which is why it is everywhere. Its flaw is structural: a client that sends its full allowance at the end of one window and again at the start of the next delivers twice the limit in a short interval, and nothing in the algorithm is violated. If your limit was derived from real capacity, you have just admitted 2× capacity, and it recurs on a clock so your incident has a suspiciously regular shape.

There is a second, quieter problem: aligned windows synchronise clients. Every well-behaved client that got a 429 waits for the top of the minute, so they all resume in the same 50 ms. This is Module P-12's thundering herd generated by your own limiter.

Sliding window log

Store a timestamp per request. To decide, drop entries older than the window and count what remains.

ts

Perfectly accurate with no boundary artefact. The cost is memory proportional to the limit, per key: a 10,000-per-hour limit across 50,000 API keys is 500 million stored timestamps, and each is a sorted-set member with overhead, not an 8-byte integer. It also does more work per request than any other option. Use it where the limit is small and precision matters — login attempts, password resets, expensive report generation — and never for a high-volume general API limit.

Sliding window counter

Keep two fixed-window counters and interpolate: weight the previous window by how much of it still falls inside the sliding window.

text

Two integers per key, no clock-aligned doubling, and an error bounded by the assumption that the previous window's traffic was evenly distributed within it — which it was not, so the estimate can be wrong in either direction by a modest amount. This is the right default for a general-purpose API limit: it costs almost what fixed window costs and removes fixed window's actual failure mode. The trade is that it is approximate, so it cannot be the mechanism behind a contractual "exactly 10,000 per hour" claim.

Token bucket

A bucket of capacity B refills at R tokens per second. Each request takes one token (or several — see cost weighting); an empty bucket means rejection.

ts

Token bucket is the only one of the four that separates two things every real API needs to state separately: sustained rate (R) and burst allowance (B). A client that is idle for a minute can spend its accumulated tokens at once, which is usually what you want — a page load firing twelve parallel API calls is normal behaviour that a strict per-second limiter punishes for no reason. And it yields an exact Retry-After, because you can compute precisely when the next token arrives.

Its cost is that burst is real: B requests can arrive in a millisecond, so your capacity planning must survive B, not R. Choosing B far above R is how teams accidentally re-create the fixed-window doubling with extra steps.

Leaky bucket deserves a note, because the name is used for two different things. As a policing algorithm it is token bucket's mirror image and behaves equivalently. As a queue — requests enter a buffer and drain at a fixed rate — it is a traffic shaper rather than a limiter: excess requests wait instead of failing. Shaping is right for outbound traffic you control (your webhook delivery workers respecting a partner's limit, Module P-17) and wrong for inbound HTTP, where making a client wait converts your limiter into the latency problem it existed to prevent.

Memory/keyBoundary burstAccuracyExpresses burst?Exact Retry-After
Fixed window1 integer2× limitexact within windownowindow end only
Sliding logO(limit)noneexactnoyes
Sliding counter2 integersnoneapproximatenoapproximate
Token bucket2 numbersbounded by Bexactyesyes

Default to token bucket for API limits where you want to be generous about bursts and strict about sustained rate, sliding window counter where you want a simple published number, and sliding log only for small, security-sensitive limits.


A Per-Instance Counter Multiplies Your Limit by Your Fleet Size

This is the design decision that matters more than the algorithm, and it is frequently made by accident — by installing a middleware whose default store is in-process memory.

Run 40 instances behind a load balancer with a 100-per-minute in-memory limiter and your actual limit is somewhere between 100 and 4,000 per minute, depending on how the load balancer distributes that client's requests. Round-robin makes it nearly 4,000. It gets worse: the effective limit now changes when you autoscale, so the same client is throttled differently at 3 a.m. and at peak, and your limit is a function of your deployment rather than of your policy.

Where the counter livesAccuracyLatency addedFailure couplingWhen it is right
In-process memorylimit × instancesnonenonesingle instance; or a deliberate per-instance concurrency cap
Central Redisexactone round trip (~0.5 ms same-AZ)limiter depends on Redisthe default for a fleet
Local counters, async aggregationapproximate, convergesnone on the request pathnonevery high volume where approximation is acceptable
Edge / CDN / gatewayexact per PoP, approximate globallynone to your originnoneabuse prevention; cheapest rejection possible

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

Sign in & Register

Discussion

0

Join the discussion

Loading comments...

© 2026 Jatin Jain Saraf (JJS). All rights reserved.