【校招VIP】翻译翻译，什么是滑动窗口- 校招VIP

转载声明：文章来源：https://blog.csdn.net/Mr_YanMingXin/article/details/121320393

1 滑动窗口的概念

滑动窗口在计算机科学领域中我认为有两层概念，一种是计算机网络中的滑动窗口协议，另一种则是滑动窗口算法,他们在计算机科学领域都有非常广泛的应用，接下来我将用一篇文章来讲述滑动窗口协议和滑动窗口算法在计算机网络和软件编程领域的应用场景和原理，开始表演~

1.1 滑动窗口协议

在TCP网络连接和数据传输中，为了保证避免拥塞的发生，对网络数据传输进行流量控制，该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认。因此该协议可以加速数据的传输，提高网络吞吐量。

1.2 滑动窗口算法

与滑动窗口协议的概念基本相同，只是应用场景不一样，是在给定特定窗口大小的数组或字符串上执行要求的操作。

2 详解滑动窗口协议在TCP网络中的应用原理

2.1 如果没有滑动窗口会怎样？

众所周知TCP是点对点连接，在TCP中只有两个角色，Client和Server，因此发送数据包就要一边发一边接，画图表示：

问题分析：

如果在单包传输中，client端发送数据之后没有得到响应，则第二次发送就会收到影响，或发送异常或接收异常，在多包传输中，如果接收包也出现异常，则必将影响同时发送的其他的数据包（或是次序或是内容）。因此我们需要一个协议或算法来实现安全性和吞吐量之前的权衡，下面就接收滑动窗口的引入。

2.2 滑动窗口引入和作用

图中有4个类型的框框，分别代表着一个数据包的四种状态，为了保证数据包发送和接收的顺序性，数据包必须按照顺序发送和接收，因此窗口的大小就意味着网络传输的吞吐量。

如何解决丢包情况？

如果对方的ACK报文在响应过程中丢失，那么解决方法就是超时重传，超时重传的核心目的也是保护报文发送的顺序性，因此我们也很容易的能总结出滑动窗口的一个缺陷所在：必须要保证顺序性

3 详解滑动窗口算法在高并发限流领域的应用原理

限流问题是在高并发系统设计中躲不开的问题之一，为什么要限流？

因为在短时间的高并发下，系统的承载能力有限，而这种高并发又是短时的，如果永久性的增加系统的资源来应对短时间的高并发，显然是得不偿失的，因此我们需要有一套专门应对短时间内高并发的算法，让系统能够最大限度的接收和处理响应，才是我们最终的目的。

正常情况：

高并发环境下：

3.1 Java实现滑动窗口算法基本原理

编程中的滑动窗口相比网络传输而言较为简单一些，主要是大部分情况都不需要考虑经过窗口部分数据的响应情况，只需要安装部分的条件向一定的方向进行“滑动”。

3.2 Java实现滑动窗口算法代码

问题场景：

力扣题https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

解决：

/**
 * 滑动窗口算法
 *
 * @param str
 * @return
 */
public int lengthOfLongestSubstring(String str) {
    int n = str.length();
    Set<Character> set = new HashSet<>();
    int ans = 0, i = 0, j = 0;
    //窗口的左边是i，右边是j，下列算法将窗口的左右移动，截取出其中一段
    while (i < n && j < n) {
        //如果set中不存在该字母，就将j+1，相当于窗口右边向右移动一格，左边不动
        if (!set.contains(str.charAt(j))) {
            set.add(str.charAt(j++));
            //记录目前存在过的最大的子字符长度
            ans = Math.max(ans, j - i);
            //如果set中存在该字母，则将窗口左边向右移动一格，右边不动，直到该窗口中不存在重复的字符
        } else {
            set.remove(str.charAt(i++));
        }
    }
    return ans;
}

3.3 使用滑动窗口进行限流

/**
 * @desc: 滑动窗口算法
 * @author: YanMingXin
 * @create: 2021/10/9-10:43
 **/
public class Test01 {

    /**
     * 数据包队列
     */
    private ConcurrentLinkedQueue<Long> queue = new ConcurrentLinkedQueue<>();

    /**
     * 间隔秒数
     */
    private int rate;

    /**
     * 最大限流
     */
    private int max;

    public Test01(int max, int rate) {
        this.rate = rate;
        this.max = max;
        /**
         * 执行清理queue任务
         */
        new Thread(() -> {
            while (true) {
                try {
                    // 等待 间隔秒数-1 执行清理操作
                    Thread.sleep((rate - 1) * 1000L);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                clean();
            }
        }).start();
    }


    /**
     * 获取令牌，并且添加时间
     */
    public void take() {
        long start = System.currentTimeMillis();
        try {
            int size = sizeOfValid();
            if (size > max) {
                System.err.println("超限");
            }
            synchronized (queue) {
                if (sizeOfValid() > max) {
                    System.err.println("超限:Queue中有 " + queue.size() + " 最大数量 " + max);
                }
                this.queue.offer(System.currentTimeMillis());
            }
            System.out.println("Queue中有 " + queue.size() + " 最大数量 " + max);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public int sizeOfValid() {
        Iterator<Long> it = queue.iterator();
        Long ms = System.currentTimeMillis() - rate * 1000;
        int count = 0;
        while (it.hasNext()) {
            long t = it.next();
            if (t > ms) {
                // 在当前的统计时间范围内
                count++;
            }
        }
        return count;
    }

    /**
     * 清理过期的时间
     */
    public void clean() {
        Long c = System.currentTimeMillis() - rate * 1000;
        Long tl = null;
        while ((tl = queue.peek()) != null && tl < c) {
            System.out.println("clean data ...");
            queue.poll();
        }
    }

    public static void main(String[] args) {
        final Test01 timeWindow = new Test01(20, 3);
        // 测试3个线程
        for (int i = 0; i < 3; i++) {
            new Thread(() -> {
                while (true) {
                    try {
                        Thread.sleep(new Random().nextInt(20) * 100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    timeWindow.take();
                }
            }).start();
        }
    }
}