限流算法

发表于 | 分类于 | 阅读次数

在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流。

在高并发系统中，限流通常指的是对请求进行限速，一旦达到系统的限速规则（比如系统限制的请求速度），则可以采取一些措施来完成限制流量的目的：

  • 拒绝处理（友好提示或者跳转到错误页面）
  • 延迟处理（排队或等待，比如秒杀系统）
  • 服务降级（返回默认的兜底数据）

一、限流算法

常见的限流算法有：计数器、漏桶和令牌桶算法。

比如每秒钟最多只有100个请求可以访问接口：

1、计数器-固定窗口

固定窗口算法简单粗暴。大致原理是：维护一个单位时间内的计数值，每次请求通过，计数值加 1，当计数值超过限流阈值时，单位时间内的其他请求就会被限流。一个周期的单位时间结束，计数器会清零，流量恢复正常，进入下一个周期。

1
2
3
4
5
6
7
8
9
//有一个「固定周期」会触发的定时器将数值清零。
private AtomicInteger reqCount = new AtomicInteger(0);
private final int limit = 100; // 时间窗口内最大请求数
public boolean counterOfFixedTime() {
    if (reqCount.get() >= limit) {
        return false;
    }
    return reqCount.incrementAndGet() <= limit;
}

固定窗口的缺点 ：计数器限流只要一定时间内的总请求数超过设定的阀值则进行限流，是一种简单粗暴的总数量限流，而不是平均速率限流。

临界问题：比如在 0:59 时，瞬间请求 100 次，并且在 1:00 请求 100 次，那么这个用户在 1 秒内请求了 200 次，但在算法中能通过。用户可以在间隔处突发请求，而瞬间超过我们设置的速率限制，用户可能通过算法漏洞击垮我们的应用。

2、计数器-滑动窗口

滑动窗口其实就是对固定窗口做了进一步的细分，将原先的粒度切的更细。比如某个服务最多只能每秒钟处理 100 个请求。我们可以设置一个 1 秒钟的滑动窗口，窗口中有 10 个格子，每个格子 100 毫秒，每 100 毫秒移动一次。然后统计的时间范围随着时间的推移同步后移。

每 100 毫秒移动一次，每次移动都需要记录当前服务请求的次数。

内存中需要保存 10 次的次数。可以用数据结构 LinkedList 来实现。格子每次移动的时候判断一次，当前访问次数和 LinkedList 中最后一个相差是否超过 100，如果超过就需要限流了。

细粒度的突发情况：滑动时间窗口无法应对细时间粒度（某个时间）的突发性请求，示例：当 t_1 = 1ms，来了 50 个请求，窗口有 50 个时间点了，中间没有请求，t_3 = 900 ms，又来了 100 个请求，只能加入 50 个。

时间区间的精度越高，算法所需的空间容量就越大。

3、漏桶算法（Leaky Bucket)

任意速率接收请求；固定速率处理请求；桶容量固定，满了则进行流量干预。

假设每秒请求数限制为 100，那么设置桶的容量为 100，1 秒漏完，流速为 100 request/s（0.1 request/ms），默认容量为 0。

漏桶算法多使用队列实现，服务的请求会存到队列中，服务的提供方则按照固定的速率从队列中取岀请
求并执行，过多的请求则放在队列中排队或直接拒绝。

缺点：瓶颈会在漏出的速度，可能会拖慢整个系统，且不能有效地利用系统的资源。

当短时间内有大量的突发请求时，即便此时服务器没有任何负载，每个请求也都得在队列中等待一段时间才能被响应。

4、令牌桶算法

令牌桶原理：以一个恒定的速度往桶里放令牌，桶填满了则丢弃多余令牌。

有请求需要被处理，就从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

令牌桶的这种特性可以对突增的流量进行平缓处理，让系统负载更加均匀。

二、限流方案实现

1、nginx 接入层限流

如果系统有接入层，比如用nginx 做的反向代理。

1）官方提供两个模块:

  • ngx_http_limit_conn_module：连接数限流模块

该模块可以根据定义的键来限制每个键值的连接数，如同一个 IP 来源的连接数。并不是所有的连接都会被该模块计数，只有那些正在被处理的请求（这些请求的头信息已被完全读入）所在的连接才会被计数。

  • ngx_http_limit_req_module ：漏桶算法实现的请求限流模块

限制的方法是使用了漏斗算法，每秒固定处理请求数，推迟过多请求。

如果请求的频率超过了限制域配置的值，请求处理会被延迟或被丢弃，所以所有的请求都是以定义的频率被处理的。

1
2
3
4
5
6
7
8
limit_req_zone $binary_remote_addr zone=limit_login:10m rate=10r/m;
代表单ip每6秒1个请求(60/10=6)
limit_req_zone $binary_remote_addr zone=limit_login:10m rate=30r/m;
代表单ip每2秒1个请求(60/30=2)(官方文档叫half-request per second 1秒半个请求)
limit_req_zone $binary_remote_addr zone=limit_login:10m rate=1r/s;
代表单ip每秒1个请求
limit_req_zone $binary_remote_addr zone=limit_login:10m rate=2r/s;
代表单ip每秒2个请求

2）接入层限流的缺点：

・限流力度静态，手动配置，面对流量波动业务，很难去定义合理阈值。
・无法对服务层单服务做有效限流策略配置
・对接入层性能有较高要求

2、Guava的限流工具：RateLimiter

Google 开源工具包 Guava 提供了限流工具类 RateLimiter，基于令牌桶算法实现。

1）常用方法：

create（Double permitsPerSecond）方法根据给定的（令牌：单位时间（1s））比例为令牌生成速率
tryAcquire（）方法尝试获取一个令牌，立即返回 true/false，不阻塞，重载方法（如tryAcquire (long timeout, TimeUint unit)）具备设置获取令牌个数、获取最大等待时间等参数
acquire（）获取一个令牌，并且返回获取这个令牌所需要的时间。如果桶里没有令牌则等待，直到有令牌。支持同时获取N个。

  • RateLimiter 使用令牌桶算法，会进行令牌的累积，如果获取令牌的频率比较低，则不会导致等待，直接获取令牌。
  • RateLimiter 由于会累积令牌，所以可以应对突发流量。也就是说如果同时请求 5 个令牌，由于此时令牌桶中有累积的令牌，能够快速响应请求。
  • RateLimiter 在没有足够的令牌发放时，采用的是滞后的方式进行处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void rateLimiter() {
    // 创建一个限流器，设置每秒放置的令牌数：2 个
    // 返回的 RateLimiter 对象可以保证1秒内不会给超过2个令牌，并且是固定速率的放置。达到平滑输出的效果
    RateLimiter r = RateLimiter.create(2);

    // acquire() 获取一个令牌，并且返回这个获取这个令牌所需要的时间。如果桶里没有令牌则等待，直到有令牌。
    // 如果需要对某些突发的流量进行处理的话，可以对这个返回值设置一个阈值，根据不同的情况进行处理，比如过期丢弃。
    System.out.println(r.acquire(2));
    System.out.println(r.acquire(1));
    System.out.println(r.acquire(1));

    // 考虑超时情况下面请求直接结束
    boolean isPermit = r.tryAcquire(500, TimeUnit.MILLISECONDS);
    if (!isPermit) {
        throw new RuntimeException("business overheated.");
    }
}

2）属于应用层限流单机单应用

・无法跨 JVM，不适用于分布式服务