浅析限流算法

限流的必要性

在应对秒杀，大促等高性能压力的场景时，为了保证系统的平稳运行，必须针对超过预期的流量，通过预先设定的限流规则选择性的对某些请求进行限流“熔断”。

在分布式系统中，其接口的调用来自多个系统，有的调用方可能会请求数量突增，过去争夺服务器资源，而来自其他调用方的接口请求因此来不及响应而排队等待，微服务整体的请求响应时间变长甚至超时。所以为了防止接口被过度调用，需要对每个调用方进行细粒度的访问限流。

除了对调用者的访问频率进行限制外，还需要对某些接口的访问频率进行限制，比如一些慢接口，可能因为逻辑复杂，处理时间会比较长，如果对慢接口的访问频率不加限制，过多的慢接口请求会一直占用服务的线程资源不释放，导致无法响应其他接口请求，影响微服务系统整体的吞吐量和接口响应时间，甚至引起大量的接口超时

限流背景

不同场景对于请求的限制标准是不同的，对于分布式系统，最好的一个限流标准是：并发请求数。通过限制并发处理的请求数目，可以限制任何时刻都不会有过多的请求在消耗资源。

计数器算法

通过一个计数器 counter 来统计一段时间内请求的数量，并且在指定的时间之后重置计数器。该方法实现简单，但是有临界问题。例如，假设我们限流规则为每秒钟不超过 100 次接口请求，第一个 1s 时间窗口内，100 次接口请求都集中在最后的 10ms 内，在第二个 1s 的时间窗口内，100 次接口请求都集中在最开始的 10ms 内，虽然两个时间窗口内流量都符合限流要求，但是在这两个时间窗口临界的 20ms 内会集中有 200 次接口请求，如果不做限流，集中在这 20ms 内的 200 次请求就有可能压垮系统。

基于 Redis Lua 计数限流算法的实现

-- 实现原理
-- 每次请求都将当前时间，精确到秒作为 key 放入 Redis 中，超时时间设置为 2s， Redis 将该 key 的值进行自增
-- 当达到阈值时返回错误，表示请求被限流
-- 写入 Redis 的操作用 Lua 脚本来完成，利用 Redis 的单线程机制可以保证每个 Redis 请求的原子性

-- 资源唯一标志位
local key = KEYS[1]
-- 限流大小
local limit = tonumber(ARGV[1])

-- 获取当前流量大小
local currentLimit = tonumber(redis.call('get', key) or "0")

if currentLimit + 1 > limit then
    -- 达到限流大小 返回
    return 0;
else
    -- 没有达到阈值 value + 1
    redis.call("INCRBY", key, 1)
    -- 设置过期时间
    redis.call("EXPIRE", key, 2)
    return currentLimit + 1
end

滑动窗口算法

滑动窗口算法是计数器算法的一种改进，将原来的一个时间窗口划分成多个时间窗口，并且不断向右滑动该窗口。流量经过滑动时间窗口算法整形之后，可以保证任意时间窗口内，都不会超过最大允许的限流值，从流量曲线上来看会更加平滑，可以部分解决上面提到的临界突发流量问题。对比固定时间窗口限流算法，滑动时间窗口限流算法的时间窗口是持续滑动的，并且除了需要一个计数器来记录时间窗口内接口请求次数之外，还需要记录在时间窗口内每个接口请求到达的时间点，对内存的占用会比较多。在临界位置的突发请求都会被算到时间窗口内，因此可以解决计数器算法的临界问题，比如在上文的例子中，通过滑动窗口算法整型后，第一个 1s 的时间窗口的 100 次请求都会通过，第二个时间窗口最开始的 10ms 内的 100 个请求都会被限流熔断。

但是基于时间窗口的限流算法，只能在选定的时间粒度上限流，对选定时间粒度内的更加细粒度的访问频率不做限制。

令牌桶法

令牌桶算法的流程：

接口限制 t 秒内最大访问次数为 n，则每隔 t/n 秒会放一个 token 到桶中
桶内最多存放 b 个 token，如果 token 到达时令牌桶已经满了，那么这个 token 就会被丢弃
接口请求会先从令牌桶中取 token，拿到 token 则处理接口请求，拿不到 token 则进行限流处理

因为令牌桶存放了很多令牌，那么大量的突发请求会被执行，但是它不会出现临界问题，在令牌用完之后，令牌是以一个恒定的速率添加到令牌桶中的，因此不能再次发送大量突发请求

基于 Redis Lua 令牌桶限流算法实现

-- 令牌桶限流

-- 令牌的唯一标识
local bucketKey = KEYS[1]
-- 上次请求的时间
local last_mill_request_key = KEYS[2]
-- 令牌桶的容量
local limit = tonumber(ARGV[1])
-- 请求令牌的数量
local permits = tonumber(ARGV[2])
-- 令牌流入的速率
local rate = tonumber(ARGV[3])
-- 当前时间
local curr_mill_time = tonumber(ARGV[4])

-- 添加令牌

-- 获取当前令牌的数量
local current_limit = tonumber(redis.call('get', bucketKey) or "0")
-- 获取上次请求的时间
local last_mill_request_time = tonumber(redis.call('get', last_mill_request_key) or "0")
-- 计算向桶里添加令牌的数量
if last_mill_request_time == 0 then
	-- 令牌桶初始化
	-- 更新上次请求时间
	redis.call("HSET", last_mill_request_key, curr_mill_time)
	return 0
else
	local add_token_num = math.floor((curr_mill_time - last_mill_request_time) * rate)
end

-- 更新令牌的数量
if current_limit + add_token_num > limit then
    current_limit = limit
else
	current_limit = current_limit + add_token_num
end
	redis.pcall("HSET",bucketKey, current_limit)
-- 设置过期时间
redis.call("EXPIRE", bucketKey, 2)

-- 限流判断

if current_limit - permits < 1 then
    -- 达到限流大小
    return 0
else
    -- 没有达到限流大小
	current_limit = current_limit - permits
	redis.pcall("HSET", bucketKey, current_limit)
    -- 设置过期时间
    redis.call("EXPIRE", bucketKey, 2)
	-- 更新上次请求的时间
	redis.call("HSET", last_mill_request_key, curr_mill_time)
end

漏桶法

相比于令牌桶算法，漏桶法对于取令牌的频率也有限制，要按照 t/n 的固定速率来取令牌

令牌桶算法和漏桶算法对流量的整形效果比较好，但是并不是整型效果好就越合适，对于没有提前预热的令牌桶，如果做否决式限流，会导致误杀很多请求。上述算法中当 n 比较小时，比如 50，间隔 20ms 才会向桶中放入一个令牌，而接口的访问在 1s 内可能随机性很强，这就会出现：尽管从曲线上看对最大访问频率的限制很有效，流量在细时间粒度上面都很平滑，但是误杀了很多本不应该拒绝的接口请求

限流规则的合理性

限流规则包含三个部分：时间粒度，接口粒度，最大限流值。限流规则设置是否合理直接影响到限流是否合理有效。对于限流时间粒度的选择，我们既可以选择 1 秒钟不超过 1000 次，也可以选择 10 毫秒不超过 10 次，还可以选择 1 分钟不超过 6 万次，虽然看起这几种限流规则都是等价的，但过大的时间粒度会达不到限流的效果，比如限制 1 分钟不超过 6 万次，就有可能 6 万次请求都集中在某一秒内；相反，过小的时间粒度会削足适履导致误杀很多本不应该限流的请求，因为接口访问在细时间粒度上随机性很大。所以，尽管越细的时间粒度限流整形效果越好，流量曲线越平滑，但也并不是越细越合适。对于访问量巨大的接口限流，比如秒杀，双十一，这些场景下流量可能都集中在几秒内，TPS 会非常大，几万甚至几十万，需要选择相对小的限流时间粒度。相反，如果接口 TPS 很小，建议使用大一点的时间粒度，比如限制 1 分钟内接口的调用次数不超过 1000 次

限流所需要考虑的问题

数据一致性问题

接口限流过程包含三步：

读取当前的接口访问计数 n
判断是否限流
写接口计数 n+1，if 接口限流验证通过

解决方案：

分布式锁
Redis 单线程工作模式 + Lua

超时问题

对于 Redis 的各种异常情况，我们处理起来并不是很难，catch 住，封装为统一的 exception，向上抛，或者吞掉。但是如果 Redis 访问超时，会严重影响接口的响应时间甚至导致接口响应超时，这个副作用是不能接受的。所以在我们访问 Redis 时需要设置合理的超时时间，一旦超时，判定为限流失效，继续执行接口逻辑。Redis 访问超时时间的设置既不能太大也不能太小，太大可能会影响到接口的响应时间，太小可能会导致太多的限流失效。我们可以通过压测或者线上监控，获取到 Redis 访问时间分布情况，再结合服务接口可以容忍的限流延迟时间，权衡设置一个较合理的超时时间。

文中所实现的限流算法的完整代码，可以在此GitHub查看

参考

微服务接口限流的设计与思考

G.Fukang's Blog