限流算法(令牌桶&漏桶&计数器)

       个人主页：五敷有你      
 系列专栏：Spring
⛺️稳中求进，晒太阳

业务重的三种情况：突发流量、恶意流量、业务本身需要

限流:   是为了保护自身系统和下游系统不被高并发流量冲垮，导致系统雪崩。

保证系统在可用的情况下尽可能增加进入的请求，其余的请求在排队等待，或者返回友好提示。保证进入系统的用户可以友好使用。

令牌桶算法

令牌桶算法是一个设定的速率产生令牌(token) 并放入令牌通，每次用户请求都得申请令牌。如果令牌不足，则拒绝请求。

        令牌桶算法中新请求到来时会从桶中拿走一个令牌，如果桶内没有i令牌可拿，就拒绝服务。

        当然令牌的数量也是有上限的。令牌的数量与时间和发放速率强相关。时间流逝的时间越长，会不断往桶里加入越多的令牌，如果令牌发送的速度比申请速度快，令牌会放满令牌桶，直到令牌占满令牌桶

令牌桶的算法特点：

好处：可以方便地应对突发出口流量。

比如：可以改变令牌发放速度(需要后端系统能力的提升)，算法能按照新的发送速率调大令牌的发放数量，使得出口突发流量能被处理。

令牌生成的速度固定，消费速度不固定。

代码简单实现：

package ratelimit;import java.util.concurrent.*;import java.util.concurrent.atomic.AtomicInteger;import java.util.logging.Logger;public class TokenBucketLimiter {    //桶的容量    private static int capacity=100;    //令牌生成速度 rate/s    private static final int rate=50;    //令牌数量    private volatile static AtomicInteger tokens=new AtomicInteger(0);    /**     * 开启一个线程，按固定频率放入令牌桶固定个数     */    public static void productTokens(){        ScheduledExecutorService scheduledExecutorService= Executors.newScheduledThreadPool(1);        scheduledExecutorService.scheduleAtFixedRate(()->{            int allTokens = tokens.get()+rate;            //设置当前的tokens数量            tokens.set(allTokens);        },1000,1000,TimeUnit.MILLISECONDS);    }    /**     * true是被限流了     *     * @param needCount     * @return     */    public static synchronized boolean limited(int needCount){        if(tokens.get(){            //现在桶中的水            int water = waterLeaf.get()-leakRate;            //设置当前的水量            waterLeaf.set(Math.max(0,water));        },1,1, TimeUnit.SECONDS);    }    public static synchronized boolean limited(int waterCount){        if(waterLeaf.get()+waterCount>capacity){            //水满了拒绝            return true;        }        waterLeaf.addAndGet(waterCount);        System.out.println("此时漏桶水量有: "+waterLeaf);        return false;    }    public static void main(String[] args) {        //开始漏水        leakWater();        //开启请求        ScheduledExecutorService executorService=Executors.newScheduledThreadPool(5);        AtomicInteger atomicInteger=new AtomicInteger(0);        for(int i=0;i{                try {                    Thread.sleep(100);                } catch (InterruptedException e) {                    throw new RuntimeException(e);                }                String taskName=Thread.currentThread().getName();                boolean limited = limited(1);                if(limited){                    System.out.println(taskName+"请求被拦截，累计拦截次数"+atomicInteger.incrementAndGet());                }else{                    System.out.println(taskName+"请求访问成功！！！");                }            });        }    }}

计数器算法

        计数器算法在一段时间间隔内(时间窗/时间区间)，处理请求的最大数量固定，超过部分不做处理。计数器算法是限流算法中最简单的，也是最容易实现的一种算法。

举个例子：

比如：我们规定对于A接口，我们一分钟访问次数不能超过100个。

可以这么做：

1. 在一开始的时候，我们可以设置一个计数器counter,每当一个请求过来的时候，counter就+1，如果counter的值大于100，并且该请求与第一个请求的间隔在一分钟之内，那么说明请求数过多，拒绝访问；

2. 如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么重置counter,就是这么简单粗暴

问题：临界问题

计数器限流的严重问题：这个算法虽然简单，但是有一个十分致命的问题，就是临界问题

两分钟之间的临界突发200请求，很危险！！！