Rate limiting an API gateway

One tenant's SDK is misconfigured. It retries every 429 after a flat one second, forever, no jitter, no cap. Your edge is now serving 36,000 rejections a minute for that tenant alone, and someone asks in the incident channel whether moving the gateway from a token bucket to a sliding window would calm it down.

It won't. I simulated four limiters against exactly that client, and the rejection count moves by less than 1% between them. What moves — by a factor of nearly four — is which requests get served.

Four limiters, one allow() each

Every algorithm here answers one question: can this request go through right now. They differ in when spent capacity comes back.

RATE = 10.0    # requests per second, nominal, identical for every limiter
WINDOW = 1.0   # seconds
LIMIT = int(RATE * WINDOW)

class TokenBucket:
    def __init__(self):
        self.tokens, self.last = float(LIMIT), 0.0

    def allow(self, t):
        self.tokens = min(float(LIMIT), self.tokens + (t - self.last) * RATE)
        self.last = t
        if self.tokens >= 1.0:
            self.tokens -= 1.0
            return True
        return False

class FixedWindow:
    def __init__(self):
        self.window, self.count = 0, 0

    def allow(self, t):
        w = int(t // WINDOW)
        if w != self.window:
            self.window, self.count = w, 0
        if self.count < LIMIT:
            self.count += 1
            return True
        return False

class SlidingWindowCounter:
    """The previous window's count decays as the current one fills."""
    def __init__(self):
        self.window, self.count, self.prev = 0, 0, 0

    def allow(self, t):
        w = int(t // WINDOW)
        if w != self.window:
            self.prev = self.count if w == self.window + 1 else 0
            self.window, self.count = w, 0
        elapsed = (t % WINDOW) / WINDOW
        if self.prev * (1.0 - elapsed) + self.count < LIMIT:
            self.count += 1
            return True
        return False

class SlidingWindowLog:
    """Exact count over the trailing window."""
    def __init__(self, count_all=False):
        self.log, self.count_all = [], count_all

    def allow(self, t):
        while self.log and self.log[0] <= t - WINDOW:
            self.log.pop(0)
        ok = len(self.log) < LIMIT
        if ok or self.count_all:     # count_all=True is the bug in section six
            self.log.append(t)
        return ok

The token bucket hands capacity back continuously — at 10 req/s, one token every 100 ms, whether or not anyone is asking. The fixed window hands all ten back at once, on the boundary. The sliding counter releases capacity continuously too, but it releases an estimate: it assumes the previous window's hits were spread evenly across it, which they almost never are. The log releases each slot exactly one window after that slot was spent, which means capacity comes back in the same clumps it left in.

That last property is the one that does the damage.

The simulation

Fifty clients share a single 10 req/s limit key. Jobs arrive per client as a Poisson process summing to 30 req/s — three times the limit, so two-thirds of the offered load cannot be served no matter what. Each job retries until it gets a 200 or the 60-second measurement window closes. Every figure below is the mean of 20 seeds.

Two retry policies. The bad one waits a flat 1.0 s after each 429 and ignores Retry-After. The good one uses full jitter as the AWS SDKs implement it in standard retry mode — delay = random(0,1) × min(20000 ms, 1000 ms × 2^attempt), with the 1-second base delay AWS applies to throttling errors specifically, not the 50 ms it uses for timeouts (AWS SDK retry behavior).

The model is deliberately small, and it leaves out plenty. One node, one key, no Redis round-trip, no clock skew, no counter sync lag, no notion of a request costing more than one slot, and no client that ever gives up. Two numbers in the output are artifacts rather than findings: the 66–67% "unfinished" share is the 3× overload by construction, and the token bucket's 10.15 req/s goodput against everyone else's 10.00 is its initial full bucket of ten tokens amortised over 60 seconds. Jain fairness across the fifty clients stayed between 0.918 and 0.927 for every correct limiter, so nothing below is about one client beating another. It is about new requests versus old ones.

The retry policy sets the 429 volume, and the algorithm does not

Amplification here is total requests divided by accepted requests — how many times the edge had to say something for each request it actually served.

The spread across algorithms is 3%. The spread between retry policies is 3.7×, and it is the same 3.7× whichever limiter you run. This follows from the arithmetic once you see it: at steady state under sustained overload, the rejection count is set by how often the client comes back, and the limiter has no vote in that. A token bucket rejecting you at 10:00:00.000 and a sliding log rejecting you at the same instant have produced the same 429, and your SDK's timer does the rest.

So the ticket that says "switch the gateway to a sliding window, the retries are killing us" is asking the wrong component to change. The 36,000 rejections stay. The gateway is cheap to reject from — it is the client's timer that decides how many times it has to.

The algorithms decide who gets served

Under the flat 1-second retry, with goodput held at 10 req/s across the board:

Burstiness is the coefficient of variation of admitted requests per 200 ms bucket; 0.2 is close to a steady drip, 1.4 is spiky.

Read the first column as a fairness property that has nothing to do with clients and everything to do with request age. Under the token bucket, a request that has never been tried before wins 55% of the served slots. Under the sliding window log, it wins 15%. Same limit, same offered load, same rejections — a request arriving fresh at the log-based limiter is a little over a quarter as likely to be one of the ten per second that make it.

The mechanism is the clumping. The log frees slots at exactly the timestamps where slots were spent a window ago, and those timestamps were themselves clustered, so capacity arrives in lumps. Retry traffic is dense — 62 attempts for every acceptance — and fresh arrivals are sparse at 30 per second, so whoever is already hammering absorbs each lump before a new request shows up. Then those acceptances schedule the next lump, and the pattern feeds itself. The token bucket refuses to clump: at 100 ms per token there is no lump to absorb, and the dry spells between tokens are short enough that arrival timing stops mattering.

The sliding window counter, which is the approximation most gateways actually ship, behaves like the token bucket here rather than like the log it is named after. Its 53% and 0.17 track the bucket's 55% and 0.21 closely, because a decaying estimate releases capacity smoothly even though the thing it is estimating did not arrive smoothly.

The p95 column is the same story measured from the client's side. A request that needs 39 seconds to get through a log-based limiter is one that got passed over by four hundred-odd admitted requests in the meantime, most of them retries of work that arrived after it did.

Now switch the client to full jitter and the algorithms stop differing:

Four points of spread on first-try acceptance, two seconds on p95. Jitter spreads retry traffic thinly enough that no lump of freed capacity gets absorbed before a fresh request can reach it, which erases the property that separated these limiters in the first place. It is not free: p95 completion goes up for three of the four, because a client that backs off to 8 or 16 seconds is not there when its slot opens. You are trading tail latency on individual requests for a 3.7× cut in wasted work, and once you have made that trade the choice of algorithm stops paying.

Fixed windows resonate with the client's retry period

The fixed window's 84% first-try rate in that table looks like a win. It is an accident of the retry period landing on the window size. Sweeping the client's flat retry interval against a fixed 1.0 s window, first-try acceptance goes:

The fixed window swings between 12% and 85% depending on a number you do not control and cannot see. When the retry period divides the window evenly, retriers land on the boundary in lockstep and take the entire quota in the first milliseconds; when it does not, they are spread across the window and fresh arrivals compete on equal terms. The token bucket and the sliding counter vary by four points across the same sweep. Their falloff at 0.25 s is mechanical — a client retrying four times a second generates more retry traffic per job, so first attempts are a smaller share of everything — and it affects all the limiters alike.

A limiter whose behaviour depends on the phase relationship between your window boundary and a third party's retry timer is a limiter you cannot reason about during an incident.

Counting rejected requests eats the limiter

The log-based limiter has a failure mode that dwarfs everything above. The common Redis implementation is: append this request's timestamp to a sorted set, trim entries older than the window, count what's left, reject if the count exceeds the limit. Written in that order, the limiter counts requests it rejected.

# wrong: the attempt is recorded before it is judged
pipe.zadd(key, {req_id: now})
pipe.zremrangebyscore(key, 0, now - WINDOW)
count = pipe.zcard(key)
return count <= LIMIT

Under a client that retries on rejection, this self-locks. Every rejected attempt keeps the window full for another full window, which guarantees the next attempt is rejected too, which refills the window again. In the simulation it takes the limiter from 10 req/s to 0.17 req/s — 1.7% of its own configured limit — at a cost of 5,424 requests for every one served, with 99% of jobs never completing.

The client-side fix does not rescue it. Full jitter drops the amplification from 5,424× to 1,245× and leaves goodput at 0.17 req/s, identical to four significant figures. This is the one case in the whole experiment where the algorithm matters more than the client, and it is not a design trade-off — it is an ordering bug. Judge first, record only what you admitted:

pipe.zremrangebyscore(key, 0, now - WINDOW)
count = pipe.zcard(key)                    # count before adding
if count >= LIMIT:
    return False
pipe.zadd(key, {req_id: now})              # record only on success
return True

Do it in a Lua script or a MULTI, since the check and the write have to be atomic against other gateway nodes.

Configuring it on a real gateway

Kong's rate limiting advanced plugin exposes the choice directly. window_type takes fixed or sliding, and sliding is the default; the sliding implementation is the weighted-estimate kind, described in the docs as "taking into account previous hit rates to create a dynamically calculated rate" (Kong plugin docs).

config:
  limit: [10]
  window_size: [1]
  window_type: sliding      # fixed | sliding
  strategy: redis           # local | cluster | redis
  sync_rate: 0.1            # seconds between node syncs; -1 disables

strategy: local keeps counters in each node's memory, which means your effective limit is the configured limit times the node count. With redis or cluster, sync_rate buys accuracy with latency, and anything above zero means nodes are deciding on stale counts.

Envoy's local rate limit filter is a token bucket and names its parameters as such:

token_bucket:
  max_tokens: 10            # burst capacity
  tokens_per_fill: 10
  fill_interval: 1s         # must be >= 50ms

Two defaults in that filter have caught me. filter_enabled and filter_enforced both default to 0% of requests "for safety", so a filter you configured and deployed does nothing until you set those runtime fractions. And local_rate_limit_per_downstream_connection defaults to false, so the bucket is per Envoy process, not per connection or per client (Envoy API reference).

NGINX's limit_req is a leaky bucket, which for admission purposes behaves like a token bucket with the queue exposed:

limit_req_zone $binary_remote_addr zone=one:10m rate=10r/s;
limit_req zone=one burst=10 nodelay;
limit_req_status 429;        # the default is 503

Without nodelay, excess requests are delayed rather than rejected, which turns a rate limit into a latency problem for the client. And limit_req_status defaults to 503, not 429 — every retry library treats those differently, and a 503 reads as "the service is broken" rather than "you are over quota" (NGINX docs).

What you can honestly tell the client

The algorithm decides how good a Retry-After you can compute. A token bucket knows exactly when the next token lands: (1 - tokens) / RATE. A log knows exactly when its oldest entry expires. A sliding counter can only solve for when its estimate drops below the limit, and that estimate is built on an assumption about the previous window's distribution, so the answer is wrong in both directions. A fixed window computes the honest thing — the boundary — and hands every rejected client the same instant to come back at, which is how you get a synchronised stampede on every window edge. That last mechanism is not something my simulation measured; the clients in it ignore Retry-After entirely.

Retry-After is integer seconds, so at 10 req/s your token bucket's true 100 ms wait rounds to 1 s and you have overstated it tenfold. Sub-second quotas and this header do not fit together.

For the machine-readable version, the IETF fields are still a draft — draft-ietf-httpapi-ratelimit-headers, revision 11, May 2026, with an HTTPDIR early review marked "Not ready" in January 2026 (datatracker). The syntax is RateLimit-Policy: "permin";q=50;w=60 for the quota and RateLimit: "default";r=50;t=30 for what's left. Send both if you like, but the draft is explicit that when you send Retry-After as well, "the Retry-After field MUST take precedence." Kong already emits RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset, which are names from an earlier revision of that same draft.

What I did not test

Every number here comes from one node holding one counter with no network in the path. The interesting production question is what sync_rate: 0.1 does to these results — whether counters that are 100 ms stale across eight nodes smear the log's clumping into something closer to the token bucket's drip, or whether each node develops its own local lump and the fresh-request starvation gets worse. I would also want the client arm that actually reads Retry-After, because a fixed window handing identical wait times to thousands of rejected clients is the one failure mode in this piece that I described from the mechanism rather than from a measurement.