在限流算法中有一种令牌桶算法，该算法能够应答短暂的突发流量，这对于事实环境中流量不怎么平均的状况特地有用，不会频繁的触发限流，对调用方比拟敌对。

例如，以后限度 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…