Fix the window reset in a tenant rate limiter
Your task
Your multi-tenant API limits each tenant to a number of requests per time window. The first version reset each tenant's count with a timer scheduled on every request, so a burst set off a cascade of resets that wiped counts in the middle of a window. The new version takes the tenant from the authenticated caller and works out the window from each request's timestamp.
An assistant wrote rate_limit_decisions(tenant_ids, timestamps_ms, max_per_window, window_ms). It is in the editor. It has a bug. Find it and fix it.
Input and output:
tenant_ids: the authenticated tenant for each request, in arrival order. Empty means the caller is not authenticated.timestamps_ms: each request's time in milliseconds. They never decrease.max_per_window: how many requests a tenant may make in one window.window_ms: the window length in milliseconds.- Return one boolean per request: true if it is allowed.
Rules the tests check:
- If the two lists differ in length, use only the first n requests, where n is the shorter length.
- A request with an empty tenant is denied and counts toward nothing.
- If
window_msormax_per_windowis 0 or less, deny every request. - A request's window is its timestamp divided by
window_ms, rounded down. Withwindow_ms1000, 0 to 999 is one window and 1000 to 1999 the next. - Each tenant has one count, for the window of its latest counted request. When a tenant's request falls in a different window from that one, its count starts again from 0.
- Every counted request adds 1 to its tenant's count, whether it is allowed or not. It is allowed when the count is then at most
max_per_window.
Examples
rate_limit_decisions(tenant_ids: list[str], timestamps_ms: list[int], max_per_window: int, window_ms: int) -> list[bool]Example 1
Input
rate_limit_decisions(["t1", "t1", "t1"], [0, 100, 200], 2, 60000)Output
[True, True, False]Example 2
Input
rate_limit_decisions(["t1", "", "t2"], [0, 0, 0], 1, 1000)Output
[True, False, True]