Sliding window
A rate-limiting algorithm that counts requests in a rolling time window rather than fixed buckets, giving a smooth, accurate recent-rate limit. It avoids the burst-at-boundary problem of fixed windows. Implemented with weighted counters or a sorted request log.
- When boundary bursts are unacceptable.
- Billing/quota that must reflect true recent usage.
- When a simple fixed window is 'good enough' and you want minimum ops cost.
Definition
Instead of resetting at window boundaries, the limit covers the last N seconds ending now. Sliding-window-log stores timestamps; sliding-window-counter approximates by combining the previous and current fixed windows weighted by overlap.
Why it exists
Fixed windows let through 2x the limit at a boundary (a burst straddling two windows). Sliding windows close that loophole so the limit reflects actual recent demand.
How it works
Log approach: keep timestamps, evict older than window, count remaining. Counter approach: weighted_count = curr_count + prev_count * (overlap_fraction). The counter variant is O(1) and memory-light.
Scaling limits
Log variant memory grows with traffic in the window; counter variant is constant. Both need atomic updates in a shared store for distributed accuracy.
Cost shape
One counter per key (cheap) or a bounded ring of timestamps (bounded by window*rate). Hot keys still concentrate load.
Alternatives
- Fixed window — Cheapest, but allows 2x bursts at boundaries.
- Token bucket — Allows configured bursts; doesn't enforce a hard recent-rate cap.
Failure modes
- Log unbounded growth if eviction is skipped.
- Counter approximation drift at very high rates.