Token Bucket vs Sliding Window: Choosing an API Rate Limiter

What the five rate limiting algorithms actually do

API rate limiting decides, per client key, whether a request is allowed right now. The five common algorithms differ in what "too many" means. Token bucket regulates a sustained rate and permits bounded bursts. Sliding window variants cap how many requests fall inside a trailing interval.

The practical question is what you need. A token bucket says "on average no faster than r, with some slack." A sliding window says "never more than N in the last T seconds."

How does an API rate limiter work in the request path?

Every algorithm in the table plugs into the same per-request sequence:

1. Identify the key. Decide whose budget the request spends. Common choices are the API key, the authenticated user or tenant ID, or the client IP address for unauthenticated traffic. Keys can be combined with the route, so an expensive endpoint gets its own budget separate from cheap reads.
2. Determine the cost. Most limiters charge 1 per request. Some charge more for expensive operations, such as a bulk export or a search with many results, which is what the cost parameter in the code below represents.
3. Load the state for that key. This is the counter, timestamp list or token count from the table, held in process memory or in a shared store.
4. Apply the algorithm. Compute whether the request fits within the limit at the current time.
5. Update the state and respond. If allowed, record the consumption and forward the request. If not, reject it with 429 Too Many Requests (covered below) or, for a queue-based leaky bucket, hold it until it can be released.

The limiter can sit at several layers: a reverse proxy or gateway in front of all services, middleware inside the application framework, or a check inside a specific handler. Gateways see every request cheaply but often know only the IP or API key. Application-level limiters know the authenticated user, the plan tier and the real cost of the operation. Many systems layer both: a coarse per-IP limit at the edge to absorb floods, and a precise per-customer limit in the application to enforce quotas.

The rest of this article covers step 4 in detail, then how steps 3 and 5 change when the state is shared across servers.

How the windows and the bucket behave under bursty traffic

Those guarantees diverge most when traffic arrives in bursts. Take a limit of 100 requests per minute and a client that sends 100 requests at 0:59.5 and another 100 at 1:00.5.

A fixed window resets its counter at 1:00:00, so both batches pass. That is 200 requests in about one second, double the stated limit. The counter only knows which minute it is in, not how recent the earlier requests were.

A sliding window log stores each timestamp and counts those in the trailing 60 seconds. At 1:00.5 all 100 earlier requests are still in range, so the second batch is rejected. The result is exact, but memory grows with every admitted request.

A sliding window counter keeps only two counts and weights the previous one by how much of it still overlaps: 100 × (59.5/60) ≈ 99. About one request gets through. The estimate assumes the previous window's traffic was spread evenly. When that traffic is clustered, the result can be slightly off in either direction, but it never comes close to 2×.

A token bucket with capacity 100 and a refill rate of 100/min (about 1.67/s) is drained by the first batch, so roughly 2 tokens are available a second later. Over any interval T, it admits at most capacity + rate × T. Capacity sets the largest burst, and the refill rate sets the long-run throughput.

Copytime:          0:59.5   1:00.5   (idle 30s)   1:31
fixed window   100 ok   100 ok                 100 ok
sliding log    100 ok   0 ok                   ~0 ok*
sliding count  100 ok   ~1 ok                  ~50 ok
token bucket   100 ok   ~2 ok                  ~50 ok
* log frees capacity only when 0:59.5 entries expire at 1:59.5

Copy+----------------------------------------------------------------+
| client: 100 @0:59.5 -> 100 @1:00.5 -> idle 30 s -> 100 @1:31   |
+-------------------------------+--------------------------------+
                                |
   +----------------------------+
   |
   +--> +--------------------------------------+
   |    | fixed window: counter resets at 1:00 |--> 100 / 100 / 100
   |    | knows only the current minute        |    (200 in ~1 s)
   |    +--------------------------------------+
   +--> +--------------------------------------+
   |    | sliding log: timestamps in last 60 s |--> 100 /   0 /  ~0
   |    | exact; memory grows per request      |    (frees at 1:59.5)
   |    +--------------------------------------+
   +--> +--------------------------------------+
   |    | sliding counter: prev x overlap+curr |--> 100 /  ~1 / ~50
   |    | 2 counts; assumes even spread        |
   |    +--------------------------------------+
   +--> +--------------------------------------+
        | token bucket: cap 100, +1.67 tok/s   |--> 100 /  ~2 / ~50
        | max burst = cap; long run = refill   |
        +--------------------------------------+

 outputs = requests admitted at 0:59.5 / 1:00.5 / 1:31 (limit 100/min)

The same bursty traffic sent through four limiters with a 100 requests/minute limit: only the fixed window admits about 200 requests across the boundary, and the counter and bucket recover capacity after the idle period.

Implementing token bucket and sliding window counter

Token bucket

Store two values per key: tokens and last_refill. Nothing refills in the background. On each request:

1. Read now from a monotonic clock.
2. Add (now - last_refill) × rate to tokens, capped at capacity. Set last_refill = now.
3. If tokens ≥ cost, subtract cost and allow. Otherwise reject. The client can retry after (cost - tokens) / rate seconds.

Because refill is computed lazily, an idle key needs no timer and no CPU, and each check is O(1). Use a monotonic clock because the wall clock can be stepped by time synchronization. A backward step makes elapsed time negative. A forward step grants an unearned burst.

Sliding window counter

Keep a counter per fixed window of length W, keyed by floor(now / W). Retain only the current and previous counts. On each request, compute f, the fraction of the current window that has elapsed, then:

estimate = previous × (1 − f) + current

If estimate + cost ≤ limit, increment current and allow.

Why it is an estimate

The weight (1 − f) assumes the previous window's requests were spread evenly across it. Take a limit of 100 per minute. If all 100 requests arrived in the last second of the previous minute, then 30 seconds later the formula counts them as 50 and admits 50 more. In reality all 100 fell inside the trailing 31 seconds. The error is worst when traffic clusters near window edges.

For abuse protection this rarely matters, because a brief overshoot is harmless. It does matter for strict quotas, contractual limits and anything tied to billing. In those cases use a sliding log or a token bucket, both of which enforce the limit exactly.

Copyimport time

class TokenBucket:  # one instance per key
    def __init__(self, capacity, rate):
        self.capacity, self.rate = capacity, rate  # rate = tokens per second
        self.tokens = capacity
        self.last_refill = time.monotonic()  # immune to wall-clock steps

    def allow(self, cost=1):
        now = time.monotonic()
        # Lazy refill: credit tokens earned since the last check, capped at capacity.
        self.tokens = min(self.capacity, self.tokens + (now - self.last_refill) * self.rate)
        self.last_refill = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True, 0.0
        return False, (cost - self.tokens) / self.rate  # seconds until retry

class SlidingWindowCounter:  # one instance per key
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.index = int(time.monotonic() // window)
        self.previous = self.current = 0

    def allow(self, cost=1):
        now = time.monotonic()
        index = int(now // self.window)
        if index != self.index:
            # Roll forward; a gap of more than one window means previous is empty.
            self.previous = self.current if index == self.index + 1 else 0
            self.current, self.index = 0, index
        f = (now % self.window) / self.window  # fraction of current window elapsed
        # Approximation: assumes previous window's requests were evenly spread.
        estimate = self.previous * (1 - f) + self.current
        if estimate + cost <= self.limit:
            self.current += cost
            return True
        return False

In-process reference implementations of a lazily refilled token bucket and a weighted sliding window counter, both driven by a monotonic clock.

Running a rate limiter across many servers

Once the limiter state lives in a shared store, every check becomes a read-compute-write cycle, and that cycle must be atomic. Suppose two servers each read a token count of 1, each decide the request is allowed, and each write back 0. Both requests pass. Under real load, dozens of servers interleave this way, and the overshoot grows with concurrency, which is exactly the condition the limiter exists to handle. To prevent it, run the whole step inside the store, either as a server-side script or as a transaction that retries on conflict. Then no other client can observe or change the state partway through.

Clocks

Take the current time from the store itself, or design the algorithm to tolerate skew between app servers. Do not use wall-clock time for elapsed-time math. NTP corrections and manual changes can move it backward or forward, which can refill a bucket instantly or freeze it. When you measure time locally, use a monotonic clock.

Cost of centralizing

A shared store adds a network round trip to every request and becomes a single point of failure. Decide in advance what happens when it is unreachable. Fail-open preserves availability but removes protection. Fail-closed protects downstream systems but turns a store outage into an API outage.

In-process limiters avoid both problems, but the effective global limit becomes the per-instance limit multiplied by the instance count. With autoscaling, that product changes every time the fleet scales up or down.

Copy-- One row per client: token bucket with capacity 100, refill 10 tokens/s.
CREATE TABLE rate_limit_bucket (
  bucket_key VARCHAR(200) PRIMARY KEY,
  tokens     DOUBLE PRECISION NOT NULL,
  updated_at TIMESTAMP NOT NULL
);

-- RACY: the app SELECTs tokens, decides in its own code, then UPDATEs.
-- Two servers can both read tokens = 1, both allow, and both write 0.
--   SELECT tokens, updated_at FROM rate_limit_bucket WHERE bucket_key = ...;
--   UPDATE rate_limit_bucket SET tokens = <app-computed value> WHERE ...;

-- ATOMIC: read, refill, check and decrement happen in one statement.
-- The row lock makes concurrent requests for the same key run one at a time,
-- and each one re-checks the WHERE clause against the latest committed row.
-- Time comes from the database, so every app server uses the same clock
-- and skew between app servers does not matter.
UPDATE rate_limit_bucket
SET tokens = LEAST(100, tokens + 10 * GREATEST(0,
               EXTRACT(EPOCH FROM (CURRENT_TIMESTAMP - updated_at)))) - 1,
    updated_at = CURRENT_TIMESTAMP
WHERE bucket_key = 'api-key:demo-123'
  -- GREATEST(0, ...) clamps elapsed time, so a backward clock step
  -- cannot produce negative refill.
  AND LEAST(100, tokens + 10 * GREATEST(0,
        EXTRACT(EPOCH FROM (CURRENT_TIMESTAMP - updated_at)))) >= 1
RETURNING tokens;

-- One row returned  -> allowed; the value is the tokens left.
-- Zero rows returned -> rate limited (or the key has no bucket yet).
-- If this query errors or times out, the caller has to apply its
-- predefined fail-open or fail-closed policy.

Moving the refill, limit check and decrement into a single conditional UPDATE that uses the store's clock prevents the read-then-write race in which concurrent servers overshoot the limit.

Memory, latency and engineering cost of each approach

Per-key state is where the algorithms diverge most. A sliding window log keeps one timestamp per accepted request, so its memory grows with the limit (O(limit)). Each check also has to evict expired entries, so its cost grows with the limit too. A sliding window counter and a token bucket keep a fixed number of fields per key no matter how high the limit is.

Illustrative estimate (assumed numbers, not a benchmark). Use memory ≈ active_keys × entries_per_key × bytes_per_entry. Assume 1,000,000 active keys, a limit of 100 per window, 16 bytes per entry, and ignore key-name overhead because it is the same for every algorithm.

• Log: 1,000,000 × 100 × 16 B ≈ 1.6 GB
• Token bucket: 1,000,000 × 1 × 16 B ≈ 16 MB

Engineering cost follows from what the store already does atomically. If it offers increment-with-expiry, a counter takes a few lines of code. A token bucket needs a scripted or CAS-based update, and a CAS-based update can lose races under contention. Constant-state algorithms with simple semantics also save time later. Capacity planning becomes one multiplication. A wrong decision can be debugged by reading two fields. Support can explain a rejection to a client in one sentence.

Who should use a rate limiter, and which kind

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

• You run a public or partner-facing API. Clients you do not control will send retries in tight loops, misconfigured cron jobs and scraping traffic. A per-key limit keeps one client from consuming capacity meant for everyone.
• You operate a multi-tenant service. Without per-tenant limits, one large or misbehaving tenant degrades latency for the rest. Here the limit is a fairness mechanism as much as a protective one.
• You sell plans with usage tiers. Quotas tied to pricing need limits that are exact and explainable, which points to a sliding window log or a token bucket rather than an approximation.
• You expose expensive or abuse-prone endpoints. Login, password reset, signup, search and report generation are common targets. These often deserve their own stricter limits, keyed by account and by IP.
• You run a platform in front of fragile shared dependencies. A database, a legacy system or a third-party API with its own quota may need traffic shaped to a steady rate, which is the leaky bucket's role.

You may not need a dedicated rate limiter if a service has a small, fixed set of trusted internal callers whose load you already control, or if the real constraint is in-flight work rather than request rate. In that second case, a concurrency limit (described in the alternatives section) fits better.

When to use each algorithm and when to avoid it

Token bucket suits client-facing APIs where short bursts are normal. A page load that fires a dozen requests, or a batch job that wakes up and submits a backlog, should not be punished for arriving all at once. Avoid it when a full-capacity burst after an idle period could overload a fragile downstream service. A bucket that refilled overnight will release its entire capacity in the first second of the morning.

Sliding window suits hard per-period quotas and fairness guarantees, because no alignment of requests lets a client exceed N per period. The log variant stores one entry per request, so avoid it at high limits across many keys. The counter variant approximates the previous window's contribution, so avoid it for limits tied to billing, where customers will dispute an estimate.

Leaky bucket suits downstream systems that need a smooth, constant outflow. A queue-based implementation shapes traffic instead of rejecting it, and that costs something. Every queued request adds latency. You need a policy for when the queue is full. Clients with short timeouts may give up while still waiting in line.

Platform teams protecting shared services usually care about outflow shape. Product teams enforcing plan quotas care about per-customer accuracy.

Alternatives to request-rate limiting

Rate limiters count requests over time. Some problems are better solved by controlling something else, and these techniques are often combined with a rate limiter rather than replacing it.

• Concurrency limits. Cap the number of requests in flight per client or per service instead of requests per second. This tracks actual resource use more closely when request durations vary widely: ten slow report queries can hurt more than a thousand cache hits, and a concurrency cap catches that where a rate limit does not.
• Adaptive concurrency and load shedding. Instead of a fixed number, the server adjusts how much work it accepts based on observed latency or queue depth, and rejects or deprioritizes requests when it is overloaded. This protects the server regardless of which client is responsible, but it does not give individual customers a predictable, documented budget.
• Long-period quotas. Daily or monthly usage caps, usually enforced by counting in a database and checking against the plan. These answer "how much may this customer use in total" rather than "how fast," and they typically sit alongside a short-term rate limit.
• Queues with backpressure. For asynchronous work, accept jobs into a queue and let workers pull at the rate they can sustain. Clients see delay instead of rejection, and a bounded queue signals overload when it fills.
• Client-side controls. Exponential backoff with jitter, retry budgets and circuit breakers in client libraries reduce retry storms at the source. They depend on clients behaving well, so they complement server-side limits but cannot replace them for untrusted callers.
• Caching and request coalescing. If much of the load is repeated identical reads, serving them from a cache or merging concurrent identical requests removes load without rejecting anyone.

If the goal is protecting a service from overload, concurrency limits and load shedding are strong candidates. If the goal is enforcing a per-client contract or fairness between tenants, a rate limiter or quota is the right tool.

Communicating limits to clients and a decision checklist

Reject over-limit requests with 429 Too Many Requests and a Retry-After header in whole seconds. Rounding up keeps a well-behaved client from retrying a fraction of a second too early and being rejected again. On successful responses, expose the limit, the remaining quota and the reset time. Many APIs use X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset, and IETF work is ongoing to standardize equivalent fields. Clients can then slow down before they hit a 429 instead of after.

"Reset" is only well defined for fixed windows, where the counter clears at a known boundary. Other algorithms have no single reset moment, so compute Retry-After from the algorithm's state:

• Token bucket: Retry-After = (cost − tokens) / refill_rate, where cost is what the request would consume. The bucket never resets, so a "reset" header should state either the time until the next token or the time until the bucket is full, and the docs should say which.
• Sliding window log: use the time until the oldest timestamp in the window expires, since that frees one slot.
• Sliding window counter: solve prev × (1 − elapsed/window) + curr < limit for elapsed. The weighting is approximate, so the result is also approximate. Round up.

Decision checklist

• Is bursting acceptable? If yes, use a token bucket. If no, use a leaky bucket or a sliding window.
• Is the limit a contractual quota or a protective measure? A contractual quota calls for windows that are exact and auditable. A protective measure can tolerate approximation.
• How many keys exist? Millions of keys rule out per-request logs.
• What atomic primitives does the store support? Without atomic scripts or compare-and-set, choose algorithms that need only an increment.
• Must the limit be exact, or can it be approximate?

Copyimport math

def retry_after_token_bucket(tokens, cost, refill_rate):
    # Seconds until enough tokens accumulate for this request.
    if tokens >= cost:
        return 0
    return math.ceil((cost - tokens) / refill_rate)

def retry_after_sliding_log(timestamps, limit, window, now):
    # timestamps: sorted request times still inside the window.
    if len(timestamps) < limit:
        return 0
    # A slot frees when the entry that put us at the limit ages out.
    blocking = timestamps[len(timestamps) - limit]
    return max(1, math.ceil(blocking + window - now))

def retry_after_sliding_counter(prev, curr, limit, window, elapsed):
    # Allowed when prev * (1 - elapsed/window) + curr < limit.
    if prev * (1 - elapsed / window) + curr < limit:
        return 0
    if curr >= limit:
        # Current window alone is full: lower bound is its rollover.
        return math.ceil(window - elapsed)
    # Solve for the elapsed time where the weighted sum drops below limit.
    target = window * (1 - (limit - curr) / prev)
    # floor + 1 keeps the inequality strict; the estimate is approximate.
    return max(1, math.floor(target - elapsed) + 1)

def reject_headers(retry_after, limit):
    # Sent with a 429 Too Many Requests response.
    return {
        "Retry-After": str(retry_after),
        "X-RateLimit-Limit": str(limit),
        "X-RateLimit-Remaining": "0",
    }

wait = retry_after_sliding_counter(prev=100, curr=40, limit=100, window=60, elapsed=12)
print(wait, reject_headers(wait, 100))  # 13 seconds

Computing a rounded-up Retry-After value from token bucket, sliding window log and sliding window counter state, and attaching it to a 429 response's headers.

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 token bucket vs sliding window, 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.