redis限流方案分析-摩杜云开发者社区

1、固定窗口计数
固定窗口计数是指，假设我们的限流规则是：1min内最多只能访问10次，那么固定窗口就是固定了【 1min-2min】这个窗口内，只能有10次访问，相应的我们就要给这个窗口维护一个计数器。为了节省空间，其实我们不需要维护一个个窗口，只需要维护当前访问时间所在的窗口即可，以及对应的计数器，当新的访问到达了下一个窗口时，则计数器重置即可。

1.1、redis实现

用redis的话，由于有过期机制，其实设置1min过期，就可以实现计数器重置的效果了

●redis设置一个名为qps的key，val用来计数，1min过期即可

1.2、存在的问题

由于是固定窗口，那其实存在窗口临界问题，比如用户可以在【1.5-2】这段区间访问10次，【2-2.5】这段区间也访问10次，这样就变成了1min内其实可以访问20次！看起来破坏了我们的限流规则，但由于我们是固定窗口计数，到达2的时候已经重置计数器了。

2、滑动窗口计数

假设我们的限流规则是：1min内最多只能访问10次，那么滑动窗口呢就是会根据你访问进来的时间，以访问时间作为区间末尾，当前时间-1min作为区间头部，相当于窗口一直在往右滑动，这样其实就能在一定程度上解决我们刚才提到的窗口临界问题

2.1、redis实现

要获得一段区间，并且按时间排序，我们可以想到用ZSet来实现，能按区间查询出【当前访问时间-1min，当前访问时间】这段区间的计数

redis.replicate_commands()

local key = KEYS[1]
local ttl = tonumber(ARGV[1])
local max = tonumber(ARGV[2])

local time = redis.call('time')
local now = tonumber(time[1]) * 1000 + tonumber(time[2]) / 1000
local expired = now - ttl

redis.call('zremrangebyscore', key, 0, expired)

local current = tonumber(redis.call('zcard', key))
local next = current + 1

if next > max then
  return tostring(0);
else
  redis.call("zadd", key, now, now)
  redis.call("pexpire", key, ttl)
  return tostring(next)
end

3、漏桶算法

不限制流入，只限制流出的速率 -- 以一定的速率，去获取桶中的请求

水(请求)先进入到漏桶里，漏桶以一定的速度出水【从下方漏出去】(接口有响应速率)，当水流入速度过大会直接溢出【从上边移除】（访问频率超过接口响应速率)，然后就拒绝请求，可以看出漏桶算法能强行限制数据的传输速率。

但无法应对突发流量，因为流出的速率，是限死的

3.1、java实现

漏桶由于是底部有一个破洞，以固定速率流出请求，顶部用来接收请求，所以其实可以用一个双端队列来实现

1收到请求时，放入队列中【后台线程以固定的速率去removeLast，处理请求】

2若队列满了，则请求就被丢弃。

4、令牌桶算法

限制流入，不限制流出 -- 以一定速率，去生成桶中的请求【令牌】

先有一个木桶，系统按照固定速度，往桶里加入Token，如果桶已经满了就不再添加。当有请求到来时，会各自拿走一个Token，取到Token 才能继续进行请求处理，没有Token 就拒绝服务。

4.1、支持突发流量

如果一段时间没有请求时，桶内就会积累一些Token，下次一旦有突发流量，只要Token足够，也能一次处理，所以令牌桶算法的特点是_允许突发流量_

4.2、Redis实现

参数名称	含义
capacity	令牌桶容量
remain	剩余令牌数
period	时间窗口大小（秒）
quota	时间窗口内的限额
timestamp	生成令牌的时间戳（秒）

-- 为了解决redis主从模式时，分别读取主机和从机的时间问题
redis.replicate_commands()

local key = KEYS[1] -- 令牌桶标识
local capacity = tonumber(ARGV[1]) -- 最大容量
local quota = tonumber(ARGV[2]) -- 时间窗口内的限额
local period = tonumber(ARGV[3]) -- 时间窗口大小（秒）
local quantity = tonumber(ARGV[4]) or 1 -- 需要的令牌数量，默认为1
local timestamp = tonumber(redis.call('time')[1]) -- 当前时间戳

-- 第一次请求时创建令牌桶
if (redis.call('exists', key) == 0) then
    redis.call('hmset', key, 'remain', capacity, 'timestamp', timestamp)
else
    -- 计算从上次生成到现在这段时间应该生成的令牌数
    local remain = tonumber(redis.call('hget', key, 'remain'))
    local last_reset = tonumber(redis.call('hget', key, 'timestamp'))
    local delta_quota = math.floor(((timestamp - last_reset) / period) * quota)
    if (delta_quota > 0) then
        remain = remain + delta_quota
        if (remain > capacity) then
            remain = capacity
        end
        redis.call('hmset', key, 'remain', remain, 'timestamp', timestamp)
    end
end

-- 支持动态调整容量和令牌生成速率
redis.call('hmset', key, 'capacity', capacity, 'quota', quota, 'period', period);

local result = {} -- 返回的结果集
local remain = tonumber(redis.call('hget', key, 'remain'))
if (remain < quantity) then
    result = {1, capacity, remain}
else
    result = {0, capacity, remain - quantity}
    redis.call('hincrby', key, 'remain', -quantity)
end

return result

4.3、懒惰更新令牌

1记录上一次访问时间，当新的访问进来时，令牌数量+= (新访问时间-上一次访问时间)×每秒生成的令牌数量

2然后判断请求数是否大于令牌数量大于：则拒绝掉小于：则减掉相应的令牌数量即可

4.4、令牌桶与漏桶相比

●令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量；

●漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率；

●令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率；