限流算法之固定窗口与滑动窗口

1.固定窗口算法

  使用固定窗口实现限流的思路大致为，将某一个时间段当做一个窗口，在这个窗口内存在一个计数器记录这个窗口接收请求的次数，每接收一次请求便让这个计数器的值加一,如果计数器的值大于请求阈值的时候，即开始限流。当这个时间段结束后，会初始化窗口的计数器数据，相当于重新开了一个窗口重新监控请求次数。

package com.example.demo;
 
import java.util.Date;
 
public class FixedWindow {
 
	private long time = new Date().getTime();
 
	private Integer count = 0; // 计数器
 
	private final Integer max = 100; // 请求阈值
 
	private final Integer interval = 1000; // 窗口大小
 
	public boolean trafficMonitoring() {
 
		long nowTime = new Date().getTime();
 
		if (nowTime < time + interval) {
			// 在时间窗口内
			count++;
 
			return max > count;
 
		} else {
			time = nowTime; // 开启新的窗口
 
			count = 1; // 初始化计数器,由于这个请求属于当前新开的窗口，所以记录这个请求
 
			return true;
		}
	}
 
}

        由上面的代码我们可以看出，固定窗口可以对一段时间的流量就行监控，但是有一个致命的问题，就是我们监控流量都是指时间段而不是具体的某一个时间，假设我们的窗口时间为一分钟，当一分钟后会切换到另外一个窗口重新监控。这个切换就有可能出现问题。假设我们在第一个窗口的最后十秒发了100个请求，在第二个窗口开始的时候也可以发100个请求，那么在这二十秒时间内服务器就会接收到200个请求，这样很有可能会使服务器接收的请求过多而挂掉。所以就出现了固定窗口的优化版，滑动窗口来解决这个问题。

 2.滑动窗口

      滑动窗口为固定窗口的改良版，解决了固定窗口在窗口切换时会受到两倍于阈值数量的请求，滑动窗口在固定窗口的基础上，将一个窗口分为若干个等份的小窗口，每个小窗口对应不同的时间点，拥有独立的计数器，当请求的时间点大于当前窗口的最大时间点时，则将窗口向前平移一个小窗口（将第一个小窗口的数据舍弃，第二个小窗口变成第一个小窗口，当前请求放在最后一个小窗口），整个窗口的所有请求数相加不能大于阀值。

       由上图我们可以看出每次窗口只是做了平移，舍弃第一个窗口，将最新的请求放置到最后的窗口，这样就保证了这滑动窗口的时间内对流量的监控。

      java代码实现如下：

package com.example.demo;
 
import java.util.Date;
 
public class SlidingWindow {
 
	private long[][] arr = { { 0 }, { 0 }, { 0 }, { 0 }, { 0 }, { 0 } };
 
	private final int max = 100;
 
	private long size = 600000;// 窗口大小
 
	private long time = new Date().getTime();// 窗口开始时间
 
	public boolean trafficMonitoring() {
 
		long nowTime = new Date().getTime();// 请求进来的时间
 
		// 计算坐标
		long result = (nowTime - time) % 10000;
 
		int index = 0;
 
		if (result == 0) {
			index = (int) (nowTime / time);
		} else {
 
			index = (int) (nowTime / time + 1);
		}
 
		if (index > arr.length) {
			// 不在窗口内，将滑动窗口平移
			for (int i = 0; i < index - arr.length; i++) {
				// 将数组平移
				for (int j = 0; j < arr.length - 1; j++) {
 
					arr[j][0] = arr[j + 1][0];
				}
				// 将起始时间也向前推进一个窗口
				time += 10000;
			}
			// 本次插入的窗口为最后一个窗口
			index = arr.length - 1;
		}
		// 计算窗口总的请求数是否小于阈值
		int total = 0;
		for (int i = 0; i < arr.length; i++) {
			total += arr[i][0];
		}
		if (total > max) {
			return false;
		}
		// 获取小窗口目前的请求值
		long count = arr[index - 1][0];
		// 加上本次请求数
		arr[index - 1][0] = count + 1;
 
		return true;
	}
 
}