CONCEPT · 45 minutes
Design a token-bucket rate limiter for an AI API — grounded in the workflow-engine-rs rate-limiting subsystem.
In workflow-engine-rs, I needed to control how many external API calls the execution engine made per unit time. The first approach was simple: a counter in memory, reset every second. It worked fine with a single worker process. The moment I added a second worker process, the counter broke — each process had its own counter, and the two workers together sent double the allowed rate.
This is the rate limiter problem in one sentence: rate limiting is easy in a single process and hard across processes. In a single process, shared memory is sufficient. In a distributed system — multiple servers, multiple workers — you need shared state that multiple processes can read and update atomically.
My workflow engine enforces per-job API call rates to stay within external API quotas — and that constraint is representative of what any service running on external APIs has to manage.
Think of a rate limiter like a highway on-ramp with a traffic light. Cars (requests) can enter the highway at a controlled pace — one car per green signal. If cars arrive faster than the light allows, they wait. If the ramp is full, the light turns red and cars are turned away. The light enforces a maximum flow rate regardless of demand.
The two questions every rate limiter design must answer: (1) What is the limiting unit — per user, per API key, per IP, per global resource? (2) What is the time window — per second, per minute, sliding or fixed? The answers determine the algorithm and the data structure.
This module walks through the token bucket algorithm (the right default for most APIs), compares it to the alternatives, and shows how to build a distributed rate limiter using Redis atomic operations.
The first thing you'd reach for is a fixed window counter: count requests per second, reset on the clock tick. Simple, and mostly works — until a burst at the window boundary doubles your intended rate without the limiter catching it. Token bucket fixes that.
The token bucket is the most flexible rate limiting algorithm for real-world APIs. The mental model: a bucket has a maximum capacity of C tokens. Tokens fill the bucket at a steady rate R (tokens per second). Each incoming request costs one token. If the bucket has tokens, the request is allowed and a token is consumed. If the bucket is empty, the request is rejected.
The key property: short bursts above the average rate are allowed, up to the bucket capacity. This is desirable for real API usage, which comes in bursts rather than perfectly uniform streams.
flowchart LR
A["Token Source\n(fills at rate R/s)"] -->|"add tokens"| B["Token Bucket\n(capacity C)"]
C[Incoming Request] --> D{Bucket has tokens?}
B --> D
D -->|"yes: consume 1 token"| E[Allow Request]
D -->|"no: bucket empty"| F[Reject Request\n429 Too Many Requests]
style E fill:#10b981,color:#fff
style F fill:#dc2626,color:#fffThe two parameters control the behavior completely:
Why bursts are desirable: Real clients do not send requests at perfectly uniform intervals. A mobile app might send 5 requests in quick succession (a user switching tabs) and then be idle for 30 seconds. A leaky bucket would reject 4 of those 5 requests even though the client is well within their average rate. The token bucket absorbs the burst by drawing down accumulated tokens.
On a single server, a token bucket is a simple in-memory structure:
The single-server limit: This implementation requires a mutex or async lock in a concurrent server — two concurrent requests calling allow() can both see tokens >= 1 and both decrement, consuming more tokens than intended. In a single process, this is solvable. Across multiple processes, you need shared state with atomic operations — which is where Redis enters.
Three algorithms appear most often in rate limiter designs. Understanding when each one is right matters.
Token bucket: bucket fills at rate R, capacity C. Bursts up to C allowed. Best for most API use cases — flexible and intuitive.
Leaky bucket: requests drain from a queue at a fixed rate; if the queue is full, the request is rejected. Enforces a strict average rate with no burst allowance. Best when you need to smooth bursty traffic before sending it downstream — for example, smoothing API calls to a rate-limited external service.
Sliding window counter: counts requests in a rolling time window. More accurate than fixed-window counting (which can allow double the rate at window boundaries) but requires storing per-second or per-minute buckets in memory or Redis. Commonly used for per-user rate limits in web APIs.
| Algorithm | Burst Allowed | Implementation Complexity | Best For |
|---|---|---|---|
| Token bucket | Yes, up to capacity | Low | API rate limits with natural burst |
| Leaky bucket | No | Medium | Smoothing traffic to external APIs |
| Sliding window | Small (sub-window) | Medium | Per-user web API rate limits |
Before the distributed design section, verify you can answer these from memory:
Reflective prompt: In workflow-engine-rs, I rate-limit external API calls to stay within a vendor's rate limits. The vendor uses a sliding window (per-minute) counter. But my internal rate limiter uses a token bucket. Why might I choose different algorithms for these two contexts? Write two sentences before moving to the distributed design section.
Redis is the standard backend for distributed rate limiters. Its INCR and EXPIRE commands allow atomic counter updates; its Lua scripting engine allows multi-step operations (check + decrement) to execute atomically on the server, eliminating race conditions.
The cleanest implementation: a Lua script that checks the token count, refills based on elapsed time, and decrements atomically — all in a single round-trip.
The Redis failure mode: If Redis goes down, your rate limiter fails. You have two options: fail open (allow all requests) or fail closed (reject all requests). Fail open maintains availability at the cost of temporarily uncontrolled traffic. Fail closed maintains correctness at the cost of a full service outage. For most APIs, fail open with an alert is the right choice — a brief uncontrolled spike is less harmful than a complete outage.
Apply rate limiter design to a concrete system.
The task: Design the rate limiting subsystem for a public AI API. The API charges by token. You need to enforce per-API-key rate limits: 60 requests per minute and 100,000 tokens per day. The API runs on 5 server instances.
<CodeExample title="Design Prompt Starter — AI API Rate Limiter" language="markdown" code={`## Requirements
Apply rate limiting design principles to realistic scenarios
1. A token bucket has rate=10 tokens/second and capacity=50. A client sends no requests for 30 seconds, then sends 60 requests in 1 second. How many are allowed?
Correct Answer: B
The bucket fills at 10 tokens/second but is capped at capacity=50. After 30 seconds of idle, the bucket holds 50 tokens (not 300). The first 50 requests consume those tokens and are allowed; the next 10 are rejected. Capacity is what makes the token bucket a rate limiter rather than a credit system.
2. You are designing a rate limiter that calls an external service with a strict 100 requests/minute limit. You need to smooth out bursty client traffic before it reaches the external service. Which algorithm is best?
Correct Answer: B
The leaky bucket drains at a fixed rate regardless of how fast requests arrive. This is exactly what you need when calling a downstream service with a strict rate limit — you want to smooth out bursty upstream traffic before it reaches the external service. The token bucket allows bursts that could exceed the external service's per-minute limit.
3. A rate limiter stores token counts in process memory. The API runs on 3 servers. Each server enforces 100 requests/minute. What is the actual effective rate limit?
Correct Answer: B
Each server has its own in-memory counter. A client whose requests are distributed across 3 servers sees 3 independent rate limiters, each allowing 100 requests. The effective limit is 300 requests/minute — triple the intended limit. In-memory rate limiters only work when all requests from a client hit the same server (sticky sessions) or when you use shared state (Redis).
4. Your Redis-backed rate limiter uses a Lua script to check and decrement the token count atomically. Why is the Lua script necessary rather than a simple GET then SET?
Correct Answer: B
GET then SET is a check-then-act pattern with a race condition. Between the GET and the SET, another request can read the same token count and also decide to proceed. Both decrement, consuming more tokens than available. A Lua script runs atomically — no other command can execute on the key between the check and the decrement. This eliminates the race condition without requiring distributed locks.
5. A rate-limited API returns 429 without a Retry-After header. What problem does this create for clients?
Correct Answer: B
Without Retry-After, clients must guess how long to wait before retrying. Aggressive clients may retry immediately and repeatedly, generating more 429s and adding load during an already-constrained period. Retry-After (or X-RateLimit-Reset) tells the client exactly when the window resets, enabling well-behaved backoff and reducing unnecessary retries.
6. Your rate limiter's Redis instance goes down. You choose to fail open (allow all requests). What is the risk and what metric should you monitor?
Correct Answer: B
Fail open maintains API availability during a Redis outage at the cost of uncontrolled traffic. The risk is that burst traffic or an abusive client hits your backend at full speed during the outage window. The mitigation is monitoring: instrument every request that bypasses the rate limiter, alert on non-zero bypass counts, and ensure Redis is highly available. Failing closed — rejecting all requests during a Redis outage — is often worse: it takes your whole API down rather than one client's quota.