Sliding Window Log Limiter
Hard · Rate Limiting
A sliding window log limiter remembers the time of every allowed request, so a limit like "at most 3 requests in any 1000 ms" is enforced exactly (a fixed window would allow bursts at window edges). Real APIs often combine several limits, for example 3 per second and also 5 per 10 seconds, so both short bursts and long-term use are capped.
Implement SlidingWindowLimiter(rules), where rules is a list of { limit, windowMs } (every limit is at least 1). Each key has one log with the times of its allowed requests.
- hit(key, now) returns { allowed, remaining, retryAfter }. For each rule, count the entries of the key's log that are inside that rule's window: an entry at time t is inside while now - t < windowMs.
- The request is allowed only if every rule has fewer than limit entries in its window. Then now is added to the log. A denied request is not recorded, so it does not count against any rule.
- remaining: for each rule, limit minus its count after this request. Return the smallest of these numbers.
- retryAfter is 0 for an allowed request. For a denied one it is how many ms the client must wait until a request would be allowed, if it sends nothing in between. Every full rule must wait until the oldest entry inside its window leaves that window (oldest + windowMs - now), and the client has to wait for the slowest of those rules.
- Entries older than the largest window can never matter again, so drop them to keep memory bounded.
- sweep(now) drops the entries that left the largest window from every key, deletes keys whose log became empty (so idle clients do not leak memory), and returns { removed, keys }: how many keys were deleted and how many are left.
now never decreases. The driver runSlidingLimiter(rules, ops) is already written. Operations are ["hit", key, now] or ["sweep", now], and it returns every result.