Token Bucket

A refiller drips tokens into a bucket at a fixed rate, and every request has to take one token to reach the server. A full bucket lets a short burst straight through, which is what token bucket is known for. An empty one answers with a 429. Below, an attacker joins two ordinary users: watch who gets hurt when they share one bucket, and when each has their own.

User A289 req/sUser B289 req/sAttacker1,736 req/sAPI serverprotectedRefillerr = 1,157/sShared buckettokens right now

Each dot stands for 579 real requests, and each token for 579 real tokens. Time is not scaled. At 1x speed the first 429 comes 5.0 s after the first request reaches the gate, which is the drain time the formula below predicts.

Sizing the shared bucket
x average

Busiest hour vs the daily average. The book's estimate uses 2x.

seconds

Seconds of peak traffic a full bucket can absorb.

  1. 1. Average requests per second

    DAU x requests per user per day / 86,400
    = 1,000,000 x 50 / 86,400 = 579 req/s

  2. 2. Peak requests per second

    average x peak factor = 579 x 2 = 1,157 req/s

  3. 3. Refill rate r

    r = peak = 1,157 tokens/s
    The steady rate you agree to serve, forever.

  4. 4. Bucket size b

    b = r x burst window = 1,157 x 5 s = 5,788 tokens
    The biggest burst you let straight through.

  5. 5. What is arriving right now

    average x (1 + attack / 2) = 579 x (1 + 6 / 2) = 2,315 req/s, which is 2.00x r
  6. Traffic beats the refill rate, so the bucket drains. A full one lasts b / (live - r) = 5,788 / 1,157 = 5.0 s. After that, about 50% of requests get a 429 (1 - r / live), and in a shared bucket that includes the innocent users.
Why changing only DAU does not change the animation

Doubling DAU doubles the traffic, and because r and b are sized from that same traffic, it doubles them too. Every ratio stays the same, so the bucket behaves identically and only the number each dot stands for changes. What changes the behaviour is traffic relative to r: the peak factor, the burst window, and the attack.

Where these formulas come from

Steps 1 and 2 are the estimation method from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1, including its 2x peak. Bucket size and refill rate are the two token bucket parameters from its rate limiter chapter. The book does not give a single formula joining them; steps 3 to 5 are that join, written here, and the drain time and drop rate follow directly from them.

Limits of per-user buckets

Use both limits together

A per-user limit keeps one client from hurting the others. A global limit protects the servers' total capacity. Turn on Attacker rotates accounts in per-user mode: every request passes its own check, and only a global limit on top would notice the flood.

Memory cost

Millions of users means millions of buckets, each just a token count and a last-refill time. The book keeps these counters in Redis with an expiry, so a user who goes quiet stops costing anything.

It needs to know the user

A login endpoint has no user yet, so it usually limits by IP address instead. That is weaker: one attacker can hold many IPs, and many real users can share one behind an office or mobile network.

Short bursts are allowed

Token bucket's trademark is letting a short burst straight through, up to b, while still holding the long-run rate to r. Press Attacker bursts 10 against a full bucket and they all get through; press it again straight away and they don't.

How AWS uses token buckets

AWS uses token buckets in several places and documents the parameters, which makes them good examples to study.

API Gateway throttling

AWS states that API Gateway "throttles requests to your API using the token bucket algorithm, where a token counts for a request". You set two numbers: a throttling rate, the tokens added per second (r), and a throttling burst, the bucket's capacity (b). These are exactly the two knobs on this page.

EC2 API throttling

EC2 throttles its own API with token buckets, one per category of action. For example, DescribeHosts has a bucket of 100 tokens refilling at 20 per second. Call it 50 times a second and a full bucket lasts 100 / (50 - 20) = 3.3 s, after which 60% of calls are throttled. Actions such as RunInstances also draw from a second, separate bucket that drains by the number of instances affected: two limits layered, just like per-user plus global.

EBS gp2 burst credits

The same idea applied to disk speed. A gp2 volume earns 3 I/O credits per GiB per second while idle, holds up to 5.4 million, and spends them to burst to 3,000 IOPS. AWS gives the burst duration as credit balance / (burst IOPS - baseline IOPS), which is this page's drain formula, b / (live - r). A 100 GiB volume (baseline 300 IOPS) bursts for 5,400,000 / 2,700 = 2,000 s, about 33 minutes.
Sources and credibility

All three are AWS's own documentation (primary sources). The quoted sentences are short attributed quotations; the worked examples are calculated here from AWS's published figures. AWS revises limits, so check the pages for current values.