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

Gratulant

how are you planing to measure the load that each request brings to the system? – Gentlemanatarms

I don't want to measure the load. System is a very low latency system. So just want to limit the rate. – Gratulant

whats is the kind of rate specification you are talking about? requests/second, requests/minutes? – Gentlemanatarms

Yes, want to limit RPS to the system. e.g. If I give 50 rps, no more than 50 request should get served every second. – Gratulant

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.

Circulate

Answer 2

since you give no hint of language or platform I'll just give out some pseudo code..

things you are gonna need

• a list of current executing requests
• a wait to get notified where a requests is finished

and the code can be as simple as

var ListOfCurrentRequests; //A list of the start time of current requests
var MaxAmoutOfRequests;// just a limit
var AverageExecutionTime;//if the execution time is non deterministic the best we can do is have a average

//for each request ether execute or return the PROBABLE amount to wait
function OnNewRequest(Identifier)
{
    if(count(ListOfCurrentRequests) < MaxAmoutOfRequests)//if we have room 
    {
        Struct Tracker
        Tracker.Request = Identifier;
        Tracker.StartTime = Now; // save the start time
        AddToList(Tracker) //add to list
    }
    else
    {
        return CalculateWaitTime()//return the PROBABLE time it will take for a 'slot' to be available
    }
}
//when request as ended release a 'slot' and update the average execution time
function OnRequestEnd(Identifier)
{
    Tracker = RemoveFromList(Identifier);
    UpdateAverageExecutionTime(Now - Tracker.StartTime);
}

function CalculateWaitTime()
{
    //the one that started first is PROBABLY the first to finish
    Tracker = GetTheOneThatIsRunnigTheLongest(ListOfCurrentRequests);
    //assume the it will finish in avg time
    ProbableTimeToFinish = AverageExecutionTime - Tracker.StartTime;
    return ProbableTimeToFinish
}

but keep in mind that there are several problems with this

• assumes that by returning the wait time the client will issue a new request after the time as passed. since the time is a estimation, you can not use it to delay execution, or you can still overflow the system
• since you are not keeping a queue and delaying the request, a client can be waiting for more time that what he needs.
• and for last, since you do not what to keep a queue, to prioritize and delay the requests, this mean that you can have a live lock, where you tell a client to return later, but when he returns someone already took its spot, and he has to return again.

so the ideal solution should be a actual execution queue, but since you don't want one.. I guess this is the next best thing.

Gentlemanatarms

Acutally looking for a solution which just uses system time and no extra data structures. Each request will just add some time to the system time and so on. – Gratulant

Answer 3

according to your comments you just what a simple (not very precise) requests per second flag. in that case the code can be something like this

var CurrentRequestCount;
var MaxAmoutOfRequests;
var CurrentTimestampWithPrecisionToSeconds
function CanRun()
{
    if(Now.AsSeconds > CurrentTimestampWithPrecisionToSeconds)//second as passed reset counter
        CurrentRequestCount=0;

    if(CurrentRequestCount>=MaxAmoutOfRequests)
        return false;

    CurrentRequestCount++
    return true;
}

doesn't seem like a very reliable method to control whatever.. but.. I believe it's what you asked..

Gentlemanatarms