Sliding Log Algorithm — Precise Rate Limiting with Timestamp Granularity

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.

The sliding log algorithm maintains a timestamped log of every request, removing entries outside the time window and counting remaining entries, providing the most accurate rate limiting at the cost of higher memory and processing overhead.

What You'll Learn

• How sliding log provides per-request accuracy
• When to use sliding log vs. sliding window
• Memory and performance trade-offs

Why It Matters

For strict SLAs or regulatory requirements, every request must be counted precisely. Sliding log guarantees that at any instant, the count reflects exactly the requests in the last N seconds, with no approximations or boundary issues.

Real-World Use

Durga Antivirus Pro's Compliance audit API uses sliding log rate limiting. Regulatory requirements mandate that no more than 1000 audit log queries occur in any rolling 60-minute period. Sliding log provides the precision needed for audit compliance.

flowchart LR
    subgraph "Sliding Log"
        Log["Request Log:\n[12:01:01, 12:01:05, 12:01:30, ...]"]
        Prune["Prune: remove\nentries < cutoff"]
        Count["Count: entries\nin window"]
        Check["Check: count\n< limit?"]
    end
    Log --> Prune --> Count --> Check
    style Log fill:#dbeafe,stroke:#2563eb

Sliding Log Implementation

import time
from collections import deque
import threading

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

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

            # Prune expired entries
            while self.log and self.log[0] < cutoff:
                self.log.popleft()

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

    def get_log_size(self):
        with self.lock:
            return len(self.log)

    def get_oldest_entry(self):
        with self.lock:
            return self.log[0] if self.log else None

Redis Sliding Log

import time
import json

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

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

        # Lua script for atomic operations
        lua_script = """
        local key = KEYS[1]
        local cutoff = tonumber(ARGV[1])
        local now = tonumber(ARGV[2])
        local max_req = tonumber(ARGV[3])

        -- Remove expired entries
        redis.call('ZREMRANGEBYSCORE', key, 0, cutoff)

        -- Count remaining
        local count = redis.call('ZCARD', key)

        if count < max_req then
            redis.call('ZADD', key, now, now)
            redis.call('EXPIRE', key, ARGV[4])
            return {1, max_req - count - 1}
        else
            return {0, 0}
        end
        """
        result = self.redis.eval(
            lua_script, 1, key, cutoff, now,
            max_requests, window_seconds * 2
        )
        allowed = result[0] == 1
        remaining = result[1]
        return allowed, remaining

Log Pruning Strategy

Efficient pruning is critical for performance:

class OptimizedSlidingLog:
    def __init__(self, max_requests, window_seconds, prune_interval=100):
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self.log = deque()
        self.lock = threading.Lock()
        self.counter = 0
        self.prune_interval = prune_interval

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

            # Prune only every N requests for efficiency
            self.counter += 1
            if self.counter >= self.prune_interval:
                while self.log and self.log[0] < cutoff:
                    self.log.popleft()
                self.counter = 0

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

Common Mistakes

1. Not Pruning the Log

Without pruning, the log grows forever, consuming memory and slowing lookups. Always prune expired entries.

2. Pruning on Every Request

For high-traffic systems, pruning on every request is expensive. Prune periodically or use probabilistic pruning.

3. Using the Log as Permanent Storage

The sliding log is ephemeral state. Redis should use TTL. In-memory log should be rebuilt if the application restarts.

4. High Memory for Long Windows

For 10,000 req/hour per client, the log holds 10,000 timestamps. For 10,000 clients, that is 100 million entries. Use sliding window counter instead.

5. Clock Skew in Distributed Logs

Server clock drift causes incorrect pruning or window calculation. Use NTP-synchronized clocks or monotonic timestamps.

Practice Questions

1. How does sliding log differ from sliding window in implementation?
2. When is sliding log necessary despite its memory cost?
3. How do you keep the log from growing without bound?
4. Why is pruning on every request potentially expensive?
5. What is the memory cost of sliding log for 50 req/min per client with 1000 clients?

Answers:

1. Sliding log stores every request timestamp. Sliding window may use approximations or weighted buckets.
2. When regulatory compliance requires exact counts, or when debugging requires exact request history.
3. Prune expired entries on every check (or periodically) and set TTL on Redis keys.
4. ZREMRANGEBYSCORE is O(log N). For 1000 entries per check, 1000 req/sec means 1 million log operations per second.
5. 50 entries/min * 1000 clients = 50,000 timestamps. Each timestamp ~16 bytes = 800 KB. Acceptable for most systems.

Challenge: Compare sliding log and sliding window memory usage for 10,000 clients with 100 req/min limits. Calculate the memory savings of sliding window and determine the crossover point where sliding window is preferred.

FAQ

Mini Project

Build a sliding log rate limiter for a compliance audit API. Limit: 100 queries per rolling 60 minutes per API key. Store logs in Redis sorted sets. Add an admin endpoint to view the current log for any client. Implement efficient pruning every 50 requests.

What's Next

Continue with Redis-Based Rate Limiting for production-grade distributed implementations, or explore Distributed Rate Limiting for multi-region systems.