Building a Rate Limiter Library

The problem

One client retries in a tight loop, a batch job forgets to sleep, a scraper finds your search endpoint. Without a limit, a single caller can use up the capacity meant for everyone. A rate limiter answers one question on every request: may this caller proceed right now? It has to answer in microseconds, under heavy concurrency, and it must never become the bottleneck it was meant to prevent.

This post builds an in-process limiter: one service, one memory space. Part 11 moves the same idea into a shared store so a fleet of servers can agree on a single budget.

Requirements

Functional

Limit by key: user, API key or IP.
A steady rate plus a short burst.
Tell rejected callers when to retry.

Non-functional

O(1) time and memory per key.
Safe for concurrent use.
Deterministic in tests.

Choosing an algorithm

Four designs come up again and again. They differ in how much they remember about each caller and in what they do at the edge of a window.

Algorithm	Memory per key	Bursts	Accuracy
Fixed window	O(1)	Up to 2× at window edges	Low
Sliding log	O(n)	None allowed	Exact
Sliding window counter	O(1)	Smoothed	Approximate
Token bucket	O(1)	Configurable	Exact for rate

Table 1 · n is the number of requests in the window. The highlighted row is the one we build.

The token bucket wins for a library: two numbers per key, a burst you can tune separately from the rate, and no timers running in the background.

How a token bucket works

Token bucket diagramPNG or SVG · 1600 × 900 · light background

Figure 1 · Refill at r tokens per second into a bucket that holds at most b. Each request takes one token: allowed, or 429 when empty. The rate sets the long-run average; the capacity sets how big a burst can be.

There is no background refill loop. Each time a request arrives we work out how many tokens would have dripped in since the last request, add them, cap at the capacity, and then try to spend one. Time does the bookkeeping for us.

The core

The bucket stores a token count and the time it was last updated. The Clock interface is the only concession to testing, and it costs nothing at runtime.

ratelimit/bucket.go

1package ratelimit2
3import (4	"math"5	"sync"6	"time"7)8
9// Clock exists so tests can move time forward without sleeping.10type Clock interface{ Now() time.Time }11
12type Bucket struct {13	mu       sync.Mutex14	clock    Clock15	tokens   float6416	capacity float6417	rate     float64 // tokens per second18	last     time.Time19}20
21func (b *Bucket) Allow() bool {22	b.mu.Lock()23	defer b.mu.Unlock()24
25	now := b.clock.Now()26	elapsed := now.Sub(b.last).Seconds()27	b.tokens = math.Min(b.capacity, b.tokens+elapsed*b.rate)28	b.last = now29
30	if b.tokens < 1 {31		return false32	}33	b.tokens--34	return true35}

Listing 1 · The highlighted line is the whole refill: elapsed time × rate, capped at capacity.

Tokens are a float64 on purpose. At 2 requests per second, a request 300 ms after the last one earns 0.6 of a token; rounding that away would make the limiter stricter than configured.

One bucket per client

A limiter keeps a map from key to bucket. The map lock is held only long enough to find or create the bucket; the bucket's own lock does the rest, so two different clients never wait on each other.

ratelimit/limiter.go

1type Limiter struct {2	mu       sync.Mutex3	buckets  map[string]*Bucket4	rate     float645	capacity float646	clock    Clock7}8
9func (l *Limiter) Allow(key string) bool {10	l.mu.Lock()11	b, ok := l.buckets[key]12	if !ok {13		b = &Bucket{clock: l.clock, tokens: l.capacity, capacity: l.capacity, rate: l.rate, last: l.clock.Now()}14		l.buckets[key] = b15	}16	l.mu.Unlock()17
18	return b.Allow()19}20
21func (l *Limiter) Middleware(next http.Handler) http.Handler {22	return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {23		if !l.Allow(clientKey(r)) {24			w.Header().Set("Retry-After", "1")25			http.Error(w, "rate limit exceeded", http.StatusTooManyRequests)26			return27		}28		next.ServeHTTP(w, r)29	})30}

Listing 2 · Per-key buckets and an HTTP middleware that answers 429 with a Retry-After header.

Testing with a fake clock

Tests that call time.Sleep are slow and flaky. With an injected clock, the test moves time forward itself and every assertion is exact.

ratelimit/bucket_test.go

1type fakeClock struct{ now time.Time }2
3func (c *fakeClock) Now() time.Time      { return c.now }4func (c *fakeClock) Advance(d time.Duration) { c.now = c.now.Add(d) }5
6func TestBucketRefills(t *testing.T) {7	clock := &fakeClock{now: time.Unix(0, 0)}8	b := &Bucket{clock: clock, tokens: 2, capacity: 2, rate: 1, last: clock.Now()}9
10	if !b.Allow() || !b.Allow() {11		t.Fatal("a fresh bucket should allow a full burst")12	}13	if b.Allow() {14		t.Fatal("an exhausted bucket should reject")15	}16
17	clock.Advance(time.Second)18	if !b.Allow() {19		t.Fatal("one second should refill exactly one token")20	}21}

Listing 3 · Burst, exhaust, refill: the three behaviours that matter, tested without sleeping.

The refill shown in Listing 1 is what makes this testable: no goroutine, no ticker, nothing to wait for.

Trade-offs

Good fit

A single service or sidecar.
Protecting a downstream dependency.
Smoothing bursts from background jobs.

Not a fit

Quotas shared across many replicas.
Limits that must survive a restart.
Billing-grade, per-request accounting.

Every one of the "not a fit" cases comes down to state that has to live outside the process. That is where the series goes next.