Token Bucket Rate Limiter Class

Problem

Implement TokenBucket(capacity, refill_rate, clock=time.monotonic), a rate limiter shared by many threads:

• The bucket holds at most capacity tokens and starts full.
• Tokens are added continuously at refill_rate tokens per second, never exceeding capacity.
• try_acquire(n=1) -> bool: if at least n tokens are available, remove them and return True; otherwise return False immediately without removing anything.
• acquire(n=1, timeout=None) -> bool: like try_acquire, but if tokens are not available, sleep until they will be (or until timeout elapses) and then take them. Must not busy-wait.

Guarantees: under any interleaving of threads, the number of successful acquisitions over any window never exceeds capacity + refill_rate × window (no over-admission), and no thread that is waiting is woken more often than needed. The clock must be injectable so tests can control time deterministically.

• capacity >= 1, refill_rate > 0, n <= capacity (larger requests are rejected outright).
• Refill must be lazy (computed on access), not driven by a background thread.

Examples

• TokenBucket(capacity=5, refill_rate=1) at t=0: five try_acquire() calls succeed, the sixth fails. At t=2.0, two more succeed and the next fails (2 tokens refilled, both spent).
• Same bucket, idle from t=2 to t=100 → at t=100 only 5 tokens are available, not 98: the bucket caps the burst.
• 8 threads each hammer try_acquire() 1,000 times against a bucket with capacity 100 and a frozen clock → exactly 100 succeed in total, never 101.
• acquire(3) on an empty bucket with refill_rate=10 → returns True after ~0.3 s, having slept, not spun.

Hints

1. You do not need a timer to add tokens. Whenever someone touches the bucket, compute how much time has passed since the last touch and add elapsed × rate tokens, capped at capacity.
2. The refill-then-check-then-subtract sequence is a read-modify-write on shared state. Two threads doing it without a lock can both see "1 token left" and both take it.
3. For the blocking version, compute exactly how long until n tokens will exist, and sleep for that long outside the lock so you do not block other callers.