滑动窗口算法

实现思路：

1. 把时间单位划分为多个区间，一般都是均分为多个小的时间段
2. 每个区间都有一个计数器，有一个请求落在该区间，则该区间内的计数器 + 1
3. 没过一个时间段，时间窗口就会往右滑动一个，抛弃最老的一个区间并重置它的计数器，并纳入新的一个区间
4. 拦截所有请求执行canPass操作，计算整个时间窗口内的请求总数需要累计所有时间片段的计数器，如果计数总和超过了限制数量，则落在当前窗口的请求都会被丢弃和拒绝
5. 时间窗口划分越细，并且按照时间“滑动”，流量控制就越平滑

public class SlidingWindowRateLimit implements RateLimit,Runnable{
    
    //阈值
    private Integer limitCount;

    //当前通过的请求数
    private AtomicInteger passCount;

    //窗口数
    private Integer windowSize;

    //每个窗口时间间隔大小
    private long windowPeriod;
    private TimeUnit timeUnit;
    private Window[] windows;
    private volatile Integer windowIndex = 0;
    private Lock lock = new ReentrantLock();

    public SlidingWindowRateLimit(Integer limitCount) {
        this(limitCount,5, 200, TimeUnit.MILLISECONDS);
    }

    public SlidingWindowRateLimit(Integer limitCount, Integer windowSize, long windowPeriod, TimeUnit timeUnit) {
        this.limitCount = limitCount;
        this.windowSize = windowSize;
        this.windowPeriod = windowPeriod;
        this.timeUnit = timeUnit;
        this.passCount = new AtomicInteger(0);
        this.initWindows(windowSize);
        this.startRestTask();
    }

    private ScheduledExecutorService scheduledExecutorService;
    private void startRestTask(){
        scheduledExecutorService = Executors.newSingleThreadScheduledExecutor();
        scheduledExecutorService.scheduleAtFixedRate(this, 0, windowPeriod, timeUnit);
    }

    private void initWindows(Integer windowSize){
        windows = new Window[windowSize];
        for (int i = 0; i < windowSize; i++){
            windows[i] = new Window();
        }
    }

    @Override
    public boolean canPass() throws RuntimeException {
        lock.lock();;
        if(passCount.get() > limitCount){
            throw new RuntimeException();
        }
        windows[windowIndex].passCount.incrementAndGet();
        passCount.incrementAndGet();
        lock.unlock();
        return true;
    }

    @Override
    public void run() {
        //获取当前窗口索引
        Integer curIndex = (windowIndex + 1) % windowSize;
        //重置当前窗口索引的通过数量，并获取上一次通过数量
        Integer count = windows[curIndex].passCount.getAndSet(0);
        windowIndex = curIndex;
        //总通过数量减去 - 当前窗口上次通过数量
        passCount.addAndGet(-count);
    }

    public static void main(String[] args) throws InterruptedException {
        SlidingWindowRateLimit slidingWindowRateLimit = new SlidingWindowRateLimit(10);
        for(int i = 0; i < 10000; i++){
            Thread.sleep(100);
            if(slidingWindowRateLimit.canPass()){
                System.out.println("通过第【" + i + "】个请求");
            }
        }
    }
}

class Window{
    public AtomicInteger passCount;
    public Window(){
        this.passCount = new AtomicInteger(0);
    }
}