实现了滑动窗口，固定窗口，令牌桶，漏桶四种限流算法，并且支持各种扩展和修改，源码简单易上手。
Gitee：https://gitee.com/sir-tree/rate-limiter-spring-boot-starter
一、令牌桶算法—入桶量限制
在客户端请求打过来的时候，会去桶里拿令牌，拿到就请求成功，拿不到不好意思，服务器拒绝服务。
关键点
- 桶有多大？您定😊
- 桶里的令牌一开始有多少？您定😊
- 桶啥时候补充令牌？您定😊
- 补充多少令牌？您定😊
在想好以上关键点后，我想你已经明白了。
主要步骤
请求打过来
- 看一下是否到补充桶的时候了，没到就到第2步，到了就补充完后再继续第2步
- 看一下桶里有没有令牌，有就拿走，没有就不好意思，服务器拒绝服务。
扩展：加个黑名单
请求打过来
- 看一下在不在黑名单，在就拒绝服务，不在，就进行第2步
- 看一下是否到补充桶的时候了，没到就到第2步，到了就补充完后再继续第3步
- 看一下桶里有没有令牌，有就拿走，没有就不好意思，加黑名单。
Lua实现
-- 参数初始化
local key = KEYS[1]
local maxCapacity = tonumber(ARGV[1]) -- <= 桶有多大/桶里的令牌一开始有多少 我写成一样的了
local fill = tonumber(ARGV[2]) -- <= 补充多少令牌
local now = tonumber(ARGV[3])
local duration = tonumber(ARGV[4]) -- <= 桶啥时候补充令牌
local blackKey = key..'-black'
local blackDuration = tonumber(ARGV[5]) -- <= 黑名单多久后放开
local expire = math.ceil(now / fill) * duration
-- 黑名单
local blackValue = redis.call('get', blackKey)
if blackValue then
return -1;
end
-- 当前值
local kValue = redis.call('get', key)
-- 第一次
if not kValue then
-- 当前消耗#刷新时间#容量
kValue = table.concat({'0', tostring(now + duration), tostring(maxCapacity)}, '#')
end
-- 解析
local parts = {}
for part in string.gmatch(kValue, "[^#]+") do
table.insert(parts, part)
end
local value = tonumber(parts[1])
local refresh = tonumber(parts[2])
local capacity = tonumber(parts[3])
local fillTimes = math.floor((now - refresh) / duration) + 1
-- 刷新桶令牌
if now >= refresh then
value = 0
-- 补充
capacity = capacity + fill * fillTimes
-- 最多补满
if capacity > maxCapacity then
capacity = maxCapacity
end
-- 刷新时间
refresh = now + duration
end
-- 拿完
if value == capacity then
-- 加入黑名单
if blackDuration > 0 then
redis.call('set', blackKey, '_', 'PX', blackDuration)
redis.call('del', key)
end
return -1
end
-- 期间
value = value + 1
kValue = table.concat({tostring(value), tostring(refresh), tostring(capacity)}, '#')
redis.call('set', key, kValue, 'PX', expire)
return capacity - value
二、 漏桶算法—出桶量限制
在客户端请求打过来的时候，会去桶里放令牌（有唯一标识），放成功后尝试把自己放的令牌拿走，拿不走就不断的尝试拿，直到拿走；但如果放失败了，不好意思，服务器拒绝服务。
关键点
- 桶有多大？您定😊
- 哪些令牌可以被自己拿走？您定不了了😎，我定，这里有两个方案，公平的方案：每个请求只能拿自己放的令牌，先放进来的令牌可以先被拿走，不公平的方案是：拿谁放的都可以，大家一起抢，谁抢到算谁的
- 多长时间内最多可以拿走多少个令牌？‘多长时间’您定😊，‘最多可拿走’您定😊
在想好以上关键点后，我想你已经明白了。
主要步骤
请求打过来
- 放令牌成功就执行第2步，但桶满了放不了了，不好意思，服务器拒绝服务
- 不断尝试拿令牌（两种方案实现） –不断尝试拿！！不断尝试拿！！！不断尝试拿！！！
实现
-- 参数初始化
local key = KEYS[1]
local capacity = tonumber(ARGV[1]) -- <= 桶有多大
local pass = tonumber(ARGV[2]) -- <= 多长时间内最多可以拿走多少个令牌 -- 最多可以拿走多少个令牌
local duration = tonumber(ARGV[3]) -- <= 多长时间内最多可以拿走多少个令牌 -- 多长时间内
local fair = tonumber(ARGV[4]) -- <= 公平/不公平方案
local queueId = tonumber(ARGV[5]) -- <= 哪些令牌可以被自己拿走
local exceedQueueId = -(capacity + 1)
local legacyPassKey = key..'-legacyPass'
local queueKey = key..'-queue'
-- redis初始化
local qMembers = redis.call('lRange', queueKey, 0, -1)
local lpValue = redis.call('get', legacyPassKey)
local lpExpire = redis.call('pTtl', legacyPassKey)
local function min(q)
if #q == 0 then
return 0
end
local mv = tonumber(q[1])
local tmp = mv
for i = 2, #q do
tmp = tonumber(q[i])
if tmp < mv then
mv = tmp
end
end
return mv
end
local function addQueue(qId)
if qId ~= exceedQueueId then
return qId
end
if #qMembers == capacity then
return exceedQueueId
end
qId = min(qMembers) - 1
redis.call('rPush', queueKey, qId)
table.insert(qMembers, tostring(qId))
return qId
end
-- 1 删除成功，0删除失败
local function delQueue()
-- >= 队列不为空，队列有元素
if #qMembers > 0 then
-- 公平
if fair > 0 then
-- 第一个不是当前请求
if tonumber(qMembers[1]) ~= queueId then
return 0
else
redis.call('lPop', queueKey)
table.remove(qMembers, 1)
end
else -- 不公平
redis.call('lRem', queueKey, 1, queueId)
for i = #qMembers, 1, -1 do
if tostring(qMembers[i]) == queueId then
table.remove(qMembers, i)
end
end
end
end
-- 队列无元素，或队列第一个是
return 1
end
-- 第一次/到刷新时间-刷新pass
if lpExpire <= 0 then
local update = delQueue()
if update == 1 then
pass = pass - 1
else
queueId = addQueue(queueId)
end
redis.call('set', legacyPassKey, pass, 'PX', duration)
if update == 1 then
return pass
end
return queueId
end
lpValue = tonumber(lpValue)
-- 如果lpValue >= 0 表示当前不需要等待
if lpValue - 1 >= 0 then
if delQueue() == 0 then
return queueId
end
lpValue = lpValue - 1
redis.call('set', legacyPassKey, lpValue, 'PX', lpExpire)
return lpValue
else
return addQueue(queueId)
end
三、 固定窗口算法
时间窗口，随时间变化，比如1秒10个，即时间窗口大小为1秒，窗口内最多允许10个请求，随时间变化，如0 ~ 1秒有一个时间窗口，1 ~ 2秒内又是一个时间窗口 … 且每个窗口内最多有10个请求，超过的就放弃。
关键点
- 时间窗口内允许最多多少个请求？您定😊
- 时间窗口大小是多大？您定😊
在想好以上关键点后，我想你已经明白了。
主要步骤
请求打过来
- 看一下还剩下多少个位置，不剩就服务器拒绝服务，否则成功
Lua实现
local key = KEYS[1]
local limit = tonumber(ARGV[1]) -- <= 时间窗口内允许最多多少个请求
local window = tonumber(ARGV[2]) -- <= 时间窗口大小是多大
local expire = redis.call('pTtl', key)
local kValue = redis.call('get', key)
if expire <= 0 then
redis.call('set', key, 1, 'PX', window)
return 1 -- 通过
end
kValue = tonumber(kValue)
if kValue == limit then
return 0 -- 限流
else
redis.call('set', key, kValue + 1, 'PX', expire)
return 1 -- 通过
end
四、滑动窗口
和固定窗口类似，只是这个窗口是动的，怎么动？每次请求过来的时候，就以当前请求为窗口的右端点，而不是固定窗口那样固定。
Lua实现
local key = KEYS[1]
local limit = tonumber(ARGV[1]) -- <= 时间窗口内允许最多多少个请求
local window = tonumber(ARGV[2]) -- <= 时间窗口大小是多大
local now = tonumber(ARGV[3]) -- <= 就以当前请求为窗口的右端点
local start = now - window
redis.call('zRemRangeByScore', key, 0, start) -- 移除上一个窗口期之前的数据
local size = redis.call('zCard', key)
if size == limit then
return 0 -- 限制
else
redis.call('zAdd', key, now, now)
redis.call('pExpire', key, window + 1000) -- 窗口期 + 1秒后过期
return 1 -- 通过
end
讨论
- 固定窗口问题：比如窗口是1秒最多10个，当流量在第一个窗口最后100毫秒满10个，且在第二个窗口前100毫秒满10个时，这200毫秒可以看做1秒内，也就是一个窗口，这就有问题（流量激增）…
- 令牌桶问题：不能平稳的处理请求…
- 滑动窗口：请求打满后，必须要延迟等到下一个窗口…
- 漏桶：突发流量会有一堆被抛弃的…
