网关限流算法及实现总结

在高并发的系统中，往往需要在系统中做限流，一方面是为了防止大量的请求使服务器过载，导致服务不可用，另一方面是为了防止网络攻击。

常见的限流场景有：

• 限制总并发数（比如数据库连接池、线程池）
• 限制瞬时并发数（如 nginx 的 limit_conn 模块，用来限制瞬时并发连接数）
• 限制时间窗口内的平均速率（如 Guava 的 RateLimiter、nginx 的 limit_req 模块，限制每秒的平均速率）
• 其他还有如限制远程接口调用速率、限制 MQ 的消费速率
• 另外还可以根据网络连接数、网络流量、CPU 或内存负载等来限流。

1.算法篇

常用的限流算法有：计数器，漏桶，令牌桶。

1.1.计数器算法

请求限流简单的做法是维护一个单位时间内的计数器，每次请求计数器加1，当单位时间内计数器累加到大于设定的阈值，则之后的请求都被拒绝，直到单位时间已经过去，再将计数器 重置为零。
这种方式有个缺点：如果在单位时间1s内允许100个请求，在10ms已经通过了100个请求，那后面的990ms，只能眼巴巴的把请求拒绝，我们把这种现象称为“突刺现象”。

计数器算法在生产实践中使用较少，在工业界常用的是更平滑的限流算法：漏桶算法和令牌桶算法。

1.2.漏桶算法

漏桶算法很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水（接口有响应速率），当水流入速度过大会直接溢出（访问频率超过接口响应速率），然后就拒绝请求，可以看出漏桶算法能强行限制请求的处理速率。

算法思想是：

1. 水（请求）从上方倒入水桶，从水桶下方流出（被处理）；
2. 来不及流出的水存在水桶中（缓冲），以固定速率流出；
3. 水桶满后水溢出（丢弃）。
   这个算法的核心是：缓存请求、匀速处理、多余的请求丢弃。

漏桶算法中主要有两个变量：

• 一个是桶大小（burst），即支持流量突发增多时可以存多少的水；
• 另一个是漏斗大小（rate），即漏桶漏出速率的固定参数；

所以，即使网络中不存在资源冲突（没有发生拥塞），漏桶算法也不能使流突发（burst）到端口速率。因此，漏桶算法对突发流量不做额外处理，无法应对存在突发特性的流量。

1.3.令牌桶算法

令牌桶算法 和漏桶算法 效果一样但方向相反的算法，更加容易理解。随着时间流逝，系统会按恒定 1/QPS 时间间隔（如果 QPS=100，则间隔是 10ms）往桶里加入 Token（想象和漏洞漏水相反，有个水龙头在不断的加水），如果桶已经满了就不再加了。新请求来临时，会各自拿走一个 Token，如果没有 Token 可拿了就阻塞或者拒绝服务。

算法思想是：

1. 令牌以固定速率产生，并缓存到令牌桶中；
2. 令牌桶放满时，多余的令牌被丢弃；
3. 请求要消耗等比例的令牌才能被处理；
4. 令牌不够时，请求被丢弃。

漏桶和令牌桶算法最明显的区别就是是否允许突发流量(burst)的处理，漏桶算法能够强行限制数据的实时传输（处理）速率，对突发流量不做额外处理；而令牌桶算法能够在限制数据的平均传输速率的同时允许某种程度的突发流量处理（桶内可累计缓存最大令牌数量）。

2.实践篇

在生产实践中，请求限流通常依赖于api网关来实现，常用网关基本都支持限流功能，例如常用的nginx和springcloud-gateway。

2.1.nginx限流

Nginx按请求速率限速模块使用的是优化漏桶算法（支持突发量请求处理，详见nodelay参数），即能够强行保证请求的实时处理速度不会超过设置的阈值。Nginx官方版本限制IP的连接和并发分别有两个模块：

• ngx_http_limit_req_module 用来限制单位时间内的请求数，即速率限制,采用的漏桶算法 “leaky bucket”。
• ngx_http_limit_conn_module 用来限制同一时间连接数，即并发限制。

2.1.1.Module ngx_http_limit_req_module

参数配置

Syntax: limit_req_zone key zone=name:size rate=req/time; 
Default: — 
Context: http
1
2
3

# 语法
Syntax: limit_req zone=name [burst=number] [nodelay];
# 默认值（无）
Default: -
# 作用域
Context: http, server, location
1
2
3
4
5
6

示例

http{

 # 声明请求限流存储区
 limit_req_zone $binary_remote_addr zone=req_one:10m rate=1r/s
 server{
  ...
  limit_req zone=req_one burst=5 nodelay;
  ...
 }
}
1
2
3
4
5
6
7
8
9
10

配置说明：

limit_req_zone $binary_remote_addr zone=req_one:10m rate=1r/s

• 第一个参数：$binary_remote_addr 表示通过remote_addr这个标识来做限制，“binary_”目的是缩写内存占用量，是限制同一客户端ip地址。
• 第二个参数：zone=one:10m 表示生成一个大小为10M，名字为one的内存区域，用来存储访问的频次信息。
• 第三个参数：rate=1r/s表示允许相同标识的客户端的访问频次，这里限制的是每秒1次，还可以有比如30r/m的。

limit_req zone=one burst=5 nodelay;

• 第一个参数：zone=one 设置使用哪个配置区域来做限制，与上面limit_req_zone 里的name对应。
• 第二个参数：burst=5，重点说明一下这个配置，burst爆发的意思，这个配置的意思是设置一个大小为5的缓冲区当有大量请求（爆发）过来时，超过了访问频次限制的请求可以先放到这个缓冲区内，缓冲区容量为5。
• 第三个参数：nodelay 该参数允许请求在排队的时候就立即被处理，也就是说只要请求能够进入burst队列，就会立即被后台worker处理，请注意，这意味着burst设置了nodelay时，系统瞬间的QPS可能会超过rate设置的阈值。nodelay参数要跟burst一起使用才有作用。否则所有请求会等待排队按漏桶固定速度处理。

其他参数：

• limit_req_log_level 当服务器由于限速或缓存，设置写入日志的级别。

Syntax: limit_req_log_level info | notice | warn | error;
Default: limit_req_log_level error; 
Context: http, server, location
1
2
3

• limit_req_status 设置拒绝请求的返回值，只能设置400-599之间

Syntax: limit_req_status code; 
Default: limit_req_status 503;
Context: http, server, location
1
2
3

2.1.2.Module ngx_http_limit_conn_module

这个模块用来限制单个IP的连接数，并非所有的连接都被计数，只有在服务器处理了请求并已经读取了完整的请求头时，才被计数。
参数配置：

Syntax: limit_conn_zone key zone=name:size; 
Default: — 
Context: http
1
2
3

Syntax: limit_conn zone number; 
Default: — 
Context: http, server, location
1
2
3

示例：
只允许每个IP保持一个连接

limit_conn_zone $binary_remote_addr zone=addr:10m; 
server {
    location /download/ { 
        limit_conn addr 1; 
    }
1
2
3
4
5

可以配置多个limit_coon指令，例如配置客户端每个IP连接数，同时限制服务端最大保持连接数

limit_conn_zone $binary_remote_addr zone=perip:10m; 
limit_conn_zone $server_name zone=perserver:10m; 
server {
    ... 
    limit_conn perip 10; 
    limit_conn perserver 100; 
    ...
}
1
2
3
4
5
6
7
8

在这里，客户端IP地址作为键，不是$remote_addr，而是使用$binary_remote_addr变量。
$remote_addr 变量的大小可以从7到15个字节不等。存储的状态在32位平台上占用32或64字节的内存，在64位平台上总是占用64字节。对于IPv4地址，$binary_remote_addr变量的大小始终为4个字节，对于IPv6地址则为16个字节。存储状态在32位平台上始终占用32或64个字节，在64位平台上占用64个字节。一个兆字节的区域可以保持大约32000个32字节的状态或大约16000个64字节的状态。如果区域存储耗尽，服务器会将错误返回给所有其他请求。

其他参数

• limit_conn_log_level 当超出连接数时，设置日志记录级别

Syntax: limit_conn_log_level info | notice | warn | error;
Default: limit_conn_log_level error;
Context: http, server, location
1
2
3

• limit_conn_status 设置拒绝请求时返回码

Syntax: limit_conn_status code; 
Default: limit_conn_status 503; 
Context: http, server, location
1
2
3

实例一 限制访问速率

limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s; 
server {
    location / { 
        limit_req zone=mylimit; 
        }
    }
1
2
3
4
5
6

上述规则限制了每个IP访问的速度为2r/s，并将该规则作用于根目录。如果单个IP在非常短的时间内并发发送多个请求，结果会怎样呢？

我们使用单个IP在10ms内发并发送了6个请求，只有1个成功，剩下的5个都被拒绝。我们设置的速度是2r/s，为什么只有1个成功呢，是不是Nginx限制错了？当然不是，是因为Nginx的限流统计是基于毫秒的，我们设置的速度是2r/s，转换一下就是500ms内单个IP只允许通过1个请求，从501ms开始才允许通过第二个请求。

实例二 burst缓存处理

短时间内发送大量请求，Nginx按照毫秒级精度统计，超出限制的请求直接拒绝。这在实际场景中未免过于苛刻，真实网络环境中请求到来不是匀速的，很可能有请求“突发”的情况，也就是“一股子一股子”的。Nginx考虑到了这种情况，可以通过burst关键字开启对突发请求的缓存处理，而不是直接拒绝。

limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s; 
server { 
    location / { 
        limit_req zone=mylimit burst=4; 
    } 
}
1
2
3
4
5
6

我们加入了burst=4，意思是每个key(此处是每个IP)最多允许4个突发请求的到来。如果单个IP在10ms内发送6个请求，结果会怎样呢？

相比实例一成功数增加了4个，这个我们设置的burst数目是一致的。具体处理流程是：1个请求被立即处理，4个请求被放到burst队列里，另外一个请求被拒绝。通过burst参数，我们使得Nginx限流具备了缓存处理突发流量的能力。
但是请注意：burst的作用是让多余的请求可以先放到队列里，慢慢处理。如果不加nodelay参数，队列里的请求不会立即处理，而是按照rate设置的速度，以毫秒级精确的速度慢慢处理。

实例三 nodelay降低排队时间

实例二中我们看到，通过设置burst参数，我们可以允许Nginx缓存处理一定程度的突发，多余的请求可以先放到队列里，慢慢处理，这起到了平滑流量的作用。但是如果队列设置的比较大，请求排队的时间就会比较长，用户角度看来就是响应变长了，这对用户很不友好。有什么解决办法呢？nodelay参数允许请求在排队的时候就立即被处理，也就是说只要请求能够进入burst队列，就会立即被后台worker处理，请注意，这意味着burst设置了nodelay时，系统瞬间的QPS可能会超过rate设置的阈值。nodelay参数要跟burst一起使用才有作用。

limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
server { 
    location / { 
        limit_req zone=mylimit burst=4 nodelay;
    } 
}
1
2
3
4
5
6

单个IP 10ms内并发发送6个请求，结果如下：

跟实例二相比，请求成功率没变化，但是总体耗时变短了。这怎么解释呢？实例二中，有4个请求被放到burst队列当中，工作进程每隔500ms(rate=2r/s)取一个请求进行处理，最后一个请求要排队2s才会被处理；实例三中，请求放入队列跟实例二是一样的，但不同的是，队列中的请求同时具有了被处理的资格，所以实例三中的5个请求可以说是同时开始被处理的，花费时间自然变短了。

但是请注意，虽然设置burst和nodelay能够降低突发请求的处理时间，但是长期来看并不会提高吞吐量的上限，长期吞吐量的上限是由rate决定的，因为nodelay只能保证burst的请求被立即处理，但Nginx会限制队列元素释放的速度，就像是限制了令牌桶中令牌产生的速度。看到这里你可能会问，加入了nodelay参数之后的限速算法，到底算是哪一个“桶”，是漏桶算法还是令牌桶算法？当然还算是漏桶算法。

在令牌桶算法中，令牌桶算法的token为耗尽时会怎么做呢？由于它有一个请求队列，所以会把接下来的请求缓存下来，缓存多少受限于队列大小。但此时缓存这些请求还有意义吗？如果server已经过载，缓存队列越来越长，响应时间越来越长，即使过了很久请求被处理了，对用户来说也没什么价值。所以当token不够用时，最明智的做法就是直接拒绝用户的请求，这就成了漏桶算法。

2.2.springcloud-gateway限流

Spring Cloud Gateway是Spring官方基于Spring 5.0，Spring Boot 2.0和Project Reactor等技术开发的网关，Spring Cloud Gateway旨在为微服务架构提供一种简单而有效的统一的API路由管理方式。Spring Cloud Gateway作为Spring Cloud生态系统中的网关，目标是替代Netflix ZUUL，其不仅提供统一的路由方式，并且基于Filter链的方式提供了网关基本的功能，例如：安全，监控/埋点，和限流等。

Spring Cloud Gateway 已经内置了一个基于令牌桶算法实现的限流器RequestRateLimiterGatewayFilterFactory，我们可以直接使用。RequestRateLimiterGatewayFilterFactory的实现依赖于 Redis，所以我们还要引入spring-boot-starter-data-redis-reactive。

pom.xml

<dependency>
    <groupId>org.springframework.cloud</groupId>
    <artifactId>spring-cloud-starter-gateway</artifactId>
</dependency>

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifatId>spring-boot-starter-data-redis-reactive</artifactId>
</dependency>
1
2
3
4
5
6
7
8
9

application.yml

server:
  port: 8080
spring:
  cloud:
    gateway:
      routes:
        - id: limit_route
          uri: http://www.baidu.com/
          predicates:
          - After=2019-02-26T00:00:00+08:00[Asia/Shanghai]
          filters:
          - name: RequestRateLimiter
            args:
              key-resolver: '#{@hostAddrKeyResolver}'
              redis-rate-limiter.replenishRate: 1
              redis-rate-limiter.burstCapacity: 3
  application:
    name: gateway-limiter
  redis:
    host: localhost
    port: 6379
    database: 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在上面的配置文件，配置了 redis的信息，并配置了RequestRateLimiter的限流过滤器，该过滤器需要配置三个参数：

• burstCapacity：令牌桶总容量。
• replenishRate：令牌桶每秒填充平均速率。
• key-resolver：用于限流的键的解析器的 Bean 对象的名字。它使用 SpEL 表达式根据#{@beanName}从 Spring 容器中获取 Bean 对象。

实例一 IP限流

获取请求用户ip作为限流key，KeyResolver是获取限流键的接口。

    @Bean
    public KeyResolver hostAddrKeyResolver() {
        return new IpKeyResolver();  
    }
1
2
3
4

实例二 用户限流

获取请求用户id作为限流key

@Bean
public KeyResolver userKeyResolver() {
    return exchange -> Mono.just(exchange.getRequest().getQueryParams().getFirst("userId"));
}
1
2
3
4

实例三 接口限流

获取请求地址的uri作为限流key

@Bean
public KeyResolver apiKeyResolver() {
    return exchange -> Mono.just(exchange.getRequest().getPath().value());
}
1
2
3
4