Explainer · Rate limiting

Token bucket rate limiting

How one small data structure lets clients burst when they've been quiet, while still holding them to an average rate — and the production details that the textbook version leaves out.

A bucket holds up to b tokens and refills at r tokens per second. Each request spends a token; no token, no admission.
That gives you two knobs with clear meanings: b is the largest burst, r is the sustained rate.
You never need a timer. Refill is computed lazily from elapsed time whenever a request arrives.

The mental model

Picture a bucket under a dripping tap. Each drip is a token. A request may pass only if it can take a token out. If the bucket is full, the extra drips spill away and are lost.

That spill is the whole design. Saving is capped at b tokens, so a client that has been idle for an hour can't then fire an hour's worth of requests at once.The token bucket is equivalent to GCRA (the generic cell rate algorithm) from ATM networking. GCRA stores one timestamp instead of a token count and a timestamp. A client that has been idle for at least b/r seconds starts with a full bucket.

The limiter is the only thing that moves. Refill isn't a background process. It is calculated when a request arrives.

How a request is decided

A request arrives at the limiter with a timestamp now.

Refill lazily. Add (now − last) × r tokens and clamp to b. Anything over the cap spills. Store last = now.

Try to take a token. If tokens ≥ 1, subtract one. A request can cost more than one token. Weight expensive endpoints that way.

Admitted. Forward the request. The state for this client is just two numbers: tokens and last.

Rejected. Return 429 with Retry-After = (1 − tokens) / r. The client knows exactly how long to wait, so it doesn't need to guess with a backoff.

Watch it run

The slots show tokens in the bucket, and the partly filled slot is the next token arriving. Below them is the last ten seconds of requests. Set the background traffic, then press Burst ×10 and watch the bucket drain.

Capacity b Refill rate r (tokens/s) Background traffic (req/s)

Tokens 0 · admitted 0 · rejected 0 · refill from empty takes s

b = 10, r = 1/s, bucket full. A client sends 15 requests at once, then 1 per second. What happens?

The first 10 are admitted and the next 5 are rejected. After that, every request at 1 per second is admitted. Each one spends the single token that arrived in the second before it, so the bucket stays almost empty. The client can't burst again until it slows below r and lets tokens build up.

Choosing b and r

Start from what the downstream system can take, not from what clients would like to send.

r: The sustained rate you can serve for every client at once, with headroom. If 200 clients share a backend that handles 10k req/s, the fair share is r ≈ 50.
b: The largest legitimate burst, such as a page load fanning out into parallel API calls. Too small and real users hit 429s. Too large and one client can saturate a replica briefly.
cost: Requests don't all weigh the same. Charge a report export 20 tokens and a health check 0.

Implementation

The core is about ten lines. The distributed version moves the same arithmetic into Redis, so the read-modify-write is atomic.

use std::time::{Duration, Instant};

pub struct TokenBucket {
    capacity: f64, // b — largest burst
    rate: f64,     // r — tokens per second
    tokens: f64,
    last: Instant, // monotonic clock: immune to NTP jumps
}

impl TokenBucket {
    pub fn new(capacity: f64, rate: f64) -> Self {
        Self { capacity, rate, tokens: capacity, last: Instant::now() }
    }

    /// Ok(()) if admitted, otherwise Err(how long until `cost` tokens exist).
    pub fn try_acquire(&mut self, cost: f64) -> Result<(), Duration> {
        let now = Instant::now();
        let elapsed = now.duration_since(self.last).as_secs_f64();
        self.tokens = (self.tokens + elapsed * self.rate).min(self.capacity);
        self.last = now;

        if self.tokens >= cost {
            self.tokens -= cost;
            Ok(())
        } else {
            Err(Duration::from_secs_f64((cost - self.tokens) / self.rate))
        }
    }
}

type Bucket struct {
	mu       sync.Mutex
	capacity float64 // b
	rate     float64 // r, tokens per second
	tokens   float64
	last     time.Time
}

func (b *Bucket) TryAcquire(cost float64) (ok bool, retryAfter time.Duration) {
	b.mu.Lock()
	defer b.mu.Unlock()

	now := time.Now() // carries a monotonic reading; Sub() uses it
	b.tokens = math.Min(b.capacity, b.tokens+now.Sub(b.last).Seconds()*b.rate)
	b.last = now

	if b.tokens >= cost {
		b.tokens -= cost
		return true, 0
	}
	return false, time.Duration((cost - b.tokens) / b.rate * float64(time.Second))
}

-- KEYS[1] = bucket key
-- ARGV    = capacity, rate (tokens/s), now (ms, from the Redis TIME command), cost
local b, r, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])

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

tokens = math.min(b, tokens + math.max(0, now - ts) / 1000 * r)
local ok = tokens >= cost
if ok then tokens = tokens - cost end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(b / r * 1000) + 1000) -- idle keys vanish when full
return { ok and 1 or 0, tostring(tokens) }

How it compares

Algorithm	Bursts	State per key	Boundary spikes	Best for
Token bucket	Up to b	2 numbers	None	APIs: tolerate bursts, enforce an average
Leaky bucket (queue)	Smoothed	queue	None	Shaping output to a fixed rate
Fixed window	Up to 2× at edges	1 counter	Yes	Coarse quotas (per day)
Sliding log	Exact	N timestamps	None	Low volume, exact limits
Sliding window counter	Approximate	2 counters	Small	A cheap approximation of the log

Gotchas in production

Go deeper: why return Retry-After?

Clients that get a bare 429 back off blindly, usually with exponential backoff, and often all at the same moment. You already know when the next token will exist, so tell them. That turns a stampede of retries into an orderly queue.

The mental model

How a request is decided

Watch it run

Choosing b and r

Implementation

How it compares

Gotchas in production

Further reading