Implement a Rate Limiter: Token Bucket, Leaky Bucket, Sliding Window

Implement a Rate Limiter: Token Bucket, Leaky Bucket, Sliding Window

Rate limiting is one of the most-asked system-design topics in 2026. It comes up at every API-heavy company — Stripe, Cloudflare, Twilio, Datadog, AWS — and at any company building public APIs at scale. The problem is conceptually simple but has enough variations and trade-offs to make a 30–45 minute interview round substantive. This guide covers the four standard rate-limiter algorithms (token bucket, leaky bucket, fixed window, sliding window), working code for each, the distributed-systems concerns at scale, and the design decisions that distinguish strong interview answers.

The Problem

A rate limiter restricts the number of requests a client can make within a time window. Common requirements:

• Allow N requests per window (e.g., 100 requests per minute per user)
• Reject or delay requests that exceed the limit
• Reset or refill counters as time passes
• Operate at low latency (typically <1ms decision time)
• Scale to millions of unique clients
• Survive process restarts and distributed deployments

The right algorithm depends on whether you want to allow short bursts (token bucket), enforce smooth output (leaky bucket), or minimize implementation complexity (fixed window).

Algorithm 1: Token Bucket

Each client has a bucket that holds up to capacity tokens. Tokens refill at refill_rate per second. Each request consumes one token; if no tokens are available, the request is rejected.

This algorithm allows controlled bursts (up to capacity requests if the bucket is full) while limiting steady-state throughput to refill_rate. Most public APIs use token bucket because of this burst-tolerance property.

import time
from threading import Lock

class TokenBucket:
    def __init__(self, capacity: int, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate  # tokens per second
        self.tokens = float(capacity)
        self.last_refill = time.monotonic()
        self.lock = Lock()

    def allow(self) -> bool:
        with self.lock:
            now = time.monotonic()
            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


# Usage: 100 requests per minute, burst of 10
bucket = TokenBucket(capacity=10, refill_rate=100/60)
for _ in range(15):
    print(bucket.allow())

Properties: Allows bursts up to capacity; long-term rate capped at refill_rate. O(1) per request. Memory: O(1) per client.

Algorithm 2: Leaky Bucket

Same metaphor (a bucket), different mechanics. Requests enter a queue; the queue is drained at a fixed rate. Excess requests overflow and are dropped.

Unlike token bucket, leaky bucket smooths the output rate — even if requests arrive in bursts, they’re processed at constant rate. Used in network traffic shaping where output smoothness matters more than burst tolerance.

from collections import deque
import time
from threading import Lock

class LeakyBucket:
    def __init__(self, capacity: int, leak_rate: float):
        self.capacity = capacity
        self.leak_rate = leak_rate  # requests per second
        self.queue = deque()
        self.last_leak = time.monotonic()
        self.lock = Lock()

    def allow(self) -> bool:
        with self.lock:
            now = time.monotonic()
            elapsed = now - self.last_leak
            leaked = int(elapsed * self.leak_rate)
            for _ in range(min(leaked, len(self.queue))):
                self.queue.popleft()
            if leaked > 0:
                self.last_leak = now
            if len(self.queue) < self.capacity:
                self.queue.append(now)
                return True
            return False

Properties: Smooth output rate; doesn’t allow bursts. Used in routers and traffic shapers where downstream consumers can’t handle bursts.

Algorithm 3: Fixed Window Counter

Count requests within fixed time windows (e.g., a 1-minute window). Reset the counter at the start of each window. Reject requests when the counter exceeds the limit.

import time
from threading import Lock

class FixedWindow:
    def __init__(self, limit: int, window_seconds: int):
        self.limit = limit
        self.window = window_seconds
        self.count = 0
        self.window_start = self._current_window()
        self.lock = Lock()

    def _current_window(self) -> int:
        return int(time.monotonic()) // self.window

    def allow(self) -> bool:
        with self.lock:
            current = self._current_window()
            if current != self.window_start:
                self.window_start = current
                self.count = 0
            if self.count < self.limit:
                self.count += 1
                return True
            return False

Properties: Simple, O(1) memory and time. Major flaw: 2× burst at window boundaries. If the limit is 100/minute and 100 requests come in the last second of one window plus 100 in the first second of the next, the client gets 200 requests in 2 seconds despite the “100/minute” limit.

Algorithm 4: Sliding Window Log

Track the timestamp of every request in the past window. Count timestamps within the window; reject if count exceeds limit.

from collections import deque
import time
from threading import Lock

class SlidingWindowLog:
    def __init__(self, limit: int, window_seconds: int):
        self.limit = limit
        self.window = window_seconds
        self.timestamps = deque()
        self.lock = Lock()

    def allow(self) -> bool:
        with self.lock:
            now = time.monotonic()
            cutoff = now - self.window
            while self.timestamps and self.timestamps[0] < cutoff:
                self.timestamps.popleft()
            if len(self.timestamps) < self.limit:
                self.timestamps.append(now)
                return True
            return False

Properties: Exact rate enforcement; no boundary bursts. Cost: O(N) memory per client where N is the limit. For limit=10000, this stores 10000 timestamps per client — substantial at scale.

Algorithm 5: Sliding Window Counter (Hybrid)

Combines fixed-window simplicity with sliding-window accuracy. Track counters for the current and previous window; estimate the sliding count via weighted interpolation.

import time
from threading import Lock

class SlidingWindowCounter:
    def __init__(self, limit: int, window_seconds: int):
        self.limit = limit
        self.window = window_seconds
        self.current_count = 0
        self.previous_count = 0
        self.window_start = self._current_window_start()
        self.lock = Lock()

    def _current_window_start(self) -> float:
        now = time.monotonic()
        return now - (now % self.window)

    def allow(self) -> bool:
        with self.lock:
            now = time.monotonic()
            current_start = self._current_window_start()
            if current_start != self.window_start:
                self.previous_count = self.current_count if (
                    current_start - self.window_start == self.window) else 0
                self.current_count = 0
                self.window_start = current_start
            elapsed_in_window = now - self.window_start
            weight = (self.window - elapsed_in_window) / self.window
            estimated = self.previous_count * weight + self.current_count
            if estimated < self.limit:
                self.current_count += 1
                return True
            return False

Properties: O(1) memory per client; approximate accuracy (weighted estimate). The standard production algorithm at most large-scale APIs because of the memory-vs-accuracy trade-off.

Distributed Rate Limiting

The above implementations are single-process. At scale, requests for the same client can hit any of N servers, requiring shared state.

Centralized counter (Redis)

Most common approach. Use Redis with atomic increments (INCR + EXPIRE) for fixed/sliding windows; or Lua scripts for token bucket atomicity.

# Pseudo-code: token bucket via Redis Lua script
LUA_SCRIPT = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local tokens = tonumber(redis.call('hget', key, 'tokens') or capacity)
local last_refill = tonumber(redis.call('hget', key, 'last_refill') or now)
local elapsed = now - last_refill
tokens = math.min(capacity, tokens + elapsed * refill_rate)
if tokens >= 1 then
    redis.call('hset', key, 'tokens', tokens - 1, 'last_refill', now)
    return 1
end
redis.call('hset', key, 'tokens', tokens, 'last_refill', now)
return 0
"""

Trade-offs: every request hits Redis (latency), single point of failure, single hot key for popular clients. Use Redis Cluster + sharded keys to scale.

Local + sync

Each server enforces its own limit (e.g., 100/N requests/min if there are N servers). Clients see the aggregate effect. Drift exists but bounded; eventually-consistent. Lower latency, less centralized; allows brief over-limit during traffic shifts.

Approximate algorithms

Count-min sketch for approximate counting at extreme scale. Trade accuracy for memory; useful when you have millions of distinct clients and per-client storage matters.

Common Interview Discussion Points

Choose the right algorithm

Token bucket for public APIs (allows bursts, intuitive for developers). Sliding window counter for high-volume internal APIs (memory-efficient, smooth enough). Fixed window for simple internal use cases where boundary bursts are acceptable.

Per-client identity

By API key, user ID, IP address, or composite. Discuss how to handle authenticated vs anonymous, NAT and shared IPs, and abuse mitigation.

Headers and response

Standard headers: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, Retry-After. Standard status: 429 Too Many Requests. Discuss what makes the API friendly to clients (predictable, observable).

Different limits for different endpoints

Auth endpoints often have stricter limits than read endpoints. Discuss how to express this — per-route limits, tier-based limits (free vs paid users), endpoint-class limits.

Failure modes

What happens if Redis is down? Fail-open (let requests through) vs fail-closed (reject all). Most production systems fail-open with degraded local enforcement; security-sensitive endpoints fail-closed.

Frequently Asked Questions

See also: Producer-Consumer Problem • Fair Server Processing • Order Book Dynamics

class TokenBucketRateLimiter {
    constructor(capacity, refillRate) {
        this.capacity = capacity;  // Max tokens
        this.refillRate = refillRate;  // Tokens per second
        this.buckets = new Map();  // userId -> bucket state
    }

    // Returns true if request is allowed, false if rate limited
    allowRequest(userId) {
        const now = Date.now() / 1000;  // Current time in seconds

        if (!this.buckets.has(userId)) {
            // First request from this user
            this.buckets.set(userId, {
                tokens: this.capacity - 1,  // Consume 1 for this request
                lastRefill: now
            });
            return true;
        }

        const bucket = this.buckets.get(userId);

        // Calculate tokens to add since last refill
        const timePassed = now - bucket.lastRefill;
        const tokensToAdd = timePassed * this.refillRate;

        // Refill bucket (up to capacity)
        bucket.tokens = Math.min(
            this.capacity,
            bucket.tokens + tokensToAdd
        );
        bucket.lastRefill = now;

        // Check if we have a token available
        if (bucket.tokens >= 1) {
            bucket.tokens -= 1;
            return true;  // Request allowed
        }

        return false;  // Rate limited
    }

    // Get current token count for user (for debugging)
    getTokens(userId) {
        if (!this.buckets.has(userId)) {
            return this.capacity;
        }

        const bucket = this.buckets.get(userId);
        const now = Date.now() / 1000;
        const timePassed = now - bucket.lastRefill;
        const tokensToAdd = timePassed * this.refillRate;

        return Math.min(this.capacity, bucket.tokens + tokensToAdd);
    }
}

// Test
const limiter = new TokenBucketRateLimiter(5, 1);  // 5 tokens, refill 1/sec

// Make 5 quick requests
for (let i = 0; i < 5; i++) {
    console.log(`Request ${i + 1}:`, limiter.allowRequest("user1"));
}
// All should be true

console.log("Request 6:", limiter.allowRequest("user1"));
// false (rate limited)

// Wait 2 seconds
setTimeout(() => {
    console.log("After 2 seconds:", limiter.allowRequest("user1"));
    // true (2 tokens refilled)

    console.log("Tokens remaining:", limiter.getTokens("user1"));
    // ~1 token
}, 2000);

class SlidingWindowRateLimiter {
    constructor(limit, windowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
        this.requests = new Map();  // userId -> array of timestamps
    }

    allowRequest(userId) {
        const now = Date.now();
        const windowStart = now - this.windowMs;

        if (!this.requests.has(userId)) {
            this.requests.set(userId, []);
        }

        const userRequests = this.requests.get(userId);

        // Remove old requests outside window
        while (userRequests.length > 0 &&
               userRequests[0] < windowStart) {
            userRequests.shift();
        }

        // Check if under limit
        if (userRequests.length < this.limit) {
            userRequests.push(now);
            return true;
        }

        return false;  // Rate limited
    }
}

// Test
const limiter2 = new SlidingWindowRateLimiter(3, 1000);  // 3 per second

console.log(limiter2.allowRequest("user1"));  // true
console.log(limiter2.allowRequest("user1"));  // true
console.log(limiter2.allowRequest("user1"));  // true
console.log(limiter2.allowRequest("user1"));  // false (rate limited)

setTimeout(() => {
    console.log(limiter2.allowRequest("user1"));  // true (window moved)
}, 1100);

class FixedWindowRateLimiter {
    constructor(limit, windowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
        this.windows = new Map();  // userId -> {count, windowStart}
    }

    allowRequest(userId) {
        const now = Date.now();
        const windowStart = Math.floor(now / this.windowMs) * this.windowMs;

        if (!this.windows.has(userId)) {
            this.windows.set(userId, {count: 0, windowStart});
        }

        const window = this.windows.get(userId);

        // New window?
        if (window.windowStart < windowStart) {
            window.count = 0;
            window.windowStart = windowStart;
        }

        // Check limit
        if (window.count < this.limit) {
            window.count++;
            return true;
        }

        return false;
    }
}

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 47
X-RateLimit-Reset: 1612345678