速率限制算法限制請求

我需要設計速率限制器限制服務來限制請求。對於每個傳入請求，方法都會檢查每秒請求是否超出其限制。如果超過，它將返回需要等待處理的時間量。速率限制算法限制請求

尋找一個簡單的解決方案，它只是使用系統滴答計數和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

速率限制算法限制請求

回答

相關問題