Rate Limiting Algorithms: 5 Implementation Methods from System Design Notes

The liquidslr/system-design-notes repository documents five fundamental rate limiting algorithms—Token Bucket, Leaking Bucket, Fixed Window Counter, Sliding Window Log, and Sliding Window Counter—that balance memory efficiency, burst tolerance, and implementation complexity for distributed systems.

The 04. Rate Limiter/Readme.md file in the system-design-notes repository provides detailed architectural analysis and practical implementations for controlling API traffic. Understanding these rate limiting algorithms is essential for preventing resource exhaustion and maintaining service availability during traffic spikes. Each approach offers distinct trade-offs between precision, memory usage, and burst handling, as illustrated in the accompanying diagrams within 04. Rate Limiter/images/.

Token Bucket Algorithm

The Token Bucket algorithm maintains a bucket with a fixed capacity of tokens that are refilled at a steady rate. According to lines 44-54 of 04. Rate Limiter/Readme.md, every incoming request consumes one token; if the bucket is empty, the system rejects the request immediately.

This method excels at handling short-term traffic bursts while maintaining long-term rate limits. However, operators must carefully tune the bucket size and refill rate parameters to prevent unnecessary rejections or excessive throughput.

Go Implementation

The repository provides a thread-safe implementation using sync.Mutex and time.Ticker to manage concurrent access and token replenishment:

type TokenBucket struct {
    rate      int           // tokens added per interval
    capacity  int           // max tokens
    tokens    int
    ticker    *time.Ticker
    mu        sync.Mutex
}

func NewTokenBucket(rate, capacity int, interval time.Duration) *TokenBucket {
    tb := &TokenBucket{rate: rate, capacity: capacity, tokens: capacity}
    tb.ticker = time.NewTicker(interval)
    go func() {
        for range tb.ticker.C {
            tb.mu.Lock()
            tb.tokens = min(tb.tokens+tb.rate, tb.capacity)
            tb.mu.Unlock()
        }
    }()
    return tb
}

func (tb *TokenBucket) Allow() bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()
    if tb.tokens > 0 {
        tb.tokens--
        return true
    }
    return false
}

Leaking Bucket Algorithm

The Leaking Bucket algorithm processes requests through a FIFO queue at a fixed outflow rate. As implemented in lines 57-65 of the source documentation, this approach guarantees steady traffic flow but can delay bursty requests since newer arrivals must wait behind earlier ones in the queue.

While memory-efficient due to fixed queue capacity, this algorithm is less forgiving of traffic spikes compared to the Token Bucket approach.

Go Implementation

The LeakingBucket struct manages a timestamp queue and drains entries based on a fixed interval:

type LeakingBucket struct {
    capacity int
    queue    []time.Time
    interval time.Duration
    mu       sync.Mutex
}

func NewLeakingBucket(capacity int, interval time.Duration) *LeakingBucket {
    return &LeakingBucket{capacity: capacity, interval: interval}
}

func (lb *LeakingBucket) Allow() bool {
    lb.mu.Lock()
    defer lb.mu.Unlock()
    now := time.Now()
    // Remove drained items
    for len(lb.queue) > 0 && now.Sub(lb.queue[0]) >= lb.interval {
        lb.queue = lb.queue[1:]
    }
    if len(lb.queue) < lb.capacity {
        lb.queue = append(lb.queue, now)
        return true
    }
    return false
}

Fixed Window Counter Algorithm

The Fixed Window Counter divides time into discrete windows (e.g., one-minute intervals) and tracks request counts per window. According to lines 71-80 of 04. Rate Limiter/Readme.md, once the counter reaches its limit, all subsequent requests are blocked until the next window begins.

This algorithm offers low computational overhead and minimal memory footprint but suffers from edge-case spikes when bursts straddle two consecutive windows, potentially allowing double the intended traffic volume at boundary transitions.

Redis-Backed Implementation

For distributed systems, the repository demonstrates a Redis-based implementation using atomic increment operations:

func FixedWindowAllow(ctx context.Context, rdb *redis.Client, key string, limit int, window time.Duration) (bool, error) {
    cur, err := rdb.Incr(ctx, key).Result()
    if err != nil {
        return false, err
    }
    if cur == 1 {
        rdb.Expire(ctx, key, window)
    }
    return cur <= int64(limit), nil
}

Sliding Window Log Algorithm

The Sliding Window Log maintains a timestamp log for every request, typically stored in a sorted set. The algorithm evaluates the current request by counting entries within a rolling time interval, as detailed in lines 86-94 of the documentation.

While this approach provides precise rate limiting with true rolling windows, it demands significant memory resources since every request timestamp must be retained for the duration of the window.

Redis Sorted Set Implementation

The SlidingLogAllow function uses Redis sorted sets to maintain and purge timestamps atomically:

func SlidingLogAllow(ctx context.Context, rdb *redis.Client, key string, limit int, window time.Duration) (bool, error) {
    now := time.Now().UnixNano()
    minScore := now - int64(window)
    // Add current request timestamp
    rdb.ZAdd(ctx, key, &redis.Z{Score: float64(now), Member: now})
    // Trim old entries
    rdb.ZRemRangeByScore(ctx, key, "0", fmt.Sprintf("%d", minScore))
    // Count recent requests
    cnt, err := rdb.ZCount(ctx, key, fmt.Sprintf("%d", minScore), fmt.Sprintf("%d", now)).Result()
    if err != nil {
        return false, err
    }
    return cnt <= int64(limit), nil
}

Sliding Window Counter Algorithm

The Sliding Window Counter combines aspects of fixed windows and sliding logs to reduce memory overhead. As documented in lines 97-104 of 04. Rate Limiter/Readme.md, this method maintains two counters (current and previous window) and calculates a weighted average to approximate the rolling count.

This algorithm offers better burst handling than fixed windows while consuming less memory than full logs, though it sacrifices absolute precision for efficiency.

In-Memory Implementation

The SlidingCounter struct tracks weighted requests across window boundaries:

type SlidingCounter struct {
    curWindow   int64
    prevWindow  int64
    curCount    int
    prevCount   int
    limit       int
    windowSize  time.Duration
    mu          sync.Mutex
}

func NewSlidingCounter(limit int, windowSize time.Duration) *SlidingCounter {
    now := time.Now().UnixNano()
    return &SlidingCounter{curWindow: now, limit: limit, windowSize: windowSize}
}

func (sc *SlidingCounter) Allow() bool {
    sc.mu.Lock()
    defer sc.mu.Unlock()
    now := time.Now().UnixNano()
    if now-sc.curWindow > int64(sc.windowSize) {
        // slide windows
        sc.prevWindow = sc.curWindow
        sc.prevCount = sc.curCount
        sc.curWindow = now
        sc.curCount = 0
    }
    // weighted count
    elapsed := now - sc.curWindow
    weight := float64(sc.windowSize-elapsed) / float64(sc.windowSize)
    approx := int(weight*float64(sc.prevCount)) + sc.curCount
    if approx >= sc.limit {
        return false
    }
    sc.curCount++
    return true
}

Summary

The liquidslr/system-design-notes repository provides practical implementations for five essential rate limiting strategies:

• Token Bucket: Best for applications requiring burst tolerance with steady-state rate limiting; memory-efficient and straightforward to implement.
• Leaking Bucket: Ideal for scenarios demanding constant outflow rates; simpler but less forgiving of traffic spikes.
• Fixed Window Counter: Suitable for high-throughput systems where approximate limiting suffices and minimal latency is critical.
• Sliding Window Log: Necessary when precise request accuracy is paramount and memory resources are abundant.
• Sliding Window Counter: The balanced choice for distributed systems requiring reasonable accuracy with reduced memory footprint compared to full logs.

Frequently Asked Questions

Which rate limiting algorithm is best for handling traffic bursts?

Token Bucket is the optimal choice for handling traffic bursts because it accumulates tokens during idle periods, allowing temporary spikes up to the bucket capacity. Unlike the Leaking Bucket algorithm, which rigidly queues requests, the Token Bucket permits immediate processing of bursts as long as tokens remain available. This makes it ideal for APIs with unpredictable but generally low-average traffic patterns.

How does the Sliding Window Counter differ from Fixed Window Counter?

The Sliding Window Counter improves upon the Fixed Window Counter by maintaining two window counters and calculating a weighted average between them, preventing the "thundering herd" problem at window boundaries. While the Fixed Window Counter can allow double the intended traffic when requests straddle two windows, the Sliding Window Counter provides a smoother approximation of the rate limit across time boundaries.

What are the memory implications of these rate limiting algorithms?

Token Bucket and Leaking Bucket require only constant O(1) memory regardless of request volume, while Fixed Window and Sliding Window Counter need minimal state storage. In contrast, Sliding Window Log requires O(n) memory proportional to the number of requests within the window, as it must store every individual timestamp, making it unsuitable for high-throughput scenarios with large windows.

Can these algorithms work in distributed environments?

Yes, though single-node implementations like the TokenBucket and SlidingCounter structs require external coordination mechanisms for distributed deployments. The repository demonstrates Redis-backed implementations for Fixed Window (FixedWindowAllow) and Sliding Window Log (SlidingLogAllow) that leverage centralized storage for cross-instance rate limiting consistency.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}