Token Bucket Algorithm — Complete Implementation Guide
In this tutorial, you will learn about Token Bucket Algorithm. We cover key concepts, practical examples, and best practices to help you master this topic.
The token bucket algorithm uses a bucket that fills with tokens at a constant rate, allowing bursts of traffic up to the bucket capacity while enforcing a steady average rate over time.
What You'll Learn
By the end of this tutorial, you will implement the token bucket algorithm, configure burst capacity and refill rates, and understand its advantages for API Rate Limiting.
Why It Matters
Token bucket is the most widely used rate limiting algorithm because it allows natural traffic bursts while maintaining long-term average limits. DodaTech's APIs use token bucket for general-purpose rate limiting.
Real-World Use
Doda Browser's sync API uses token bucket rate limiting with a capacity of 100 requests and a refill rate of 10 requests per second, allowing short bursts of activity while preventing sustained abuse.
Token Bucket Learning Path
flowchart LR
A[Algorithms Overview] --> B[Token Bucket]
B --> C[Burst Handling]
C --> D[Implementation]
B --> E{You Are Here}
style E fill:#f90,color:#fff
How Token Bucket Works
Imagine a bucket that holds tokens. A new token is added every refillInterval milliseconds. Each request removes one token. If the bucket is empty, the request is rejected. The bucket has a maximum capacity that limits bursts.
class TokenBucket {
constructor(capacity, refillRate, refillInterval) {
this.capacity = capacity;
this.tokens = capacity;
this.refillRate = refillRate;
this.refillInterval = refillInterval;
this.lastRefill = Date.now();
}
refill() {
const now = Date.now();
const elapsed = now - this.lastRefill;
const tokensToAdd = Math.floor(elapsed / this.refillInterval) * this.refillRate;
if (tokensToAdd > 0) {
this.tokens = Math.min(this.capacity, this.tokens + tokensToAdd);
this.lastRefill = now;
}
}
tryConsume(count = 1) {
this.refill();
if (this.tokens >= count) {
this.tokens -= count;
return true;
}
return false;
}
}
Per-Client Token Buckets
In production, each client gets its own token bucket identified by IP address, API key, or user ID.
const express = require("express");
const app = express();
const buckets = new Map();
function getBucket(key) {
if (!buckets.has(key)) {
buckets.set(key, new TokenBucket(100, 10, 1000));
}
return buckets.get(key);
}
app.use((req, res, next) => {
const key = req.ip;
const bucket = getBucket(key);
if (!bucket.tryConsume()) {
return res.status(429).json({
error: "Rate limit exceeded",
retryAfter: Math.ceil(bucket.refillInterval / bucket.refillRate)
});
}
next();
});
app.get("/", (req, res) => res.json({ ok: true }));
app.listen(3000);
Expected behavior: Each IP gets a bucket with 100 initial tokens, refilling 10 tokens per second. A burst of 100 requests is allowed, followed by 10 requests per second thereafter.
Token Bucket with Redis
For distributed deployments, Redis stores token bucket state that all server instances share.
const Redis = require("ioredis");
const redis = new Redis();
async function redisTokenBucket(req, res, next) {
const key = `bucket:${req.ip}`;
const capacity = 100;
const refillRate = 10;
const refillInterval = 1;
const result = await redis.eval(`
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refillRate = tonumber(ARGV[2])
local refillInterval = tonumber(ARGV[3])
local now = tonumber(ARGV[4])
local bucket = redis.call("HMGET", key, "tokens", "lastRefill")
local tokens = tonumber(bucket[1]) or capacity
local lastRefill = tonumber(bucket[2]) or now
local elapsed = now - lastRefill
local refillAmount = math.floor(elapsed / refillInterval) * refillRate
tokens = math.min(capacity, tokens + refillAmount)
lastRefill = now
if tokens >= 1 then
tokens = tokens - 1
redis.call("HMSET", key, "tokens", tokens, "lastRefill", lastRefill)
redis.call("EXPIRE", key, 86400)
return {1, tokens, capacity}
else
redis.call("HMSET", key, "tokens", tokens, "lastRefill", lastRefill)
return {0, tokens, capacity}
end
`, 1, key, capacity, refillRate, refillInterval, Date.now());
if (result[0] === 0) {
return res.status(429).json({ error: "Too many requests", remaining: 0 });
}
next();
}
Common Mistakes
Not handling clock precision — Using seconds instead of milliseconds for refill intervals leads to inaccurate rate limiting.
Allowing negative token counts — When consuming with zero tokens, the count should not go below zero.
Creating buckets without cleanup — Each unique client creates a bucket. Without cleanup, memory grows indefinitely for high-traffic APIs.
Refilling on every request -- Calculating refill on every request is fine. The alternative (a background timer) adds complexity without benefit.
Using floating point for token counts -- Round token counts to integers to avoid drift over time.
Practice Questions
What happens when the token bucket is full? Additional refill tokens are discarded. The bucket never exceeds its capacity.
How does token bucket allow bursts? A full bucket (capacity N) allows N requests instantly. After depletion, the steady refill rate applies.
What is the advantage of token bucket over fixed window? Token bucket allows bursts and does not have boundary spikes. Fixed window allows double traffic at window boundaries.
Challenge: Implement a token bucket that supports consuming multiple tokens per request for expensive operations.
class WeightedTokenBucket extends TokenBucket {
tryConsume(weight = 1) {
this.refill();
if (this.tokens >= weight) {
this.tokens -= weight;
return true;
}
return false;
}
}
FAQ
Mini Project
Build a complete token bucket rate limiter with configurable per-client limits, Redis persistence, and proper cleanup.
class CleanableTokenBucket {
constructor(capacity, refillRate, refillInterval, ttl) {
this.capacity = capacity;
this.refillRate = refillRate;
this.refillInterval = refillInterval;
this.ttl = ttl || 3600000;
this.buckets = new Map();
}
getBucket(key) {
if (!this.buckets.has(key)) {
this.buckets.set(key, {
tokens: this.capacity,
lastRefill: Date.now(),
createdAt: Date.now()
});
}
return this.buckets.get(key);
}
tryConsume(key) {
const bucket = this.getBucket(key);
const now = Date.now();
const elapsed = now - bucket.lastRefill;
const refillAmount = Math.floor(elapsed / this.refillInterval) * this.refillRate;
bucket.tokens = Math.min(this.capacity, bucket.tokens + refillAmount);
bucket.lastRefill = now;
if (bucket.tokens >= 1) {
bucket.tokens -= 1;
return true;
}
return false;
}
cleanup() {
const now = Date.now();
for (const [key, bucket] of this.buckets) {
if (now - bucket.createdAt > this.ttl && bucket.tokens >= this.capacity) {
this.buckets.delete(key);
}
}
}
}
setInterval(() => limiter.cleanup(), 300000);
What's Next
Now that you understand the token bucket algorithm, explore the leaky bucket algorithm for traffic shaping. Then learn about implementing the fixed window algorithm.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro