四种限流算法

四种限流算法

为什么要限流

限流是为了防止系统突然收到大量请求，后台面对大量并发请求对cpu和内存，网络io产生巨大压力，可能将一些服务如mysql，redis等打崩，引发系统故障，服务瘫痪。

固定窗口：Fixed Window Rate Limiting Algorithm

将时间分为固定窗口，将请求按时间顺序放入时间窗口，如果超过设置时间窗口的阈值就返回限流结果，但是在两个时间窗口替换间隙可能会有2n请求并发。

优点：实现简单，便于理解

缺点：存在明显的临界问题，切换间隙可产生产生2n请求：0.75秒-1.0秒产生n个请求，刷新，1.0-1.5s又产生n个请求，这n个请求各自窗口满足要求，但是再它门组成的窗口中并发量达到了2n

public class FixedWindow {
    //窗口大小
    private final static Integer timeUnit=1000;
    //请求计数
    private  AtomicInteger count=new AtomicInteger();

    private  Long lastTime=0L;

    private Integer  threshold=10;

    public boolean fixedWindow()
    {
          long currentTime=System.currentTimeMillis();
          if(currentTime-lastTime>timeUnit)
          {
              count.set(0);
              lastTime=currentTime;
          }
          if(count.get()>=threshold) //初始计数是0 ，所以是大于等于刚好执行十次
          {
              return false;
          }
          count.getAndIncrement();
          return true;
    }

    public static void main(String[] args) {
        FixedWindow fixedWindow=new FixedWindow();
        for(int i=0;i<20;i++)
        {
            System.out.println(fixedWindow.fixedWindow());
        }
    }

}

滑动窗口：Sliding Windows Algorithm

将单位时间周期又划分成n个小周期，分别根据每个小周期内接口的访问次数，并根据时间滑动自动删除过期的小周期（tcp就是根据这个来实现对发送字节的大小控制）

优点： 简单易懂，精度高可以调整时间粒度来调节限流效果，可拓展性，可与和其他限流算法结合使用

缺点：无法应对突发请求，突发请求会被大量拒绝，会损失大量请求

public class SlidingWindow {


    private final int maxRequests; // 最大请求数
    private final long timeWindowMillis; // 时间窗口（毫秒）
    private final Queue<Long> requests; // 请求队列

    public SlidingWindow(int maxRequests, long timeWindowMillis) {
        this.maxRequests = maxRequests;
        this.timeWindowMillis = timeWindowMillis;
        this.requests = new LinkedList<>();
    }

    public synchronized boolean tryAcquire() {
        // 移除超出时间窗口的请求
        while (!requests.isEmpty() && System.currentTimeMillis() - requests.peek() > timeWindowMillis) {
            requests.poll();
        }

        // 判断当前窗口内的请求数量是否超过最大请求数
        if (requests.size() < maxRequests) {
            // 添加新请求到队列
            requests.offer(System.currentTimeMillis());
            return true;
        } else {
            return false;
        }
    }
    public static void main(String[] args) throws InterruptedException {

        SlidingWindow rateLimiter = new SlidingWindow(5, 1000); // 每秒最多5个请求

        for (int i = 0; i < 20; i++) {
            System.out.println("Request " + (i + 1) + ": " + (rateLimiter.tryAcquire() ? "Accepted" : "Rejected"));
        }

    }
}

漏桶算法：Leaky Bucket Algorithm

控制流入网络的速率速度，以防止网络堵塞。核心思想就是将请求比作小水滴，漏桶看作固定容量的水桶，数据包从顶部进入漏桶，漏桶底部以匀速形式流出数据包。水满则溢，拒绝请求。

优点：可以十分平滑的处理请求，对瞬间增加的请求有一定的承载能力

缺点：需要对请求进行缓存，会增加服务器的内存消耗。面对突发流量无法进行快速处理请求。

public class LeakyBucket {
    private int capacity = 10;
    private int rate = 1;  //每ms多少个
    private int total = 0;
    private long lastTime = System.currentTimeMillis();

    private synchronized boolean leakBucket(Integer water) throws InterruptedException {
        long time=System.currentTimeMillis();
        long escapeTime=time-lastTime;
        long leakWater=escapeTime*rate;
        if(leakWater>0)
        {
            total=(int) Math.max(0,total-leakWater);
            lastTime=time;
        }
        if(total+water>capacity)
        {
            Thread.sleep(4);
            return false;
        }
        total=total+water;
        return true;
    }

    public static void main(String[] args) throws InterruptedException {
        LeakyBucket leakyBucket=new LeakyBucket();
        for (int i = 0; i < 20; i++) {
            System.out.println(leakyBucket.leakBucket(2));
        }
    }
}

令牌桶算法：Token Bucket Algorithm

系统以一定的速率向令牌桶中添加令牌，请求到来时先去尝试获取令牌，拿到令牌就正常请求并消耗这个令牌，拿不到就拒绝服务。

优点：可以应对突发流量，具有弹性处理请求的特点，稳定性好。精度高：可以根据请求动态调节生成令牌桶的速率

缺点：实现复杂，时间精度控制要求比较高

public class TokenBucket {
    private long capacity = 5;//令牌总数
    private long lastTime=System.currentTimeMillis();
    private long  rate=5;//每毫秒发放令牌
    private long  total=capacity;
    private synchronized boolean tokenBucket() throws InterruptedException {
        long now=System.currentTimeMillis();
        long gap=now-lastTime;
        long add=gap*rate;
        if(total<20)
        {
            total=Math.min(total+add,capacity);
            lastTime=now;
        }
        if(total-1<0)
        {
            Thread.sleep(1);
            return false;
        }
        total--;
        return true;
    }

    public static void main(String[] args) throws InterruptedException {
        TokenBucket tokenBucket=new TokenBucket();
        for (int i = 0; i < 20; i++) {
            System.out.println(tokenBucket.tokenBucket());
        }
    }
}