限流算法：滑动时间窗口算法。

谁借莪１个温暖的怀抱￠ 2023-06-25 08:16 3阅读 0赞

本文实现了一种基于java的滑动时间窗口计数器算法

滑动时间窗口计数器算法思想：针对固定时间算法会在临界点存在瞬间大流量冲击的场景，滑动时间窗口计数器算法应运而生。它将时间窗口划分为更小的时间片段，每过一个时间片段，我们的时间窗口就会往右滑动一格，每个时间片段都有独立的计数器。我们在计算整个时间窗口内的请求总数时会累加所有的时间片段内的计数器。时间窗口划分的越细，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70][]

本文代码逻辑：新建一个本地缓存，每5s为一个时间窗口，每1s为一个时间片段，时间片段作为缓存的key，原子类计数器作为缓存的value。每秒发送随机数量的请求，计算每个时间片段的前5秒内的累加请求数量，超出阈值则限流。

@Slf4j
    public class WindowLimiter {
     
        private LoadingCache<Long, AtomicLong> counter =
                CacheBuilder.newBuilder()
                        .expireAfterWrite(10, TimeUnit.SECONDS)
                        .build(new CacheLoader<Long, AtomicLong>() {
                            @Override
                            public AtomicLong load(Long seconds) throws Exception {
                                return new AtomicLong(0);
                            }
                        });
        private ScheduledExecutorService scheduledExecutorService = Executors.newScheduledThreadPool(5);
        //限流阈值
        private long limit = 15;
     
        /**
         * 滑动时间窗口
         * 每隔1s累加前5s内每1s的请求数量，判断是否超出限流阈值
         */
        public void slideWindow() {
            scheduledExecutorService.scheduleWithFixedDelay(() -> {
                try {
                    long time = System.currentTimeMillis() / 1000;
                    //每秒发送随机数量的请求
                    int reqs = (int) (Math.random() * 5) + 1;
                    counter.get(time).addAndGet(reqs);
                    long nums = 0;
                    // time windows 5 s
                    for (int i = 0; i < 5; i++) {
                        nums += counter.get(time - i).get();
                    }
                    log.info("time=" + time + ",nums=" + nums);
                    if (nums > limit) {
                        log.info("限流了,nums=" + nums);
                    }
                } catch (Exception e) {
                    log.error("slideWindow error", e);
                } finally {
                }
            }, 5000, 1000, TimeUnit.MILLISECONDS);
        }
    }

输出结果：

> 20:14:50.083 \[pool-1-thread-3\] INFO com.example.demo.limit.WindowLimiter - time=1574079290,nums=15  
> 20:14:51.114 \[pool-1-thread-3\] INFO com.example.demo.limit.WindowLimiter - time=1574079291,nums=13  
> 20:14:52.119 \[pool-1-thread-3\] INFO com.example.demo.limit.WindowLimiter - time=1574079292,nums=14  
> 20:14:53.121 \[pool-1-thread-3\] INFO com.example.demo.limit.WindowLimiter - time=1574079293,nums=15  
> 20:14:54.126 \[pool-1-thread-3\] INFO com.example.demo.limit.WindowLimiter - time=1574079294,nums=17  
> 20:14:54.127 \[pool-1-thread-3\] INFO com.example.demo.limit.WindowLimiter - 限流了,nums=17  
> 20:14:55.128 \[pool-1-thread-3\] INFO com.example.demo.limit.WindowLimiter - time=1574079295,nums=14  
> 20:14:56.131 \[pool-1-thread-3\] INFO com.example.demo.limit.WindowLimiter - time=1574079296,nums=17  
> 20:14:56.132 \[pool-1-thread-3\] INFO com.example.demo.limit.WindowLimiter - 限流了,nums=17

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191227143418466.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VuX2pva2Vy,size_16,color_FFFFFF,t_70