1. One-Liner
The Sliding Window Log keeps a sorted log of all request timestamps. On each request, it removes entries older than the window, counts what remains, and denies if at limit.
2. The Problem It Solves
Fixed Window can allow a 2x burst at window boundaries. Token Bucket uses O(1) memory but approximates. Sliding Window Log gives precise rate limiting: exactly N requests per sliding window of W seconds, with no boundary bursts.
3. The Core Idea
Imagine a scroll of timestamps: every time a request arrives, you add its time to the scroll. Before adding, you erase any timestamps older than W seconds. Count what's left. If count >= limit, deny. Otherwise add and allow.
The window "slides" forward with time — old entries drop off, new ones are added. No fixed boundaries.
4. How It Works
| Step | What Happens |
|---|---|
| 1. Get time | Get current timestamp |
| 2. Calc cutoff | cutoff = now - windowSize |
| 3. Remove expired | Filter out timestamps <= cutoff |
| 4. Count remaining | count = len(log) |
| 5. Check limit | count >= limit? |
| 6a. YES → Deny | Too many in window |
| 6b. NO → Allow | Append timestamp, allow |
5. Key Properties
| Property | Value |
|---|---|
| Precision | Exact — no boundary bursts |
| Memory | O(n) — stores all timestamps in window |
| Time per request | O(n) — filter + count |
| Best for | When accuracy matters more than memory |
Implementation Example (PYTHON)
import time
class SlidingWindowLog:
def __init__(self, window_size, limit):
self.window_size = window_size
self.limit = limit
self.log = [] # sorted timestamps
def try_allow(self):
now = time.monotonic()
cutoff = now - self.window_size
self.log = [t for t in self.log if t > cutoff]
count = len(self.log)
if count >= self.limit:
return False # DENY
self.log.append(now)
return True # ALLOW