Rate limiting algorithm for throttling request

Question

I need to design a rate limiter service for throttling requests. For every incoming request a method will check if the requests per second has exceeded its limit or not. If it has exceeded then it will return the amount of time it needs to wait for being handled.

Looking for a simple solution which just uses system tick count and rps(request per second). Should not use queue or complex rate limiting algorithms and data structures.

Edit: I will be implementing this in c++. Also, note I don't want to use any data structures to store the request currently getting executed. API would be like:

if (!RateLimiter.Limit()) { do work RateLimiter.Done();

} else reject request

Answer 1

The most common algorithm used for this is token bucket. There is no need to invent a new thing, just search for an implementation on your technology/language.

If your app is high avalaible / load balanced you might want to keep the bucket information on some sort of persistent storage. Redis is a good candidate for this.

I wrote Limitd is a different approach, is a daemon for limits. The application ask the daemon using a limitd client if the traffic is conformant. The limit is configured on the limitd server and the app is agnostic to the algorithm.