Problem 41.4 · Concurrency-Aware Data StructuresMedium

Token Bucket Rate Limiter

What it teaches: Lazy refill on each request, guarded by a lock so concurrent requests can't overspend.

In plain words

Imagine a jar of tickets. Each request must take a ticket to get in. The jar is refilled by a fixed number of tickets every second, but it can never hold more than its size. Instead of a helper refilling it every second, we just work out how many tickets would have arrived since the last visit whenever someone shows up.

Return true if the request may go ahead, false otherwise. Example: capacity 2, refill 1: allow(0), allow(0), allow(0), allow(1) → true, true, false, true.

The problem

Design TokenBucket(capacity, refillPerSecond) with allow(timestamp) (seconds, non-decreasing): add refillPerSecond tokens for each elapsed second (never above capacity), then spend one token and return true, or return false if none are left. The bucket starts full. It must be safe to call from many threads.

Example 1

Input: capacity 2, refill 1: allow(0), allow(0), allow(0), allow(1)
Output: true, true, false, true

Constraints

1 ≤ capacity, refillPerSecond ≤ 10⁶

Pattern clues in the wording

→ Rate limiting
→ Burst up to a capacity

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

TokenBucket · starter

class TokenBucket {
    public TokenBucket(int capacity, int refillPerSecond) {}
    public synchronized boolean allow(int timestamp) { return false; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["TokenBucket","allow","allow","allow","allow","allow","allow","allow","allow"] args = [[2,1],[0],[0],[0],[1],[1],[5],[5],[5]]	[null,true,true,false,true,false,true,true,false]

From slow to fast

Approaches

1. Lazy refill under a lock · O(1)

Lazy refill under a lock

Time O(1) Space O(1)

tokens = min(capacity, tokens + (t − last) × rate); last = t; if tokens ≥ 1, spend one.

▶ Dry run: Refill on arrival, then spendcapacity 2, refill 1: allow(0), allow(0), allow(0), allow(1)

state(vars)

tokens: 2last: 0

returned(list)

empty

Step 1/4The bucket starts full with 2 tokens.

Approach 1

class TokenBucket {
    private final long capacity, rate;
    private long tokens, last;

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

    public synchronized boolean allow(int timestamp) {
        tokens = Math.min(capacity, tokens + (timestamp - last) * rate);
        last = timestamp;
        if (tokens == 0) return false;
        tokens--;
        return true;
    }
}

Verdict: The algorithm behind many API gateways.

Before you submit

Edge cases and common mistakes

Test these inputs

Long idle period (refill caps at capacity)
Many requests in the same second

Mistakes people make

Checking tokens and decrementing in separate unsynchronised steps (two threads spend the last token).

Interview

Follow-up questions

How do you rate-limit across many servers?

Connect the dots

Where this shows up in real systems

System Design · Problem 4.15 — Rate Limiter (LLD)A token bucket with lazy refill, made thread-safe.

Command Palette