在限流算法中有一种令牌桶算法,该算法能够应答短暂的突发流量,这对于事实环境中流量不怎么平均的状况特地有用,不会频繁的触发限流,对调用方比拟敌对。
例如,以后限度 10qps,大多数状况下不会超过此数量,但偶然会达到 30qps,而后很快就会恢复正常,假如这种突发流量不会对系统稳定性产生影响,咱们能够在肯定水平上容许这种刹时突发流量,从而为用户带来更好的可用性体验。这就是应用令牌桶算法的中央。
令牌桶算法原理
如下图所示,该算法的基本原理是:有一个容量为 X 的令牌桶,每 Y 单位工夫内将 Z 个令牌放入该桶。如果桶中的令牌数量超过 X,那么它将被抛弃。解决申请时,须要先从令牌桶中取出令牌,如果拿到了令牌,则持续解决;如果拿不到令牌,则拒绝请求。
能够看出,在令牌桶算法中设置 X,Y 和 Z 的数量尤为重要。Z 应该比每 Y 单位工夫内的申请数稍大,零碎将长时间处于此状态;X 是零碎容许的刹时最大申请数,并且零碎不应该长时间处于此状态,否则就会频繁触发限流,此时表明流量呈现了超预期的状况,须要及时考察起因并采取相应措施。
Redis 实现令牌桶算法
之前看过有些程序实现的令牌桶,其向桶中放入令牌的办法是启动一个线程,每隔 Y 单位工夫减少一次令牌数量,或者在 Timer 中定时执行这一过程。我不太称心这种办法,起因有二,一是节约线程资源,二是因为调度的问题执行工夫不准确。
这里确定令牌桶中令牌数量的办法是通过计算得出,首先算出从上次申请到这次申请通过了多长时间,是否达到发令牌的工夫阈值,而后减少的令牌数是多少,这些令牌可能放到桶中的是多少。
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 中应用令牌桶限流。
对于 FireflySoft.RateLimit
FireflySoft.RateLimit 是一个基于 .NET Standard 的限流类库,其内核简略笨重,可能灵便应答各种需要的限流场景。
其次要特点包含:
- 多种限流算法:内置固定窗口、滑动窗口、漏桶、令牌桶四种算法,还可自定义扩大。
- 多种计数存储:目前反对内存、Redis 两种存储形式。
- 分布式敌对:通过 Redis 存储反对分布式程序对立计数。
- 限流指标灵便:能够从申请中提取各种数据用于设置限流指标。
- 反对限流惩办:能够在客户端触发限流后锁定一段时间不容许其拜访。
- 动静更改规定:反对程序运行时动静更改限流规定。
- 自定义谬误:能够自定义触发限流后的错误码和谬误音讯。
- 普适性:原则上能够满足任何须要限流的场景。
Github 开源地址:https://github.com/bosima/Fir…