限流算法用于控制请求速率的限制

Question

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

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

编辑：我将在c++中实现这个。还要注意，我不想使用任何数据结构来存储当前正在执行的请求。 API如下：

如果(!RateLimiter.Limit()) { do work RateLimiter.Done(); } 否则 拒绝请求

- user3403260

---

你打算如何测量每个请求对系统的负载？ - CaldasGSM

我不想测量负载。该系统是一个非常低延迟的系统。因此，只想限制速率。 - user3403260

你在谈论什么样的速率规范？每秒请求数，每分钟请求数？ - CaldasGSM

是的，想要限制系统的 RPS。例如，如果我给出 50 RPS，则每秒最多只能处理 50 个请求。 - user3403260

Answer 1

最常用于此的算法是令牌桶算法。没有必要发明新事物，只需在您的技术/语言上搜索实现。

如果您的应用程序具有高可用性/负载均衡，则可能希望将桶信息保留在某种持久性存储中。Redis是这方面的一个不错选择。

我写了Limitd，这是一种不同的方法，是限制的守护进程。应用程序使用limitd客户端向守护进程询问流量是否符合规定。限制在limitd服务器上配置，应用程序对算法不知情。

- José F. Romaniello

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
}

但请记住，这种方法存在几个问题。

• 假设通过返回等待时间，客户端将在时间结束后发出新的请求。由于时间是估计值，您不能使用它来延迟执行，否则仍可能导致系统溢出。
• 由于您没有保留队列和延迟请求，客户端可能需要等待比实际需要更长的时间。
• 最后，由于您不想保留队列以对请求进行优先级排序和延迟处理，这意味着您可能会出现“活锁”，即告诉客户端稍后返回，但当他返回时，已经有人占据了他的位置，他必须再次返回。

因此，理想的解决方案应该是一个实际的执行队列，但由于您不想要一个...我猜这是下一个最好的选择。

- CaldasGSM

---

实际上，我正在寻找一种只使用系统时间而不需要额外数据结构的解决方案。每个请求只会将一些时间添加到系统时间中，依此类推。 - user3403260

Answer 3

根据您的评论，您只需要一个简单（不是非常精确）的每秒请求标志。在这种情况下，代码可以是这样的。

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

看起来不像是一种很可靠的控制方法，但是我相信这就是你要求的。

- CaldasGSM