Sliding-window request rate limiter

Implement a rate limiter that accepts at most limit requests in any window of ttl milliseconds.

class RateLimiter:
    def __init__(self, limit: int, ttl: int) -> None: ...
    def allow(self, timestamp: int) -> bool: ...

• allow(timestamp) is called once per incoming request. timestamp is in milliseconds, and calls arrive in non-decreasing time order.
• Return True and record the request if accepting it keeps the limiter within limit accepted requests in the window. Otherwise return False.
• A request accepted at time s counts against requests up to, but not including, time s + ttl. At s + ttl it no longer counts.
• Rejected requests do not use up capacity.
• The limit must hold for every window of length ttl, not just for fixed buckets such as [0, ttl), [ttl, 2*ttl).

Constraints

• 0 <= limit <= 10^5
• 1 <= ttl <= 10^9
• 0 <= timestamp <= 10^12
• Up to 10^6 calls to allow

Example 1

RateLimiter(limit=2, ttl=500)
allow(10)   -> True
allow(20)   -> True
allow(400)  -> False   # 10 and 20 are still in the window
allow(510)  -> True    # 10 expired at exactly 510
allow(515)  -> False   # 20 and 510 are in the window

Example 2

RateLimiter(limit=1, ttl=60)
allow(0)  -> True
allow(30) -> False
allow(45) -> False   # rejections do not extend the wait
allow(60) -> True

Aim for amortized O(1) time per call and O(limit) memory. Be ready to extend the limiter to many clients, each identified by a key.