Rate Limiter System Design: Token Bucket vs Sliding Window

A rate limiter is a system component that restricts the number of requests a client can make to a service within a defined time window, protecting backend resources from overload and abuse. It sits at the API gateway or application layer and rejects excess requests with an HTTP 429 status code and a Retry-After header. Distributed rate limiters share state — typically in Redis — across multiple application servers so the limit is enforced consistently regardless of which server handles a request.

Rate limiter system design shows up in almost every backend interview and in almost every
production PHP API I’ve shipped, because the moment your API has more than one client, someone will
either abuse it or accidentally hammer it with a retry loop. I’ve watched a single misbehaving cron
job on a client’s Drupal integration push 40,000 requests a minute into an endpoint built for 200
requests a minute, tipping the database connection pool over in under a minute. A rate limiter isn’t
optional at that point — it’s the difference between a degraded endpoint and a full outage. This post
covers the algorithms actually used in production, the exact race condition that breaks naive Redis
implementations, and the PHP code I run in front of API endpoints today.

What Is Rate Limiting and Why Does Every Production API Need It?

Rate limiting is the practice of capping how many requests a client can send to your API in a
given time window, and it exists to protect your infrastructure, not to annoy your users. Without
it, a single client — malicious or just buggy — can exhaust database connections, saturate your
PHP-FPM worker pool, or run up your AWS bill through unbounded Lambda invocations.

In one production incident I traced, a partner’s retry logic had no backoff: every failed request
triggered an immediate retry, turning 300 requests/second into over 4,000 requests/second within 90
seconds during a transient database blip. A rate limiter at the gateway would have returned 429s and
let retries queue instead of compounding. AWS API Gateway enforces this exact pattern by default,
throttling accounts at a baseline of 10,000 requests/second with a burst capacity of 5,000, using
token bucket under the hood.

If your API has more than one consumer, or exposes anything expensive, you need rate limiting
before almost any other resilience pattern.

How Does the Token Bucket Algorithm Work?

Token bucket works by giving each client a bucket that holds a fixed number of tokens, refilling
it at a constant rate, and requiring one token per request — when the bucket is empty, the request is
rejected. This is the algorithm AWS API Gateway and most developer-facing APIs use because it
tolerates bursts gracefully without needing to track individual timestamps.

1. Initialize a bucket with a maximum capacity (e.g., 100 tokens).
2. Refill tokens at a fixed rate (e.g., 10 tokens/second) up to the capacity.
3. On each request, attempt to remove one token.
4. If a token is available, allow the request and decrement the count.
5. If the bucket is empty, reject the request with HTTP 429.

The advantage is real-world flexibility: a client that’s been idle can burst up to 100 requests
instantly, then settle into the steady 10/second refill rate. I use this for public API keys where
occasional bursts are legitimate and shouldn’t be punished like sustained abuse. Token bucket is the
right default whenever burst tolerance matters more than millisecond-precise enforcement.

What Is the Sliding Window Counter Algorithm, and Why Does Cloudflare Use It?

Sliding window counter blends the current window’s request count with a weighted portion of the
previous window’s count, smoothing the boundary-burst problem that plagues fixed window counters
while using only O(1) memory per key. Cloudflare runs this algorithm across its global edge network
at a published 0.003% error rate, making it the reference implementation for accurate, low-memory
rate limiting.

The problem it solves: with a naive fixed window (100 requests per 60 seconds), a client can send
100 requests in the last second of window one and 100 more in the first second of window two — 200
requests in two seconds against a “100 per minute” limit. Sliding window counter weights the previous
window’s count by how much still overlaps the current moment, capping that spike without the memory
cost of storing every timestamp, which sliding window log requires.

Sliding window counter is worth the extra implementation complexity for anything customer-facing
where precise enforcement matters — billing-tied quotas or login attempt limits.

How Do You Build a Distributed Rate Limiter With Redis and PHP?

You build a distributed rate limiter with Redis by storing a counter keyed per client and using
an atomic Lua script so check-and-increment happens as one operation Redis can’t interleave with
other requests. A PHP implementation that calls INCR then EXPIRE as two separate round trips looks
fine in testing and breaks under real concurrency.

$redis = new Redis();
$redis->connect('127.0.0.1', 6379);

$luaScript = <<<'LUA'
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local current = redis.call('INCR', key)
if current == 1 then
    redis.call('EXPIRE', key, window)
end
if current > limit then
    return 0
end
return 1
LUA;

function isAllowed(Redis $redis, string $luaScript, string $clientId, int $limit = 100, int $window = 60): bool {
    $key = "ratelimit:{$clientId}:" . floor(time() / $window);
    $allowed = $redis->eval($luaScript, [$key, $limit, $window], 1);
    return (bool) $allowed;
}

if (!isAllowed($redis, $luaScript, $_SERVER['REMOTE_ADDR'])) {
    http_response_code(429);
    header('Retry-After: 60');
    exit(json_encode(['error' => 'rate_limit_exceeded']));
}

I load this script once with SCRIPT LOAD and call it via EVALSHA in production — a cached SHA1
hash cuts the payload from roughly 400 bytes to 40 bytes per call. Use EVAL/EVALSHA for anything
beyond a single-server setup: MULTI/EXEC can’t branch on a value it just read, so it can’t express
“check the limit, then conditionally increment” atomically.

Why Does Rate Limiting Break Under Concurrent Load, and How Do You Fix It?

Rate limiting breaks under concurrency because of a TOCTOU (time-of-check-to-time-of-use) race:
if you read the counter, compare it to the limit, and write the new value as separate Redis calls,
multiple concurrent requests can all read the same “under limit” value before any writes back,
letting all of them through. I’ve seen this let 6-8x the configured limit slip through during a
traffic spike, because the read-check-write gap widens exactly when concurrency is highest.

The fix is making the entire check-and-increment sequence atomic. Redis guarantees a Lua script
runs to completion with no other command interleaved, so wrapping INCR, the comparison, and EXPIRE
inside one script closes the race window completely — this bug passes every manual test and then
fails in production during your highest-traffic hour. Always push read-check-write logic into a
single atomic Redis operation; never split it across multiple round trips.

How Do You Scale a Rate Limiter to Millions of Requests Per Second?

You scale a rate limiter past a single Redis instance’s ceiling — roughly 50,000-100,000 rate
limit checks per second before it becomes the bottleneck — by sharding keys across a Redis Cluster
and keeping the round trip off the critical path where possible. Raw Redis throughput sustains
100,000-200,000 operations per second, and with pipelining, benchmarks show over 1.5 million SET
operations/second at a p50 latency of roughly 0.4-0.5ms — but rate limiting’s
INCR-plus-EXPIRE-plus-compare pattern doesn’t pipeline as cleanly as bulk SET/GET.

Network latency, not Redis itself, usually kills a rate limiter’s performance budget: one
documented case saw 80ms of network latency between API servers and Redis balloon a 50ms API response
into a 2-second response once rate limiting ran synchronously on every request. Co-locating Redis in
the same availability zone and pooling connections instead of opening one per check eliminates most
of that overhead. Beyond roughly 50,000 checks/second per node, shard by client ID hash across a
Redis Cluster — a well-tuned distributed setup benchmarks at 50,000+ requests/second with sub-2ms
p95 latency per node.

What HTTP Response Should a Rate-Limited Request Return?

A rate-limited request should return HTTP 429 Too Many Requests along with a Retry-After header
telling the client exactly when to try again, plus the informational X-RateLimit-* headers so
well-behaved clients can self-throttle before hitting the wall. Returning a generic 403 or 500
instead of 429 breaks client retry logic that specifically checks for the 429 status code.

The three headers I always include: X-RateLimit-Limit (the window’s ceiling), X-RateLimit-Remaining
(requests left), and X-RateLimit-Reset (a Unix timestamp for when the window resets). Cloudflare’s own
responses follow this exact pattern, and clients built against Stripe, GitHub, or AWS SDKs already
know how to parse it — you get well-behaved backoff for free by matching convention. Always ship
Retry-After alongside 429; it’s a one-line addition that turns a hard failure into an actionable
signal.

Rate limiting algorithm comparison

Algorithm	Performance	Complexity	When to Use
Fixed Window Counter	O(1) memory, fastest to check	Low	Internal services, low-stakes limits where boundary bursts are acceptable
Sliding Window Log	O(n) memory per client, most accurate	High	Low-volume, high-precision limits (e.g., login attempts)
Sliding Window Counter	O(1) memory, 0.003% error rate at Cloudflare scale	Medium	Customer-facing API quotas, billing-tied limits
Token Bucket	O(1) memory, tolerates bursts	Medium	Developer APIs, SDKs, public API keys
Leaky Bucket	O(1) memory, enforces constant output rate	Medium	Traffic shaping to protect a fixed-capacity downstream service

• Cloudflare’s sliding window counter runs globally at a published 0.003% error rate using O(1)
  memory per client key.
• A single Redis instance realistically sustains 50,000-100,000 rate limit checks per second before
  becoming the bottleneck, even though raw throughput reaches 100,000-200,000 ops/second.
• AWS API Gateway throttles accounts using token bucket with a default baseline of 10,000
  requests/second and a burst capacity of 5,000.
• Splitting check-and-increment into separate Redis calls (INCR then EXPIRE) creates a TOCTOU race
  condition that can let 6-8x the configured limit through under concurrent load.
• Redis EVALSHA with a cached SHA1 hash reduces a Lua rate-limit call’s payload from roughly 400
  bytes to about 40 bytes versus sending the full script each time.
• A documented production case showed 80ms of Redis network latency turning a 50ms API response into
  a 2-second response once synchronous rate limiting hit the request path.

Frequently Asked Questions

What is rate limiting and how does it work?

Rate limiting restricts how many requests a client can send to an API within a defined time window, typically enforced by counting requests against a limit stored in a shared store like Redis. When a client exceeds the limit, the server rejects further requests with HTTP 429 until the window resets.

What algorithm does Cloudflare use for rate limiting?

Cloudflare uses the sliding window counter algorithm globally, blending the current window’s request count with a weighted portion of the previous window’s count. This gives O(1) memory usage per client and a published error rate of 0.003%, avoiding the boundary-burst problem of fixed window counters.

Should I use Redis for rate limiting?

Yes — Redis is the standard backend for distributed rate limiting because Lua scripts via EVAL/EVALSHA let multiple application servers share the same counters atomically, without race conditions. A single Redis instance realistically handles 50,000-100,000 rate limit checks per second before you need to shard.

What is the difference between token bucket and sliding window rate limiting?

Token bucket allows bursts by letting clients spend saved-up tokens instantly, then refills at a steady rate — ideal for developer APIs where occasional spikes are normal. Sliding window counter enforces the limit more precisely across time boundaries, better for billing-tied quotas or login attempt limits.

How do you rate limit an API without a database?

You can rate limit in-memory on a single server using a local counter, but it won’t work across multiple servers or survive restarts. For anything beyond a single-instance API, a shared store like Redis is effectively required so all servers see consistent, atomic counters.

Rate limiter system design looks simple until you put it behind real concurrent traffic — the
algorithm choice matters less than most tutorials suggest, and the atomicity of your
check-and-increment logic matters more. I’ve rebuilt the same naive INCR/EXPIRE rate limiter into a
Lua-backed atomic version on three separate client projects, always after the same failure mode: it
worked in staging, then let traffic through during the exact spike it was supposed to stop. Start
with token bucket for burst tolerance, back it with a single atomic Redis Lua script, and return
proper 429s with Retry-After headers — that combination covers most production API traffic patterns.