Building a Rate Limiter with the Sliding Window Pattern

A weekly series where we break down real systems — from the business problem, to the architecture, to the exact data structure that makes it work.

The Problem

Any public API needs a way to stop a single user (or a bug, or an attacker) from hammering it with requests. Without limits, one misbehaving client can degrade the service for everyone else.

Rate limiting is the answer: allow up to N requests per user in a given time window, and reject anything beyond that. Simple to state — but the naive implementation has a real bug that most people don't think about until it bites them in production.

Step 1: Define the Requirements

Functional requirements:

• Allow up to N requests per user within a rolling time window (e.g. 100 requests per minute)
• Reject requests beyond that limit with a clear response (HTTP 429)
• The limit should apply smoothly over time — not reset in a way that lets users burst past it

Non-functional requirements:

• The rate-limit check itself must be fast — it runs on every single API request, so it can't become the bottleneck
• Memory-efficient — a real API has thousands or millions of users, so the data structure per user needs to stay small
• Accurate under concurrent requests — the limiter can't be fooled by rapid parallel calls

Step 2: Why the Naive Approach Fails

The simplest idea: keep a counter per user, reset it every 60 seconds (a "fixed window").

This has a real, well-known flaw: boundary bursting. If a user sends 100 requests at 0:59 and another 100 at 1:01, they've sent 200 requests in 2 seconds — technically "within limit" for each window, but clearly violating the spirit of "100 requests per minute." A fixed window resets abruptly, so requests can cluster right at the reset boundary.

This is exactly why sliding window approaches exist — they don't have a hard reset point.

Step 3: The Data Structure — Sliding Window Log

The clean fix: instead of a single counter, track the timestamp of every request in a rolling window, and count how many fall within the last N seconds — recalculated on every request, not on a fixed reset schedule.

The natural data structure for this is a deque (double-ended queue):

• New requests get appended to the right
• Old requests (older than the window) get popped from the left
• The current count is simply the deque's length

Both operations — append and popleft — are O(1), which is exactly what we need since this runs on every request.

Python Implementation

from collections import deque
import time

class SlidingWindowRateLimiter:
    def __init__(self, max_requests: int, window_seconds: int):
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self.requests = {}  # user_id -> deque of timestamps

    def is_allowed(self, user_id: str) -> bool:
        now = time.time()
        window_start = now - self.window_seconds

        if user_id not in self.requests:
            self.requests[user_id] = deque()

        user_requests = self.requests[user_id]

        # Evict timestamps that have fallen out of the window — O(1) each
        while user_requests and user_requests[0] < window_start:
            user_requests.popleft()

        if len(user_requests) < self.max_requests:
            user_requests.append(now)
            return True

        return False  # rate limit exceeded


# Example usage: 5 requests per 10 seconds
limiter = SlidingWindowRateLimiter(max_requests=5, window_seconds=10)

for i in range(7):
    allowed = limiter.is_allowed("user_123")
    print(f"Request {i+1}: {'allowed' if allowed else 'blocked'}")

Because we evict expired timestamps on every call, the window is always accurate to the current moment — no boundary bursting, no abrupt resets.

Step 4: The Memory Trade-off — Sliding Window Counter

The Sliding Window Log above is precise, but storing every single timestamp per user gets expensive at high request volume. A common optimization: the Sliding Window Counter, which approximates the log using just two fixed-window counters (current and previous) and a weighted calculation between them, instead of storing every timestamp.

This trades a small amount of precision for a large reduction in memory — a classic engineering trade-off, and usually the right one at real scale.

Step 5: Trade-offs at Scale

The bottleneck: The implementation above works cleanly for a single server, but a real API typically runs behind a load balancer across multiple servers — a per-server in-memory deque doesn't see requests hitting other servers.

The fix: At real scale, rate limiting moves to a shared store like Redis, using sorted sets (ZADD/ZRANGEBYSCORE) to implement the same sliding-window-log logic, but accessible from every server. This is precisely why Redis is such a common piece of infrastructure in rate limiter designs — it gives you a fast, shared, atomic place to track this state.

Other real considerations we'd flag to a client:

• Token Bucket is a related, commonly used alternative — it allows short bursts up to a set limit while still enforcing an average rate, useful when occasional bursts are acceptable
• Rate limits are often tiered — different limits for free vs. paid API users, which means the limiter needs to know the caller's plan, not just their identity
• Returning proper Retry-After headers on a 429 response is a small detail that meaningfully improves the experience for legitimate API consumers

Where This Shows Up in Real Systems

This exact pattern is what powers rate limiting in API gateways (AWS API Gateway, Kong, Nginx), and it's the same reasoning behind Cloudflare's DDoS protection and per-IP throttling — different infrastructure, same underlying sliding-window idea.

Why We Build This Way

The naive fixed-window counter isn't "wrong" in an obvious way — it looks correct until you think about the boundary case. That's the pattern we care about across every system we design: it's rarely the happy path that breaks a product, it's the edge case nobody thought to check. That's the habit of mind we try to bring to every client project, not just the ones that happen to look like a classic algorithm problem.

This is Week 3 of Brainy Blueprints. Next week: the Trie, and how it powers search autocomplete.

📩 Want to talk through a scaling or performance problem in your product? [email protected]