這篇文章跟大家分享一下令牌桶演算法原理,並介紹一下利用Redis實作令牌桶演算法的方法,希望對大家有幫助!
在限流演算法中有一種令牌桶演算法,該演算法可以應對短暫的突發流量,這對於現實環境中流量不太均勻的情況特別有用,不會頻繁的觸發限流,對呼叫方比較友善。
例如,目前限制10qps,大多數情況下不會超過此數量,但偶爾會達到30qps,然後很快就會恢復正常,假設這種突發流量不會對系統穩定性產生影響,我們可以在一定程度上允許這種瞬時突發流量,從而為用戶帶來更好的可用性體驗。這就是使用令牌桶演算法的地方。
如下圖所示,此演算法的基本原理是:有一個容量為X的令牌桶,每Y單位時間內將Z個令牌放入該桶。如果桶中的令牌數量超過X,那麼它將被丟棄。處理請求時,需要先從令牌桶中取出令牌,如果拿到了令牌,則繼續處理;如果拿不到令牌,則拒絕請求。
可以看出,在令牌桶演算法中設定X,Y和Z的數量尤其重要。 Z應該比每Y單位時間內的請求數稍大,系統將長時間處於此狀態;X是系統允許的瞬時最大請求數,且系統不應該長時間處於此狀態,否則就會頻繁觸發限流,此時表示流量出現了超預期的情況,需要及時調查原因並採取相應措施。
之前看過有些程式實作的令牌桶,其向桶中放入令牌的方法是啟動一個線程,每隔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('set',lock_key,'1','EX',lock_seconds,'NX') end ret[1]=1 return ret end -- 来到这里,代表可以成功扣减令牌,则需要更新令牌桶KV if last_time_changed==1 then redis.call('set',KEYS[1],bucket_amount,'PX',key_expire_time) -- 有新投放,更新[上次投放时间]为本次投放时间 redis.call('set',st_key,last_time,'PX',key_expire_time) else redis.call('set',KEYS[1],bucket_amount,'PX',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 是一個基於.NET Standard 的限流類別庫,其核心簡單輕巧,能夠靈活應對各種需求的限流場景。
其主要特點包括:
Github開源位址:https://github.com/bosima/FireflySoft.RateLimit/blob/master/README.zh-CN.md
##本文轉載自:https://juejin.cn/post/7039105263168651301
作者:螢火架構
#更多程式相關知識,請造訪:程式影片! !
以上是利用Redis怎麼實現令牌桶演算法? (附代碼)的詳細內容。更多資訊請關注PHP中文網其他相關文章!