We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningIntermediate · Security Architecture
A rate limiting algorithm where tokens are added to a bucket at a fixed rate. Each request consumes a token; requests are rejected when the bucket is empty. Allows short bursts.
In short
Token bucket is a rate limiting algorithm that fills a fixed-capacity bucket with tokens at a steady rate, and lets each incoming request proceed only if it can remove a token; when the bucket is empty, requests are rejected or queued. Because unused tokens accumulate up to the bucket's capacity, it permits short bursts of traffic while still capping the long-run average rate.
In short
Token bucket is a rate limiting algorithm that fills a fixed-capacity bucket with tokens at a steady rate, and lets each incoming request proceed only if it can remove a token; when the bucket is empty, requests are rejected or queued. Because unused tokens accumulate up to the bucket's capacity, it permits short bursts of traffic while still capping the long-run average rate.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers Token Bucket across a run of lessons, not one page. These 4 alone are about 125 minutes of step-by-step reading, 1 of them with code you run in the browser, all with a quiz.
A bucket of tokens that refills at a steady rate, the most popular rate limiting algorithm in production.
Protect your API from abuse and overload by controlling how many requests each consumer can make.
Protect services from abuse and overload, token bucket, sliding window, and distributed rate limiting.
Design a distributed rate limiting system - token bucket, sliding window, and protecting services at massive scale.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Token Bucket Algorithmpay once,
yours for life
A token bucket controls how fast a client, an API caller, or a network flow is allowed to do work. You picture a bucket that holds at most B tokens. Tokens are dropped into the bucket at a constant refill rate of R tokens per second. Every request must take one token (or a number of tokens proportional to its cost) before it runs.
If a token is available, the request proceeds and the token is removed. If the bucket is empty, the request is either rejected immediately, retried later, or held in a queue, depending on how the system is configured.
The two numbers fully define the behavior. The refill rate R sets the sustained average throughput. The capacity B sets how large a burst you tolerate after an idle period. A bucket with R = 100 tokens/second and B = 100 lets a client send up to 100 requests in one instant if it has been quiet, then settle to 100 per second after that.
Real implementations almost never run a background timer that adds tokens. Instead they store two values per client: the current token count and the timestamp of the last update. When a request arrives, the code computes how much time has passed, multiplies by the refill rate, adds that many tokens up to the capacity ceiling, and only then checks whether a token can be spent. This lazy refill makes each check O(1) and avoids one timer per client.
Concretely the math is: tokens = min(capacity, tokens + (now - last_refill) * rate); last_refill = now. If tokens is at least the request cost, subtract the cost and allow it; otherwise reject. Storing just a counter and a timestamp means the whole limiter for one key fits in a few bytes, which is why it scales to millions of keys in Redis.
In a distributed system the state lives in a shared store so all servers see the same count. Redis is the common choice, with the read-modify-write done atomically inside a Lua script so two concurrent requests cannot both spend the last token.
Reach for token bucket when real traffic is bursty but you still want a hard average cap. A user who opens an app and fires ten requests in one second is normal; token bucket absorbs that burst from saved-up tokens and then throttles them to the steady rate. This is why it is the default for public APIs.
Compare it to two neighbors. Leaky bucket smooths output to a perfectly constant rate and never allows bursts, which is good for traffic shaping but punishes legitimate spikes. A fixed window counter is simpler but suffers a boundary problem where a client can send a full window's worth at the end of one window and the start of the next, briefly doubling the intended rate. Token bucket avoids both issues.
The trade-offs to watch: in a distributed setup every request needs a round trip to the shared store, so the limiter can become a hotspot and adds latency. Clock skew between nodes can corrupt the time-based refill. And tuning matters: a large capacity allows bigger bursts that may still overwhelm a fragile backend, so the burst size should match what your downstream can actually survive.
Stripe rate limits its API with a token bucket and returns HTTP 429 with a Retry-After header when you run dry. A typical live-mode account gets on the order of 100 read or write requests per second, and because of the bucket you can briefly exceed the steady rate after an idle stretch without being blocked.
AWS uses token buckets all over its platform. EC2 API request throttling, DynamoDB's older provisioned-capacity model with burst credits, and gp2 EBS volume IOPS bursting are all token-bucket designs: you accumulate credits while idle and spend them during spikes.
On the client side, a well-behaved caller pairs token bucket with exponential backoff. When it sees a 429, it waits the suggested time, then retries, which keeps it inside the server's bucket instead of hammering an already-empty one.
Stripe API
Throttles API calls with a token bucket and returns HTTP 429 plus Retry-After when the bucket empties, allowing short bursts above the steady rate.
Amazon Web Services
Uses token buckets for EC2 API throttling, DynamoDB burst capacity, and gp2 EBS IOPS bursting, all of which bank credits while idle and spend them on spikes.
NGINX
Its limit_req module implements a leaky/token bucket with a burst parameter so clients can momentarily exceed the configured request rate.
Cloudflare
Rate limiting rules at the edge use token-bucket-style counters per IP or key to absorb bursts while capping sustained request rates.
Token bucket allows bursts: saved-up tokens let a client send many requests at once, then it settles to the refill rate. Leaky bucket forces a smooth, constant output rate and never lets bursts through, so it is used for traffic shaping rather than burst-friendly API limits.
The refill rate R sets the long-run average throughput, for example 100 requests per second. The capacity B sets the maximum burst size you tolerate after an idle period. They are tuned independently.
A timer per client does not scale. Instead they refill lazily: on each request they compute elapsed time times the rate, add that many tokens capped at the capacity, and update a stored timestamp. This is O(1) per request and stores only a counter and a timestamp per key.
The token count and timestamp are kept in a shared store like Redis, and the read, refill, and decrement are done atomically inside a Lua script so two concurrent requests cannot both spend the last token. The downside is a network round trip per request and a potential hotspot.
Respect the Retry-After header if present, then retry with exponential backoff and jitter. Retrying immediately just hits an empty bucket again and wastes the call.
Rate Limits and Provider Failure: The Number One Production Error
HTTP 429 is the first failure an LLM app hits at scale. Beat rate limits and provider outages with token buckets, backoff, degraded modes, and failover.
Rate Limiting
Protect your API from abuse and overload by controlling how many requests each consumer can make
Rate Limiting for Resilience
Protect services from abuse and overload, token bucket, sliding window, and distributed rate limiting
Design a Rate Limiter
Design a distributed rate limiting system - token bucket, sliding window, and protecting services at massive scale
Rate Limiting
Controlling how many requests a client can make in a given time window. Protects your API from abuse and ensures fair usage.
Sliding Window
A rate limiting algorithm that tracks requests in a rolling time window. More accurate than fixed windows because it smooths out spikes at window boundaries.
Throttling
Slowing down the rate of processing requests instead of rejecting them outright. The gentler cousin of rate limiting.
OAuth
An authorization framework that lets users grant third-party apps limited access to their accounts without sharing passwords. Powers 'Sign in with Google.'
JWT
JSON Web Token: a compact, self-contained token for transmitting claims between parties. The server can verify it without a database lookup.
SSL/TLS
Cryptographic protocols that encrypt data in transit between client and server. TLS is the modern successor to SSL. The 'S' in HTTPS.
This page explains the idea. The "Token Bucket Algorithm" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Token Bucket Algorithm lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about Token Bucket in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
