限流算法

发表于 | 分类于
字数统计: 869

限流算法

固定窗口算法

基于固定时间窗口的限流算法是非常简单的。首先需要选定一个时间起点，之后每次接口请求到来都累加计数器。如果在当前时间窗口内，累加访问次数超过限流值，则限流熔断拒绝接口请求。当进入下一个时间窗口之后，计数器清零重新计数。

这种算法的缺点在于：限流策略过于粗略，无法应对两个时间窗口临界时间内的突发流量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//固定窗口示例
//延时计算，在访问时再计算
public boolean tryAcquire() throws InternalErrorException {
    int updatedCount = currentCount.incrementAndGet();
    if (updatedCount <= limit) {
        return true;
    }

    try {
        if (lock.tryLock(TRY_LOCK_TIMEOUT, TimeUnit.MILLISECONDS)) {
            try {
                if (stopwatch.elapsed(TimeUnit.MILLISECONDS) > TimeUnit.SECONDS.toMillis(1)) {
                    currentCount.set(0);
                    stopwatch.reset();
                }
                updatedCount = currentCount.incrementAndGet();
                return updatedCount <= limit;
            } finally {
                lock.unlock();
            }
        } else {
            throw new InternalErrorException("tryAcquire() wait lock too long:" + TRY_LOCK_TIMEOUT + "ms");
        }
    } catch (InterruptedException e) {
        throw new InternalErrorException("tryAcquire() is interrupted by lock-time-out.", e);
    }
}

滑动窗口算法

滑动时间窗口算法是对固定时间窗口算法的一种改进，流量经过滑动时间窗口算法整形之后，可以保证任意时间窗口内，都不会超过最大允许的限流值。对比固定时间窗口限流算法，滑动时间窗口限流算法的时间窗口是持续滑动的，并且除了需要一个计数器来记录时间窗口内接口请求次数之外，还需要记录在时间窗口内每个接口请求到达的时间点，对内存的占用会比较多。

实现上可以基于循环队列实现。

令牌桶算法

上面介绍了两种基于时间窗口的限流算法。这两种限流算法都无法应对细时间粒度的突发流量，对流量的整形效果在细时间粒度上不够平滑。

令牌桶算法试一种更滑平滑的限流算法。令牌桶算法大致思路：

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

漏桶算法

漏桶算法对流量的整形效果更加好，流量更加平滑，任何突发流量都会被限流。漏桶算法对于取令牌的频率也有限制，要按照 t/n 固定的速度来取令牌。

令牌桶和漏桶算法比较适合阻塞式限流，比如一些后台 job 类的限流，超过了最大访问频率之后，请求并不会被拒绝，而是会被阻塞到有令牌后再继续执行。

基于时间窗口的算法比较适合否决式限流，比如线上接口这种对响应时间比较敏感的限流场景。

分布式限流

基于Redis+Lua实现集群限流。不需要加锁，Redis+Lua会以原子的方式运行。

1
2
3
4
5
6
7
8
9
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local current = tonumber(redis.call('incr', key))
if current > limit then
   return 0
elseif current == 1 then
   redis.call('expire', key, '1')
end
return 1

Reference

https://mp.weixin.qq.com/s?__biz=MzI4MTY5NTk4Ng==&mid=2247488993&idx=1&sn=4b9d5deedd0e626c456744f04b499bbb&source=41#wechat_redirect