Learning rate limiter algorithms in Go

I wanted to understand rate limiters as algorithms rather than only as infrastructure components. The simplest way was to implement each one and pass explicit timestamps into it. That makes window boundaries, refill behavior and burst handling visible without waiting for a real clock.

This note builds five in-memory limiters:

Fixed window.
Sliding window log.
Sliding window counter.
Token bucket.
Leaky bucket.

The examples use seconds as the time unit and keep separate state for every user. They are small enough to study, but they also handle concurrent calls with a mutex.

One interface for every algorithm

All five implementations satisfy the same interface:

package main import (	"fmt"	"sync") type RateLimiter interface {	Allow(userID string, timestamp int64) bool}

Passing the timestamp from the caller is deliberate. It makes the algorithms deterministic and easy to test:

Allow("u1", 8)  → evaluate a request from u1 at second 8

In an application I would normally inject a clock or pass time.Time. All timestamps given to one limiter must use the same unit and clock source.

1. Fixed window

A fixed-window limiter splits time into equal intervals and keeps one counter per user for the current interval.

For a ten-second window:

[0, 10)  [10, 20)  [20, 30)

The aligned start of a window is:

windowStart := (timestamp / windowSize) * windowSize

At timestamp 17 with a window size of 10, the result is 10. At timestamp 29 it is 20.

Implementation

type FixedWindowState struct {	count       int	windowStart int64} type FixedWindowLimiter struct {	mu         sync.Mutex	limit      int	windowSize int64	users      map[string]*FixedWindowState} func NewFixedWindowLimiter(limit int, windowSize int64) RateLimiter {	if limit < 1 || windowSize < 1 {		panic("limit and window size must be positive")	} 	return &FixedWindowLimiter{		limit:      limit,		windowSize: windowSize,		users:      make(map[string]*FixedWindowState),	}} func (f *FixedWindowLimiter) Allow(userID string, timestamp int64) bool {	f.mu.Lock()	defer f.mu.Unlock() 	windowStart := (timestamp / f.windowSize) * f.windowSize	state, exists := f.users[userID] 	if !exists {		f.users[userID] = &FixedWindowState{			count:       1,			windowStart: windowStart,		}		return true	} 	// Reject time moving backwards in this deterministic example.	if windowStart < state.windowStart {		return false	} 	if windowStart > state.windowStart {		state.windowStart = windowStart		state.count = 1		return true	} 	if state.count >= f.limit {		return false	} 	state.count++	return true}

With a limit of three requests per ten seconds:

t=1   allow, count=1 in [0,10)t=2   allow, count=2 in [0,10)t=3   allow, count=3 in [0,10)t=4   rejectt=11  allow, new window [10,20)

State is constant per active user: one window start and one count.

Boundary burst

The weakness appears at a window boundary. A user can send three requests just before second 10 and three more just after it:

7, 8, 9       → three accepted10, 11, 12    → three accepted

Six requests arrive in roughly five seconds even though the configured policy sounds like three requests per ten seconds. The algorithm obeys its fixed windows, but a fixed window is not the same as every possible rolling ten-second interval.

Use fixed window when small boundary bursts are acceptable and low state cost matters more than rolling accuracy.

2. Sliding window log

A sliding-window log stores the timestamp of every accepted request. For a request at time now, it removes timestamps older than the rolling interval:

[now - windowSize, now]

It then compares the number of remaining timestamps with the limit.

Implementation

type SlidingLogState struct {	timestamps []int64} type SlidingWindowLog struct {	mu         sync.Mutex	limit      int	windowSize int64	users      map[string]*SlidingLogState} func NewSlidingWindowLog(limit int, windowSize int64) RateLimiter {	if limit < 1 || windowSize < 1 {		panic("limit and window size must be positive")	} 	return &SlidingWindowLog{		limit:      limit,		windowSize: windowSize,		users:      make(map[string]*SlidingLogState),	}} func (sl *SlidingWindowLog) Allow(userID string, timestamp int64) bool {	sl.mu.Lock()	defer sl.mu.Unlock() 	state, exists := sl.users[userID]	if !exists {		sl.users[userID] = &SlidingLogState{			timestamps: []int64{timestamp},		}		return true	} 	if len(state.timestamps) > 0 &&		timestamp < state.timestamps[len(state.timestamps)-1] {		return false	} 	cutoff := timestamp - sl.windowSize	firstKept := 0	for firstKept < len(state.timestamps) &&		state.timestamps[firstKept] < cutoff {		firstKept++	} 	state.timestamps = state.timestamps[firstKept:]	if len(state.timestamps) >= sl.limit {		return false	} 	state.timestamps = append(state.timestamps, timestamp)	return true}

The timestamps remain sorted because this example rejects time moving backwards. Instead of allocating a new kept slice for every request, it advances an index and reuses the existing backing array.

The boundary rule is explicit: a timestamp exactly equal to now - windowSize is still retained. Changing < cutoff to <= cutoff would make the interval open on the left instead.

Walking through the original sequence

For a limit of three and a window size of ten:

t=1   [1]        → allowt=3   [1,3]      → allowt=5   [1,3,5]    → allowt=8   [1,3,5]    → rejectt=12  [3,5,12]   → allow; 1 is older than the cutoff 2t=13  [3,5,12]   → reject; 3 is exactly on the cutoff

This is much more accurate than a fixed window because every request evaluates the interval relative to its own timestamp.

The trade-off is memory and update work. The limiter stores up to the accepted request limit per active user. It also has to remove expired timestamps. A deque or ring buffer avoids retaining a large backing array for a user whose old entries have been discarded.

Use a sliding log when exact rolling-window behavior matters and the request limit is small enough for timestamp storage to be reasonable.

3. Sliding window counter

The sliding-window counter approximates a rolling window without storing every timestamp. It keeps two fixed-window counters:

previous window countcurrent window count

The previous count is weighted by how much of that window overlaps the current rolling interval.

At second 13 with ten-second windows:

previous fixed window: [0,10)current fixed window:  [10,20)rolling interval:      [3,13] elapsed in current window = 3 secondsprevious overlap weight = (10 - 3) / 10 = 0.7

If the previous window contains three requests and the current one contains one, the estimate is:

3 × 0.7 + 1 = 3.1 requests

Implementation

type SlidingCounterState struct {	previousWindowStart int64	previousCount       int	currentWindowStart  int64	currentCount        int} type SlidingWindowCounter struct {	mu         sync.Mutex	limit      int	windowSize int64	users      map[string]*SlidingCounterState} func NewSlidingWindowCounter(limit int, windowSize int64) RateLimiter {	if limit < 1 || windowSize < 1 {		panic("limit and window size must be positive")	} 	return &SlidingWindowCounter{		limit:      limit,		windowSize: windowSize,		users:      make(map[string]*SlidingCounterState),	}} func (sc *SlidingWindowCounter) Allow(	userID string,	timestamp int64,) bool {	sc.mu.Lock()	defer sc.mu.Unlock() 	windowStart := (timestamp / sc.windowSize) * sc.windowSize	state, exists := sc.users[userID]	if !exists {		state = &SlidingCounterState{			currentWindowStart: windowStart,		}		sc.users[userID] = state	} 	if windowStart < state.currentWindowStart {		return false	} 	if windowStart > state.currentWindowStart {		if windowStart == state.currentWindowStart+sc.windowSize {			state.previousWindowStart = state.currentWindowStart			state.previousCount = state.currentCount		} else {			// At least one complete inactive window was skipped.			state.previousWindowStart = windowStart - sc.windowSize			state.previousCount = 0		} 		state.currentWindowStart = windowStart		state.currentCount = 0	} 	elapsed := timestamp - state.currentWindowStart	previousWeight := float64(sc.windowSize-elapsed) /		float64(sc.windowSize)	estimatedCount := float64(state.previousCount)*previousWeight +		float64(state.currentCount) 	if estimatedCount >= float64(sc.limit) {		return false	} 	state.currentCount++	return true}

This fixes the incomplete parts of my first attempt: the receiver is now SlidingWindowCounter, field names are consistent, the window is rotated before calculating the estimate and Allow returns a boolean on every path.

Using the same sequence as the sliding log:

t=1   estimate 0.0 → allowt=3   estimate 1.0 → allowt=5   estimate 2.0 → allowt=8   estimate 3.0 → rejectt=12  estimate 2.4 → allowt=13  estimate 3.1 → reject

The calculation assumes requests in the previous window were distributed uniformly. If all three arrived at the end of that window, the estimate can undercount. If they all arrived at the beginning, it can overcount.

State remains constant per user, making this a practical middle ground between fixed-window simplicity and sliding-log accuracy.

Use a sliding counter when rolling behavior matters but exact timestamp storage is too expensive.

4. Token bucket

A token bucket represents permission as tokens:

capacity    = maximum stored tokensrefill rate = tokens added per secondrequest     = consumes one token

Tokens accumulate while a user is idle, up to the capacity. This saved credit permits a controlled burst. After the burst, requests are admitted only as new tokens arrive.

For a capacity of three and a refill rate of 0.2 tokens per second:

the bucket starts with 3 tokensone new token takes 5 secondsthe user can spend 3 tokens immediately

Implementation

type TokenBucketState struct {	tokens     float64	lastRefill int64} type TokenBucketLimiter struct {	mu         sync.Mutex	capacity   float64	refillRate float64	users      map[string]*TokenBucketState} func NewTokenBucketLimiter(capacity int, refillRate float64) RateLimiter {	if capacity < 1 || refillRate <= 0 {		panic("capacity and refill rate must be positive")	} 	return &TokenBucketLimiter{		capacity:   float64(capacity),		refillRate: refillRate,		users:      make(map[string]*TokenBucketState),	}} func (tb *TokenBucketLimiter) Allow(userID string, timestamp int64) bool {	tb.mu.Lock()	defer tb.mu.Unlock() 	state, exists := tb.users[userID]	if !exists {		state = &TokenBucketState{			tokens:     tb.capacity,			lastRefill: timestamp,		}		tb.users[userID] = state	} 	if timestamp < state.lastRefill {		return false	} 	elapsed := timestamp - state.lastRefill	state.tokens += float64(elapsed) * tb.refillRate	if state.tokens > tb.capacity {		state.tokens = tb.capacity	}	state.lastRefill = timestamp 	if state.tokens < 1 {		return false	} 	state.tokens--	return true}

The bucket refills lazily. It does not need a background goroutine or ticker. Every call calculates how many tokens accumulated since the last request.

Floating-point tokens make fractional rates easy to understand. A production implementation may store scaled integers or elapsed nanoseconds to control rounding behavior.

Example

capacity=3, refill=0.2 token/second t=0   allow, 2 tokens remaint=0   allow, 1 token remainst=0   allow, 0 tokens remaint=0   rejectt=5   allow, one token has refilledt=6   reject, only 0.2 token has refilled

Token bucket is a strong default for API traffic because it expresses both the long-term rate and the allowed burst explicitly.

5. Leaky bucket

The leaky-bucket model imagines requests as water entering a bucket. Water leaves at a constant rate. A request is rejected when adding it would overflow the bucket.

requests add water         ↓    ┌─────────┐    │ bucket  │ capacity controls burst tolerance    └────┬────┘         ↓    constant leak rate

There are two common forms:

As a meter: leaked capacity is calculated on each request. A request is rejected when the bucket is full.
As a queue: accepted work waits in the bucket and a worker releases it at a steady rate.

The implementation below is the meter form.

Implementation

type LeakyBucketState struct {	level    float64	lastLeak int64} type LeakyBucketLimiter struct {	mu       sync.Mutex	capacity float64	leakRate float64	users    map[string]*LeakyBucketState} func NewLeakyBucketLimiter(capacity int, leakRate float64) RateLimiter {	if capacity < 1 || leakRate <= 0 {		panic("capacity and leak rate must be positive")	} 	return &LeakyBucketLimiter{		capacity: float64(capacity),		leakRate: leakRate,		users:    make(map[string]*LeakyBucketState),	}} func (lb *LeakyBucketLimiter) Allow(userID string, timestamp int64) bool {	lb.mu.Lock()	defer lb.mu.Unlock() 	state, exists := lb.users[userID]	if !exists {		state = &LeakyBucketState{lastLeak: timestamp}		lb.users[userID] = state	} 	if timestamp < state.lastLeak {		return false	} 	elapsed := timestamp - state.lastLeak	state.level -= float64(elapsed) * lb.leakRate	if state.level < 0 {		state.level = 0	}	state.lastLeak = timestamp 	if state.level+1 > lb.capacity {		return false	} 	state.level++	return true}

With capacity three and a leak rate of 0.2 units per second, three simultaneous requests fit. A fourth is rejected. Five seconds later one complete unit has leaked, so one more request fits.

The meter form and token bucket are mathematical counterparts: one tracks available credit while the other tracks consumed capacity. The queue form is operationally different because it delays accepted work to create a steady output rate instead of immediately returning true.

Use leaky-bucket queueing when downstream traffic must be smoothed. Use the meter form when rejecting overflow is sufficient.

Running all five

The implementations above can be placed in one file in the same order, followed by this main function:

func main() {	var limiter RateLimiter 	limiter = NewFixedWindowLimiter(3, 10)	fmt.Println("fixed window")	fmt.Println(limiter.Allow("u1", 1))  // true	fmt.Println(limiter.Allow("u1", 2))  // true	fmt.Println(limiter.Allow("u1", 3))  // true	fmt.Println(limiter.Allow("u1", 4))  // false	fmt.Println(limiter.Allow("u1", 11)) // true	fmt.Println(limiter.Allow("u2", 4))  // true: independent user 	limiter = NewSlidingWindowLog(3, 10)	fmt.Println("\nsliding window log")	fmt.Println(limiter.Allow("u1", 1))  // true	fmt.Println(limiter.Allow("u1", 3))  // true	fmt.Println(limiter.Allow("u1", 5))  // true	fmt.Println(limiter.Allow("u1", 8))  // false	fmt.Println(limiter.Allow("u1", 12)) // true	fmt.Println(limiter.Allow("u1", 13)) // false 	limiter = NewSlidingWindowCounter(3, 10)	fmt.Println("\nsliding window counter")	fmt.Println(limiter.Allow("u1", 1))  // true	fmt.Println(limiter.Allow("u1", 3))  // true	fmt.Println(limiter.Allow("u1", 5))  // true	fmt.Println(limiter.Allow("u1", 8))  // false	fmt.Println(limiter.Allow("u1", 12)) // true	fmt.Println(limiter.Allow("u1", 13)) // false 	limiter = NewTokenBucketLimiter(3, 0.2)	fmt.Println("\ntoken bucket")	fmt.Println(limiter.Allow("u1", 0)) // true	fmt.Println(limiter.Allow("u1", 0)) // true	fmt.Println(limiter.Allow("u1", 0)) // true	fmt.Println(limiter.Allow("u1", 0)) // false	fmt.Println(limiter.Allow("u1", 5)) // true	fmt.Println(limiter.Allow("u1", 6)) // false 	limiter = NewLeakyBucketLimiter(3, 0.2)	fmt.Println("\nleaky bucket")	fmt.Println(limiter.Allow("u1", 0)) // true	fmt.Println(limiter.Allow("u1", 0)) // true	fmt.Println(limiter.Allow("u1", 0)) // true	fmt.Println(limiter.Allow("u1", 0)) // false	fmt.Println(limiter.Allow("u1", 5)) // true	fmt.Println(limiter.Allow("u1", 6)) // false}

Comparing the algorithms

Algorithm	State per user	Rolling accuracy	Burst behavior	Main trade-off
Fixed window	Constant	Low near boundaries	Can burst across a boundary	Simplest implementation
Sliding log	Up to the accepted request limit	Exact for the chosen boundary rule	Strict rolling limit	Stores timestamps
Sliding counter	Constant	Approximate	Smoother than fixed window	Assumes requests were evenly distributed
Token bucket	Constant	Rate-based	Explicit burst capacity	Needs refill arithmetic
Leaky bucket	Constant, plus queued jobs in queue form	Rate-based	Rejects or delays overflow	Queue form adds latency

There is no universally best limiter. The correct choice depends on the policy:

Simple quota per interval             → fixed windowExact rolling maximum                 → sliding window logCheap rolling approximation           → sliding window counterAverage rate with controlled bursts   → token bucketSmooth downstream processing          → leaky bucket queue

Concurrency and state ownership

Each implementation uses one mutex around its user map and state transitions. The lock is important because Allow is a read-modify-write operation. Two goroutines must not both observe the same count or token balance and admit requests independently.

One global mutex is intentionally simple. If profiling shows contention, the user map can be divided into shards with one lock per shard. Another option is to hash each user to a worker goroutine that exclusively owns its state. Those ownership patterns are explored in Five concurrency patterns from Go to distributed systems.

An atomic counter alone is not sufficient for these implementations. Updating a fixed-window limiter involves both windowStart and count. A token bucket must update both tokens and lastRefill as one state transition.

Moving from this code to production

These examples explain the algorithms, but a production limiter needs a few more decisions.

Choose the identity and policy key

The key may include a user, API key, endpoint or operation cost:

rate-limit:{tenant}:{endpoint}

Two endpoints can have different capacities. One expensive request may consume more than one token.

Use a reliable time source

Wall clocks can jump because of clock correction. Inside one process, elapsed-time calculations should use Go's monotonic clock information. In a distributed store, define which clock is authoritative and what happens when nodes disagree.

Clean up inactive users

The maps in this note retain every user forever. A real in-memory limiter needs expiry, periodic cleanup or a bounded cache. A Redis-backed limiter normally applies a TTL to inactive keys.

Make distributed updates atomic

Several application instances cannot enforce one global limit with independent in-memory maps. Shared state must be updated atomically. Reading a counter and writing it back as separate remote operations creates a race.

The separate note Designing a distributed rate limiter covers shared storage, atomic updates, failure behavior and policy design.

Return more than a boolean

Callers often need:

allowedremaining capacityretry-after durationlimit reset time

The boolean interface keeps the algorithm examples focused. A production result type should expose enough information to build correct HTTP headers and useful metrics.

What I want to remember

A rate limiter is state plus a time rule.

Fixed and sliding windows ask, “How many requests belong to this interval?” Token and leaky buckets ask, “How quickly does capacity recover?”

The algorithm defines the traffic shape. The mutex, shard owner or shared database only makes that state transition safe. Choosing the storage or synchronization mechanism does not replace choosing the policy.