Wie implementiert man den Token-Bucket-Algorithmus mit Redis? (mit Code)

Dieser Artikel wird Ihnen das Prinzip des Token-Bucket-Algorithmus vorstellen und die Methode zur Verwendung von Redis zur Implementierung des Token-Bucket-Algorithmus vorstellen. Ich hoffe, dass er für alle hilfreich ist!

Unter den Strombegrenzungsalgorithmen gibt es einen Token-Bucket-Algorithmus, der mit kurzen Verkehrsstößen umgehen kann. Dies ist besonders nützlich für Situationen, in denen die Strombegrenzung nicht sehr gleichmäßig ist Wird häufig ausgelöst. Der Anrufer ist relativ freundlich.

Zum Beispiel liegt der aktuelle Grenzwert bei 10 qps. In den meisten Fällen wird dieser Wert nicht überschritten, aber gelegentlich werden 30 qps erreicht, und dann wird der Wert bald wieder normal sein, vorausgesetzt, dass dieser Verkehrsstoß keine Auswirkungen hat Durch die Systemstabilität können wir diesen momentanen Burst-Verkehr bis zu einem gewissen Grad zulassen und so den Benutzern ein besseres Benutzererlebnis bieten. Hier kommt der Token-Bucket-Algorithmus ins Spiel.

Prinzip des Token-Bucket-Algorithmus

Wie in der folgenden Abbildung dargestellt, lautet das Grundprinzip des Algorithmus: Es gibt einen Token-Bucket mit einer Kapazität von X, und alle Y-Zeiteinheiten werden Z-Token in den Bucket gelegt. Wenn die Anzahl der Token im Bucket X überschreitet, werden sie verworfen. Wenn Sie eine Anfrage bearbeiten, müssen Sie zuerst das Token aus dem Token-Bucket entfernen. Wenn Sie das Token erhalten, fahren Sie mit der Verarbeitung fort. Wenn Sie das Token nicht erhalten können, lehnen Sie die Anfrage ab.

Es ist ersichtlich, dass das Festlegen der Anzahl von X, Y und Z im Token-Bucket-Algorithmus besonders wichtig ist. Z sollte etwas größer sein als die Anzahl der Anfragen pro Y-Zeiteinheit, und das System wird sich für längere Zeit in diesem Zustand befinden. Dies weist darauf hin, dass der Datenverkehr die Erwartungen übertroffen hat und die Ursache umgehend untersucht und entsprechende Maßnahmen ergriffen werden müssen.

Redis implementiert den Token-Bucket-Algorithmus

Ich habe zuvor von einigen Programmen Token-Buckets gesehen. Die Methode zum Einfügen von Token in den Bucket besteht darin, einen Thread zu starten und die Anzahl der Token alle Y-Einheiten zu erhöhen, oder dies auszuführen regelmäßig im Timer verarbeiten. Ich bin mit dieser Methode nicht sehr zufrieden. Der eine ist die Verschwendung von Thread-Ressourcen und der andere ist die ungenaue Ausführungszeit aufgrund von Planungsproblemen. [Verwandte Empfehlungen: Redis-Video-Tutorial]

Die Methode zur Bestimmung der Anzahl der Token im Token-Bucket ist hier die Berechnung. Berechnen Sie zunächst, wie lange seit der letzten Anforderung dieser Anforderung vergangen ist und ob sie ausreicht Zeitschwelle für die Ausgabe von Token und dann, wie viele Token hinzugefügt werden und wie viele dieser Token in den Bucket gelegt werden können.

Talk ist billig!

Werfen wir einen Blick darauf, wie es in Redis implementiert wird, da es mehrere Interaktionen mit Redis erfordert, um den Durchsatz der aktuellen Begrenzungsverarbeitung zu verbessern und die Anzahl der Interaktionen zwischen dem Programm und Redis zu reduzieren. Redis wird vom Lua-Skript unterstützt. Die Ausführung des Lua-Skripts ist atomar, sodass Sie sich keine Sorgen über schmutzige Daten machen müssen.

Der Code ist ein Auszug aus FireflySoft.RateLimit, das nicht nur die normale Master-Slave-Bereitstellung von Redis, sondern auch geclusterte Redis unterstützt, sodass der Durchsatz durch horizontale Erweiterung verbessert werden kann. Um die Lektüre zu erleichtern, werden hier einige Kommentare hinzugefügt, in Wirklichkeit sind jedoch keine vorhanden.

-- 定义返回值，是个数组，包含：是否触发限流（1限流 0通过）、当前桶中的令牌数
local ret={}
ret[1]=0
-- Redis集群分片Key，KEYS[1]是限流目标
local cl_key = '{' .. KEYS[1] .. '}'

-- 获取限流惩罚的当前设置，触发限流惩罚时会写一个有过期时间的KV
-- 如果存在限流惩罚，则返回结果[1,-1]
local lock_key=cl_key .. '-lock'
local lock_val=redis.call('get',lock_key)
if lock_val == '1' then
    ret[1]=1
    ret[2]=-1
    return ret;
end

-- 这里省略部分代码

-- 获取[上次向桶中投放令牌的时间]，如果没有设置过这个投放时间，则令牌桶也不存在，此时：
-- 一种情况是：首次执行，此时定义令牌桶就是满的。
-- 另一种情况是：较长时间没有执行过限流处理，导致承载这个时间的KV被释放了，
-- 这个过期时间会超过自然投放令牌到桶中直到桶满的时间，所以令牌桶也应该是满的。
local last_time=redis.call('get',st_key)
if(last_time==false)
then
 -- 本次执行后剩余令牌数量：桶的容量- 本次执行消耗的令牌数量
    bucket_amount = capacity - amount;
    -- 将这个令牌数量更新到令牌桶中，同时这里有个过期时间，如果长时间不执行这个程序，令牌桶KV会被回收
    redis.call('set',KEYS[1],bucket_amount,'PX',key_expire_time)
    -- 设置[上次向桶中放入令牌的时间]，后边计算应放入桶中的令牌数量时会用到
    redis.call('set',st_key,start_time,'PX',key_expire_time)
    -- 返回值[当前桶中的令牌数]
    ret[2]=bucket_amount
    -- 无需其它处理
    return ret
end

-- 令牌桶存在，获取令牌桶中的当前令牌数
local current_value = redis.call('get',KEYS[1])
current_value = tonumber(current_value)

-- 判断是不是该放入新令牌到桶中了：当前时间-上次投放的时间 >= 投放的时间间隔
last_time=tonumber(last_time)
local last_time_changed=0
local past_time=current_time-last_time
if(past_time<inflow_unit)
then
 -- 不到投放的时候，直接从令牌桶中取走令牌
    bucket_amount=current_value-amount
else
 -- 需要放入一些令牌, 预计投放数量 = (距上次投放过去的时间/投放的时间间隔)*每单位时间投放的数量
    local past_inflow_unit_quantity = past_time/inflow_unit
    past_inflow_unit_quantity=math.floor(past_inflow_unit_quantity)
    last_time=last_time+past_inflow_unit_quantity*inflow_unit
    last_time_changed=1
    local past_inflow_quantity=past_inflow_unit_quantity*inflow_quantity_per_unit
    bucket_amount=current_value+past_inflow_quantity-amount
end

-- 这里省略部分代码

ret[2]=bucket_amount

-- 如果桶中剩余数量小于0，则看看是否需要限流惩罚，如果需要则写入一个惩罚KV，过期时间为惩罚的秒数
if(bucket_amount<0)
then
    if lock_seconds>0 then
        redis.call(&#39;set&#39;,lock_key,&#39;1&#39;,&#39;EX&#39;,lock_seconds,&#39;NX&#39;)
    end
    ret[1]=1
    return ret
end

-- 来到这里，代表可以成功扣减令牌，则需要更新令牌桶KV
if last_time_changed==1 then
    redis.call(&#39;set&#39;,KEYS[1],bucket_amount,&#39;PX&#39;,key_expire_time)
 -- 有新投放，更新[上次投放时间]为本次投放时间
    redis.call(&#39;set&#39;,st_key,last_time,&#39;PX&#39;,key_expire_time)
else
    redis.call(&#39;set&#39;,KEYS[1],bucket_amount,&#39;PX&#39;,key_expire_time)
end
return ret

Anhand des obigen Codes ist ersichtlich, dass der Hauptverarbeitungsprozess wie folgt aussieht:

1. Bestimmen Sie, ob eine aktuelle Grenzstrafe vorliegt. Wenn nicht, fahren Sie mit dem nächsten Schritt fort.

2. Stellen Sie fest, ob der Token-Bucket vorhanden ist. Erstellen Sie dann den Token-Bucket und geben Sie ihn zurück. Wenn er vorhanden ist, fahren Sie mit dem nächsten Schritt fort.

3. Bestimmen Sie, ob Tokens freigegeben werden müssen. Wenn nicht, werden die Tokens zuerst freigegeben und dann werden die Tokens abgezogen.

4. Bestimmen Sie die Anzahl der Token nach dem Abzug. Wenn sie kleiner als 0 ist, kehren Sie zum aktuellen Limit zurück und legen Sie die aktuelle Limitstrafe fest. Wenn sie größer oder gleich 0 ist, fahren Sie mit dem nächsten Schritt fort.

5. Aktualisieren Sie die Anzahl der Token im Bucket auf Redis.

Sie können dieses Lua-Skript in der Redis-Bibliothek einer beliebigen Entwicklungssprache einreichen und ausführen. Wenn Sie die .NET-Plattform verwenden, können Sie sich auf diesen Artikel beziehen: Verwendung der Token-Bucket-Strombegrenzung in ASP.NET Core (https://. /blog.bossma.cn/dotnet/asp-net-core-token-bucket-algorithm-of-rate-limit/).

Über FireflySoft.RateLimit

FireflySoft.RateLimit ist eine aktuelle Begrenzungsklassenbibliothek, die auf .NET Standard basiert. Ihr Kern ist einfach und leichtgewichtig und kann flexibel auf verschiedene Anforderungen aktueller Begrenzungsszenarien reagieren.

Zu den Hauptfunktionen gehören:

• Mehrere Strombegrenzungsalgorithmen: Vier integrierte Algorithmen: festes Fenster, Schiebefenster, Leaky Bucket und Token Bucket, die auch angepasst und erweitert werden können.
• Speicher mit mehreren Zählungen: Unterstützt derzeit zwei Speichermethoden: Speicher und Redis.
• Verteilungsfreundlich: Unterstützt die einheitliche Zählung verteilter Programme über Redis-Speicher.
• Flexibles Strombegrenzungsziel: Aus der Anfrage können verschiedene Daten extrahiert werden, um das Strombegrenzungsziel festzulegen.
• Unterstützung der Strombegrenzungsstrafe: Sie können den Client für einen bestimmten Zeitraum sperren, nachdem die Strombegrenzung ausgelöst wurde, und den Zugriff verweigern.
• Dynamische Regeländerung: Unterstützt die dynamische Änderung aktueller Begrenzungsregeln während der Programmausführung.
• Benutzerdefinierter Fehler: Sie können den Fehlercode und die Fehlermeldung anpassen, nachdem Sie das aktuelle Limit ausgelöst haben.
• Universelle Anwendbarkeit: Grundsätzlich kann es jedes Szenario erfüllen, das eine Strombegrenzung erfordert.

Github Open-Source-Adresse: https://github.com/bosima/FireflySoft.RateLimit/blob/master/README.zh-CN.md

Dieser Artikel wurde reproduziert von: https://juejin. cn/post /7039105263168651301

Autor: Yinghuo Architecture

Weitere Programmierkenntnisse finden Sie unter: Programmiervideo! !

Das obige ist der detaillierte Inhalt vonWie implementiert man den Token-Bucket-Algorithmus mit Redis? (mit Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!