Module 12 · Lesson 10 of 13Free

Rate limiting algorithms: token bucket to sliding window

Level

Intermediate

Topic

Reliability, overload and traffic spikes

Reading time

19 min

Kartly accepts 120 requests from one seller just before a minute ends. It accepts another 120 just after the next minute begins. The seller obeyed “120 requests per minute”, yet sent 240 requests almost together.

Which requests should a rate limiter admit when traffic arrives unevenly?

This lesson follows Kartly’s seller stock-read API. Kartly already has separate services. The numbers below describe one account’s allowance, not the store’s total traffic.

A minute has two meanings

Suppose the rule means “120 accepted requests during each clock minute”. A fixed window stores a counter for each account and clock interval. It admits a request if incrementing that counter would stay within the limit. The next interval gets a fresh counter. ^{1Build 5 Rate Limiters with Redis: Fixed Window, Sliding Window, Token Bucket, and Leaky BucketWilliam Johnston, Redis, 2026}

For this lesson’s scenario, the window lasts 60 seconds. The interval number is the current timestamp divided by 60, rounded down.

At 12:00:59.9, the request uses the 12:00 counter. At 12:01:00.1, it uses a different counter. Neither counter exceeds 120.

Now change the wording: “At most 120 accepted requests in the preceding 60 seconds.”

That rule follows the current time instead of a clock boundary. At 12:01:00.1, the first group is still recent. The second group must wait.

The common belief that “120 per minute means about two per second” misses this distinction. Both rules permit 120 requests together after sufficient inactivity. Neither promises evenly spaced traffic.

Before choosing an algorithm, write down the promise you actually need.

Choose the promise before storage

From Rate limiter placement, keep the same identity and enforcement point. Here, the trusted identity is a seller account, and the policy covers stock reads.

Kartly’s product question is: should a seller dashboard load several stock panels together?

For this scenario, yes. Allow a short burst of 10 requests. After that, admit work at a sustained rate of two requests per second. These are illustrative policy values, not measured service capacity.

A token bucket fits this scenario. Next, we need to see exactly how it earns and spends permission.

Tokens remember unused permission

A token bucket keeps an available balance and a last-update time. Elapsed time restores tokens up to a capacity. An admitted request spends tokens; an insufficient balance causes rejection. ^{1Build 5 Rate Limiters with Redis: Fixed Window, Sliding Window, Token Bucket, and Leaky BucketWilliam Johnston, Redis, 2026}

Kartly charges one token per stock read. Capacity is 10 tokens, and refill is two tokens per second.

There is no need for a timer that wakes twice a second. On each request, compute what should have accumulated since the previous update:

available = min(capacity, previous_tokens + elapsed_seconds × refill_rate)

If available is at least the request cost, subtract that cost. Otherwise, leave the refreshed balance unspent.

Assume a full bucket at time zero:

Fractional tokens preserve elapsed-time credit. Rounding the balance down on every arrival would discard that credit.

A rejection updates the accounting time but does not spend a token. Frequent rejected requests therefore cannot prevent the bucket from refilling.

Show the allowance’s limits

The bound follows from accounting: requests can spend only the starting balance plus tokens earned during the interval.

An expensive endpoint could charge several tokens. That makes the allowance a budget of work rather than a count of requests. Its cost estimate must still reflect the resource you intend to protect.

The next risk is implementation: a correct equation does not help if two callers spend the same balance.

Implement one serialized state transition

The following function belongs to the limiter, not the stock service. It receives one bucket’s state and returns the new state, the decision and a retry delay.

The caller initializes a new bucket as full. It must serialize calls for the same bucket. The function itself provides neither locking nor shared storage.

Time comes from a monotonic clock within one running process. Supplying time explicitly also makes request traces easy to reason about.

from dataclasses import dataclass
from math import isfinite

@dataclass(frozen=True)
class Bucket:
    tokens: float
    updated_at: float

def admit(
    state: Bucket, now: float, capacity: float,
    rate: float, cost: float = 1.0,
) -> tuple[Bucket, bool, float]:
    values = (state.tokens, state.updated_at, now, capacity, rate, cost)
    if not all(isfinite(value) for value in values):
        raise ValueError("values must be finite")
    if capacity <= 0 or rate <= 0 or not 0 < cost <= capacity:
        raise ValueError("invalid policy")
    if not 0 <= state.tokens <= capacity:
        raise ValueError("invalid balance")

    timestamp = max(now, state.updated_at)
    available = min(
        capacity, state.tokens + (timestamp - state.updated_at) * rate
    )
    allowed = available >= cost
    remaining = available - cost if allowed else available
    retry_after = 0.0 if allowed else (cost - available) / rate
    return Bucket(remaining, timestamp), allowed, retry_after

type Bucket = Readonly<{ tokens: number; updatedAt: number }>;

function admit(
  state: Bucket, now: number, capacity: number,
  rate: number, cost: number = 1,
): readonly [Bucket, boolean, number] {
  const values = [
    state.tokens, state.updatedAt, now, capacity, rate, cost,
  ];
  if (!values.every((value) => Number.isFinite(value))) {
    throw new Error("values must be finite");
  }
  if (capacity <= 0 || rate <= 0 || cost <= 0 || cost > capacity) {
    throw new Error("invalid policy");
  }
  if (state.tokens < 0 || state.tokens > capacity) {
    throw new Error("invalid balance");
  }

  const timestamp = Math.max(now, state.updatedAt);
  const available = Math.min(
    capacity, state.tokens + (timestamp - state.updatedAt) * rate,
  );
  const allowed = available >= cost;
  const remaining = allowed ? available - cost : available;
  const retryAfter = allowed ? 0 : (cost - available) / rate;
  return [{ tokens: remaining, updatedAt: timestamp }, allowed, retryAfter];
}

For an empty bucket at time zero, a call at 0.25 seconds returns a half-token balance. It rejects the request and reports a further wait of 0.25 seconds.

The timestamp clamp prevents an earlier reading from moving accounting backwards. It does not make unrelated machines’ clocks comparable.

These examples use floating-point arithmetic for clarity. A policy requiring exact boundary decisions needs defined integer units and rounding rules. Otherwise, a tiny representation error can change a decision at the threshold.

This implements the burst policy. A strict preceding-minute quota needs different state.

Sliding windows remember recent admissions

A sliding-window log stores timestamps of accepted requests. Before deciding, remove expired entries, count the survivors, and append the new admission only if space remains. ^{1Build 5 Rate Limiters with Redis: Fixed Window, Sliding Window, Token Bucket, and Leaky BucketWilliam Johnston, Redis, 2026}

Define Kartly’s alternative rolling interval precisely: include timestamps later than now − 60 seconds, through now.

At time 60 seconds, an admission at time zero has expired. An admission at time 0.001 seconds has not. This boundary convention prevents implementations from disagreeing about equality.

For a limit of three, trace this smaller example:

Do not append the rejected arrival at 59 seconds. This lesson’s policy counts admissions. Counting attempts instead would define a different policy.

Inside one process, ordered arrivals can use a double-ended queue. Remove old entries from the front and append accepted entries at the back. Each timestamp enters and leaves once, giving amortized constant work per request.

A shared implementation can use a Redis sorted set, with timestamps as scores and unique admission identifiers as members. Redis’s tutorial uses sorted sets for this algorithm. ^{1Build 5 Rate Limiters with Redis: Fixed Window, Sliding Window, Token Bucket, and Leaky BucketWilliam Johnston, Redis, 2026}

The unique member matters: two admissions can have the same timestamp. Using that timestamp as both score and member could collapse them into one entry.

Exact history has a price

Suppose, for this scenario, 100,000 active seller-policy pairs each retain 120 admissions.

That is 12 million entries. At an illustrative 16 bytes per timestamp-and-identifier pair, the raw payload alone is 192 MB. Container overhead, keys and replication are additional.

The log also permits all 120 admissions together when the preceding interval is empty. Exact counting does not imply smooth traffic.

If approximate fairness is enough, we can discard individual timestamps. The cost is uncertainty about where requests occurred.

Two counters lose timing information

A sliding-window counter estimates recent traffic from the current fixed-window count plus a weighted previous count. It assumes the previous window’s requests were spread evenly. ^{1Build 5 Rate Limiters with Redis: Fixed Window, Sliding Window, Token Bucket, and Leaky BucketWilliam Johnston, Redis, 2026}

Use this rule for the estimate before admitting a new request:

estimate = current_count + previous_count × (1 − elapsed_fraction)
accept only if estimate + request_cost <= limit

Halfway through a minute, half the preceding clock minute overlaps the rolling interval. With a previous count of 120 and a current count of 20:

20 + 120 × 0.5 = 80 estimated recent admissions

Now consider two histories with those same counters.

In the first history, the previous 120 requests arrived near that minute’s end. At the midpoint of the current minute, all remain recent.

In the second history, they arrived near its beginning. At the current midpoint, all have expired.

The estimator returns the same previous contribution, 60, for both histories. The true contribution is different. No calculation can recover timestamps that were never stored.

This algorithm can therefore admit too much or reject too early. More, smaller time buckets reduce the uncertainty but retain more state.

One remaining distinction is whether excess work should wait or leave.

Waiting is another policy

A leaky-bucket shaper puts accepted work in a bounded queue and releases it at a configured pace. It trades immediate bursts for waiting. ^{1Build 5 Rate Limiters with Redis: Fixed Window, Sliding Window, Token Bucket, and Leaky BucketWilliam Johnston, Redis, 2026}

For this scenario’s rate, releasing one request every half-second spaces downstream admissions. Ten queued requests take about five seconds to release, depending on the initial release slot.

That may suit a seller’s background export. It is less attractive for an interactive stock panel that might time out before its turn.

The phrase “leaky bucket” also appears in rejecting, rather than queueing, implementations. Specify the behavior: store pending work, or reject arrivals that exceed a pacing allowance.

Do not silently add waiting to a rejecting limiter. Waiting requires queue bounds, deadlines and cancellation. Backpressure covers slowing producers without accumulating unlimited work.

Whatever algorithm you choose, multiple servers must agree on the state they are spending.

One balance needs one decision

Kartly’s illustrative shared design stores one bucket per seller and policy. The gateway performs the check before forwarding an admitted stock read.

The normal request path is:

1. The gateway derives a key such as rl:v1:seller:842:stock-read.
2. The state owner obtains time and loads that bucket.
3. One atomic operation refills, checks and conditionally debits it.
4. The gateway forwards an allowed request or returns a rejection.

The limiter writes allowance state even for a rejected request if it refreshes the accounting timestamp. The stock service does not own that write.

If two gateways both read one remaining token, both could admit a request before either writes zero. Atomic individual reads and writes do not make the whole transition atomic. A Redis script can keep that sequence together. ^{1Build 5 Rate Limiters with Redis: Fixed Window, Sliding Window, Token Bucket, and Leaky BucketWilliam Johnston, Redis, 2026}

A local bucket avoids the shared-store call. However, independent full buckets on four replicas multiply both this scenario’s burst allowance and sustained rate by four. Envoy’s HTTP local limiter defaults to per-process enforcement; it also supports a per-connection scope. ^{3Local rate limitEnvoy Project, Envoy documentation}

Rejection must explain recovery

HTTP defines 429 Too Many Requests for rate limiting. Its response may include Retry-After; such responses must not be cached. ^{2RFC 6585: Additional HTTP Status CodesMark Nottingham and Roy Fielding, IETF, 2012}

For a calculated half-second wait, Kartly rounds up to a whole second:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 1

{"error":"RATE_LIMITED","policy":"seller-stock-read"}

That delay is not a reservation. Another request can spend the next token. Follow Exponential backoff and jitter rather than retrying immediately in a loop.

A store timeout is different from an exhausted bucket. Record it separately. For this read endpoint, an illustrative fallback is a conservative local cap, accepting weaker account-wide enforcement during the outage.

Track check latency, store errors and rejections by policy. Otherwise, a broken limiter can look like abusive customers.

Deleting a partly empty bucket and recreating it full grants extra allowance. Expire an idle token bucket only after enough time for it to become full anyway. A restart or state loss also requires an explicit reset policy.

Where this shows up

• Design: an API rate limiter develops shared enforcement and its storage failures.
• Design: a web crawler needs pacing per destination, not only an aggregate quota.

An algorithm controls allowance; the next lesson asks how Kartly handles bots that spread abuse across many identities.

Common mistakes

• Treating all per-minute rules as equivalent. Clock windows, rolling windows and token buckets admit different request sequences.
• Calling sliding counters exact. Their missing timing information is an intentional tradeoff.
• Making refill a large periodic reset. Adding a minute’s tokens together recreates a large burst instead of gradual permission.
• Resetting expiry on every fixed-window attempt. A duration since the latest attempt is not an aligned clock window.
• Assuming admission guarantees capacity. Many accounts can spend saved tokens together. Aggregate overload still needs separate protection.

Check your understanding

Summary