Articles / Go

1095 words

  • go
  • rate-limiting
  • token-bucket
  • concurrency
  • golang-x-time
  • networking

Reading the Source of rate.Limiter to Understand Token Buckets

There is no goroutine anywhere in golang.org/x/time/rate refilling a bucket every N milliseconds. No ticker, no timer, nothing running in the background. That nagged at me every time I reached for it.

And yet Limiter.Allow() correctly reports how many tokens are available at any instant, even if you haven't touched the limiter for ten minutes. That only makes sense once you read the source and realise the bucket isn't refilled, it's recomputed, lazily, every time someone asks.

That single design decision is the whole article. Once you see it, half the "surprising" behaviour of rate.Limiter stops being surprising.

The struct has no channel and no worker

Strip x/time/rate down to its actual fields (as of the current module, the shape has been stable for years):

type Limiter struct {
    mu     sync.Mutex
    limit  Limit // tokens per second
    burst  int
    tokens float64
    last   time.Time
    lastEvent time.Time
}

That's it. No channel, no worker. Three fields tell you most of the story:

  • tokens is a float64, which already tells you something: this isn't counting discrete integer tokens one at a time, it's tracking a continuous quantity that happens to look like tokens when you round it.
  • last is the timestamp of the last time the struct was updated.
  • limit is expressed as Limit, which is just float64 events per second (rate.Every(d) is a convenience constructor that inverts a duration into that rate).

advance: the function that does all the work

Everything interesting happens in an unexported method, roughly:

func (lim *Limiter) advance(now time.Time) (newNow time.Time, newLast time.Time, newTokens float64) {
    last := lim.last
    if now.Before(last) {
        last = now
    }
    elapsed := now.Sub(last)
    delta := lim.limit.tokensFromDuration(elapsed)
    tokens := lim.tokens + delta
    if burst := float64(lim.burst); tokens > burst {
        tokens = burst
    }
    return now, now, tokens
}

Read that carefully and the trick is obvious. Instead of a background process adding tokens every tick, advance computes how many tokens would have accumulated since the last recorded timestamp, given the configured rate, and clamps the result at the burst size.

It's the same maths you'd do by hand: "it's been 3 seconds, the rate is 10/s, so 30 tokens have notionally arrived, capped at whatever the bucket can hold." There's nothing to schedule because there's nothing to keep running. The fill level is just f(elapsed_time), evaluated on demand.

This is why Allow(), AllowN(), Wait() and Reserve() all follow the same three steps under the mutex:

  1. Call advance(now).
  2. Decide what to do with the resulting token count.
  3. Write the (possibly reduced) tokens and timestamp back into the struct.

The limiter has no notion of "current state" independent of "state as of the last time someone looked."

Allow is an honest yes or no

Allow() is AllowN(time.Now(), 1). AllowN boils down to: advance the bucket to now, see if there are at least N tokens, and if so subtract N and return true.

If not, it leaves the bucket untouched and returns false. No blocking, no queuing, just an honest answer based on the notional token count at this exact instant.

Reserve borrows tokens, so always Cancel what you don't use

Reserve() and ReserveN() answer a slightly different question: "if I can't have this now, when could I?"

Internally this calls reserveN, which does the same advance step. It then works out how far in the future the token deficit would be repaid at the configured rate, and returns a Reservation carrying that delay.

Crucially, reserveN optimistically subtracts the requested tokens from the running total immediately, allowing it to go negative. It assumes the caller will actually wait out the delay.

That's what makes Reservation.Cancel() a real, useful operation rather than a no-op: cancelling gives the tokens back. It matters if you reserved speculatively and then decided not to proceed (say, the surrounding request got cancelled via its context).

Skip the cancel and you've silently starved your own bucket for tokens nobody consumed.

Wait() and WaitN() are just Reserve() plus a time.Timer wrapping the reservation's delay, wired up to respect context.Context cancellation. If the context is cancelled while waiting, the reservation is cancelled too, for exactly the reason above.

Burst is the bucket's capacity, not requests per second

The field most people misuse is burst. Compare two limiters with the same rate:

  • rate.NewLimiter(rate.Limit(10), 1) gives you a steady 10 events/second in the long run but permits no burst beyond one token at a time, because tokens can never exceed 1.
  • rate.NewLimiter(rate.Limit(10), 20) also averages 10/s over time. But a caller who hasn't touched the limiter in the last two seconds can suddenly fire off 20 requests back to back, because that's how many tokens accumulated (capped at the burst) while nothing was drawing them down.

This is what bites people in production. They set the rate they want and leave burst at some default (or worse, set it to the rate value out of habit) without thinking about what happens after an idle period.

If your downstream service genuinely can't tolerate 20 requests arriving in the same millisecond, tune the burst down, not just the rate. Pick something the downstream can actually absorb, even if it looks stingy next to the steady-state rate.

No goroutine is a feature, not a shortcut

It would be easy to assume the lazy recomputation is a corner someone cut to keep the package simple. It's actually the more careful design. A ticking-goroutine implementation:

  • has to run forever, or be shut down explicitly, which every caller then has to remember to do
  • wakes up on a schedule regardless of whether the limiter is even being used
  • needs its own synchronisation to avoid racing with callers checking the token count

The lazy version has none of those problems. An idle limiter costs nothing beyond the memory for the struct, there's nothing to leak if you drop the last reference to it, and the entire concurrency story is "hold one mutex while computing a value."

Quick detour: time.Timer leaks are already a known trap in Go, as is the closely related mistake of forgetting to stop one in a select loop. So it's reasonable that a library used inside hot request paths avoids a background timer of its own when the maths lets it.

A worked example: ten through, then queuing

package main

import (
    "context"
    "fmt"
    "time"

    "golang.org/x/time/rate"
)

func main() {
    lim := rate.NewLimiter(rate.Limit(5), 10) // 5/s, burst of 10

    for i := 0; i < 12; i++ {
        if lim.Allow() {
            fmt.Println("request", i, "allowed immediately")
            continue
        }
        r := lim.Reserve()
        if !r.OK() {
            fmt.Println("request", i, "would never fit burst, dropping")
            continue
        }
        delay := r.Delay()
        fmt.Println("request", i, "waiting", delay)
        ctx, cancel := context.WithTimeout(context.Background(), time.Second)
        select {
        case <-time.After(delay):
            fmt.Println("request", i, "proceeded after wait")
        case <-ctx.Done():
            r.Cancel()
            fmt.Println("request", i, "gave up, tokens returned")
        }
        cancel()
    }
}

Run that and the first ten requests sail through (the burst). The last two start queuing behind a computed delay, because the bucket only had ten tokens to begin with and refills at five a second.

Nothing in that output required a background goroutine. It's all advance() doing arithmetic on a timestamp difference each time Allow or Reserve is called.

If you ever need a genuinely different refill shape (leaky bucket instead of token bucket, say, or a sliding log), remember how x/time/rate solved its problem: by refusing to run anything continuously. That constraint, more than the token bucket algorithm itself, is the reusable idea.

← All articles