The Rate Limiter Strikes Back: Designing a Token Bucket from Scratch

The Quest Begins (The "Why") I still remember the first time our API started choking under a sudden traffic spike. It was a Friday afternoon, the kind where you’re just about to log off, and the monitoring dashboard lit up like a Christmas tree. Requests were piling up, latency shot through the roof, and our users began seeing those dreaded “429 Too Many Requests” errors. We had a naive rate limiter in place—a simple fixed‑window counter that reset every minute. It worked fine when traffic was steady, but as soon as a burst hit, the counter would either let too many through (because we hadn’t hit the limit yet) or block everything for the whole minute (because we’d already exhausted the quota). It felt like trying to hold back a tsunami with a sandbag. Honestly, I was frustrated. I knew there had to be a smarter way to smooth out those bursts without penalizing honest users or over‑protecting the system. That’s when I dove into the world of rate‑limiting algorithms, and the token bucket caught my eye like a shiny loot drop in a dungeon. The Revelation (The Insight) The token bucket is deceptively simple, yet it solves the exact pain points we were experiencing. Imagine a bucket that holds a fixed number of tokens. Tokens drip into the bucket at a steady rate (say, 10 tokens per second). Each incoming request consumes a token. If the bucket is empty, the request is denied or delayed; if there’s a token, the request proceeds and the token is removed. Why does this beat the fixed‑window counter? Burst tolerance – The bucket can store up to its capacity, allowing a short burst of requests up to that limit without waiting for the next window. Smooth throttling – Because tokens are added continuously, the limiter adapts to the actual request rate rather than resetting abruptly at arbitrary intervals. Memory‑light – We only need to track two numbers: the current token count and the last time we refilled the bucket. No arrays of timestamps per key. Here’s a quick ASCII sket