固定窗口限流

固定窗口算法通过在单位时间内维护一个计数器，能够限制在每个固定的时间段内请求通过的次数，以达到限流的效果。

算法实现起来也比较简单，可以通过构造方法中的参数指定时间窗口大小以及允许通过的请求数量，当请求进入时先比较当前时间是否超过窗口上边界，未越界且未超过计数器上限则可以放行请求。

package com.example.limit.service;

/**
 * @author linqinyong@leelen.cn
 * @version 1.0.0
 * @ClassName TrafficLimiter.java
 * @Description
 * @createTime 2024年03月12日 14:45:00
 */
public interface TrafficLimiter {
    Boolean limit();
}

package com.example.limit.service;

/**
 * @author linqinyong@leelen.cn
 * @version 1.0.0
 * @ClassName CounterLiniter.java
 * @Description 计数器限流
 * @createTime 2024年03月12日 15:05:00
 */
public class CounterLimiter implements TrafficLimiter {
    private long timeStamp = System.currentTimeMillis();
    private int reqCount;//请求数
    private int limiNum = 100;//每秒限流的最大请求数
    private long interval = 1000L;//时间窗口时长，单位ms

    @Override
    public synchronized Boolean limit() {

        long now = System.currentTimeMillis();
        if (now < timeStamp + interval) {//在当前时间窗口内
            //判断当前时间窗口请求数加1是否超过每秒限流的最大请求数
            if (reqCount + 1 > limiNum) {
                return true;
            }
            reqCount++;
            return false;

        } else {//开启新的时间窗口
            timeStamp = now;
            //重置计数器
            reqCount = 1;
            return false;
        }

    }
}

滑动窗口限流

滑动窗口算法在固定窗口的基础上，进行了一定的升级改造。它的算法的核心在于将时间窗口进行了更精细的分片，将固定窗口分为多个小块，每次仅滑动一小块的时间。

并且在每个时间段内都维护了单独的计数器，每次滑动时，都减去前一个时间块内的请求数量，并再添加一个新的时间块到末尾，当时间窗口内所有小时间块的计数器之和超过了请求阈值时，就会触发限流操作。

package com.example.limit.service;

import java.util.LinkedList;

/**
 * @author linqinyong@leelen.cn
 * @version 1.0.0
 * @ClassName SlidingTimeWindowLimiter.java
 * @Description 滑动窗口限流
 * @createTime 2024年03月12日 15:13:00
 */
public class SlidingTimeWindowLimiter implements TrafficLimiter {


    //服务在最近1秒内的访问次数，可以放在redis中，实现分布式系统的访问计数
    private int reqCount;
    //使用LinkedList来记录滑动窗口的10个格子
    private LinkedList<Integer> slots = new LinkedList<>();
    private int limitNum = 100;//每秒限流的最大请求数
    private long windowLength = 100L;//滑动时间窗口里的每个格子的时间长度，单位ms
    private int windowNum = 10;//滑动时间窗口里的格子数量

    public SlidingTimeWindowLimiter() {
        slots.addLast(0);
        new Thread(() -> {
            while (true) {
                try {
                    Thread.sleep(windowLength);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                slots.addLast(0);
                if (slots.size() > windowNum) {
                    reqCount = reqCount - slots.peekFirst();
                    slots.removeFirst();
                    System.out.println("滑动格子：" + reqCount);
                }
            }
        }).start();
    }

    @Override
    public synchronized Boolean limit() {
        if ((reqCount + 1) > limitNum) {
            return true;
        }
        slots.set(slots.size() - 1, slots.peekLast() + 1);
        reqCount++;
        return false;
    }


}

漏桶限流

为了应对流量激增的问题，后续又衍生出了漏桶算法，用专业一点的词来说，漏桶算法能够进行流量整形和流量控制。

漏桶是一个很形象的比喻，外部请求就像是水一样不断注入水桶中，而水桶已经设置好了最大出水速率，漏桶会以这个速率匀速放行请求，而当水超过桶的最大容量后则被丢弃。

package com.example.limit.service;

/**
 * @author linqinyong@leelen.cn
 * @version 1.0.0
 * @ClassName LeakyBucketLimiter.java
 * @Description 漏桶限流
 * @createTime 2024年03月12日 14:59:00
 */
public class LeakyBucketLimiter implements TrafficLimiter {
    private long timeStamp = System.currentTimeMillis();
    private long capacity = 100;//桶的容量
    private long rate = 10;//水漏出的速度（每秒系统能处理的请求数）
    private long water = 20;//当前水量（当前累积请求数）


    @Override
    public synchronized Boolean limit() {
        long now = System.currentTimeMillis();
        water = Math.max(0, water-((now - timeStamp)/1000)*rate);//先执行漏水，计算生于水量
        timeStamp = now;
        if ((water +1)<=capacity) {
            //水还未满，加水
            water++;
            System.out.println();
            return false;
        } else {
            //水满，聚聚加水
            return true;
        }
    }

}

令牌桶限流

令牌桶算法是基于漏桶算法的一种改进，主要在于令牌桶算法能够在限制服务调用的平均速率的同时，还能够允许一定程度内的突发调用。

它的主要思想是系统以恒定的速度生成令牌，并将令牌放入令牌桶中，当令牌桶中满了的时候，再向其中放入的令牌就会被丢弃。而每次请求进入时，必须从令牌桶中获取一个令牌，如果没有获取到令牌则被限流拒绝。

假设令牌的生成速度是每秒100个，并且第一秒内只使用了70个令牌，那么在第二秒可用的令牌数量就变成了130，在允许的请求范围上限内，扩大了请求的速率。当然，这里要设置桶容量的上限，避免超出系统能够承载的最大请求数量。

package com.example.limit.service;

/**
 * @author linqinyong@leelen.cn
 * @version 1.0.0
 * @ClassName TokenBucketLimiter.java
 * @Description 令牌桶限流
 * @createTime 2024年03月12日 14:44:00
 */
public class TokenBucketLimiter implements TrafficLimiter {
    private long timeStamp = System.currentTimeMillis();
    private long capacity = 100;//桶的容量
    private long rate = 10;//令牌是否速度
    private long tokens = 20;//当前令牌数量


    @Override
    public synchronized Boolean limit() {
        long now = System.currentTimeMillis();
        //先添加令牌
        tokens = Math.min(capacity, tokens + (now - timeStamp) * rate);
        timeStamp = now;
        if (tokens < 1) {
            //若不到1个令牌，则拒绝
            return true;
        } else {
            //还有令牌，领取令牌
            tokens--;
            return false;
        }
    }
}