Token Bucket Refill Precision and Clock Sources

A token bucket is two numbers and one multiplication, and every production bug in one comes from the multiplication’s inputs: which clock produced now, what resolution it has, and what happens when it moves backwards. This page is the precision companion to the token bucket implementation guide, covering the clock choices that decide whether your advertised rate is what clients actually get.

The problem in concrete numbers

A limiter allows 5 requests per second and stores ts in whole seconds. Two requests arrive 200 ms apart within the same second: elapsed = 0, so no tokens refill — correct. But a request arriving 999 ms after the previous one, in the next whole second, computes elapsed = 1 and refills a full second’s worth, 5 tokens, for 1 ms of real time. Over a busy minute the bucket refills far faster than the rate allows and the effective limit drifts upward by tens of per cent.

Switch ts to milliseconds and the same sequence refills 0.005 tokens — correct. Second-resolution timestamps are the single most common precision bug in hand-rolled limiters, and they always fail in the client’s favour, so they are discovered during a capacity incident rather than a test.

Clock source reference

The rule that resolves most arguments: shared state must use the store’s clock; in-process state should use a monotonic clock. Mixing the two — refilling with a monotonic reading and persisting a wall-clock timestamp — produces state that is nonsense the moment the process restarts.

Step-by-step: a precise refill

• Store timestamps as integer milliseconds; never seconds, never floats.
• Read now from the same source that produced the stored timestamp.
• Clamp elapsed time at zero: elapsed = max(0, now - ts).
• Cap the refill at capacity before comparing against cost, so a long idle period cannot overflow.
• Compare with a small epsilon, or round tokens to a fixed precision, so 0.9999999 does not reject a valid request.
• Always write the new timestamp, even on a denial, so the next refill measures from the right instant.
• Persist tokens with bounded precision — three decimal places is ample and avoids float drift accumulating.
• Assert in tests that a long idle period yields exactly capacity, no more.

-- Precise refill: integer ms, clamped elapsed, capped capacity, epsilon compare.
local EPS = 1e-9
local cap  = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])          -- tokens per second
local cost = tonumber(ARGV[3]) or 1

-- One clock for every caller, in milliseconds.
local t   = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local st     = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(st[1]) or cap
local ts     = tonumber(st[2]) or now

-- Clamp: a clock correction must never produce a negative refill.
local elapsed = math.max(0, now - ts)
tokens = math.min(cap, tokens + elapsed / 1000 * rate)

local allowed = 0
if tokens + EPS >= cost then            -- epsilon: 0.9999999999 is one token
  tokens  = tokens - cost
  allowed = 1
end

-- Round to 3 dp so repeated float writes cannot accumulate drift.
tokens = math.floor(tokens * 1000 + 0.5) / 1000

-- Write the timestamp on BOTH paths, or the next refill measures from stale time.
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate * 1000) + 1000)

local retry = 0
if allowed == 0 then retry = math.ceil((cost - tokens) / rate * 1000) end
return { allowed, math.floor(tokens), retry }

Gotchas and edge cases

• Mixing clocks between read and write. Refilling with a monotonic reading and storing a wall-clock timestamp produces an elapsed value that is meaningless. Pick one source per state.
• Passing the application’s clock into a shared script. Every node’s skew is written into shared state; read the store’s clock instead, as the clock skew page covers in detail.
• Not writing the timestamp on denial. The next refill then measures from an older instant and grants a larger refill than elapsed time justifies.
• Unbounded float precision. Repeatedly storing 0.30000000000000004 and reading it back accumulates noise and makes tests platform-dependent. Round to a fixed precision.
• Refill capped after the comparison. Capping tokens after checking tokens >= cost lets a long idle period admit more than capacity in one burst.
• Monotonic clocks across process restarts. performance.now() restarts at zero, so persisted state computed from it produces enormous elapsed values on the next boot. Never persist monotonic readings.
• Leap seconds and container suspend. Both produce jumps in wall time. Clamping handles backwards jumps; forward jumps simply refill to capacity, which is harmless.

Verification and testing

# refill_test.py — assert precision across resolutions and clock anomalies.
import math

def refill(tokens, ts, now, cap, rate):
    elapsed = max(0, now - ts)                       # clamp
    return min(cap, tokens + elapsed / 1000 * rate)  # cap after refill

CAP, RATE = 5, 5           # 5 tokens, 5 per second

# 1. A millisecond past a boundary refills a millisecond's worth, not a second's.
assert abs(refill(0, 1_000, 1_001, CAP, RATE) - 0.005) < 1e-9

# 2. A long idle period refills to exactly capacity, never beyond.
assert refill(0, 0, 3_600_000, CAP, RATE) == CAP

# 3. A backwards clock step leaves the bucket untouched.
assert refill(2.5, 10_000, 5_000, CAP, RATE) == 2.5

# 4. Accumulated drift over a million operations stays negligible.
tokens, ts = float(CAP), 0
for i in range(1, 1_000_001):
    now = i * 7                                       # a request every 7 ms
    tokens = refill(tokens, ts, now, CAP, RATE); ts = now
    if tokens >= 1: tokens -= 1
expected_max = CAP
assert tokens <= expected_max + 1e-6, tokens
print("refill precision OK")

Add the same four assertions to whatever language your limiter is written in. They take minutes to write and cover the entire class of precision bug that otherwise surfaces as “our limit is 20% looser than we documented.”

Frequently Asked Questions

Related

• Token Bucket Implementation — the parent guide with the full algorithm and state model.
• Handling Clock Skew in Distributed Limiters — the fleet-wide version of the clock problem.
• GCRA vs Token Bucket Precision — an algorithm that avoids float accumulation entirely.
• Redis vs In-Memory Token Bucket — where the state lives, and therefore which clock applies.