Sliding Window Algorithm — Accurate Rate Limiting Without Boundary Spikes

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.

The sliding window algorithm maintains a moving time window that slides forward with each request, providing accurate Rate Limiting without the boundary spikes of fixed window by tracking request timestamps within the window.

What You'll Learn

• How sliding window eliminates the boundary problem
• Sliding window vs. fixed window comparison
• Redis sorted set implementation

Why It Matters

The boundary problem in fixed window allows 2x the intended rate. Sliding window solves this by moving the window continuously, ensuring that at any moment the count reflects only the last N seconds of traffic.

Real-World Use

Durga Antivirus Pro uses sliding window for its premium API tier. With 1000 req/min limits, even a 2x burst at the boundary would overwhelm the backend. Sliding window guarantees that no 60-second period ever sees more than 1000 requests.

flowchart LR
    subgraph "Sliding Window"
        T1["12:00:30\nCount: 45"] --> T2["12:01:00\nCount: 52"]
        T2 --> T3["12:01:30\nCount: 38"]
        T3 --> T4["12:02:00\nCount: 61"]
    end
    Window["Window: last 60s\nAlways moving"] --> T4
    style Window fill:#dbeafe,stroke:#2563eb

Sliding Window with Redis Sorted Sets

import time
import redis

class SlidingWindowRateLimiter:
    def __init__(self, redis_client):
        self.redis = redis_client

    def allow_request(self, client_id, max_requests, window_seconds):
        now = time.time()
        key = f"sw:{client_id}"
        window_start = now - window_seconds

        # Remove timestamps outside the window
        self.redis.zremrangebyscore(key, 0, window_start)

        # Count remaining requests in window
        current_count = self.redis.zcard(key)

        if current_count >= max_requests:
            return False, current_count

        # Add current request timestamp
        self.redis.zadd(key, {str(now): now})
        self.redis.expire(key, window_seconds * 2)
        return True, current_count + 1

    def get_remaining(self, client_id, max_requests, window_seconds):
        now = time.time()
        key = f"sw:{client_id}"
        window_start = now - window_seconds
        self.redis.zremrangebyscore(key, 0, window_start)
        count = self.redis.zcard(key)
        return max(0, max_requests - count)

Sliding Window Without Redis (In-Memory)

from collections import deque
import time
import threading

class InMemorySlidingWindow:
    def __init__(self, max_requests, window_seconds):
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self.timestamps = deque()
        self.lock = threading.Lock()

    def allow_request(self):
        with self.lock:
            now = time.monotonic()
            cutoff = now - self.window_seconds

            # Remove expired timestamps
            while self.timestamps and self.timestamps[0] < cutoff:
                self.timestamps.popleft()

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

    def remaining(self):
        with self.lock:
            now = time.monotonic()
            cutoff = now - self.window_seconds
            while self.timestamps and self.timestamps[0] < cutoff:
                self.timestamps.popleft()
            return max(0, self.max_requests - len(self.timestamps))

Usage Example

rl = InMemorySlidingWindow(max_requests=5, window_seconds=10)

for i in range(8):
    allowed = rl.allow_request()
    print(f"Request {i+1}: {'Allowed' if allowed else 'Blocked'}")

time.sleep(10)
print(f"\nAfter 10s wait: {rl.remaining()} remaining")

Expected output:

Request 1: Allowed
Request 2: Allowed
...
Request 5: Allowed
Request 6: Blocked
Request 7: Blocked
Request 8: Blocked

After 10s wait: 5 remaining

Sliding Window vs. Fixed Window

Common Mistakes

1. Not Cleaning Up Expired Timestamps

Without cleanup, the window grows unbounded. Always remove timestamps outside the window before counting.

2. Using Client Timestamps

Clients may have inaccurate clocks. Always use server time (time.monotonic() or time.time()).

3. Large Memory for High Limits

For 10,000 req/min, sliding window stores 10,000 timestamps per client. Use a hybrid approach (sliding window counter) for high limits.

4. Not Setting Redis TTL

Without TTL, stale keys for inactive clients accumulate. Set TTL to 2x the window size.

5. Performance Issues with Sorted Sets

ZADD and ZREMRANGEBYSCORE are O(log N). For very high throughput, consider a sliding window counter approximation.

Practice Questions

1. How does sliding window eliminate the fixed window boundary problem?
2. What data structure is typically used for sliding window implementation?
3. Why is sliding window more memory-intensive than fixed window?
4. How do you prevent unbounded memory growth in sliding window?
5. When would you choose fixed window over sliding window?

Answers:

1. The window slides continuously with time. There is no discrete boundary where the counter resets, so no boundary burst is possible.
2. A sorted set (Redis ZSET) or deque of timestamps, ordered by time, allowing efficient removal of expired entries.
3. Sliding window stores a timestamp for each request. Fixed window stores only a counter. For 1000 req/min, sliding window stores 1000 entries.
4. Remove expired timestamps before every check. Set Redis TTL to auto-cleanup inactive clients.
5. Choose fixed window when the boundary problem is acceptable (generous limits), when memory is constrained, or for simpler debugging.

Challenge: Implement a hybrid sliding window counter that divides the window into N buckets and estimates the count by weighting partial buckets, reducing memory to O(N) instead of O(requests).

FAQ

Mini Project

Build a sliding window rate limiter using Redis sorted sets. Implement per-client limits of 10 req/30 sec. Clean up expired entries on every request. Return remaining count and reset time in response headers.

What's Next

Continue with Sliding Log Algorithm for precise timestamp-based rate limiting, or explore Redis-Based Rate Limiting for production implementations.