# Token Bucket
Requests spend tokens, time refills them, and an empty bucket says no. A rate limiter in two rules.
**Time:** O(1)
**Space:** O(1)
**Difficulty:** MEDIUM
*[Interactive widget: token-bucket-visualizer (Token Bucket Visualizer) — open the HTML page]*
Canonical: https://scaleengineer.com/algorithms/token-bucket
---
A token bucket limits a rate with two rules instead of a clock\. Requests spend tokens from a bucket\. Time refills the bucket at a fixed rate, up to a fixed capacity\. A request that finds the bucket empty is turned away\. That is the whole mechanism, and the figure above runs it\.

The bucket in the figure holds six tokens and refills at two per second\. Three workloads are queued: a burst of nine requests in just over a second, a steady drip under the limit, and a flood over it\. Press play and watch the level\. Then read on to see why the burst gets through and the flood does not\.

Rate limits exist to protect the thing behind them\. A backend that can serve a thousand requests per second should not see two thousand, however eager the clients are\. The limiter stands in front and turns excess demand into a clear, cheap no, instead of a slow, expensive failure\.

## Two rules: spend and refill

Rule one: every request costs a token\. No token, no service\. Rule two: the bucket earns tokens at the refill rate, two per second in the figure, but never past capacity\. A full bucket earns nothing, so idle time past full is thrown away\.

Both rules run on arrival, not on a timer\. When a request arrives, the limiter tops up the bucket for the seconds since the last request, then checks the balance\. The state is two numbers: the level and the time of the last update\. A token bucket therefore costs `O(1)` time and `O(1)` memory per request, however many requests have passed\.

The whole limiter fits in one class\. Like the figure, this bucket starts full:

```python
class TokenBucket:
	def __init__(self, capacity, rate):
		self.capacity = capacity
		self.rate = rate
		self.tokens = capacity
		self.updated_at = 0.0

	def allow(self, now, cost=1):
		elapsed = now - self.updated_at
		self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
		self.updated_at = now
		if self.tokens >= cost:
			self.tokens -= cost
			return True
		return False
```

Starting full is a convention worth keeping\. Idle time before the first request is as good as idle time after it, so the first burst should be allowed\. A limiter that started empty would tax well\-behaved clients for showing up early\.

The cost need not be one token\. A heavy report query can cost five while a ping costs one, and the same bucket then budgets work instead of count\. The check stays the same: enough tokens or not\.

Two implementation details are easy to get wrong\. Use a monotonic clock, because a wall clock that jumps backward hands out free tokens\. And compare with a small epsilon, or store milli\-tokens as integers, because float dust can turn a token into 0\.999999 tokens\.

## A burst spends saved time

The figure opens on the burst workload: nine requests inside 1\.3 seconds, against a refill rate of two per second\. A strict two\-per\-second limiter would pass the first two requests and reject the rest\. The token bucket passes the first eight\.

Step through the burst and watch the level\. The bucket starts full at six\. Each request spends one token, and each 0\.15\-second gap drips back 0\.3\. Request eight arrives to 1\.1 tokens and spends down to 0\.1\. Request nine arrives to 0\.4, needs a whole token, and is dropped\. The eight that passed spent six saved tokens and two freshly dripped ones\.

That is what capacity buys\. The six tokens in a full bucket are three seconds of earlier quiet, saved and ready to spend in a fraction of a second\. A burst is never free\. It is paid for in advance\.

The figure below replays the burst\. Step backward and forward over request nine, the frame where the savings run out\. Then switch the workload to Steady\. One request every 0\.6 seconds stays under the refill rate, so the bucket never leaves full and the limiter goes invisible\. Well\-behaved traffic never meets the limiter\.

*[Interactive widget: token-bucket-visualizer — open the HTML page]*

## An empty bucket says no

Now switch to Flood: a request every 0\.25 seconds, four per second against a refill of two\. The first eleven requests get through on savings, and the bucket drains from full to empty in 2\.75 seconds\. From request twelve the limiter becomes a metronome: drop, allow, drop, allow\. Every second request passes, which is exactly two per second\. A flood cannot beat the rate\. It can only spend the savings once\.

Watch request thirteen\. It passes only because a token dripped in during the 0\.25 seconds after request twelve died\. That sawtooth, drain then drip, is the refill rate made visible\.

What happens to a dropped request is policy, not algorithm\. If you have met this limiter as a user, it was as `429 Too Many Requests`, often with a Retry\-After header so the client knows when to come back\. The header value is the deficit divided by the rate: half a token short at two per second means come back in 0\.25 seconds\. Systems that cannot lose work queue the request until a token arrives\. Either way, two invariants hold: the level never goes negative, and no request borrows from the future\.

If you are the client, honor the signal\. Retrying at once spends another request against an empty bucket and pushes your own retry further out\. Wait for the Retry\-After interval, or back off exponentially when there is no header\.

## Sizing the bucket

The two knobs answer two different questions\. The refill rate is the sustainable pace: the requests per second that may pass forever\. The capacity is the burst allowance: how far above that pace traffic may spike\. Rate is a speed\. Capacity is a savings account\.

Recovery time ties the knobs together\. A bucket drained to empty needs `capacity / rate` seconds to refill: three seconds for the figure's six tokens at two per second\. Pick the rate from what the backend can serve\. Pick the capacity from the burst you want to absorb\.

The common sizing mistake is a capacity of one\. With no savings, every request must wait for its own drip, and the limiter degenerates into a leaky bucket: no bursts at all\. Clients are bursty, so give the bucket room\.

Per\-key buckets scale the same way\. A million users need a million pairs of numbers, and idle keys can be evicted: a key that has been quiet for `capacity / rate` seconds is full again, so its stored state is worth nothing\.

The figure below plots the bucket level over twelve seconds for each workload\. Drag the sliders\. The rate tilts the slope of every climb, and the capacity raises the ceiling\. The flood trace shows the shape to remember: a straight\-line drain while savings last, then a sawtooth pinned to the refill rate\.

*[Interactive widget: token-bucket-tuning — open the HTML page]*

For the burst workload at two tokens per second, capacity buys bursts of:

| Capacity | Burst absorbed from full |
| --- | --- |
| `4` | `5` |
| `6` | `8` |
| `8` | `11` |
| `12` | `16` |

The table shows the refill at work\. At this gap, every two extra tokens of capacity absorb about three more requests, because tokens keep dripping in during the burst\. Capacity stretches a burst\. It never raises the pace\.

## Token bucket and its neighbors

The token bucket is one limiter in a family, and the family differs on one question: what happens to a burst?

- **Leaky bucket\. **Requests leave a queue at a fixed rate, so bursts are smoothed instead of absorbed\. A leaky bucket cannot bank idle time\. Choose it when downstream needs a perfectly even flow\.
- **Fixed window\. **A counter per window, such as 100 requests per minute, reset on the minute\. Simple, but weak at the boundary: 100 requests at 10:00:59 and 100 more at 10:01:00 both pass, and the backend sees 200 in two seconds\.
- **Sliding log\. **Store the timestamp of every request and count the last window\. Exact, but memory grows with the traffic being limited\.
- **Sliding window counter\. **Keep the current and previous window counts and weight them by where the window sits\. Still `O(1)` memory, but the count is an estimate, and it can refuse honest traffic right after a burst\.

The token bucket is the usual default because it keeps the two properties that matter, bounded memory and bursts allowed, for two numbers of state per key\.

## Where it earns its keep

The same two rules show up at every scale, from one endpoint to a continental network:

- **API gateways\. **Envoy's local rate\-limit filter is a token bucket, and Stripe has published its use of token\-bucket limiters\. Per\-user quotas are one bucket per API key: a map from key to level and timestamp\.
- **Network shaping\. **The Linux traffic\-control stack shapes packets with token buckets\. The same math that throttles API calls smooths packet flows\.
- **Your own endpoints\. **One bucket per user id turns a rule like five invites per minute into six lines of code\.

Keep the two rules straight and the practice problems below read as the same idea in new clothes: requests spend, time refills, empty says no\. [Number of Recent Calls](/dsa/problems/number-of-recent-calls) is the measurement half of limiting, counting the requests in a trailing window\. [Task Scheduler](/dsa/problems/task-scheduler) is a cooldown, one task per label per interval, which is a rate limit in a costume\.

## Code examples

### Token bucket rate limiter (Python)

```python
class TokenBucket:
    """Rate limiter: requests spend tokens, time refills them."""

    def __init__(self, capacity: int, rate: float) -> None:
        self.capacity = capacity
        self.rate = rate          # tokens per second
        self.tokens = capacity    # start full
        self.updated_at = 0.0

    def allow(self, now: float, cost: float = 1) -> bool:
        elapsed = now - self.updated_at
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.updated_at = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

```

### Token bucket rate limiter (JavaScript)

```javascript
class TokenBucket {
  /**
   * @param {number} capacity    max tokens (the burst allowance)
   * @param {number} refillRate  tokens added per second (the sustained rate)
   */
  constructor(capacity, refillRate) {
    if (capacity <= 0) throw new Error("capacity must be > 0");
    if (refillRate <= 0) throw new Error("refillRate must be > 0");

    this.capacity = capacity;
    this.refillRate = refillRate;
    this.tokens = capacity;              // start full
    this.lastRefill = performance.now(); // monotonic — never Date.now()
  }

  #refill() {
    const now = performance.now();
    const elapsedSec = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(this.capacity, this.tokens + elapsedSec * this.refillRate);
    this.lastRefill = now;
  }

  /** @returns {{allowed: boolean, remaining: number, retryAfterMs: number}} */
  tryConsume(n = 1) {
    if (n <= 0) throw new Error("n must be > 0");
    if (n > this.capacity) {
      return { allowed: false, remaining: this.tokens, retryAfterMs: Infinity };
    }

    this.#refill();

    if (this.tokens >= n) {
      this.tokens -= n;
      return { allowed: true, remaining: this.tokens, retryAfterMs: 0 };
    }

    const deficit = n - this.tokens;
    return {
      allowed: false,
      remaining: this.tokens,
      retryAfterMs: (deficit / this.refillRate) * 1000,
    };
  }

  /** Waits for capacity instead of rejecting. */
  async consume(n = 1) {
    for (;;) {
      const r = this.tryConsume(n);
      if (r.allowed) return;
      if (!Number.isFinite(r.retryAfterMs)) throw new Error("n exceeds capacity");
      await new Promise((res) => setTimeout(res, Math.ceil(r.retryAfterMs)));
    }
  }

  get available() {
    this.#refill();
    return this.tokens;
  }
}
```

### Token bucket rate limiter (Java)

```java
public class TokenBucket {
    private final double capacity;      // burst allowance
    private final double refillRate;    // sustained tokens per second

    private double tokens;
    private long lastRefillNanos;       // monotonic — never currentTimeMillis()

    public record Result(boolean allowed, double remaining, double retryAfterSeconds) {}

    public TokenBucket(double capacity, double refillRate) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        if (refillRate <= 0) throw new IllegalArgumentException("refillRate must be > 0");

        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = capacity;                  // start full
        this.lastRefillNanos = System.nanoTime();
    }

    private void refill() {
        long now = System.nanoTime();
        double elapsedSec = (now - lastRefillNanos) / 1_000_000_000.0;
        tokens = Math.min(capacity, tokens + elapsedSec * refillRate);
        lastRefillNanos = now;
    }

    public synchronized Result tryConsume(double n) {
        if (n <= 0) throw new IllegalArgumentException("n must be > 0");
        if (n > capacity) {
            return new Result(false, tokens, Double.POSITIVE_INFINITY);
        }

        refill();

        if (tokens >= n) {
            tokens -= n;
            return new Result(true, tokens, 0.0);
        }

        double deficit = n - tokens;
        return new Result(false, tokens, deficit / refillRate);
    }

    public Result tryConsume() { return tryConsume(1.0); }

    /** Blocks until n tokens are available. */
    public void consume(double n) throws InterruptedException {
        while (true) {
            Result r = tryConsume(n);
            if (r.allowed()) return;
            if (Double.isInfinite(r.retryAfterSeconds()))
                throw new IllegalArgumentException("n exceeds capacity");

            long millis = (long) Math.ceil(r.retryAfterSeconds() * 1000);
            Thread.sleep(Math.max(1, millis));
        }
    }

    public synchronized double available() {
        refill();
        return tokens;
    }
}
```

### Token bucket rate limiter (CPP)

```cpp
#include <algorithm>
#include <chrono>
#include <limits>
#include <mutex>
#include <stdexcept>

class TokenBucket {
public:
    struct Result {
        bool   allowed;
        double remaining;
        double retryAfterSeconds;
    };

    /// capacity = burst allowance, refillRate = sustained tokens per second.
    TokenBucket(double capacity, double refillRate)
        : capacity_(capacity), refillRate_(refillRate), tokens_(capacity),
          lastRefill_(Clock::now()) {
        if (capacity <= 0) throw std::invalid_argument("capacity must be > 0");
        if (refillRate <= 0) throw std::invalid_argument("refillRate must be > 0");
    }

    Result tryConsume(double n = 1.0) {
        if (n <= 0) throw std::invalid_argument("n must be > 0");
        if (n > capacity_) {
            return {false, tokens_, std::numeric_limits<double>::infinity()};
        }

        std::lock_guard<std::mutex> lock(mutex_);
        refill();

        if (tokens_ >= n) {
            tokens_ -= n;
            return {true, tokens_, 0.0};
        }

        double deficit = n - tokens_;
        return {false, tokens_, deficit / refillRate_};
    }

    /// Blocks until n tokens are available.
    void consume(double n = 1.0) {
        for (;;) {
            Result r = tryConsume(n);
            if (r.allowed) return;
            std::this_thread::sleep_for(
                std::chrono::duration<double>(r.retryAfterSeconds));
        }
    }

    double available() {
        std::lock_guard<std::mutex> lock(mutex_);
        refill();
        return tokens_;
    }

private:
    using Clock = std::chrono::steady_clock;   // monotonic — never system_clock

    void refill() {
        auto now = Clock::now();
        double elapsedSec = std::chrono::duration<double>(now - lastRefill_).count();
        tokens_ = std::min(capacity_, tokens_ + elapsedSec * refillRate_);
        lastRefill_ = now;
    }

    double capacity_;
    double refillRate_;
    double tokens_;
    Clock::time_point lastRefill_;
    std::mutex mutex_;
};
```

### Token bucket rate limiter (C)

```c
#define _POSIX_C_SOURCE 199309L

#include <math.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
    double capacity;      /* burst allowance             */
    double refill_rate;   /* sustained tokens per second */
    double tokens;
    double last_refill;   /* seconds, monotonic          */
} TokenBucket;

typedef struct {
    int    allowed;
    double remaining;
    double retry_after_seconds;   /* INFINITY if n > capacity */
} TBResult;

static double monotonic_now(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);   /* never CLOCK_REALTIME */
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9;
}

/* Returns NULL on bad arguments or allocation failure. */
TokenBucket *tb_create(double capacity, double refill_rate) {
    if (capacity <= 0.0 || refill_rate <= 0.0) return NULL;

    TokenBucket *tb = malloc(sizeof *tb);
    if (!tb) return NULL;

    tb->capacity = capacity;
    tb->refill_rate = refill_rate;
    tb->tokens = capacity;                 /* start full */
    tb->last_refill = monotonic_now();
    return tb;
}

void tb_free(TokenBucket *tb) { free(tb); }

static void tb_refill(TokenBucket *tb) {
    double now = monotonic_now();
    double elapsed = now - tb->last_refill;

    tb->tokens += elapsed * tb->refill_rate;
    if (tb->tokens > tb->capacity) tb->tokens = tb->capacity;
    tb->last_refill = now;
}

TBResult tb_try_consume(TokenBucket *tb, double n) {
    TBResult r;

    if (n > tb->capacity) {
        r.allowed = 0;
        r.remaining = tb->tokens;
        r.retry_after_seconds = INFINITY;   /* can never be satisfied */
        return r;
    }

    tb_refill(tb);

    if (tb->tokens >= n) {
        tb->tokens -= n;
        r.allowed = 1;
        r.remaining = tb->tokens;
        r.retry_after_seconds = 0.0;
    } else {
        r.allowed = 0;
        r.remaining = tb->tokens;
        r.retry_after_seconds = (n - tb->tokens) / tb->refill_rate;
    }
    return r;
}

double tb_available(TokenBucket *tb) {
    tb_refill(tb);
    return tb->tokens;
}
```

### Token bucket rate limiter (CSharp)

```csharp
using System;
using System.Diagnostics;
using System.Threading;
using System.Threading.Tasks;

public class TokenBucket
{
    public readonly record struct Result(
        bool Allowed, double Remaining, double RetryAfterSeconds);

    private readonly double capacity;      // burst allowance
    private readonly double refillRate;    // sustained tokens per second
    private readonly object gate = new();

    private double tokens;
    private long lastRefillTicks;          // monotonic — never DateTime.Now

    public TokenBucket(double capacity, double refillRate)
    {
        if (capacity <= 0) throw new ArgumentOutOfRangeException(nameof(capacity));
        if (refillRate <= 0) throw new ArgumentOutOfRangeException(nameof(refillRate));

        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = capacity;                       // start full
        this.lastRefillTicks = Stopwatch.GetTimestamp();
    }

    private void Refill()
    {
        long now = Stopwatch.GetTimestamp();
        double elapsedSec = (now - lastRefillTicks) / (double)Stopwatch.Frequency;
        tokens = Math.Min(capacity, tokens + elapsedSec * refillRate);
        lastRefillTicks = now;
    }

    public Result TryConsume(double n = 1.0)
    {
        if (n <= 0) throw new ArgumentOutOfRangeException(nameof(n));
        if (n > capacity) return new Result(false, tokens, double.PositiveInfinity);

        lock (gate)
        {
            Refill();

            if (tokens >= n)
            {
                tokens -= n;
                return new Result(true, tokens, 0.0);
            }

            double deficit = n - tokens;
            return new Result(false, tokens, deficit / refillRate);
        }
    }

    /// <summary>Waits for capacity instead of rejecting.</summary>
    public async Task ConsumeAsync(double n = 1.0, CancellationToken ct = default)
    {
        while (true)
        {
            var r = TryConsume(n);
            if (r.Allowed) return;
            if (double.IsInfinity(r.RetryAfterSeconds))
                throw new ArgumentOutOfRangeException(nameof(n), "n exceeds capacity");

            await Task.Delay(
                TimeSpan.FromSeconds(Math.Max(0.001, r.RetryAfterSeconds)), ct);
        }
    }

    public double Available
    {
        get { lock (gate) { Refill(); return tokens; } }
    }
}
```