滑动窗口计数器算法.md

升级

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

概念

固定窗口计数器算法的升级版。

• 把时间以一定比例分片：每分钟处理60个请求，我们可以把1分钟分为60个窗口。
• 每隔1秒移动一次，每个窗口一秒只能处理 <= (请求数)/窗口数)的请求。
• 如果当前窗口的请求计数总和超过了限制的数量的话就不再处理其他请求。

当滑动窗口的格子划分的越多，滑动窗口的滚动就越平滑，限流的统计就会越精确。

在每次有访问进来时，我们判断前N个单位时间内的总访问量是否超过了设置的阈值，并对当前时间片上的请求数+1。

队列实现方式：

package com.guava.limit.jdk;

import lombok.extern.slf4j.Slf4j;

import java.util.Iterator;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * 滑动窗口：原理演示
 * @author lizhifu
 */
@Slf4j
public class SlidingWindow {
    /**
     * 窗口：存放每个请求的时间
     * ConcurrentLinkedQueue 是一个基于链接节点的无界线程安全的队列，
     * 按照先进先出原则对元素进行排序。新元素从队列尾部插入，而获取队列元素，则需要从队列头部获取。
     */
    private ConcurrentLinkedQueue<Long> queue = new ConcurrentLinkedQueue<Long>();
    /**
     * 单个窗口时间：单位秒
     */
    private int seconds;
    /**
     * 最大限流数,例如限制1分钟内100个请求
     */
    private int maxLimit;
    public SlidingWindow(int maxLimit,int seconds){
        this.maxLimit = maxLimit;
        this.seconds = seconds;
    }

    /**
     * 获取限流
     * @return
     */
    public void tryAcquire(){
        clean();
        //开始时间
        long currentTimeMillis = System.currentTimeMillis();
        int size = count();
        if (size > maxLimit) {
            throw new RuntimeException("超过限流大小");
        }
        log.info("队尾添加元素{}",currentTimeMillis);
        queue.offer(currentTimeMillis);

    }
    /**
     * 统计请求请求总数
     * @return
     */
    public int count() {
        Iterator<Long> it = queue.iterator();
        //获取间隔时间:获取有效的时间窗口
        Long ms = System.currentTimeMillis() - seconds * 1000;
        int count = 0;
        while (it.hasNext()) {
            long t = it.next();
            if (t > ms) {
                count++;
            }
        }
        log.info("元素总数为{}",count);
        return count;
    }
    public void clean(){
        //当前时间 - 单个窗口的时间
        //等于是滑动第一个窗口的时间范围
        Long c = System.currentTimeMillis() - seconds * 1000;
        Long tl = null;
        //获取头部元素:时间
        while ((tl = queue.peek()) != null && tl < c) {
            Long e = queue.poll();
            log.info("移除元素{}",e);
        }
    }
}

测试方法：

package com.guava.limit;

import com.guava.limit.jdk.SlidingWindow;

/**
 * SlidingWindow
 *
 * @author lizhifu
 * @date 2021/1/14
 */
public class SlidingWindowTest {
    public static void main(String[] args) throws InterruptedException {
        SlidingWindow slidingWindow = new SlidingWindow(10,1);
        for (int i = 0; i < 20; i++) {
            slidingWindow.tryAcquire();
            Thread.sleep(500L);
        }
    }
}

其实就是固定技术法的细密度实现。