I needed a rate limit and wrote the 3 line version: a counter and the start of the current window. In review somebody said the words boundary problem, I switched to a token bucket, everybody nodded, the change went in. I could not have told you what either one lets through, so I built all of them and pushed 4 shapes of traffic at each.
The limit is 100 requests per 60 seconds throughout. What I measure is not how many requests got in overall, but the worst 60 seconds anywhere in the admitted stream, because that is the number the service behind the limiter has to survive.
The famous flaw is real. Put 100 requests in the last second of one window and 100 in the first second of the next. The counter admits all 200, because from its point of view those are 2 different windows with 100 each. The 60 seconds straddling the boundary contain double the limit.
It also needs an adversary who knows where the boundary is. Under steady traffic at twice the limit, the same counter never exceeds 100.
The one I switched to
The token bucket sized the obvious way, capacity equal to the limit, admits 199 in a window under plain steady overload. No adversary, no timing, just a client sending faster than it is allowed.
The arithmetic is not subtle once the number is in front of you. The bucket starts a window holding its capacity, which is spendable immediately. It refills at exactly the limit over the window, so that part is spendable as it lands. Capacity plus refill is what a window can pay out. Set the capacity to the limit and the answer is double.
Shrinking the bucket fixes that. Capacity 10 keeps the worst window at 109 across every shape I threw at it.
The cost of shrinking it
The fourth traffic shape is a client that says nothing for 9 minutes then sends 300 requests at once. Every limiter should let 100 of those through, since the client has been under its limit all along and now asks for exactly a window worth of work.
The fixed window admits 100. The sliding log admits 100. The bucket sized at the limit admits 100. The bucket I shrank to 10 admits 10, turning away 90 requests that were within the client rights.
That is the whole trade in 1 line of the table. A large bucket is generous to a quiet client. It also lets an overloaded one through at double. A small bucket holds the line and punishes exactly the well behaved caller who saved up nothing.
The one that never leaks
The sliding log admits exactly 100 in all 4 shapes, which is what it promises: it keeps the timestamps then counts what actually happened in the last 60 seconds.
It also keeps up to 100 timestamps per client. At 8 bytes each that is 800 bytes against the 16 a counter and a window start need. A token count with a refill time costs the same 16. 50 times the memory per client, plus a walk down the front of the list on every request. That is the price of a limiter with no scenario where it is the worst row in the table.
What I did not check
Any of this spread over more than 1 machine, which is where I actually needed it. 3 nodes with a counter each is 3 windows and 3 times the leak. The fix is either a shared store on the hot path or an allowance split 3 ways that wastes 2 thirds of the limit under uneven traffic. I measured none of that. I also gave every limiter a perfect clock. The sliding log in particular is exactly as correct as the timestamps it is handed.
The narrow claim is that the choice is not between a broken limiter and a correct one. Each of the cheap ones is the worst one in some traffic shape. The shape you get decides which flaw you bought.