# TokenBucket

A minimal, thread-safe **token bucket rate limiter** for Python.

A token bucket refills continuously at a fixed `rate` (tokens per second) up to a
maximum `capacity`. Every operation you want to rate-limit consumes one or more
tokens. If tokens are available, the operation proceeds immediately; if not, you
either get an instant `False` (`try_acquire`) or block until enough tokens have
accrued (`acquire`).

This gives you two knobs with intuitive meanings:

| Parameter   | Meaning                                                        |
| ----------- | -------------------------------------------------------------- |
| `rate`      | Sustained throughput limit: tokens (operations) per second.    |
| `capacity`  | Maximum burst size: how many tokens can be banked at once.     |

The bucket starts **full**, so a fresh bucket permits an immediate burst of up to
`capacity` operations, then settles into the sustained `rate`.

```python
from tokenbucket import TokenBucket

bucket = TokenBucket(rate=2, capacity=10)  # burst of 10, then 2/sec sustained

for i in range(5):
    bucket.acquire()  # blocks until a token is free
    print(f"request {i} sent")
```

There is no background thread: tokens are computed lazily from elapsed clock
time on each call, so a bucket costs nothing while idle.

---

## API Reference

### Class

```python
TokenBucket(rate, capacity=None, clock=time.monotonic)
```

Creates a new token bucket, initially full.

**Parameters**

| Name       | Type                | Default           | Description                                                                     |
| ---------- | ------------------- | ----------------- | ------------------------------------------------------------------------------- |
| `rate`     | `float`             | — (required)      | Refill rate in tokens per second. Must be `> 0`.                                 |
| `capacity` | `float` \| `None`   | `None` → `rate`   | Maximum number of tokens the bucket can hold (burst size).                       |
| `clock`    | `() -> float`       | `time.monotonic`  | Time source used for refilling and timeout math. Injectable for testing.         |

**Raises**

- `ValueError` — if `rate <= 0` (`"rate must be positive"`).

**Public attributes** (read-only by convention; do not mutate after construction)

- `rate` (`float`) — refill rate, tokens per second.
- `capacity` (`float`) — bucket capacity. Defaults to one second's worth of
  tokens (`rate`), e.g. `TokenBucket(10)` means capacity 10.

Everything prefixed with `_` (including `_tokens`, `_refill`, `_lock`) is
internal and subject to change.

---

### `try_acquire(n=1)`

Non-blocking attempt to take `n` tokens.

```python
try_acquire(n=1) -> bool
```

- Returns `True` and deducts `n` tokens if at least `n` are available.
- Returns `False` immediately (deducting nothing) otherwise.

**Parameters**

- `n` (`float`, default `1`) — number of tokens to take. Use fractional values
  to weight operations (e.g. `0.5` for cheap requests, `4` for expensive ones).

**Raises**

- `ValueError` — if `n > capacity` (`"request exceeds capacity"`). Such a
  request could never succeed, so it is treated as a programming error.

**Thread safety:** safe to call concurrently from any number of threads.

---

### `acquire(n=1, timeout=None)`

Blocking attempt to take `n` tokens.

```python
acquire(n=1, timeout=None) -> bool
```

- If `n` tokens are available, deducts them and returns `True` immediately.
- Otherwise sleeps until enough tokens have accrued, retrying internally, and
  returns `True` once it succeeds.
- If `timeout` (seconds) elapses first, gives up and returns `False` without
  deducting anything.

**Parameters**

- `n` (`float`, default `1`) — number of tokens to take.
- `timeout` (`float` \| `None`, default `None`) — maximum seconds to block.
  `None` (the default) waits forever. `timeout=0` degenerates into a
  `try_acquire` call.

**Important:** unlike `try_acquire`, this method **does not validate `n` against
`capacity`**. With `timeout=None` and `n > capacity` it will block forever —
see [Caveats](#caveats-and-edge-cases). Passing `timeout=0` raises no error and
simply returns `False` if tokens are unavailable.

**Thread safety:** safe to call concurrently. The internal lock is only held
for brief bookkeeping; sleeping happens *outside* the lock, so one blocked
caller does not stall other threads.

---

## Examples

### Rate-limiting API calls (basic)

Cap a client at 3 requests/second, allowing a small burst of 5 on startup:

```python
import time
from tokenbucket import TokenBucket

bucket = TokenBucket(rate=3, capacity=5)

def call_api():
    bucket.acquire()          # wait for permission to proceed
    return "calling api..."   # your request goes here

start = time.monotonic()
for i in range(6):
    call_api()
    print(f"call {i} at t={time.monotonic() - start:.2f}s")
```

Output (approximately — the first 5 calls burst through instantly, then the
pace locks to 3/sec):

```
call 0 at t=0.00s
call 1 at t=0.00s
call 2 at t=0.00s
call 3 at t=0.00s
call 4 at t=0.00s
call 5 at t=0.33s
```

### Non-blocking checks with `try_acquire`

Skip the work instead of waiting when you're out of budget:

```python
bucket = TokenBucket(rate=10, capacity=20)

def maybe_handle(request):
    if not bucket.try_acquire():
        return "busy, try again later"   # drop / defer / return 429
    return handle(request)
```

### Bounded waiting with `acquire(timeout=...)`

```python
bucket = TokenBucket(rate=1, capacity=1)
bucket.try_acquire(1)  # drain the bucket

if bucket.acquire(timeout=0.25):     # would need ~1s to refill
    print("got a token in time")
else:
    print("timed out")               # <- this runs
```

`acquire(n, timeout=0)` is equivalent to `try_acquire(n)` (minus the capacity
validation).

### Weighted operations with fractional/multi tokens

```python
bucket = TokenBucket(rate=100, capacity=200)

bucket.try_acquire(0.5)   # cheap lookup costs half a token
bucket.acquire(10)        # heavy report costs ten tokens
```

### Sharing one bucket across threads

All methods are thread-safe, so one bucket can police a whole worker pool:

```python
import threading
from tokenbucket import TokenBucket

bucket = TokenBucket(rate=5, capacity=10)   # 10 to start, then 5/sec

def worker(worker_id):
    for _ in range(10):
        bucket.acquire()
        do_work(worker_id)

threads = [threading.Thread(target=worker, args=(i,)) for i in range(4)]
for t in threads:
    t.start()
for t in threads:
    t.join()
# 40 total acquires: the initial 10 are instant, the rest trickle out at 5/sec.
```

### Deterministic testing with a fake clock

Inject a clock to test rate-limit logic without real sleeps:

```python
class FakeClock:
    def __init__(self):
        self.t = 1000.0
    def __call__(self):
        return self.t
    def advance(self, dt):
        self.t += dt

clock = FakeClock()
bucket = TokenBucket(rate=10, capacity=10, clock=clock)

assert bucket.try_acquire(10) is True    # drains the full bucket
assert bucket.try_acquire() is False     # empty
clock.advance(0.5)                       # simulate half a second passing
assert bucket.try_acquire(5) is True     # 5 tokens refilled
```

Note that a fake clock only affects *token accounting*; `acquire()` still calls
the real `time.sleep` while waiting, so prefer `try_acquire` plus explicit
`clock.advance(...)` in unit tests.

---

## How it works

- **Lazy refill.** On every call, elapsed time since the last refill is
  converted into tokens at `elapsed * rate`, capped at `capacity`. Unused
  headroom above `capacity` is lost — the bucket never exceeds its capacity, so
  idle time beyond one full refill grants no extra credit.
- **Clock.** The default `time.monotonic` is immune to system clock adjustments.
  Elapsed time is clamped at `0`, so a custom clock that runs backwards simply
  adds no tokens rather than corrupting state.
- **Concurrency model.** A `threading.Lock` guards all token bookkeeping.
  `acquire` computes how long to wait, releases the lock, sleeps, then re-checks
  in a loop — other threads proceed freely in the meantime.

## Caveats and edge cases

1. **`acquire(n > capacity, timeout=None)` blocks forever.** `try_acquire`
   rejects impossible requests with `ValueError`, but `acquire` has no such
   check; it will sleep and retry indefinitely because the bucket can never
   hold `n` tokens. If `n` can exceed `capacity`, validate it yourself or
   always pass a `timeout`.

2. **`n` must be positive.** Neither method validates the lower bound.
   `try_acquire(0)` trivially returns `True`, and negative values are worse:
   `try_acquire(-3)` returns `True` *and inflates the token count* by 3. Treat
   `n <= 0` as a caller bug.

3. **No fairness guarantee.** Blocked `acquire` callers sleep independently and
   race for the lock when they wake; there is no queue. Under heavy contention
   a thread can be repeatedly beaten to the tokens and starve. If you need
   FIFO ordering, add a `queue.Queue` or semaphore in front of the bucket.

4. **Timing is approximate.** Actual throughput is slightly *below* `rate` and
   `acquire` may block marginally *past* its `timeout`, because `time.sleep`
   can overshoot (OS scheduling granularity). Don't use this module for
   precision timing, and don't rely on `acquire` succeeding strictly within
   `timeout`.

5. **Wakeup races.** If several threads wait at once, each sleeps exactly as
   long as *it* needs, but on waking any thread may find its tokens already
   consumed by a peer; it recomputes and sleeps again. This is correct but
   means wall-clock wait times can stack under contention.

6. **Only `rate` is validated.** A `capacity` of `0` or less is accepted and
   produces a bucket where every `try_acquire(n >= 1)` raises and every
   `acquire(n >= 1, ...)` fails or hangs. Pass a sensible positive capacity.

7. **Bursts start immediately.** The bucket is full at construction and its
   clock reference starts then too, so even `try_acquire`-only users see time
   pass: build the bucket when rate limiting should begin, not long before.

8. **Fake clocks and `acquire`.** `acquire` computes its deadline and wait
   times from the injected clock but sleeps in real time. With a fake clock
   that never advances, `acquire` with insufficient tokens sleeps the real
   computed wait and still fails. For tests, drive `try_acquire` and
   `clock.advance` explicitly (see the example above).
