博客

1.常用限流算法

1.1计数器法

计数器是最简单的限流算法，思路是维护一个单位时间内的计数器 Counter，如判断单位时间已经过去，则将计数器归零。

我们假设有个需求对于某个接口 /query 每分钟最多允许访问 200 次。

1. 可以在程序中设置一个变量 count，当过来一个请求我就将这个数 +1，同时记录请求时间。
2. 当下一个请求来的时候判断 count 的计数值是否超过设定的频次，以及当前请求的时间和第一次请求时间是否在 1 分钟内。
3. 如果在 1 分钟内并且超过设定的频次则证明请求过多，后面的请求就拒绝掉。
4. 如果该请求与第一个请求的间隔时间大于 1 分钟，且 count 值还在限流范围内，就重置 count。

1.2滑动窗口

滑动窗口（Sliding window）（https://en.wikipedia.org/wiki/Sliding_window_protocol） 是一种流量控制技术，这个词出现在 TCP 协议中。我们来看看在限流中它是怎样表现的：

上图中我们用红色的虚线代表一个时间窗口（一分钟），每个时间窗口有 6 个格子，每个格子是 10 秒钟。每过 10 秒钟时间窗口向右移动一格，可以看红色箭头的方向。我们为每个格子都设置一个独立的计数器 Counter，假如一个请求在 0:45 访问了那么我们将第五个格子的计数器 +1（也是就是 0:40~0:50），在判断限流的时候需要把所有格子的计数加起来和设定的频次进行比较即可。

我再来回顾一下刚才的计数器算法，我们可以发现，计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做进一步地划分，所以只有1格。

由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

1.3漏桶算法

从图中我们可以看到，整个算法其实十分简单。首先，我们有一个固定容量的桶，有水流进来，也有水流出去。对于流进来的水来说，我们无法预计一共有多少水会流进来，也无法预计水流的速度。但是对于流出去的水来说，这个桶可以固定水流出的速率。而且，当桶满了之后，多余的水将会溢出。

我们将算法中的水换成实际应用中的请求，我们可以看到漏桶算法天生就限制了请求的速度。当使用了漏桶算法，我们可以保证接口会以一个常速速率来处理请求。

漏桶算法有以下特点：

• 漏桶具有固定容量，出水速率是固定常量（流出请求）
• 如果桶是空的，则不需流出水滴
• 可以以任意速率流入水滴到漏桶（流入请求）
• 如果流入水滴超出了桶的容量，则流入的水滴溢出（新请求被拒绝）

漏桶限制的是常量流出速率（即流出速率是一个固定常量值），所以最大的速率就是出水的速率，不能出现突发流量。

1.4令牌桶算法

令牌桶算法和漏桶算法的方向刚好是相反的，我们有一个固定容量的桶，桶里存放着令牌（token）。桶一开始是空的，token以 一个固定的速率r往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通过。

令牌桶有以下特点：

• 令牌按固定的速率被放入令牌桶中
• 桶中最多存放 B 个令牌，当桶满时，新添加的令牌被丢弃或拒绝
• 如果桶中的令牌不足 N 个，则不会删除令牌，且请求将被限流（丢弃或阻塞等待）

令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量。

1.5 小结

计数器和滑动窗口比较

计数器算法实现起来最简单，可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上需要更多的存储空间。也就是说，如果滑动窗口的精度越高，需要的存储空间就越大。

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

2.ratelimit总览

开启zuul服务限流的组件，包含五种内置的限流方式：

只需向列表中添加多个值，就可以将经过身份验证的用户、请求源、URL、角色和请求方法组合在一起

3.用法

添加ratelimit依赖

<dependency>
    <groupId>com.marcosbarbero.cloud</groupId>
    <artifactId>spring-cloud-zuul-ratelimit</artifactId>
    <version>LATEST</version>
</dependency>

使用数据存储不同，则需引入不同依赖

Redis:

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

Consul:

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

Spring Data JPA:

<dependency>
   <groupId>org.springframework.boot</groupId>
   <artifactId>spring-boot-starter-data-jpa</artifactId>
</dependency>

Bucket4j JCache:

<dependency>
     <groupId>com.github.vladimir-bukhtoyarov</groupId>
     <artifactId>bucket4j-core</artifactId>
</dependency>

<dependency>
     <groupId>com.github.vladimir-bukhtoyarov</groupId>
     <artifactId>bucket4j-jcache</artifactId>
</dependency>

<dependency>
     <groupId>javax.cache</groupId>
     <artifactId>cache-api</artifactId>
</dependency>

Bucket4j Hazelcast (depends on Bucket4j JCache):

<dependency>
     <groupId>com.github.vladimir-bukhtoyarov</groupId>
     <artifactId>bucket4j-hazelcast</artifactId>
</dependency>

<dependency>
     <groupId>com.hazelcast</groupId>
     <artifactId>hazelcast</artifactId>
</dependency>

Bucket4j Infinispan (depends on Bucket4j JCache):

<dependency>
     <groupId>com.github.vladimir-bukhtoyarov</groupId>
     <artifactId>bucket4j-infinispan</artifactId>
</dependency>

<dependency>
     <groupId>org.infinispan</groupId>
     <artifactId>infinispan-core</artifactId>
</dependency>

Bucket4j Ignite (depends on Bucket4j JCache):

<dependency>
     <groupId>com.github.vladimir-bukhtoyarov</groupId>
     <artifactId>bucket4j-ignite</artifactId>
</dependency>

<dependency>
     <groupId>org.apache.ignite</groupId>
     <artifactId>ignite-core</artifactId>
</dependency>

配置示例：

zuul:
  ratelimit:
    key-prefix: your-prefix  #限流key前缀
    enabled: true      #是否启用限流
    repository: REDIS  #使用何种方式存储数据
    behind-proxy: true
    add-response-headers: true
    default-policy-list: #optional - will apply unless specific policy exists  默认策略 （60s内超过10次或请求时间累积超过1000s触发限流）
      - limit: 10 #optional - request number limit per refresh interval window  单位时间内请求次数限制
        quota: 1000 #optional - request time limit per refresh interval window (in seconds)  单位时间内累计请求时间限制（秒）
        refresh-interval: 60 #default value (in seconds)   限流时间窗口，默认60s
        type: #optional  限流方式
          - user
          - origin
          - url
          - httpmethod
    policy-list:  # 自定义策略
      myServiceId: #本例配置：60s内超过10次，请求时间累积超过1000s触发限流
        - limit: 10 #optional - request number limit per refresh interval window 单位时间内请求次数限制
          quota: 1000 #optional - request time limit per refresh interval window (in seconds) 单位时间内累计请求时间限制（秒）
          refresh-interval: 60 #default value (in seconds)  限流时间窗口，默认60s
          type: #optional 限流方式
            - user
            - origin
            - url
        - type: #optional value for each type
            - user=anonymous
            - origin=somemachine.com
            - url=/api #url prefix
            - role=user
            - httpmethod=get #case insensitive

4.多种实现

Memory

1.7.1.RELEASE

2.2.6.RELEASE

5.常用配置解读

zuul.ratelimit

. :配置项

policy(策略配置项)：

6.自定义生成key

@RequiredArgsConstructor
public class CustomRateLimitKeyGenerator implements RateLimitKeyGenerator {
 
    private final RateLimitProperties properties;
    private final RateLimitUtils rateLimitUtils;
 
    @Override
    public String key(final HttpServletRequest request, final Route route, final Policy policy) {
        final List<Type> types = policy.getType().stream().map(MatchType::getType).collect(Collectors.toList());
        final StringJoiner joiner = new StringJoiner(":");
        joiner.add(properties.getKeyPrefix());
        if (route != null) {
            joiner.add(route.getId());
        }
        if (!types.isEmpty()) {
            if (types.contains(Type.URL) && route != null) {
                joiner.add(route.getPath());
            }
            if (types.contains(Type.ORIGIN)) {
                joiner.add(rateLimitUtils.getRemoteAddress(request));
            }
            if (types.contains(Type.USER)) {
                joiner.add(rateLimitUtils.getUser(request));
            }
        }
        return joiner.toString();
    }
}

7.源码

properties配置类：

RateLimitProperties加载前缀：zuul.ratelimit的配置

@Data
@Validated
@RefreshScope
@NoArgsConstructor
@ConfigurationProperties(RateLimitProperties.PREFIX)
public class RateLimitProperties {
 
    public static final String PREFIX = "zuul.ratelimit";

key\rate

redis\jpa\consul 用的是计数器的方式实现限流，不同的限流策略生成一个限流key，计算剩余的限流数据等存入rate,key–rate 一一对应，请求进来后由key查询是否已有rate,没有则生成rate保存，后置filter更新剩余请求次数、请求耗时

public class Rate {
 
    @Id
    @Column(name = "rate_key")
    private String key;
    /**
     * 剩余的请求数
     *
     */
    private Long remaining;
    /**
     * 剩余的请求耗时
     *
     */
    private Long remainingQuota;
    /**
     *
     *
     */
    private Long reset;
    /**
     * 过期时间
     *
     */
    @JsonFormat(shape = JsonFormat.Shape.STRING, pattern = "dd-MM-yyyy HH:mm:ss")
    private Date expiration;
}

前置过滤

取得配置的Route信息，策略集合，遍历集合，生成限流key,创建rate(保存或更新),比较limit调用次数，请求时间是否超过阈值

后置过滤

计算请求耗时，更新key值对应的 限流rate的请求时间阈值