【限流01】限流算法理论篇_固定时间窗口限流算法

微服务就是将复杂的大应用拆分成小的应用，这样做的好处是各个应用之间独立开发、测试、上线，互不影响。但是服务拆分之后，带来的问题也很多，我们需要保障微服务的正常运行，就需要进行服务治理。常用手段有：鉴权、限流、降级、熔断等。

其中，限流是指对某个接口的调用频率进行限制，防止接口调用频率过快导致线程资源被耗尽从而导致整个系统响应变慢。限流在很多业务中都有应用，比如：秒杀、双11。当用户请求量过大时，就会拒绝后续接口请求，保障系统的稳定性。

接口限流的实现思路是：统计某个时间段内的接口调用次数，当调用次数超过设置的阈值时，就进行限流限制接口访问。

常见的限流算法有：固定时间窗口算法、滑动时间窗口算法、令牌桶算法、漏桶算法等，下面我们将一一介绍每种算法的实现思路和代码实现。

一、固定时间窗口限流算法

1、算法概述

固定时间窗口限流算法的思路就是：确定一段时间段，在该时间段内统计接口的调用次数，来判断是否限流。

实现步骤如下：
选定一个时间起点，当接口请求到来时，

• 接口访问次数小于阈值，可以访问，接口访问次数 + 1；
• 接口访问次数大于阈值，拒绝该时间段内后续访问进行限流，接口访问次数不变；
• 进入下一个时间窗口之后，计数器清零，时间起点设置为当前时间，这样就进入下一个时间窗口。

示意图如下：

​ （图片来源：https://time.geekbang.org/column/article/80388?utm_term=zeusNGLWQ&utm_source=xiangqingye&utm_medium=geektime&utm_campaign=end&utm_content=xiangqingyelink1104，下图同上）

这种限流算法的缺点是：无法应对两个时间窗口临界时间内的突发流量。

如下图：假设要求每秒钟接口请求次数不超过100，在第1s时间窗口内接口请求次数为100，但是都集中在最后10ms；第2s时间窗口内接口请求次数也为100，都集中在前10ms内；两个时间窗口请求次数都小于100，满足要求。但是在两个10ms内接口请求次数=200 > 100。如果这个次数不是200，是2000万，可能就会导致系统崩溃。

2、代码实现

public class FixedWindowRateLimitAlg implements RateLimitAlg {
   
    // ms
    private static final long LOCK_EXPIRE_TIME = 200L;

    private Stopwatch stopWatch;
    // 限流计数器
    private AtomicInteger counter = new AtomicInteger(0);
    private final int limit;
    private Lock lock = new ReentrantLock();

    public FixedWindowRateLimitAlg(int limit) {
   
        this(limit, Stopwatch.createStarted());
    }

    public FixedWindowRateLimitAlg(int limit, Stopwatch stopWatch) {
   
        this.limit = limit;
        this.stopWatch = stopWatch;
    }

    @Override
    public boolean tryAcquire() throws InterruptedException {
   
        int currentCount = counter.incrementAndGet();
        // 未达到限流
        if (currentCount < limit) {
   
            return true;
        }

        // 使用固定时间窗口统计当前窗口请求数
        // 请求到来时,加锁进行计数器统计工作
        try {
   
            if (lock.tryLock(LOCK_EXPIRE_TIME, TimeUnit.MILLISECONDS)) {
   
                // 如果超过这个时间窗口, 则计数器counter归零, stopWatch, 窗口进入下一个窗口
                if (stopWatch.elapsed(TimeUnit.MILLISECONDS) > TimeUnit.SECONDS.
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
32
33
34
35
36
37
38
39