Leaky Bucket

Requests pour into a bucket and wait their turn in a queue. A hole near the bottom lets them out to the server at a fixed rate, however bursty the traffic is, and a request that finds the bucket full is dropped. Below, an attacker joins two ordinary users: watch who is dropped, and who waits, when they share one queue and when each has their own.

User A289 req/sUser B289 req/sAttacker1,736 req/sAPI serversteady streamleaks r = 1,157/sShared queuerequests waiting

Each dot stands for 579 real requests. Time is not scaled. At 1x speed the first drop comes about 5.0 s after the first request reaches the bucket, which is the fill time the formula below predicts.

Sizing the shared queue
x average

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

seconds

The longest a request may sit in a full queue before it is served.

  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. Leak rate r

    r = peak = 1,157 req/s
    The steady rate the servers take requests off the queue.

  4. 4. Queue size b

    b = r x longest wait = 1,157 x 5 s = 5,788 requests
    The back of a full queue is b / r = 5 s from the front.

  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. Requests arrive faster than they leak, so the queue fills, in b / (live - r) = 5,788 / 1,157 = 5.0 s. After that, about 50% of requests are dropped (1 - r / live), and every request that does get in waits about 5 s. In a shared queue, 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 queue behaves identically and only the number each dot stands for changes. What changes the behaviour is traffic relative to r: the peak factor, the longest wait, 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. Queue size and outflow rate are the two leaky 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. Sizing the queue from the longest acceptable wait follows from how a queue works: the last request in a full one is b / r seconds from the front.

Token bucket or leaky bucket

Same two numbers

Both are set by a rate and a size. In a token bucket the size is how big a burst may pass at once; in a leaky bucket it is how many requests may wait in line.

Different behaviour

A token bucket lets a burst straight through to the server. A leaky bucket never does: every request waits its turn, and the server sees a perfectly steady stream. Use a leaky bucket when the thing behind it needs a constant rate, and a token bucket when users should not wait.

Limits of per-user queues

Waiting is the price

Smoothing traffic means holding requests back. Even an honest user who sends three requests at once waits for the second and third. Press Attacker bursts 10 in per-user mode and watch them leave one by one.

Old requests can crowd out new ones

A burst can fill the queue with requests that are already stale by the time they are served, while newer, more useful ones are dropped at the door. The book lists this as the leaky bucket's main drawback.

Use both limits together

Per-user queues keep one client from delaying the others; a global limit protects total capacity. Turn on Attacker rotates accounts: every request finds an empty queue, and only a global limit would notice.

Memory cost

A queue holds the requests themselves, not just a count, so a queue per user costs more memory than a token bucket per user. Keep queues short, which also keeps waits short.

How NGINX and Shopify use leaky buckets

The name covers two slightly different designs, and these two examples show both.

NGINX: a leaky bucket as a queue

NGINX's request limiter documentation says: "The limitation is done using the 'leaky bucket' method." In limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s; and limit_req zone=one burst=5;, the rate is the leak rate r, the burst is the queue size b, and the key is the client's IP address, so it is a queue per client. Extra requests are delayed while they wait, and refused once the queue is full, with a 503 by default (limit_req_status changes it). Adding nodelay serves queued requests at once instead of spacing them out, which in effect makes it behave like a token bucket. The documentation's own example also stacks a per-IP limit and a per-server limit, the layered setup described above.

Shopify: a leaky bucket as a meter

Shopify's documentation says: "Most Shopify rate limits are enforced with a leaky bucket algorithm." Each app has its own bucket; each request tosses marbles into it; it leaks continuously at a restore rate; and when it is full the request gets a throttle error. Nothing is held in a queue: a request either fits or is refused at once. That "meter" form behaves like a token bucket, which is why the same name can describe both. Bucket sizes and restore rates vary by API and by plan, so the current figures are on Shopify's page.
Sources and credibility

Both are the projects' own documentation (primary sources). Quoted sentences are short attributed quotations; the configuration lines are NGINX's own example. Limits change, so check the pages for current values.