节流请求的速率限制算法

Question

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

寻找一种简单的解决方案，仅使用系统刻度计数和rps（每秒请求数）。不应使用队列或复杂的速率限制算法和数据结构。

编辑：我将在C ++中实现。另外，请注意，我不想使用任何数据结构来存储当前正在执行的请求。API将如下所示：

如果（！RateLimiter.Limit（））{做RateLimiter.Done（）;

} else拒绝请求

Answer 1

最常用的算法是令牌桶。无需发明新事物，只需在您的技术/语言中搜索实现。

如果您的应用具有高可用性/负载均衡，则您可能希望将存储桶信息保留在某种持久性存储上。Redis是一个很好的候选人。

我写Limitd是一种不同的方法，是限制的守护进程。应用程序使用受限客户端询问守护程序流量是否符合要求。该限制是在受限服务器上配置的，该应用程序与算法无关。

Answer 2

因为您没有给出语言或平台的提示，所以我只会给出一些伪代码。

你需要的东西

• 当前正在执行的请求的列表
• 等待请求完成时收到通知

代码可以很简单

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
}

但请记住，这有几个问题

• 假设通过返回等待时间，客户端将在经过时间后发出新请求。由于时间是一个估计值，因此您不能使用它来延迟执行，否则仍然可能导致系统溢出
• 由于您没有保留队列并延迟请求，因此客户端可能会等待比他需要的时间更多的时间。
• 最后，由于您不需要保持队列、优先级和延迟请求，这意味着您可以拥有一个活锁，您可以告诉客户端稍后返回，但当他返回时，有人已经占据了它的位置，他必须再次回来。

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