Engineering Atlas › Low-Level Design

Code a rate limiter with swappable algorithms

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional:

Non-functional:

Out of scope: sharing limits across servers, persisting state across restarts, and per-route configuration loading. Extensibility covers the first.

Entities and relationships

Class diagram

classDiagram
    class RateLimiter {
        <<interface>>
        +allow(key) bool
    }
    class Clock {
        <<interface>>
        +nowMs() long
    }
    class TokenBucketLimiter {
        -int capacity
        -double refillPerSecond
        -Map buckets
        +allow(key) bool
    }
    class SlidingWindowLimiter {
        -int limit
        -long windowMs
        -Map windows
        +allow(key) bool
    }
    class Bucket {
        +double tokens
        +long lastRefillMs
    }
    class Window {
        +long start
        +int previousCount
        +int currentCount
    }
    class CompositeLimiter {
        -List limiters
        +allow(key) bool
    }
    RateLimiter <|.. TokenBucketLimiter
    RateLimiter <|.. SlidingWindowLimiter
    RateLimiter <|.. CompositeLimiter
    TokenBucketLimiter --> Clock
    SlidingWindowLimiter --> Clock
    TokenBucketLimiter *-- Bucket
    SlidingWindowLimiter *-- Window
    CompositeLimiter o-- RateLimiter

Key flows

A token-bucket check, with the lock held for the whole read-modify-write:

sequenceDiagram
    participant MW as Middleware
    participant TB as TokenBucketLimiter
    participant C as Clock
    participant M as Bucket map
    MW->>TB: allow("api-key-42")
    TB->>TB: lock
    TB->>C: nowMs()
    C-->>TB: 10500
    TB->>M: get or create bucket
    M-->>TB: tokens 0.2, last 10000
    TB->>TB: tokens = min(cap, 0.2 + 500 ms x rate)
    TB->>TB: if tokens >= 1 then take one
    TB->>TB: unlock
    TB-->>MW: true or false
    MW-->>MW: forward, or reply 429 with Retry-After

The token bucket starts each key full. Every call adds elapsed × rate tokens, caps the total at capacity, and spends one token if at least one is there. Capacity sets the largest burst and the rate sets the long-run average. A bucket with capacity 10 and 5 tokens per second allows a burst of 10 and then 5 per second.

The sliding-window counter splits time into fixed windows but smooths the edge between them. It estimates the count over the last windowMs as previousCount × (windowMs − elapsedInCurrent) / windowMs + currentCount. Take a limit of 4 per second. A key that made 4 requests in the previous second and is now 500 ms into the current one has an estimate of 4 × 0.5 = 2. Two more requests fit. A plain fixed window would let 4 more through right after the boundary, which doubles the rate across the edge. A sliding log fixes that exactly by storing every timestamp, but it costs O(L) memory per key. The counter version costs two integers and is accurate to within a few percent when traffic is spread fairly evenly across the window.

Design patterns used and why

Concurrency and edge cases

allow is a read-modify-write: read tokens, compute, write tokens. Two threads that both read 1 token can both spend it. That is the classic contention shape, the same one that oversells the last concert seat. The simplest correct fix is one mutex around the whole operation, which the Go practice uses. Under very high concurrency a single lock becomes a hot spot. Two well-known escalations:

Edge cases worth naming:

Down the stack

Layer 1The contract

For a token bucket with capacity C and rate R, any interval of length T admits at most C + R×T requests per key. Each call is O(1), with no background work and no allocation after the key's first request. For the sliding-window counter, the guarantee is approximate. It never admits more than L in a single fixed window, and it smooths the boundary using an estimate that assumes requests were spread evenly across the previous window.

Layer 2The mechanism

Lazy refill is the central trick. Instead of a timer adding tokens every 1/R seconds, which means one timer per key and millions of wakeups, the bucket stores the time of its last update and catches up arithmetically. Go's golang.org/x/time/rate.Limiter works this way: it stores tokens, last and lastEvent under a mutex, and also offers Reserve and Wait for callers that want to queue instead of being rejected. Envoy's local rate limit filter is a token bucket configured with max_tokens, tokens_per_fill and fill_interval. The sliding-window counter is the approach Cloudflare described for counting requests across a large edge network, because it needs two counters per key instead of a log.

Layer 3The machine

A bucket is about 16 bytes of payload: a float64 and an int64. In Go, a map[string]*bucket entry adds the key string, a pointer and map overhead, so roughly 80–100 bytes per active key. A million keys costs about 100 MB, which is why eviction matters. An uncontended sync.Mutex lock and unlock costs around 10–20 ns. Under contention the cache line holding the mutex bounces between cores, at around 100 ns per transfer, and goroutines may park. That is why striping helps once you pass a few million calls per second on one process. Reading a monotonic clock through the vDSO costs about 20 ns, cheap enough to do on every call.

Why it's built this way

  • Overload has to be stopped before the expensive work starts, so the check must cost far less than the request it guards.
  • To be that cheap it can't run timers or scan logs, so state is a few numbers per key, updated lazily from elapsed time.
  • Elapsed time makes the algorithm depend on a clock, so the clock is injected. That keeps production monotonic and tests deterministic.
  • Many callers hit the same key at once, so each update is atomic under a lock. When one lock is too hot, you shard it.

Extensibility

Leadership lens

Check yourself

  1. A token bucket has capacity 10 and refills at 2 tokens per second. A key has been idle for an hour. How many requests can it make in the next 3 seconds?

    Show answer

    Up to 16: 10 from the full bucket immediately, plus 2 per second for 3 seconds. The idle hour adds nothing beyond the cap.

  2. Why does the sliding-window counter need the previous window's count at all?

    Show answer

    Without it, the limiter forgets everything at each boundary, so a client can send L requests just before the boundary and L just after. Weighting the previous count by how much of it still overlaps the rolling window closes that gap.

  3. Why inject a clock instead of calling the system time inside allow?

    Show answer

    The algorithm's output depends on time, so time is an input. Injecting it makes tests deterministic and fast, and lets production choose a monotonic source that never jumps backwards.

  4. Two goroutines call allow on a bucket holding exactly one token. Without a lock, what can happen, and why?

    Show answer

    Both read one token, both decide to allow, and both write zero, so two requests pass. The read-modify-write must be atomic, under a mutex or with a compare-and-swap loop.

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →