My favourite algorithm is generic cell rate algorithm (GCRA). It works like token bucket in this post. The implementation is dead simple and requires no background tasks and needs very minimal state.
Instead of storing the current number of tokens, you instead store when the bucket will be full. If you take a token from the bucket, you increment the timestamp accordingly by 1/rps. The only complication is it the filled timestamp was in the past, you have to first update it with the current timestamp to avoid overfilling.
What's even nicer is that it doubles as a throttle implementation rather than just a rate limiter. You know the bucket is empty if you compute empty_at=filled_at-(max_tokens/rps) which is still in the future. From that calculation you now know when it will have capacity again, so you can sleep accordingly. If you use a queue before the gcra, it then starts sowing down new connections rather than just dropping them.
You should still have a limit on the queue, but it's nice in that it can gracefully turn from token bucket into leaky bucket.
Ahh this has a name! I started doing this years ago and figured this must be used frequently because it’s so simple, elegant and can be done lock free. Thanks for calling it the name!
Instead of storing the current number of tokens, you instead store when the bucket will be full. If you take a token from the bucket, you increment the timestamp accordingly by 1/rps. The only complication is it the filled timestamp was in the past, you have to first update it with the current timestamp to avoid overfilling.
What's even nicer is that it doubles as a throttle implementation rather than just a rate limiter. You know the bucket is empty if you compute empty_at=filled_at-(max_tokens/rps) which is still in the future. From that calculation you now know when it will have capacity again, so you can sleep accordingly. If you use a queue before the gcra, it then starts sowing down new connections rather than just dropping them.
You should still have a limit on the queue, but it's nice in that it can gracefully turn from token bucket into leaky bucket.