Redis实现多种限流算法

一 常见限流算法

1 固定窗口限流

每一个时间段计数器，当计数器达到阈值后拒绝，每过完这个时间段，计数器重置0，重新计数。

优点：实现简单，性能高；

缺点：明显的临界问题，限流不准确；

--KEYS[1]: 限流 key
--ARGV[1]: 阈值
--ARGV[2]: 时间窗口，计数器的过期时间
local rateLimitKey = KEYS[1];
local rate = tonumber(ARGV[1]);
local rateInterval = tonumber(ARGV[2]);

local allowed = 1;
-- 每次调用，计数器rateLimitKey的值都会加1
local currValue = redis.call('incr', rateLimitKey);

if (currValue == 1) then
--  初次调用时，通过给计数器rateLimitKey设置过期时间rateInterval达到固定时间窗口的目的
    redis.call('expire', rateLimitKey, rateInterval);
    allowed = 1;
else
--  当计数器的值（固定时间窗口内） 大于频度rate时，返回0，不允许访问
    if (currValue > rate) then
        allowed = 0;
    end
end
return allowed

2 滑动日志限流

记录每次请求时间戳，新请求到来后以该时间为时间窗口的结尾统计该时间窗口内请求数是否超过阈值。

优点：没有临界问题，限流较准确；

缺点：记录时间戳内存占用大，每次重新计算请求数，计算性能差；

--KEYS[1]: 限流器的 key
--ARGV[1]: 当前时间窗口的开始时间
--ARGV[2]: 请求的时间戳（也作为score）
--ARGV[3]: rate阈值
--ARGV[4]: 时间间隔
-- 1. 移除时间窗口之前的数据
redis.call('zremrangeByScore', KEYS[1], ARGV[1]-ARGV[4], ARGV[1])
-- 2. 统计当前元素数量
local res = redis.call('zcard', KEYS[1])
-- 3. 是否超过阈值
if (res == nil) or (res < tonumber(ARGV[3])) then
    -- 4、保存每个请求的时间搓
    redis.call('zadd', KEYS[1], ARGV[2], ARGV[2])
    return 1
else
    return 0
end

3 滑动窗口

3.1普通模式

假设n秒内最多处理b个请求。我们可以将n秒切分成每个大小为m毫秒得时间片。每m毫秒滑动一次窗口，滑动一次统计前n秒各子块请求数之和进而判断当前子块窗口阈值。如1秒内允许通过的请求是200个，但是在这里我们需要把1秒的时间分成多格，假设分成5格（格数越多，流量过渡越平滑），每格窗口的时间大小是200毫秒，每个小窗口中的数字表示在这个窗口中请求数，所以通过观察上图，可知在当前窗口（1000ms-1200毫秒）只要超过110(200-(10+20+50+10))就会被限流。

优点：实现简单，相比较固定窗口，稍微可以降低临界问题；

缺点：临界问题依然存在；

3.2 优化模式

n秒内最多处理b个请求。我们可以将n秒切分成每个大小为m毫秒得时间片，只有最新的时间片内缓存请求和时间戳，之前的时间片内只保留一个请求量的数字。这样可以大大优化存储。例如，如果我们有一个小时费率限制，我们可以为每分钟保留一个计数，并在收到计算限制的新请求时计算过去一小时内所有计数器的总和。

4 漏桶限流

每一个请求到来就会向桶中添加一定的水量，桶底有一个孔，以恒定速度不断的漏出水；当一个请求过来需要向加水时，如果漏桶剩余容积不足以容纳添加的水量，就会触发拒绝策略。漏桶为空，为并发最大情况。

优点：避免激增流量；

缺点：对激增流量反应迟钝，不能高效地利用可用的资源。因为它只在固定的时间间隔放行请求，所以在很多情况下，流量非常低，即使不存在资源争用，也无法有效地消耗资源；实现复杂，内存占用大，性能差；

--参数说明:
--KEYS[1]: 限流器的 key
--ARGV[1]: 容量，决定最大的并发量
--ARGV[2]: 漏水速率，决定平均的并发量
--ARGV[3]: 一次请求的加水量
--ARGV[4]: 时间戳
local limitInfo = redis.call('hmget', KEYS[1], 'capacity', 'passRate', 'addWater','water', 'lastTs')
local capacity = limitInfo[1]
local passRate = limitInfo[2]
local addWater= limitInfo[3]
local water = limitInfo[4]
local lastTs = limitInfo[5]

--初始化漏斗
if capacity == false then
    capacity = tonumber(ARGV[1])
    passRate = tonumber(ARGV[2])
    --请求一次所要加的水量,一定不能大于容量值的
    addWater=tonumber(ARGV[3])
    --当前储水量，初始水位一般为0
    water = addWater
    lastTs = tonumber(ARGV[4])
    redis.call('hmset', KEYS[1], 'capacity', capacity, 'passRate', passRate,'addWater',addWater,'water', water, 'lastTs', lastTs)
    return 1
else
    local nowTs = tonumber(ARGV[4])
    --计算距离上一次请求到现在的漏水量 =  流水速度 *  (nowTs - lastTs)
    local waterPass = tonumber(ARGV[2] *  (nowTs - lastTs))
    --计算当前剩余水量   =  上次水量  - 时间间隔中流失的水量
    water = math.max(tonumber(0), tonumber(water - waterPass))
    --设置本次请求的时间
    lastTs = nowTs
	--判断是否可以加水   （容量 - 当前水量 >= 增加水量，判断剩余容量是否能够容纳增加的水量）
   if capacity - water >= addWater then
        -- 加水
        water = water + addWater
        -- 更新增加后的当前水量和时间戳
        redis.call('hmset', KEYS[1], 'water', water, 'lastTs', lastTs)
        return 1
    end
    -- 请求失败
    return 0
end

5 令牌桶限流

我们以恒定速率往令牌桶里加入令牌，令牌桶被装满时，多余的令牌会被丢弃。当请求到来时，会先尝试从令牌桶获取令牌（相当于从令牌桶移除一个令牌），获取成功则请求被放行，获取失败则阻塞或拒绝请求。那么当突发流量来临时，只要令牌桶有足够的令牌，就不会被限流。

优点：可以适应激增流量，通过业务高峰和负载情况调整令牌桶速率，较大利用率下消耗请求；

缺点：实现复杂，占用内存大，性能差。

-- 令牌桶限流算法实现
-- key：限流的key
-- reqTokens：一次请求所需要的令牌数阈值
-- passRate：生成令牌的速率
-- capacity：桶的大小
-- now：当前时间
-- return：0表示限流，1表示放行
local function token_bucket(key, reqTokens, passRate, capacity, now)
    local current_tokens = tonumber(redis.call('get', key) or '0')
    local last_refreshed = tonumber(redis.call('get', key .. ':last_refreshed') or '0')
    local time_passed = math.max(now - last_refreshed, 0)
    local new_tokens = math.floor(time_passed * passRate)

    if new_tokens > 0 then
        local tokens = math.min(current_tokens + new_tokens, capacity)
        redis.call('set', key, tokens)
        redis.call('set', key .. ':last_refreshed', now)
    end

    if current_tokens < reqTokens then
        redis.call('decr', key)
        return 1
    else
        return 0
    end
end