Rate limiting-Algorithmus für die Drosselung Anfrage

Ich brauche zur Gestaltung einer rate limiter service für die Drosselung Anfragen.
Für jede ankommende Anfrage eine Methode soll überprüfen, ob die Anforderungen pro Sekunde das limit überschritten hat oder nicht. Wenn es überschritten hat, dann wird es wieder die Zeit, die man warten muss behandelt werden.

Suche nach einer einfachen Lösung, die nur das system-tick count und rps(Anfragen pro Sekunde). Sollten Sie nicht verwenden die Warteschlange oder Komplex rate limiting algorithmen und Datenstrukturen.

Edit: ich werde die Umsetzung in c++. Beachten Sie auch, ich will nicht beliebige Daten verwenden, die Strukturen, die zum speichern der Antrag derzeit immer ausgeführt.
API wäre wie:

if (!RateLimiter.Limit())
{
arbeiten
RateLimiter.Done();

}
sonst
ablehnen Antrag

  • wie planen Sie zur Messung die Last, die jeder Anforderung bringt das system?
  • Ich will nicht zu Messen Sie den laden. System ist ein low-latency system. So einfach wollen für die Begrenzung der rate.
  • was ist die Art der rate-Spezifikation, die Sie sprechen? Anfragen/Sekunde, Anfragen/Minuten?
  • Ja, einschränken möchten, RPS system. Wenn ich z.B. 50 rps, nicht mehr als 50 Anfrage bekommen sollten, Ihnen jeden zweiten.
InformationsquelleAutor user3403260 | 2014-10-30
  1. 6

    Die häufigsten verwendete Algorithmus für diese ist token bucket. Es gibt keine Notwendigkeit, zu erfinden, zu einer neuen Sache, nur Suche für eine Implementierung auf die Technik/Sprache".

    Wenn Sie Ihre app hoch ist avalaible /Lastenausgleich möchten Sie vielleicht halten Sie den Eimer Informationen auf irgendeine Art von persistent-storage. Redis ist ein guter Kandidat für diese.

    Schrieb ich Limitd ist ein anderer Ansatz, ist ein daemon für Grenzen. Die Anwendung fragt der Dämon mit einer limitd-client, wenn der Verkehr ist konform. Die Grenze konfiguriert ist, auf die limitd server und die app ist agnostisch an den Algorithmus.

    InformationsquelleAutor José F. Romaniello
  2. 0

    da Sie geben keinen Hinweis auf die Sprache oder Plattform werde ich nur geben, einige pseudo-code..

    Dinge, die Sie sind gonna brauchen

    • eine Liste der aktuellen Ausführung von Anfragen
    • warten, um benachrichtigt zu werden, wo Anfragen fertig ist

    ist und der code kann so einfach sein wie

    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
}

    aber im Hinterkopf behalten, dass es gibt einige Probleme mit dieser

    • davon ausgegangen, dass-auch durch Rücksendung der Wartezeit der client eine neue Anfrage nach der Zeit als bestanden. seit der Zeit ist eine Schätzung, die Sie nicht verwenden, kann es zu Verzögerung der Ausführung, oder Sie können noch overflow das system
    • da Sie nicht das halten einer Warteschlange und die Verzögerung der Anforderung eines Clients wartet auf mehr Zeit, dass das, was er braucht.
    • und zum letzten, da Sie nicht wissen, was zu halten eine Warteschlange, um Prioritäten zu setzen und unverzüglich die Anforderungen, das bedeutet, dass Sie können haben eine live lock, wo Sie sagen, ein client zu einem späteren Zeitpunkt wieder, aber wenn er zurück kommt schon jemand nahm seinen Platz, und er hat wieder zu kommen.

    also die ideale Lösung sollte eine tatsächliche Ausführung der Warteschlange, aber da wollen Sie nicht ein.. ich denke, das ist die nächste beste Sache.

    • Eigentlich auf der Suche nach einer Lösung, die einfach das system Zeit und keine extra Daten-Strukturen. Jede Anfrage wird fügen Sie einfach einige Zeit, um das system Zeit, und so weiter.
    InformationsquelleAutor CaldasGSM
  3. 0

    nach, um Ihre Kommentare, was ein einfaches (nicht sehr präzise) Anfragen pro Sekunde Flagge. in diesem Fall kann der code so etwas wie dieses

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

    scheint nicht, wie eine sehr zuverlässige Methode, um zu Steuern, was auch immer.. aber.. ich glaube, es ist das, was Sie gefragt..

    InformationsquelleAutor CaldasGSM
Schreibe einen Kommentar