Per-user sliding window rate limiter

Q: What if limit is 10,000 per hour? That is a lot of timestamps per user.

Switch to the sliding window counter approximation. Keep only two counters per user, one for the current fixed window and one for the previous window, and estimate previous * (fraction of previous window still overlapping) + current. It is O(1) memory per user and slightly inexact at window edges. Many production limiters use it for exactly this reason. The sliding log is exact but costs memory proportional to limit.

Q: How would this look in Go, and in production?

In Go: map[string][]time.Time (a slice used as a queue, re-sliced from the front) or a small ring buffer per user, behind a sync.Mutex or a sharded set of mutexes keyed by user hash. Across several instances you move the log to Redis: a sorted set per user, with ZREMRANGEBYSCORE to drop old entries, ZCARD to count and ZADD to record, run inside one Lua script so the check-and-add is atomic.

mediumRate limiting and resilience Must-do

Build a rate limiter that allows each user at most limit requests in any rolling window of window seconds. A fixed-window counter ("100 per calendar minute") lets a user send 100 requests at 12:00:59 and 100 more at 12:01:00. A sliding window closes that loophole.

API (Java: same names, DoubleSupplier clock)

◈ DIAGRAM

SlidingWindowLimiter(limit: int, window: float, clock=time.monotonic)
allow(user: str) -> bool     # accept and record the request, or reject it
remaining(user: str) -> int  # requests the user could make right now

Rules

A request at time now is accepted if fewer than limit accepted requests from the same user have timestamps in the half-open interval (now - window, now]. So a request made exactly window seconds ago no longer counts.
Rejected requests are not recorded. A client that keeps hammering does not extend its own ban.
Users are independent.
Memory must not grow with total traffic. Per user it may hold at most limit timestamps, and a user with no requests in the current window should cost no memory.
limit < 1 or window <= 0 raises ValueError.

Outputs are the return values of each call, in order, with the fake clock at t.

Examples

Example 1

Input: t=0 rl = SlidingWindowLimiter(limit=2, window=10) t=0 rl.allow("alice") t=1 rl.allow("alice") t=2 rl.allow("alice") t=2 rl.allow("bob") t=10 rl.allow("alice") t=10 rl.allow("alice") t=10 rl.remaining("alice") t=11 rl.remaining("alice")

Output: true true false true true false 0 1

Explanation: At t=10 the request from t=0 has left the window (0, 10], so one slot is free. At t=11 the t=1 request also expires.

Example 2

Input: t=0 rl = SlidingWindowLimiter(limit=3, window=60) t=0 rl.allow("ci-runner") t=5 rl.allow("ci-runner") t=30 rl.allow("ci-runner") t=59 rl.allow("ci-runner") t=61 rl.allow("ci-runner") t=61 rl.remaining("ci-runner")

Output: true true true false true 0

Explanation: The rejected request at t=59 was not recorded. At t=61 the window (1, 61] holds the t=5 and t=30 requests, so one more fits.

Hints

Approach

This is the sliding log algorithm with a deque per user.

_evict(user, now): pop timestamps from the left while q[0] <= now - window. They have left the window. If the deque becomes empty, delete the user's entry so idle users take no memory.
allow: evict, then if len(q) >= limit reject without recording. Otherwise append now and accept.
remaining: evict, then return limit - len(q).

Each timestamp is appended once and popped once, so the cost is O(1) amortised. A deque never holds more than limit entries, because a full deque rejects.

ComplexityTime O(1) amortised per callSpace O(limit) per active user

Python

import time
from collections import deque
 
 
class SlidingWindowLimiter:
    def __init__(self, limit, window, clock=time.monotonic):
        if limit < 1 or window <= 0:
            raise ValueError("limit must be >= 1 and window > 0")
        self.limit = limit
        self.window = window
        self.clock = clock
        self.log = {}                  # user -> deque of accepted timestamps, oldest first
 
    def _evict(self, user, now):
        q = self.log.get(user)
        if q is None:
            return None
        while q and q[0] <= now - self.window:   # outside (now - window, now]
            q.popleft()
        if not q:
            del self.log[user]         # idle users cost no memory
            return None
        return q
 
    def allow(self, user):
        now = self.clock()
        q = self._evict(user, now)
        if q is None:
            q = self.log[user] = deque()
        if len(q) >= self.limit:
            return False               # rejected requests are not recorded
        q.append(now)
        return True
 
    def remaining(self, user):
        q = self._evict(user, self.clock())
        return self.limit - (len(q) if q else 0)

Follow-up questions

Different limits per plan tier (free: 10/min, paid: 1000/min). Where does that config live?
Return how long the client should wait before retrying (the oldest timestamp plus window, minus now).
Make it safe for many threads without one global lock.

Frequently asked questions

Switch to the sliding window counter approximation. Keep only two counters per user, one for the current fixed window and one for the previous window, and estimate previous * (fraction of previous window still overlapping) + current. It is O(1) memory per user and slightly inexact at window edges. Many production limiters use it for exactly this reason. The sliding log is exact but costs memory proportional to limit.

In Go: map[string][]time.Time (a slice used as a queue, re-sliced from the front) or a small ring buffer per user, behind a sync.Mutex or a sharded set of mutexes keyed by user hash. Across several instances you move the log to Redis: a sorted set per user, with ZREMRANGEBYSCORE to drop old entries, ZCARD to count and ZADD to record, run inside one Lua script so the check-and-add is atomic.