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

> Explore the five main rate limiting algorithms: Token Bucket, Leaking Bucket, Fixed Window Counter, Sliding Window Log, and Sliding Window Counter. Understand their trade-offs for effective API management.

- Repository: [Gaurav Kumar/system-design-notes](https://github.com/liquidslr/system-design-notes)
- Tags: deep-dive
- Published: 2026-09-09

---

**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.

```python
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.

```go
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.

```java
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.

```javascript
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.

```python
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.