常见的限流算法及其实现

本文最后更新于 2024年7月24日晚上

限流算法

限流是指在系统面临高并发、大流量请求的情况下，限制新的流量对系统的访问，从而保证系统服务的安全性。常用的限流算法有计数器固定窗口算法、滑动窗口算法、漏斗算法和令牌桶算法，下面将对这几种算法进行分别介绍，并给出具体的实现。

针对软件系统来说，限流就是对请求的速率进行限制，避免瞬时的大量请求击垮软件系统。毕竟，软件系统的处理能力是有限的。如果说超过了其处理能力的范围，软件系统可能直接就挂掉了。

//限流接口
public interface RateLimit {
    //获取访问许可
    boolean getToken();
    boolean getToken(RpcRequest request);
}

计数器固定窗口算法

原理

计数器固定窗口算法是最基础也是最简单的一种限流算法。原理就是对一段固定时间窗口内的请求进行计数，如果请求数超过了阈值，则舍弃该请求；如果没有达到设定的阈值，则接受该请求，且计数加1。当时间窗口结束时，重置计数器为0。

计数器固定窗口算法

优点

实现简单，易于理解。

缺点

流量曲线可能不够平滑，有“突刺现象”

出现突刺现象

一段时间内（不超过时间窗口）系统服务不可用。比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第1ms来了100个请求，然后第2ms-999ms的请求就都会被拒绝，这段时间用户会感觉系统服务不可用。
窗口切换时可能会产生两倍于阈值流量的请求。比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第999ms来了100个请求，窗口前期没有请求，所以这100个请求都会通过。再恰好，下一个窗口的第1ms有来了100个请求，也全部通过了，那也就是在2ms之内通过了200个请求，而我们设定的阈值是100，通过的请求达到了阈值的两倍。

窗口切换导致的流量激增

代码实现

/**
 * @Description 计数器固定窗口算法
 * @author GuoZihan
 * @date 10:11 2024/7/24
 */
public class CounterLimiter implements RateLimit {
    private int windowSize;//窗口大小
    private int limit;//窗口内限流大小
    private AtomicInteger count;//当前窗口的计数器

    public CounterLimiter(int windowSize, int limit) {
        this.limit = limit;
        this.windowSize = windowSize;
        count = new AtomicInteger(0);
        //开启一个线程负责清空count
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    count.set(0);
                    try {
                        Thread.sleep(windowSize);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();
    }
    @Override
    public boolean getToken() {
        int newCount = count.incrementAndGet();
        return newCount > limit ? false : true;
    }

    @Override
    public boolean getToken(RpcRequest request) {
        return false;
    }
}

计数器滑动窗口算法

原理

滑动窗口计数器算法 算的上是固定窗口计数器算法的升级版，限流的颗粒度更小。

滑动窗口计数器算法相比于固定窗口计数器算法的优化在于：它把时间以一定比例分片 。

例如我们的接口限流每分钟处理 60 个请求，我们可以把 1 分钟分为 60 个窗口。每隔 1 秒移动一次，每个窗口一秒只能处理不大于 60(请求数)/60（窗口数） 的请求，如果当前窗口的请求计数总和超过了限制的数量的话就不再处理其他请求。

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

计数器滑动窗口算法

优点

相比于固定窗口算法，滑动窗口计数器算法可以应对突然激增的流量。
相比于固定窗口算法，滑动窗口计数器算法的颗粒度更小，可以提供更精确的限流控制。

缺点

与固定窗口计数器算法类似，滑动窗口计数器算法依然存在限流不够平滑的问题。
相比较于固定窗口计数器算法，滑动窗口计数器算法实现和理解起来更复杂一些。

代码实现

/**
 * @Description  计数器滑动窗口算法
 * @author GuoZihan
 * @date 17:51 2024/7/24
 */
public class CounterSlideWindowLimiter implements RateLimit {
    private int windowSize; //窗口大小，毫秒为单位
    private int limit;//窗口内限流大小
    private int splitNum;//切分小窗口的数目大小
    private int[] counters;//每个小窗口的计数数组
    private int index;//当前小窗口计数器的索引
    private long startTime;//窗口开始时间

    public CounterSlideWindowLimiter(int windowSize, int limit, int splitNum) {
        this.limit = limit;
        this.windowSize = windowSize;
        this.splitNum = splitNum;
        counters = new int[splitNum];
        index = 0;
        startTime = System.currentTimeMillis();
    }
    @Override
    public boolean getToken() {
        return false;
    }

    @Override
    public boolean getToken(RpcRequest request) {
        return false;
    }

    public synchronized boolean tryAcquire() {
        long curTime = System.currentTimeMillis();
        //计算滑动小窗口的数量
        long windowsNum = Math.max(curTime - windowSize - startTime, 0) / (windowSize / splitNum);
        //滑动窗口
        slideWindow(windowsNum);
        int count = 0;
        //计算窗口内的请求次数
        for(int i = 0; i < splitNum; ++i)
            count += counters[i];
        if(count >= limit)
            return false;
        else {
            counters[index]++;
            return true;
        }
    }

    public synchronized void slideWindow(long windowsNum) {
        if (windowsNum == 0)
                return;
        long slideNum = Math.min(windowsNum, splitNum);
        for(int i = 0; i < slideNum; ++i) {
            //把已经滑动过的窗口计数器设为0
            index = (index + 1) % splitNum;
            counters[index] = 0;
        }
        //更新滑动窗口的开始时间
        startTime = startTime + windowsNum * (windowSize / slideNum);
    }
}

漏桶算法

原理

漏斗算法的原理也很容易理解。请求来了之后会首先进到漏斗里，然后漏斗以恒定的速率将请求流出进行处理，从而起到平滑流量的作用。当请求的流量过大时，漏斗达到最大容量时会溢出，此时请求被丢弃。从系统的角度来看，我们不知道什么时候会有请求来，也不知道请求会以多大的速率来，这就给系统的安全性埋下了隐患。但是如果加了一层漏斗算法限流之后，就能够保证请求以恒定的速率流出。在系统看来，请求永远是以平滑的传输速率过来，从而起到了保护系统的作用。

漏桶算法

优点

实现简单，易于理解。
可以控制限流速率，避免网络拥塞和系统过载。

缺点

无法应对突然激增的流量，因为只能以固定的速率处理请求，对系统资源利用不够友好。
桶流入水（发请求）的速率如果一直大于桶流出水（处理请求）的速率的话，那么桶会一直是满的，一部分新的请求会被丢弃，导致服务质量下降。

代码实现

/**
 * @Description 漏桶算法
 * @author GuoZihan
 * @date 17:54 2024/7/24
 */
public class LeakyBucketLimiter implements RateLimit {
    private int capaticy;//漏斗容量
    private int rate;//漏斗速率
    private int left;//剩余容量
    private LinkedList<RpcRequest> requestList;

    public LeakyBucketLimiter(int capaticy, int rate) {
        this.capaticy = capaticy;
        this.rate = rate;
        this.left = capaticy;
        requestList = new LinkedList<>();
        //开启一个线程，以固定速率将漏斗中的请求流出，进行处理
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    if(!requestList.isEmpty()) {
                        RpcRequest request = requestList.removeFirst();
                    }
                    try {
                        Thread.sleep(rate);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();
    }

    @Override
    public boolean getToken() {
        return false;
    }

    @Override
    public boolean getToken(RpcRequest request) {
        if(left <= 0)
            return false;
        else {
            left--;
            requestList.addLast(request);
            return true;
        }
    }
}

令牌桶算法

原理

令牌桶算法是对漏斗算法的一种改进，除了能够起到限流的作用外，还允许一定程度的流量突发。在令牌桶算法中，存在一个令牌桶，算法中存在一种机制以恒定的速率向令牌桶中放入令牌。令牌桶也有一定的容量，如果满了令牌就无法放进去了。当请求来时，会首先到令牌桶中去拿令牌，如果拿到了令牌，则该请求会被处理，并消耗掉拿到的令牌；如果令牌桶为空，则该请求会被丢弃。

令牌桶算法

优点

可以限制平均速率和应对突然激增的流量。
可以动态调整生成令牌的速率。

缺点

如果令牌产生速率和桶的容量设置不合理，可能会出现问题比如大量的请求被丢弃、系统过载。
相比于其他限流算法，实现和理解起来更复杂一些。

代码实现

public class TokenBucketRateLimitImpl implements RateLimit {
    //令牌产生速率（单位为ms）
    private static  int RATE;
    //桶容量
    private static  int CAPACITY;
    //当前桶容量
    private volatile int curCapcity;
    //时间戳
    private volatile long timeStamp=System.currentTimeMillis();
    public TokenBucketRateLimitImpl(int rate,int capacity){
        RATE=rate;
        CAPACITY=capacity;
        curCapcity=capacity;
    }
    @Override
    public synchronized boolean getToken() {
        //如果当前桶还有剩余，就直接返回
        if(curCapcity>0){
            curCapcity--;
            return true;
        }
        //如果桶无剩余，
        long current=System.currentTimeMillis();
        //如果距离上一次的请求的时间大于RATE的时间
        if(current-timeStamp>=RATE){
            //计算这段时间间隔中生成的令牌，如果>2,桶容量加上（计算的令牌-1）
            //如果==1，就不做操作（因为这一次操作要消耗一个令牌）
            if((current-timeStamp)/RATE>=2){
                curCapcity+=(int)(current-timeStamp)/RATE-1;
            }
            //保持桶内令牌容量<=10
            if(curCapcity>CAPACITY) curCapcity=CAPACITY;
            //刷新时间戳为本次请求
            timeStamp=current;
            return true;
        }
        //获得不到，返回false
        return false;
    }

    @Override
    public boolean getToken(RpcRequest request) {
        return false;
    }
}

总结

计数器固定窗口算法实现简单，容易理解。和漏斗算法相比，新来的请求也能够被马上处理到。但是流量曲线可能不够平滑，有“突刺现象”，在窗口切换时可能会产生两倍于阈值流量的请求。而计数器滑动窗口算法作为计数器固定窗口算法的一种改进，有效解决了窗口切换时可能会产生两倍于阈值流量请求的问题。

漏斗算法能够对流量起到整流的作用，让随机不稳定的流量以固定的速率流出，但是不能解决流量突发的问题。令牌桶算法作为漏斗算法的一种改进，除了能够起到平滑流量的作用，还允许一定程度的流量突发。

令牌桶算法一般用于保护自身的系统，对调用者进行限流，保护自身的系统不被突发的流量打垮。如果自身的系统实际的处理能力强于配置的流量限制时，可以允许一定程度的流量突发，使得实际的处理速率高于配置的速率，充分利用系统资源。而漏斗算法一般用于保护第三方的系统，比如自身的系统需要调用第三方的接口，为了保护第三方的系统不被自身的调用打垮，便可以通过漏斗算法进行限流，保证自身的流量平稳的打到第三方的接口上。

参考资料

项目 > 手撕RPC框架

#八股 #限流算法

常见的限流算法及其实现

https://love-enough.github.io/2024/07/24/常见的限流算法及其实现/

作者

GuoZihan

发布于

2024年7月24日

更新于

2024年7月24日

许可协议

熔断器的实现上一篇

常见的负载均衡算法实现下一篇