Implementing an Effective Token Bucket Rate Limiter

The Problem with Fixed-Window Rate Limiters

Many initial attempts at rate limiting use a simple fixed-window counter: requests are counted within a predefined time interval (e.g., one second), and once the limit is reached, subsequent requests are blocked until the window resets. While seemingly intuitive, this approach has a critical flaw: it allows for a "thundering herd" problem at the start of each new window. If a large number of requests arrive just before a window reset, followed by another large number immediately after, the downstream service can experience a burst of traffic far exceeding the intended rate. This can lead to service degradation, increased latency, and cascade failures.

The Token Bucket Algorithm

The token bucket algorithm offers a more sophisticated and effective approach to rate limiting. It models a bucket that holds a certain number of "tokens" which are continuously refilled at a fixed rate. Each incoming request consumes one token. If the bucket is empty, the request is rejected or queued. This mechanism provides two key advantages:

1. Burst Tolerance: During idle periods, tokens accumulate in the bucket up to its maximum capacity. This allows the system to handle short, legitimate bursts of requests without immediately hitting rate limits.
2. Smooth Outflow: The rate at which tokens are consumed (and thus requests are processed) is smoothed over time, never exceeding the refill rate. This protects downstream systems from sudden spikes in traffic, ensuring a more consistent load.

package ratelimiter
import (
	"sync"
	"time"
)
type TokenBucket struct {
	rate float64 // tokens added per second
	capacity float64 // max tokens the bucket can hold
	tokens float64 // current tokens
	lastRefill time.Time
	mu sync.Mutex // protects tokens and lastRefill
}
func NewTokenBucket(rate float64, capacity float64) *TokenBucket {
	return &TokenBucket{
		rate: rate,
		capacity: capacity,
		tokens: capacity, // start full so we can burst initially
		lastRefill: time.Now(),
	}
}
func (b *TokenBucket) Allow() bool {
	b.mu.Lock()
	defer b.mu.Unlock()
	now := time.Now()
	elapsed := now.Sub(b.lastRefill).Seconds()
	b.tokens += elapsed * b.rate
	if b.tokens > b.capacity {
		b.tokens = b.capacity
	}
	b.lastRefill = now
	if b.tokens < 1.0 {
		return false
	}
	b.tokens--
	return true
}

Key Considerations and Trade-offs

• State Management: The token bucket requires maintaining a small amount of state (current tokens, last refill time). For single instances, this is simple memory and a mutex. For distributed systems, an external state store (e.g., Redis, DynamoDB) and atomic operations are necessary.
• Concurrency: Proper synchronization (e.g., mutexes) is crucial for thread-safe token updates in concurrent environments to prevent race conditions and over-allowance.
• Configurability: The `rate` (tokens per second) and `capacity` (max burst) parameters allow fine-grained control over traffic shaping, enabling systems to balance strict limits with responsiveness to legitimate bursts.

Adopting a token bucket significantly improves system resilience by providing predictable traffic shaping and preventing overload of downstream dependencies. It shifts the focus from merely counting requests to actively smoothing their arrival rate, making services more robust under varying load conditions.