Sliding Log Algorithm — Complete Precise Rate Limiting Guide

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

Sliding log (or Sliding Window log) stores a timestamped log of every request. When a new request arrives, it counts how many timestamps fall within the window. It provides the most accurate Rate Limiting.

What You'll Learn

You'll learn how sliding log works, its trade-offs compared to other algorithms, and when to use it.

Why It Matters

Sliding log is the most accurate algorithm but also the most memory-intensive. Use it when precision is critical and your rate limits are relatively low.

Real-World Use

An authentication API uses sliding log for login rate limiting (5 attempts per 15 minutes). The high precision ensures attackers are blocked at exactly the 5th attempt, not approximately.

Implementation

import time
from collections import deque
import threading

class SlidingLog:
    def __init__(self, limit, window_seconds):
        self.limit = limit
        self.window_seconds = window_seconds
        self.logs = {}
        self.lock = threading.Lock()

    def is_allowed(self, client_id):
        now = time.time()
        cutoff = now - self.window_seconds
        with self.lock:
            if client_id not in self.logs:
                self.logs[client_id] = deque()
            log = self.logs[client_id]
            while log and log[0] < cutoff:
                log.popleft()
            if len(log) >= self.limit:
                return False, max(0, cutoff - log[0])
            log.append(now)
            return True, 0

    def oldest_timestamp(self, client_id):
        log = self.logs.get(client_id)
        if log:
            return log[0]
        return None

limiter = SlidingLog(limit=5, window_seconds=900)
client = "user@example.com"
for i in range(6):
    allowed, retry_after = limiter.is_allowed(client)
    print(f"Attempt {i+1}: {'Allowed' if allowed else f'Wait {retry_after:.0f}s'}")

Common Mistakes

| Mistake | Fix | |---------|-----| | No cleanup of old entries | Memory leak | Purge entries outside window on each request | | Using list instead of deque | O(n) removal from front | Use collections.deque for O(1) popleft | | No Thread Safety | Race conditions on log | Use locks or atomic operations | | High memory for high-rate APIs | Each request stored in memory | Use sliding window with counter estimation for high rates | | Not returning retry_after | Client does not know when to retry | Calculate and return wait time |

Practice Questions

1. When should you use sliding log over sliding window?
2. What is the memory complexity of sliding log?
3. How do you calculate retry-after time?
4. Why is deque better than list for sliding log?
5. How do you implement sliding log with Redis?

Challenge

Implement sliding log for an auth endpoint: 5 attempts per 15 minutes. Return remaining attempts and retry-after. Test by sending 6 rapid requests.

What's Next

Learn about Redis implementation for distributed rate limiting.