Choosing the Right Rate Limiter: Token Bucket vs Sliding Window

When an API receives a sudden surge of traffic, a single request can cascade into a denial‑of‑service. Rate limiting is the first line of defense that balances usability with stability. Choosing the right algorithm is not just a technical decision; it shapes latency, memory usage, and how fair your service feels to every client.

TL;DR

• Token Bucket: low overhead, smooth traffic, allows short bursts up to bucket size.
• Sliding Window: stricter average‑rate enforcement, higher memory/CPU cost, more predictable fairness.
• Go example: a fixed‑size slice sliding window that keeps per‑client timestamps in O(1) memory.
• Key trade‑offs: burst tolerance vs. precision, simplicity vs. strictness, in‑memory vs. distributed coordination.

When Rate Limiting Matters: Real‑World Scenarios

• High‑traffic APIs that need to absorb traffic spikes – e.g., a public weather service that suddenly gets hit by a flash sale on an e‑commerce site.
• Services that must enforce per‑user quotas over time – a SaaS that offers 1000 requests per hour per customer.
• Systems where fairness between clients is critical – a shared messaging platform where no single user should starve others of bandwidth.

In all these cases, the limiter must be fast, accurate, and predictable.

Token Bucket: How It Works in Practice

Token bucket is the classic “smooth‑enforcement” algorithm. A bucket holds up to capacity tokens. Tokens are added at a fixed rate (e.g., 10 tokens per second). A request consumes one token; if no token is available the request is rejected or queued.

time ──►
   +-----+-----+-----+-----+-----+-----+-----+
   |     |     |     |     |     |     |     |
   |     |     |     |     |     |     |     |
   |  ┌───┐  ┌───┐  ┌───┐  ┌───┐  ┌───┐  ┌───┐  |
   |  │ T │  │ T │  │ T │  │ T │  │ T │  │ T │  |
   |  └───┘  └───┘  └───┘  └───┘  └───┘  └───┘  |
   |     |     |     |     |     |     |     |

Advantages

• Simplicity – only two counters per client.
• Low memory – a single integer per key.
• Smooth traffic – bursts up to the bucket size are allowed, preventing sudden drops in throughput.

Drawbacks

• Burst tolerance – a client can send a burst equal to capacity in a single instant.
• Fairness – a fast client can accumulate tokens and then use them all at once, potentially starving others.

Sliding Window: The Fine‑Grained Alternative

Sliding window measures the number of requests in a moving time window (e.g., last 60 seconds). Every new request increments a counter; old requests are removed as time advances. The counter is compared against the allowed quota.

Implementation Approaches

The Go example below uses the first approach: a fixed‑size slice of timestamps, which keeps memory bounded while still offering fine granularity.

Go Sliding Window Example

package main

import (
	"sync"
	"time"
)

// SlidingWindow holds a fixed‑size slice of request timestamps.
// It allows at most `limit` requests in the last `window` duration.
type SlidingWindow struct {
	mu       sync.Mutex
	times    []time.Time // ring buffer
	head     int
	size     int
	limit    int
	window   time.Duration
}

// NewSlidingWindow creates a limiter with a ring buffer of `size` entries.
func NewSlidingWindow(limit int, window time.Duration, size int) *SlidingWindow {
	return &SlidingWindow{
		times:  make([]time.Time, size),
		limit:  limit,
		window: window,
		size:   size,
	}
}

// Allow checks if a request can be served at current time.
func (s *SlidingWindow) Allow(now time.Time) bool {
	s.mu.Lock()
	defer s.mu.Unlock()

	// Remove outdated timestamps
	expire := now.Add(-s.window)
	// Since we store timestamps in a ring buffer, we don't need to delete.
	// We simply skip over them when counting.

	// Count current valid requests
	count := 0
	for i := 0; i < s.size; i++ {
		t := s.times[(s.head+i)%s.size]
		if !t.IsZero() && t.After(expire) {
			count++
		}
	}

	if count >= s.limit {
		return false // rate limit exceeded
	}

	// Record current request
	s.times[s.head] = now
	s.head = (s.head + 1) % s.size
	return true
}

How it works

1. Ring buffer – times is a fixed‑size slice acting as a circular queue.
2. Timestamp insertion – the newest request overwrites the oldest entry.
3. Counting – we iterate over the buffer to count timestamps newer than now-window.
4. Complexity – O(size) per request, but size is typically small (e.g., 60 for a per‑second granularity).

Trade‑offs

• Memory – bounded by size.
• CPU – linear in size.
• Accuracy – depends on granularity; if size is too small, bursts can slip through.

Choosing the Right Tool: Performance vs Fairness

When to pick Token Bucket

• High throughput, low latency: a microservice that must respond in milliseconds.
• Burst‑friendly: applications that can tolerate short bursts (e.g., video streaming prefetch).
• Limited resources: environments with strict memory budgets.

When to pick Sliding Window

• Strict SLA: a SaaS that guarantees a per‑user request quota.
• Fairness matters: shared APIs where one client should not monopolize bandwidth.
• Predictable behavior: monitoring shows that clients need consistent, bounded rates.

Integrating Into Your Stack: A Minimal Example

1. Shared store – Use Redis INCR with expiry for a token bucket, or a sorted set for a timestamp queue.
2. Middleware – Wrap the limiter in HTTP or gRPC middleware that checks before calling the handler.
3. Metrics – Expose hit/miss counters via Prometheus to detect misbehaving clients.

func RateLimitMiddleware(limiter *SlidingWindow) func(http.Handler) http.Handler {
	return func(next http.Handler) http.Handler {
		return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
			if !limiter.Allow(time.Now()) {
				http.Error(w, "rate limit exceeded", http.StatusTooManyRequests)
				return
			}
			next.ServeHTTP(w, r)
		})
	}
}

Deploy the middleware behind a reverse proxy (e.g., NGINX) or as a sidecar container to centralize control.

Common Pitfalls & Trade‑offs

• Assuming a bucket size of 1 enforces strict limits – a bucket of 1 still permits a burst of one request; the real limit is the refill rate.
• Ignoring clock skew – in distributed deployments, clock drift can cause sliding windows to miscount. Use monotonic clocks or synchronize clocks with NTP.
• Over‑tuning refill rates – setting a refill rate too low underutilizes capacity; too high, and you let bursts slip.
• Memory leaks in sliding window – if the buffer size is too large for the expected traffic, you may consume more memory than necessary.
• Per‑client state explosion – both algorithms require per‑client storage; in a global API with millions of keys, consider sharding or using a probabilistic data structure (e.g., Bloom filter) for low‑priority clients.

Key takeaways

• Token bucket offers low overhead and smooth traffic but allows short bursts.
• Sliding window provides tighter average‑rate enforcement at the cost of higher CPU/memory.
• A Go sliding window with a fixed‑size slice keeps memory bounded while still offering fine granularity.
• Choose based on latency needs, fairness requirements, and infrastructure constraints.
• Always monitor hit/miss ratios and adjust parameters to match real traffic patterns.