Token Bucket Rate Limiter

Implement a token bucket rate limiter for one client.

TokenBucket(capacity, refillPerSecond): the bucket holds at most capacity tokens and gains refillPerSecond tokens per second (continuously, fractions allowed). It starts full at time 0.
allow(nowMs): called with a non-decreasing timestamp in milliseconds. Refill based on elapsed time, then, if at least one whole token is available, consume one and return true; otherwise return false.

Time is passed in rather than read from a clock so the limiter is deterministic and testable — a common interview follow-up.

Example 1

Input: ["TokenBucket","allow","allow","allow","allow","allow"]
[[2,1],[0],[0],[0],[500],[1000]]
Output: [null,true,true,false,false,true]
Explanation: Two burst requests pass, the third fails; after 1 s one token has refilled.

Solution and explanation

Show the solution

Time O(1) per call · Space O(1)

Refill lazily on each call instead of running a timer: compute elapsed time since the last call, add elapsed × rate tokens, cap at capacity, then try to spend one token. This is O(1) per call and is how most API gateways implement token buckets (often in Redis with a Lua script so the read-modify-write is atomic).

Reference solution

class TokenBucket {
  constructor(capacity, refillPerSecond) {
    this.capacity = capacity;
    this.rate = refillPerSecond;
    this.tokens = capacity;
    this.last = 0;
  }

  allow(nowMs) {
    this.tokens = Math.min(this.capacity, this.tokens + ((nowMs - this.last) / 1000) * this.rate);
    this.last = nowMs;
    if (this.tokens < 1) return false;
    this.tokens -= 1;
    return true;
  }
}

class TokenBucket {
  private tokens: number;
  private last = 0;

  constructor(private readonly capacity: number, private readonly refillPerSecond: number) {
    this.tokens = capacity;
  }

  allow(nowMs: number): boolean {
    const elapsed = (nowMs - this.last) / 1000;
    this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.refillPerSecond);
    this.last = nowMs;
    if (this.tokens < 1) return false;
    this.tokens -= 1;
    return true;
  }
}

class TokenBucket:
    def __init__(self, capacity: int, refill_per_second: int):
        self.capacity = capacity
        self.rate = refill_per_second
        self.tokens = float(capacity)
        self.last = 0

    def allow(self, now_ms: int) -> bool:
        self.tokens = min(self.capacity, self.tokens + (now_ms - self.last) / 1000 * self.rate)
        self.last = now_ms
        if self.tokens < 1:
            return False
        self.tokens -= 1
        return True

<?php

class TokenBucket
{
    private float $tokens;
    private int $last = 0;

    public function __construct(private int $capacity, private int $refillPerSecond)
    {
        $this->tokens = $capacity;
    }

    public function allow(int $nowMs): bool
    {
        $elapsed = ($nowMs - $this->last) / 1000;
        $this->tokens = min($this->capacity, $this->tokens + $elapsed * $this->refillPerSecond);
        $this->last = $nowMs;
        if ($this->tokens < 1) {
            return false;
        }
        $this->tokens -= 1;
        return true;
    }
}

class TokenBucket {
    private final int capacity;
    private final int refillPerSecond;
    private double tokens;
    private long last = 0;

    public TokenBucket(int capacity, int refillPerSecond) {
        this.capacity = capacity;
        this.refillPerSecond = refillPerSecond;
        this.tokens = capacity;
    }

    public boolean allow(long nowMs) {
        tokens = Math.min(capacity, tokens + (nowMs - last) / 1000.0 * refillPerSecond);
        last = nowMs;
        if (tokens < 1) return false;
        tokens -= 1;
        return true;
    }
}

Common mistakes

Letting tokens exceed capacity after a long idle period.
Using wall-clock time inside the class — hard to test and non-deterministic.
Distributed version: non-atomic read-then-write races between instances.

Follow-up questions

Rate-limit per API key (map of buckets + eviction).
Return Retry-After: how long until the next token?
Compare with fixed window, sliding window and GCRA.

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

More Design & Data Structures problems