yhzdys's notes
0%

限流-滑动时间窗

发表于 分类于 ，

滑动时间窗算法通常被用于系统限流，限流的目的是通过对并发访问/请求进行限速，或者对一个时间段内的请求进行限速来保护系统，一旦达到限制速率程序可以进行拒绝、等待或降级等操作。

滑动时间窗算法是针对 固定窗口算法 的改良，一定程度上缓解了固定窗口算法下的临界问题，它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。

当滑动时间窗的格子越小，那么窗口的滚动就越平滑，限流就会越精确。

Java实现

实场景中通常使用Redis的有序集合(sorted set)来实现

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
40
public class SlideWindowLimiter {
    // 限流时间长度，单位：毫秒
    private final long windowTime;
    // 单个时间长度内限流次数
    private final int limitNum;
    private final List<Long> windows;

    public SlideWindowLimiter(long windowTime, int limitNum) {
        this.windowTime = windowTime;
        this.limitNum = limitNum;
        this.windows = new LinkedList<>();
    }

    public synchronized boolean outOfLimit() {
        // 获取当前时间
        long now = System.currentTimeMillis();
        // 如果队列还没满，则允许通过，并添加当前时间戳到队列开始位置
        if (this.windows.size() < this.limitNum) {
            this.windows.add(0, now);
            return true;
        }

        // 队列已满（达到限制次数），则获取队列中最早添加的时间戳
        int lastIndex = this.limitNum - 1;
        Long lastTime = this.windows.get(lastIndex);
        // 用当前时间戳 减去 最早添加的时间戳
        if (this.windowTime >= now - lastTime) {
            // 若结果小于等于timeWindow，则说明在timeWindow内，通过的次数大于limit
            // 不允许通过
            return false;
        } else {
            // 若结果大于时间窗长度，则说明在限定时间内，通过的次数小于等于limit
            // 允许通过，并删除最早添加的时间戳，将当前时间添加到队列开始位置
            this.windows.remove(lastIndex);
            this.windows.add(0, now);
            return true;
        }
    }

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main(String[] args) throws Exception {
        SlideWindowLimiter limiter = new SlideWindowLimiter(2 * 1000L, 3);
        System.out.println(limiter.outOfLimit());
        System.out.println(limiter.outOfLimit());
        Thread.sleep(990L);
        System.out.println(limiter.outOfLimit());
        System.out.println(limiter.outOfLimit());
        System.out.println(limiter.outOfLimit());
        Thread.sleep(990L);
        System.out.println(limiter.outOfLimit());
        System.out.println(limiter.outOfLimit());
        Thread.sleep(990L);
        System.out.println(limiter.outOfLimit());
        Thread.sleep(990L);
        System.out.println(limiter.outOfLimit());
        System.out.println(limiter.outOfLimit());
        System.out.println(limiter.outOfLimit());
}

结果

1
2
3
4
5
6
7
8
9
10
11
true
true
true
false
false
false
false
true
true
true
false

缺点

滑动时间窗算法虽然解决了 固定窗口算法 的临界问题，但是程序一旦到达限流次数后，程序的操作会被拒绝，会丢失相应的数据，所以这种算法一般用于对外的openAPI中，对于系统内部的业务实现，其实并不友好。