Sliding Window Algorithm — Complete Smooth Rate Limiting Guide

In this tutorial, you will learn about Sliding Window Algorithm. We cover key concepts, practical examples, and best practices to help you master this topic.

Sliding window algorithm maintains a rolling time window. Instead of resetting at fixed boundaries, it evaluates the request count over the last N seconds continuously. This eliminates the boundary spike problem.

What You'll Learn

You'll learn how sliding window works, implementation approaches, and why it is preferred for most production APIs.

Why It Matters

Fixed window allows up to 2x traffic at boundary moments. Sliding window provides smooth, accurate Rate Limiting without spikes, making it the recommended approach for production APIs.

Real-World Use

GitHub API uses sliding window rate limiting. If you have 5000 requests per hour, you cannot send all 5000 in the last minute of one hour and first minute of the next as with fixed window.

flowchart LR
    A[Request at t=30s] --> B[Count requests from t-60s to t]
    B --> C{Counter < Limit?}
    C -->|Yes| D[Allow]
    C -->|No| E[Deny]
    D --> F[Add current timestamp]

Implementation

import time
from collections import defaultdict

class SlidingWindow:
    def __init__(self, limit, window_seconds):
        self.limit = limit
        self.window_seconds = window_seconds
        self.requests = defaultdict(list)

    def is_allowed(self, client_id):
        now = time.time()
        cutoff = now - self.window_seconds
        self.requests[client_id] = [
            t for t in self.requests[client_id]
            if t > cutoff
        ]
        if len(self.requests[client_id]) >= self.limit:
            return False
        self.requests[client_id].append(now)
        return True

    def remaining(self, client_id):
        now = time.time()
        cutoff = now - self.window_seconds
        active = [t for t in self.requests[client_id] if t > cutoff]
        return max(0, self.limit - len(active))

limiter = SlidingWindow(limit=100, window_seconds=60)
client = "api_key_abc"
print(f"Remaining: {limiter.remaining(client)}")

Common Mistakes

| Mistake | Fix | |---------|-----| | Not pruning old timestamps | Memory grows unbounded | Clean expired entries on each request | | Using in-memory for Distributed Systems | Limits not shared across instances | Use Redis sorted sets | | No timestamp precision | Sub-millisecond bursts not tracked | Use millisecond precision | | Integer instead of float timestamps | Loss of precision | Use time.time() with float | | Different clocks across servers | Inconsistent rate limiting | Synchronize clocks via NTP

Practice Questions

1. How does sliding window solve the boundary problem?
2. What data structure is best for sliding window?
3. How do you implement sliding window with Redis?
4. What is the memory cost of sliding window?
5. How do you handle clock skew in distributed sliding window?

Challenge

Implement sliding window with Redis sorted sets. Support 60-second window with 100 request limit. Include remaining count and reset time in response headers.

What's Next

Learn about the sliding log algorithm.