《分布式IM系统》大后端平台-通用模型-第06节：滑动窗口IP校验规则的设计和实现

作者：冰河
星球：http://m6z.cn/6aeFbs (opens new window)
博客：https://binghe.gitcode.host (opens new window)
文章汇总：https://binghe.gitcode.host/md/all/all.html (opens new window)
源码获取地址：https://t.zsxq.com/0dhvFs5oR (opens new window)
课程视频：https://t.zsxq.com/15xid8Zxy (opens new window)

沉淀，成长，突破，帮助他人，成就自我。

• 本节难度：★★☆☆☆
• 本节重点：基于通用拦截器规则链设计和实现滑动窗口IP的校验规则，掌握滑动窗口IP校验规则的设计和实现，掌握在通用拦截器规则链上新增具体校验规则的方法，并能够将其灵活应用到自身实际项目中。
• 课程视频：https://t.zsxq.com/15xid8Zxy (opens new window)

大家好，我是冰河~~

大后端平台作为用户访问分布式IM即时通讯系统的入口，在某种程度上，其访问流量是不容忽视的，为了避免高并发大流量的场景压垮大后端平台，一种简单粗暴的方式就是对访问的流量进行限流。一想到限流，很多小伙伴可能会想到在一段时间内限制访问频次，这种方式是可行的，但稍不注意，就可能会造成流量呈现忽高忽低的现象。所以，此时我们可以使用滑动窗口的原理来实现限流校验规则。

注意：有关各种限流的架构设计和落地方案，在《Seckill秒杀系统》 (opens new window) 专栏中有详细的介绍，包括：单机限流、分布式流控、业务网关限流、流量网关限流等。大家系统性可以学习《Seckill秒杀系统》 (opens new window) 中的限流架构设计和落地方案，这里不再赘述。

一、前言

在前面的文章中，我们设计和实现了通用的拦截器规则链，并基于通用的拦截器规则链实现了XSS漏洞校验规则，尽最大程度避免系统出现XSS漏洞。考虑到大后端平台作为整个分布式IM即时通讯系统的访问入口，可能会产生高并发访问的现象，为此，我们可以基于滑动窗口原理结合用户终端的IP地址来实现限流。

二、本节诉求

了解滑动窗口的基本原理。基于通用拦截器规则链设计和实现滑动窗口IP的校验规则，掌握滑动窗口IP校验规则的设计和实现，结合自身实际业务场景进行思考，并能够将其灵活应用到自身实际项目中。

三、滑动窗口简单介绍

滑动窗口（Sliding Window）是一种常用的算法思想，常用于解决字符串和数组相关的问题。

滑动窗口的基本思想是维护一个窗口，通过移动窗口的起始位置和结束位置来解决问题。在解决问题的过程中，我们可以根据实际情况来调整窗口的大小和位置。

具体来说，滑动窗口的流程如下：

• 初始化窗口的起始位置和结束位置。
• 将窗口内的元素进行处理，得到当前的结果。
• 根据结果调整窗口的大小和位置，使得窗口继续覆盖需要处理的区域。
• 重复 2 和 3，直到窗口覆盖完整个需要处理的区域。

滑动窗口可以应用于很多问题，例如：

• 找到字符串中的最长不含重复字符的子串；
• 在数组中找到满足某个条件的子数组；
• 给定两个字符串 s 和 t，在 s 中找到包含 t 所有字符的最小子串。

我们也可以使用Java来实现一个简单的滑动窗口的示例，如下所示。

public class SlidingWindow {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);
        System.out.println(Arrays.toString(result));
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int ri = 0; // 记录结果数组的索引

        Deque<Integer> deque = new LinkedList<>(); // 使用双端队列保存窗口内元素的索引
        
        for (int i = 0; i < n; i++) {
            // 在窗口前面删除超出窗口范围的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // 在窗口后面删除小于当前元素的元素，保证队列中存储的是递减的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            // 将当前元素的索引添加到队列中
            deque.offerLast(i);
            
            // 当窗口达到大小 k 时，记录当前窗口的最大值
            if (i >= k - 1) {
                result[ri++] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

在该示例中，我们使用双端队列来保存窗口内元素的索引。通过维护一个递减的窗口，可以保证队列的头部元素始终是当前窗口的最大值。在遍历数组时，我们根据窗口的大小进行相应的操作，包括删除超出窗口范围的元素、删除小于当前元素的元素以及添加当前元素的索引。当窗口达到大小 k 时，我们记录当前窗口的最大值，并将其存入结果数组中。

四、滑动窗口IP校验规则

查看完整文章

加入冰河技术 (opens new window)知识星球，解锁完整技术文章与完整代码