Build a thread-safe rate limiter

Why is a rate limiter not thread safe as written?

Because allow is a check followed by a record: count the calls in the window, and if there is room, add this one. Two threads can both count before either records, both see room, and both record. Under a limit of two, three callers arriving together can all be let through, and a recorded run of a model of the threads shows exactly that. The global interpreter lock does not help, because the check and the record are separate steps and a thread can be switched out between any two steps.

One lock for the whole limiter, or one lock per client?

Start with one lock, held across the check and the record. It is correct, it is three lines, and a reviewer can check it by reading. Its cost is that callers for unrelated clients queue behind each other: on one recorded schedule, the one caller for a second client was refused turns by a lock it had no reason to want. A lock per client removes that wait, and costs one lock object per client and a safe way to create it.

How do I create the per-client lock safely?

Look the client up, and create it if it is missing, while holding one short registry lock, and create the client's lock and its state together as one object. Creating the lock lazily without that guard is a race of its own: two threads can both find the client missing, both build a lock, and each then holds a different lock for the same client. Hold the registry lock only for the lookup, never for the check and the record, or every client waits on it again.

Does a token bucket need a background thread to refill it?

No, and it should not have one. Store the token count and the time it was last counted. On each call, add the tokens earned since then, which is the elapsed time multiplied by the rate, clip at the capacity, and spend one if there is one. There is no thread to start, stop, or race with, idle clients cost nothing, and a test moves time by setting a fake clock instead of sleeping.

How do I test threaded code in an interview without it being flaky?

Assert something that holds whatever the interleaving. Start many threads behind a barrier so they all call at once, use a fake clock that does not move, and assert that exactly the limit of them were let through. Join every thread before the assertion. A test that sleeps to make a race likely, or asserts that a race happened, passes on one machine and fails on another, so prove races with a written-down schedule instead.