Umgang mit Bursty Traffic: Leaky Bucket- und Token Bucket-Algorithmen

API7.ai

January 5, 2023

OpenResty (NGINX + Lua)

In den vorherigen Artikeln haben wir uns mit Code-Optimierung und Cache-Design beschäftigt, die eng mit der Gesamtleistung der Anwendung verbunden sind und unsere Aufmerksamkeit verdienen. In realen Geschäftsszenarien müssen wir jedoch auch die Auswirkungen von plötzlichem Datenverkehr auf die Leistung berücksichtigen. Plötzlicher Datenverkehr kann hier normal sein, wie z. B. Verkehr durch aktuelle Nachrichten, Werbeaktionen usw., oder abnormaler Verkehr, wie z. B. DDoS-Angriffe.

OpenResty wird heute hauptsächlich als Zugriffsschicht für Webanwendungen wie WAFs (Web Application Firewalls) und API-Gateways verwendet, die mit dem oben genannten normalen und abnormalen plötzlichen Datenverkehr umgehen müssen. Schließlich können Backend-Dienste leicht überlastet werden, wenn plötzlicher Datenverkehr nicht bewältigt werden kann, und das Geschäft wird nicht angemessen reagieren. Daher werden wir uns heute mit Möglichkeiten zur Bewältigung von plötzlichem Datenverkehr befassen.

Verkehrssteuerung

Die Verkehrssteuerung ist eine unverzichtbare Funktion für WAFs und API-Gateways. Sie stellt sicher, dass Upstream-Dienste ordnungsgemäß funktionieren, indem der eingehende Datenverkehr durch einige Algorithmen kanalisiert und kontrolliert wird, wodurch das System gesund bleibt.

Da die Verarbeitungskapazität des Backends begrenzt ist, müssen wir mehrere Aspekte wie Kosten, Benutzererfahrung und Systemstabilität berücksichtigen. Unabhängig davon, welcher Algorithmus verwendet wird, wird dies unweigerlich dazu führen, dass normale Benutzeranfragen verlangsamt oder sogar abgelehnt werden, was einen Teil der Benutzererfahrung opfert. Daher müssen wir den Datenverkehr kontrollieren und gleichzeitig die Geschäftsstabilität und die Benutzererfahrung ausbalancieren.

Tatsächlich gibt es im wirklichen Leben viele Beispiele für "Verkehrssteuerung". Zum Beispiel während der chinesischen Frühlingsfest-Reisezeit, wenn Menschenmengen in U-Bahn-Stationen, Bahnhöfen, Flughäfen und anderen Verkehrsknotenpunkten gedrängt sind, weil die Kapazität dieser Verkehrsmittel begrenzt ist. Daher müssen die Passagiere in der Schlange warten und in Gruppen in den Bahnhof eintreten, um ihre Sicherheit und den regulären Betrieb des Verkehrs zu gewährleisten.

Dies beeinträchtigt natürlich die Passagiererfahrung, aber insgesamt gewährleistet es den effizienten und sicheren Betrieb des Systems. Wenn es beispielsweise keine Warteschlange und keine Gruppenbildung gäbe, sondern jeder in einem Schwarm in den Bahnhof eintreten dürfte, wäre das Ergebnis, dass das gesamte System zusammenbrechen würde.

Zurück zur Technologie: Nehmen wir an, ein Upstream-Dienst ist dafür ausgelegt, 10.000 Anfragen pro Minute zu verarbeiten. Zu Spitzenzeiten, wenn es am Eingangspunkt keine Verkehrssteuerung gibt und der Stapel von Aufgaben 20.000 pro Minute erreicht, wird die Verarbeitungsleistung dieses Upstream-Dienstes möglicherweise auf nur 5.000 Anfragen pro Minute sinken und sich weiter verschlechtern, was schließlich zur Nichtverfügbarkeit des Dienstes führen könnte. Dies ist nicht das Ergebnis, das wir sehen möchten.

Die gängigen Algorithmen zur Verkehrssteuerung, die wir zur Bewältigung solcher plötzlichen Datenverkehrsspitzen verwenden, sind der Leaky-Bucket-Algorithmus und der Token-Bucket-Algorithmus.

Leaky-Bucket-Algorithmus

Beginnen wir mit dem Leaky-Bucket-Algorithmus, der darauf abzielt, eine konstante Anforderungsrate aufrechtzuerhalten und plötzliche Verkehrsspitzen zu glätten. Aber wie wird dies erreicht? Schauen wir uns zunächst die folgende konzeptionelle Abstraktion aus der Wikipedia-Einführung zum Leaky-Bucket-Algorithmus an.

Leaky-Bucket-Algorithmus

Wir können uns den Datenverkehr des Clients als Wasser vorstellen, das aus einem Wasserrohr mit einer ungewissen Fließgeschwindigkeit fließt, manchmal schnell und manchmal langsam. Das externe Verkehrsverarbeitungsmodul, das den Eimer darstellt, der das Wasser aufnimmt, hat ein Loch am Boden, durch das das Wasser ausläuft. Dies ist der Ursprung des Namens des Leaky-Bucket-Algorithmus, der die folgenden Vorteile hat:

Erstens: Egal, ob der Zufluss in den Eimer ein Rinnsal oder eine riesige Flut ist, es wird garantiert, dass die Rate des aus dem Eimer fließenden Wassers konstant ist. Dieser stetige Verkehr ist freundlich zu Upstream-Diensten, was das Ziel der Verkehrsformung ist.

Zweitens: Der Eimer selbst hat ein bestimmtes Volumen und kann eine bestimmte Menge Wasser ansammeln. Dies entspricht Client-Anfragen, die in eine Warteschlange gestellt werden können, wenn sie nicht sofort verarbeitet werden können.

Drittens: Wasser, das das Volumen des Eimers überschreitet, wird vom Eimer nicht aufgenommen, sondern fließt ab. Die entsprechende Metapher hier ist, dass, wenn es zu viele Client-Anfragen gibt, die die Warteschlangenlänge überschreiten, direkt eine Fehlermeldung an den Client zurückgegeben wird. In diesem Moment kann der Server so viele Anfragen nicht verarbeiten, und das Warten in der Warteschlange wird unnötig.

Wie sollte dieser Algorithmus implementiert werden? Nehmen wir die resty.limit.req-Bibliothek, die mit OpenResty geliefert wird, als Beispiel. Es ist ein Ratenbegrenzungsmodul, das mit dem Leaky-Bucket-Algorithmus implementiert ist. Wir werden in den folgenden Artikeln mehr darüber erfahren. Heute beginnen wir mit einem kurzen Blick auf die folgenden Codezeilen, die die Schlüsselzeilen sind:

local elapsed = now - tonumber(rec.last)
excess = max(tonumber(rec.excess) - rate * abs(elapsed) / 1000 + 1000,0)
if excess > self.burst then
    return nil, "rejected"
end
-- return the delay in seconds, as well as excess
return excess / rate, excess / 1000

Lassen Sie uns diese Codezeilen kurz durchlesen. Dabei ist elapsed die Anzahl der Millisekunden zwischen der aktuellen und der letzten Anfrage, und rate ist die Rate, die wir pro Sekunde festlegen. Da die kleinste Einheit von rate 0,001 s/r ist, muss der obige Code mit 1000 multipliziert werden, um ihn zu berechnen.

excess gibt die Anzahl der Anfragen an, die sich noch in der Warteschlange befinden, 0 bedeutet, dass der Eimer leer ist, keine Anfragen in der Warteschlange, und burst bezieht sich auf das Volumen des gesamten Eimers. Wenn excess größer als burst ist, bedeutet dies, dass der Eimer voll ist, und der eingehende Verkehr wird direkt verworfen; wenn excess größer als 0 und kleiner als burst ist, wird er in die Warteschlange gestellt, um auf die Verarbeitung zu warten, und das hier zurückgegebene excess/rate ist die Wartezeit.

Auf diese Weise können wir die Warteschlangenlänge von plötzlichem Datenverkehr durch Anpassen der burst-Größe kontrollieren, während die Verarbeitungskapazität des Backend-Dienstes unverändert bleibt. Es hängt jedoch von Ihrem Geschäftsszenario ab, ob Sie dem Benutzer mitteilen, dass es zu viele Anfragen gibt und er später erneut versuchen soll, oder ob Sie den Benutzer länger warten lassen.

Token-Bucket-Algorithmus

Sowohl der Token-Bucket-Algorithmus als auch der Leaky-Bucket-Algorithmus haben das gleiche Ziel, nämlich sicherzustellen, dass Backend-Dienste nicht durch plötzliche Verkehrsspitzen überlastet werden, obwohl die beiden nicht auf die gleiche Weise implementiert sind.

Der Leaky-Bucket-Algorithmus verwendet die Endpunkt-IP, um die Grundlagen für die Verkehrs- und Ratenbegrenzung zu schaffen. Auf diese Weise ist die Ausgangsrate des Leaky-Bucket-Algorithmus für jeden Client festgelegt. Dies stellt jedoch ein Problem dar:

Angenommen, die Anfragen des Benutzers A sind häufig und die Anfragen anderer Benutzer sind selten. In diesem Fall wird der Leaky-Bucket-Algorithmus einige der Anfragen von A verlangsamen oder ablehnen, obwohl der Dienst sie zu diesem Zeitpunkt verarbeiten könnte, obwohl der Gesamtdruck auf den Dienst nicht sehr hoch ist.

Hier kommt der Token-Bucket ins Spiel.

Während der Leaky-Bucket-Algorithmus darauf abzielt, den Verkehr zu glätten, ermöglicht der Token-Bucket, dass plötzliche Verkehrsspitzen in den Backend-Dienst gelangen. Das Prinzip des Token-Buckets besteht darin, Token mit einer festen Rate in den Eimer zu legen und sie weiterhin einzulegen, solange der Eimer nicht voll ist. Auf diese Weise müssen alle Anfragen, die vom Endpunkt kommen, zuerst zum Token-Bucket gehen, um das Token zu erhalten, bevor der Backend sie verarbeiten kann; wenn sich kein Token im Eimer befindet, wird die Anfrage abgelehnt.

OpenResty implementiert jedoch keine Token-Buckets, um den Verkehr und die Rate in seiner Bibliothek zu begrenzen. Daher hier eine kurze Einführung in das auf Token-Buckets basierende Ratenbegrenzungsmodul lua-resty-limit-rate, das von UPYUN als Open Source bereitgestellt wird, als Beispiel:

local limit_rate = require "resty.limit.rate"

-- global 20r/s 6000r/5m
local lim_global = limit_rate.new("my_limit_rate_store", 100, 6000, 2)

-- single 2r/s 600r/5m
local lim_single = limit_rate.new("my_limit_rate_store", 500, 600, 1)

local t0, err = lim_global:take_available("__global__", 1)
local t1, err = lim_single:take_available(ngx.var.arg_userid, 1)

if t0 == 1 then
    return -- global bucket is not hungry
else
    if t1 == 1 then
        return -- single bucket is not hungry
    else
        return ngx.exit(503)
    end
end

In diesem Code haben wir zwei Token-Buckets eingerichtet: einen globalen Token-Bucket und einen Token-Bucket mit ngx.var.arg_userid als key, getrennt nach Benutzer. Es gibt eine Kombination der beiden Token-Buckets, die den folgenden Hauptvorteil hat:

  • Es muss nicht der Token-Bucket des Benutzers bestimmt werden, wenn sich noch Token im globalen Token-Bucket befinden, und es können so viele plötzliche Anfragen von Benutzern bedient werden, wie der Backend-Dienst ordnungsgemäß ausführen kann.
  • Wenn kein globaler Token-Bucket vorhanden ist, können Anfragen nicht willkürlich abgelehnt werden, daher ist es notwendig, den Token-Bucket einzelner Benutzer zu bestimmen und Anfragen von Benutzern mit mehr plötzlichen Anfragen abzulehnen. Auf diese Weise wird sichergestellt, dass Anfragen anderer Benutzer nicht beeinträchtigt werden.

Offensichtlich sind Token-Buckets flexibler als Leaky-Buckets und ermöglichen Situationen, in denen plötzliche Verkehrsspitzen an Backend-Dienste weitergeleitet werden. Aber natürlich haben beide ihre Vor- und Nachteile, und Sie können sie je nach Ihrer Situation auswählen.

NGINX-Ratenbegrenzungsmodul

Nachdem wir diese beiden Algorithmen behandelt haben, schauen wir uns abschließend an, wie eine Ratenbegrenzung in NGINX implementiert werden kann. In NGINX ist das limit_req-Modul das am häufigsten verwendete Ratenbegrenzungsmodul, und die folgende ist eine einfache Konfiguration:

limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;

server {
    location /search/ {
        limit_req zone=one burst=5;
    }
}

Dieser Code nimmt die IP-Adresse des Clients als key, fordert einen 10M großen Speicherplatz namens one an und begrenzt die Rate auf 1 Anfrage pro Sekunde.

Im Standort des Servers wird auch die one-Ratenbegrenzungsregel referenziert, und brust wird auf 5 gesetzt. Wenn die Rate 1r/s überschreitet, können 5 Anfragen gleichzeitig in die Warteschlange gestellt werden, was einen gewissen Pufferbereich bietet. Wenn brust nicht gesetzt ist, werden Anfragen, die die Rate überschreiten, direkt abgelehnt.

Dieses NGINX-Modul basiert auf einem Leaky-Bucket, ist also im Wesentlichen das gleiche wie resty.limit.req in OpenResty, das wir oben beschrieben haben.

Zusammenfassung

Das größte Problem der Ratenbegrenzung in NGINX ist, dass sie nicht dynamisch geändert werden kann. Schließlich müssen Sie die Konfigurationsdatei nach der Änderung neu starten, um sie wirksam zu machen, was in einer sich schnell ändernden Umgebung nicht akzeptabel ist. Daher werden wir uns im folgenden Artikel mit der dynamischen Implementierung von Verkehrs- und Ratenbegrenzungen in OpenResty befassen.

Abschließend stellen wir uns eine Frage. Aus der Perspektive von WAFs und API-Gateways: Gibt es eine bessere Möglichkeit, normale Benutzeranfragen von bösartigen Anfragen zu unterscheiden? Denn für plötzlichen Datenverkehr von normalen Benutzern können wir die Backend-Dienste schnell skalieren, um die Kapazität des Dienstes zu erhöhen, während es besser ist, bösartige Anfragen direkt an der Zugriffsschicht abzulehnen.

Sie sind herzlich eingeladen, diesen Artikel an Ihre Kollegen und Freunde weiterzuleiten, um gemeinsam zu lernen und Fortschritte zu erzielen.