Dinesh/ Blog
systems

Token buckets: bursts, clocks and the atomic boundary

Implement and test one token bucket, then identify what changes when several servers enforce the same quota.

12 min read
Checking device speech…
Lesson preparation & details

Level: intermediate

By the end, you should be able to

  • Trace refill and consumption exactly
  • Test burst and backward-clock cases
  • Choose an explicit limiter failure policy

Sources checked: . A source check does not change the publication or update date.

Editorial review: · What review means

In this article · 16 sections

The capacity worksheet says the service needs bounded admission. The policy for this lab is two requests per second with a burst capacity of three. That is not “no more than two in every one-second interval”: an idle tenant may spend three accumulated tokens immediately. If you require a hard count in every rolling interval, a token bucket is a different contract.

Derive the state transition

Keep a token balance, a last-update time, a refill rate and a capacity. At time now, add elapsed × rate, cap at capacity, then subtract the request cost if enough remains. An empty bucket needs (cost - balance) / rate seconds to afford that request. Update the timestamp even on rejection, because refill has already been accounted for.

Use a monotonic time source inside one process. A wall clock moving backward must not manufacture capacity. The test uses exact rational arithmetic so fractional boundaries are unambiguous; a high-throughput implementation would choose a documented fixed-point representation and bound its numerical errors.

Derive the state transition
Figure text equivalent — labels and relationships
  • Node “Request plus trusted tenant” (square).
  • Node “Atomic refill and consume” (square).
  • Node “Persist balance and clock” (square).
  • Node “Allow or reject with delay” (square).
  • “Request plus trusted tenant” leads to “Atomic refill and consume”. Line: normal; ends: arrow point.
  • “Atomic refill and consume” leads to “Persist balance and clock”. Line: normal; ends: arrow point.
  • “Persist balance and clock” leads to “Allow or reject with delay”. Line: normal; ends: arrow point.

“Atomic” covers the read, decision and write together. Separate GET and SET operations can let two callers spend the same last token.

from fractions import Fraction as F
 
class Bucket:
    def __init__(self, capacity, rate, now=0):
        if capacity <= 0 or rate <= 0:
            raise ValueError("positive capacity and rate required")
        self.capacity, self.rate = F(capacity), F(rate)
        self.tokens, self.last = F(capacity), F(now)
 
    def take(self, now, cost=1):
        now, cost = F(now), F(cost)
        if cost <= 0 or cost > self.capacity:
            raise ValueError("cost must fit the bucket")
        if now < self.last:
            raise ValueError("clock moved backwards")
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True, F(0)
        return False, (cost - self.tokens) / self.rate
 
b = Bucket(3, 2)
assert [b.take(0)[0] for _ in range(4)] == [True, True, True, False]
assert b.take(F(1, 4)) == (False, F(1, 4))
assert b.take(F(1, 2)) == (True, F(0))
assert b.take(100)[0] is True
assert b.tokens == 2  # idle time cannot exceed capacity
try:
    b.take(99)
except ValueError:
    pass
else:
    raise AssertionError("backward clock accepted")
print("burst, partial refill, idle cap and clock tests passed")

At one quarter second the empty bucket contains half a token, so the rejected request needs another quarter second. Rejections do not consume a token in this policy. That choice affects abuse resistance and should be documented rather than assumed.

From a class to multiple replicas

Two independent full buckets each admit three immediate requests: six in total. A per-tenant global burst of three therefore needs shared coordination or a deliberately partitioned quota. Redis documents atomic server-side Lua execution, but also says it blocks server activity during the script. A short script avoids a client-side read/modify/write race; it is not a zero-cost distributed lock replacement with unlimited scale.

This article intentionally does not publish an untested Lua deployment. A real shared implementation must define authoritative time, key placement, expiry, failover behavior, quota changes and bounded script runtime. If a depleted bucket expires before it could refill, recreating it full can grant extra capacity. On Redis Cluster, key locality and the supported execution contract matter. Benchmark the real operation, not this Python class.

Failure policy is a product decision

Do not make “always fail open” a universal rule. Losing the quota store during an expensive inference endpoint could turn an outage into an uncontrolled bill. Denying every low-risk public read might instead cause unnecessary unavailability. Options include fail closed, a conservative local emergency quota, or limited fail open. Each needs an owner, a time bound and monitoring; authentication and authorization never become optional because a limiter failed.

RFC 6585 defines 429 Too Many Requests and permits a Retry-After header; it does not mandate X-RateLimit-Reset. Round an estimated delay upward if expressing whole seconds, and tell clients to use bounded backoff rather than retry immediately. A limiter dependency failure is not necessarily a client quota violation, so do not label every infrastructure failure 429.

Exercises

  1. An idle bucket has capacity five and rate one/second. What happens to six simultaneous unit-cost requests?
  2. Why is this class not thread-safe merely because it has a method named take?
  3. A request costs four tokens but capacity is three. Should it wait forever?
Answers and reasoning
  1. Five are allowed and one is rejected with a one-second refill estimate.
  2. The read/modify/write sequence needs synchronization; the example is a single-threaded state machine. Multiple processes need a shared atomic authority or explicit quota partitioning.
  3. No. The request can never fit and the example rejects the configuration with an error. Waiting would hide a contract error.

Limits

The exact arithmetic tests the policy, not Redis, networking, authentication, fairness or denial-of-service resilience. One noisy tenant's requests may still cost far more than another's; admission should be tied to measured resource costs where appropriate.

Sources and verification boundary

Primary sources checked on 7 October 2026:

  • Redis: Scripting with Lua — Server-side scripts execute atomically with blocking semantics; key arguments must be explicit and script caches are volatile.
  • RFC 6585, section 4 — 429 means rate limiting; a Retry-After header is optional and a 429 response must not be cached.
  • Google SRE: Handling overload — Request costs vary; resource consumption, quotas, load shedding and retry behavior matter beyond aggregate requests per second.

The numerical fixtures and Python programs are teaching examples, not measurements of a deployed service. Python blocks were executed locally; no cloud deployment or model inference was performed.

Previous: Capacity estimates that survive an overload question. Track map.

Choose the contract before the algorithm

A rate limit identifies both a subject and a resource. An authenticated tenant can have a request budget and a separate expensive-query budget. A public IP is useful for coarse edge admission, but NAT can put unrelated people behind one address and a client can change addresses. Do not trust a caller-supplied tenant header without binding it to the authenticated principal. Before authentication, bounded IP/connection controls still have a role; after it, use the verified tenant or API-key identity. Avoid putting raw API secrets in counter keys.

The choices below are policy alternatives, not a universal ranking of accuracy or speed. RFC 2697 describes a byte-oriented token-bucket meter; this lesson adapts the same capped refill idea to request costs. Network packet coloring and HTTP rejection are different uses.

Token Bucket

The class above uses continuous refill: balance = min(B, balance + r × elapsed). A periodic refill is a different implementation that can introduce tick-boundary bursts. For any interval of duration t, a correctly coordinated continuous bucket can admit at most B + r × t units, including credit stored before the interval. That envelope follows by accounting for initial credit plus replenishment; it is not a hard r-requests-per-second window. Choose it when bounded bursts are welcome and cost can be represented in tokens.

Leaky Bucket

Here “leaky bucket” means a bounded queue with scheduled release, rather than a meter that only accepts or rejects. If five unit jobs arrive at once and the drain rate is two jobs/s, a schedule starting immediately releases them at 0, 0.5, 1, 1.5 and 2 seconds. This protects a backend's arrival rate but makes the last job wait two seconds. Bound queue length and waiting time; a backend slower than the drain rate still accumulates work. Do not promise constant completion rate when only dispatch is paced. Some literature uses leaky-bucket metering terminology, so specify which state machine is intended.

Fixed Window Counter

With a limit of 100 in each aligned minute, 100 requests at 59.9 seconds and another 100 at 60.1 seconds are both permitted. That is 200 in 0.2 seconds despite each aligned window meeting its quota. An atomic increment with correctly paired expiry prevents lost updates, not this boundary effect. Use fixed windows when their reset semantics are acceptable, not as an approximation silently advertised as a strict rolling bound.

Sliding Window Log

For a 60-second policy at time t, retain accepted timestamps in (t-60, t], remove older ones, count, then admit and append only if the count is below the limit. The endpoint convention matters for requests exactly 60 seconds apart. These operations must be atomic for one subject. A unique request identifier avoids overwriting equal timestamps in a sorted-set representation. Keeping rejected requests too would implement a different policy. State grows with retained admissions; cleanup also costs work. “Exact” means exact for the authority's recorded times, not immune to clock errors or lost state on failover.

Weighted sliding-window counter

Store only the previous and current aligned-window counts. Halfway through a minute with 80 previous requests and 20 current requests, estimate 80 × 0.5 + 20 = 60. The actual rolling count can be 20 if all previous requests were early, or 100 if they were late. The weighted estimate assumes a spread it does not observe. This saves timestamp storage, but it cannot certify a strict rolling quota. Test adversarial bursts as well as evenly spaced traffic before choosing the approximation.

Architecture: the shared decision and its failure boundary

The race is concrete: callers A and B both read one remaining token, both accept, and both write zero. A client-side lock can serialize the decision, but adds round trips and lease, owner-failure and timeout questions. A short Redis Lua operation moves the read/check/write to one server's atomic execution boundary. Redis blocks other server work while the script executes: this is serialization, not proof of better throughput or distributed durability. Keep every accessed key explicit, colocate related keys under the applicable Cluster rules, and do not assume atomic execution rolls back earlier writes after a script runtime error.

A deployment design must specify the refill time authority, numeric units, policy version, expiry and result on retry. Do not reuse one process's monotonic timestamp as if it were comparable across machines. A lost response after a debit makes retry semantics ambiguous: a repeated operation may spend another token unless the policy tracks request identity. Asynchronous replication/failover may lose recent state; the allowed overshoot depends on that failure model. These are conceptual design requirements, not an untested Lua recipe represented as production-ready code.

Where should the Rate Limiter live?

Place cheap coarse controls at the edge to avoid doing expensive work merely to reject it. Place business-cost checks where authenticated identity and the operation's cost are known. These may be gateway plugins or application middleware; no layer is inherently incapable of knowing a subscription tier. A hundred workers each allowing 10/s allow up to 1000/s, not a global 10/s. Leasing disjoint quota portions avoids a shared operation on every request, but unused allocations reduce utilization and reassigning an unexpired lease can overspend.

A policy update must define what happens to existing credit: reducing capacity from ten to three should clamp a balance of eight to three, not silently preserve eight spendable units. Distribute versioned limits, monitor inconsistent versions and test expiry during outages. For a limiter timeout, choose fail-closed, a bounded emergency allocation, or fail-open by endpoint risk. A low-risk read and an expensive inference operation need not share a policy. Keep authorization mandatory and record degraded enforcement separately from ordinary 429s.

Compare policies with a trace

Attempt this before opening the solution: a full token bucket has capacity four and rate one/s; a fixed-window limiter allows four per aligned four-second window; a sliding log allows four in (t-4,t]. Four requests arrive at t=3.9, then four at t=4.1.

Admission decisions and what they protect

The token bucket admits the first four and rejects the next four: only 0.2 tokens have returned. The fixed window admits all eight because the boundary reset its count. The sliding log rejects the second group because all four earlier admissions remain in its rolling window. None of these policies limits concurrent work if a request runs indefinitely; use separate concurrency limits and deadlines. A queue-based leaky bucket could accept jobs for later dispatch, but must state queue capacity and response/wait semantics.

What to carry forward

Choose identity, resource unit, time interval, burst tolerance and outage policy together. An atomic operation repairs the lost-update race inside its authority, not every distributed failure. A reference state-machine test and a documented implementation contract are enough to study this design; production acceptance additionally needs a pinned Redis deployment, failover experiments and workload measurements.

Additional primary specifications: RFC 2697, September 1999 and RFC 6585, April 2012. Redis behavior follows the access-dated server-side scripting documentation, not a claim that a particular Redis version was deployed.

Pause / Recall / Apply

Can you explain it without the page?

Close the example. Reconstruct the core idea, then change one assumption. Mark complete when you’re ready; you can always undo it.

Stored in this browser only. No account, no sync. Clearing browser data removes your record.