Requests arrive with a key (an API key) and an integer timestamp in seconds. Timestamps are non-decreasing across calls.
Implement the simplest policy: a fixed window counter.
class FixedWindowLimiter:
def __init__(self, limit: int, window: int): ...
def allow(self, key: str, ts: int) -> bool: ...
Rules:
- Time is chopped into fixed buckets of
window seconds starting at 0, so ts belongs to bucket ts // window.
allow returns True and records the request if the key has made fewer than limit requests in the current bucket, otherwise returns False.- Rejected requests do not count against the quota.
- Keys are independent of each other.
lim = FixedWindowLimiter(limit=2, window=10)
lim.allow("a", 0) # True
lim.allow("a", 3) # True
lim.allow("a", 9) # False (bucket 0 is full)
lim.allow("b", 9) # True (different key)
lim.allow("a", 10) # True (bucket 1)