Redis を使用してトークン バケット アルゴリズムを実装するにはどうすればよいですか? (コード付き)

この記事では、トークン バケット アルゴリズムの原理を説明し、Redis を使用してトークン バケット アルゴリズムを実装する方法を紹介します。

電流制限アルゴリズムの中には、短期間のトラフィックのバーストに対処できるトークン バケット アルゴリズムがあります。これは、トラフィックが大量に発生する実際の環境で特に役立ちます。あまり均一ではないため、現在の制限が頻繁にトリガーされることはなく、呼び出し側にとってはより親切です。

たとえば、現在の制限は 10qps です。ほとんどの場合、この量を超えることはありませんが、場合によっては 30qps に達し、すぐに通常に戻ります。このトラフィックのバーストは発生しないと想定されています。システムの安定性に影響を与えるため、この瞬間的なバースト トラフィックをある程度まで許容できるため、ユーザーにより良い可用性エクスペリエンスが提供されます。ここでトークン バケット アルゴリズムが登場します。

トークン バケット アルゴリズムの原理

下の図に示すように、アルゴリズムの基本原理は次のとおりです。このバケットに入る容量を持つトークン バケットが存在します。バケット内のトークンの数が X を超えると、バケットは破棄されます。リクエストを処理するときは、まずトークン バケットからトークンを削除する必要があります。トークンを取得した場合は処理を続行し、トークンを取得できない場合はリクエストを拒否します。

トークン バケット アルゴリズムでは、X、Y、Z の数を設定することが特に重要であることがわかります。 Z が単位時間当たりのリクエスト数 Y よりわずかに大きく、この状態が長時間続くことは、予想を超えるトラフィックが発生していることを示しており、早急に原因を究明し、対策を講じる必要があります。

Redis はトークン バケット アルゴリズムを実装します

以前、いくつかのプログラムでトークン バケットが実装されているのを見てきましたが、トークンをバケットに入れる方法はスレッドを開始することです。 Y単位時間ごとのトークン数を取得するか、Timerで定期的にこの処理を実行します。この方法にはあまり満足していませんが、理由は 2 つあり、1 つはスレッド リソースの無駄であり、もう 1 つはスケジュールの問題により実行時間が不正確になることです。 [関連する推奨事項: Redis ビデオ チュートリアル ]

トークン バケット内のトークンの数を決定する方法は計算によって行われます。まず、最後のリクエストから今回のリクエストまでにどれくらいの時間が経過したかを計算します。長期間にわたって、トークン発行の時間しきい値に達したかどうか、追加されるトークンの数、およびこれらのトークンをバケットに入れることができる数。

トークは安い!

それでは、Redis での実装方法を見てみましょう。Redis との複数のやり取りが含まれるため、ここでは電流制限処理のスループットを向上させ、プログラムを削減するために、 Redis インタラクションの数は、Redis がサポートする Lua スクリプトを使用します。Lua スクリプトの実行はアトミックであるため、ダーティ データについて心配する必要はありません。

コードは FireflySoft.RateLimit から抜粋したものですが、通常の Redis のマスター/スレーブ展開だけでなく、クラスター化された Redis にも対応しているため、水平拡張によるスループットの向上が可能です。読みやすいように、ここにはいくつかのコメントが追加されていますが、実際にはコメントはありません。

-- 定义返回值，是个数组，包含：是否触发限流（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

上記のコードから、主な処理プロセスは次のとおりであることがわかります:

1. 現在の制限ペナルティがあるかどうかを確認します。ある場合は、直接戻ります。ない場合は、進みます。次のステップへ。

2. トークン バケットが存在するかどうかを確認します。存在しない場合は、まずトークン バケットを作成し、トークンを差し引いて返します。存在する場合は、次のステップに進みます。

3. トークンを発行する必要があるかどうかを決定します。発行しない場合は、トークンが直接差し引かれます。必要な場合は、最初にトークンが発行されてから、トークンが差し引かれます。

4. 控除後のトークンの数を決定します。0 未満の場合は、現在の制限を返し、現在の制限ペナルティを設定します。0 以上の場合は、次のステップに進みます。 。

5. バケット内のトークンの数を Redis に更新します。

この Lua スクリプトは、任意の開発言語の Redis ライブラリで送信して実行できます。.NET プラットフォームを使用している場合は、この記事を参照してください: ASP.NET Core のトークン バケット レートの使用制限 (https://blog.bossma.cn/dotnet/asp-net-core-token-bucket-algorithm-of-rate-limit/)。

FireflySoft.RateLimit について

FireflySoft.RateLimit は、.NET Standard に基づいた電流制限クラス ライブラリであり、そのコアはシンプルかつ軽量であり、柔軟に変更できます。さまざまな需要電流制限シナリオに対応します。

その主な機能は次のとおりです:

• 複数の電流制限アルゴリズム: 固定ウィンドウ、スライディング ウィンドウ、リーキー バケット、トークン バケットの 4 つのアルゴリズムが組み込まれており、カスタマイズおよび拡張も可能です。
• 複数のカウント ストレージ: 現在、メモリと Redis の 2 つのストレージ方法をサポートしています。
• 分散型フレンドリー: Redis ストレージを介して分散型プログラムの統合カウントをサポートします。
• 柔軟な電流制限ターゲット: 電流制限ターゲットを設定するリクエストからさまざまなデータを抽出できます。
• 電流制限ペナルティのサポート: 電流制限をトリガーした後、一定期間クライアントをロックし、アクセスを許可しないことができます。
• 動的変更ルール: プログラムの実行中に動的に変更される電流制限ルールをサポートします。
• カスタマイズされたエラー: 電流制限をトリガーした後、エラー コードとエラー メッセージをカスタマイズできます。
• 汎用性: 原理的には、電流制限が必要なあらゆるシナリオに対応できます。

#Github オープンソース アドレス: https://github.com/bosima/FireflySoft.RateLimit/blob/master/README.zh-CN.md

この記事は、https://juejin.cn/post/7039105263168651301

著者: Yinghuo Architecture

プログラミング関連の知識の詳細については、次のサイトを参照してください。

プログラミングビデオ ! ！

以上がRedis を使用してトークン バケット アルゴリズムを実装するにはどうすればよいですか? (コード付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。