The 5 Main Rate Limiting Algorithms Explained: Token Bucket, Leaking Bucket, and Beyond

The five main rate limiting algorithms are Token Bucket, Leaking Bucket, Fixed Window Counter, Sliding Window Log, and Sliding Window Counter, each providing distinct trade-offs between burst tolerance, memory consumption, and rate precision.

Rate limiting controls how many requests a client can make to a service within a specific time frame to prevent resource exhaustion. According to the liquidslr/system-design-notes repository, specifically documented in 04. Rate Limiter/Readme.md, these five canonical rate limiting algorithms form the foundation of modern API gateway and microservice protection strategies. Understanding their implementation details enables engineers to select the optimal approach for handling traffic spikes while maintaining system stability.

Token Bucket Algorithm

The Token Bucket algorithm maintains a bucket with a configurable capacity of tokens. Tokens refill at a steady rate, and each request consumes one token. If the bucket is empty, the request is rejected.

This approach is ideal for APIs that need to allow short traffic bursts while enforcing an average rate over time, such as chat message posting or image upload endpoints. The algorithm is memory-efficient and simple to implement, though it requires careful tuning of bucket size versus refill rate to avoid over- or under-throttling.

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity          # max tokens

        self.tokens = capacity
        self.refill_rate = refill_rate    # tokens per second

        self.last_refill = time.time()

    def allow(self):
        now = time.time()
        # Refill tokens based on elapsed time

        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Reference: Token Bucket implementation details in 04. Rate Limiter/Readme.md【Token Bucket】

Leaking Bucket Algorithm

The Leaking Bucket algorithm queues incoming requests in a FIFO buffer and releases them at a constant rate, like water leaking from a bucket. The bucket’s capacity limits the maximum number of concurrent pending requests.

This algorithm suits systems where smooth, steady outflow is critical, such as load-balanced microservices that downstream components cannot handle in bursts. While it guarantees a stable output rate and remains memory-efficient, large bursts may cause increased latency for later requests waiting in the queue.

type LeakyBucket struct {
    capacity int
    queue    []time.Time
    rate    time.Duration // interval between leaks
}

func (b *LeakyBucket) Allow() bool {
    now := time.Now()
    // Leak tokens that have passed their interval
    for len(b.queue) > 0 && now.Sub(b.queue[0]) >= b.rate {
        b.queue = b.queue[1:]
    }
    if len(b.queue) < b.capacity {
        b.queue = append(b.queue, now)
        return true
    }
    return false
}

Reference: Leaking Bucket specification in 04. Rate Limiter/Readme.md【Leaking Bucket】

Fixed Window Counter Algorithm

The Fixed Window Counter divides time into fixed intervals (e.g., 1 second). A counter tracks requests in the current window; once the limit is reached, further requests are dropped until the next window starts.

This method works well for scenarios with coarse-grained limits, such as limiting login attempts per minute. It is extremely simple, fast, and has low overhead. However, edge-window spikes can allow twice the intended traffic at window boundaries, creating a "thundering herd" at the reset moment.

class FixedWindow {
    private final int limit;
    private final long windowSizeMs;
    private long windowStart;
    private int count;

    public FixedWindow(int limit, long windowSizeMs) {
        this.limit = limit;
        this.windowSizeMs = windowSizeMs;
        this.windowStart = System.currentTimeMillis();
    }

    public synchronized boolean allow() {
        long now = System.currentTimeMillis();
        if (now - windowStart >= windowSizeMs) {
            windowStart = now;
            count = 0;
        }
        if (count < limit) {
            count++;
            return true;
        }
        return false;
    }
}

Reference: Fixed Window Counter logic in 04. Rate Limiter/Readme.md【Fixed Window Counter】

Sliding Window Log Algorithm

The Sliding Window Log records every request timestamp. To determine if a new request is allowed, the system counts timestamps falling within the sliding time window (e.g., the last 60 seconds) and compares against the limit.

This algorithm provides high-precision throttling where exact request rates matter, such as financial transaction APIs. It eliminates window-boundary artifacts, ensuring strict rate enforcement. The primary weakness is high memory consumption, as each request must be stored individually.

class SlidingLog {
    constructor(limit, windowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
        this.timestamps = [];
    }

    allow() {
        const now = Date.now();
        // Discard old timestamps
        this.timestamps = this.timestamps.filter(t => now - t < this.windowMs);
        if (this.timestamps.length < this.limit) {
            this.timestamps.push(now);
            return true;
        }
        return false;
    }
}

Reference: Sliding Window Log documentation in 04. Rate Limiter/Readme.md【Sliding Window Log】

Sliding Window Counter Algorithm

The Sliding Window Counter merges Fixed Window Counter and Sliding Log concepts. It maintains two counters (current and previous window) and uses a weighted average to approximate a sliding window calculation.

This approach balances accuracy and memory efficiency, making it suitable for media streaming services or high-throughput APIs that cannot afford the memory overhead of full logs but need better precision than fixed windows. While more memory-efficient than a full log, it provides an approximation rather than perfectly strict rate limiting for every request.

class SlidingCounter:
    def __init__(self, limit, window_ms):
        self.limit = limit
        self.window_ms = window_ms
        self.current = 0
        self.prev = 0
        self.last_switch = time.time()

    def _rotate(self):
        now = time.time()
        if now - self.last_switch >= self.window_ms / 1000:
            self.prev = self.current
            self.current = 0
            self.last_switch = now

    def allow(self):
        now = time.time()
        self._rotate()
        # Weighted sum of two windows (approximation)

        weight = (now - self.last_switch) / (self.window_ms / 1000)
        estimated = self.current + self.prev * (1 - weight)
        if estimated < self.limit:
            self.current += 1
            return True
        return False

Reference: Sliding Window Counter implementation notes in 04. Rate Limiter/Readme.md【Sliding Window Counter】

Summary

• Token Bucket and Leaking Bucket offer the best memory efficiency, with Token Bucket favoring burst tolerance and Leaking Bucket favoring smooth output.
• Fixed Window Counter provides the simplest implementation but suffers from edge-window spike issues at boundary transitions.
• Sliding Window Log delivers perfect accuracy by storing every timestamp, incurring high memory costs suitable only for strict, low-volume requirements.
• Sliding Window Counter represents the middle ground, approximating sliding window behavior with minimal memory overhead compared to full logging.

All five algorithms are comprehensively documented in the 04. Rate Limiter/Readme.md file of the liquidslr/system-design-notes repository.

Frequently Asked Questions

What is the most memory-efficient rate limiting algorithm?

Token Bucket and Leaking Bucket are the most memory-efficient rate limiting algorithms because they only store a single counter or small queue rather than individual request timestamps. Both algorithms maintain O(1) space complexity regardless of request volume, making them ideal for high-throughput systems.

Which rate limiting algorithm handles burst traffic best?

The Token Bucket algorithm naturally accommodates bursts by allowing clients to consume accumulated tokens up to the bucket capacity. Unlike Leaking Bucket, which smooths traffic into a constant outflow, or Fixed Window Counter, which rigidly blocks at boundaries, Token Bucket permits legitimate traffic spikes while maintaining long-term average rates.

How do Sliding Window Log and Sliding Window Counter differ?

Sliding Window Log stores every request timestamp to calculate exact rates within the window, providing perfect accuracy at the cost of O(n) memory usage where n is the request count. Sliding Window Counter approximates this behavior using two fixed windows and weighted averaging, reducing memory usage to O(1) while accepting minor precision trade-offs.

When should I use Fixed Window Counter over Sliding Window algorithms?

Use Fixed Window Counter when system resources are severely constrained and you can tolerate boundary conditions where twice the allowed request rate might occur at window edges. Avoid it for financial or strict contractual rate limiting where Sliding Window Log or Sliding Window Counter provide necessary precision against edge-window spikes.

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