Rate Limiting Algorithms: Token Bucket vs Sliding Window in Practice

What rate limiting algorithms decide: the shape of traffic you permit

A rate limiter answers one question for every incoming request: admit it now, or not. Behind that yes/no is a policy about shape, meaning how much traffic a client may send, over what interval, and how unevenly. The stated limit, such as "100 requests per minute," is only half the policy. The other half is what happens when a client sends all 100 in the first second.

Teams usually adopt rate limiting for three reasons:

• Protecting capacity. A database, a third-party API with its own quota, or a service with a fixed worker pool has a ceiling. Exceeding it causes queueing, timeouts, and retry storms. A limiter turns that overload into fast, explicit rejections.
• Fairness between tenants. On shared infrastructure, one noisy customer should not consume the latency budget of everyone else. Per-key limits keep each tenant within an agreed share.
• Abuse and cost control. Credential stuffing, scraping, and runaway client loops all show up as request volume. When each request carries real cost, such as compute, egress, or paid upstream calls, limits also cap spend.

The algorithms covered here differ mainly on one axis. Some allow bounded bursts: a client that has been idle can briefly exceed the average rate. Others enforce a smoother ceiling across a window. Neither behavior is more correct. A burst-tolerant limiter in front of a fragile downstream can still overwhelm it, and a strict limiter in front of bursty but legitimate clients rejects normal traffic.

This choice matters most to engineers who own public APIs, gateways, or services protecting a fragile dependency. Decide which traffic shape you need first, then pick the algorithm that produces it.

Who should use rate limiting

Rate limiting is worth building or configuring if any of these describe your system:

• You expose an API to clients you do not control. Public APIs, partner integrations, and mobile backends receive traffic from code you cannot fix or redeploy. A limiter is the only lever you have when a client misbehaves.
• You run multi-tenant infrastructure. If many customers share the same services and databases, per-tenant limits are how you keep one tenant's spike from becoming everyone's outage.
• You call a downstream with a hard quota. If a payment provider, messaging service, or other upstream caps you at a fixed rate, limiting on your side keeps you below that cap instead of discovering it through errors.
• You have endpoints attractive to abuse. Login, signup, password reset, search, and anything that triggers an email or SMS should be limited per user, per IP, or per account identifier.
• Each request costs real money. Expensive compute, paid upstream calls, and egress all make an unlimited client a budget problem.

It is less useful for purely internal batch systems where every producer is under your control and you can apply backpressure directly, or for services whose capacity comfortably exceeds any plausible load. In those cases a limiter adds a dependency and a failure mode without protecting much.

How rate limiting works

Every rate limiter, regardless of algorithm, follows the same request path:

1. Identify the caller. Derive a key from the request: a user ID, API key, client IP, tenant ID, or a composite such as API key plus route. The key decides whose budget the request spends.
2. Look up state for that key. Depending on the algorithm, the state is a token count and a timestamp, one or two window counters, a list of recent timestamps, or a queue.
3. Update and decide. Apply elapsed time to the state (refill tokens, roll windows forward, evict old timestamps), then check whether this request fits. If it fits, record it. If it does not, reject it or, in the queueing variant, hold it.
4. Respond. Admitted requests continue to the handler. Rejected requests get a 429 Too Many Requests response, ideally with a Retry-After header telling the client when to try again.

The algorithms differ only in step 2 and step 3: what state they keep and how they turn elapsed time into an admit-or-reject decision. That difference determines burst behavior, accuracy, memory per key, and whether rejected requests fail fast or wait. The next sections walk through each one.

How the token bucket and leaky bucket work

A token bucket has two parameters: a capacity (the most tokens it can hold) and a refill rate (tokens added per second). Each request spends one token. If a token is available, the request is admitted immediately. If not, it is rejected. Capacity is the maximum burst size: a client that has been idle can send capacity requests back to back, then is held to the refill rate.

You don't need a background timer to add tokens. Store two values per key, the current token count and the timestamp of the last update. On each request, compute the elapsed time, add elapsed × rate tokens, cap the total at capacity, then try to spend one. This lazy refill keeps the cost constant per request, and idle keys cost nothing. That matters when you track millions of clients.

A leaky bucket as a queue works differently. Requests enter a FIFO buffer that drains at a fixed rate. Output is perfectly smooth, which suits a downstream system that cannot absorb bursts. The cost is that requests wait instead of failing fast. Queued requests add latency and hold memory and connections. They may also sit until the client times out and retries, which adds load at the worst moment.

The term "leaky bucket" also describes a meter. In that form, a counter drains at a constant rate and requests that would overflow it are rejected without queuing. That version is mathematically equivalent to a token bucket viewed from the other direction. Much confusion about these algorithms comes from conflating the meter and the queue.

Copyimport time

class TokenBucket:
    def __init__(self, capacity: float, rate: float):
        self.capacity = capacity      # max burst size
        self.rate = rate              # tokens added per second
        self.tokens = capacity        # start full: an idle client may burst
        self.last = time.monotonic()  # timestamp of last update

    def allow(self, cost: float = 1.0) -> bool:
        now = time.monotonic()
        elapsed = now - self.last
        self.last = now
        # Lazy refill: credit tokens for the time since the last call,
        # instead of running a background timer per key.
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        if self.tokens >= cost:
            self.tokens -= cost
            return True   # admit immediately
        return False      # reject now; no queue, no added latency

bucket = TokenBucket(capacity=10, rate=5)
results = [bucket.allow() for _ in range(12)]
print(results)  # roughly the first 10 True, then False until tokens refill

A single-process token bucket that refills lazily from elapsed time on each request, showing capacity as the burst limit and immediate admit/reject behavior.

How window-based limiters work: fixed window, sliding log, and sliding counter

Fixed window counter

The fixed window keeps one counter per key per window, such as "requests from this API key in the current minute." It increments on each request and resets when the clock crosses the boundary. It costs one integer per key and one increment per request, but it only enforces the limit inside each calendar window.

Illustrative estimate: assume a limit of 100 requests per minute. A client sends 100 requests at 00:59.5 and another 100 at 01:00.5. Each window sees exactly 100, so all are admitted. The backend still absorbs about 200 requests in roughly one second, which is twice the intended rate.

Sliding window log

The sliding log stores a timestamp for every admitted request. On each new request it evicts entries older than the window, counts what remains, and admits the request if the count is under the limit. The result is exact, with no boundary artifact. The cost is that memory and per-request work grow with the limit. A 10,000-per-hour limit can mean 10,000 stored timestamps for each key.

Sliding window counter

The sliding counter keeps only the current and previous fixed-window counts and estimates:

estimate = current + previous × (1 − elapsed / window)

Assume a 60-second window, with 80 requests in the previous window and 30 so far in this one, 15 seconds in. The estimate is 30 + 80 × 0.75 = 90, so 10 more requests are allowed.

The weighting assumes the previous window's traffic was spread evenly. If those 80 requests actually arrived in its final seconds, the true count is higher and the limiter over-admits. If they arrived early, it rejects requests that were within the limit. For most abuse protection this error is acceptable. For contractual limits that you must neither exceed nor undercut, use the log or a token bucket instead.

Copyimport time

class SlidingWindowCounter:
    """Approximates a rolling window using only two fixed-window counts per key."""

    def __init__(self, limit, window_s):
        self.limit = limit
        self.window = window_s
        self.state = {}  # key -> (window_start, current_count, previous_count)

    def allow(self, key, now=None):
        now = time.time() if now is None else now
        start = now - (now % self.window)  # start of the current fixed window
        ws, cur, prev = self.state.get(key, (start, 0, 0))
        if start != ws:
            # Roll forward: the old current becomes previous only if it was the
            # immediately preceding window; anything older no longer overlaps.
            prev = cur if start - ws == self.window else 0
            cur = 0
        elapsed = now - start
        # Weighted overlap: assumes previous-window traffic was evenly spread.
        estimate = cur + prev * (1 - elapsed / self.window)
        if estimate >= self.limit:
            self.state[key] = (start, cur, prev)
            return False
        self.state[key] = (start, cur + 1, prev)
        return True

lim = SlidingWindowCounter(limit=100, window_s=60)
for _ in range(80):
    lim.allow("api-key-123", now=30.0)   # 80 requests in the previous window
for _ in range(30):
    lim.allow("api-key-123", now=70.0)   # 30 requests early in the current window

admitted = sum(lim.allow("api-key-123", now=75.0) for _ in range(20))
print(admitted)  # 10

A minimal in-memory sliding window counter that stores two counts per key and reproduces the worked example, admitting exactly 10 more requests when the weighted estimate is 90 against a limit of 100.

Implementing limiters against a shared store

Once several application servers enforce the same limit, the limiter state has to live in a shared key-value store, and every update to it must be atomic. If a server issues a GET, computes the new token count, and then issues a SET, two concurrent requests can read the same count and both get admitted. Run the refill and decrement in one server-side script, or use a single atomic increment-with-expiry, so the store applies each decision as one indivisible step.

Choose the key to match what you want to protect, such as user:{id}, apikey:{key}, ip:{addr}, or a composite like apikey:{key}:route:/search. Compute the elapsed time from the store's clock inside the script, not from each application server's clock. Otherwise clock skew between servers adds or removes tokens.

In the usual architecture, clients reach a gateway, the gateway or each service calls the store before handling the request, and the store returns allow or deny. That check adds a network round trip to every request. When the store is unreachable you have two options. You can fail open and accept unlimited traffic, which suits abuse protection. You can fail closed and reject requests, which suits billing or quota enforcement.

Per-instance limiters avoid the round trip, but the effective global limit becomes the per-instance limit multiplied by the instance count, so it changes whenever autoscaling adds or removes instances. Watch for hot keys. A heavy tenant, or many users behind one shared NAT IP, sends all of its traffic to a single key and therefore to a single shard.

Copyimport redis

TOKEN_BUCKET = """
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])  -- tokens added per second
local cost     = tonumber(ARGV[3])
local t   = redis.call('TIME')      -- one authoritative clock, no app-server skew
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000
local s   = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or capacity
local ts     = tonumber(s[2]) or now
tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate)
local allowed = 0
if tokens >= cost then tokens = tokens - cost; allowed = 1 end
redis.call('HSET', KEYS[1], 'tokens', tostring(tokens), 'ts', tostring(now))
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) * 2)  -- idle keys expire
return allowed
"""

r = redis.Redis(host="ratelimit-store.internal", port=6379, socket_timeout=0.05)
bucket = r.register_script(TOKEN_BUCKET)

def allow(api_key: str, route: str, fail_open: bool = True) -> bool:
    # Composite key: limit each API key separately on each route.
    key = f"rl:apikey:{api_key}:route:{route}"
    try:
        # 100-token burst, refilling at 10 tokens/s, this request costs 1.
        return bucket(keys=[key], args=[100, 10, 1]) == 1
    except redis.RedisError:
        # Store unreachable: fail open for abuse protection, closed for quotas/billing.
        return fail_open

if __name__ == "__main__":
    print(allow("demo-key-123", "/search"))

A token bucket in Redis where the refill, the decrement, and the clock read all happen in one Lua script, keyed per API key and route, with an explicit choice between failing open and failing closed when the store is unreachable.

When to use each algorithm and when to avoid it

Pick the algorithm by the traffic shape your downstream can absorb, not by which one your library ships with.

Token bucket suits public and internal APIs where clients legitimately batch work: a page load that fires a dozen requests, or a job that wakes up and syncs. Bursts up to capacity cost nothing, and the refill rate still bounds the long-run average. Avoid a large capacity in front of fragile dependencies. A bucket sized for 500 tokens can release 500 requests in the same second, and a database with a small connection pool will feel every one of them.

Sliding window fits strict quotas, billing-relevant counts, and abuse-sensitive endpoints such as login or password reset, where "100 per rolling hour" must mean exactly that. Within this family, the sliding counter estimates by weighting the previous window. That is fine for abuse control but wrong for contractual limits a customer can dispute. The sliding log is exact, but it stores one timestamp per request, so avoid it for high-throughput keys.

Leaky bucket or queueing fits when a downstream needs a steady rate, such as a third-party API with a hard per-second cap or a batch writer. It smooths load by delaying requests rather than rejecting them. Avoid it when latency budgets are tight, because queue wait time adds directly to response time.

Alternatives to rate limiting

Rate limiting caps requests per unit of time per key. Several other techniques address overlapping problems, and they are often combined with a limiter rather than replacing it.

• Concurrency limits. Instead of capping requests per second, cap how many requests are in flight at once, per key or per service. This tracks actual resource use more closely: slow requests hold a slot longer, so the limit tightens automatically when a downstream degrades. A rate limit cannot see that a request takes ten times longer than usual. A concurrency limit can.
• Load shedding. The service rejects work based on its own health, such as queue depth, CPU saturation, or latency, rather than on per-client counters. It protects capacity without needing per-key state, but it does not provide fairness: a single noisy client can still cause everyone's requests to be shed.
• Backpressure. When you control both producer and consumer, such as in a message pipeline or an internal streaming system, the consumer can signal the producer to slow down through bounded queues or flow control. This avoids rejected work entirely, but it only works where the producer will honor the signal.
• Circuit breakers. A client-side breaker stops calling a failing dependency for a period after errors cross a threshold. It protects the downstream from retry storms and protects the caller from waiting on timeouts. It reacts to failure rather than preventing overload, so it complements a limiter instead of substituting for one.
• Quotas over long periods. Daily or monthly usage caps tied to a plan or invoice are accounting, not traffic shaping. They are usually enforced with durable counters checked against a billing record, and they do nothing to stop a burst within the period.
• Autoscaling. Adding capacity absorbs legitimate growth, but it reacts in minutes, costs money for every request including abusive ones, and does nothing for a fixed-capacity dependency such as a database or a quota-capped upstream.
• Abuse-specific controls. For login and signup endpoints, challenge mechanisms, account lockout policies, and authentication requirements target the attacker directly instead of counting requests.

In practice, a robust setup uses a rate limiter for per-client fairness and abuse control, a concurrency limit or load shedding for overall service health, and circuit breakers on outbound calls.

Communicating limits to clients and choosing where to enforce

When a request is rejected, return 429 Too Many Requests with a Retry-After header. Without it, clients guess, and many retry immediately, which adds load to a system that is already shedding it. A minimal rejection looks like HTTP/1.1 429 Too Many Requests with Retry-After: 12 and X-RateLimit-Remaining: 0, plus a short body naming the limit that was hit. Retry-After is standard HTTP. The X-RateLimit-* family is only a convention, so document exactly what your values mean.

Those values mean different things under each algorithm. A fixed window has a real reset instant, the window boundary, so "remaining" and "reset" are exact. A token bucket has no reset instant. Tokens trickle back continuously, so the honest Retry-After is the time until one token, or enough tokens for this request's cost, is available. Reporting a "full reset" time for a bucket overstates the wait. A sliding counter's remaining quota is an estimate, so present it as approximate.

Where to enforce

Enforce at the edge or gateway to reject floods before they consume service resources such as connections, TLS handshakes, and worker threads. The gateway usually only sees IPs, API keys, and paths, though. Limits that depend on tenant plan, request cost, or business state belong inside the service, which has that context. In practice, layer them. A coarse global limit at the edge protects capacity, and finer per-tenant or per-route limits in the service enforce fairness. The edge limit should sit above the sum of legitimate per-tenant traffic so it only triggers during abuse or overload.

Copyimport math
import time

class TokenBucket:
    def __init__(self, capacity: int, refill_per_sec: float):
        self.capacity = capacity
        self.rate = refill_per_sec
        self.tokens = float(capacity)
        self.updated = time.monotonic()

    def _refill(self) -> None:
        now = time.monotonic()
        elapsed = now - self.updated
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.updated = now

    def try_acquire(self, cost: int = 1) -> tuple[bool, dict[str, str]]:
        if cost > self.capacity:
            raise ValueError("cost exceeds bucket capacity; request can never succeed")
        self._refill()
        if self.tokens >= cost:
            self.tokens -= cost
            return True, {"X-RateLimit-Remaining": str(int(self.tokens))}
        # A bucket has no reset instant. Report the wait until enough tokens
        # exist for THIS request, not until the bucket is full again.
        wait = (cost - self.tokens) / self.rate
        return False, {
            "Retry-After": str(math.ceil(wait)),  # whole seconds, rounded up
            "X-RateLimit-Remaining": str(int(self.tokens)),
        }

A token bucket that derives Retry-After from the time until enough tokens refill for the current request's cost, along with the 429 response a service would return when it rejects a request.

Impact on development cost and engineering time

The largest recurring cost is infrastructure. A limiter shared across instances adds a network round trip to the store on every request, so the store becomes a latency-sensitive dependency that must be sized, replicated, and monitored. Token bucket and sliding counter keep a small fixed amount of state per key. A sliding log stores one entry per request, so its memory grows with traffic.

Illustrative estimate (assumed numbers, not a benchmark) Memory ≈ active keys × requests allowed per window × bytes per entry Assume 10,000 active keys, a limit of 1,000 requests per minute, and 50 bytes per log entry: 10,000 × 1,000 × 50 = 500 MB at full utilization. If a sliding counter uses about 100 bytes per key, the same keys need about 1 MB.

Operational work adds to that. Someone has to choose and test fail-open or fail-closed behavior, handle hot keys that concentrate load on one shard, and keep clocks and TTLs consistent.

Most of the engineering time spent on limiters goes into rework. If the team decides the permitted traffic shape before writing code (bursty or smooth, approximate or exact), it avoids three expensive outcomes:

• Rewriting a fixed-window limiter after boundary bursts cause an incident.
• Spending days investigating why autoscaling keeps reacting to traffic spikes the limiter allowed.
• Arguing with customers over quota counts that the algorithm cannot reproduce exactly.

To reduce maintenance, use the gateway's built-in limiter for coarse capacity protection. Write custom code only for tenant-specific rules that the gateway cannot express, such as plan tiers or contractual quotas.

How OneEnv can help

Disclosure: OneEnv is the product behind this blog.

OneEnv (oneenv.io) is a workspace-based governance platform for the things services share — environment variables, database structure, API routes and validation rules. A change to a shared value is staged on a branch, reviewed once, and then every affected service explicitly approves or rejects it before it goes live, so you can see who a change touches before it ships instead of finding out in production.

Applied to rate limiting algorithms, this is where it helps:

Saves time

• Every service that inherits a shared value is listed in one place, so nobody searches repos and chats to find out who is affected.
• One review per branch replaces coordinating each team separately; each service still keeps its own approve/reject.
• Changing a route's URL or method automatically notifies the services that consume it — no hunting through repos for callers.

Saves cost

• Fewer production incidents and rollbacks caused by a shared value, route or column changing under a consumer unannounced.
• Less duplicated configuration to maintain: one shared definition inherited by many services.
• Consumers learn about a breaking change at review time rather than from production errors.
• OneEnv has a free plan (1 workspace, unlimited services and members, full governance), so trying it costs nothing.

These are qualitative benefits, not measured results — how much you save depends on how many services share the value.

Want to try it? Start at oneenv.io.