利用Redis怎麼實現令牌桶演算法？ （附代碼）

這篇文章跟大家分享一下令牌桶演算法原理，並介紹一下利用Redis實作令牌桶演算法的方法，希望對大家有幫助！

在限流演算法中有一種令牌桶演算法，該演算法可以應對短暫的突發流量，這對於現實環境中流量不太均勻的情況特別有用，不會頻繁的觸發限流，對呼叫方比較友善。

例如，目前限制10qps，大多數情況下不會超過此數量，但偶爾會達到30qps，然後很快就會恢復正常，假設這種突發流量不會對系統穩定性產生影響，我們可以在一定程度上允許這種瞬時突發流量，從而為用戶帶來更好的可用性體驗。這就是使用令牌桶演算法的地方。

令牌桶演算法原理

如下圖所示，此演算法的基本原理是：有一個容量為X的令牌桶，每Y單位時間內將Z個令牌放入該桶。如果桶中的令牌數量超過X，那麼它將被丟棄。處理請求時，需要先從令牌桶中取出令牌，如果拿到了令牌，則繼續處理；如果拿不到令牌​​，則拒絕請求。

可以看出，在令牌桶演算法中設定X，Y和Z的數量尤其重要。 Z應該比每Y單位時間內的請求數稍大，系統將長時間處於此狀態；X是系統允許的瞬時最大請求數，且系統不應該長時間處於此狀態，否則就會頻繁觸發限流，此時表示流量出現了超預期的情況，需要及時調查原因並採取相應措施。

Redis實作令牌桶演算法

之前看過有些程式實作的令牌桶，其向桶中放入令牌的方法是啟動一個線程，每隔Y單位時間增加一次令牌數量，或在Timer中定時執行此程序。我不太滿意這種方法， 原因有二，一是浪費線程資源，二是因為調度的問題執行時間不精確。 【相關推薦：Redis影片教學】

這裡確定令牌桶中令牌數量的方法是透過計算得出，首先算出從上次請求到這次請求經過了多長時間，是否達到發令牌的時間閾值，然後增加的令牌數是多少，這些令牌能夠放到桶中的是多少。

Talk is cheap!

下邊就來看看Redis中怎麼實現的，因為涉及到多次與Redis的交互，這裡為了提高限流處理的吞吐量，減少程序與Redis的互動次數，採用了Redis支援的Lua script，Lua script的執行是原子的，所以也不用擔心出現髒數據的問題。

程式碼節選自 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。

你可以在任何一種開發語言的Redis函式庫中提交並執行這段Lua script腳本，如果你使用的是.NET平台，可以參考這篇文章：ASP.NET Core中使用令牌桶限流（https://blog.bossma.cn/dotnet/asp-net-core-token-bucket-algorithm-of-rate-limit/） 。

關於FireflySoft.RateLimit

FireflySoft.RateLimit 是一個基於.NET Standard 的限流類別庫，其核心簡單輕巧，能夠靈活應對各種需求的限流場景。

其主要特點包括：

• 多種限流演算法：內建固定視窗、滑動視窗、漏桶、令牌桶四種演算法，還可自訂擴充。
• 多種計數儲存：目前支援記憶體、Redis兩種儲存方式。
• 分散式友善：透過Redis儲存支援分散式程式統一計數。
• 限流目標靈活：可以從請求中提取各種資料用於設定限流目標。
• 支援限流懲罰：可以在客戶端觸發限流後鎖定一段時間不允許其存取。
• 動態變更規則：支援程式執行時動態變更限流規則。
• 自訂錯誤：可以自訂觸發限流後的錯誤碼和錯誤訊息。
• 普適性：原則上可以滿足任何需要限流的場景。

Github開源位址：https://github.com/bosima/FireflySoft.RateLimit/blob/master/README.zh-CN.md

##本文轉載自：https://juejin.cn/post/7039105263168651301

作者：螢火架構

#更多程式相關知識，請造訪：程式影片！ ！

以上是利用Redis怎麼實現令牌桶演算法？ （附代碼）的詳細內容。更多資訊請關注PHP中文網其他相關文章！