Designing a Scalable Rate Limiter: From Fixed Window to Token Bucket

The Challenge: Burstiness and Fixed-Window Limitations

The initial approach to rate limiting often involves a fixed-window counter. This method resets a counter at regular intervals (e.g., every minute) and rejects requests once a limit is reached within that window. While simple to implement, this strategy suffers from significant drawbacks, especially with bursty traffic. A sudden surge of requests right at the start or end of a window can either consume the entire quota immediately, throttling legitimate subsequent requests, or allow an excessive number of requests if a burst occurs just before the window resets, leading to system overload. This creates "cliff edges" where user experience is inconsistent and unpredictable.

Introducing the Token Bucket Algorithm

The token bucket algorithm provides a more sophisticated solution by smoothing out traffic. It allows for a configurable burst capacity and a sustained refill rate, making it resilient to traffic spikes without unfairly throttling requests. Key advantages over fixed-window include:

• No Cliff Edges: Tokens are added continuously, allowing for smoother handling of traffic bursts across arbitrary time intervals.
• Simplicity: It typically requires only two state variables: current tokens and the timestamp of the last refill, simplifying implementation and reasoning.
• Predictability: It provides mathematical guarantees on the maximum number of requests allowed over any given time period, ensuring long-term stability.

Lock-Free Token Bucket Implementation in Go

The article demonstrates a lock-free implementation of the token bucket in Go, utilizing atomic operations to manage token count and last refill timestamp. This approach minimizes contention under high load, which is crucial for high-performance rate limiters. The `Allow()` function atomically refills tokens based on elapsed time and then attempts to decrement the token count, ensuring thread safety without explicit mutexes in the critical path for token consumption.

type TokenBucket struct {
    capacity int64 // max tokens
    rate     float64 // tokens per second
    tokens   int64 // current tokens
    last     int64 // unix nano of last refill
}

func NewTokenBucket(capacity int64, ratePerSec float64) *TokenBucket {
    return &TokenBucket{
        capacity: capacity,
        rate:     ratePerSec,
        tokens:   capacity, // start full
        last:     time.Now().UnixNano(),
    }
}

func (b *TokenBucket) Allow() bool {
    now := time.Now().UnixNano()
    elapsed := float64(now-b.last) / 1e9
    newTokens := int64(elapsed * b.rate)
    if newTokens > 0 {
        b.tokens = minInt64(b.tokens+newTokens, b.capacity)
        b.last = now
    }

    for {
        cur := b.tokens
        if cur == 0 {
            return false // bucket empty, reject
        }
        if atomic.CompareAndSwapInt64(&b.tokens, cur, cur-1) {
            return true // token taken
        }
    }
}