速率限制算法限制请求

我需要设计速率限制器限制服务来限制请求。对于每个传入请求，方法都会检查每秒请求是否超出其限制。如果超过，它将返回需要等待处理的时间量。速率限制算法限制请求

寻找一个简单的解决方案，它只是使用系统滴答计数和rps（请求每秒）。不应该使用队列或复杂的速率限制算法和数据结构。

编辑：我将在C++中实现这一点。另外，请注意我不想使用任何数据结构来存储当前执行的请求。 API会像：（！RateLimiter.Limit（））

如果 { 做工作 RateLimiter.Done（）;

} 其他拒绝请求

来源

2014-10-30 user3403260

你打算如何衡量每个请求给系统带来的负载？ – CaldasGSM 2014-10-30 16:24:49

我不想测量负载。系统是一个非常低延迟的系统。所以只想限制费率。 – user3403260 2014-10-30 16:32:09

什么是你正在谈论的费率规格？请求/秒，请求/分钟？ – CaldasGSM 2014-10-30 16:35:37

，因为你给没有语言或平台我只是给了一些伪代码的提示..

的东西，你是要去需要

一当前正在执行的请求列表
等待收到通知，请求完成后

和代码可以简单到

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 
}

，但请记住，有几个问题与此

假定通过返回的等待时间，客户端会发出一个新的请求过了一段时间。由于时间是估计值，因此您不能使用它来延迟执行，或者您仍然可以溢出系统
，因为您没有保持队列并延迟请求，客户端可能会等待更多时间以满足他的需要。
对于最后一个，既然你没有什么要保持队列，优先和延迟请求，这意味着你可以有一个活锁，你告诉客户稍后返回，但是当他返回某人时已经采取了它的位置，他必须再次返回。

所以理想的解决方案应该是一个实际的执行队列，但因为你不想要一个..我想这是下一个最好的事情。

来源

2014-10-30 10:41:31 CaldasGSM

Acutally寻找一个只使用系统时间并且不需要额外数据结构的解决方案。每个请求只会增加一些时间到系统时间等等。 – user3403260 2014-10-30 16:22:12

根据你的意见你只是一个简单的（不是很精确）每秒请求标志。在这种情况下，代码可以是这样的

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; 
}

似乎并不像控制任何一个非常可靠的方法..但是..我相信这是你的要求..

来源

2014-10-30 16:55:13 CaldasGSM

最常见的算法用于此是token bucket。没有必要发明一个新的东西，只需要搜索你的技术/语言的实现。

如果您的应用程序的可用性/负载平衡较高，则可能需要将存储桶信息保存在某种持久存储上。 Redis是一个很好的候选人。

我写的Limitd是一种不同的方法，是一个限制的守护进程。如果流量符合要求，应用程序会询问使用有限客户端的守护进程。该限制是在限制服务器上配置的，该应用程序对该算法不可知。

来源

2015-04-19 14:17:33

速率限制算法限制请求

回答

相关问题