Sliding Window Counter Algorithm

1. One-Liner

The Sliding Window Counter is a hybrid of Fixed Window and Sliding Window Log. It keeps counts for the previous and current window, computes a weighted count, and uses O(1) memory while smoothing the boundary burst problem.

2. The Problem It Solves

Fixed Window allows a 2x burst at boundaries. Sliding Window Log is precise but uses O(n) memory. The Sliding Window Counter gives a good balance: O(1) memory with better accuracy than Fixed Window. The weighted formula reduces boundary bursts.

3. The Core Idea

Track prev_count (previous window) and curr_count (current window). The weighted count is:

weighted = prev_count × (1 - t) + curr_count

where t = fraction of current window elapsed. As time progresses, the previous window contributes less. If weighted >= limit, deny; else increment curr_count and allow.

4. How It Works

Step	What Happens
1. Get time	Get current timestamp
2. Calc window	window_id = now / window_size
3. Check window change	New window? Roll prev=curr, curr=0
4. Calc fraction	t = elapsed / window_size
5. Calc weighted	weighted = prev × (1-t) + curr
6. Check limit	weighted >= limit?
7a. YES → Deny	Over limit
7b. NO → Allow	Increment curr, allow

5. Key Properties

Property	Value
Boundary burst	Reduced vs Fixed Window
Memory	O(1) — prev, curr, window_id
Accuracy	Better than Fixed, less than Log
Best for	Balance of accuracy and efficiency

Implementation Example (PYTHON)

import time

class SlidingWindowCounter:
    def __init__(self, window_size, limit):
        self.window_size = window_size
        self.limit = limit
        self.prev_count = 0
        self.curr_count = 0
        self.current_window = 0

    def try_allow(self):
        now = time.monotonic()
        window_id = int(now / self.window_size)
        if window_id != self.current_window:
            self.prev_count = self.curr_count
            self.curr_count = 0
            self.current_window = window_id
        elapsed = now - self.current_window * self.window_size
        fraction = elapsed / self.window_size
        weighted = self.prev_count * (1 - fraction) + self.curr_count
        if weighted >= self.limit:
            return False   # DENY
        self.curr_count += 1
        return True        # ALLOW