滑动窗口限流算法实现一

固定算法

原理：固定算法是将时间线分隔成固定大小的时间窗口，每个窗口都会有个计数器，用来记录窗口时间范围内的请求总数，如果窗口的请求总数达到最大限定值，会认定流量超限。比如将窗口大小设为1分钟，每分钟请求最大数为2：

请求在00:00:24时刻到来的时候，会落在窗口1内，计数器值为1，下一个请求在00:00:36时刻，也会落在窗口1内，计数器值+1变成2，第三个请求在00:00:49时刻来到，此时计数器值已达到最大限定值2，请求会被拒掉，最后一个请求在00:01:12到来，会落在窗口2内。

固定算法的缺点

固定算法只能判断单个窗口内的请求总数，但是无法判断相邻的两个窗口，落在相邻窗口的两个请求时间间隔完全有可能在一个窗口时间范围内。比如00:00:58和00:00:59两个时刻各有一个请求过来，窗口1的计数器值为2， 第三个请求在00:01:01到来，会落在窗口2内，但是00:00:58和00:01:01之间没有超过一个单元时间1分钟，但是请求总数已经超过最大限定值2。

滑动窗口算法

为了优化固定算法的缺点，将固定大小的时间窗口分成更小的时间窗口，比如1min的窗口分成6个10s的小窗口。

实现一（简单无脑版）

思路：

1.   使用一个Map：counterMap 用来存储每个时间戳的请求总数
2.   请求到来时，会将单位时间之前（now-timeUnit）的所有请求记录全部清除
3.   统计单位时间timeUnit内的请求总数
4.   判断请求总数是否超过请求阈值capacity，超过则返回false
5.   没有超过,则记录当前时间戳和请求。
1
2
3
4
5

源码：

public class SlidingWindow3 {
    /**
     * 单位时间请求阈值
     */
    private int capacity;
    /**
     * 单位时间/ms
     */
    private long timeUnit;

    /**
     * 时间戳计数器
     */
    private Map<Long,Integer> counterMap = new HashMap<>();

    public SlidingWindow3(int capacity, long timeUnit) {
        this.capacity = capacity;
        this.timeUnit = timeUnit;
    }

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        long start = now-timeUnit;
        Iterator<Map.Entry<Long, Integer>> iterator = counterMap.entrySet().iterator();
        while (iterator.hasNext()){
            if(iterator.next().getKey()<start){
                iterator.remove();
            }
        }
        iterator = counterMap.entrySet().iterator();
        int totalCount = 0;

        while (iterator.hasNext()){
            totalCount += iterator.next().getValue();
        }

        if(totalCount>= capacity){
            return false;
        }
        if(counterMap.containsKey(now)){
            counterMap.put(now,counterMap.get(now)+1);
        }else {
            counterMap.put(now,1);
        }
        return true;
    }
}
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
41
42
43
44
45
46
47

测试

 public static void main(String[] args) throws InterruptedException {
        SlidingWindow3 slidingWindow = new SlidingWindow3(2, 1000);
        for (int j = 0; j < 10; j++) {
            System.out.println("第：" + j + "轮测试");
            int concurrency = 30;
            CyclicBarrier cyclicBarrier = new CyclicBarrier(concurrency);
            for (int i = 1; i <= concurrency; i++) {
                new Thread("Thread:" + i) {
                    @Override
                    public void run() {
                        try {
                            cyclicBarrier.await();
                            if (slidingWindow.tryAcquire()) {
                                System.out.println("name:" + Thread.currentThread().getName() + " get permit");
                            }
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        } catch (BrokenBarrierException e) {
                            e.printStackTrace();
                        }
                    }
                }.start();
            }
            Thread.sleep(3 * 1000L);
        }
    }
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

结果

参考

《Rate-Limiter-Part1》