解决方案：限流算法_keyresolver

解决方案：限流算法

---

关键词

• 计数器法，漏桶（单位时间内），令牌桶算法（并发）
• gateway 默认使用redis的RateLimter限流算法（lua实现）
• nginx限流（ngx_http_limit_req_module，ngx_http_limit_conn_module）

---

一、常见限流算法

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

- 计数器法
计数器算法 简单粗暴。该算法会维护一个counter，规定在单位时间内counter的大小不能超过最大值，每隔固定时间就将counter的值置零。如果这个counter大于设定的阈值了，那么系统就开始拒绝请求以保护系统的负载。

- 漏桶算法
在漏桶算法中，我们会维护一个固定容量的桶，这个桶会按照指定的速度漏水。如果这个桶空了，那么就停止漏水；请求到达系统就类似于将水加入桶中，这个速度可以是匀速的也可以是瞬间的，如果这个桶满了，就会忽略后面来的请求，直到这个桶可以存放多余的水。漏桶算法的好处是可以将系统的处理能力维持在一个比较平稳的水平，缺点是在瞬间流量过来时，会拒绝后续的请求流量。一般来说，代码中会使用一个队列实现“漏斗”的效果，当请求过多时，队列中的请求就开始积压，当队列满了之后，系统就会开始拒绝请求。（相当于一个队列）

如图下图所示，把请求比作水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就导致水直接溢出，即拒绝服务。

- 令牌桶算法
令牌桶算法和漏桶算法效果一样，但思路相反：随着时间的流逝，系统会按照指定速度往桶里添加token，每来一个新请求，就从桶里拿走一个token，如果没有token可拿就拒绝服务。这种算法的好处是便于控制系统的处理速度，甚至可以通过统计信息实时优化令牌桶的大小。

令牌桶算法是比较常见的限流算法之一，大概描述如下：
1）所有的请求在处理之前都需要拿到一个可用的令牌才会被处理；
2）根据限流大小，设置按照一定的速率往桶里添加令牌；
3）桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝；
4）请求达到后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除；

从理论上来说，令牌桶算法和漏桶算法的不同之处在于处理瞬间到达的流量的不同：令牌桶算法由于在令牌桶里攒了很多令牌，因此在大流量到达的瞬间可以一次性将队列中所有的请求都处理完，然后按照恒定的速度处理请求；
漏桶算法则一直有一个恒等的阈值，在大流量到达的时候，也会将多余的请求拒绝。

在Nginx这种基本没什么业务逻辑的网关中，自身的处理不会是瓶颈，在这种场景下，就比较适合使用令牌桶算法了。

二、限流实践

RateLimiter是guava中concurrent包下的一个限流工具类，使用了令牌桶算法。

它支持两种令牌获取接口：

• 获取不到一直阻塞；
• 在指定时间内获取不到就阻塞，超过这个时间就返回获取失败。

（1）RateLimiter的使用。
在下面的这个例子中，我们希望每秒最多2000次业务操作，因此先初始化令牌桶的大小为2000，在执行业务操作之前，先调用acquire（）获取令牌，如果获取不到就阻塞。

如果请求可以丢弃，并且在某种程度上需要这种快速失败，那么就不能使用acquire（）方法，为了避免源源不断的请求将整体的系统资源耗尽，就需要使用 tryAcquire（）方法。下面是针对tryacquire（）的示例，还可以使用带超时参数的 tryAcquire（）方法，在指定时间内获取不到令牌再返回false。

（2）RateLimiter的设计思路。
RateLimiter的主要功能是通过 限制请求流入的速度 来提供稳定的服务速度。

实现QPS速度最简单的方式就是记住上一次请求的最后授权时间，然后保证1/QPS秒内不允许请求进入。例如QPS=5，如果我们保证最后一个被授权请求之后的200ms内没有请求被授权，那么就达到了预期的速度。如果一个请求现在过来但最后一个被授权请求是在100ms之前，那么我们就要求当前这个请求等待100ms，按照这个思路请求15个新令牌（许可证）就需要3秒。（控制申请令牌的速度）

三、网关限流实现（ 底层实现redis的RateLimter限流算法 [lua实现] ）

需求：每个ip地址1秒内只能发送1次请求，多出来的请求返回429错误。

（1）spring cloud gateway 默认使用redis的RateLimter限流算法来实现。所以我们要使用首先需要引入redis的依赖

<!--redis-->
<dependency>
   <groupId>org.springframework.boot</groupId>
   <artifactId>spring-boot-starter-data-redis-reactive</artifactId>
   <version>2.1.3.RELEASE</version>
</dependency>
1
2
3
4
5
6

（2）定义KeyResolver（通过IP限流）
指定限流的方式，可以基于IP限流、通过用户限流、通过接口限流。在GatewayApplicatioin引导类中添加如下代码，KeyResolver用于计算某一个类型的限流的KEY也就是说，可以通过KeyResolver来指定限流的Key。

    /**
     * 通过IP限流
     * @return
     */
    @Bean
    public KeyResolver ipKeyResolver(){
        return new KeyResolver() {
            @Override
            public Mono<String> resolve(ServerWebExchange exchange) {
                return Mono.just(exchange.getRequest().getRemoteAddress().getHostName());
            }
        };
    }

    /**
     * 通过用户限流
     * 请求路径中必须要包含用户的唯一表示，userId参数
     */
    //@Bean
    public KeyResolver userKeyResolver() {
        return exchange -> Mono.just(exchange.getRequest().getQueryParams().getFirst("userId"));
    }

    /**
     * 通过接口限流
     * 请求地址的uri作为限流的key
     */
    //@Bean
    public KeyResolver apiKeyResolver() {
        return exchange -> Mono.just(exchange.getRequest().getPath().value());
    }
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
28
29
30
31

（3）修改application.yml中配置项，指定限制流量的配置以及REDIS的配置，修改后最终配置如下：

spring:
  application:
    name: dabing-gateway
  cloud:
    gateway:
      #redis-rate-limiter:  全局限流配置位置
      #开启网关的跨域功能，具体微服务上的跨域需要进行关闭，否则无效
      routes:
        - id: goods
          uri: lb://dabing-goods
          predicates:
            - Path=/goods/**
          filters:
            - StripPrefix= 1
            # 具体微服务限流位置
            - name: RequestRateLimiter #请求数限流 名字不能随便写
              args:
                key-resolver: "#{@ipKeyResolver}"  #指定限流的key
                redis-rate-limiter.replenishRate: 1 # 允许每秒处理了多少个请求
                redis-rate-limiter.burstCapacity: 1 # 令牌桶的容量（最高处理并发容量大小1）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

参数介绍：

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

配置文件参数具体说明：

• 表示 一秒内，允许 一个请求通过，令牌桶的填充速率也是一秒钟添加一个令牌。
• 最大突发状况 也只允许 一秒内有一次请求，可以根据业务来调整 。

四、Nginx限流实现

Nginx提供两种限流的方式：

• 一是控制速率，请求限制。
  • ngx_http_limit_req_module模块，通过漏桶算法限制单位时间内请求数目。
• 二是控制并发，控制并发连接数，TCP连接，令牌桶算法。
  • ngx_http_limit_conn_module模块
• 负载均衡模块。max_conns可以对服务端进行限流。
  • ngx_http_upstream_module模块（高版本可以使用）

4.1 控制速率

控制速率的方式之一就是采用漏桶算法。

漏桶算法实现控制速率限流

修改/usr/local/openresty/nginx/conf/nginx.conf:

limit_req_zone： 控制速率，单位时间内的请求数。

1. Key：通过什么进行限流，比如可以通过用户的IP地址限流。

   获取IP地址：$binary_remote_add。

2. Zone：存储获取到的客户端的IP地址，zone=keyword（自定义）,可以指定该内存空间的大小，keyword:空间大小。1MB大概可以存储二进制的IP地址16000个。

3. Rate，限制请求数，rate=10r/s，每个IP地址每秒最多允许10个请求，以毫秒为单位：每100ms执行一个请求（因为是匀速的）。

   http {
     # 设置限流配置
     limit_req_zone $binary_remote_addr zone=myRateLimit:10m rate=10r/s;
       
     server { 
       listen    80;
       server_name localhost;
       charset utf-8;
           
       location / {
         limit_req zone=myRateLimit;
         root  html;
         index  index.html index.htm;
       }
     }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16

解释：

#binary_remote_addr 是一种key，表示基于 remote_addr(客户端IP) 来做限流，binary_ 的目的是压缩内存占用量。

#zone：定义共享内存区来存储访问信息,myRateLimit:10m 表示一个大小为10M，名字为myRateLimit的内存区域。1M能存储16000 IP地址的访问信息，10M可以存储16W IP地址访问信息。

#rate 用于设置最大访问速率，rate=10r/s 表示每秒最多处理10个请求。Nginx 实际上以毫秒为粒度来跟踪请求信息，因此 10r/s 实际上是限制：每100毫秒处理一个请求。这意味着，自上一个请求处理完后，若后续100毫秒内又有请求到达，将拒绝处理该请求。我们这里设置成2 方便测试。
1
2
3
4
5

限流速度为每秒10次请求，如果有10次请求同时到达一个空闲的nginx，他们都能得到执行吗？

漏桶漏出请求是匀速的。10r/s是怎样匀速的呢？每100ms漏出一个请求。

在这样的配置下，桶是空的，所有不能实时漏出的请求，都会被拒绝掉。

所以如果10次请求同时到达，那么只有一个请求能够得到执行，其它的，都会被拒绝。这不太友好，大部分业务场景下我们希望这10个请求都能得到执行。

测试：重新加载配置文件

cd /usr/local/openresty/nginx/sbin

./nginx -s reload
1
2
3

访问页面：

处理突发流量

我们把配置改一下，解决上一节的问题。

例如，如下配置表示：

server {
  location / {
	limit_req zone=myRateLimit burst=10;
    root  html;
    index  index.html index.htm;
 }
}
1
2
3
4
5
6
7

burst 译为突发、爆发，表示在超过设定的处理速率后能额外处理的请求数,当 rate=10r/s 时，将1s拆成10份，即每100ms可处理1个请求。

逻辑上叫漏桶，实现起来是FIFO队列，把得不到执行的请求暂时缓存起来。

这样漏出的速度仍然是100ms一个请求，但并发而来，暂时得不到执行的请求，可以先缓存起来。只有当队列满了的时候，才会拒绝接受新请求。

这样漏桶在限流的同时，也起到了削峰填谷的作用。

在这样的配置下，如果有10次请求同时到达，它们会依次执行，每100ms执行1个（不会立马拒绝另外9个）。

虽然得到执行了，但因为排队执行，延迟大大增加，在很多场景下仍然是不能接受的。

此处，burst=20 ，若同时有21个请求到达，Nginx 会处理第一个请求，剩余20个请求将放入队列，然后每隔100ms从队列中获取一个请求进行处理。若请求数大于21，将拒绝处理多余的请求，直接返回503.

不过，单独使用 burst 参数并不实用。假设 burst=50 ，rate依然为10r/s，排队中的50个请求虽然每100ms会处理一个，但第50个请求却需要等待 50 * 100ms即 5s（一直等待），这么长的处理时间自然难以接受。

因此，burst 往往结合 nodelay 一起使用。（进桶的全部马上就执行，不等待）

例如：如下配置：

server {
  location / {
	limit_req zone=myRateLimit burst=5 nodelay;
    root  html;
    index  index.html index.htm;
 }
}
1
2
3
4
5
6
7

如上表示：

平均每秒允许不超过2个请求，突发不超过5个请求，并且处理突发5个请求的时候，没有延迟，等到完成之后，按照正常的速率处理。

nodelay 把开始执行请求的时间提前，以前是delay到从桶里漏出来才执行，现在不delay了，只要入桶就开始执行。

要么立刻执行，要么被拒绝，请求不会因为限流而增加延迟了。

因为请求从桶里漏出来还是匀速的，桶的空间又是固定的，最终平均下来，还是每秒执行了5次请求，限流的目的还是达到了。

但这样也有缺点，限流是限了，但是限得不那么匀速。以上面的配置举例，如果有12个请求同时到达，那么这12个请求都能够立刻执行，然后后面的请求只能匀速进桶，100ms执行1个。如果有一段时间没有请求，桶空了，那么又可能出现并发的12个请求一起执行。

大部分情况下，这种限流不匀速，不算是大问题。不过nginx也提供了一个参数才控制并发执行也就是nodelay的请求的数量。

limit_req_zone $binary_remote_addr zone=ip_limit:10mrate=10r/s;

    server {
     location /login/ {
      	limit_req zone=ip_limit burst=12 delay=4;
      	proxy_pass http://login_upstream;
    }
}
1
2
3
4
5
6
7
8

delay=4 从桶内第5个请求开始delay

这样通过控制delay参数的值，可以调整允许并发执行的请求的数量，使得请求变的均匀起来，在有些耗资源的服务上控制这个数量，还是有必要的。

测试：如下图 在1秒钟之内可以刷新5次，正常处理。

但是超过之后，连续刷新5次，抛出异常。

限制请求

  #限制请求
  limit_req_zone $uri zone=api_read:20m rate=50r/s;
  
  #按ip配置一个连接 zone
  limit_conn_zone $binary_remote_addr zone=perip_conn:10m;
  
  #按server配置一个连接 zone
  limit_conn_zone $server_name zone=perserver_conn:100m;
  
  #按goodId配置一个连接 zone
1
2
3
4
5
6
7
8
9
10

4.2 并发限制

Nginx 并发限制的功能来自于 ngx_http_limit_conn_module 模块，跟请求配置一样，使用它之前，需要先定义参照标准和状态缓存区。

limit_conn_zone 只能配置在 http 范围内；

$binary_remote_addr 表示客户端请求的IP地址；

myconn 自己定义的变量名（缓冲区）；

limit_rate 限制传输速度

limit_conn 与 limit_conn_zone 对应，限制网络连接数

# 定义了一个 myconn 缓冲区（容器）
limit_conn_zone $binary_remote_addr zone=myconn:10m;
server {
  listen 70;
  location / {
    # 每个 IP 只允许一个连接
    limit_conn myconn 1;
    # 限制传输速度（如果有N个并发连接，则是 N * limit_rate）
    limit_rate 1024k;
    proxy_pass http://localhost:80;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12