🎓 A1Learner
🔍
0 of 42 lessons completed

The Token Bucket

A token bucket is a store of tokens that fills steadily and pays one token per request. This lesson gives the high-level design for the rate limiter check.

Spending tokens on a burst

The bucket starts full and each request spends one token. The burst drains the bucket, and the later requests find it empty.

tokens = 5

for i in range(1, 8):
    if tokens > 0:
        tokens -= 1
        print("request", i, "accepted, tokens left", tokens)
    else:
        print("request", i, "rejected, tokens left", tokens)

The bucket fills at a steady rate

Time is scripted as data, and the bucket earns one token per second up to its cap. The printout shows the balance growing between arrivals.

tokens = 0
last_time = 0
arrivals = [(0, "request 1"), (1, "request 2"), (2, "request 3"), (5, "request 4")]

for time, name in arrivals:
    tokens = min(5, tokens + (time - last_time))
    last_time = time
    if tokens > 0:
        tokens -= 1
        print(name, "at second", time, "accepted, tokens left", tokens)
    else:
        print(name, "at second", time, "rejected, tokens left", tokens)

Burst first, then the refill pace

A scripted burst hits an emptying bucket, then more requests arrive close together. After the burst, only the steady refill pace gets through.

tokens = 5
last = 0
arrivals = [0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 5]

for i, t in enumerate(arrivals, 1):
    tokens = min(5, tokens + (t - last))
    last = t
    if tokens > 0:
        tokens -= 1
        print("request", i, "at second", t, "accepted")
    else:
        print("request", i, "at second", t, "rejected")

Example

capacity = 5
tokens = 5
last = 0
arrivals = [0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 10]
accepted = 0
rejected = 0

for t in arrivals:
    tokens = min(capacity, tokens + (t - last))
    last = t
    if tokens > 0:
        tokens -= 1
        accepted += 1
        print("second", t, "accepted, tokens left", tokens)
    else:
        rejected += 1
        print("second", t, "rejected, tokens left", tokens)

print("accepted", accepted)
print("rejected", rejected)

Key points

  • Token bucket: a store of tokens that fills at a steady rate and pays one token for each request.
  • Refill rate: this design adds tokens at the worked limit rate of 100 tokens per minute.
  • In 30 seconds the bucket earns 50 tokens at that refill rate.
  • Full bucket: a bucket holding 100 tokens lets a burst of 100 requests pass at once.
  • Empty bucket: a request that finds no token is rejected until a new token arrives.

In this example, a scripted burst spends the full bucket and the next requests are rejected until refills arrive. Later requests pass at the refill pace, and the totals show the burst-then-starve shape in full.

Note

the bucket allows short bursts, then holds the long-run pace to the refill rate.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

A bucket is empty and a request arrives before any refill. What happens to the request?