限流策略

发表于 |

基于计数器的单机限流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//限流计数器
private static AtomicLong counter = new AtomicLong();
//限流阈值
private static final long counterMax = 500;
//业务处理方法
public void invoke(Request request) {
    try {
        //请求过滤
        if (counter.incrementAndGet() > counterMax) {
            return;
        }
        //业务逻辑
        doBusiness(request);
    } catch (Exception e) {
        //错误处理
        doException(request,e);
    } finally {
        counter.decrementAndGet();
    }
}

优点：代码简洁，操作方便
缺点：先到先得，先到的请求可执行概率为100%，后到的请求可执行概率小一些，每个请求获得执行的机会是不平等的。

基于随机数的单机限流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//获取随机数
private static ThreadLocalRandom ptgGenerator = ThreadLocalRandom.current();
//限流百分比，允许多少流量通过此业务，这里限定为10%
private static final long ptgGuarder = 10;
//业务处理方法
public void invoke(Request request) {
    try {
        //请求进入，获取百分比
        int currentPercentage = ptgGenerator.nextInt(1, 100);
        if (currentPercentage <= ptgGuarder) {
            //业务处理
            doBusiness(request);
        } else {
            return;
        }
    } catch (Exception e) {
        //错误处理
        doException(request, e);
    }
}

优点：代码简洁，操作简便，每个请求可执行的机会是平等的。
缺点：不适合应用突增的流量。

基于固定、滑动时间窗口的单机限流

问题：
1、粒度太大了，不均匀，针对1秒以下的，没法辨析。
我们能不能把粒度拆细了，1秒拆成10个100毫秒。每一个100毫秒有一个计数器。了解TCP/IP的应该知道，TCP/IP为了增加传输速度和控制传输速度，有个叫“滑动窗口协议”。
就算拆得再细，也无法解决匀速限制速度的问题。

2、临界点问题
而且还有个临界点问题，假如，一秒限制10个请求，在第1秒和第2秒之间，第1秒后半段时间10个请求，第2秒前半段10个请求，那第1秒后半段+第2秒前半段时间组成的一秒钟里就有20个请求，没有起到限速的作用。

基于漏桶算法的单机限流

漏桶作为计量工具时，可以用于流量整型和流量控制，网上大多数关于漏桶算法的描述如下:

  • 一个固定容量的漏桶，按照常量固定速率流出水滴
  • 如果桶是空的，则不需流出水滴
  • 可以以任意速率流入水滴到漏桶
  • 如果流入水滴超出了桶的容量，则流入的水滴溢出了(被丢弃)，而漏桶容量是不变的

漏桶算法思路很简单，水(数据或者请求)先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。

漏桶它的主要目的是控制注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供了一个稳定的流量。漏桶可以看做是一个带有常量服务时间的单服务器队列，如果漏桶(包缓存)溢出，那么数据包会被丢弃。

在某些情况下，漏桶算法不能够有效使用网络资源，因为漏桶的漏出速率是固定的参数，所以，即使网络中不存在资源冲突(没有发生拥塞)，漏桶算法也不能使某一个单独的流突发到端口速率。因此，对于存在突发特性的流量来说缺乏效率，而令牌桶算法则能够满足这些具有突发特性的流量。

通常，漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制

优缺点:

  1. 漏桶算法优点很明显，简单、高效，能恰当拦截容量外的暴力流量。
  2. 缺点也明显，无法对流量做频率处理。比如:桶大小设置范围内，进行并发攻击依然能产生大流量并发效果，桶容量又不可以设置的过小，否则容易卡死正常用户。

基于令牌桶算法的单机限流

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。桶中最多存放一定数量的令牌,当桶满时，新添加的令牌被丢弃或拒绝

令牌桶的另一个好处是可以方便的改变速度，一旦需要提高速率，则按需提高放入桶中的令牌的速率。一般会定时(比如100毫秒)往桶中增加一定数量的令牌，有些变种的算法则实时的计算应该增加的令牌的数量。

优缺点:

  1. 令牌桶的另外一个好处是可以方便的改变速度。 一旦需要提高速率，则按需提高放入桶中的令牌的速率。
  2. 可以限制总请求大小，还限制平均频率大小；
  3. 还是容易导致误判等问题
  4. 对比基于时间窗口的限流算法，令牌桶和漏桶算法对流量整形效果比时间窗口算法要好很多，但是并不是整形效果越好就越合适，对于没有提前预热的令牌桶，如果做否决式限流，会导致误杀很多请求。上述算法中当 n 比较小时，比如 50，间隔 20ms 才会向桶中放入一个令牌，而接口的访问在 1s 内可能随机性很强，这就会出现：尽管从曲线上看对最大访问频率的限制很有效，流量在细时间粒度上面都很平滑，但是误杀了很多本不应该拒绝的接口请求。

令牌桶算法和漏桶算法比较

令牌桶和漏桶比较:

  • 针对突发性流量
    • 令牌桶可以限制平均流入速率，只要有令牌，允许一定程度的突发流量
    • 漏桶流入速率任意，流出速率常量，即平滑突发流入速率

它们之间最主要的差别在于：漏桶算法能够强行限制数据的传输速率，而令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的上限，因此它适合于具有突发特性的流量。

基于redis lua的分布式限流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
--限流的key
local key = 'limitkey'..KEYS[1]

--累加请求数
local val = tonumber(redis.call('get', key) or 0)

--限流阈值
local threshold = tonumber(ARGV[1])

if  val>threshold then
    --请求被限
    return 0
else
    --递增请求数
    redis.call('INCRBY', key, "1")
    --5秒后过期
    redis.call('expire', key, 5)
    --请求通过
    return 1
end

优点：集群整体流量控制，防止雪崩效应
缺点：需要引入额外的redis组件，且要求redis支持lua脚本。

参考

浅谈限流算法
限流:漏桶算法和令牌桶算法
https://mp.weixin.qq.com/s/9cDIMBx3neN2wz0LNxBeRA
https://juejin.im/entry/5be00d916fb9a049f153a70e
https://zhuanlan.zhihu.com/p/47863288
https://www.infoq.cn/article/microservice-interface-rate-limit