限流算法比较与实现

API或者微服务一般来说有个QPS或TPS的设计值，超过这个设计值响应性能会快速下降。假如服务的某个调用方在短时间内发送大量请求就会导致服务整体性能下降， 其他调用方也会受到影响。一个解决办法就是做流量控制将超过限制的调用方限流或者拒绝响应以保护服务。这就需要采用限流算法。举个例子， 某个写入接口对单个用户的操作上限是10次/秒， 假如用户操作频率大于上限就要触发限流， 限流后的处理方式可以有很多比如放到队列里排队等待执行或者直接拒绝。

本文主要介绍几种限流算法的思路以及具体实现方式，并进行对比。

Fixed-Window算法

这个算法的思路是比较简单的， 考虑一个固定长度的时间窗口，比如10s、1min、1h等， 在这个时间窗口内统计请求次数， 但请求次数超过阈值就触发限流。这个算法有两点第一时间窗口的长度是固定的并对应一个计数器， 第二每个时间窗口开始时计数器清零。

用redis结合伪码来描述这个算法如下：(实现限流10次/1s)

count = GET Key  # 获取某个用户(Key)的计数值

# 如果计数值大于10(阈值)就限流
IF count != NULL AND count > 10 THEN
    ERROR "too many requests per second"
ELSE  # 如果没有超过阈值
    value = INCR(Key)  # 计数值增加1
    # 如果计数值是1(表示这是一个新的窗口)
    # 那么设置过期时间为1s， 这里体现了窗口是固定长度的
    IF value == 1 THEN  
        EXPIRE(Key,1)  
    END
END

上面的伪码可以很好的说明算法的思路，但是实际使用的过程中却不能这样写代码， 因为INCR跟EXPIRE在这里不是一个原子操作， 假如INCR成功了但是EXPIRE失败了那么这个用户请求量超过阈值后就再也不能正常请求了。

必须采用原子操作的另外一个原因是避免竞争， 整个操作可以看做GET-then-INCR，因为服务是分布的所以多个实例会GET到相同的值导致限流失效。

为了实现原子操作可以使用redis结合lua代码：(实现限流10次/1s)

local count
local limit ＝ ARGV[1]
count = redis.call("incr",KEYS[1])
if tonumber(count) == 1 then
    redis.call("expire",KEYS[1],1])
end
return count＜limit 

这个算法的优点是：

• 实现简单
• 时间窗口固定， 每个窗口开始时计数为零，这样后面的请求不会受到之前的影响，做到了前后请求隔离

缺点：

• 上面优点中的第二点其实也是缺点， 因为两个时间窗口之间没有任何联系， 所以调用者可以在一个时间窗口的结束到下一个时间窗口的开始这个非常短的时间段内发起两倍于阈值的请求。所以Fixed-Window算法无法限制窗口间突发流量
• 无法平滑限流， 比如限流10万次/小时， 那调用者可以在1s内调用10万次而不触发限流

Fixed-window-elastic

Fixed-window-elastic算法其实是Fixed-Window的变种， 主要是为了解决Fixed-Window无法限制突发流量的缺点。

Fixed-window-elastic算法也是在时间窗口内采用计数器来实现限流，但不同的是这个算法的时间窗口不是固定时间刷新一次而是每次计数后都刷新一次。 对比一下：

• Fixed-Window算法的时间窗口固定时间过期一次， 即计数器固定时间失效
• Fixed-window-elastic算法时间窗口的过期时间在计数后顺延一次， 即计数器不会在固定时间失效

还是使用redis， 给出Python代码：(实现限流10次/1s)

count = redis_client.incr(key)
redis_client.expire(key, 1)
if count > 10:
    return "too many requests"

代码更加简单了， 但是这里incr跟expire没有做成原子操作，为什么呢？因为expire失败是小概率事件，既然每次都要expire那偶尔一次失败是不会造成灾难性后果的,对吗？

这个算法的优点是：

• 还是实现简单
• 因为窗口顺延所以可以抵御窗口间突发流量(对比Fixed-Window)

缺点:

• 优点一样是缺点， 假如限流10万次/小时, 如果某个调用者在前10分钟调用了10万零1次那么他必须再等待1小时才能发起下一次正常请求。所以没有做到前后请求隔离
• 无法平滑限流

Moving-Window

这个算法的思路是为每个调用方维护一个长度为limit的先进先出队列， 将每次请求的时间戳放到队列中， 比如阈值是10次/1s 那么limit = 10, 每次请求时取出队列头部(下标为limit -1 )的时间戳timestamp1， 假如timestamp1存在并且本次请求的时间戳减去timestamp1小于等于时间窗口长度expiry(单位为秒, 时间戳的单位也是秒)， 比如阈值是10次/1s， 那么expiry=1， 那么说明在一个时间窗口长度内请求数量超过了阈值需要限流。否则就把这次请求的时间戳放入队列中， 并更新队列过期时间。

结合redis给出lua代码：(实现限流10次/1s)

lcoal limit = 10
local entry = redis.call('lindex', KEYS[1], limit - 1)
local timestamp = tonumber(ARGV[1]) # ARGV[1]是当前请求时间戳
local expiry = 1
if entry and tonumber(entry) >= timestamp - expiry then
    return false
end
redis.call('lpush', KEYS[1], timestamp)
redis.call('ltrim', KEYS[1], 0, limit - 1)
redis.call('expire', KEYS[1], expiry)
return true

Fixed-window-elastic与Fixed-Window其实是在抵御窗口间突发流量与前后请求隔离之间做了选择, 选择了前者就必须放弃后者。 但是Moving-Window可以同时实现抵御窗口间突发流量前后请求隔离，为什么呢？

来看这个算法的两个要点：

• 每次正常请求后时间窗口的过期时间顺延一次，时间窗口是滑动的所以可以抵御窗口间突发流量
• 虽然时间窗口的长度不是固定的但是队列的长度是固定，所以可以做到前后请求隔离

这个算法的缺点是：

• 占用的内存大， 举个例子限流10万次/小时那么就需要维护一个长度为10万的队列
• 无法平滑限流
• 时间复杂度高，这是相对于Fixed-window-elastic与Fixed-Window来说的， 如果服务并发大，那么redis可能会成为瓶颈

Token Bucket

这个算法的思路很简单， 想象有一个桶用来存放令牌，并且以恒定的速率向桶内放入令牌， 每次请求时就取出一块令牌， 如果桶内没有令牌了那么就表示这个请求需要被限流。这个桶的容量是有限的， 桶满后新的令牌不会被放入。

实现这个算法的代码就有点复杂了，首先不能真的为每个用户设置一个线程去放入令牌， 这是不可能做到的。所以采用记录上次添加令牌的时间跟当前请求时间相减算出应该添加的令牌数

还是采用redis给出lua代码：

local key = KEYS[1]
local intervalPerToken = tonumber(ARGV[2])
local currentTime = tonumber(ARGV[1])
local maxToken = tonumber(ARGV[3])
local initToken = tonumber(ARGV[4])
local maxInterval = tonumber(ARGV[5])
local tokens
local bucket = redis.call("hmget", key, "lastTime", "lastToken")
local lastTime = bucket[1]
local lastToken = bucket[2]
if lastTime == false or lastToken == false then
    tokens = initToken
    redis.call('hset', key, 'lastTime', currentTime)
else
    local thisInterval = currentTime - tonumber(lastTime)
    if thisInterval > maxInterval then
        tokens = initToken
        redis.call('hset', key, 'lastTime', currentTime)
    elseif thisInterval > 0 then
        local tokensToAdd = math.floor(thisInterval / intervalPerToken)
        tokens = math.min(lastToken + tokensToAdd, maxToken)
        redis.call('hset', key, 'lastTime', lastTime + intervalPerToken * tokensToAdd)
    else
        tokens = lastToken
    end
end
if tokens == 0 then
    redis.call('hset', key, 'lastToken', tokens)
    return false
else
    redis.call('hset', key, 'lastToken', tokens - 1)
    return true
end

其中

• key
• currentTime： 当前请求时间 ms
• intervalPerToken： 每个令牌之间的间隔
• maxToken： 桶内最大的令牌数量
• initToken： 初始的令牌数量
• maxInterval: 空闲这个时间后恢复到初始令牌数量 ms

这六个参数都是运行lua脚本时传入的

注意0 < initToken <= maxToken

这算法的优点是：

• 可以抵御突发流量， 因为桶内的令牌数不会超过给定的最大值，当然在设置时initToken必须小于等于maxToken
• 可以做到前后流量隔离， 因为令牌最小值是0
• 可以做到平滑限流， 因为令牌是匀速放入的

缺点：

• 相对复杂

总结

来个表总结下：

算法	隔离流量	限制突发流量	平滑限流	时间复杂度	空间复杂度
Fixed-Window	Yes	No	No	低	低
Fixed-window-elastic	No	Yes	No	低	低
Moving-Window	Yes	Yes	No	中	高
Token Bucket	Yes	Yes	Yes	高	低

总结完发现上面的优缺点分析犯了一个错误： 没有指明具体的使用场景。 不能平滑限流一定是缺点吗？ 不能限制突发流量一定是缺点吗？能隔离前后流量一定是优点吗？

不一定！对吗？