heyrian.dev
← Applied algorithms
Smaller data, steadier systems From a burst of requests to a fair 429

Token bucket

Save up a burst. Hold the pace.

You have met this one from the other side: 429 Too Many Requests. Stripe’s engineers wrote that they “use the token bucket algorithm to do rate limiting,” and Amazon API Gateway’s documentation says it “throttles requests to your API using the token bucket algorithm.”

So let’s build that bucket for an API of our own. Each key saves up five requests for a burst and earns one more every second. When a key runs dry, it hears 429 and exactly how long to wait.

TypeScriptGoOne API-key limit in each language

01 / The idea

Let a burst through, then hold the pace.

A client app opening a dashboard might fire five requests in the same instant, then go quiet. That’s ordinary, and a limit should allow it. A script calling the API all afternoon is different. You want one limit that says yes to the first and slows the second.

A counter that resets every second struggles with that. At five per second, five requests just before the reset and five just after all get through: ten in a moment.

A token bucket admits a request only if it holds enough tokens, and refills tokens at a steady rate up to a fixed capacity. The capacity is the burst you allow. The refill rate is the pace you allow over time.

Watch one key spend its burst, sit idle, and then send requests faster than the bucket refills.

Token bucket

Save up a burst. Hold the pace.

5-TOKEN BUCKET · ONE TOKEN EVERY 1,000 MS t = 0 ms

5 of 5 tokens saved

Waiting for the first request.

01/ 03
Spend the burst

A full bucket lets the burst in.

Seven requests arrive at once. A new key starts with 5 tokens, so the first 5 are admitted. The other 2 are rejected and told to retry in 1,000 ms, the time one token takes to refill.

Reduced motion: choose a scene to see its completed state.

Read this scene

Seven requests arrive at once. A new key starts with 5 tokens, so the first 5 are admitted. The other 2 are rejected and told to retry in 1,000 ms, the time one token takes to refill.

At 0 ms, 5 of 5 tokens are saved. 0 requests decided: 0 admitted, 0 rejected. No requests yet.

Watch and Step through replay one key's requests. Try it runs the same TypeScript bucket on a clock that moves only when you press Wait, and starts fresh each time you open it.

Rejected requests aren’t kept waiting. The bucket answers straight away, and a rejection says how long until that request would fit.

02 / Name the rule

Save refill time, not fractions of a token.

Our key’s bucket has a capacity of 5 tokens and earns one token every refill interval of 1,000 ms. A request costs 1 token. Some APIs charge more for expensive calls, so a cost can be larger.

Capacity

5 tokens

The biggest burst. A new key starts full.

Refill

1 token per 1,000 ms

The pace over time. Refill stops at capacity.

Decision

Admit or reject

Enough tokens now: spend them. Otherwise, say no and say when.

Here is what keeps the arithmetic exact. Instead of storing tokens as a fraction like 2.5, the bucket stores saved time in whole milliseconds. One token is 1,000 saved ms, a full bucket is 5,000, and every millisecond that passes adds one, up to the top. A request costing c needs c × 1,000 saved ms. If the time is there, spend it. If not, the shortfall is the wait: 400 ms short means retry in 400 ms.

Two rules hold after every call: saved time stays between zero and a full bucket, and the clock never moves backward. One guarantee follows from them. In any stretch of t milliseconds, a key can spend at most a full bucket plus t ms of refill.

Why that guarantee holdsFrom the two rules

At the start of any stretch, at most a full bucket is saved. During it, refill adds at most the milliseconds that pass. Every admitted request spends what it costs, and saved time never drops below zero. So everything spent fits inside what was saved plus what arrived.

Both test suites check it on random traffic: 200 rounds of 60 requests with random capacities, refill intervals, costs, and gaps, comparing every window.

03 / Read the shape

One bucket, one key, one call site.

Basic form is the bucket: level reads saved time without spending, and take refills, then admits or rejects. In the wild keeps one bucket per API key and turns a rejection into a 429 with a Retry-After header. The TypeScript version returns the status and the header’s value for your server framework to send; the Go version also shows the http.Handler middleware that sets them. At the call site replays a burst and a partial refill, then two keys. Both languages print the same fourteen lines.

The bucket for one key. Saved refill time in whole milliseconds, level to read it, and take to refill, then admit or reject with the wait.

TypeScriptReading
bucket.ts
// A token bucket for one API key. It saves refill time in whole milliseconds, so every step
// is exact integer arithmetic: one token is refillMs of saved time.
export const MAX_CAPACITY = 1000;
export const MAX_REFILL_MS = 3_600_000; // one token an hour at the slowest
export const MAX_CLOCK_MS = 2 ** 50; // keeps saved time plus elapsed time exact in a number

export type BucketErrorCode = 'bad-limits' | 'bad-cost' | 'bad-time' | 'time-backward';

export class BucketError extends Error {
	readonly code: BucketErrorCode;
	constructor(code: BucketErrorCode, message: string) {
		super(message);
		this.name = 'BucketError';
		this.code = code;
	}
}

export type Limits = { capacity: number; refillMs: number };

export type Decision = {
	admitted: boolean;
	banked: number; // saved milliseconds left after this decision
	retryAfterMs: number | null; // if rejected: time until this cost fits, or null if it never can
};

const whole = (n: number, min: number, max: number) =>
	Number.isSafeInteger(n) && n >= min && n <= max;

function checkTime(ms: number) {
	if (!whole(ms, 0, MAX_CLOCK_MS))
		throw new BucketError('bad-time', `times are whole milliseconds from 0 to ${MAX_CLOCK_MS}`);
}

export class TokenBucket {
	readonly capacity: number;
	readonly refillMs: number;
	#banked: number;
	#last: number;

	constructor(limits: Limits, startMs: number) {
		if (!whole(limits.capacity, 1, MAX_CAPACITY) || !whole(limits.refillMs, 1, MAX_REFILL_MS))
			throw new BucketError(
				'bad-limits',
				`capacity must be 1 to ${MAX_CAPACITY} tokens and refillMs 1 to ${MAX_REFILL_MS}`
			);
		checkTime(startMs);
		this.capacity = limits.capacity;
		this.refillMs = limits.refillMs;
		this.#banked = limits.capacity * limits.refillMs; // a new bucket starts full
		this.#last = startMs;
	}

	// Saved time at nowMs, without spending any. Refill stops when the bucket is full.
	level(nowMs: number): number {
		checkTime(nowMs);
		if (nowMs < this.#last)
			throw new BucketError('time-backward', 'the clock went backward; use a monotonic clock');
		return Math.min(this.capacity * this.refillMs, this.#banked + (nowMs - this.#last));
	}

	take(nowMs: number, cost = 1): Decision {
		const banked = this.level(nowMs);
		if (!whole(cost, 1, MAX_CAPACITY))
			throw new BucketError('bad-cost', `cost must be 1 to ${MAX_CAPACITY} tokens`);
		this.#banked = banked;
		this.#last = nowMs;
		const needed = cost * this.refillMs;
		if (cost > this.capacity) return { admitted: false, banked, retryAfterMs: null };
		if (banked < needed) return { admitted: false, banked, retryAfterMs: needed - banked };
		this.#banked = banked - needed;
		return { admitted: true, banked: this.#banked, retryAfterMs: null };
	}
}
GoAlongside
bucket.go
// A token bucket for one API key. It saves refill time in whole milliseconds, so every step
// is exact integer arithmetic: one token is refillMs of saved time.
const (
	MaxCapacity = 1000
	MaxRefillMs = 3_600_000 // one token an hour at the slowest
	MaxClockMs  = 1 << 50   // the same bound as the TypeScript version
)

// BucketError carries the same codes as the TypeScript version.
type BucketError struct {
	Code    string
	Message string
}

func (e *BucketError) Error() string { return e.Message }

type Limits struct {
	Capacity int
	RefillMs int64
}

type Decision struct {
	Admitted     bool   `json:"admitted"`
	Banked       int64  `json:"banked"`       // saved milliseconds left after this decision
	RetryAfterMs *int64 `json:"retryAfterMs"` // if rejected: time until this cost fits; nil if it never can
}

type TokenBucket struct {
	capacity int
	refillMs int64
	banked   int64
	last     int64
}

func checkTime(ms int64) error {
	if ms < 0 || ms > MaxClockMs {
		return &BucketError{"bad-time", fmt.Sprintf("times are whole milliseconds from 0 to %d", int64(MaxClockMs))}
	}
	return nil
}

func NewTokenBucket(limits Limits, startMs int64) (*TokenBucket, error) {
	if limits.Capacity < 1 || limits.Capacity > MaxCapacity || limits.RefillMs < 1 || limits.RefillMs > MaxRefillMs {
		return nil, &BucketError{"bad-limits", fmt.Sprintf("capacity must be 1 to %d tokens and refillMs 1 to %d", MaxCapacity, MaxRefillMs)}
	}
	if err := checkTime(startMs); err != nil {
		return nil, err
	}
	full := int64(limits.Capacity) * limits.RefillMs // a new bucket starts full
	return &TokenBucket{capacity: limits.Capacity, refillMs: limits.RefillMs, banked: full, last: startMs}, nil
}

func (b *TokenBucket) full() int64 { return int64(b.capacity) * b.refillMs }

// Level is the saved time at nowMs, without spending any. Refill stops when the bucket is full.
func (b *TokenBucket) Level(nowMs int64) (int64, error) {
	if err := checkTime(nowMs); err != nil {
		return 0, err
	}
	if nowMs < b.last {
		return 0, &BucketError{"time-backward", "the clock went backward; use a monotonic clock"}
	}
	return min(b.full(), b.banked+(nowMs-b.last)), nil
}

func (b *TokenBucket) Take(nowMs int64, cost int) (Decision, error) {
	banked, err := b.Level(nowMs)
	if err != nil {
		return Decision{}, err
	}
	if cost < 1 || cost > MaxCapacity {
		return Decision{}, &BucketError{"bad-cost", fmt.Sprintf("cost must be 1 to %d tokens", MaxCapacity)}
	}
	b.banked, b.last = banked, nowMs
	needed := int64(cost) * b.refillMs
	if cost > b.capacity {
		return Decision{Admitted: false, Banked: banked}, nil
	}
	if banked < needed {
		wait := needed - banked
		return Decision{Admitted: false, Banked: banked, RetryAfterMs: &wait}, nil
	}
	b.banked = banked - needed
	return Decision{Admitted: true, Banked: b.banked}, nil
}
Reading the TypeScriptPrivate fields, a thrown error, and null

#banked and #last are private, so only take changes them. Errors are a BucketError whose code matches the Go version. A request that can never fit returns retryAfterMs: null rather than a wait that would never be enough.

Times are whole milliseconds up to 250. That bound keeps saved time plus elapsed time exact in a JavaScript number.

Reading the Goint64 milliseconds, a nil pointer, and a mutex

Times and saved time are int64 milliseconds. RetryAfterMs is a *int64: nil when the cost can never fit, like TypeScript’s null.

KeyedLimiter holds a mutex around its map and buckets, so two handlers can’t spend the same token. A test sends 200 goroutines at a 50-token bucket and counts exactly 50 admissions. Middleware wraps any http.Handler.

What is refused before any decisionLimits, costs, and times

Capacity is 1 to 1,000 tokens, the refill interval 1 to 3,600,000 ms, a cost 1 to 1,000 tokens, and a time 0 to 250 ms. Anything else is an error: bad-limits, bad-cost, or bad-time, and a time earlier than the last call is time-backward. An invalid call changes nothing.

A valid cost above this bucket’s capacity is not an error. It is a rejection with no retry time, because no amount of waiting makes it fit.

04 / Try a decision

Two and a half tokens is not three.

A different key has a smaller bucket: 4 tokens, one every 500 ms. It spends all four at once. Before you answer, work out how much time it has saved 1,250 ms later.

A key with 4 tokens, refilled one every 500 ms, spends all four at 0 ms. At 1,250 ms it sends three more requests at once. What happens?

05 / Follow the cost

Constant work per request, memory per key.

Token bucket: time and extra space per operation
OperationTimeExtra spaceWhat it assumes
Decide one requestO(1)O(1)A few integer operations. No history of earlier requests.
Read the levelO(1)O(1)The same refill arithmetic, without spending anything or moving the clock.
Handle a request for a keyO(1) averageO(1)One map lookup, plus one new bucket the first time a key is seen. Go also takes a mutex.
Forget idle keysO(k)O(1)Reads the level of each of the k keys and removes the full ones.
Hold k keys—O(k)Two changing numbers per key, saved time and when it was last touched, plus its fixed limits, however busy the key is.

The row worth a second look is the last one. A limit that stored the time of every recent request would grow with traffic. The bucket keeps two changing numbers and its two limits per key, no matter how busy the key is. What grows is the number of keys.

And a full bucket behaves exactly like a brand-new one: both admit the same burst and refill at the same pace from here on. So forgetIdle can drop full buckets without changing any future answer, and a key that comes back starts full again.

06 / Give it a real job

Answer 429, and say when to come back.

Put a bucket per API key in front of a search endpoint. The status code has a standard meaning: RFC 6585 defines 429 as “the user has sent too many requests in a given amount of time (‘rate limiting’),” and the response “MAY include a Retry-After header indicating how long to wait before making a new request.” RFC 9110 lets Retry-After be a date or a number of seconds.

Seconds are coarser than our milliseconds, so the handler rounds up: 1,400 ms becomes Retry-After: 2. A client that waits the full two seconds finds its token there, as long as nothing else spent it first. A request with no key never reaches a bucket; it gets 401.

This bucket lives in one process. Run three copies of the API behind a load balancer and each copy has its own buckets, so a key can spend up to three times its limit. RFC 6585 leaves that to you: a server can count requests “on a per-resource basis, across the entire server, or even among a set of servers.” A limit shared by every instance needs shared state that they all update, and that is a different problem from the arithmetic here.

Measure with a clock that never runs backward

The bucket assumes time only moves forward, and a wall clock doesn’t promise that. MDN notes that Date.now() “may have been impacted by system and user clock adjustments,” while performance.now() is relative to a monotonic clock whose “current time never decreases.” In Go, time.Now carries a monotonic reading used by “comparisons and subtractions,” so time.Since(start) is safe. That is what MonotonicMillis does.

If an earlier time still arrives, our bucket refuses it with time-backward and changes nothing, and the Go middleware answers 500. Go’s golang.org/x/time/rate makes a different choice: in v0.16.0, an earlier time counts as no time passing for that call. Choose one on purpose, and test it.

The other end is easy. A key idle for an hour doesn’t come back with 3,600 tokens. Refill stops at capacity, which is exactly what keeps the burst a limit.

Already written for you in Gogolang.org/x/time/rate v0.16.0

The package docs say a Limiter “implements a ‘token bucket’ of size b, initially full and refilled at rate r tokens per second.” AllowN answers yes or no for “if you intend to drop / skip events that exceed the rate limit”; WaitN “blocks until lim permits n events to happen,” which turns rejection into waiting.

It keeps tokens as a float64 (rate.go). For a Go service that needs a process-local limiter, reach for it. Our version keeps whole milliseconds so every number in this lesson can be checked in both languages.

The bucket runs on the API server, in front of the endpoint it protects; nothing in a component computes it. What reaches your fetch is its answer. When a request comes back 429, the server’s bucket for your key is empty: read Retry-After and wait at least that long, since retrying straight away usually earns another 429. On a cross-origin request, response.headers.get('Retry-After') returns null unless the API lists the header in Access-Control-Expose-Headers: it isn’t one of the CORS-safelisted response headers. Without it, fall back to your own backoff. Spacing retries in general has its own lesson, Retry, backoff & idempotency.

07 / Make the call

Admit now, delay, or queue?

A token bucket answers immediately: yes, or no and when. That suits an API, where the client decides what to do with a 429.

Other limiters make a different choice. nginx’s limit_req says its limitation “is done using the ‘leaky bucket’ method.” With a burst set, excessive requests are delayed until their number exceeds that burst, and only then rejected, with status 503 unless you set limit_req_status. Delaying means holding requests in line; if waiting is what you want, Backpressure & queues is about exactly that.

Reach for something else when the limit isn’t about pace. A monthly quota is a counter that resets on a date. A limit shared across servers needs shared state. And five per second with no burst at all is a bucket with capacity 1 and a 200 ms refill, which spaces requests out.

SourcesStandards, services, and packages, checked 13 September 2026

Stripe and API Gateway are named for what their own writing says about their limits. Our API and its numbers are an illustration, not either service’s implementation.

08 / Take the idea with you

Explain the 429 without saying “token bucket.”

“Each key saves up to five requests’ worth of time and earns one more every second. A request spends what it costs if the time is there. If it isn’t, we say no, and we say how long.”

Before moving on, open the rate-limit page of an API you use. Find the burst and the sustained rate, and work out how long a client that just used its whole burst has to wait for one more request.

Connections to follow nextRelated lessons

Copy the complete example, change the first bucket to capacity 1 with a 200 ms refill, and predict which requests in the burst survive before you run it.

Back to applied algorithms →