代码实现滑动窗口限流

r囧r小猫 2023-10-03 15:24 15阅读 0赞

#### 代码实现滑动窗口限流 ####

*  代码
 *  思路

## 代码 ##

package 限流;
    
    import java.time.LocalTime;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Random;
    import java.util.concurrent.ConcurrentHashMap;
    
    /**
     * Created by yazai
     * Date: 13:25 2021/8/28
     * Description: 简单版滑动窗口限流
     * 本限流工具只适用于单机版，如果想要做全局限流，可以按本程序的思想，用redis的List结构去实现
     */
    public class SlideWindow {
        
    
        /**
         * 队列id和队列的映射关系，队列里面存储的是每一次通过时候的时间戳，这样可以使得程序里有多个限流队列
         */
        private volatile static Map<String, List<Long>> MAP = new ConcurrentHashMap<>();
    
        private SlideWindow() {
        
        }
    
        public static void main(String[] args) throws InterruptedException {
        
            while (true) {
        
                // 任意10秒内，只允许2次通过
                System.out.println(LocalTime.now().toString() + SlideWindow.isGo("ListId", 1000, 10000L));
                // 睡眠0-10秒
                Thread.sleep(1000 * new Random().nextInt(10));
            }
        }
    
        /**
         * 滑动时间窗口限流算法
         * 在指定时间窗口，指定限制次数内，是否允许通过
         *
         * @param listId     队列id
         * @param count      限制次数
         * @param timeWindow 时间窗口大小
         * @return 是否允许通过
         */
        public static synchronized boolean isGo(String listId, int count, long timeWindow) {
        
            // 获取当前时间
            long nowTime = System.currentTimeMillis();
            // 根据队列id，取出对应的限流队列，若没有则创建
            List<Long> list = MAP.computeIfAbsent(listId, (k) -> {
        
                return new LinkedList<>();
            });
            // 如果队列还没满，则允许通过，并添加当前时间戳到队列开始位置
            if (list.size() < count) {
        
                list.add(0, nowTime);
                return true;
            }
    
            // 队列已满（达到限制次数），则获取队列中最早添加的时间戳
            Long farTime = list.get(count - 1);
            // 用当前时间戳 减去 最早添加的时间戳
            if (nowTime - farTime <= timeWindow) {
        
                // 若结果小于等于timeWindow，则说明在timeWindow内，通过的次数大于count
                // 不允许通过
                return false;
            } else {
        
                // 若结果大于timeWindow，则说明在timeWindow内，通过的次数小于等于count
                // 允许通过，并删除最早添加的时间戳，将当前时间添加到队列开始位置
                list.remove(count - 1);
                list.add(0, nowTime);
                return true;
            }
        }
    
    }

## 思路 ##

这里画图做说明，为什么这样可以做到滑动窗口限流，假设10秒内允许通过5次  
1.这条线就是队列list，当第一个事件进来，队列大小是0，时间是第1秒：  
![在这里插入图片描述][d8cdcf00f7c54781b19c6d02077f98a9.png]  
2.因为size=0，小于5，都没有到限制的次数，完全不用考虑时间窗口，直接把这次事件的时间戳放到0的位置：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16]  
3.第2.8秒的时候，第二个事件来了。因为此时size=1，还是小于5，把这次事件的时间戳放到0的位置，原来第1秒来的事件时间戳会往后移动一格：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
4.陆续的又来了3个事件，队列大小变成了5，先来的时间戳依次向后移动。此时，第6个事件来了，时间是第8秒：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
5.因为size=5，不小于5，此时已经达到限制次数，以后都需要考虑时间窗口了。所以取出位置4的时间（离现在最远的时间），和第6个事件的时间戳做比较：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
6.得到的差是7秒，小于时间窗口10秒，说明在10秒内，来的事件个数大于5了，所以本次不允许通过：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16 4]

[d8cdcf00f7c54781b19c6d02077f98a9.png]: https://img-blog.csdnimg.cn/d8cdcf00f7c54781b19c6d02077f98a9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/e5f9080a9be64062b80f8b91559b1cea.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAZkZlZS1vcHM=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/61daee3525c64d2e9e3e2ec529b01b84.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAZkZlZS1vcHM=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/d5030f6e422d4d12b4ff131d61d21f71.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAZkZlZS1vcHM=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/0339d622f87b42ce8f204e40341bec99.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAZkZlZS1vcHM=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAZkZlZS1vcHM_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/909e1e4f85414ddaa0955f060bad0709.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAZkZlZS1vcHM=,size_20,color_FFFFFF,t_70,g_se,x_16