Thread-safe per-user rate limiter

An API gateway gives each user limit requests per window. It runs on a server where 50 threads handle requests at once, all sharing one limiter.

Implement RateLimiter(limit: int, window: int) with allow(user: str, t: int) -> bool, a request from user at time t (milliseconds).

• Time is cut into fixed windows [0, window), [window, 2 * window), and so on.
• A request is allowed (True) if the user has had fewer than limit requests allowed in the window that contains t. Rejected requests don't count. Users never share counts.
• Thread safety: many threads call allow at the same time. Exactly limit requests per user per window may get True, never one more. The tests hammer the limiter from 50 threads and count every True.

For one user, t never goes backwards, and calls that run at the same moment for the same user share the same t.

r = RateLimiter(2, 1000)
r.allow("ann", 0)      # True
r.allow("ann", 10)     # True
r.allow("ann", 999)    # False  (2 already allowed in [0, 1000))
r.allow("bob", 999)    # True   (bob has his own count)
r.allow("ann", 1000)   # True   (a new window)
r.allow("ann", 1500)   # True
r.allow("ann", 1999)   # False
r.allow("ann", 5000)   # True

1 <= limit <= 10^5, 1 <= window <= 10^9, 0 <= t <= 10^9.