Phase Three: The Limits

Phase Three: The Limits#

"Suppose this is behind a service taking a few thousand requests a second, across a thread pool. What happens?"

Six minutes left. Almost none of what follows involves writing code, and that is not a failure mode — it is what this phase is for. Phase three is usually a conversation, and the candidates who treat it as one do better than the candidates who start typing.

Reaching this phase at all is a positive signal. Plenty of sessions are still fighting phase one when the clock runs out.

0:34 - 0:37 — The race#

The honest answer to the interviewer's question is that the limiter breaks, and specifically where:

def allow(self, user_id):
    bucket = self._bucket_for(user_id)
    bucket._refill()
    if bucket.tokens >= 1:      # thread A reads 1.0
        bucket.tokens -= 1      # thread B also read 1.0, before A wrote back
        return True
    return False

Two threads can both evaluate tokens >= 1 before either decrements. Both are allowed through. One token was spent twice.

Worth naming the symmetry, because it is genuinely interesting rather than just correct: this is the same over-admission as the original bug, arriving by a completely different route. Phase one let extra requests through because the arithmetic was wrong. Phase three lets them through because the arithmetic is not atomic. Same observable failure, unrelated cause — which is exactly why the reproduction you wrote in phase one would not catch it.

The fix is a lock around refill-and-decrement. Say what it costs rather than presenting it as free:

"A lock around the refill and the decrement closes it. But that serialises every call to allow, and for a rate limiter sitting in front of everything on a hot path, that's a real cost rather than a theoretical one — I'd want to measure it under load before assuming it's acceptable. If contention turned out to be a problem, the next move is a lock per user rather than one global lock, since two users' buckets never touch each other."

That last sentence matters more than the lock. It shows you can see past the first correct answer to the one that actually scales, which is the question underneath the question.