Build a thread-safe rate limiter
A token bucket per key, built in three stages on real threads: one lock over the refill and the spend, a lock for the map and one per bucket, then a timed acquire and the removal of idle keys, each with its tests.
Why is a token bucket not thread safe without a lock?
Because a call is several steps: read the clock, add what was earned since the last call, check that a token is there, and spend it. Two threads can both read the same count, both see a token, and both spend it, so two calls get through on one token. The global interpreter lock does not prevent this: Python may switch threads between any two bytecode instructions, and each of those steps is several. Holding one lock across the refill, the check and the spend makes them one step as far as other threads can see.
One lock for the whole limiter, or one lock per key?
Start with one lock, because it is correct and short. Once keys are involved, give each key a bucket with its own lock, so callers for different keys never wait for each other, and guard the dict of buckets with a separate lock held only for the lookup and the insert. Decide the order the two are taken in, the map first and then a bucket, and never take them the other way round.
What goes wrong if each bucket is created lazily without a lock?
Two threads asking for a new key can both find it missing, both build a bucket, and each spend from its own. On this page the build forces that order with a clock that holds both threads inside the bucket constructor, and a bucket of capacity one lets two callers through. Hold the map lock for the lookup and the insert together.
How should a timed acquire wait for a token?
Compute one deadline from the clock when the call starts. On each attempt, take a token if there is one, otherwise work out how long until the next one is earned. If that is past the deadline, return False at once; if not, sleep that long outside every lock and try again, because another thread may take the token first. Inject the sleep as well as the clock, so a test can move time instead of waiting.
How do I test a thread-safe limiter without it being flaky?
Hold time still with a fake clock and assert something no interleaving can change. Release many threads together from a Barrier and assert that exactly the capacity got through. Hold one thread inside a lock with a clock that waits on an Event, and assert that a caller for another key still gets through. Give every wait and join a timeout, and assert that no thread is left alive.